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 (CWI), Paul Vitanyi (CWI and University of Amsterdam)
Comments: LaTeX 10 pages
Report-no: CWI Manuscript 1994
Subj-class: Learning; Artificial Intelligence; Computational Complexity
ACM-class: F.2, E.4, I.2

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 there and extend the reverse to superpolynomial running times.

Paper: PostScript (600 dpi), or Other formats

(N.B.: delivery types and potential problems)

Links to: arXiv, cs, /find, /abs (-/+), /, ?

Reply via email to