A Robust Minimax Approach to Classification
Gert R.G. Lanckriet, Laurent El Ghaoui, Chiranjib Bhattacharyya, Michael I. Jordan;
3(Dec):555-582, 2002.
Abstract
When constructing a classifier, the probability of correct
classification of future data points should be maximized. We
consider a binary classification problem where the mean and
covariance matrix of each class are assumed to be known. No
further assumptions are made with respect to the class-conditional
distributions. Misclassification probabilities are then controlled
in a worst-case setting: that is, under all possible choices of
class-conditional densities with given mean and covariance matrix,
we
minimize the worst-case (
maximum) probability of
misclassification of future data points. For a linear decision
boundary, this desideratum is translated in a very direct way into
a (convex) second order cone optimization problem, with complexity
similar to a support vector machine problem. The minimax problem
can be interpreted geometrically as minimizing the maximum of the
Mahalanobis distances to the two classes. We address the issue of
robustness with respect to estimation errors (in the means and
covariances of the classes) via a simple modification of the input
data. We also show how to exploit Mercer kernels in this setting
to obtain nonlinear decision boundaries, yielding a classifier
which proves to be competitive with current methods, including
support vector machines. An important feature of this method is
that a worst-case bound on the probability of misclassification of
future data is always obtained explicitly.
[abs]
[pdf]
[ps.gz]
[ps]
