Efficient interactive multiclass learning from binary feedback

Hung Ngo, Matthew Luciw, Ngo Anh Vien, Jawad Nagi, Alexander Förster, Jürgen Schmidhuber

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

We introduce a novel algorithm called upper confidence-weighted learning (UCWL) for online multiclass learning from binary feedback (e.g., feedback that indicates whether the prediction was right or wrong). UCWL combines the upper confidence bound (UCB) framework with the soft confidence-weighted (SCW) online learning scheme. In UCB, each instance is classified using both score and uncertainty. For a given instance in the sequence, the algorithm might guess its class label primarily to reduce the class uncertainty. This is a form of informed exploration, which enables the performance to improve with lower sample complexity compared to the case without exploration. Combining UCB with SCW leads to the ability to deal well with noisy and nonseparable data, and state-of-the-art performance is achieved without increasing the computational cost. A potential application setting is human-robot interaction (HRI), where the robot is learning to classify some set of inputs while the human teaches it by providing only binary feedback-or sometimes even the wrong answer entirely. Experimental results in the HRI setting and with two benchmark datasets from other settings show that UCWL outperforms other state-of-the-art algorithms in the online binary feedback setting-and surprisingly even sometimes outperforms state-of-the-art algorithms that get full feedback (e.g., the true class label), whereas UCWL gets only binary feedback on the same data sequence.
Original languageEnglish (US)
JournalACM Transactions on Interactive Intelligent Systems
Volume4
Issue number3
DOIs
StatePublished - Oct 14 2014
Externally publishedYes

ASJC Scopus subject areas

  • Human-Computer Interaction
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Efficient interactive multiclass learning from binary feedback'. Together they form a unique fingerprint.

Cite this