Queries and concept learning

DANA ANGLUIN

article1988Machine-mediated learning1,464 citations

Establishes a foundational theoretical framework for exact concept learning via structured queries, proving efficient algorithms and lower bounds across formal languages and boolean domains while connecting query-based learning to Valiant's PAC model.

Listen

Expert systems and automated reasoning tools must acquire complex target concepts accurately, but relying solely on passive, randomly supplied training examples is frequently inefficient or impractical. In real-world environments, an automated system needs interactive mechanisms to query human experts or automated test environments. However, before deploying such interactive learners, system architects need to understand which specific types of queries are mathematically sufficient to learn target concepts efficiently, which combinations are inadequate, and how interactive querying compares to probabilistic learning from random data.

The article establishes a rigorous theoretical framework to evaluate how six distinct types of queries—membership, equivalence, subset, superset, disjointness, and exhaustiveness—enable efficient, exact concept learning across various formal domains. It systematically analyzes the minimum query capabilities required to guarantee successful learning in polynomial time and identifies the fundamental mathematical limits where efficient learning is provably impossible.

To conduct this evaluation, the analysis uses formal computational complexity models, constructible learning algorithms, and adversarial lower-bound techniques across domains such as formal grammars, automata, pattern languages, and propositional logic formulas. The investigation assesses both exact identification (where the algorithm must precisely pinpoint the target concept) and probabilistic identification (identifying an approximation of the concept with high confidence under random sampling), while evaluating queries in both unrestricted forms that return counterexamples and restricted forms that return simple yes-or-no answers.

The analysis reveals several primary findings regarding interactive learning power and efficiency. First, combining equivalence queries with membership queries forms a minimally adequate teacher that allows for efficient, polynomial-time exact identification across challenging domains, including regular languages, monotone disjunctive normal form formulas, and bounded context-free grammars. Second, query utility is highly domain-dependent: pattern languages can be identified in polynomial time using restricted superset queries alone, but they require an exponential number of queries if limited to equivalence, membership, and subset queries. Third, counterexamples are vital; when algorithms are restricted to simple yes-or-no answers without counterexamples, learning tasks that were previously tractable suddenly require worst-case exponential queries. Fourth, the article establishes an asymmetric relationship between exact query learning and probabilistic sampling: any exact algorithm that uses equivalence queries can be transformed into an efficient probabilistic learning algorithm via random sampling, but probabilistic algorithms cannot generally be converted into efficient exact query algorithms. Finally, the article presents a worst-case construct, known as the double sunflower, demonstrating that some concept classes cannot be learned efficiently even when an algorithm has access to all six query types simultaneously.

These findings have direct implications for the architecture and cost of interactive automated systems. Relying on an incomplete or poorly matched query protocol risks exponential computational delays and system failure, whereas selecting the correct query types guarantees fast, predictable convergence. Furthermore, the practical substitute of approximating equivalence queries via stochastic testing enables designers to build robust learners without demanding exhaustive domain evaluations from human experts. When designing domain interactions, engineers must also recognize that asking a human expert for high-level subset or rule-level evaluations can often be more feasible and informative than generating fully specified, concrete membership examples.

For systems engineering and future development, technical leaders should align their system interfaces with the specific query types proven sufficient for their target domain. When exact equivalence testing is intractable for human instructors, systems should implement automated stochastic sampling or prediction-based interfaces to achieve high-accuracy probabilistic identification. Researchers and developers should prioritize developing error-tolerant learning models, given that practical inputs from human experts frequently contain noise, bias, or malicious inaccuracies, and should investigate rich query models such as hint requests and partial explanations.

These conclusions are theoretical and rely on the boundary condition that queried hypotheses must generally be members of the defined hypothesis space unless explicitly expanded. The findings provide high mathematical confidence regarding the absolute lower bounds and algorithmic guarantees for clean environments, but practitioners should exercise caution when applying these idealized models to noisy, unconstrained, or poorly specified real-world domains where human responses may be fallible.

