Computer Science, abstract
cs.LG/0201005
From: Paul Vitanyi <paul.vitanyi.domain.name.hidden>
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 (-/+), /, ?
--------------------------------------------------------------------------------
Received on Thu Jan 10 2002 - 03:28:39 PST