- Author
- Year
- 2015
- host editors
-
K. Chaudhuri
C. Gentile
S. Zilles - Title
- Two problems for sophistication
- Event
- 26th International Conference on Algorithmic Learning Theory, ALT 2015
- Book/source title
- Algorithmic Learning Theory
- Book/source subtitle
- 26th International Conference, ALT 2015, Banff, AB, Canada, October 4-6, 2015 : proceedings
- Pages (from-to)
- 379-394
- Number of pages
- 16
- Publisher
- Cham: Springer
- ISBN
- 9783319244853
- ISBN (electronic)
- 9783319244860
- Series
- Lecture Notes in Computer Science, Lecture Notes in Artificial Intelligence, 0302-9743, 1611-3349, 9355
Lecture Notes in Computer Science, Lecture Notes in Artificial Intelligence, 0302-9743, 1611-3349, 9355 - Document type
- Conference contribution
- Faculty
- Faculty of Science (FNWI)
Interfacultary Research - Institute
- Informatics Institute (IVI)
Institute for Logic, Language and Computation (ILLC) - Abstract
-
Kolmogorov complexity measures the amount of information in data, but does not distinguish structure from noise. Kolmogorov’s definition of the structure function was the first attempt to measure only the structural information in data, by measuring the complexity of the smallest model that allows for optimal compression of the data. Since then, many variations of this idea have been proposed, for which we use sophistication as an umbrella term. We describe two fundamental problems with existing proposals, showing many of them to be unsound. Consequently, we put forward the view that the problem is fundamental: it may be impossible to objectively quantify the sophistication.
- URL
- go to publisher's site
- Other links
- Link to publication in Scopus
- Language
- English
- Persistent Identifier
- https://hdl.handle.net/11245.1/73820b56-7045-494a-9800-3cf1ebd88a33
Disclaimer/Complaints regulations
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.