Yale University first order logic pattern languages propositional formulas concept learning equivalence queries membership queries

ANGLUIN (1988).pdf

Paper: A Theory of the Learnable, Leslie G. Valiant (1984). Valiant introduced the foundational PAC-learning framework and early query-oracles that Angluin formalizes, extends, and evaluates across different query protocols.

Paper: Query by committee, H. Seung et al. (1992). This paper builds on theoretical query-learning concepts by proposing Query by Committee as an efficient active-querying algorithm using model ensembles.
Paper: Improving Generalization with Active Learning, David Cohn et al. (1994). This work applies interactive query concepts to neural networks via selective sampling within regions of hypothesis disagreement.
Paper: Active Learning with Statistical Models, David Cohn et al. (1996). This paper extends active query selection principles to continuous statistical regression models by formulating variance-minimizing query criteria.
Paper: Support Vector Machine Active Learning with Applications to Text Classification, Simon Tong et al. (2001). This work adapts version-space reduction and active querying strategies to support vector machines for text classification tasks.

Abstract

We consider the problem of using queries to learn an unknown concept. Several types of queries are described and studied: membership, equivalence, subset, superset, disjointness, and exhaustiveness queries. Examples are given of efficient learning methods using various subsets of these queries for formal domains, including the regular languages, restricted classes of context-free languages, the pattern languages, and restricted types of propositional formulas. Some general lower bound techniques are given. Equivalence queries are compared with Valiant's criterion of probably approximately correct identification under random sampling.

Topics

first order logic pattern languages propositional formulas regular languages

Keywords

concept learning equivalence queries membership queries superset queries subset queries disjointness queries exhaustiveness queries inductive inference probabilistic identification hypothesis space

1. Introduction
1.1 An example: Poker hands
1.2 Exact and probabilistic identification
2. Equivalence queries
2.1 Exhaustive search
2.2 A logarithmic strategy: Majority vote
2.3 Some general lower bound techniques
2.4 Equivalence queries and stochastic equivalence
2.5 Equivalence queries: k-CNF and k-DNF formulas
3. Membership queries
3.1 Monotone DNF formulas
3.2 Other methods using membership and equivalence queries
4. Subset and superset queries
4.1 The pattern languages
5. Disjointness queries
5.1 Queries in Shapiro's debugging system
5.2 k-CNF formulas using disjointness queries
5.3 A very small class of context-free languages
6. The double sunflower: A lower bound for all six queries
7. Summary, remarks, and open questions
Acknowledgements
References

Knowls

Knowl 1 — Query Types in Concept Learning
definition
In the query learning framework, an unknown target concept $L^* \subseteq U$ from a hypothesis space $L_1, L_2, \dots \subseteq U$ over a universal set $U$ is identified by presenting queries to specific oracles. The standard query types are:
- Membership Query: The input is an element $x \in U$ . The oracle replies yes if $x \in L^*$ , and no if $x \notin L^*$ .
- Equivalence Query: The input is a concept $L \subseteq U$ . The oracle replies yes if $L = L^*$ . If $L \neq L^*$ , the oracle replies no and supplies a counterexample $x \in L \oplus L^*$ , where $L \oplus L^* = (L \setminus L^*) \cup (L^* \setminus L)$ is the symmetric difference.
- Subset Query: The input is a concept $L \subseteq U$ . The oracle replies yes if $L \subseteq L^*$ . If $L \not\subseteq L^*$ , the oracle replies no and supplies a counterexample $x \in L \setminus L^*$ .
- Superset Query: The input is a concept $L \subseteq U$ . The oracle replies yes if $L \supseteq L^*$ . If $L \not\supseteq L^*$ , the oracle replies no and supplies a counterexample $x \in L^* \setminus L$ .
- Disjointness Query: The input is a concept $L \subseteq U$ . The oracle replies yes if $L \cap L^* = \emptyset$ . If $L \cap L^* \neq \emptyset$ , the oracle replies no and supplies a counterexample $x \in L \cap L^*$ .
- Exhaustiveness Query: The input is a concept $L \subseteq U$ . The oracle replies yes if $L \cup L^* = U$ . If $L \cup L^* \neq U$ , the oracle replies no and supplies a counterexample $x \in U \setminus (L \cup L^*)$ .
Restricted queries refer to variants of the non-membership queries where the oracle returns only a boolean yes or no response without providing a counterexample. Unless specified otherwise, any query taking a set $L$ as input requires $L$ to be an element of the specified hypothesis space.
Knowl 2 — Double Sunflower Lower Bound for the Full Query Set
theoretical result
For any integer $n > 0$ , let $N = 2^n$ . Let $X = \{x_1, x_2, \dots, x_N\}$ and $Y = \{y_1, y_2, \dots, y_N\}$ be two disjoint sets of $N$ points each, and let $z_1, z_2 \notin X \cup Y$ be two distinct points. Define the universal set $U = X \cup Y \cup \{z_1, z_2\}$ , which contains $2^{n+1} + 2$ elements. The hypothesis space consists of the $N$ distinct concepts:

