Learning Conjunctive Concepts in Structural Domains
Machine LearningPublished 1 October 1989Open access
David Haussler
Citations154
SJR quartileQ1
SJR score1.15
SNIP2.14
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 class of concepts is formally defined, and it is shown that for any fixed bound on the number of objects per scene, this class is polynomially learnable if, in addition to providing random examples, the learning algorithm is allowed to make subset queries.
Abstract
We study the problem of learning conjunctive concepts from examples on structural domains like the blocks world. This class of concepts is formally defined, and it is shown that even for samples in which each example (positive or negative) is a two-object scene, it is NP-complete to determine if there is any concept in this class that is consistent with the sample. We demonstrate how this result affects the feasibility of Mitchell's version of space approach and how it shows that it is unlikely that this class of concepts is polynomially learnable from random examples alone in the PAC framework of Valiant. On the other hand, we show that for any fixed bound on the number of objects per scene, this class is polynomially learnable if, in addition to providing random examples, we allow the learning algorithm to make subset queries. In establishing this result, we calculate the capacity of the hypothesis space of conjunctive concepts in a structural domain and use a general theorem of Vapnik and Chervonenkis. This latter result can also be used to estimate a sample size sufficient for heuristic learning techniques that do not use queries.
Keywords
Computer Science
Pattern classification and scene analysis
12,643 Citations1973Richard O. Duda, Peter E. Hart
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.
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.
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
3,175 Citations2015Vladimir Vapnik, Alexey Chervonenkis
This chapter reproduces the English translation by B. Seckler of the paper by Vapnik and Chervonenkis in which they gave proofs for the innovative results they had obtained in a draft form in July 1966 and announced in 1968 in their note in Soviet Mathematics Doklady.
Information science and statisticsEstimation of Dependences Based on Empirical Data
2,238 Citations2006Vladimir Vapnik
Journal of the ACMLearnability and the Vapnik-Chervonenkis dimension
1,852 Citations1989Anselm Blumer, Andrzej Ehrenfeucht +2 more
This paper shows that the essential condition for distribution-free learnability is finiteness of the Vapnik-Chervonenkis dimension, a simple combinatorial parameter of the class of concepts to be learned.
Machine LearningQueries and Concept Learning
1,622 Citations1988Dana Angluin
This work considers the problem of using queries to learn an unknown concept, and several types of queries are described and studied: membership, equivalence, subset, superset, disjointness, and exhaustiveness queries.
Neural ComputationWhat Size Net Gives Valid Generalization?
1,555 Citations1989Eric B. Baum, David Haussler
It is shown that if m O(W/ ∊ log N/∊) random examples can be loaded on a feedforward network of linear threshold functions with N nodes and W weights, so that at least a fraction 1 ∊/2 of the examples are correctly classified, then one has confidence approaching certainty that the network will correctly classify a fraction 2 ∊ of future test examples drawn from the same distribution.
Machine LearningExplanation-Based Generalization: A Unifying View
1,175 Citations1986Tom M. Mitchell, Richard M. Keller +1 more
This paper proposes a general, domain-independent mechanism, called EBG, that unifies previous approaches to explanation-based generalization, and is illustrated in the context of several example problems, and used to contrast several existing systems for explanation- based generalization.
DSpace@MIT (Massachusetts Institute of Technology)Learning Structural Descriptions From Examples
1,007 Citations1970Patrick Henry Winston
Machine LearningQueries and concept learning
817 Citations1988Dana Angluin
This work considers the problem of using queries to learn an unknown concept, and several types of queries are described and studied: membership, equivalence, subset, superset, disjointness, and exhaustiveness queries.
Computer CompactsA theory and methodology of inductive learning
778 Citations1983Ryszard S. Michalski
Discrete & Computational Geometryɛ-nets and simplex range queries
731 Citations1987David Haussler, Emo Welzl
The concept of an ɛ-net of a set of points for an abstract set of ranges is introduced and sufficient conditions that a random sample is an Â-net with any desired probability are given.
SIAM Journal on ComputingComputational Complexity of Probabilistic Turing Machines
694 Citations1977John Gill
It is shown that every nondeterministic machine can be simulated in the same space by a probabilistic machine with small error probability.
Journal of the ACMComputational limitations on learning from examples
532 Citations1988Leonard Pitt, Leslie G. Valiant
It is shown for various classes of concept representations that these cannot be learned feasibly in a distribution-free sense unless R = NP, and relationships between learning of heuristics and finding approximate solutions to NP-hard optimization problems are given.
BMC NursingThe Need for Biases in Learning Generalizations
527 Citations2007Tom M. Mitchell
The current study showed that the Digital Education Package (DEP) is an effective method for reducing children’s anxiety during hospitalization and recommended it as a preferred and simple method rather than routine education for pediatric nurses.
Artificial IntelligenceQuantifying inductive bias: AI learning algorithms and Valiant's learning framework
499 Citations1988David Haussler
It is shown that the notion of inductive bias in concept learning can be quantified in a way that directly relates to learning performance in the framework recently introduced by Valiant.
Elsevier eBooksMachine Invention of First-order Predicates by Inverting Resolution
441 Citations1988Stephen Muggleton, Wray Buntine
A mechanism for automatically inventing and generalising first-order Horn clause predicates is presented, based on inverting the mechanism of resolution, which has its roots in the Duce system for induction of propositional Horn clauses.
Information and ComputationA general lower bound on the number of examples needed for learning
414 Citations1989Andrzej Ehrenfeucht, David Haussler +2 more
This paper proves a lower bound on the number of random examples required for distribution-free learning of a concept class C and shows that for many interesting concept classes, including k CNF and k DNF, the bound is actually tight to within a constant factor.
IEEE Transactions on Pattern Analysis and Machine IntelligencePattern Recognition as Rule-Guided Inductive Inference
405 Citations1980Ryszard S. Michalski
The paper formulates the theoretical framework and a method for inferring general and optimal descriptions of object classes from examples of classification or partial descriptions and an experimental computer implementation of the method is briefly described and illustrated by an example.
Shift of bias for inductive concept learning
288 Citations1984Paul E. Utgoff
It is shown that search for appropriate bias is itself a major part of the learning task, and that mechanical procedures for conducting a well-directed search for an appropriate bias can be created.
Elsevier eBooksExplanation-Based Generalization: A Unifying View
261 Citations1988T. M. Mitchell, Richard M. Keller +1 more
Machine LearningA Comparative Review of Selected Methods for Learning from Examples
252 Citations1983Thomas G. Dietterich, Ryszard S. Michalski
Methods for finding the maximally-specific conjunctive generalizations (MSC-generalizations) that cover all of the training examples of a given concept are examined.
Machine LearningA THEORY AND METHODOLOGY OF INDUCTIVE LEARNING
205 Citations1983Ryszard S. Michalski
The presented theory views inductive learning as a heuristic search through a space of symbolic descriptions, generated by an application of various inference rules to the initial observational statements.
Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension
170 Citations1986Anselm Blumer, Andrzej Ehrenfeucht +2 more
It is shown that the essential condition for distribution-free learnability is finiteness of the Vapnik-Chervonenkis dimension, a simple combinatorial parameter of the class of concepts to be learned.
Learning disjunction of conjunctions
167 Citations1985Leslie G. Valiant
Positive results are shown for significant subclasses that allow not only propositional predicates but also some relations and under certain restrictions on these subclasses the learning algorithms are well suited to implementation on neural networks of threshold elements.
Machine LearningOn Learning Sets and Functions
151 Citations1989B. K. Natarajan
This paper presents some results on the probabilistic analysis of learning, illustrating the applicability of these results to settings such as connectionist networks.
Epsilon-nets and simplex range queries
137 Citations1986David Haussler, Emo Welzl
A new technique for half-space and simplex range query using random sampling to build a partition-tree structure and introduces the concept of anε-net for an abstract set of ranges to describe the desired result of this random sampling.
Elsevier eBooksRecent Results on Boolean Concept Learning
130 Citations1987Michael Kearns, Ming Li +2 more
A recently introduced model of concept learning that pays particular attention to computational feasibility is described and the various directions in which the model can be extended are discussed.
Communications of the ACMAn interference matching technique for inducing abstractions
124 Citations1978Frederick Hayes‐Roth, John McDermott
Three tasks solved by a program that uses an interference-matching algorithm are presented and several problems concerning the description of the training examples and the adequacy of interference matching are discussed.
Artificial IntelligenceAn analytical comparison of some rule-learning programs
123 Citations1985Alan Bundy, Bernard Silver +1 more
This work compares the rule-learning programs of Brazdil, Langley, Mitchell, Mitchell et al, Shapiro, Waterman, and Quinlan with the concept- learning programs of Quinlan, and Young et al.
LEARNING CONCEPTS BY ASKING QUESTIONS
118 Citations1998Claude Sammut, Ranan B. Banerji
This chapter describes a program, called Marvin, which uses concepts it has learned previously to learn new concepts, and forms hypotheses about the concept being learned and tests the hypotheses by asking the trainer questions.
International Joint Conference on Artificial IntelligenceInduction of concepts in the predicate calculus
117 Citations1975Steven A. Vere
This work is directed to providing a formal model for the inductive processes which are observed in artificial intelligence studies in specialized areas, by an induction procedure which operates on the product graph form of positive and negative instances.
International Journal of General SystemsON THE CONNECTION BETWEEN THE COMPLEXITY AND CREDIBILITY OF INFERRED MODELS
97 Citations1978Judea Pearl
This paper derives formal relationships between n, c and the probability of ambiguous predictions by examining three modeling languages under binary classification tasks: perceptrons, Boolean formulae, and Boolean networks.
Machine LearningLearning conjunctive concepts in structural domains
95 Citations1989David Haussler
This class of concepts is formally defined, and it is shown that for any fixed bound on the number of objects per scene, this class is polynomially learnable if, in addition to providing random examples, the learning algorithm is allowed to make subset queries.
Machine LearningOn learning sets and functions
93 Citations1989B. K. Natarajan
This paper presents some results on the probabilistic analysis of learning, illustrating the applicability of these results to settings such as connectionist networks.
Elsevier eBooksBias, Version Spaces and Valiant's Learning Framework
58 Citations1987David Haussler
This work presents an overview of some recent theoretical results in the learning framework introduced by Valiant and a comparison to the work of Mitchell on version spaces, and discusses learning problems for both attribute-based and structural domains.
Topics in information systemsLearning Improved Integrity Constraints and Schemas From Exceptions in Data and Knowledge Bases
47 Citations1986Alexander Borgida, Tom M. Mitchell +1 more
The purpose of this chapter is to demonstrate some ways in which a KBMS can be endowed with the ability to refine its schema on the basis of the data actually stored so far.
National Conference on Artificial IntelligenceFactorization in experiment generation
41 Citations1986Devika Subramanian, Joan Feigenbaum
The class of experiments that accomplish discrimination experiments are examined, called discrimination experiments, and factoring is proposed as a technique for generating them efficiently.
National Conference on Artificial IntelligenceQuantifying the inductive bias in concept learning (extended abstract)
21 Citations1986David Haussler
It is shown that the notion of bias in inductive concept learning can be quantified in a way that directly relates to learning performance, and that this quantitative theory of bias can provide guidance in the design of effective learning algorithms.
International Journal of Man-Machine StudiesInduction of Horn clauses: methods and the plausible generalization algorithm
16 Citations1987Wray Buntine
A framework where induction is viewed as a process of model-directed discovery of consistent patterns (constraints and rules) in data is proposed, and a new algorithm is described that has been used to investigate the sub-problem of discovering rules.
Elsevier eBooksMachine Learning from Structured Objects
13 Citations1987Robert E. Stepp
A motivation is given for the importance of careful attention to the semantics that underly descriptions of structured examples and categories of such examples and the ability to determine relevant attributes.