Learning Simple Concepts under Simple Distributions

DOI10.1137/0220056MaRDI QIDQ3982714zbMATH OpenOpenAlexFDO

Authors Paul M. B. Vitányi, Ming Li

Publication date 26 June 1992

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/d664e5b703af51336e7b830064d7ace95e3f57cc

zbMATH Keywords

Kolmogorov complexitylearning simple conceptspac-learningpolynomial-time learningsimple distributionsValiant's learning model

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Learning and adaptive systems in artificial intelligence (68T05) Parallel algorithms in computer science (68W10)

Recommendations

• scientific article; zbMATH DE number 67636
• scientific article; zbMATH DE number 4060753
• Nonuniform learnability
• PAC learning with simple examples

Cited in

(18)

• Inductive reasoning and Kolmogorov complexity
• Efficient distribution-free population learning of simple concepts
• Efficient distribution-free learning of probabilistic concepts
• Simple translation-invariant concepts are hard to learn
• Computational depth and reducibility
• PAC learning under helpful distributions
• Learning nearly monotone k-term DNF
• PACS, simple-PAC and query learning
• Efficiency in the identification in the limit learning paradigm
• A theory of the learnable
• scientific article; zbMATH DE number 67636 (Why is no real title available?)
• Weakening the language bias in LINUS
• Philosophical issues in Kolmogorov complexity
• Pac-learning non-recursive Prolog clauses
• Pac-learning non-recursive Prolog clauses
• Learning logic programs with structured background knowledge
• Monotone term decision lists
• Simple PAC learning of simple decision lists

This page was built for publication: Learning Simple Concepts under Simple Distributions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3982714)