A fast iterative algorithm for fisher discriminant using heterogeneous kernels

ABSTRACT

We propose a fast iterative classification algorithm for Kernel Fisher Discriminant (KFD) using heterogeneous kernel models. In contrast with the standard KFD that requires the user to predefine a kernel function, we incorporate the task of choosing an appropriate kernel into the optimization problem to be solved. The choice of kernel is defined as a linear combination of kernels belonging to a potentially large family of different positive semidefinite kernels. The complexity of our algorithm does not increase significantly with respect to the number of kernels on the kernel family. Experiments on several benchmark datasets demonstrate that generalization performance of the proposed algorithm is not significantly different from that achieved by the standard KFD in which the kernel parameters have been tuned using cross validation. We also present results on a real-life colon cancer dataset that demonstrate the efficiency of the proposed method.

REFERENCES

• 1: (2004). CPLEX optimizer. ILOG CPLEX Division, 889 Alder Avenue, Incline Village, Nevada. http://www.cplex.com/.
• 2: Bach, F., Lanckriet, J., & Jordan, M. (2004). Fast kernel learning using sequential minimal optimizationTechnical Report CSD-04-1307). Division of Computer Science, University of California, Berkeley.
• 3: 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]
• 4: James C. Bezdek , Richard J. Hathaway, Some Notes on Alternating Optimization, Proceedings of the 2002 AFSS International Conference on Fuzzy Systems. Calcutta: Advances in Soft Computing, p.288-300, February 03-06, 2002
• 5: James C. Bezdek , Richard J. Hathaway, Convergence of alternating optimization, Neural, Parallel & Scientific Computations, v.11 n.4, p.351-368, December 2003
• 6: Vladimir S. Cherkassky , Filip Mulier, Learning from Data: Concepts, Theory, and Methods, John Wiley & Sons, Inc., New York, NY, 1998
• 7: Nello Cristianini , John Shawe-Taylor, An introduction to support Vector Machines: and other kernel-based learning methods, Cambridge University Press, New York, NY, 1999
• 8: Evgeniou, T., Pontil, M., & Poggio, T. (2000a). Regularization networks and support vector machines. Advances in Computational Mathematics, 13, 1--50.
• 9: Evgeniou, T., Pontil, M., & Poggio, T. (2000b). Regularization networks and support vector machines. Advances in Large Margin Classifiers (pp. 171--203). Cambridge, MA: MIT Press.
• 10: Keinosuke Fukunaga, Introduction to statistical pattern recognition (2nd ed.), Academic Press Professional, Inc., San Diego, CA, 1990
• 11: Glenn Fung , Olvi L. Mangasarian, Proximal support vector machine classifiers, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.77-86, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502527]
• 12: Fung, G., & Mangasarian, O. L. (2003). Finite Newton method for Lagrangian support vector machine classification. Special Issue on Support Vector Machines. Neurocomputing, 55, 39--55.
• 13: Hamers, B., Suykens, J., Leemans, V., & Moor, B. D. (2003). Ensemble learning of coupled parmeterised kernel models. International Conference on Neural Information Processing (pp. 130--133).
• 14: 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
• 15: Lee, Y.-J., & Mangasarian, O. L. (2001). SSVM: A smooth support vector machine. Computational Optimization and Applications, 20, 5--22. Data Mining Institute, University of Wisconsin, Technical Report 99-03. ftp://ftp.cs.wisc.edu/pub/dmi/techreports/99-03.ps.
• 16: Mangasarian, O. L. (1994). Nonlinear programming. Philadelphia, PA: SIAM.
• 17: Mangasarian, O. L. (2000). Generalized support vector machines. Advances in Large Margin Classifiers (pp. 135--146). Cambridge, MA: MIT Press. ftp://ftp.cs.wisc.edu/math-prog/techreports/98-14.ps.
• 18: Mika, S., Rätsch, G., & Müüller, K.-R. (2000). A mathematical programming approach to the kernel fisher algorithm. NIPS (pp. 591--597).
• 19: Mika, S., Rätsch, G., Weston, J., Schölkopf, B., & Müüller, K.-R. (1999). Fisher discriminant analysis with kernels. Neural Networks for Signal Processing IX (pp. 41--48). IEEE.
• 20: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 21: Murphy, P. M., & Aha, D. W. (1992). UCI machine learning repository. www.ics.uci.edu/~mlearn/MLRepository.html.
• 22: J. A. K. Suykens , J. Vandewalle, Least Squares Support Vector Machine Classifiers, Neural Processing Letters, v.9 n.3, p.293-300, June 1999 [doi>10.1023/A:1018628609742]
• 23: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 24: Xu, J., & Zhang, X. (2001). Kernel mse algorithm: A unified framework for kfd, ls-svm and krr. Proceedings of The International Joint Conference on Neural Networks 2001. IEEE.
• 25: Yee, J., Geetanjali, A., Hung, R., Steinauer-Gebauer, A., wall, A., & McQuaid, K. (2003). Computer tomographic virtual colonoscopy to screen for colorectal neoplasia in asymptomatic adults. Proceeding of NEJM-2003 (pp. 2191--2200).

INDEX TERMS

Keywords:
Binary Classification, Heterogeneous Kernels, Linear Fisher Discriminant, Mathematical Programming