Semidefinite Programming in Classification Learning

Knowledge about local invariances with respect to given pattern transformations can greatly improve the accuracy of classification. Previous approaches are either based on regularisation or on the generation of virtual (transformed) examples. We developed a new framework for learning linear classifiers under known transformations based on semi-definite programming. We present a new learning algorithm - the Semi-Definite Programming Machine (SDPM) - which is able to find a maximum margin hyper-plane when the training examples are polynomial trajectories instead of single points. The solution is found to be sparse in dual variables and allows to identify those points on the trajectory with minimal real-valued output as virtual support vectors. Extensions to segments of trajectories, to more than one trans- formation parameter, and to learning with kernels are conceivable.

References

• Thore Graepel and Ralf Herbrich. Invariant Pattern Recognition by Semidefinite Programming Machines. Advances in Neural Information Processing Systems 16, 33--40, 2004. (Gzipped Postscript).
• Thore Graepel, Ralf Herbrich, Andriy Kharechko and John Shawe-Taylor. Semidefinite Programming by Perceptron Learning. Advances in Neural Information Processing Systems 16, 457--464, 2004. (Gzipped Postscript)