Two Problems for Sophistication

Peter Bloem, Steven de Rooij, Pieter Adriaans

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.
LanguageEnglish
Title of host publicationAlgorithmic Learning Theory - 26th International Conference, ALT 2015
PublisherSpringer/Verlag
Pages379-394
Number of pages16
Volume9355
ISBN (Print)9783319244853
DOIs
StatePublished - 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)
Volume9355
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference26th International Conference on Algorithmic Learning Theory (ALT 2015)
CountryCanada
CityBanff
Period4/10/156/10/15

Fingerprint

Kolmogorov Complexity
Complexity Measure
Structure-function
Quantify
Compression
Term
Model

Cite this

Bloem, P., de Rooij, S., & Adriaans, P. (2015). Two Problems for Sophistication. In Algorithmic Learning Theory - 26th International Conference, ALT 2015 (Vol. 9355, pp. 379-394). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9355). Springer/Verlag. DOI: 10.1007/978-3-319-24486-0_25
Bloem, Peter ; de Rooij, Steven ; Adriaans, Pieter. / Two Problems for Sophistication. Algorithmic Learning Theory - 26th International Conference, ALT 2015. Vol. 9355 Springer/Verlag, 2015. pp. 379-394 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{eced28c75c29442a9cb6be7e3a60ed73,
title = "Two Problems for Sophistication",
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.",
author = "Peter Bloem and {de Rooij}, Steven and Pieter Adriaans",
year = "2015",
doi = "10.1007/978-3-319-24486-0_25",
language = "English",
isbn = "9783319244853",
volume = "9355",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer/Verlag",
pages = "379--394",
booktitle = "Algorithmic Learning Theory - 26th International Conference, ALT 2015",

}

Bloem, P, de Rooij, S & Adriaans, P 2015, Two Problems for Sophistication. in Algorithmic Learning Theory - 26th International Conference, ALT 2015. vol. 9355, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9355, Springer/Verlag, pp. 379-394, 26th International Conference on Algorithmic Learning Theory (ALT 2015), Banff, Canada, 4/10/15. DOI: 10.1007/978-3-319-24486-0_25

Two Problems for Sophistication. / Bloem, Peter; de Rooij, Steven; Adriaans, Pieter.

Algorithmic Learning Theory - 26th International Conference, ALT 2015. Vol. 9355 Springer/Verlag, 2015. p. 379-394 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9355).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Two Problems for Sophistication

AU - Bloem,Peter

AU - de Rooij,Steven

AU - Adriaans,Pieter

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84945943708&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84945943708&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-24486-0_25

DO - 10.1007/978-3-319-24486-0_25

M3 - Conference contribution

SN - 9783319244853

VL - 9355

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 379

EP - 394

BT - Algorithmic Learning Theory - 26th International Conference, ALT 2015

PB - Springer/Verlag

ER -

Bloem P, de Rooij S, Adriaans P. Two Problems for Sophistication. In Algorithmic Learning Theory - 26th International Conference, ALT 2015. Vol. 9355. Springer/Verlag. 2015. p. 379-394. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Available from, DOI: 10.1007/978-3-319-24486-0_25