Classification reliability

The reliability of automatic pattern classification systems is a critical issue in many practical applications, like medical diagnosis and optical character recognition. In some cases it could be mandatory to avoid certain kinds of misclassification due to their very high cost or undesirable consequences (like false negatives in medical diagnosis), or to keep the misclassification rate below a given acceptable threshold (like in optical character recognition). In such cases it could be preferable that the system withholds the classification of an input sample, if the classification reliability is deemed low. The input sample can then be handled by a human operator, or by a different classification system, more accurate and usually more costly. The possibility for a classification system to withhold the assignment of an input sample to one of the predefined classes is named reject option. A reject option can be implemented in several ways, depending on the application, on the kind of classification system and on its goals and requirements (see the bibliography page).

In our works we considered the most common kind of reject option, when the goal is simply to attain the best trade-off between the error and rejection rates, for given misclassification and a rejection costs. The optimal classification rule for this kind of reject option is Chow's rule: it consists in rejecting an input pattern, if the maximum of its a posteriori probabilities is lower than a threshold, which depends on the misclassification and rejection costs. The optimality of Chow's tule relies on the exact knowledge of the class posterior probabilities, as for the standard Bayes rule for classification without the reject option. We proposed a different rule based on a different rejection threshold associated to each class (Class-related Rejection Threshold, CRT) to improve the performance over Chow's rule when the true posteriors are unknown, as in all real applications. We point out that the use of a different rejection threshold for each class had already been proposed by other authors for different purposes (Yau, H.C., Manry, M.T., "Automatic Determination of Reject Threshold in Classifiers Employing Discriminant Functions," IEEE Trans. on Signal Processing 40, 711-713, 1992). We also provided an analysis of the improvement of the error-reject trade-off attainable by linearly combining an ensemble of classifiers, through the extension of the analytical model for linear combiners developed in works by K. Tumer and J. Ghosh (see the section related to multiple classifier systems). Finally, we proposed a method to implement the reject option tailored to Support Vector Machine classifiers.

People working on this topic:

• Giorgio Fumera
• Fabio Roli

Publications on Classification reliability