\(P\)-sufficient statistics for PAC learning \(k\)-term-DNF formulas through enumeration

DOI10.1016/S0304-3975(98)00215-1zbMath0939.68056MaRDI QIDQ1978498

Claudio Gentile, Bruno Apolloni

Publication date: 4 June 2000

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

zbMATH Keywords

computational complexitysufficient statisticsBoolean functionconcept learningnonparametric statisticslearning by examples

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast learning of \(k\)-term DNF formulas with queries.
• Estimation of dependences based on empirical data. Transl. from the Russian by Samuel Kotz
• PAC learning of concept classes through the boundaries of their items
• A general lower bound on the number of examples needed for learning
• On the density of families of sets
• Constant depth circuits, Fourier transform, and learnability
• Learnability and the Vapnik-Chervonenkis dimension
• A theory of the learnable
• Computational limitations on learning from examples
• Learning Monotone Boolean Functions by Uniformly Distributed Examples
• Efficient noise-tolerant learning from statistical queries
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• A formal theory of inductive inference. Part I
• Some Principles of the Theory of Testing Hypotheses
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

This page was built for publication: \(P\)-sufficient statistics for PAC learning \(k\)-term-DNF formulas through enumeration