Inductive reasoning and Kolmogorov complexity

@inproceedings{citeulike:1656114, abstract = {The inductive reasoning concepts of R.J. Solomonoff (Inf. Control. vol.7, p.1-22, 224-254, 1964) are considered. The thesis is developed that Solomonoff's method is fundamental in the sense that many other induction principles can be viewed as particular ways to obtain computable approximations to it. This is demonstrated explicitly in the cases of E.M. Gold's (1967, 1978) paradigm for inductive inference, L.G. Valiant's (1984) learning (by adding computational requirements), J. Rissanen's (1982) minimum description length principle, Fisher's maximum-likelihood principle (J. Rissanen, 1982), and E.T. Jayne's (1968, 1982) maximum entropy principle. Several new theorems and derivations to this effect are presented. What can and cannot be learned in terms of Kolmogorov complexity is delimited, and an experiment in machine learning of handwritten characters is described}, author = {Li, M. and Vitanyi, P. M. B. }, booktitle = {Structure in Complexity Theory Conference, 1989. Proceedings., Fourth Annual}, citeulike-article-id = {1656114}, journal = {Structure in Complexity Theory Conference, 1989. Proceedings., Fourth Annual}, pages = {165--185}, posted-at = {2007-09-14 14:32:13}, priority = {2}, title = {Inductive reasoning and Kolmogorov complexity}, url = {http://ieeexplore.ieee.org/xpls/abs\_all.jsp?arnumber=41823}, year = {1989} }

TY - CONF ID - citeulike:1656114 L3 - citeulike-article-id:1656114 TI - Inductive reasoning and Kolmogorov complexity T2 - Structure in Complexity Theory Conference, 1989. Proceedings., Fourth Annual JF - Structure in Complexity Theory Conference, 1989. Proceedings., Fourth Annual SP - 165 EP - 185 N2 - The inductive reasoning concepts of R.J. Solomonoff (Inf. Control. vol.7, p.1-22, 224-254, 1964) are considered. The thesis is developed that Solomonoff's method is fundamental in the sense that many other induction principles can be viewed as particular ways to obtain computable approximations to it. This is demonstrated explicitly in the cases of E.M. Gold's (1967, 1978) paradigm for inductive inference, L.G. Valiant's (1984) learning (by adding computational requirements), J. Rissanen's (1982) minimum description length principle, Fisher's maximum-likelihood principle (J. Rissanen, 1982), and E.T. Jayne's (1968, 1982) maximum entropy principle. Several new theorems and derivations to this effect are presented. What can and cannot be learned in terms of Kolmogorov complexity is delimited, and an experiment in machine learning of handwritten characters is described AU - Li, M AU - Vitanyi, PMB PY - 1989/// UR - http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=41823 ER -