On prediction by data compression

Paul VitÁnyi; Ming Li

doi:10.1007/3-540-62858-4_69

On prediction by data compression

Paul VitÁnyi
, Ming Li

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

13 Citations (Scopus)

Abstract

Traditional wisdom has it that the better a theory compresses the learning data concerning some phenomenon under investigation, the better we leaxn, generalize, and the better the theory predicts unknown data. This belief is vindicated in practice but apparently has not been rigorously proved in a general setting. Making these ideas rigorous involves the length of the shortest effective description of an individual object: its Kolmogorov complexity. In a previous paper we have shown that optimal compression is almost always a best strategy in hypotheses identification (an ideal form of the minimum description length (MDL) principle). Whereas the single best hypothesis does not necessarily give the best prediction, we demonstrate that nonetheless compression is almost always the best strategy in prediction methods in the style of R. Solomonoff. © Springer-Verlag Berlin Heidelberg 1997.

Original language	English
Title of host publication	Machine Learning: ECML-97 - 9th European Conference on Machine Learning, Proceedings
Publisher	Springer Verlag
Pages	14-30
Volume	1224
ISBN (Print)	3540628584, 9783540628583
DOIs	https://doi.org/10.1007/3-540-62858-4_69
Publication status	Published - 1997
Event	9th European Conference on Machine Learning, ECML 1997 - Prague, Czech Republic Duration: 23 Apr 1997 → 25 Apr 1997

Publication series

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

Conference

Conference	9th European Conference on Machine Learning, ECML 1997
Place	Czech Republic
City	Prague
Period	23/04/97 → 25/04/97

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Funding

Paul Vits is also affiliated with the University of Amsterdam. He was supported by NSERC through International Scientific Exchange Award ISE0125663, and by the European Union through NeuroCOLT ESPRIT Working Group Nr. 8556, and by NWO through NFI Project ALADDIN under Contract number NF 62-376. Ming Li was supported in part by NSERC operating grant OGP-046506, ITRC, and a CGAT grant and the Steacie Fellowship.

Access Output

10.1007/3-540-62858-4_69

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

VitÁnyi, P., & Li, M. (1997). On prediction by data compression. In Machine Learning: ECML-97 - 9th European Conference on Machine Learning, Proceedings (Vol. 1224, pp. 14-30). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1224). Springer Verlag. https://doi.org/10.1007/3-540-62858-4_69

@inproceedings{3ba06f80933643388038ef846cbd3c42,

title = "On prediction by data compression",

abstract = "Traditional wisdom has it that the better a theory compresses the learning data concerning some phenomenon under investigation, the better we leaxn, generalize, and the better the theory predicts unknown data. This belief is vindicated in practice but apparently has not been rigorously proved in a general setting. Making these ideas rigorous involves the length of the shortest effective description of an individual object: its Kolmogorov complexity. In a previous paper we have shown that optimal compression is almost always a best strategy in hypotheses identification (an ideal form of the minimum description length (MDL) principle). Whereas the single best hypothesis does not necessarily give the best prediction, we demonstrate that nonetheless compression is almost always the best strategy in prediction methods in the style of R. Solomonoff. {\textcopyright} Springer-Verlag Berlin Heidelberg 1997.",

author = "Paul Vit{\'A}nyi and Ming Li",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].; 9th European Conference on Machine Learning, ECML 1997 ; Conference date: 23-04-1997 Through 25-04-1997",

year = "1997",

doi = "10.1007/3-540-62858-4\_69",

language = "English",

isbn = "3540628584",

volume = "1224",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "14--30",

booktitle = "Machine Learning: ECML-97 - 9th European Conference on Machine Learning, Proceedings",

address = "Germany",

}

VitÁnyi, P & Li, M 1997, On prediction by data compression. in Machine Learning: ECML-97 - 9th European Conference on Machine Learning, Proceedings. vol. 1224, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1224, Springer Verlag, pp. 14-30, 9th European Conference on Machine Learning, ECML 1997, Prague, Czech Republic, 23/04/97. https://doi.org/10.1007/3-540-62858-4_69

On prediction by data compression. / VitÁnyi, Paul; Li, Ming.
Machine Learning: ECML-97 - 9th European Conference on Machine Learning, Proceedings. Vol. 1224 Springer Verlag, 1997. p. 14-30 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1224).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - On prediction by data compression

AU - VitÁnyi, Paul

AU - Li, Ming

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 1997

Y1 - 1997

N2 - Traditional wisdom has it that the better a theory compresses the learning data concerning some phenomenon under investigation, the better we leaxn, generalize, and the better the theory predicts unknown data. This belief is vindicated in practice but apparently has not been rigorously proved in a general setting. Making these ideas rigorous involves the length of the shortest effective description of an individual object: its Kolmogorov complexity. In a previous paper we have shown that optimal compression is almost always a best strategy in hypotheses identification (an ideal form of the minimum description length (MDL) principle). Whereas the single best hypothesis does not necessarily give the best prediction, we demonstrate that nonetheless compression is almost always the best strategy in prediction methods in the style of R. Solomonoff. © Springer-Verlag Berlin Heidelberg 1997.

AB - Traditional wisdom has it that the better a theory compresses the learning data concerning some phenomenon under investigation, the better we leaxn, generalize, and the better the theory predicts unknown data. This belief is vindicated in practice but apparently has not been rigorously proved in a general setting. Making these ideas rigorous involves the length of the shortest effective description of an individual object: its Kolmogorov complexity. In a previous paper we have shown that optimal compression is almost always a best strategy in hypotheses identification (an ideal form of the minimum description length (MDL) principle). Whereas the single best hypothesis does not necessarily give the best prediction, we demonstrate that nonetheless compression is almost always the best strategy in prediction methods in the style of R. Solomonoff. © Springer-Verlag Berlin Heidelberg 1997.

UR - https://www.scopus.com/pages/publications/84947935921

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84947935921&origin=recordpage

U2 - 10.1007/3-540-62858-4_69

DO - 10.1007/3-540-62858-4_69

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 3540628584

SN - 9783540628583

VL - 1224

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

SP - 14

EP - 30

BT - Machine Learning: ECML-97 - 9th European Conference on Machine Learning, Proceedings

PB - Springer Verlag

T2 - 9th European Conference on Machine Learning, ECML 1997

Y2 - 23 April 1997 through 25 April 1997

ER -

On prediction by data compression

Abstract

Publication series

Conference

Bibliographical note

Funding

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this