Algorithmes séquentiels pour l’analyse de données par méthodes à noyau

Algorithmes séquentiels pour l’analyse de données par méthodes à noyau

Sequential algorithms for data analysis with kernel-based methods

C. Richard F. Abdallah  R. Lengellé 

Équipe M2S, Institut des Sciences et Technologies de l'Information de Troyes (ISTIT - FRE CNRS 2732) Université de Technologie de Troyes (UTT), 12 rue Marie Curie, B.P. 2060, 10010 Troyes cedex, France

Corresponding Author Email: 
prenom.nom@utt.fr
Page: 
97-107
|
Received: 
10 February 2004
|
Accepted: 
N/A
|
Published: 
30 April 2004
| Citation

OPEN ACCESS

Abstract: 

In recent years, many methods of analysis and classification of data based on reproducing kernel Hilbert spaces have been developed. Most of these methods incorporate the fundamental principle dictated by Vapnik et al. in Support Vector Machines, which consists in extending linear algorithms to the non-linear case by using kernels. Kernel Fisher Discriminant (KFD) is one of these nonlinear methods which provides interesting results in many practical cases. However, the use of KFD requires storage and processing of matrices whose size equals the number of available data. This may be critical when the training set is large. This paper presents a sequential KFD algorithm which does not require the manipulation of large matrices. Sequential algorithms that fulfil the same requirements as KFD are also presented to perform Kernel Principal Component Analysis(KPCA) and Kernel Generalized Discriminant Analysis (KGDA).

Résumé

Au cours de la dernière décennie, de multiples méthodes pour l'analyse et la classification de données fondées sur la théorie des espaces de Hilbert à noyau reproduisant ont été développées. Elles reposent sur le principe fondamental du kernel trick, initialement exploité par Vapnik et col. dans le cadre des Support Vector Machines. Celui-ci permet d'étendre au cas non-linéaire des traitements initialement linéaires en utilisant la notion de noyau. La méthode KFD, pour Kernel Fisher Discriminant, constitue ainsi une généralisation non-linéaire de l'analyse discriminante de Fisher. Bien que son efficacité soit indiscutable, on déplore le fait que sa mise en œuvre nécessite le stockage et la manipulation de matrices de dimension égale au nombre de données traitées, point critique lorsque l'ensemble d'apprentissage est de grande taille. Cet article présente un algorithme séquentiel palliant cette difficulté puisqu'il ne nécessite, ni la manipulation, ni même le stockage de telles matrices. Un parallèle est également proposé entre KFD et KPCA, acronyme de Kernel Principal Component Analysis, cette dernière méthode constituant une extension au cas non-linéaire de l'analyse en composantes principales. Cet article s'achève par la présentation d'un algorithme séquentiel à noyau pour la méthode GDA, Generalized Discriminant Analysis, qui étend l'analyse discriminante de Fisher au cas multi-classe.

Keywords: 

Sequential algorithms, KPCA, KFD, Mercer kernels, SVM

Mots clés

Algorithmes séquentiels, ACP à noyau, AFD à noyau, noyaux de Mercer, SVM

1. Introduction
2. Espaces À Noyau Reproduisant Et Condition De Mercer
3. Méthode KFD Et Algorithme De Calcul Séquentiel
4. Analyse Discriminante Multi-Classe
5. Conclusion
  References

[1] G. Baudat, F. Anouar, Generalized discriminant analysis using a kernel approach, Neural Computation, vol.12, n°10, pp.2385-2404, 2000.

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

[3] L.Devroye, L.Györfi, G.Lugosi, A Probabilistic Theory of Pattern Recognition, New York: Springer-Verlag, 1996.

[4] R. O. Duda, P. E. Hart, D. G. Stork, Pattern Classification, New York: Wiley and Sons, 2001.

[5] S.C. Douglas, S.-I. Amari, S.-Y. Kung, Gradient adaptation with unitnorm constraints, Technical Report, n° EE-99-003, Southern Methodist University, Dallas, 1999.

