Training SVM with indefinite kernels

ABSTRACT

Similarity matrices generated from many applications may not be positive semidefinite, and hence can't fit into the kernel machine framework. In this paper, we study the problem of training support vector machines with an indefinite kernel. We consider a regularized SVM formulation, in which the indefinite kernel matrix is treated as a noisy observation of some unknown positive semidefinite one (proxy kernel) and the support vectors and the proxy kernel can be computed simultaneously. We propose a semi-infinite quadratically constrained linear program formulation for the optimization, which can be solved iteratively to find a global optimum solution. We further propose to employ an additional pruning strategy, which significantly improves the efficiency of the algorithm, while retaining the convergence property of the algorithm. In addition, we show the close relationship between the proposed formulation and multiple kernel learning. Experiments on a collection of benchmark data sets demonstrate the efficiency and effectiveness of the proposed algorithm.

REFERENCES

• 1: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 2: Nello Cristianini , John Shawe-Taylor, An introduction to support Vector Machines: and other kernel-based learning methods, Cambridge University Press, New York, NY, 1999
• 3: Golub, G. H., & Van Loan, C. F. (1996). Matrix computations. Johns Hopkins University Press. 3 edition.
• 4: Thore Graepel , Ralf Herbrich , Peter Bollmann-Sdorra , Klaus Obermayer, Classification on pairwise proximity data, Proceedings of the 1998 conference on Advances in neural information processing systems II, p.438-444, July 1999
• 5: Bernard Haasdonk, Feature Space Interpretation of SVMs with Indefinite Kernels, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.4, p.482-492, April 2005 [doi>10.1109/TPAMI.2005.78]
• 6: R. Hettich , K. O. Kortanek, Semi-infinite programming: theory, methods, and applications, SIAM Review, v.35 n.3, p.380-429, Sept. 1993 [doi>10.1137/1035089]
• 7: R. Hettich , K. O. Kortanek, Semi-infinite programming: theory, methods, and applications, SIAM Review, v.35 n.3, p.380-429, Sept. 1993 [doi>10.1137/1035089]
• 8: Hiriart-Urruty, J.-B., & Lemarechal, C. (1993). Convex analysis and minimization algorithms II. Springer.
• 9: J. J. Hull, A Database for Handwritten Text Recognition Research, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.16 n.5, p.550-554, May 1994 [doi>10.1109/34.291440]
• 10: Risi Imre Kondor , John D. Lafferty, Diffusion Kernels on Graphs and Other Discrete Input Spaces, Proceedings of the Nineteenth International Conference on Machine Learning, p.315-322, July 08-12, 2002
• 11: Gert R. G. Lanckriet , Nello Cristianini , Peter Bartlett , Laurent El Ghaoui , Michael I. Jordan, Learning the Kernel Matrix with Semidefinite Programming, The Journal of Machine Learning Research, 5, p.27-72, 12/1/2004
• 12: Lin, H.-T., & Lin, C.-J. (2003). A study on sigmoid kernels for svm and the training of non-psd kernels by smo-type methods. Technical Report, National Taiwan University.
• 13: Luss, R., & d'Aspremont, A. (2007). Support vector machine classification with indefinite kernels. NIPS.
• 14: Newman, D., Hettich, S., Blake, C., & Merz, C. (1998). UCI repository of machine learning databases.
• 15: Nocedal, J., & Wright, S. J. (1999). Numerical optimization springer series in operations research. Springer.
• 16: Cheng Soon Ong , Xavier Mary , Stéphane Canu , Alexander J. Smola, Learning with non-positive kernels, Proceedings of the twenty-first international conference on Machine learning, p.81, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015443]
• 17: Elzbieta Pekalska , Pavel Paclik , Robert P. W. Duin, A generalized kernel approach to dissimilarity-based classification, The Journal of Machine Learning Research, 2, 3/1/2002
• 18: Arun Qamra , Yan Meng , Edward Y. Chang, Enhanced Perceptual Distance Functions and Indexing for Image Replica Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.3, p.379-391, March 2005 [doi>10.1109/TPAMI.2005.54]
• 19: Alain Rakotomamonjy , Francis Bach , Stéphane Canu , Yves Grandvalet, More efficiency in multiple kernel learning, Proceedings of the 24th international conference on Machine learning, p.775-782, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273594]
• 20: Volker Roth , Julian Laub , Motoaki Kawanabe , Joachim M. Buhmann, Optimal Cluster Preserving Embedding of Nonmetric Proximity Data, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.12, p.1540-1551, December 2003 [doi>10.1109/TPAMI.2003.1251147]
• 21: Volker Roth , Julian Laub , Motoaki Kawanabe , Joachim M. Buhmann, Optimal Cluster Preserving Embedding of Nonmetric Proximity Data, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.12, p.1540-1551, December 2003 [doi>10.1109/TPAMI.2003.1251147]
• 22: Bernhard Scholkopf , Alexander J. Smola, Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond, MIT Press, Cambridge, MA, 2001
• 23: Shimodaira, H., Noma, K.-I., Nakai, M., & Sagayama, S. (2001). Dynamic time-alignment kernel in support vector machine. NIPS (pp. 921--928).
• 24: Smola, A. J., Óvári, Z. L., & Williamson, R. C. (2000). Regularization with dot-product kernels. NIPS (pp. 308--314).
• 25: Sören Sonnenburg , Gunnar Rätsch , Christin Schäfer , Bernhard Schölkopf, Large Scale Multiple Kernel Learning, The Journal of Machine Learning Research, 7, p.1531-1565, 12/1/2006
• 26: Choon Hui Teo , Alex Smola , S. V.N. Vishwanathan , Quoc Viet Le, A scalable modular convex solver for regularized risk minimization, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281270]
• 27: Simon Tong , Edward Chang, Support vector machine active learning for image retrieval, Proceedings of the ninth ACM international conference on Multimedia, September 30-October 05, 2001, Ottawa, Canada [doi>10.1145/500141.500159]
• 28: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 29: Wu, G., Zhang, Z., & Chang, E. Y. (2005). An analysis of transformation on non-positive semidefinite similarity matrix for kernel machines. Technical Report, UCSB.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming; Quadratic programming methods; Constrained optimization

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Similarity measures
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design, Measurement, Performance