$C_j = \{z_1, x_j\} \cup (Y \setminus \{y_j\}), \quad \text{for } j = 1, 2, \dots, N.$

Every concept $C_j$ contains $z_1$ , excludes $z_2$ , contains exactly one element of $X$ ( $x_j$ ), and contains all elements of $Y$ except $y_j$ .

Any algorithm that exactly identifies an unknown concept $L^* \in \{C_1, \dots, C_N\}$ using any combination of equivalence, membership, subset, superset, disjointness, and exhaustiveness queries (even with counterexamples provided for non-membership queries) must make at least $N - 1 = 2^n - 1$ queries in the worst case.
Knowl 3 — Simulation of Equivalence Queries via Random Sampling for PAC Identification
theoretical result
Let $U$ be a universal set, $D$ an arbitrary probability distribution on $U$ , and $EX()$ a sampling oracle that repeatedly draws an element $x \in U$ according to $D$ and returns $(x, \mathbb{I}[x \in L^*])$ for an unknown target concept $L^* \subseteq U$ . The probability difference between two concepts $L, L' \subseteq U$ under $D$ is defined as:

$d(L, L') = \sum_{x \in L \oplus L'} \Pr(x).$

Any algorithm that exactly identifies $L^*$ using equivalence queries can be transformed into an algorithm that probably approximately correctly (PAC) identifies $L^*$ (producing a hypothesis $L_j$ satisfying $d(L_j, L^*) \le \epsilon$ with confidence at least $1 - \delta$ , where $\epsilon, \delta \in (0, 1)$ ) using calls to $EX()$ .

In place of the $i$ -th equivalence query with hypothesis $L$ , the learner draws:

$q_i = \left\lceil \frac{1}{\epsilon} \left(\ln \frac{1}{\delta} + i \ln 2\right) \right\rceil$

samples from $EX()$ . If any sample $x$ is inconsistent with $L$ ( $x \in L \oplus L^*$ ), the simulation provides $x$ as a counterexample and continues. If $L$ is consistent with all $q_i$ samples, the simulation treats the equivalence query as returning yes and terminates with $L$ . The probability that this procedure outputs a hypothesis that is not an $\epsilon$ -approximation is bounded by:

$\sum_{i=1}^\infty (1 - \epsilon)^{q_i} \le \sum_{i=1}^\infty e^{-\epsilon q_i} \le \sum_{i=1}^\infty \frac{\delta}{2^i} \le \delta.$
Knowl 4 — Pairwise Intersection and Union Lower Bound Criteria
theoretical result
Let a hypothesis space contain $N$ distinct concept sets $L_1, L_2, \dots, L_N \subseteq U$ .

