Sharpening Occam's razor

DOI10.1016/S0020-0190(02)00427-1zbMath1173.68886MaRDI QIDQ1007542

Ming Li, Paul M. B. Vitányi, John Tromp

Publication date: 23 March 2009

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

Kolmogorov complexityanalysis of algorithmsOccam's razor-style theoremspac-learning

Mathematics Subject Classification ID

Analysis of algorithms (68W40) General topics in artificial intelligence (68T01)

Related Items

The DNF exception problem ⋮ Implementation of Boolean functions with a bounded number of zeros by disjunctive normal forms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quantifying inductive bias: AI learning algorithms and Valiant's learning framework
• Occam's razor
• Predicting \(\{ 0,1\}\)-functions on randomly drawn points
• A general lower bound on the number of examples needed for learning
• On weak learning
• DNA sequencing and string learning
• Learnability and the Vapnik-Chervonenkis dimension
• A theory of the learnable
• Linear approximation of shortest superstrings