Computer Science, abstract
cs.LG/0201005 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.
(N.B.: delivery
types and potential problems)
|
