Sharpening Occam's Razor

Abstract

We provide a new representation-independent formulation of Occam's razor theorem, based on Kolmogorov complexity. This new formulation allows us to: (i) Obtain better sample complexity than both length-based and VC-based versions of Occam's razor theorem, in many applications. (ii) Achieve a sharper reverse of Occam's razor theorem than previous work. Specifically, we weaken the assumptions made in an earlier publication, and extend the reverse to superpolynomial running times.

LaTeX 13 pages; Proc 8th COCOON, LNCS 2387, Springer-Verlag, Berlin, 2002, 411--419