Computer Science, abstract
From: Paul Vitanyi <[EMAIL PROTECTED]>
Date: Tue, 8 Jan 2002 16:44:10 GMT (11kb)
Sharpening Occam's Razor
Authors: Ming Li (Univ.
Waterloo), John Tromp
Vitanyi (CWI and University of Amsterdam)
Comments: LaTeX 10
Report-no: CWI Manuscript 1994
Artificial Intelligence; Computational Complexity
ACM-class: F.2, E.4,
We provide a new representation-independent formulation of Occam's
razor theorem, based on Kolmogorov complexity. This new formulation allows us
types and potential problems)
(i) Obtain better sample complexity than both length-based and
VC-based versions of Occam's razor theorem, in many applications.
Achieve a sharper reverse of Occam's razor theorem than previous work.
Specifically, we weaken the assumptions made in there and extend the
reverse to superpolynomial running times.