TL;DR
This paper introduces a framework for training classifiers using "discriminative feature feedback"—where a teacher provides not just a label, but a specific feature that distinguishes a misclassified example from a similar one. The authors present an efficient online algorithm that achieves a mistake bound dependent only on the complexity of the target concept, making it highly effective even in infinite-dimensional feature spaces.
The Problem: Bridging the Human-Machine Teaching Gap
In traditional supervised learning, the communication between a human and a machine is remarkably narrow: the human provides a label, and the machine updates its internal weights. This is far more rigid than how humans teach one another. If you were teaching a child to tell a zebra from a horse, you wouldn't just say "No, that's a zebra"; you’d likely add, "See the stripes? Horses don't have those."
The authors address the gap between this natural human "explanation" and algorithmic learning. While previous work explored predictive features (features that indicate a specific class globally, like the word "filibuster" indicating "politics"), this paper focuses on discriminative features. These are features that distinguish between two specific groups, even if they aren't unique to the entire class (e.g., "stripes" distinguish zebras from horses, but not necessarily from tigers).
Methods: An Online Learning Algorithm
The authors propose an online learning model where interaction happens in rounds:
- Prediction: The learner receives a new instance and predicts a label, citing a "similar" previously seen instance as a rationale.
- Correction: If the prediction is wrong, the "teacher" provides the correct label and a discriminative feature—a Boolean attribute that is true for the current instance but false for the cited similar instance.
The Algorithm: The learner maintains a list $L$ of representative instances. For each instance in $L$, it stores a label and a "conjunction" (a set of features that must all be true).
- If a new point satisfies an existing conjunction but has the wrong label, the learner adds the negation of the teacher's provided feature to that conjunction to "narrow" it.
- If a new point satisfies no existing conjunctions, it is added to the list as a new rule.
The beauty of this approach is its simplicity: it builds a logical decision list that evolves dynamically based on contrastive explanations.
Empirical Evaluation: The ZOO Dataset
The authors evaluated their algorithm using the ZOO dataset from the UCI Machine Learning Repository. This dataset contains 101 animals characterized by 21 Boolean features (like hair, eggs, milk, aquatic). The task is to classify animals into seven categories (mammal, bird, reptile, fish, amphibian, insect, and "other").
They simulated a teacher who, upon a mistake, picks a random feature that distinguishes the misclassified animal from the learner's suggested "similar" animal.
Key Insights and Results
- Theoretical Bound: The authors prove a tight mistake bound of $m^2$, where $m$ is the number of underlying clusters in the data. This is a significant result in computational learning theory, as learning DNF formulas is typically considered computationally hard in standard supervised settings.
- Concept Complexity vs. Feature Count: The most striking insight is that the number of mistakes the algorithm makes does not depend on the total number of available features. It only depends on $m$, the number of "clusters" or "terms" needed to represent the concept. This means the algorithm can theoretically handle an infinite number of features without losing efficiency.
- Empirical Performance: On the ZOO dataset, starting from a single default prediction ("frog"), the algorithm reached perfect convergence after only 14 mistakes.
- The Power of "Why": By asking the teacher to justify a correction relative to a specific mistake, the learner identifies relevant dimensions in high-dimensional space much faster than by looking at labels alone.
- Interpretability: The resulting model is a human-readable decision list. For example, it learned rules like:
if (not backbone) AND (not six-legs) then "other" (e.g., worm).
Limitations and Future Work
- Teacher Reliability: The current model assumes a "perfect" teacher who always provides a correct, noise-free discriminative feature. The authors acknowledge that real-world human feedback is often noisy or inconsistent, which could derail the current algorithm.
- Model Conciseness: While the algorithm is guaranteed to converge, the resulting decision list might be longer or more complex than necessary. Future work could explore how to prune these lists to make them more interpretable without losing the $m^2$ mistake bound.
- Feature Discovery: The model assumes features are Boolean and already exist. Integrating this with deep learning—where a neural net might "propose" low-level features for a human to name—is a promising but unexplored direction.
Summary updated