摘要: We provide a new representation-independent formulation of Occam's razor theorem, based on Kolmogorov complexity. This allows us to: - Obtain better sample complexity than both length-based [4] and VC-based[3] versions in many applications. Achieve sharper reverse theorem that [5]. Specifically, we weaken the assumptions made [5] extend to superpolynomial running times.
springer.com
arxiv.org
core.ac.uk
narcis.nl参考文章(16)
William Gasarch, None, Book Review: An introduction to Kolmogorov Complexity and its Applications Second Edition, 1997 by Ming Li and Paul Vitanyi (Springer (Graduate Text Series)) Sigact News. ,vol. 28, pp. 37- 40 ,(1997) , 10.1145/262301.1040343
Norman Biggs, Martin Anthony, Computational learning theory: an introduction Cambridge University Press. ,(1992)
Paul Vitányi, Ming Li, An Introduction to Kolmogorov Complexity and Its Applications ,(1993)
David Haussler, Quantifying inductive bias: AI learning algorithms and Valiant's learning framework Artificial Intelligence. ,vol. 36, pp. 177- 221 ,(1988) , 10.1016/0004-3702(88)90002-1
R. Board, L. Pitt, On the necessity of Occam algorithms symposium on the theory of computing. pp. 54- 63 ,(1990) , 10.1145/100216.100223
Tao Jiang, Ming Li, DNA sequencing and string learning Theory of Computing Systems \/ Mathematical Systems Theory. ,vol. 29, pp. 387- 405 ,(1996) , 10.1007/BF01192694
L. G. Valiant, A theory of the learnable symposium on the theory of computing. ,vol. 27, pp. 1134- 1142 ,(1984) , 10.1145/800057.808710
Andrzej Ehrenfeucht, David Haussler, Michael Kearns, Leslie Valiant, A general lower bound on the number of examples needed for learning Information & Computation. ,vol. 82, pp. 247- 261 ,(1989) , 10.1016/0890-5401(89)90002-3
D. Haussler, N. Littlestone, M.K. Warmuth, Predicting {0, 1}-functions on randomly drawn points Information & Computation. ,vol. 115, pp. 248- 292 ,(1994) , 10.1006/INCO.1994.1097
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, Manfred K. Warmuth, Occam's razor Information Processing Letters. ,vol. 24, pp. 377- 380 ,(1987) , 10.1016/0020-0190(87)90114-1