Abstract: In this paper we are interested in classification problems
with a performance constraint on error probability. In such
problems if the constraint cannot be satisfied, then a rejection option
is introduced. For binary labelled classification, a number of SVM
based methods with rejection option have been proposed over the
past few years. All of these methods use two thresholds on the SVM
output. However, in previous works, we have shown on synthetic data
that using thresholds on the output of the optimal SVM may lead to
poor results for classification tasks with performance constraint. In
this paper a new method for supervised classification with rejection
option is proposed. It consists in two different classifiers jointly
optimized to minimize the rejection probability subject to a given
constraint on error rate. This method uses a new kernel based linear
learning machine that we have recently presented. This learning
machine is characterized by its simplicity and high training speed
which makes the simultaneous optimization of the two classifiers
computationally reasonable. The proposed classification method with
rejection option is compared to a SVM based rejection method
proposed in recent literature. Experiments show the superiority of
the proposed method.