PATTERN SEPARATION VIA ELLIPSOIDS AND CONIC PROGRAMMING

Machine learning is a scientific discipline whose purpose is to design
computer procedures that are able to perform classification tasks. For
example, given a certain number of medical characteristics about a patient
(e.g. age, weight, blood pressure, etc.), we would like to infer automatically
whether he or she is healthy or not.

A special case of machine learning problem is the separation problem, which
asks to find a way to classify patterns that are known to belong to different
well-defined classes. This is equivalent to finding a procedure that is able
to recognize to which class each pattern belongs. In this talk, we demonstrate
how to apply conic optimization to classification using ellipsoids.

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.