jmlr-announce: A Robust Minimax Approach to Classification

[David 'Pablo' Cohn]

The Journal of Machine Learning Research is pleased to announce the
availability of yet another new paper online at http://www.jmlr.org.

----------------------------------------
A Robust Minimax Approach to Classification

Gert R.G. Lanckriet, Laurent El Ghaoui,
Chiranjib Bhattacharyya and Michael I. Jordan
JMLR 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.

----------------------------------------

This paper and all previous papers are available electronically at
http://www.jmlr.org/ in PostScript and PDF formats. Many are also available
in HTML. The papers of Volume 1 and 2 are also available in hardcopy from
the MIT Press; please see http://mitpress.mit.edu/JMLR for details.

 -David Cohn, <David.Cohn at acm.org>
  Managing Editor, Journal of Machine Learning Research