Timezone: »

 
Poster
Boosting with Abstention
Corinna Cortes · Giulia DeSalvo · Mehryar Mohri

Mon Dec 05 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #77 #None
in Monday Posters »

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.

Keywords: Ensemble Methods and Boosting · (Other) Classification

Author Information

Corinna Cortes (Google Research)
Giulia DeSalvo (New York University)
Mehryar Mohri (Courant Inst. of Math. Sciences & Google Research)

More from the Same Authors