Learning Simple Concepts under Simple Distributions

DOI10.1137/0220056zbMath0751.68055OpenAlexW1982500696MaRDI QIDQ3982714

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 complexitypolynomial-time learningpac-learninglearning simple conceptssimple distributionsValiant's learning model

Mathematics Subject Classification ID

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

Related Items (13)

Computational depth and reducibility ⋮ Learning nearly monotone \(k\)-term DNF ⋮ PACS, simple-PAC and query learning ⋮ Weakening the language bias in LINUS ⋮ Simple PAC learning of simple decision lists ⋮ Efficiency in the Identification in the Limit Learning Paradigm ⋮ Inductive reasoning and Kolmogorov complexity ⋮ PAC Learning under Helpful Distributions ⋮ Learning logic programs with structured background knowledge ⋮ Monotone term decision lists ⋮ Pac-learning non-recursive Prolog clauses ⋮ Philosophical issues in Kolmogorov complexity ⋮ Pac-learning non-recursive Prolog clauses

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