Kolmogorov's structure functions with an application to the foundations of model selection
作者： N. Vereshchagin , P. Vitanyi
DOI: 10.1109/SFCS.2002.1182000
关键词:
摘要: Kolmogorov (1974) proposed a non-probabilistic approach to statistics, an individual combinatorial relation between the data and its model. We vindicate, for first time, rightness of original "structure function", by Kolmogorov: minimizing data-to-model code length (finding ML estimator or MDL estimator), in class contemplated models prescribed maximal (Kolmogorov) complexity, always results model best fit (expressed as minimal randomness deficiency). show that both structure function minimum deficiency can assume all shapes over their full domain (improving old result L.A. Levin recent one VV Vyugin). determine (un)computability properties various functions "algorithmic sufficient statistic.".
narcis.nl
arxiv.org 
acm.org 参考文章(17)
C. S. Wallace, P. R. Freeman, Estimation and Inference by Compact Coding Journal of the royal statistical society series b-methodological. ,vol. 49, pp. 240- 252 ,(1987) , 10.1111/J.2517-6161.1987.TB01695.X
Thomas M. Cover, Kolmogorov Complexity, Data Compression, and Inference Springer Netherlands. pp. 23- 33 ,(1985) , 10.1007/978-94-009-5113-6_2
Paul Vitányi, Ming Li, An Introduction to Kolmogorov Complexity and Its Applications ,(1993)
Thomas M. Cover, Peter Gacs, Robert M. Gray, KOLMOGOROV'S CONTRIBUTIONS TO INFORMATION THEORY AND ALGORITHMIC COMPLEXITY Annals of Probability. ,vol. 17, pp. 840- 865 ,(1989) , 10.1214/AOP/1176991250
V. V. V’Yugin, On the Defect of Randomness of a Finite Object with Respect to Measures with Given Complexity Bounds Theory of Probability & Its Applications. ,vol. 32, pp. 508- 512 ,(1988) , 10.1137/1132071
A. N. Kolmogorov, Three approaches to the quantitative definition of information International Journal of Computer Mathematics. ,vol. 2, pp. 157- 168 ,(1968) , 10.1080/00207166808803030
Per Martin-Löf, The definition of random sequences Information & Computation. ,vol. 9, pp. 602- 619 ,(1966) , 10.1016/S0019-9958(66)80018-9
V.V. V'yugin, Does snooping help Theoretical Computer Science. ,vol. 276, pp. 407- 415 ,(2002) , 10.1016/S0304-3975(01)00122-0
On the Mathematical Foundations of Theoretical Statistics Philosophical Transactions of the Royal Society A. ,vol. 222, pp. 309- 368 ,(1922) , 10.1098/RSTA.1922.0009
A. Barron, J. Rissanen, Bin Yu, The minimum description length principle in coding and modeling IEEE Transactions on Information Theory. ,vol. 44, pp. 2743- 2760 ,(1998) , 10.1109/18.720554