[6] K. Fukunaga, Statistical Pattern Recognition, San Diego : Academic Press, 1990.

[7] R.Lengellé, C.Richard, Apprentissage de règles de décision à structure imposée et contrôle de la complexité (33 p.), In R.Lengellé, (éd.), Reconnaissance des Formes et Décision en Signal, Paris : Hermès Sciences, Traité IC2, 2002.

[8] S.Mika, Kernalgorithmen zur nichtlinearen Signalverarbeitung in Mermalsrôumen, Master's thesis, Technische Universität Berlin, 1998.

[9] S.Mika, G.Rätsch, J.Weston, B.Schölkopf, K.R.Müller, Fisher discriminant analysis with kernels, In Y. H. Hu, J. Larsen, E. Wilson, S. Douglas, (éds), Proc. Advances in Neural Information Processing Systems, San Mateo: Morgan Kaufmann, pp. 41-48, 1999.

[10] S. Mika, G. Rätsch, K.R. Müller, A mathematical programming approach to the kernel Fisher algorithm, In T. K. Leen, T. G. Dietterich, V. Tresp, (éds), Proc. Advances in Neural Information Processing Systems, Cambridge : MIT Press, pp. 591-597, 2001.

[11] P.Moerland, Mixture models for unsupervised and supervised learning, Ph. D. thesis, École Polytechnique Fédérale de Lausanne, 2000.

[12] K.R.Müller, S.Mika, G.Rätsch, K.Tsuda, B.Schökopf, An introduction to kernel-based learning algorithms, IEEE Transactions on Neural Networks, vol. 12, n°. 2, pp. 181-201, 2001.

[13] E.Oja, A simplified neuron model as a principal component analyzer, Journal of Mathematical Biology, vol.15, pp. 267-277.

[14] H.V. Poor, An Introduction to Signal Detection and Estimation, New York : Springer-Verlag, 1994.

[15] J.Principe, D.Xu, C.Wang, Generalized Oja's rule for linear discriminant analysis with Fisher criterion, Proc. ICASSP'97, vol. 4, pp.3401-3404, Seattle, WA, 1997.

[16] C.Richard, Méthodes à noyau et critères de contraste pour la détection à structure imposée, Habilitation à diriger des recherches, Université de Technologie de Compiègne, 2002.

[17] C.Richard, F.Abdallah, Algorithme d'apprentissage séquentiel pour la méthode KFD. Relations avec la méthode KPCA, Proc. Colloque GRETSI, Paris, 2003.

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

[19] S. Roweis, EM algorithm for PCA and SPCA, In M. I. Jordan, M.J.Kearns, S.A.Solla, (éds), Proc. Advances in Neural Information Processing Systems, Cambridge, MA : MIT Press, vol.10, pp.626-632, 1998.

[20] B.Schölkopf, A.Smola, K.-R.Müller, Nonlinear component analysis as a kernel eigenvalue problem, Neural Computation, vol.10, n°5, pp.1299-1319, 1998.

[21] B.Schölkopf, R. Herbrich, A.Smola, A generalized representer theorem, In Proceedings of the Annual Conference on Computational Learning Theory, pp. 416-426, 2001.

[22] H.L. Van Trees, Detection, Estimation, and Modulation Theory, vol.1, New York : John Wiley & Sons, 1968.

[23] V.Vapnik, A.Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities, Theory of Probability and its Applications, vol. 16, pp. 264-280, 1971.

[24] V.Vapnik, A.Chervonenkis, Theory of Pattern Recognition, Moscou : Nauka, 1974.

[25] V.Vapnik, Estimation of Dependencies based on Empirical Data, New York : Springer-Verlag, 1982.

[26] V.Vapnik, A.Chervonenkis, The necessary and sufficient conditions for consistency of the method of empirical risk minimization (in Russian), Yearbook of the Academy of Sciences of the USSR on Recognition, Classification and Forecasting, vol. 2, pp. 217-249, 1989.

[27] V.Vapnik, The Nature of Statistical Learning Theory, New York : Springer-Verlag, 1995.