Intersection Bounds:
1. If there exists a set $L_\cap \subseteq U$ such that $L_i \cap L_j = L_\cap$ for all distinct indices $i \neq j$ , and $L_\cap$ belongs to the hypothesis space, then any algorithm that exactly identifies each $L_i$ using restricted equivalence, membership, and subset queries must make at least $N - 1$ queries in the worst case.
2. If $L_i \cap L_j = L_\cap$ for all distinct $i \neq j$ , and $L_\cap$ is not in the hypothesis space, then any algorithm that exactly identifies each $L_i$ using unrestricted equivalence (with counterexamples), membership, and subset queries must make at least $N - 1$ queries in the worst case.
Union Bounds (Dual):
1. If there exists a set $L_\cup \subseteq U$ such that $L_i \cup L_j = L_\cup$ for all distinct indices $i \neq j$ , and $L_\cup$ belongs to the hypothesis space, then any algorithm that exactly identifies each $L_i$ using restricted equivalence, membership, and superset queries must make at least $N - 1$ queries in the worst case.
2. If $L_i \cup L_j = L_\cup$ for all distinct $i \neq j$ , and $L_\cup$ is not in the hypothesis space, then any algorithm that exactly identifies each $L_i$ using unrestricted equivalence (with counterexamples), membership, and superset queries must make at least $N - 1$ queries in the worst case.
Knowl 5 — Exact Identification of Monotone DNF Formulas Using Equivalence and Membership Queries
algorithm
Monotone DNF formulas over $n$ Boolean variables $x_1, \dots, x_n$ contain no negative literals. An unknown monotone DNF formula $\phi^*$ with $m$ terms can be exactly identified in time polynomial in $n$ and $m$ using at most $m + 1$ equivalence queries and at most $m \cdot n$ membership queries.
Input: Equivalence oracle and membership oracle for unknown monotone DNF formula $\phi^*$ over variables $x_1, \dots, x_n$
Output: A monotone DNF formula $\phi$ equivalent to $\phi^*$
$\phi \leftarrow \text{false}$
loop
    Ask equivalence query with $\phi$
    if the answer is yes then
        return $\phi$
    else
        Receive counterexample assignment $a \in \{0, 1\}^n$ where $a(\phi^*) = 1$ and $a(\phi) = 0$
         $t \leftarrow \bigwedge_{\{i : a(x_i) = 1\}} x_i$
        for each variable $x_i$ appearing in $t$ do
            Let $t'$ be the term obtained by deleting $x_i$ from $t$
            Let $a'$ be the Boolean assignment setting all variables in $t'$ to 1 and all others to 0
            Ask membership query for $a'$
            if $a'(\phi^*) = 1$ then
                 $t \leftarrow t'$
         $\phi \leftarrow \phi \lor t$
The minimization loop reduces the initial term $t$ constructed from $a$ to a prime implicant of $\phi^*$ using at most $n$ membership queries. Each iteration adds a new prime implicant to $\phi$ that covers $a$ , guaranteeing progress until equivalence is achieved.
Knowl 6 — Exponential Lower Bound for Monotone DNF Without Counterexamples
theoretical result
For each positive integer $n$ , there exists a class $\mathcal{D}$ of $2^n$ monotone DNF formulas over $2n$ variables $\{x_1, y_1, x_2, y_2, \dots, x_n, y_n\}$ , each having $n + 1$ terms. Let:

$\phi_n = x_1 y_1 \lor x_2 y_2 \lor \dots \lor x_n y_n.$

The class $\mathcal{D}$ consists of all formulas of the form:

$\phi = T \lor \phi_n, \quad \text{where } T = P_1 P_2 \cdots P_n \text{ and each } P_i \in \{x_i, y_i\}.$

