Advanced Methods for Pattern Recognition with the Reject Option

When the cost of misclassifications is very high it is useful to allow a pattern classification system to withheld the automatic classification of an input pattern, if it is considered unreliable. This is know as the reject option. Rejected patterns must be manually handled or fed to a more accurate and more costly classifier. It is thus necessary to find a trade-off between rejection and misclassification rates. In the framework of the minimum risk theory, the optimal classification rule with the reject option was defined by C.K. Chow in 1957. However the optimality of Chow's rule relies on the exact knowledge of the class posterior probabilities, which in practical applications are usually unknown. Moreover, while some classifiers (like neural networks) provide estimates of the posteriors, other classifiers (like support vector machines, SVM) do not: in such cases the reject option has to be implemented using different estimates of classification reliability. So far few works in the literature addressed the problem of designing effective classification rules with the reject option in real applications, and none of them attempted to give a theoretical support to such rules, taking into account the non-optimality of Chow's rule. A case of particular interest is the SVM classifier: despite its strong theoretical roots in statistical learning theory and its effectiveness in several real applications, no work addressed so far the issue of implementing a reject option in SVMs in a principled way.

 

In this thesis we address the two topics mentioned above. As a first contribution, we analyse the effects of estimation errors on the performance of Chow's rule and propose a new rejection rule based on using a different rejection threshold for each class, formally proving that it can allow to achieve a better error-reject trade-off than Chow's rule in presence of estimation errors on the a posteriori probabilities. We also analyse the improvement of the error-reject trade-off which can be attained by ensebles of linearly combined classifiers, by extending an analytical model derived in works by Tumer and Ghosh. As the second contribution we propose a method for implementing a reject option in SVM classifiers. Our method is based on a modification of the objective function of the SVM learning algorithm which allows to include the reject option in the resulting decision function, with the aim of preserving the capacity control capability of the original SVM learning algorithm.