1 Modélisation statistique de la topologie dun nuage de points CEA-DAM – Bruyères-le-Châtel...
101
1 Modélisation statistique de la topologie d’un nuage de points CEA-DAM – Bruyères-le-Châtel Département Analyse Surveillance Environnement Laboratoire Détection et Sismologie Opérationnelle Présentation aux Journées de Géométrie Algorithmique 12-16 mars 2007 Michaël Aupetit – Ingénieur Chercheur Pierre Gaillard – Doctorant
1 Modélisation statistique de la topologie dun nuage de points CEA-DAM – Bruyères-le-Châtel Département Analyse Surveillance Environnement Laboratoire
1 Modlisation statistique de la topologie dun nuage de points
CEA-DAM Bruyres-le-Chtel Dpartement Analyse Surveillance
Environnement Laboratoire Dtection et Sismologie Oprationnelle
Prsentation aux Journes de Gomtrie Algorithmique 12-16 mars 2007
Michal Aupetit Ingnieur Chercheur Pierre Gaillard Doctorant
Page 2
2 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Un point de vue
statistique Etant donn un nuage de points de R D, chantillon dune
population (sous-varits de R D ) inconnue, si lon connat la densit
de probabilit de la population (estime partir de lchantillon), on
peut apporter une solution de nombreux problmes usuels:
classification, discrimination, rgression Il reste pourtant une
information peu exploite car difficile extraire
Page 3
3 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Une question en
attente de rponse Les modles statistiques de densit existant ne
permettent pas de rpondre la question suivante : Quelle est la
forme de ce nuage de points ?
Page 4
4 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Une rponse
subjective 1 point et 1 courbe La rponse attendue serait :
Topologie : 1 varit de type point, 1 varit de type segment Non
connectes lune lautre Gomtrie : Leur position absolue, leur
position relative, la courbure du segment, sa longueur, limportance
du bruit
Page 5
5 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Pourquoi modliser la
topologie in situ? Reconnaissance de formes Ajout de
caractristiques topologiques au caractristiques statistiques et
gomtriques Classification via composantes connexes; dimension
intrinsque Apprentissage semi-supervis
Page 6
6 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Pourquoi modliser la
topologie in situ? Reconnaissance de formes Ajout de
caractristiques topologiques au caractristiques statistiques et
gomtriques Classification via composantes connexes; dimension
intrinsque Apprentissage semi-supervis Analyse exploratoire Mesure
des caractristiques topologiques dun nuage de point en dimensions
>3 Plus court chemin le long des varits (projection non
linaire)
Page 7
7 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Pourquoi modliser la
topologie in situ? Reconnaissance de formes Ajout de
caractristiques topologiques au caractristiques statistiques et
gomtriques Classification via composantes connexes; dimension
intrinsque Apprentissage semi-supervis Analyse exploratoire Mesure
des caractristiques topologiques dun nuage de point en dimensions
>3 Plus court chemin le long des varits (projection non linaire)
Robotique, commande de processus Trajectoire optimale Cinmatique
inverse [Zeller, Schulten - IEEE ISIC1996]
Page 8
8 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille QV [Gray] Approches
descriptives (critre MSE) Approches gnratives (critre ML) Gauss.
Mixt. Etat de lart (Machine Learning): topologie fixe a priori
Codage,prdiction, compression Prdiction, correction derreurs
OD
Page 9
9 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille QV [Gray] Approches
descriptives (critre MSE) Approches gnratives (critre ML) Gauss.
Mixt. Etat de lart (Machine Learning): topologie fixe a priori
Codage,prdiction, compression Prdiction, correction derreurs OD SOM
[Kohonen] GTM [Bishop] Projection, clustering, compression
Projection 1D-2D Modle de topologie
Page 10
10 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille QV [Gray] Approches
descriptives (critre MSE) Approches gnratives (critre ML) Gauss.
Mixt. Etat de lart (Machine Learning): topologie fixe a priori
Codage,prdiction, compression Prdiction, correction derreurs OD SOM
[Kohonen] GTM [Bishop] Projection, clustering, compression
Projection 1D-2D Modle de topologie Prin. Curv. [Kegl] PSOM
[Walter] Prin. Curv. [Hastie,Stuetzle] LPCA [Bishop] Prdiction,
correction derreurs Projection 1D-2D Modle de varits
Page 11
11 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille QV [Gray] Approches
descriptives (critre MSE) Approches gnratives (critre ML) Gauss.
Mixt. Etat de lart (Machine Learning): topologie fixe a priori
Problmes : topologie impose ou incomplte Codage,prdiction,
compression Prdiction, correction derreurs OD SOM [Kohonen] GTM
[Bishop] Projection, clustering, compression Projection 1D-2D Modle
de topologie Prin. Curv. [Kegl] PSOM [Walter] Prin. Curv.
[Hastie,Stuetzle] LPCA [Bishop] Prdiction, correction derreurs
Projection 1D-2D Modle de varits
Page 12
12 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Etat de lart :
topologie apprise des donnes Information parcellaire sur la
topologie Calcul de la dimension intrinsque locale
Page 13
13 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Etat de lart :
topologie apprise des donnes Information parcellaire sur la
topologie Calcul de la dimension intrinsque locale Modlisation sous
forme de graphes partir des donnes seules Gabriel Graph, Sphere of
Influence Graph, Relative Neighborhood Graph, KNN Graph,
beta-squelette
Page 14
14 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Etat de lart :
topologie apprise des donnes Information parcellaire sur la
topologie Calcul de la dimension intrinsque locale Modlisation sous
forme de graphes partir des donnes seules Gabriel Graph, Sphere of
Influence Graph, Relative Neighborhood Graph, KNN Graph,
beta-squelette Modlisation sous forme de complexes simpliciaux
partir des donnes seules Crust [Amenta98] (k2) Sommets candidats
pour les triangles
Page 41
41 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille TRN et Witness
Complexes : les qualits Intrt On construit un sous-complexe de
Delaunay avec peu de calculs O(DNG) Si les sommets sont bien placs
et en nombre suffisant mais pas trop , Alors le complexe simplicial
obtenu est satisfaisant
Page 42
42 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille TRN et Witness
Complexes : les qualits Intrt On construit un sous-complexe de
Delaunay avec peu de calculs O(DNG) Si les sommets sont bien placs
et en nombre suffisant mais pas trop , Alors le graphe obtenu est
satisfaisant Passons aux dfauts de mon point de vue (ML) : Le choix
de ces ROI est-il pertinent pour rsoudre le problme pos?
Page 43
43 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille TRN et Witness
Complexes : les dfauts 1) Existence de zones mortes (K>2) donc
sous-utilisation des G chantillons (G>>N)
Page 44
44 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille TRN et Witness
Complexes : les dfauts 2) Pas de prservation des 0-simplexes
gnrateurs car tout point toujours deux prototypes 1er et 2nd plus
proches voisins qui seront donc connects Avec bruit Sans bruit
Page 45
45 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille TRN et Witness
Complexes : les dfauts 3) Sensibilit au bruit car modle bas sur des
ROI binaires : il suffit dun seul point dans la rgion pour crer le
lien.
Page 46
46 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille TRN et Witness
Complexes : les dfauts 4) Modle de varits abstrait : les
k-simplexes (k>0) sont plongeables, mais ne sont pas plongs
gomtriquement dans lespace du nuage de point. Ce nest pas un modle
des varits gnratrices au sens o on lentend en ML modle proche des
donnes au sens des moindres carrs (e.g. K-means), mais seulement un
modle de leur connexit.
Page 47
47 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille TRN et Witness
Complexes : les dfauts 4) Modle de varits abstrait : les
k-simplexes (k>0) sont plongeables, mais ne sont pas plongs
gomtriquement dans lespace du nuage de point. Ce nest pas un modle
des varits gnratrices au sens o on lentend en ML modle proche des
donnes au sens des moindres carrs (e.g. K-means), mais seulement un
modle de leur connexit.
Page 48
48 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille TRN et Witness
Complexes : les dfauts Toutes les mesures de proximit sont
effectues par rapport aux seuls sommets Le complexe simplicial est
abstrait 4) Modle de varits abstrait : les k-simplexes (k>0)
sont plongeables, mais ne sont pas plongs gomtriquement dans
lespace du nuage de point. Ce nest pas un modle des varits
gnratrices au sens o on lentend en ML modle proche des donnes au
sens des moindres carrs (e.g. K-means), mais seulement un modle de
leur connexit.
Page 49
49 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille TRN et Witness
Complexes : les dfauts 4.1) Consquence 1 : ROI de formes pas
toujours adaptes Les witness sont loin de larc quils gnrent
(contre-intuitif en ML: moyenne, centre de gravit)
Page 50
50 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille TRN et Witness
Complexes : les dfauts 4.2) Consquence 2 : Pas de self-consistance
(dfinie par Hastie et Stuetzle avec les Varits Principales), on
peut avoir une intersection vide entre un segment et sa ROI (les
points chantillons dun segment peuvent ne pas gnrer ce segment) Pas
dintersection entre la ROI et le segment quelle gnre
Page 51
51 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille TRN et Witness
Complexes : les dfauts 4.3) Consquence 3 : Volume des ROI non
pertinent car li la lgitimit que le simplexe associ appartienne ou
non au complexe de Delaunay Volume minuscule = arte de Delaunay peu
robuste un lger dplacement des sommets - Risque quaucune donne
nactive cette rgion - Volume de cette rgion sans rapport avec la
lgitimit dexistence de larte : la densit uniforme de donnes gnres
dans le carr, devrait impliquer une lgitimit similaire des artes
retenues (4 cts + 1 diagonale quimporte laquelle).
Page 52
52 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille TRN et Witness
Complexes : les dfauts 5) Pas de mesure objective de la qualit du
modle Comment mesurer la qualit du modle sur des donnes de grande
dimension (>3) dont on ne connat rien a priori? (visualisation
impossible) Comment comparer les modles en labsence de vrit
terrain?
Page 53
53 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Approximation : TRN
et Witness Complexes Bilan : Une approche peu satisfaisante (point
de vue ML) pour rsoudre notre problme Vers une autre solution :
formuler le problme avec une approche statistique
Page 54
54 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Tabula rasa
Page 55
55 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Hypothses gnrales
sur le processus statistique de gnration des donnes Des varits
gnratrices inconnues
Page 56
56 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Des varits
gnratrices inconnues desquelles sont tirs des individus avec une
densit de probabilit inconnue Hypothses gnrales sur le processus
statistique de gnration des donnes
Page 57
57 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Des varits
gnratrices inconnues desquelles sont tirs des individus avec une
densit de probabilit inconnue corrompus par un bruit de nature
inconnue menant aux observations Hypothses gnrales sur le processus
statistique de gnration des donnes
Page 58
58 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Des varits
gnratrices inconnues desquelles sont tirs des individus avec une
densit de probabilit inconnue corrompus par un bruit de nature
inconnue menant aux observations Hypothses gnrales sur le processus
statistique de gnration des donnes Ce que lon veut
Page 59
59 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Extraire la
topologie partir dun modle de densit Un moyen dextraire la
topologie / la structure des donnes est de modliser la distribution
p(x) cest--dire le processus statistique de gnration des donnes
Modle gnratif La clef du problme :
Page 60
60 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Extraire la
topologie partir dun modle de densit Un moyen dextraire la
topologie / la structure des donnes est de modliser la distribution
p(x) cest--dire le processus statistique de gnration des donnes
laide dune collection de varits gnratrices dont on puisse extraire
la topologie La clef du problme : Modle gnratif Topologie
Page 61
61 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Modliser des varits
gnratrices par des varits Approximation de varits par une varit
composite assemblage de varits lmentaires intressantes (comme en
approx. de fonctions)
Page 62
62 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Modliser des varits
gnratrices par des varits Approximation de varits par une varit
composite assemblage de varits lmentaires intressantes (comme en
approx. de fonctions) Quelle famille de varits lmentaires ?
Page 63
63 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Modliser des varits
gnratrices par des varits Approximation de varits par une varit
composite assemblage de varits lmentaires intressantes (comme en
approx. de fonctions) Quelle famille de varits lmentaires ?....
k-boules k=0k=1k=2k=3
Page 64
64 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Modliser des varits
gnratrices par des varits Approximation de varits par une varit
composite assemblage de varits lmentaires intressantes (comme en
approx. de fonctions) Quelle famille de varits lmentaires ?....
k-boules k=0k=1k=2k=3 Pas de connexit structurelle entre
lments
Page 65
65 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Modliser des varits
gnratrices par des varits Approximation de varits par une varit
composite assemblage de varits lmentaires intressantes (comme en
approx. de fonctions) Quelle famille de varits lmentaires ?....
k-pavs.... k-boules k=0k=1k=2k=3 Pas de connexit structurelle entre
lments
Page 66
66 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Modliser des varits
gnratrices par des varits Approximation de varits par une varit
composite assemblage de varits lmentaires intressantes (comme en
approx. de fonctions) Quelle famille de varits lmentaires ?....
k-pavs.... k-boules k=0k=1k=2k=3 Pas de connexit structurelle entre
lments Ncessite 2 k paramtres pour un k-pav
Page 67
67 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Modliser des varits
gnratrices par des varits Approximation de varits par une varit
composite assemblage de varits lmentaires intressantes (comme en
approx. de fonctions) Quelle famille de varits lmentaires ?....
k-pavs.... k-simplexes.... k-boules k=0k=1k=2k=3 Pas de connexit
structurelle entre lments Ncessite 2 k paramtres pour un k-pav
Page 68
68 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Modliser des varits
gnratrices par des varits Approximation de varits par une varit
composite assemblage de varits lmentaires intressantes (comme en
approx. de fonctions) Quelle famille de varits lmentaires ?....
k-pavs.... k-simplexes.... k-boules k=0k=1k=2k=3 Enveloppe convexe
de k+1 points dans IR D (D >=k ) Pas de connexit structurelle
entre lments Ncessite 2 k paramtres pour un k-pav
Page 69
69 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Modliser des varits
gnratrices par des varits Approximation de varits par une varit
composite assemblage de varits lmentaires intressantes (comme en
approx. de fonctions) Quelle famille de varits lmentaires ?....
k-pavs.... k-simplexes.... k-boules k=0k=1k=2k=3 Complexe
simplicial Enveloppe convexe de k+1 points dans IR D (D >=k )
Pas de connexit structurelle entre lments Ncessite 2 k paramtres
pour un k-pav
Page 70
70 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Modliser des varits
gnratrices par des varits Approximation de varits par une varit
composite assemblage de varits lmentaires intressantes (comme en
approx. de fonctions) Quelle famille de varits lmentaires ?....
k-pavs.... k-simplexes.... k-boules k=0k=1k=2k=3 Complexe
simplicial Pourquoi? CS = ensemble de varits : - parcimonieux (k+1
points / lments) - flexible (vers approx. universelle) - topologie
extractible (calculable, exacte car structure discrte + algo Betti)
- interpolation (linaire,B-splines) Enveloppe convexe de k+1 points
dans IR D (D >=k ) Pas de connexit structurelle entre lments
Ncessite 2 k paramtres pour un k-pav
Page 71
71 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Modliser des varits
gnratrices par des varits Approximation de varits par une varit
composite assemblage de varits lmentaires intressantes (comme en
approx. de fonctions) Quelle famille de varits lmentaires ? Quel
complexe simplicial?.... k-simplexes
Page 72
72 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Modliser des varits
gnratrices par des varits Approximation de varits par une varit
composite assemblage de varits lmentaires intressantes (comme en
approx. de fonctions) Quelle famille de varits lmentaires ? Quel
complexe simplicial? Un que lon sache construire : le complexe de
Delaunay.... k-simplexes
Page 73
73 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Modle propos Des
varits gnratrices inconnues desquelles sont tirs des individus avec
une densit de probabilit inconnue corrompus par un bruit de nature
inconnue menant aux observations.
Page 74
74 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Modle propos Des
varits gnratrices inconnues desquelles sont tirs des individus avec
une densit de probabilit inconnue corrompus par un bruit de nature
inconnue menant aux observations. Supposons une varit composite
linaire par morceaux sous-complexe du CS Delaunay
Page 75
75 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Modle propos Des
varits gnratrices inconnues desquelles sont tirs des individus avec
une densit de probabilit inconnue corrompus par un bruit de nature
inconnue menant aux observations. chaque composant de laquelle est
associ une fdp uniforme Supposons une varit composite linaire par
morceaux sous-complexe du CS Delaunay
Page 76
76 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Modle propos Des
varits gnratrices inconnues desquelles sont tirs des individus avec
une densit de probabilit inconnue corrompus par un bruit de nature
inconnue menant aux observations. Supposons une varit composite
linaire par morceaux sous-complexe du CS Delaunay chaque composant
de laquelle est associ une fdp uniforme convolue un bruit Gaussien
centr isovari.
Page 77
77 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Modle propos Des
varits gnratrices inconnues desquelles sont tirs des individus avec
une densit de probabilit inconnue corrompus par un bruit de nature
inconnue menant aux observations. Supposons une varit composite
linaire par morceaux sous-complexe du CS Delaunay chaque composant
de laquelle est associ une fdp uniforme convolue un bruit Gaussien
centr isovari. Un complexe simplicial gnratif gaussien
Page 78
78 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Gnrer les
k-simplexes gaussiens Comment dfinir un modle gnratif bas sur un
complexe simplicial? Expression analytique Approximation (quasi
Monte Carlo) Point-gaussien A Segment-gaussien A B
Triangle-gaussien A B C k-simplexe gaussien
Page 79
79 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Le Complexe
Simplicial Gnratif Gaussien Un modle de mlange gaussien tendu aux
k-simplexes dun complexe simplicial initial Rglage des paramtres
Positionnement des sommets du complexe simplicial Probabilit a
priori des k-simplexes Variance du bruit gaussien Critres
Maximisation de la vraisemblance du modle sachant les donnes
Pnalisation par le critre BIC gestion automatique de la complexit
du modle lie au nombre de prototypes Mthode doptimisation GEM
Page 80
80 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Principe du Graphe
Gnratif Gaussien (GGG) Positionnement de prototypes par Modle de
mlange gaussien puis construction du graphe de Delaunay (varit
composite) Initialisation
Page 81
81 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Principe du Graphe
Gnratif Gaussien (GGG) Positionnement de prototypes par Modle de
mlange gaussien puis construction du graphe de Delaunay (varit
composite) Initialisation Modle statistique de densit gnr par la
varit composite (quiprobabilit des composants)
Page 82
82 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Principe du Graphe
Gnratif Gaussien (GGG) Certaines composantes ont une probabilit
associe (quasi-)nulle: elle ne servent pas expliquer les donnes.
Aprs apprentissage
Page 83
83 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Principe du Graphe
Gnratif Gaussien (GGG) Certaines composantes ont une probabilit
associe (quasi-)nulle: elle ne servent pas expliquer les donnes. On
peut les supprimer : lagage du graphe Aprs apprentissage
Page 84
84 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Principe du Graphe
Gnratif Gaussien (GGG) Certaines composantes ont une probabilit
associe (quasi-)nulle: elle ne servent pas expliquer les donnes. On
peut les supprimer : lagage du graphe Aprs apprentissage Complexe
simplicial dont la topologie est suppose proche de celle des varits
gnratrices des donnes
Page 85
85 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Exprience : CHL vs
GGG donnes bruites Seuillage sur le nombre de witness
Page 86
86 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Exprience : CHL vs
GGG donnes bruites Seuillage sur le nombre de witness
Page 87
87 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Exprience : CHL vs
GGG donnes bruites Seuillage sur le nombre de witness
Page 88
88 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Algorithme propos :
algorithme incrmental 1.Dimension 0 Placer les simplexes de
dimension 0 a laide dun modle de mlange gaussien isovari 2.Ajouter
la dimension 1 i.Construire le Graphe de Delaunay, ii.Initialiser
le poids des segments, iii.Modifier le poids des diffrents
simplexes (dim 0 et 1) et la variance du bruit, iv.Modifier les
sommets en plus des autres paramtres v.lagage 3. Ajouter la
dimension k i.Ajouter les simplexes de dimensions o cest possible,
ii.Initialiser le poids des simplexes, iii.Modifier le poids des
diffrents simplexes (dim 0 k) et la variance du bruit, iv.Modifier
les sommets en plus des autres paramtres v.lagage
Page 89
89 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Exemple
Page 90
90 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Application sur
donnes hydro-acoustiques Chant des baleines (F. Samaran, C. Guinet,
Centre dtude biologique de Chiz CNRS)
Page 91
91 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Application sur
donnes hydro-acoustiques Chant des baleines (F. Samaran, C. Guinet,
Centre dtude biologique de Chiz CNRS)
Page 92
92 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Application sur
donnes hydro-acoustiques Chant des baleines (F. Samaran, C. Guinet,
Centre dtude biologique de Chiz CNRS) chantillonnage
Page 93
93 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Application sur
donnes hydro-acoustiques Chant des baleines (F. Samaran, C. Guinet,
Centre dtude biologique de Chiz CNRS) chantillonnage Filtrage
statistique du bruit de fond par ajout dune composante ddie dans le
GGG
Page 94
94 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Application sur
donnes hydro-acoustiques Chant des baleines (F. Samaran, C. Guinet,
Centre dtude biologique de Chiz CNRS) chantillonnage Filtrage
statistique du bruit de fond par ajout dune composante ddie dans le
GGG Puis filtrage topologique des 0-simplexes avant extraction de
caractristiques gomtriques de la composante connexe 1D candidate
pour comparaison une base de rfrence (discrimination)
Page 95
95 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Points positifs 1)
Pas de zones mortes : toutes les donnes sont exploites 2) 0-varits
gnratrices isoles prserves 3) Moindre sensibilit au bruit : on
introduit un modle de bruit (gaussien) et les ROI sont floues
(gaussiennes) 4) Modle de varits complet : plongement gomtrique de
tous les k-simplexes 4.1) ROI englobant les k-simplexes
(convolution) 4.2) Self-consistance : modle gnratif lest par
dfinition 4.3) Pertinence des k-simplexes mesure par une probabilit
5) Mesure objective de la qualit : la vraisemblance pnalise
Page 96
96 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Points durs No free
lunch Complexit de calcul en O(DN 3 ) (graphe de Delaunay initial)
Convergence lente (EM) Approximation numrique pour le calcul des
k-simplexes gaussiens Multiples optima locaux de la fonction de
vraisemblance
Page 97
97 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Points clefs
Estimateur statistique de la topologie Ide principale : Mme gomtrie
implique mme topologie Donc en imposant une proximit gomtrique
modle/donnes (modulo le bruit gaussien) avec une gestion de la
complexit du modle, on suppose que la topologie du modle sera
proche de celle des varits gnratrices (do limportance du plongement
complet du modle) Do la conjecture suivante : La topologie des
varits modles estime celle des varits gnratrices du nuage de points
dautant mieux que le modle de densit associ est vraisemblable
complexit donne Modle de mlange particulier Topologie des varits
extractible et flexible Gnralisant les modles de mlange classiques
(0-simplexes) Estimation de densits particulires localement
uniformes (voire linaire ou non-linaire par interpolation)
Page 98
98 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Questions ouvertes
Validit de la conjecture bonne vraisemblance pnalise = bonne
topologie - liens avec la persistence topologique? - lien entre
prservation de la topologie et densit de lchantillonnage (au sens
probabiliste)? Thorme dapproximation universelle de varit?
Complexit (nb. doptima) de la fonction de vraisemblance?
Algorithmes efficaces pour Optimiser la vraisemblance? Construire
le graphe de Delaunay en dimension D ? Estimer les k-simplexes
gaussiens?
Page 99
99 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Travaux et
collaborations Collaboration avec F. Chazal (INRIA Futurs) et D.
Cohen-Steiner (INRIA Sophia) Collaboration avec S. Canu, G.Gasso et
K. Zapien (INSA-Rouen) Thse Pierre Gaillard (CEA-UTC, G. Govaert) :
adaptation du modle dans le cas de donnes tiquetes pour lanalyse de
donnes et lapprentissage semi-supervis Thse venir (CEA-UTC, G.
Govaert) : utilisation du modle pour la visualisation de systmes
dinfrence floue Publications NIPS 2005 et ESANN 2007 Proposition
dun Workshop sur ce thme NIPS en dcembre 2007 (Communaut Machine
Learning)
Page 100
100 Merci de votre attention
Page 101
101 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Perspectives pour
les Witness Complex Comment positionner les prototypes pour que les
ROI soient mieux places
Page 102
102 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Vorono et Delaunay
Du diagramme de Vorono au complexe simplicial de Delaunay Ensemble
v de points de IR D Cellules de Vorono d-cellule
Page 103
103 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Vorono et Delaunay
Du diagramme de Vorono au complexe simplicial de Delaunay Ensemble
v de points de IR D Cellules de Vorono (d-1)-cellule
Page 104
104 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Vorono et Delaunay
Du diagramme de Vorono au complexe simplicial de Delaunay Ensemble
v de points de IR D Cellules de Vorono (d-2)-cellule
Page 105
105 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Vorono et Delaunay
Du diagramme de Vorono au complexe simplicial de Delaunay Ensemble
v de points de IR D Rgions de Vorono Graphe de Delaunay chaque
d-cellule un 0-simplexe
Page 106
106 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Vorono et Delaunay
Du diagramme de Vorono au complexe simplicial de Delaunay Ensemble
v de points de IR D Rgions de Vorono Graphe de Delaunay
Page 107
107 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Vorono et Delaunay
Du diagramme de Vorono au complexe simplicial de Delaunay Ensemble
v de points de IR D Rgions de Vorono Graphe de Delaunay chaque
(d-1)-cellule un 1-simplexe
Page 108
108 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Vorono et Delaunay
Du diagramme de Vorono au complexe simplicial de Delaunay Ensemble
v de points de IR D Rgions de Vorono Graphe de Delaunay chaque
(d-1)-cellule un 1-simplexe
Page 109
109 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Vorono et Delaunay
Du diagramme de Vorono au complexe simplicial de Delaunay Ensemble
v de points de IR D Rgions de Vorono Graphe de Delaunay chaque
(d-1)-cellule un 1-simplexe
Page 110
110 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Vorono et Delaunay
Du diagramme de Vorono au complexe simplicial de Delaunay Ensemble
v de points de IR D Rgions de Vorono Graphe de Delaunay chaque
(d-1)-cellule un 1-simplexe
Page 111
111 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Vorono et Delaunay
Du diagramme de Vorono au complexe simplicial de Delaunay Ensemble
v de points de IR D Rgions de Vorono Graphe de Delaunay chaque
(d-1)-cellule un 1-simplexe
Page 112
112 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Vorono et Delaunay
Du diagramme de Vorono au complexe simplicial de Delaunay Ensemble
v de points de IR D Rgions de Vorono Graphe de Delaunay chaque
(d-1)-cellule un 1-simplexe
Page 113
113 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Vorono et Delaunay
Du diagramme de Vorono au complexe simplicial de Delaunay Ensemble
v de points de IR D Rgions de Vorono Complexe simplicial de
Delaunay chaque (d-2)-cellule un 2-simplexe
Page 114
114 15/03/2007 CEA-DAM Laboratoire Dtection et Sismologie
Oprationnelle Prsentation JGA 2007 - Marseille Vorono et Delaunay
Du diagramme de Vorono au complexe simplicial de Delaunay Ensemble
v de points de IR D Rgions de Vorono Complexe simplicial de
Delaunay chaque (d-k)-cellule un k-simplexe