For any two distinct formulas $\phi_1, \phi_2 \in \mathcal{D}$ , the set of satisfying truth assignments common to both is exactly the set of assignments satisfying $\phi_n$ . Consequently, any algorithm that exactly identifies every formula in $\mathcal{D}$ using restricted equivalence queries (no counterexamples), membership queries, subset queries, disjointness queries, and exhaustiveness queries must make at least $2^n - 1$ queries in the worst case.
Knowl 7 — Exact Identification of Pattern Languages Using Restricted Superset Queries
algorithm
Let $A$ be a finite alphabet with $|A| \ge 2$ , and $X = \{x_1, x_2, \dots\}$ be an infinite set of variable symbols. A pattern $p \in (A \cup X)^+$ defines a language $L(p) \subseteq A^+$ consisting of all non-empty strings obtained by substituting strings from $A^+$ for each variable in $p$ .
Input: Finite alphabet $A$ , restricted superset oracle for unknown pattern $p^*$
Output: A pattern $p$ equivalent to $p^*$
$k \leftarrow 1$
while Superset query " $L(x_1 x_2 \cdots x_{k+1}) \supseteq L(p^*)$ ?" returns yes do
     $k \leftarrow k + 1$
for $i \leftarrow 1$ to $k$ do
     $s_i \leftarrow \text{variable}$
    for each $a \in A$ do
        if Superset query " $L(x_1 \cdots x_{i-1} a x_{i+1} \cdots x_k) \supseteq L(p^*)$ ?" returns yes then
             $s_i \leftarrow a$
            break
for each pair of indices $1 \le i < j \le k$ with $s_i = \text{variable}$ and $s_j = \text{variable}$ do
    Let $p_{i,j}$ be $x_1 x_2 \cdots x_k$ with both $x_i$ and $x_j$ replaced by a single variable $x$
    if Superset query " $L(p_{i,j}) \supseteq L(p^*)$ ?" returns yes then
        Mark positions $i$ and $j$ as sharing the same variable
Construct pattern $p$ from $s_1 \cdots s_k$ by assigning identical variable names to identified positions
return $p$
The algorithm exactly identifies a target pattern of length $k$ in polynomial time using at most $(k + 1) + k|A| + k(k - 1)/2$ restricted superset queries.

Conversely, any algorithm that exactly identifies all patterns of length $n$ using equivalence, membership, and subset queries requires at least $2^n - 1$ queries in the worst case.
Knowl 8 — Majority Vote Strategy for Unrestricted Equivalence Queries
algorithm
When equivalence queries are not restricted to the hypothesis space (allowing arbitrary subsets of the universal set $U$ as query inputs), any finite hypothesis space $\{L_1, \dots, L_N\}$ can be learned in at most $\lfloor \log_2 N \rfloor$ equivalence queries.
Input: Finite hypothesis space $\{L_1, \dots, L_N\} \subseteq 2^U$ , unrestricted equivalence oracle for unknown $L^* \in \{L_1, \dots, L_N\}$
Output: A concept $M \subseteq U$ equivalent to $L^*$
$S \leftarrow \{1, 2, \dots, N\}$
while $|S| > 1$ do
    Define $M_S = \{x \in U : |\{i \in S : x \in L_i\}| > |S| / 2\}$
    Ask equivalence query with $M_S$
    if the answer is yes then
        return $M_S$
    else
        Receive counterexample $x \in M_S \oplus L^*$
        if $x \in M_S$ then
             $S \leftarrow \{i \in S : x \in L_i\}$
        else
             $S \leftarrow \{i \in S : x \notin L_i\}$
Let $i$ be the unique index remaining in $S$
return $L_i$
Each negative query eliminates more than $|S|/2$ hypotheses from $S$ , guaranteeing termination in at most $\lfloor \log_2 N \rfloor$ queries.
Knowl 9 — Exact Identification of k-CNF Formulas Using Equivalence Queries
algorithm
The class $k$ -CNF consists of propositional formulas in conjunctive normal form over $n$ variables with at most $k$ literals per clause. The total number of such clauses is at most $(2n + 1)^k$ .
Input: Variables $x_1, \dots, x_n$ , parameter $k$ , equivalence oracle for unknown $k$ -CNF formula $\phi^*$
Output: A $k$ -CNF formula $\phi$ equivalent to $\phi^*$
$\phi \leftarrow$ conjunction of all possible clauses over $x_1, \dots, x_n$ with at most $k$ literals
loop
    Ask equivalence query with $\phi$
    if the answer is yes then
        return $\phi$
    else
        Receive counterexample assignment $a \in \{0, 1\}^n$ where $a(\phi^*) = 1$ and $a(\phi) = 0$
        Remove from $\phi$ all clauses $C$ such that $a(C) = 0$
