Rademacher complexity and grammar induction algorithms: what it may (not) tell us

Authors
Publication date 2010
Host editors
  • J.M. Sempere
  • P. García
Book title Grammatical Inference: Theoretical Results and Applications
Book subtitle 10th international colloquium, ICGI 2010, Valencia, Spain, September 13-16, 2010 : proceedings
ISBN
  • 9783642154874
ISBN (electronic)
  • 9783642154881
Series Lecture Notes in Computer Science
Event 10th International Colloquium on Grammatical Inference (ICGI 2010), Valencia, Spain
Pages (from-to) 293-296
Publisher Berlin: Springer
Organisations
  • Faculty of Science (FNWI) - Informatics Institute (IVI)
Abstract This paper revisits a problem of the evaluation of computational grammatical inference (GI) systems and discusses what role complexity measures can play for the assessment of GI. We provide a motivation for using the Rademacher complexity and give an example showing how this complexity measure can be used in practice.
Document type Conference contribution
Language English
Published at https://doi.org/10.1007/978-3-642-15488-1_29
Permalink to this page
Back