PUB - Publikationen an der Universität Bielefeld

We analyse optimum reject strategies for prototype-based classifiers andreal-valued rejection measures, using the distance of a data point to theclosest prototype or probabilistic counterparts. We compare reject schemes withglobal thresholds, and local thresholds for the Voronoi cells of theclassifier. For the latter, we develop a polynomial-time algorithm to computeoptimum thresholds based on a dynamic programming scheme, and we propose anintuitive linear time, memory efficient approximation thereof with competitiveaccuracy. Evaluating the performance in various benchmarks, we conclude thatlocal reject options are beneficial in particular for simple prototype-basedclassifiers, while the improvement is less pronounced for advanced models. Forthe latter, an accuracy-reject curve which is comparable to support vectormachine classifiers with state of the art reject options can be reached.