This algorithm implicitly executes the majority-vote strategy over consistent sub-formulas. Each counterexample eliminates at least one clause from $\phi$ . The algorithm runs in time polynomial in $n^k$ and asks at most $(2n + 1)^k$ equivalence queries. By duality, $k$ -DNF formulas are learnable with at most $(2n + 1)^k$ equivalence queries.

Conversely, exact identification of 1-CNF formulas using restricted equivalence, membership, and subset queries requires at least $2^n - 1$ queries in the worst case.
Knowl 10 — Exact Identification of k-CNF Formulas Using Restricted Disjointness Queries
algorithm
Let $T_k$ be the set of all terms (conjunctions of $k$ or fewer literals) over $n$ Boolean variables $x_1, \dots, x_n$ , where $|T_k| \le (2n + 1)^k$ . A $k$ -CNF formula $\phi^*$ can be identified using only restricted disjointness queries.
Input: Variables $x_1, \dots, x_n$ , parameter $k$ , restricted disjointness oracle for unknown $k$ -CNF formula $\phi^*$
Output: A $k$ -CNF formula $\phi$ equivalent to $\phi^*$
$\mathcal{C} \leftarrow \emptyset$
for each term $t \in T_k$ do
    Ask restricted disjointness query: "Is the set of assignments satisfying $t$ disjoint from $\phi^*$ ?"
    if the answer is yes then
         $\mathcal{C} \leftarrow \mathcal{C} \cup \{\neg t\}$
$\phi \leftarrow \bigwedge_{c \in \mathcal{C}} c$
return $\phi$
Because the negation $\neg t$ of any term $t \in T_k$ is a clause with at most $k$ literals, $\phi$ is a valid $k$ -CNF formula. A satisfying assignment for $\phi^*$ falsifies every term disjoint from $\phi^*$ and thus satisfies $\phi$ ; conversely, the negation of each clause of $\phi^*$ is a term in $T_k$ disjoint from $\phi^*$ , ensuring $\phi \equiv \phi^*$ . The algorithm uses at most $(2n + 1)^k$ restricted disjointness queries and runs in time polynomial in $n^k$ . Dually, $k$ -DNF formulas are exactly learnable using at most $(2n + 1)^k$ restricted exhaustiveness queries.

Knowl 11 — Taxonomy of Sufficient and Insufficient Query Sets Across Concept Classes

data/table

The paper characterizes the exact learnability of various concept domains under different combinations of query types. Query types are denoted by numbers:

(1) Equivalence queries ( $1^-$ denotes restricted equivalence without counterexamples)
(2) Membership queries ( $2^+$ denotes nonterminal membership queries for CFLs)
(3) Subset queries
(4) Superset queries ( $4^-$ denotes restricted superset queries)
(5) Disjointness queries ( $5^-$ denotes restricted disjointness queries)
(6) Exhaustiveness queries ( $6^-$ denotes restricted exhaustiveness queries)

Domain	Reference	Sufficient Queries	Insufficient Queries
Singleton languages	2.1	4	1, 2, 3, 5
$k$ -CNF formulas	2.5, 5.2	1 or $5^-$	$1^-$ , 2, 3
$k$ -DNF formulas	2.5, 5.2	1 or $6^-$	$1^-$ , 2, 4
Monotone DNF formulas	3.1	1, 2	$1^-$ , 2, 3, 5, 6
Regular languages	3.2	1, 2	$1^-$ , 2, 3
$k$ -bounded CFLs	3.2	1, $2^+$	—
$k$ -term DNF formulas	3.2	1, 2	$1^-$ , 2, 3
$k$ -clause CNF formulas	3.2	1, 2	$1^-$ , 2, 4
Pattern languages	4.1	$4^-$	1, 2, 3
Very restricted CFLs	5.3	5 or (1, 2)	—
Double sunflower	6	none	1, 2, 3, 4, 5, 6

