Title: A General Framework for Robust Interactive Learning,
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.