1 Modélisation statistique de la topologie dun nuage de points CEA-DAM – Bruyères-le-Châtel...
Preview:
Citation preview
- Page 1
- 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