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

DOI10.1016/S0304-3975(98)00215-1MaRDI QIDQ1978498zbMATH OpenFDO

Authors Claudio Gentile, B. Apolloni

Publication date 4 June 2000

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

zbMATH Keywords

computational complexitynonparametric statisticsBoolean functionconcept learningsufficient statisticslearning by examples

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Recommendations

• scientific article; zbMATH DE number 1804125
• On learning monotone DNF under product distributions
• Proper learning of \(k\)-term DNF formulas from satisfying assignments
• scientific article; zbMATH DE number 4092808
• scientific article; zbMATH DE number 1256728

Cites work

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

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

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