Chargement...
 
Imprimer

Michael Aupetit, CEA

Apprentissage statistique de la topologie d’un ensemble de données étiquetées

le Graphe Génératif Gaussien Supervisé


Pierre Gaillard & Michaël Aupetit

Commissariat à l'Energie Atomique

DAM - Département Analyse Surveillance Environnement

pierre.gaillard@gmail.com , michael.aupetit à cea.fr


1. Introduction
Dans les problèmes statistiques d’apprentissage supervisé, on suppose généralement que les données étiquetées que l’on observe ont été générées par un modèle probabiliste dont le degré de liberté est inférieur à la dimension de l’espace ambiant. On suppose donc l’existence sous-jacente de variétés génératrices étiquetées.
L’objectif des méthdodes de discrimination est de construire un classifieur afin de prédire la classe de nouvelles données étiquetées avec le minimum d’erreur. Cependant, la classification est seulement la dernière étape du processus d’apprentissage qui peut être perfectionné par l’étude des propriétés topologiques des variétés génératrices étiquetées (leur dimension intrinsèque, leur connexité,…). Par exemple, dans le contexte de l’analyse exploratoire de données étiquetées, la connexité des variétés permet d’évaluer la complexité du problème de classification.


2. Trois hypothèses générales sur la génération des données
Image



3. Trois hypothèses simplifiées...Un modèle génératif

Pour simplifier le problème, on suppose que :
Image

Le modèle génératif sous-jacent est donc basé sur deux éléments gaussiens, appelés "points-gaussiens" et "segments-gaussiens", qui définissent un modèle de mélange.


4. L'Algorithme : quatre étapes

Figure (a) : une base de données étiquetées (+ et o) générées par 4 variétés. Le demi cercle en haut à gauche est "mixte" + et o (superposition de deux variétés), le demi-cercle en haut à droite est d'une seule classe o et les deux autres variétés (le point et le demi-cercle en bas) sont aussi d'une seule classe +.

4.1. L'initialisation : figure (b)
On place N prototypes à l'aide d'un mélange de gaussiennes isovariées et de variance unique.
Le nombre N de prototypes est sélectionné de manière a maximiser le "Bayesian Information Criterion" (Schwartz, 78).
On contruit le graphe de Delaunay des prototypes.
On initialise le Graphe Génératif Gaussien Supervisé (équiprobabilité des composants, équiprobabilité des classes).

4.2. L'Apprentissage : figure (c)
L'objectif d'apprentissage choisi est la maximisation de la vraisemblance.
Les paramètres du modèle - p(j), p(c|j) et la variance du bruit - sont estimés par l'algorithme EM (Dempster et al., 72).

4.3. L'Extraction de la topologie : figure (d)
Pour obtenir la topologie supervisée, on élague du Graphe de Delaunay intial (figure b) les arcs pour lesquels il y a peu de chance qu’ils aient généré les données i.e. les segment-gaussiens associés à un poids -p(j)- nul à la fin de l’apprentissage.
On associe à chaque point et segment-gaussien du modèle la ou les classes qu'il génère (représentée par le paramètre p(c|j)). Les points et segments-gaussiens générant plusieurs classes sont en vert.

4.4. La représentation de la topologie : figure (e)
La topologie des classes peut donc être représentée par "un graphe des classes" :
- une composante 'o' est densité-connectée (connectée dans le graphe final - figure (d)) à une composante '+/o' (en trait continu dans la figure (e))
- deux composantes '+' sont densité-déconnectées (non connectées dans le graphe final) des autres mais elles étaient adjacentes dans le graphe initial (figure (b))(en trait pointillé dans la figure (e))
Image


5. Topologie de la base IRIS

La base Iris est visualisée à l'aide de deux projections non-linéaires : l'ACC et le GTM.
On apprend le Graphe Génératif Gaussien Supervisé (voir l'algorithme section 4) et on représente sa topologie avec un "graphe des classes".

Projection et Topologie de la base IRIS - Setosa (+), Versicolour (o) et Virginica (*)

Contrairement à ce que laissent penser les projections, on peut en conclure grâce au graphe des classes, que :
- Les classes sont chacune en 1 composante connexe,
- Pas de chevauchement des variétés dans l’espace des données,
- Les classes * et o sont densité-connectées,
- La classe + est densité-déconnectée mais adjacente (dans le graphe initial) aux deux autres dans l’espace des données.


6. Conclusion

Découvrir la topologie d’un ensemble de données étiquetées, peut fournir d’importantes informations dans le but de construire un classifieur (Belkin & Niyogi, 04) ou d'analyser les données (Aupetit, 05).
Le Graphe Génératif Gaussien Supervisé est le premier modèle génératif permettant d'extraire la topologie des classes, en particulier d'apprendre la connexité inter et intra classes.

Nous envisageaons de poursuivre ces travaux dans le contexte des problèmes d'apprentissage semi-supervisé, en utilisant l'information topologique fournie par le Graphe Génératif Gaussien Supervisé pour aider la classification des données non-étiquetées.

Un workshop s'est tenu à NIPS*2007 sur le thème de l'apprentissage statistique de la topologie.

Pierre Gaillard & Michaël Aupetit



Afficher les messages d'erreurs PHP