On Reject and Refine Options in Multicategory Classification

ABSTRACT

In many real applications of statistical learning, a decision made from misclassification can be too costly to afford; in this case, a reject option, which defers the decision until further investigation is conducted, is often preferred. In recent years, there has been much development for binary classification with a reject option. Yet, little progress has been made for the multicategory case. In this article, we propose margin-based multicategory classification methods with a reject option. In addition, and more importantly, we introduce a new and unique refine option for the multicategory problem, where the class of an observation is predicted to be from a set of class labels, whose cardinality is not necessarily one. The main advantage of both options lies in their capacity of identifying error-prone observations. Moreover, the refine option can provide more constructive information for classification by effectively ruling out implausible classes. Efficient implementations have been developed for the proposed methods. On the theoretical side, we offer a novel statistical learning theory and show a fast convergence rate of the excess ℓ-risk of our methods with emphasis on diverging dimensionality and number of classes. The results can be further improved under a low noise assumption and be generalized to the excess 0-d-1 risk. Finite-sample upper bounds for the reject and reject/refine rates are also provided. A set of comprehensive simulation and real data studies has shown the usefulness of the new learning tools compared to regular multicategory classifiers. Detailed proofs of theorems and extended numerical results are included in the supplemental materials available online.

KEYWORDS:

• Coordinate descent
• Discriminant analysis
• Diverging number of classes
• High-dimensional data
• Multi-class classification
• Statistical learning theory

Acknowledgments

The authors gratefully acknowledge Professor Mu Zhu for his helpful suggestions.

Additional information

Funding

Qiao’s research is partially supported by a collaboration grant from Simons Foundation (award number 246649).