Kernel Fisher‘s Discriminant

http://ida.first.fhg.de/~mika/Fisher.html

Kernel Fisher Discriminants

This page is dedicated to present detailed results,implementations and further information about Kernel Fisher Discriminants.

• Publications
  • W. Zheng, L. Zhao, and C. Zou. A modified algorithm for generalized discriminant analysis. Neural Computation, 16(6):1283-1297, 2004.

  • G.C. Cawley and N.L.C. Talbot. Efficient leave-one-out cross-validation of kernel fisher discriminant classifiers. Pattern Recognition, 2003. (PostScript) (PDF)

  • S.A. Billings and K.L Lee. Nonlinear Fisher discriminant analysis using a minimum squared error cost function and the orthogonal least squares algorithm. Neural Networks, 15(2):263-270, 2002.

  • T.v. Gestel, J.A.K. Suykens, G. Lanckriet, A. Lambrechts, B. De Moor, and J. Vanderwalle. Bayesian framework for least squares support vector machine classifiers, gaussian processs and kernel fisher discriminant analysis. Neural Computation, 15(5):1115-1148, May 2002.

  • P. Navarrete and J. Ruiz del Solar. Pattern Recognition with Support Vector Machines, volume 2388, chapter On the Generalization of Kernel Machines, pages 24-39. Springer, August 2002. (PDF)

  • J.A.K. Suykens, T. Van Gestel, J. De Brabanter, B. De Moor, and J. Vandewalle. Least Squares Support Vector Machines. World Scientific Pub. Co., Singapore, 2002. http://www.esat.kuleuven.ac.be/sista/lssvmlab/book.html.

  • S. Mika, G. Rätsch, and K.-R. Müller. A mathematical programming approach to the Kernel Fisher algorithm. In T.K. Leen, T.G. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems 13, pages 591-597. MIT Press, 2001. (PostScript) (PDF)

     

    We investigate a new kernel-based classifier: the Kernel Fisher Discriminant (KFD). A mathematical programming formulation based on the observation that KFD maximizes the average margin permits an interesting modification of the original KFD algorithm yielding the sparse KFD. We find that both, KFD and the proposed sparse KFD, can be understood in an unifying probabilistic context. Furthermore, we show connections to Support Vector Machines and Relevance Vector Machines. From this understanding, we are able to outline a very intuitive kernel-regression technique based upon the KFD algorithm. Simulations support the usefulness of our approach

  • S. Mika, A.J. Smola, and B. Schölkopf. An improved training algorithm for kernel fisher discriminants. In T. Jaakkola and T. Richardson, editors, Proceedings AISTATS 2001, pages 98-104, San Francisco, CA, 2001. Morgan Kaufmann. (PostScript) (PDF)

     

    We present a fast training algorithm for the kernel Fisher discriminant classifier. It uses a greedy approximation technique and has an empirical scaling behaviour which improves upon the state of the art by more than an order of magnitude, thus rendering the kernel Fisher algorithm a viable option also for large datasets.

  • K.-R. Müller, S. Mika, G. Rätsch, K. Tsuda, and B. Schölkopf. An introduction to kernel-based learning algorithms. IEEE Transactions on Neural Networks, 12(2):181-201, 2001.

     

    This review provides an introduction to Support Vector Machines, Kernel Fisher Discriminant analysis and Kernel PCA, as examples for successful kernel based learning methods. We first give a short background about VC theory and kernel feature spaces and then proceed to kernel based learning in supervised and unsupervised scenarios including practical and algorithmic considerations. We illustrate the usefulness of kernel algorithms by finally discussing applications such as OCR and DNA analysis.

  • G. Baudat and F. Anouar. Generalized discriminant analysis using a kernel approach. Neural Computation, 12(10):2385-2404, 2000.

  • S. Mika, G. Rätsch, J. Weston, B. Schölkopf, A.J. Smola, and K.-R. Müller. Invariant feature extraction and classification in kernel spaces. In S.A. Solla, T.K. Leen, and K.-R. Müller, editors, Advances in Neural Information Processing Systems 12, pages 526-532. MIT Press, 2000. (PostScript) (PDF)

     

    We incorporate prior knowledge to construct nonlinear algorithms for invariant feature extraction and discrimination. Employing a unified framework in terms of a nonlinear variant of the Rayleigh coefficient, we propose non-linear generalizations of Fisher‘s discriminant and oriented PCA using Support Vector kernel functions. Extensive simulations show the utility of our approach.

  • S. Mika, A.J. Smola, and B. Schölkopf. An improved training algorithm for kernel fisher discriminants. MSR-TR-2000- 77, Microsoft Research, Cambridge, UK, 2000. see also above, AISTATS 2001.

     

    We present a fast training algorithm for the kernel Fisher discriminant classifier. It uses a greedy approximation technique and has an empirical scaling behavior which improves upon the state of the art by more than an order of magnitude, thus rendering the kernel Fisher algorithm a viable option also for large datasets.

  • V. Roth and V. Steinhage. Nonlinear discriminant analysis using kernel functions. In S.A. Solla, T.K. Leen, and K.-R. Müller, editors, Advances in Neural Information Processing Systems, volume 12, pages 568-574. MIT Press, 2000.

  • S. Mika, G. Rätsch, J. Weston, B. Schölkopf, and K.-R. Müller. Fisher discriminant analysis with kernels. In Y.-H. Hu, J. Larsen, E. Wilson, and S. Douglas, editors, Neural Networks for Signal Processing IX, pages 41-48. IEEE, 1999. (PostScript) (PDF)

     

    A non-linear classification technique based on Fisher‘s discriminant is proposed. Main ingredient is the kernel trick which allows to efficiently compute the linear Fisher discriminant in feature space. The linear classification in feature space corresponds to a powerful non-linear decision function in input space. Large scale simulations demonstrate the competitiveness of our approach.

  • B. Schölkopf, S. Mika, C.J.C. Burges, P. Knirsch, K.-R. Müller, G. Rätsch, and A.J. Smola. Input space vs. feature space in kernel-based methods. IEEE Transactions on Neural Networks, 10(5):1000-1017, September 1999. (PostScript) (PDF)

     

    This paper collects some ideas targeted at advancing our understanding of the feature spaces associated with Support Vector (SV) kernel functions. We first discuss the geometry of feature space. In particular, we review what is known about the shape of the image of input space under the feature space map, and how this influences the capacity of SV methods. Following this, we describe how the metric governing the intrinsic geometry of the mapped surface can be computed in terms of the kernel, using the example of the class of inhomogeneous polynomial kernels, which are often used in SV pattern recognition. We then discuss the connection between feature space and input space by dealing with the question of how one can, given some vector in feature space, find a pre-image (exact or approximate) in input space. We describe algorithms to tackle this issue, and show their utility in two applications of kernel methods. First, we use it to reduce the computational complexity of SV decision functions; second, we combine it with the Kernel PCA algorithm, thereby constructing a nonlinear statistical denoising technique which is shown to perform well on real-world data.

  • A. Shashua. On the relationship between the support vector machine for classification and sparsified fisher‘s linear discriminant. Neural Processing Letters, 9(2):129-139, April 1999.

  • J.A.K. Suykens and J. Vanderwalle. Least squares support vector machine classifiers. Neural Processing Letters, 9(3):293-300, 1999.

  • R.A. Fisher. The use of multiple measurements in taxonomic problems. Annals of Eugenics, 7:179-188, 1936.

  18 references, last updated Thu Aug 5 12:39:52 2004
  • Submit new entry


• Simulation Results
Shortly we will post here the detailed simulation results for some KFD experiments we did.

• Implementations
Currently there are the following implementations for KFD, SKFD and LSKFD:
• Simple matlab function for two class KFD using mathematical programming. Click here to download
• Least Squares SVM page in Leuven
• Kernel Machine page (publications, implementations, etc.)
• Boosting.org a page devoted to boosting.