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.
Cite
Text
Bloem et al. "Two Problems for Sophistication." International Conference on Algorithmic Learning Theory, 2015. doi:10.1007/978-3-319-24486-0_25Markdown
[Bloem et al. "Two Problems for Sophistication." International Conference on Algorithmic Learning Theory, 2015.](https://mlanthology.org/alt/2015/bloem2015alt-two/) doi:10.1007/978-3-319-24486-0_25BibTeX
@inproceedings{bloem2015alt-two,
title = {{Two Problems for Sophistication}},
author = {Bloem, Peter and de Rooij, Steven and Adriaans, Pieter},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2015},
pages = {379-394},
doi = {10.1007/978-3-319-24486-0_25},
url = {https://mlanthology.org/alt/2015/bloem2015alt-two/}
}