Optimal local rejection for classifiers

We analyse optimal rejection strategies for classifiers with input space partitioning, e.g. prototype-based classifiers, support vector machines or decision trees using certainty measures such as the distance to the closest decision border. We provide new theoretical results: we link this problem to the multiple choice knapsack problem and devise an exact polynomial-time dynamic programming (DP) scheme to determine optimal local thresholds on given data. Further, we propose a linear time, memory efficient approximation thereof. We show in experiments that the approximation has a competitive performance compared to the full DP. Further, we evaluate the performance of classification with rejection in various benchmarks: we conclude that local rejection is beneficial in particular for simple classifiers, while the improvement is less pronounced for advanced classifiers. An evaluation on speech prosody and biomedical data highlights the benefit of local thresholds.