Teaching via Best-Case Counterexamples in the Learning-with-Equivalence-Queries Paradigm

Akash Kumar, Yuxin Chen, Adish SinglaNeurIPS 2021 · OpenReview

Summary

This paper introduces LwEQ-TD, a novel framework for measuring the "teaching dimension" in scenarios where a helpful teacher provides optimal counterexamples to a learner’s queries. The authors demonstrate that a best-case teacher can achieve a massive reduction in query complexity—often reducing it to a small constant—compared to the exponential or linear bounds typically seen with adversarial or random teachers.

Introduction: The Role of the Teacher

In traditional "learning-with-queries" paradigms, a learner attempts to identify a target concept by asking equivalence queries (e.g., "Is this hypothesis correct?"). Most existing research assumes the teacher is either adversarial (providing the least helpful counterexample) or random. This assumption naturally leads to high query complexity, meaning the learner must ask many questions to isolate the correct answer.

However, in many real-world scenarios, teachers are actively helpful and aim to "steer" the learner toward the truth as efficiently as possible. This paper bridges a critical gap between Machine Teaching (where teachers optimally select data) and Query-based Learning. The central question is: If a teacher provides the most informative counterexample possible, how much faster can a learner find the target?

An overview of different teaching settings in the context of LwEQ and LfS paradigms.

Methodology: Formalizing LwEQ-TD

The authors formalize this helpful teaching setting using a new metric called the Learning-with-Equivalence-Queries Teaching Dimension (LwEQ-TD). Key components of their theoretical approach include:

  • Recursive Cost Function: They define a recursive function to calculate the minimum number of queries needed to steer a specific type of learner to a target hypothesis.
  • Learner Modeling: The framework does not assume a single, monolithic type of learner. Instead, it analyzes a spectrum of learners, ranging from "constant" learners (who pick any valid hypothesis consistent with the data) to "global" learners (who follow a fixed preference ranking).
  • Ranking Framework: To connect their work to existing literature, the authors utilize a mathematical framework of "ranking functions" to describe how different learners choose their next query based on the history of received counterexamples.

Evaluated Hypothesis Classes

As a theoretical machine learning paper, the study evaluates LwEQ-TD on three fundamental hypothesis classes (mathematical structures used to represent concepts) rather than empirical datasets:

  1. Axes-aligned hyperplanes: Concepts defined by a single threshold on one dimension.
  2. Monotone monomials: Logical "AND" combinations of variables without negations.
  3. Orthogonal rectangles: Multi-dimensional boxes used to classify data points.

Key Insights

  • The Power of Helpfulness: The most striking insight is the sheer power of best-case counterexamples. For many complex concept classes, query complexity drops from being dependent on the size of the space (e.g., dimensions $d$ or variables $n$) to a small constant like 1 or 2.
  • A Unified Theory: The authors prove that LwEQ-TD is deeply connected to the "Learning-from-Samples" (LfS) paradigm. They show that under certain conditions, LwEQ-TD is mathematically equivalent to well-known metrics like the Recursive Teaching Dimension (RTD) and the Non-Clashing Teaching Dimension (NCTD).
  • Collusion-Free Teaching: A common pitfall in teaching theory is "collusion," where a teacher and learner use a secret code to bypass actual learning. The authors use "collusion-free" ranking functions to ensure their results reflect genuine, generalizable learning.

Key Results

The paper provides a rigorous quantitative comparison across different teacher types (Adversarial/Worst-TEQ, Random-TEQ, and Best-TEQ). The introduction of the best-case teacher yields dramatic improvements:

  • Axes-aligned hyperplanes: While an adversarial teacher can force $\Omega(d + \log n)$ queries, a best-case teacher needs only 1 query.
  • Monotone monomials: Complexity drops from $\Omega(n)$ (adversarial/random) to exactly 1 query.
  • Orthogonal rectangles: Complexity drops from $\Omega(d \cdot \log n)$ to exactly 2 queries.
Lower and upper bounds on query complexity for various hypothesis classes, highlighting the efficiency of Best-TEQ.

Limitations and Future Work

  • Proper vs. Improper Queries: This study focuses on "proper" queries, where the learner must pick a hypothesis from within the target class. The authors suggest that allowing "improper" queries (picking a hypothesis from outside the class) could potentially reduce complexity even further.
  • Complex Automata: The current work focuses on geometric and logical classes. A major next step is applying LwEQ-TD to more complex structures like Deterministic Finite Automata (DFAs) or Context-Free Grammars (CFGs), where worst-case query complexity is known to be exponential.
  • Mixed Query Types: Real-world learning often involves a mix of equivalence queries ("Is this the exact concept?") and membership queries ("Does this specific point belong to the concept?"). Extending the TD framework to handle multiple query types simultaneously is a promising direction for future research.

Summary updated

Abstract

We study the sample complexity of teaching, termed as "teaching dimension" (TD) in the literature, for the learning-with-equivalence-queries (LwEQ) paradigm. More concretely, we consider a learner who asks equivalence queries (i.e., "is the queried hypothesis the target hypothesis?"), and a teacher responds either "yes" or "no" along with a counterexample to the queried hypothesis. This learning paradigm has been extensively studied when the learner receives worst-case or random counterexamples; in this paper, we consider the optimal teacher who picks best-case counterexamples to teach the target hypothesis within a hypothesis class. For this optimal teacher, we introduce LwEQ-TD, a notion of TD capturing the teaching complexity (i.e., the number of queries made) in this paradigm. We show that a significant reduction in queries can be achieved with best-case counterexamples, in contrast to worst-case or random counterexamples, for different hypothesis classes. Furthermore, we establish new connections of LwEQ-TD to the well-studied notions of TD in the learning-from-samples paradigm.
BibTeX
@inproceedings{kumar2021teaching,
  author = {Akash Kumar and Yuxin Chen and Adish Singla},
  title = {{Teaching via Best-Case Counterexamples in the Learning-with-Equivalence-Queries Paradigm}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=WE44rBHoN-7},
}
Figure