Learning From Discriminative Feature Feedback

Authors:
Sanjoy Dasgupta UC San Diego
Sivan Sabato Ben-Gurion University of the Negev
Nick Roberts UC San Diego
Akansha Dey UCSD

Introduction:

The authors consider the problem of learning a multi-class classifier from labels as well as simple explanations that the authors call "discriminative features".The authors present an efficient online algorithm for learning from such feedback and the authors give tight bounds on the number of mistakes made during the learning process.

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.

You may want to know: