A General Agnostic Active Learning Algorithm.

We present a simple, agnostic active learning algorithm that works\nfor any hypothesis class of bounded VC dimension, and any data distribution.\nOur algorithm extends a scheme of Cohn, Atlas, and Ladner to the agnostic\nsetting, by (1) reformulating it using a reduction to supervised learning and\n(2) showing how to apply generalization bounds even for the non-i.i.d. samples\nthat result from selective sampling. We provide a general characterization of\nthe label complexity of our algorithm. This quantity is never more than the\nusual PAC sample complexity of supervised learning, and is exponentially\nsmaller for some hypothesis classes and distributions. We also demonstrate\nimprovements experimentally.Pre-2018 CSE ID: CS2007-0898