Boosting with abstention
Abstract
We present a new boosting algorithm for the key scenario of binary classification
with abstention where the algorithm can abstain from predicting the label of a point,
at the price of a fixed cost. At each round, our algorithm selects a pair of functions,
a base predictor and a base abstention function. We define convex upper bounds
for the natural loss function associated to this problem, which we prove to be
calibrated with respect to the Bayes solution. Our algorithm benefits from general
margin-based learning guarantees which we derive for ensembles of pairs of base
predictor and abstention functions, in terms of the Rademacher complexities of the
corresponding function classes. We give convergence guarantees for our algorithm
along with a linear-time weak-learning algorithm for abstention stumps. We also
report the results of several experiments suggesting that our algorithm provides a
significant improvement in practice over two confidence-based algorithms.
with abstention where the algorithm can abstain from predicting the label of a point,
at the price of a fixed cost. At each round, our algorithm selects a pair of functions,
a base predictor and a base abstention function. We define convex upper bounds
for the natural loss function associated to this problem, which we prove to be
calibrated with respect to the Bayes solution. Our algorithm benefits from general
margin-based learning guarantees which we derive for ensembles of pairs of base
predictor and abstention functions, in terms of the Rademacher complexities of the
corresponding function classes. We give convergence guarantees for our algorithm
along with a linear-time weak-learning algorithm for abstention stumps. We also
report the results of several experiments suggesting that our algorithm provides a
significant improvement in practice over two confidence-based algorithms.