Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Apprentissage de Mélanges de Gaussiens par Maximisation de la marge avec SMO Tr

Apprentissage de Mélanges de Gaussiens par Maximisation de la marge avec SMO Trinh Minh Tri DO1, Thierry Artières LIP6, Université Pierre et Marie Curie Paris, France Résumé : Les modèles de Mélange de lois Gaussiennes (MG) ont étés utilisés dans de nombreux domaines, par exemple pour le traitement et la reconnaissance des images ou de la parole, où ils sont traditionnellement appris de façon non dis- criminante. Récemment des travaux ont porté sur l’apprentissage discriminants de tels modèles, à travers notamment la maximisation de la marge. L’idée de ces travaux consiste à formuler l’apprentissage discriminant de ces modèles comme un problème de maximisation de la marge et de le mettre sous la forme d’un pro- blème d’optimisation convexe, pour lequel des techniques d’optimisation de type descente de gradient projeté peuvent être employées. Nous nous inspirons ici de ces travaux et proposons une nouvelle formulation du problème permettant l’em- ploi d’un algorithme de type SMO, popularisé pour les Machines à Vecteurs de Support, plus performant et plus rapide que la descente de gradient. Mots-clés : apprentissage discriminant, maximisation de la marge, mélange Gaus- sien, SMO 1 Introduction Les modèles de Mélange de lois Gaussiennes (MG) ont étés utilisés dans de nombreux domaines, par exemple pour le traitement et la reconnaissance des images ou de la parole, aﬁn de construire des classiﬁeurs via l’apprentissage de modèles génératifs. On apprend alors un MG par classe pour modéliser la densité de probabilité conditionnelle, étant donnée la classe y, p(x|y) puis on implémente la règle de décision Bayésienne en supposant, par exemple, que les classes sont a priori équiprobables, donc en identiﬁant argmaxy p(x|y) ∗p(y). Un modèle de mélange Gaussien correspond à une densité de la forme : p(x|y) = K X k=1 p(k) × N(x; µyk, Σyk) (1) où N(x; µyk, Σyk) représente la loi gaussienne de moyenne µyk et de matrice de cova- riance Σyk évaluée en x, et p(k) représente la probabilité a priori que x soit produite par la kieme composante du mélange. Les modèles de mélanges Gaussiens doivent une partie de leur popularité d’une part au théorème central limite qui confère à la loi Gaus- sienne un statut particulier parmi les lois de probabilités paramétriques et d’autre part CAp 2007 à leur généricité. Les mélanges de lois Gaussiennes permettent en effet d’approximer toute densité de probabilité, pourvu qu’elle présente certains caractères de régularité. Egalement, ces modèles se sont avérés plutôt robustes et relativement faciles à em- ployer. Enﬁn, les lois gaussiennes et les mélanges de lois gaussiennes ont proﬁté de la popularité des modèles Markoviens cachés (MMC), auxquels ils sont traditionnelle- ment attachés, et qui ont été intensivement utilisés depuis une vingtaine d’années dans le cadre du traitement, de la reconnaissance et de la segmentation de séquences, par exemple en reconnaissance de la parole ou de l’écriture manuscrite etc. Les MG (de même que les MMC) sont traditionnellement appris indépendamment, classe par classe, à l’aide d’un critère de Maximum de Vraisemblance (Dempster et al., 1977; Neal & Hinton, 1998; Aﬁfy, 2005). L’optimisation est alors réalisée à l’aide d’un algorithme EM (Expectation - Maximization) qui repose sur une optimisation itérative des paramètres du modèle (moyennes, matrices de covariances, et probabilités a priori des composantes du mélange). L’approche générative consiste à apprendre de façon non discriminante un modèle de densité pour chaque classe, elle est en règle générale moins efﬁcace (du point de vue du taux de classiﬁcation) qu’une approche purement discrimi- nante. L’approche générative a pourtant été privilégiée depuis longtemps dans le cas de problèmes ouverts ou de données complexes, telles que des données séquentielles, pour lesquelles il est plus délicat de mettre en oeuvre des techniques discriminantes. Ainsi bon nombre de systèmes de reconnaissance de la parole ou du locuteur ont été construits sur des modèles acoustiques appris en modélisation plutôt qu’en discrimination. Nous nous intéressons ici à l’apprentissage discriminants de mélanges Gaussiens, notre but étant d’étendre par la suite ces travaux à l’apprentissage de modèles de séquences de type Markovien. Divers travaux ont porté sur l’apprentissage discriminant de systèmes qui étaient jusque là appris de façon non discriminante. Ainsi quelques approches discriminantes ont été proposées pour la classiﬁcation de séquences (plus rarement pour la segmenta- tion). Les premières approches ont consisté à exploiter des critères discriminants tels que le Maximum de Vraisemblance Conditionnelle (Nadas, 1983), le Maximum d’In- formation Mutuelle (L.R. et al., 1986; Normandin, 1991; Dahmen et al., 1999; Valtchev et al., 1997) ou le Minimum d’Erreur de Classiﬁcation (Juang & Katagiri, 1992) pour apprendre des modèles génératifs tels que les MG et les MMC. (LeCun et al., 1998) dresse un panorama d’un certain nombre de ces méthodes. (Tong & Koller, 2000) pro- posent d’apprendre un classiﬁeur discriminant, qui minimise la probabilité d’erreur cal- culée à l’aide de modèles génératifs. Plus récemment d’autres techniques ont consisté à construire des fonctions discriminantes à partir de modèles génératifs, comme l’uti- lisation des scores de Fisher (Jaakkola et al., 1999), ou l’exploitation de noyaux entre modèles dans (Moreno et al., 2004). Enﬁn, ces dernières années, plusieurs approches ont été proposées pour combiner les modèles Markoviens, exploitant des densités de probabilités de type mélanges de Gaus- siennes, et les algorithmes discriminants des machines à vecteurs de supports (Vapnik, 1999; Kruger et al., 2006; Li et al., 2005; Sha & Saul, 2006, 2007). Par exemple, la tech- nique proposée dans (Sha & Saul, 2006, 2007) vise à apprendre des MG (puis des MMC Gaussiens) par maximisation de la marge. Ces travaux sur l’apprentissage de modèles MG par maximisation de la marge sont très prometteurs. Leur application est pourtant SMO pour MG limitée, soit par la nature des modèles appris (e.g. seules les vecteurs moyennes sont appris dans (Li et al., 2005)), soit dans leur efﬁcacité, la convergence de l’algorithme proposé dans (Sha & Saul, 2006, 2007) est par exemple assez lente et sensible à l’ini- tialisation. Le travail décrit ici est inspiré des travaux de (Sha & Saul, 2006, 2007) et vise le même objectif, l’apprentissage de modèles génératifs basés sur des MG par maximisa- tion de la marge. Nous nous concentrons ici sur l’apprentissage de MG et proposons un algorithme qui diffère en plusieurs points de celui proposé par (Sha & Saul, 2006, 2007). Le coeur de notre travail tient dans la façon dont nous avons traité les contraintes convexes (caractère semi-déﬁni positif des matrices de covariance) et dans la formula- tion particulière du problème d’optimisation qui rend possible l’utilisation d’un algo- rithme d’optimisation du type SMO (Séquential Minimal Optimization) (Platt, 1998; Crammer & Singer, 2002; Aiolli & Sperduti, 2003), réputé nettement plus performant et plus rapide que les algorithmes de descente de gradient. Notre algorithme présente des avantages sur l’algorithme de gradient projeté (Bert- sekas, 1999) utilisé dans (Sha & Saul, 2006, 2007). Tout d’abord, par notre prise en compte des contraintes, nous évitons l’étape de projection de la solution dans l’espace des contraintes. Cette étape est d’une part assez lourde dans le cas de contraintes sur les matrices de covariance, et est d’autre part source d’erreurs numériques lorsque la dimension des données est importante. Notre approche, basée sur l’algorithme SMO, converge bien plus rapidement et mieux si bien que notre approche est expérimenta- lement plus performante et moins sensible à l’initialisation que l’algorithme original proposé par les auteurs. Dans la suite, nous présentons l’algorithme de départ, proposé dans (Sha & Saul, 2006, 2007) en Section 2. Puis en Section 3, nous détaillons notre approche en refor- mulant le problème sous sa forme duale et nous explicitons l’algorithme SMO dans notre cas. Enﬁn, nous fournissons en Section 4 des résultats expérimentaux permettant d’évaluer l’apport de notre algorithme en termes de vitesse de convergence et de per- formance pour le problème de classiﬁcation de chifres manuscrits, et sur deux bases de données internationales de référence. 2 Classiﬁcation avec des MG Nous nous focalisons ici sur un problème de discrimination pour des données vecto- rielles en dimension d, le but est de déterminer le label y correspondant à une donnée x = [x1, x2, .., xd]. Nous décrivons ici brièvement l’approche classiquement employée pour classiﬁer des données avec des modèles Gaussiens, puis nous présentons les tra- vaux proposés dans (Sha & Saul, 2006, 2007). 2.1 Approche non discriminante En supposant une loi de probabilité sur l’ensemble des vecteurs et les classes, l’ap- proche probabiliste consiste à estimer cette loi de probabilité et à classiﬁer en détermi- nant la classe y de probabilité a posteriori maximale, ou de façon équivalente la classe CAp 2007 maximisant la probabilité jointe P(x, y), c’est cette dernière stratégie qui est implé- mentée en pratique. La fonction de décision est déﬁnie par : ˆ y = argmax y p(x|y) × p(y) (2) où p(x|y) est la densité de probabilité de la classe y donnée par l’équation (1), et p(y) est la probabilité a priori de la classe y. Les lois composantes des densités sont des lois normales du type : p(x|Ny,k) = 1 p (2π)d|Σy,k| exp −1 2(x −µy,k)Σ−1 y,k(x −µy,k) (3) où Ny,k représente la kieme uploads/Litterature/ apprentissage-de-melanges-de-gaussiens-par-maximisation-de-la-marge-2007.pdf