Timezone: »

Learning from discriminative feature feedback
Sanjoy Dasgupta · Sivan Sabato · Nicholas Roberts · Akansha Dey

Wed Dec 05 07:45 AM -- 09:45 AM (PST) @ Room 517 AB #113

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.

Author Information

Sanjoy Dasgupta (UC San Diego)
Sivan Sabato (Ben-Gurion University of the Negev)
Nicholas Roberts (UC San Diego)
Akansha Dey (UCSD)

More from the Same Authors