The table illustrates key separations: restricted superset queries ( $4^-$ ) suffice for pattern languages where equivalence, membership, and subset queries ( $1, 2, 3$ ) fail; equivalence queries with counterexamples ( $1$ ) succeed for $k$ -CNF, whereas restricted equivalence ( $1^-$ ) fails even alongside membership and subset queries; and the double sunflower domain cannot be learned even with all six query types combined.

Coverage note — The artificial class of context-free languages defined by additive integer functions (Section 5.3) was omitted as it serves purely as a toy example of disjointness queries without introducing general techniques beyond the main results. Review summaries of external algorithms (e.g., deterministic finite automata, $k$-bounded context-free grammars, and Prolog debugging) were omitted as background context.

References

1.Angluin, D. (1980). Finding patterns common to a set of strings. Journal of Computer and System Sciences, 21, 46-62.
2.Angluin, D. (1986). Types of queries for concept learning (Technical Report YALEU/DCS/RR-479). New Haven, CT: Yale University, Department of Computer Science.
3.Angluin, D. (1987a). Learning k-bounded context-free grammars (Technical Report YALEU/DCS/RR-557). New Haven, CT: Yale University, Department of Computer Science.
4.Angluin, D. (1987b). Learning k-term DNF formulas using queries and counterexamples (Technical Report YALEU/DCS/RR-559). New Haven, CT: Yale University, Department of Computer Science.
5.Angluin, D. (1987c). Learning propositional Horn sentences with hints (Technical Report YALEU/DCS/RR-590). New Haven, CT: Yale University, Department of Computer Science.
6.Angluin, D. (1987d). Learning regular sets from queries and counterexamples. Information and Computation, 75, 87-106.
7.Angluin, D., & Laird, P. (1987). Learning from noisy examples. Machine Learning, 2, 343-370.
8.Angluin, D., & Smith, C. (1983). Inductive inference: Theory and methods. Computing Surveys, 15, 237-269.
9.Barzdin, J. M., & Freivald, R. V. (1972). On the prediction of general recursive functions. Soviet Mathematics Doklady, 13, 1224-1228.
10.Berman, P., & Roos, R. (1987). Learning one-counter languages in polynomial time. Proceedings of the Twenty-Eighth IEEE Symposium on Foundations of Computer Science (pp. 61-67). New York: The Institute of Electrical and Electronics Engineers.
11.Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. (1986). Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension. Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (pp. 273-282). Berkeley, CA: The Association for Computing Machinery.
12.Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. (1987). Learnability and the Vapnik-Chervonenkis dimension (Technical Report UCSC-CRL-87-20). Santa Cruz: University of California, Computer Research Laboratory.
13.Haussler, D. (1986). Quantifying the inductive bias in concept learning. Proceedings of the Fifth National Conference on Artificial Intelligence (pp. 485-489). Philadelphia, PA: Morgan Kaufmann.
14.Haussler, D. (in press). Quantifying the inductive bias: AI learning algorithms and Valiant's framework. Artificial Intelligence.
15.Kearns, M., & Li, M. (1987). Learning in the presence of malicious errors (Technical Report TR-03-87). Cambridge, MA: Harvard University, Center for Research in Computing Technology.
16.Kearns, M., Li, M., Pitt, L., & Valiant, L. (1987). On the learnability of Boolean formulae. Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (pp. 285-295). New York: The Association for Computing Machinery.
17.Knobe, B., & Knobe, K. (1976). A method for inferring context-free grammars. Information and Control, 31, 129-146.
18.Laird, P. (1987). Learning from good data and bad. Doctoral dissertation, Department of Computer Science, Yale University, New Haven, CT.
19.Levy, L., & Joshi, A. (1978). Skeletal structural descriptions. Information and Control, 39, 192-211.
20.Littlestone, N. (1987). Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2, 285-318.
21.Pitt, L., & Valiant, L. (1986). Computational limitations on learning from examples (Technical Report TR-05-86). Cambridge, MA: Harvard University, Center for Research in Computing Technology.
22.Sakakibara, Y. (1987a). Inductive inference of logic programs based on algebraic semantics (Technical Report No. 79). Numazu, Japan: Fujitsu Limited, International Institute for Advanced Study of Social Information Science.
23.Sakakibara, Y. (1987b). Inferring parsers of context-free languages from structural examples (Technical Report No. 81). Numazu, Japan: Fujitsu Limited, International Institute for Advanced Study of Social Information Science.
24.Sammut, C., & Banerji, R. (1986). Learning concepts by asking questions. In R. S. Michalski, J. G. Carbonell, & T. M. Mitchell (Eds.), Machine learning: An artificial intelligence approach (Vol. 2). Los Altos, CA: Morgan Kaufmann.
25.Shapiro, E. (1981). A general incremental algorithm that infers theories from facts. Proceedings of the Seventh International Joint Conference on Artificial Intelligence (pp. 446-451). Vancouver, B.C., Canada: Morgan Kaufman.
26.Shapiro, E. (1982). Algorithmic program diagnosis. Proceedings of the Ninth ACM Symposium on Principles of Programming Languages (pp. 299-308). Albuquerque, NM: The Association for Computing Machinery.
27.Shapiro, E. (1983). Algorithmic program debugging. Cambridge, MA: MIT Press.
28.Valiant, L. G. (1984). A theory of the learnable. Communications of the ACM, 27, 1134-1142.
29.Valiant, L. G. (1985). Learning disjunctions of conjunctions. Proceedings of the Ninth International Joint Conference on Artificial Intelligence (pp. 560-566). Los Angeles, CA: Morgan Kaufmann.

Citation

MLA

Angluin, D. “Queries and Concept Learning”. Machine Learning, vol. 2, no. 4, 1988, pp. 319–42, https://doi.org/10.1023/A:1022821128753.

APA

Angluin, D. (1988). Queries and Concept Learning. Machine Learning, 2(4), 319–342. https://doi.org/10.1023/A:1022821128753

Chicago

Angluin, D. 1988. “Queries and Concept Learning”. Machine Learning 2 (4): 319–42. https://doi.org/10.1023/A:1022821128753.

Harvard

Angluin, D. (1988) “Queries and Concept Learning”, Machine Learning, 2(4), pp. 319–342. Available at: https://doi.org/10.1023/A:1022821128753.

Vancouver

1. Angluin D (1988) Queries and Concept Learning. Machine Learning 2:319–342

BibTeX

@article{Angluin_1988, title={Queries and Concept Learning}, volume={2}, ISSN={1573-0565}, url={http://dx.doi.org/10.1023/A:1022821128753}, DOI={10.1023/a:1022821128753}, number={4}, journal={Machine Learning}, publisher={Springer Science and Business Media LLC}, author={Angluin, Dana}, year={1988}, month=Apr, pages={319–342} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Queries and concept learning

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Query Types in Concept Learning

Knowl 2 — Double Sunflower Lower Bound for the Full Query Set

Knowl 3 — Simulation of Equivalence Queries via Random Sampling for PAC Identification

Knowl 4 — Pairwise Intersection and Union Lower Bound Criteria

Knowl 5 — Exact Identification of Monotone DNF Formulas Using Equivalence and Membership Queries

Knowl 6 — Exponential Lower Bound for Monotone DNF Without Counterexamples

Knowl 7 — Exact Identification of Pattern Languages Using Restricted Superset Queries

Knowl 8 — Majority Vote Strategy for Unrestricted Equivalence Queries

Knowl 9 — Exact Identification of k-CNF Formulas Using Equivalence Queries

Knowl 10 — Exact Identification of k-CNF Formulas Using Restricted Disjointness Queries

Knowl 11 — Taxonomy of Sufficient and Insufficient Query Sets Across Concept Classes

References

Citation

BibTeX

Access the Paper