Title: 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.