Two Problems for Sophistication

Peter Bloem; Steven de Rooij; Pieter Adriaans

doi:10.1007/978-3-319-24486-0_25

Two Problems for Sophistication

Peter Bloem, Steven de Rooij, Pieter Adriaans

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

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.

Original language	English
Title of host publication	Algorithmic Learning Theory - 26th International Conference, ALT 2015
Publisher	Springer/Verlag
Pages	379-394
Number of pages	16
Volume	9355
ISBN (Print)	9783319244853
DOIs	https://doi.org/10.1007/978-3-319-24486-0_25
Publication status	Published - 2015
Externally published	Yes
Event	26th International Conference on Algorithmic Learning Theory (ALT 2015) - Banff, Canada Duration: 4 Oct 2015 → 6 Oct 2015

Publication series

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

Conference

Conference	26th International Conference on Algorithmic Learning Theory (ALT 2015)
Country/Territory	Canada
City	Banff
Period	4/10/15 → 6/10/15

Access to Document

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

Persistent URL (handle)

Copy link address

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. https://doi.org/10.1007/978-3-319-24486-0_25

@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{\textquoteright}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",

note = "26th International Conference on Algorithmic Learning Theory (ALT 2015) ; Conference date: 04-10-2015 Through 06-10-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. https://doi.org/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 proceeding › Conference contribution › Academic › peer-review

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

T2 - 26th International Conference on Algorithmic Learning Theory (ALT 2015)

Y2 - 4 October 2015 through 6 October 2015

ER -

Two Problems for Sophistication

Abstract

Publication series

Conference

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this