  We design an active learning algorithm for cost-sensitive multiclass
classification: problems where different errors have different costs. Our
algorithm, COAL, makes predictions by regressing to each label's cost and
predicting the smallest. On a new example, it uses a set of regressors that
perform well on past data to estimate possible costs for each label. It queries
only the labels that could be the best, ignoring the sure losers. We prove COAL
can be efficiently implemented for any regression family that admits squared
loss optimization; it also enjoys strong guarantees with respect to predictive
performance and labeling effort. We empirically compare COAL to passive
learning and several active learning baselines, showing significant
improvements in labeling effort and test cost on real-world datasets.
