[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

MDL in the Limit

  • Conference paper
Grammatical Inference: Theoretical Results and Applications (ICGI 2010)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 6339))

Included in the following conference series:

  • 821 Accesses

Abstract

We show that within the Gold paradigm for language learning an informer for a superfinite set can cause an optimal MDL learner to make an infinite amount of mind changes. In this setting an optimal learner can make an infinite amount of wrong choices without approximating the right solution. This result helps us to understand the relation between MDL and identification in the limit in learning: MDL is an optimal model selection paradigm, identification in the limit defines recursion theoretical conditions for convergence of a learner.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 35.99
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 44.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Gold, E.M.: Language Identification in the Limit. Information and Control 10(5), 447–474 (1967)

    Article  MATH  Google Scholar 

  2. Grünwald, P.D.: The Minimum Description Length Principle, 570 pages. MIT Press, Cambridge (2007)

    Google Scholar 

  3. Li, M., Vitányi, P.M.B.: An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn. Springer, New York (2008)

    MATH  Google Scholar 

  4. Zeugmann, T., Lange, S.: A Guided Tour Across the Boundaries of Learning Recursive Languages. In: Lange, S., Jantke, K.P. (eds.) GOSLER 1994. LNCS (LNAI), vol. 961, pp. 190–258. Springer, Heidelberg (1995)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Theory of Computer Science Group, IVI, University of Amsterdam, Science Park 107, 1098, XG, Amsterdam, The Netherlands

    Pieter Adriaans

  2. Logica, Prof. W.H. Keesomlaan, 1183, DJ, Amstelveen, The Netherlands

    Wico Mulder

Authors
  1. Pieter Adriaans
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wico Mulder
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Departamento de Sistemas Informáticos y Computatión, Universidad Politécnica de Valencia, Camino de Vera s/n, 46022, Valencia, Spain

    José M. Sempere  & Pedro García  & 

Rights and permissions

Reprints and permissions

Copyright information

© 2010 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Adriaans, P., Mulder, W. (2010). MDL in the Limit. In: Sempere, J.M., García, P. (eds) Grammatical Inference: Theoretical Results and Applications. ICGI 2010. Lecture Notes in Computer Science(), vol 6339. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15488-1_21

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-15488-1_21

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-15487-4

  • Online ISBN: 978-3-642-15488-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation