Teaching Dimension and the Complexity of Active Learning

Steve HannekeCOLT 2007 · OpenReview

Abstract

We study the label complexity of pool-based active learning in the PAC model with noise. Taking inspiration from extant literature on Exact learning with membership queries, we derive upper and lower bounds on the label complexity in terms of generalizations of extended teaching dimension. Among the contributions of this work is the first nontrivial general upper bound on label complexity in the presence of persistent classification noise.
BibTeX
@inproceedings{hanneke2007teaching,
  author = {Steve Hanneke},
  title = {{Teaching Dimension and the Complexity of Active Learning}},
  booktitle = {Conference on Learning Theory},
  year = {2007},
  url = {https://openreview.net/forum?id=cdBA7qdpCfr},
}

Loading related content...

Figure