Set-Valued Support Vector Machine with Bounded Error Rates

This article concerns cautious classification models that are allowed to predict a set of class labels or reject to make a prediction when the uncertainty in the prediction is high. This set-valued classification approach is equivalent to the task of acceptance region learning, which aims to identify subsets of the input space, each of which guarantees to cover observations in a class with at least a predetermined probability. We propose to directly learn the acceptance regions through risk minimization, by making use of a truncated hinge loss and a constrained optimization framework. Collectively our theoretical analyses show that these acceptance regions, with high probability, satisfy simultaneously two properties: (1) they guarantee to cover each class with a non-coverage rate bounded from above; (2) they give the least ambiguous predictions among all the acceptance regions satisfying (1). An efficient algorithm is developed and numerical studies are conducted using both simulated and real data.