PAC Learning from Positive Statistical Queries
Lecture notes in computer sciencePublished 1 January 1998
François Denis
Citations177
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work defines a PAC learning model from positive and unlabeled examples, and defines a PAC learning model from positive and unlabeled statistical queries and shows that k-DNF and k-decision lists are learnable in both models.
Abstract
Learning from positive examples occurs very frequently in natural learning. The PAC learning model of Valiant takes many features of natural learning into account,but in most cases it fails to describe such kind of learning. We show that in order to make the learning from positive data possible, extra-information about the underlying distribution must be provided to the learner. We define a PAC learning model from positive and unlabeled examples. We also define a PAC learning model from positive and unlabeled statistical queries.Relations with PAC model ([Val84]), statistical query model ([Kea93]) and constant-partition classification noise model ([Dec97]) are studied. We show that k DNF and k decision lists are learnable in both models, i.e. with far less information than it is assumed in previously used algorithms.
Keywords
Computer Science
A theory of the learnable
4,242 Citations1984Leslie G. Valiant
This paper regards learning as the phenomenon of knowledge acquisition in the absence of explicit programming, and gives a precise methodology for studying this phenomenon from a computational viewpoint.
Information and ControlLanguage identification in the limit
3,569 Citations1967Eric Gold
It was found that theclass of context-sensitive languages is learnable from an informant, but that not even the class of regular languages is learningable from a text.
Communications of the ACMA theory of the learnable
3,268 Citations1984Leslie G. Valiant
This paper regards learning as the phenomenon of knowledge acquisition in the absence of explicit programming, and gives a precise methodology for studying this phenomenon from a computational viewpoint.
The MIT Press eBooksAn Introduction to Computational Learning Theory
1,733 Citations1994Michael Kearns, Umesh Vazirani
The probably approximately correct learning model Occam's razor the Vapnik-Chervonenkis dimension weak and strong learning learning in the presence of noise inherent unpredictability reducibility in PAC learning learning finite automata is described.
Machine LearningLearning Decision Lists
761 Citations1987Ronald L. Rivest
This paper introduces a new representation for Boolean functions, called decision lists, and shows that they are efficiently learnable from examples, and strictly increases the set of functions known to be polynomially learnable, in the sense of Valiant (1984).
Information and ControlInductive inference of formal languages from positive data
750 Citations1980Dana Angluin
A theorem characterizing when an indexed family of nonempty recursive formal languages is inferrable from positive data is proved, and other useful conditions for inference frompositive data are obtained.
Journal of the ACMEfficient noise-tolerant learning from statistical queries
712 Citations1998Michael Kearns
This paper formalizes a new but related model of learning from statistical queries, and demonstrates the generality of the statistical query model, showing that practically every class learnable in Valiant's model and its variants can also be learned in the new model (and thus can be learning in the presence of noise).
Machine LearningLearning From Noisy Examples
667 Citations1988Dana Angluin, Philip Laird
This paper shows that when the teacher may make independent random errors in classifying the example data, the strategy of selecting the most consistent rule for the sample is sufficient, and usually requires a feasibly small number of examples, provided noise affects less than half the examples on average.
Efficient noise-tolerant learning from statistical queries
177 Citations1993Michael Kearns
The generality of the statistical query model is demonstrated, showing that practically every class learnable in Valiant’s model and its variants can also be learned in the new model (and thus can be learned in the presence of noise).
Lecture notes in computer sciencePAC Learning from Positive Statistical Queries
177 Citations1998François Denis
This work defines a PAC learning model from positive and unlabeled examples, and defines a PAC learning model from positive and unlabeled statistical queries and shows that k-DNF and k-decision lists are learnable in both models.
On learning Boolean functions
144 Citations1987B. K. Natarajan
An intuitively appealing notion of dimensionality is developed and used to identify the most general class of Boolean function families that are learnable from polynomially many positive examples with one-sided error.
Lecture notes in computer scienceA guided tour across the boundaries of learning recursive languages
115 Citations1995Thomas Zeugmann, Steffen Lange
The influence of various monotonicity constraints to the learning process is considered, and a thorough study concerning the influence of several parameters is provided, which provides a unifying framework for learning.
SIAM Journal on ComputingLearning Integer Lattices
84 Citations1992David P. Helmbold, Robert H. Sloan +1 more
Journal of Computer and System SciencesLearning Distributions by Their Density Levels: A Paradigm for Learning without a Teacher
57 Citations1997Shai Ben-David, Michael Lindenbaum
It is proved that classes whose VC-dimension is finite are learnable in a very strong sense, while on the other hand,�-covering numbers of a concept class impose lower bounds on the sample size needed for learning in the authors' models.
SIAM Journal on ComputingProbably Approximate Learning of Sets and Functions
25 Citations1991B. K. Natarajan
The scope of the learning model is widened to include the inference of functions, and the Vapnik–Chervonenkis dimension is extended to obtain a measure called the “generalized dimension” of a class of functions.
Machine LearningA Necessary Condition for Learning from Positive Examples
10 Citations1990Haim Shvaytser