SEPARATION BY ELLIPSOIDS USING SEMIDEFINITE PROGRAMMING

In this talk, we demonstrate how to apply semidefinite programming
to classification using ellipsoids.

Semidefinite programming is a convex generalization of linear
programming, where vectors become symmetric matrices and the
nonnegativity conditions are replaced by positive semidefiniteness
requirements. These programs can be solved very efficiently using a
interior point polynomial time algorithm.

We first consider the problem of separating two sets of
n-dimensional vectors with an ellipsoid, i.e. finding an ellipsoid
E such that every point from the first set belongs to E while none
from the other set does. We model this problem as a semidefinite
program, using different formulations. We also optimize various
criteria (shape of the ellipsoid, separation strength, etc.)

We then use this approach in the context of classification, with a
cross-validation technique. We first compute an ellipsoid for each
class of points from the learning set, then we test the accuracy of
the resulting classifier on points from the validation set. This
produced very encouraging results, since we were able to classify
correctly Fisher's famous iris data set.