Agnostic Active Learning Without Constraints

We present and analyze an agnostic active learning algorith m that works without keeping a version space. This is unlike all previous approac hes where a restricted set of candidate hypotheses is maintained throughout learn ing, and only hypotheses from this set are ever returned. By avoiding this version space approach, our algorithm sheds the computational burden and brittleness a ssociated with maintaining version spaces, yet still allows for substantial im provements over supervised learning for classification.