Learning from discriminative feature feedback

Sanjoy Dasgupta, Akansha Dey, Nicholas Roberts, Sivan SabatoNeurIPS 2018 · OpenReview

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:

  1. Prediction: The learner receives a new instance and predicts a label, citing a "similar" previously seen instance as a rationale.
  2. 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.
Online learning algorithm for discriminative feature feedback

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.

Trace of the algorithm on the ZOO dataset

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

Abstract

We consider the problem of learning a multi-class classifier from labels as well as simple explanations that we call "discriminative features". We show that such explanations can be provided whenever the target concept is a decision tree, or more generally belongs to a particular subclass of DNF formulas. We present an efficient online algorithm for learning from such feedback and we give tight bounds on the number of mistakes made during the learning process. These bounds depend only on the size of the target concept and not on the overall number of available features, which could be infinite. We also demonstrate the learning procedure experimentally.
BibTeX
@inproceedings{dasgupta2018learning,
  author = {Sanjoy Dasgupta and Akansha Dey and Nicholas Roberts and Sivan Sabato},
  title = {{Learning from discriminative feature feedback}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=H1beuObu-S},
}
Figure