nips nips2003 nips2003-96 nips2003-96-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Thore Graepel, Ralf Herbrich
Abstract: 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 develop a new framework for learning linear classifiers under known transformations based on semidefinite programming. We present a new learning algorithm— the Semidefinite Programming Machine (SDPM)—which is able to find a maximum margin hyperplane 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 transformation parameter, and to learning with kernels are discussed. In experiments we use a Taylor expansion to locally approximate rotational invariance in pixel images from USPS and find improvements over known methods. 1
[1] O. Chapelle and B. Sch¨lkopf. Incorporating invariances in non-linear support vector o machines. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems 14, pages 609–616, Cambridge, MA, 2002. MIT Press.
[2] C. Cortes and V. Vapnik. Support vector networks. Machine Learning, 20:273–297, 1995.
[3] T. Graepel, R. Herbrich, A. Kharechko, and J. Shawe-Taylor. Semidefinite programming by perceptron learning. In S. Thrun, L. Saul, and B. Sch¨lkopf, editors, Advances in o Neural Information Processing Systems 16. MIT Press, 2004.
[4] A. Nemirovski. Five lectures on modern convex optimization, 2002. Lecture notes of the C.O.R.E. Summer School on Modern Convex Optimization.
[5] Y. Nesterov. Squared functional systems and optimization problems. In H. Frenk, K. Roos, T. Terlaky, and S. Zhang, editors, High Performance Optimization, pages 405– 440. Kluwer Academic Press, 2000.
[6] F. Rosenblatt. The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65(6):386–408, 1958.
[7] B. Sch¨lkopf. Support Vector Learning. R. Oldenbourg Verlag, M¨nchen, 1997. Doko u torarbeit, TU Berlin. Download: http://www.kernel-machines.org.
[8] P. Simard, Y. LeCun, J. Denker, and B. Victorri. Transformation invariance in pattern recognition, tangent distance and tangent propagation. In G. Orr and M. K., editors, Neural Networks: Tricks of the trade. Springer, 1998.
[9] L. Vandenberghe and S. Boyd. Semidefinite programming. SIAM Review, 38(1):49–95, 1996.