Graph-based active learning: A new look at expected error minimization

Kwang Sung Jun, Robert Nowak

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

In graph-based active learning, algorithms based on expected error minimization (EEM) have been popular and yield good empirical performance. The exact computation of EEM optimally balances exploration and exploitation. In practice, however, EEM-based algorithms employ various approximations due to the computational hardness of exact EEM. This can result in a lack of either exploration or exploitation, which can negatively impact the effectiveness of active learning. We propose a new algorithm TSA (Two-Step Approximation) that balances between exploration and exploitation efficiently while enjoying the same computational complexity as existing approximations. Finally, we empirically show the value of balancing between exploration and exploitation in both toy and real-world datasets where our method outperforms several state-of-the-art methods.

Original languageEnglish (US)
Title of host publication2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1325-1329
Number of pages5
ISBN (Electronic)9781509045457
DOIs
StatePublished - Apr 19 2017
Externally publishedYes
Event2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Washington, United States
Duration: Dec 7 2016Dec 9 2016

Publication series

Name2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016 - Proceedings

Conference

Conference2016 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2016
Country/TerritoryUnited States
CityWashington
Period12/7/1612/9/16

Keywords

  • Active learning
  • Graph-based learning
  • Machine learning
  • Probabilistic model
  • Semi-supervised learning

ASJC Scopus subject areas

  • Signal Processing
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Graph-based active learning: A new look at expected error minimization'. Together they form a unique fingerprint.

Cite this