A General Framework for Robust Interactive Learning

Ehsan Emamjomeh-Zadeh, David Kempe

Introduction

Most research in interactive learning centers on binary classification: a system proposes a label, and a human user corrects it. However, real-world applications frequently demand the learning of much more complex structures, such as how a user prefers to rank search results or how they want data points clustered.

This paper introduces a unified theoretical framework for interactive learning that extends beyond simple classification to encompass complex models like rankings and clusterings. By representing the space of possible models as a graph, the authors prove that a target model can be learned efficiently—even when the user's feedback is frequently noisy or adversarial.

The Challenges: Complexity and Noise

Moving beyond binary classification introduces two major hurdles:

  1. Complexity: There is no "one-size-fits-all" algorithm for fundamentally different types of models, such as rankings versus clusterings.
  2. Noise: Human feedback is rarely perfect. Users make mistakes, or different users might have slightly conflicting preferences.

The authors address these challenges by developing a general mathematical "language" to describe diverse learning tasks, alongside a robust algorithm capable of succeeding even when user feedback is incorrect nearly half the time.

A Geometric Approach to Feedback

The core innovation of this paper is the Graph Model for Feedback. The authors represent the set of all possible models (for instance, all $n!$ possible ways to rank $n$ items) as nodes in a weighted graph $G$.

This framework relies on a crucial geometric constraint called the Shortest Path Property. It assumes that if the algorithm proposes a model $s$ and the true target model is $s^*$, any correct piece of user feedback $s'$ must lie on a shortest path from $s$ to $s^*$ in the graph $G$.

This powerful insight treats user feedback as a geometric constraint. If feedback always moves the system "closer" to the goal within a specific graph structure, learning effectively becomes a structured search problem. The authors demonstrate how different types of feedback correspond to different graph structures. For example, if a user only points out adjacent items that are out of order, the underlying graph resembles an "adjacent transposition" (Bubble Sort) graph. If they can move an item anywhere, it becomes a weighted "insertion" graph.

The Algorithm: Binary Search in Graphs

Leveraging the shortest path property, the authors adapt an algorithm known as Binary Search in Graphs.

  • Without Noise: The algorithm identifies a "median" model that effectively halves the search space (the "version space") with each query, regardless of the specific feedback the user provides.
  • With Noise: When feedback can be wrong (with probability $1-p$), the algorithm employs a weight-based approach similar to the Multiplicative Weights Update. It maintains likelihoods for each model and updates them based on feedback, allowing the system to recover from "wrong turns" caused by noisy input.

To handle the computational explosion of tracking every possible model, the authors propose using Monte Carlo sampling to efficiently find the next model to propose. By framing the problem through this graph lens, noise resilience emerges as a fundamental property of the search space's geometry rather than a feature of a specific classification algorithm.

Key Results and Applications

As a theoretical paper, the authors provide rigorous proofs and apply their framework to three fundamental problem domains: ranking/ordering, clustering, and binary classification. They demonstrate that their general results either recover or improve upon existing specialized bounds.

  • Query Efficiency: The algorithm finds the target model $s^*$ in $O(\log N)$ queries, where $N$ is the total number of possible models.
  • Optimal Ranking: For ordering $n$ items, the framework achieves $O(n \log n)$ queries, which is mathematically optimal.
  • Clustering Bounds: For partitioning $n$ items into $k$ clusters, if the clusters come from a "small" concept class (e.g., low VC-dimension), the true clustering can be found in $O(k \log M)$ queries, where $M$ is the size of the concept class.
  • Robustness: Even with adversarial noise—where the user actively tries to mislead the algorithm—the query complexity only increases by a constant factor, provided the user is correct more than 50% of the time.

Limitations and Future Work

While the framework is highly query-efficient, it presents some limitations:

  • Computational Hardness of Noise: The algorithm is not always computationally efficient when noise is present. The authors prove that for rankings with noise, sampling the next model to propose is NP-hard.
  • Uniform Noise Assumption: The current model assumes the probability of a mistake ($1-p$) is identical for all types of feedback. In reality, users might be more likely to make mistakes on subtle differences than on glaring errors.
  • Improper Learning: The algorithm might propose "intermediate" models that do not strictly follow the rules of the target class (e.g., proposing a non-hyperplane classifier while trying to learn a hyperplane). While mathematically efficient, this could confuse a human user interacting with the system.

Summary updated

Abstract

We propose a general framework for interactively learning models, such as (binary or non-binary) classifiers, orderings/rankings of items, or clusterings of data points. Our framework is based on a generalization of Angluin's equivalence query model and Littlestone's online learning model: in each iteration, the algorithm proposes a model, and the user either accepts it or reveals a specific mistake in the proposal. The feedback is correct only with probability $p > 1/2$ (and adversarially incorrect with probability $1 - p$), i.e., the algorithm must be able to learn in the presence of arbitrary noise. The algorithm's goal is to learn the ground truth model using few iterations. Our general framework is based on a graph representation of the models and user feedback. To be able to learn efficiently, it is sufficient that there be a graph $G$ whose nodes are the models and (weighted) edges capture the user feedback, with the property that if $s, s^*$ are the proposed and target models, respectively, then any (correct) user feedback $s'$ must lie on a shortest $s$-$s^*$ path in $G$. Under this one assumption, there is a natural algorithm reminiscent of the Multiplicative Weights Update algorithm, which will efficiently learn $s^*$ even in the presence of noise in the user's feedback. From this general result, we rederive with barely any extra effort classic results on learning of classifiers and a recent result on interactive clustering; in addition, we easily obtain new interactive learning algorithms for ordering/ranking.
BibTeX
@inproceedings{emamjomehzadeh2017general,
  author = {Ehsan Emamjomeh-Zadeh and David Kempe},
  title = {{A General Framework for Robust Interactive Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
}
Figure