NeuroCOLT workshop
on
Generalisation Bounds Less than 0.5
Windsor, 29 April - 2 May 2002
Cumberland Lodge

"The Robust Minimax Probability Machine"

Gert Lanckriet

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. Over all possible class-conditional densities with given mean and covariance matrix, we wish to minimize the worst-case 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. A crucial property of this Minimax Probability Machine is that a worst-case bound on the probability of misclassification of future data is obtained explicitly. Nonlinear decision boundaries with an explicit worst-case bound can be obtained as well, by exploiting Mercer kernels in this setting. In a next step, we drop the assumption of known mean and covariance matrix for each class and estimate their values from the available data using plug-in estimates. We then address the issue of robustness with respect to estimation errors: for an "unknown-but-bounded" uncertainty on the mean and covariance estimates, we can train a Minimax Probability Machine which is robust against the worst-case estimation errors. This results in the formulation of a slightly different second-order cone program. The consequences for the resulting classifier and the explicitly obtained worst-case bound on the probability of misclassification of future data are studied. This leads to the Robust version of the Minimax Probability Machine.