On the necessity of Occam algorithms

DOI10.1016/0304-3975(92)90367-OzbMath0825.68544OpenAlexW2075121617MaRDI QIDQ1193631

Raymond Board, Leonard Pitt

Publication date: 27 September 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90367-o

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Related Items

The DNF exception problem ⋮ On the hardness of approximating the minimum consistent OBDD problem ⋮ Partial Occam's Razor and its applications ⋮ Learning recursive functions: A survey ⋮ Implementation of Boolean functions with a bounded number of zeros by disjunctive normal forms ⋮ Explanatory and creative alternatives to the MDL principle ⋮ PAC Learning under Helpful Distributions ⋮ Monotone term decision lists ⋮ Prediction-preserving reducibility

Cites Work

• Unnamed Item
• Prediction-preserving reducibility
• Occam's razor
• A general lower bound on the number of examples needed for learning
• Learnability and the Vapnik-Chervonenkis dimension
• A theory of the learnable
• Computational limitations on learning from examples
• The minimum consistent DFA problem cannot be approximated within any polynomial
• Computational Complexity of Probabilistic Turing Machines