Name
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 [Blumer et al., Inform. Process. Lett. 24 (1987) 377–380] and VC-based [Blumer et al., J. ACM 35 (1989) 929–965] versions of Occam's razor theorem, in many applications; and (ii) achieve a sharper reverse of Occam's razor theorem than that of Board and Pitt [STOC, 1999, pp. 54–63]. Specifically, we weaken the assumptions made by Board and Pitt [STOC, 1999, pp. 54–63] and extend the reverse to superpolynomial running times. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0020-0190(02)00427-1 | Information Processing Letters |
Keywords | DocType | Volume |
Analysis of algorithms,Pac-learning,Kolmogorov complexity,Occam's razor-style theorems | Journal | 85 |
Issue | ISSN | Citations |
5 | 0020-0190 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ming Li | 1 | 5595 | 829.00 |
| John Tromp | 2 | 0 | 0.34 |
| Paul Vitányi | 3 | 2130 | 287.76 |