Upper Confidence Weighted Learning for Efficient Exploration in Multiclass Prediction with Binary Feedback

Ngo, Hung Quoc; Luciw, Matthew D.; Vien, Ngo Anh; Schmidhuber, Jürgen

Upper Confidence Weighted Learning for Efficient Exploration in Multiclass Prediction with Binary Feedback

Hung Quoc Ngo, Matthew D. Luciw, Ngo Anh Vien, Jürgen Schmidhuber

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 2488-2493.

Abstract

We introduce a novel algorithm called Upper Confidence Weighted Learning (UCWL) for online multiclass learning from binary feedback. UCWL combines the Upper Confidence Bound (UCB) framework with the Soft Confidence Weighted (SCW) online learning scheme. UCWL achieves state of the art performance (especially on noisy and non-separable data) with low computational costs. Estimated confidence intervals are used for informed exploration, which enables faster learning than the uninformed exploration case or the case where exploration is not used. The targeted application setting is human-robot interaction (HRI), in which a robot is learning to classify its observations while a human teaches it by providing only binary feedback (e.g., right/wrong). Results in an HRI experiment, and with two benchmark datasets, show UCWL outperforms other algorithms in the online binary feedback setting, and surprisingly even sometimes beats state-of-the-art algorithms that get full feedback, while UCWL gets only binary feedback on the same data.

Hung Quoc Ngo, Matthew D. Luciw, Ngo Anh Vien, and Jürgen Schmidhuber. 2013. Upper Confidence Weighted Learning for Efficient Exploration in Multiclass Prediction with Binary Feedback. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 2488–2493. https://ijcai.org/proceedings/2013/366

@inproceedings{ijcai2013p366,
  title     = {Upper Confidence Weighted Learning for Efficient Exploration in Multiclass Prediction with Binary Feedback},
  author    = {Ngo, Hung Quoc and Luciw, Matthew D. and Vien, Ngo Anh and Schmidhuber, Jürgen},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {2488--2493},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/366},
}

TY  - CPAPER
TI  - Upper Confidence Weighted Learning for Efficient Exploration in Multiclass Prediction with Binary Feedback
AU  - Ngo, Hung Quoc
AU  - Luciw, Matthew D.
AU  - Vien, Ngo Anh
AU  - Schmidhuber, Jürgen
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 2488
EP  - 2493
UR  - https://ijcai.org/proceedings/2013/366
ER  -