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: (a) they guarantee to cover each class with a noncoverage rate bounded from above; (b) they give the least ambiguous predictions among all the acceptance regions satisfying (a). An efficient algorithm is developed and numerical studies are conducted using both simulated and real data. Supplementary materials for this article are available online.

本文探讨了一种谨慎的分类模型，该模型在预测的不确定性较高时，允许预测一组类别标签或拒绝做出预测。这一集合值分类方法与接受域学习任务等价，旨在识别输入空间中的子集，每个子集均能以至少预定的概率保证覆盖某一类别的观察值。我们提出通过风险最小化直接学习接受域，利用截断的铰链损失和约束优化框架。我们的理论分析共同表明，这些接受域以高概率同时满足以下两个性质：(a) 确保覆盖每一类别，且非覆盖率受上限约束；(b) 在满足性质(a)的所有接受域中，提供最不模糊的预测。一种高效的算法被开发出来，并使用模拟数据和真实数据进行了数值研究。本文的补充材料可在网上查阅。