Two Problems for Sophistication

Peter Bloem, Steven de Rooij, Pieter Adriaans

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review


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.
Original languageEnglish
Title of host publicationAlgorithmic Learning Theory - 26th International Conference, ALT 2015
Number of pages16
ISBN (Print)9783319244853
Publication statusPublished - 2015
Externally publishedYes
Event26th International Conference on Algorithmic Learning Theory (ALT 2015) - Banff, Canada
Duration: 4 Oct 20156 Oct 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference26th International Conference on Algorithmic Learning Theory (ALT 2015)

Cite this