The Relationship Between Agnostic Selective Classification and Active Learning

Roei Gelbhart, M.Sc. Thesis Seminar

Sunday, 19.3.2017, 15:00

Taub 601

A selective classifier (f,g) consists of a classification function f
and a binary selection function g, which determines if the classifier
abstains from prediction, or uses f to predict.The classifier is called
pointwise-competitive if it classifies each point identically to the best
classifier in hindsight (from the same class), whenever it does not
abstain. The quality of such a classifier is quantified by its rejection
mass, defined to be the probability mass of the of the points it rejects.
A ``fast'' rejection rate is achieved if the rejection mass is bounded
from above by O(1/m) where m is the number of labeled examples
used to train the classifier (and O() hides logarithmic
factors).Pointwise-competitive selective (PCS) classifiers are intimately
related to disagreement-based active learning and it is known that in the
realizable case, a fast rejection rate of a known PCS algorithm (called
Consistent Selective Strategy) is equivalent to an exponential speedup of
the well known CAL active algorithm.
We focus on the agnostic setting, for which there is a known algorithm
called LESS that learns a PCS classifier and achieves a fast rejection
rate (depending on Hanneke