Optimal kernel selection in Kernel Fisher discriminant analysis

ABSTRACT

In Kernel Fisher discriminant analysis (KFDA), we carry out Fisher linear discriminant analysis in a high dimensional feature space defined implicitly by a kernel. The performance of KFDA depends on the choice of the kernel; in this paper, we consider the problem of finding the optimal kernel, over a given convex set of kernels. We show that this optimal kernel selection problem can be reformulated as a tractable convex optimization problem which interior-point methods can solve globally and efficiently. The kernel selection method is demonstrated with some UCI machine learning benchmark examples.

REFERENCES

• 1: Francis R. Bach , Gert R. G. Lanckriet , Michael I. Jordan, Multiple kernel learning, conic duality, and the SMO algorithm, Proceedings of the twenty-first international conference on Machine learning, p.6, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015424]
• 2: Kristin P. Bennett , Michinari Momma , Mark J. Embrechts, MARK: a boosting algorithm for heterogeneous kernel models, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775051]
• 3: Jinbo Bi , Tong Zhang , Kristin P. Bennett, Column-generation boosting methods for mixture of kernels, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014113]
• 4: Bousquet, O., & Herrmann, D. (2003). On the complexity of learning the kernel matrix. In Advances in Neural Information Processing Systems, 15, MIT Press.
• 5: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 6: Crammer, K., Keshet, J., & Singer, Y. (2003). Kernel design using boosting. In Advances in Neural Information Processing Systems, 15, MIT Press.
• 7: Cristianini, N., Elisseeff, A., Shawe-Taylor, J., & Kandla, J. (2001). On kernel target alignment. In Advances in Neural Information Processing Systems, 13, pp. 367--373, MIT Press.
• 8: Glenn Fung , Murat Dundar , Jinbo Bi , Bharat Rao, A fast iterative algorithm for fisher discriminant using heterogeneous kernels, Proceedings of the twenty-first international conference on Machine learning, p.40, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015409]
• 9: Hastie, T., Tibshirani, R., & Friedman, J. (2001). The elements of statistical learning: Data mining, inference, and prediction. Springer-Verlag.
• 10: Gert R. G. Lanckriet , Tijl De Bie , Nello Cristianini , Michael I. Jordan , William Stafford Noble, A statistical framework for genomic data fusion, Bioinformatics, v.20 n.16, p.2626-2635, November 2004 [doi>10.1093/bioinformatics/bth294]
• 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: Charles A. Micchelli , Massimiliano Pontil, Learning the Kernel Function via Regularization, The Journal of Machine Learning Research, 6, p.1099-1125, 9/1/2005
• 13: Mika, S., Rätsch, G., & Müüller, K. (2001). A mathematical programming approach to the kernel Fisher algorithm. In Advances in Neural Information Processing Systems, 13, pp. 591--597, MIT Press.
• 14: Sebastian Mika , Gunnar Rätsch , Jason Weston , Bernhard Schölkopf , Alex Smola , Klaus-Robert Müller, Constructing Descriptive and Discriminative Nonlinear Features: Rayleigh Coefficients in Kernel Feature Spaces, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.5, p.623-633, May 2003 [doi>10.1109/TPAMI.2003.1195996]
• 15: Nesterov, Y., & Nemirovsky, A. (1994). Interior-point polynomial methods in convex programming, vol. 13 of Studies in Applied Mathematics. Philadelphia, PA: SIAM.
• 16: Newman, D., Hettich, S., Blake, C., & Merz, C. (1998). UCI repository of machine learning databases. Available from www.ics.uci.edu/~mlearn/MLRepository.html.
• 17: Cheng Soon Ong , Alexander J. Smola , Robert C. Williamson, Learning the Kernel with Hyperkernels, The Journal of Machine Learning Research, 6, p.1043-1071, 9/1/2005
• 18: Pepe, M. (2000). Receiver operating characteristic methodology. Journal of the American Statistical Association, 95, 308--311.
• 19: John Shawe-Taylor , Nello Cristianini, Kernel Methods for Pattern Analysis, Cambridge University Press, New York, NY, 2004
• 20: Sturm, J. (2001). Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones. Available from sedumi.mcmaster.ca/.
• 21: Toh, K., Tütüncü, R., & Todd, M. (2002). SDPT3 version 3.02. a Matlab software for semidefinite-quadratic-linear programming. Available from www.math.nus.edu.sg/~mattohkc/sdpt3.html.
• 22: Lieven Vandenberghe , Stephen Boyd, Semidefinite programming, SIAM Review, v.38 n.1, p.49-95, Mar. 1996 [doi>10.1137/1038003]
• 23: Xiong, H., Swamy, M., & Ahmad, M. (2005). Optimizing the kernel in the empirical feature space. IEEE Transactions on Neural Networks, 16, 460--474.
• 24: Jian Yang , Alejandro F. Frangi , Jing-yu Yang , David Zhang , Zhong Jin, KPCA Plus LDA: A Complete Kernel Fisher Discriminant Framework for Feature Extraction and Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.2, p.230-244, February 2005 [doi>10.1109/TPAMI.2005.33]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical
      I.5.3 Clustering

General Terms:
Algorithms