Soutenance hdr aupetit_2012

APPROCHES TOPOLOGIQUES POUR

L’ANALYSE EXPLORATOIRE DE DONNÉES

ET L’AIDE À LA DÉCISION

SOUTENANCE D’HABILITATION A DIRIGER DES RECHERCHES

11 juillet 2012

Michaël Aupetit

Expert senior CEA

CEA LIST

Laboratoire Information, Modèles et Apprentissage

CEA | 10 AVRIL 2012

CONTEXTEDES DONNEES A LA DECISIONAPPROCHE TOPOLOGIQUEDEUX AXES DE RECHERCHESVISUALISATION TOPOLOGIQUE IN SITUMODELISATION TOPOLOGIQUE IN SITUPERSPECTIVESCONCLUSION

| PAGE 2

CEA | 10 AVRIL 2012

CONTEXTE

| PAGE 3

CEA | 10 AVRIL 2012

CONTEXTE

| PAGE 4CEA | 11 JUILLET 2012

Une information sans contexte n’a pas de sens

CONTEXTE


-300

000

-100

00

-600

0

-500

-150

-50

-30

-20

-10

-5

(Néant)

Années

Notre parcours

Mon parcours

CONTEXTE


-300

000

-100

00

-600

0

-500

-150

-50

-30

-20

-10

-5

Années

…à un monde fortement instrumentéet automatisé.

Une explosion technologique

D’un monde sans machines…

…mais aussi des calamités

CONTEXTE


-300

000

-100

00

-600

0

-500

-150

-50

-30

-20

-10

-5

Temps en années

Un monde toujours incertain

D’une nature qui dicte ses lois… …à une technologie qui génère des solutions…

http://www.visoterra.com/images/original/visoterra-fumerolles-de-neige-3376.jpg




CONTEXTE


-300

000

-100

00

-600

0

-500

-150

-50

-30

-20

-10

-5

Du graphique pour communiquer…

Temps en années

Face aux incertitudes, un besoin inné de comprendre et de contrôler

… au graphique pour comprendre et agir

DES DONNÉES À LA DÉCISION

| PAGE 9

CEA | 10 AVRIL 2012


Des données au modèle

Agir c’est modifier le monde

Pour bien agir, il faut prédire les conséquences de nos actes

Pour prédire il faut un modèle simulable du système réel sur lequel on agit

Pour calibrer ce modèle, il faut des données observées sur le système réel

Pour acquérir ces données, on instrumente le système réel



Les modèles statistiques

Les données sont des individus, mesures simultanées de plusieurs variables (pression, température, vitesse, débit, densité…)

Hypothèse Statistique - l’ensemble des individus forme un échantillon

supposé issu d’une population plus vaste mais inobservable suivant une certaine fonction densité de probabilité

Inférence Bayésienne [Jayne 2003]- Estimer les paramètres d’un modèle de la

population à partir de l’échantillon et d’une hypothèse a priori


Deux types de modèles [Tukey 1977]

Modèles descriptifs pour l’analyse exploratoire de donnée

Modèles prédictifs pour l’analyse confirmatoire et l’inférence



Exploration et décision

Représentation

Monde objectif

Monde objectif

Monde subjectif

Modèle prédictif

Action

(taux de réussite 73.4992%)

Système réel

Monde subjectif

Chaîne de mesure

Modèle descriptif

Le besoin d’interprétabilité

En pratique- système réel inconnu- décisions prises à partir du modèleNécessité de distinguer - la part de réalité reproduite par le modèle - la part d’artifice introduite par le modèle Le modèle doit être interprétable



ModèleAdjacence des terres, mers, fleuves, montagnes…

Longues distances, formes…

Vitesse du vent, pression,plus court chemin…

Système réel


Les conditions de l’interprétabilité

Interaction avec l’analyste- se forger une représentation mentale (subjective) dont le

modèle est l’implémentation objective- s’investir dans la conception du modèle [Gibson 1979]

pour corréler perceptions et actions : changer interactivement de points de vue

- « On ne connaît un objet qu’en agissant sur lui et en le transformant » [Piaget 1970]

Elément d’une famille de modèles interprétables- hiérarchie de modèles simples (empan mnésique 7), - transparent (montre les relations élémentaires)- prévisible (confiance)- complet (non muet)- contextualisé (fournit une référence)- sensé (reliant au sens fournit a priori)


Explorationinteractive

Modèle interprétable

L’interprétabilité pour l’aide à la décision

Conception interactive du modèle par analyse exploratoire

Exploitation du modèle prédictif implémentation objective du modèle mental subjectif



Système réelExploration et décision

Modèle descriptif

Représentation

Modèle prédictifinterprétable

Action

Système réel(taux de réussite

100%)


La visualisation comme canal de transmission vers l’analysteDeux modes de représentation graphique

Propriétés du canal visuel- Plus grande bande passante de tous nos sens- Perception pré-attentive diminue la charge cognitive [Triesman 1985]- Théorie psychologique de la Gestalt [1920]

- le tout est plus que la somme des parties- loi de continuité- loi de proximité- loi de similitude


Pour compter le nombre dee dans un texte il fautle scanner totalement.

Pour compter le nombre dee dans un texte il fautle scanner totalement.

symbolique (conventionnel) analogique (perceptuel)


Qu’est-ce qu’une bonne représentation graphique?

Objectif de la représentation graphique- corréler les variables abstraites (informations topologique, statistiques et

géométriques) aux variables graphiques (position, couleur, forme des glyphes…) en minimisant la charge cognitive (perception pré-attentive)

Critères- expressivité (ne montrer que le nécessaire)- efficacité (choix des bonnes variables graphiques)- vérité (toute valeur estimée est montrée avec son incertitude)


Age

fem

me

Age mari

Age mari

Age femme

I1 20 19

I2 42 37

I3 35 38

… … …

Aha!

Age femme = k1* Age mari + k2

« The purpose of visualization is insight, not pictures » Ben Schneiderman, 2008


Chaîne de visualisation : des capteurs aux neurones

V1 V2

I1 2 3.4

I2 1 -0.7

I3 0.33 4

… … …

ND

Réalité

Capteurs

Mesures (données brutes)

Nuage dans IR2

Espace de représentation- Choix individus et variables abstraites, - Codage géométrique - Choix des variables graphiques

Rendu , type d’écran

Perception visuelle

Cognition

Filtrage

Encodage graphique

Réglage écran

Choix capteursExpérience

Echan

tillon

nage

Incertit

udes, bru

it

Distorsions géométriques et topologiques

Acuité visuelleperception des couleurs…

Illusions cognitives, biais d’attention, croyance a priori…

Nb de pixels, rendu des couleurs…

Action possible

Distorsion possible

Concentration, apprentissage

Port de lunettes

APPROCHE TOPOLOGIQUE

| PAGE 19

CEA | 10 AVRIL 2012


Notions de base

La Topologie étudie, caractérise (invariants) et classes les espaces

Deux espaces ont même topologie si et seulement s’ils sont homéomorphes, liés par une fonction H continue de réciproque H-1 continue


x’ = H(x)

H H-1


Points clefs de l’approche topologique

Conditions pour obtenir un bon modèle prédictif (capacités de généralisation)- régularité, continuité du phénomène modélisé - des causes voisines engendrent des effets voisins


Prédiction ?

présent

présent

Prédiction ?


Points clefs de l’approche topologique

Robustesse- Géométrie préservée par isométries (translations, rotations, symétries)- Probabilités préservées par similitudes (isométries + homothéties)- Topologie (connexités, dimension, torsion) préservée par homéomorphismes- Connexités préservées par homotopies

Fiabilité- Il est plus probable que la chaîne de mesure soit une homotopie- l’information topologique a plus de chance de survivre à la chaîne de mesure- l’information topologique est plus fiable que l’information probabiliste ou géométrique


U

Isométries Similitudes Homéomorphismes Homotopies

U U

Objet initial

ConnexitéTopologie

ProbabilitésGéométrie


Gestalt visuelle et Topologie : le principe de fiabilité

Gestalt : loi de similitude « qui se ressemble s’assemble »

Principe de fiabilité - Les objets qui apparaissent immédiatement comme voisins à l’écran (pré-

attentif) doivent être le plus souvent effectivement voisins suivant l’information à transmettre, afin de diminuer la charge cognitive nécessaire pour reconstituer l’information qui n’est pas transmise suivant ce principe


L’information topologique forme le contexte dans lequel s’interprètent les autres informations

Sans topologie Avec topologie


Applications de l’approche topologique

Contrôle d’un système critique

Projections non linéaires - diagnostic a priori- distances géodésiques


Mauvaise généralisation d’un modèle prédictif ignorantl’information topologique

[Zeller 1996]


Applications de l’approche topologique

Discrimination semi-supervisée

Classification automatique

Autres applications- débruitage- reparamétrage- préservation de l’interprétabilité dans les systèmes d’inférence floue


Etat épileptique

Etat normal

Espace des phases EEG [Kalitzin et al. 2010]

Prise en compte uniquement des données étiquetées

- 1

+1

Prise en compte de la connexité des données non étiquetées

Topologie et cognition

La sélection Darwinienne d’un encodage neuronal topologique montre l’importance de l’information topologique dans les processus cognitifs

La grammaire et le langage [Petitot 1991] s’appuient sur les structures topologiques émergeant de notre système primitif de perception du temps et de l’espace.



Carte de Kohonen de différentes trajectoires [Bernard 2009]

Reconstitution de l’organisation de la rétine à partir des images perçues [leRoux 2007]

Carte rétinotopique d’une souris [Hübener 2003]

Topologie et représentation (Intelligence Artificielle)

Description topologique primitive

Description objective (« réalisme » vs « constructivisme »)



Plan objectif Pd’un bâtiment Plan subjectif P1

du bâtimentPlan subjectif P2

du bâtiment

Malgré le système de mesure et l’expérience radicalement différents de chaque observateur, un invariant topologique persiste entre eux et le monde objectif :

la connexité du plan du bâtiment (encodée par un graphe reliant les pièces)

Descriptions géométriques et probabilistes s’appuient sur la description topologique


Les clefs de l’approche topologique pour l’aide à la décision

Perception visuelle native (Gestalt, traitement pré-attentif rapide)

Description primaire essentielle (Mathématiques)

Robuste des capteurs aux neurones (information objective et partageable)

Essentielle à l’interprétabilité par le principe de fiabilité (carte contextuelle)

Solution de problèmes classiques en fouille de données et apprentissage automatique

Encodée dans le cortex visuel (rôle analytique et plausibilité biologique)

Solution de problèmes fondamentaux de l’Intelligence Artificielle


DEUX AXES DE RECHERCHE

| PAGE 29

CEA | 10 AVRIL 2012

Comment transmettre l’information topologique à l’analyste ?

En 2 dimensions

DEUX AXES DE RECHERCHES


Topologique Statistique GéométriqueStructures sous-jacentes Densités sous-jacentes Formes sous-jacentes

et position des points

Inférence sur la population (modèle prédictif)

Mesure sur l’échantillon (modèle descriptif)

Problème, en pratique plus de 2 variables à analyser



En dimension supérieure à 2


Données multivariées

Modèle topologique

subjectif???

Représentation perceptuelleDistorsions dues à la projection

Visualisationd’Information

Visualisation topologique in situ

Représentation symboliqueConnexité préservée par la projection

Apprentissage Automatique

Modèle topologique objectif

Modélisation topologique in situ




Représentation perceptuelle


Visualisationd’Information

Modèle topologique

subjectif

Visualisation topologique in situ

VISUALISATION TOPOLOGIQUE IN SITU

| PAGE 33

CEA | 10 AVRIL 2012

Données

Tâches / mesure de similarité entre individus (MI) ou entre variables (MV)

Groupes I’ et I’’ d’individussimilaires (euclidien) / {V2,V4}

I’

I’’

Groupes {V1,V2} et {V3,V4} de variablessimilaires (corrélation) / individus I

V1 V2 …

I1 2 3.4 …

I2 1 -0.7 …

I3 0.33

4 …

… … … …

I

VT 1 D1

N

I1 I2 I3 …

I1 0 2 1.3 …

I2 2 0 -0.7 …

I3 1.3 -0.7 0 …

… … … … …

I

I

MI

N

11 NV2

V1

MV…

Grouper les individus Grouper les variables


Distorsions de projection(réduction de dimension, contraintes

topologiques, optima locaux)

Distorsions de perception(pixels écran, rendu couleurs, acuité visuelle,

illusions perceptuelles, biais cognitifs…)

Ce qui est montré Ce qui est perçuMI

Inférence ???

Distorsions dans la chaîne de visualisation


???

Déchirures Faux Voisinages

Espace d’origine Espace de projection

[T, MI , MV ] [ ]

Inférence possible car connaissances externes aux données

Distorsions de projection


Espace de projection

???

Espace d’origine

n’est qu’une estimation de MI

seule ne permet pas de reconstruire MI

MI = + E

[E] MI

Diagramme de Shepard

[T, MI , MV ] [ ]

Non interprétable !!!

Distorsions de projection


Trois règles d’inférence graphique à partir de la projection

Aucune distorsionLe groupe existe

dans l’espace d’origine Chevauchement vraiLes deux classesse chevauchent

dans l’espace d’origine

Séparation vraieLes deux groupes

sont séparéesdans l’espace d’origine

Echelle de couleur 2D perceptuellement uniforme

D

FV

Déchirure Faux Voisinage D&FVOrigine

Montrer et E sur la même représentation graphique : CheckViz

[ ][ ][ ][MI]


D

FV

Classe bleue et classe verte séparées dans l’espace d’origine

Séparation vraie

[ , E ] [ , E ]

Classe rouge morceléedans l’espace d’origine

Aucune distorsion

CheckViz


MS*

MS*MS*

MS*

Déchirure Déchirure

Déchirure Faux voisinage

[ , MI ]

Montrer et MI sur la même représentation graphique : ProxiViz

[ ]

Non interprétable !!!

[ , E ]


CheckViz

Projection ACC données ISOLETD=617, N=1800

Proximité intra-classe

Proximité inter-classe

ProxiViz

Structureinférée fausse

Structureinférée

d’origine


Applications

GTM GTM + ProxiViz

Les données Oil Flow (1000 individus, 3 classes, 12 variables) sont projetées (à droite) par une carte topographique générative (GTM). La classe verte semble formée de deux composantes (ellipses rouges). Est-ce vrai?

Question Réponse

2 groupes? 1 groupe

Applications


Lorène Allano, Sylvain Lespinats, Jean-Philippe Poli

ClassiViz : Extension de ProxiViz à la classification

Projet ERITR@C

Applications

T-ShirtVélos

Arbres Livres

MoteursPlantes

Carton

Câbles

Jouets

Bassines

ClassiViz Brevet en cours

de dépôt PCT

Projet ERITR@CAnalyser des conteneurs

sans les ouvrir

ClassiViz dans le projet ERITR@C

Carte des contenus de référence

[ , MI ][ ]

Très forte

Très faible

Similarité de la donnée à classer avec les

données de référence

T-ShirtVélos

Arbres Livres

MoteursPlantes

Carton

Câbles

Jouets

BassinesSignature chimique mesurée

Contenu réel caché

Interprétation « le contenu réel est composé de matériaux plutôt présents dans les arbres et les T-Shirts »


Paradigme WinSitu pour l’interprétabilité

3 principes clefs pour l’interprétabilitéPrincipe de fiabilité

- une projection minimisant les distorsions E

Principe d’authenticité

- une information authentique T ou MI - ou bien les distorsions E associées à des règles d’interprétation

explicites

Principe d’efficacité

- covisualisation de ces informations

Les représentations graphiques par projection non linéaire deviennent exploitablesLes projections non linéaires ne sont pas une fin en soi mais un moyen,

support contextuel graphique d’une l’information authentique supplémentaire| PAGE 45CEA | 11 JUILLET 2012



Paradigme WinSitu

MODELISATION TOPOLOGIQUE IN SITU

| PAGE 47

CEA | 10 AVRIL 2012




Représentation symboliqueApprentissage Automatique

Modèle topologique

subjectif

Modélisation topologique in situ


Modèle descriptif multidimensionnel





Graphe de Delaunay





41

7 2

24

7

Synthèse de la connexitéGraphe des classes

1 sommet par composante

connexe

1 arête entre 2 sommets initialement connectés



-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3-2

-1.5

-1

-0.5

0

0.5

1

1.5

2

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3-2

-1.5

-1

-0.5

0

0.5

1

1.5

2

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3-2

-1.5

-1

-0.5

0

0.5

1

1.5

2

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3-2

-1.5

-1

-0.5

0

0.5

1

1.5

2

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3-2

-1.5

-1

-0.5

0

0.5

1

1.5

2

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3-2

-1.5

-1

-0.5

0

0.5

1

1.5

2

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3-2

-1.5

-1

-0.5

0

0.5

1

1.5

2

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3-2

-1.5

-1

-0.5

0

0.5

1

1.5

2

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3-2

-1.5

-1

-0.5

0

0.5

1

1.5

2

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3-2

-1.5

-1

-0.5

0

0.5

1

1.5

2

Modèle topologique objectif

Sélection de modèle par Bayesian Information Criterion


Modèle génératif multidimensionnel

)jc(p

)j(p

),jx(p

c

j

)jc(p)jc(p

)j(p)j(p

01

01

Jj

)c,x(p ),jx(p )jc(p)j(pMaximisation

de la vraisemblance

Comment définir un modèle génératif

basé sur des points et des segments ?

Point Gaussien

2

2

22

22

)Ax(

exp)(),Ax(pDA

Segment Gaussien AB

dv),vx(p),ABx(p

A

B

peut être exprimée à l’aide de la fonction « erf »



Application données Oil Flow


Graphe de classes issu du GGG

1 groupe

GTM GTM + ProxiViz


Question Réponse

2 groupes? 1 groupe


Application données Oil Flow



ACPACP locale

Graphe de classes issu du GGG

1 groupe?

2 groupes

2 groupes

Question Réponse

Application données Teapot 365 images de 192 pixels (1 donnée = 1 point en 192 dimensions)

d’une théière en rotation. Retrait de 10 images pour former 2 variétés linéiques


Application données Teapot 365 images de 192 pixels (1 donnée = 1 point en 192 dimensions)

d’une théière en rotation. Retrait de 10 images pour former 2 variétés linéiques


2 composantes connexes

N*0 = 67 Projection du graphe GGG par ACP Projection des images par ACP

Apprentissage semi-supervisé avec le GGG

Probabilité d’appartenance à la classe rouge ou bleue

en chaque sommet wdu GGG

P(rouge|w) = 1

P(rouge|w) = 0

Sans propagation

Modèle de densitéfourni par le GGG

Graphe pondéré par la densitépour la propagation des classes

Avec propagation

2 individus étiquetés, l’un de classe bleue (en bas), l’autre de classe rouge (en haut)

P(rouge|w) = 0.5 P(bleue|w) = 0.5

P(bleue|w) = 1

P(bleue|w) = 0


Avantage : Sélection de modèle avec BIC et toutes les données au lieu de validation croisée sur peu de données étiquetées

PERSPECTIVES

| PAGE 62

CEA | 10 AVRIL 2012

PERSPECTIVES

Visualisation in situ

Topologie et distorsions- Formaliser la distinction entre

étirements/déchirures et compression/recollement

- Validation du principe de fiabilité : Déchirures préférables aux recollements

ProxiViz interactifParcours exploratoireOutils d’assistance visuelle à la modélisation topologiquePassage à l’échelle, synthétiser l’information en multi-échelle

Formaliser l’interprétabilitéTransmission du sens

Critère d’authenticitéReprésentation graphique du fond plutôt que de la forme


Full text Schema Full visualization

What could we do here to ease inference

from graphics

???

Aide à l’interprétation des graphiquesM

ech

anic

sP

rob

abili

stic

m

od

els

Info

Vis

http://en.wikipedia.org/wiki/File:HiddenMarkovModel.svg

PERSPECTIVES

Visualisation in situ

Extension à d’autres types de données (arbres, graphes, signaux…)Extension à d’autres types de représentation (TreeMap, Coordonnées Parallèles, SOM…)

Autres applicationsClassiMap


[Vesanto99]

[Rousset & Guinot 2001]

PERSPECTIVES

Modélisation in situ

Extension aux complexes simpliciaux (GGSC) pour extraire les nombres de Betti

Gérer la complexité de calculDelaunay ou pasPertinence du critère BIC pour la sélection de modèleFonction de densité linéaire par morceaux (plutôt que constante)


1-cycle which can contract to a point

Red and brown 1-cycles cannot collapse

to each otherThey form a homology group,

the rank of which is 2(b1=2)

1-cycles which cannot contract to a point

(b0,b1,b2)= (1,2,1)# of connected components# of independent 1-cycles (tunnels)# of independent 2-cycles (cavities)

Nombres de Betti

PERSPECTIVES

Persistence Topologique

PERSPECTIVES

Modélisation in situ

Encoder les nombres de Betti dans le graphe des classesEntrelacement, inclusion [Egenhofer 1994]Visualisation complémentaire avec ProxiViz sur le graphe des classes

Structures multi-échelleComment intégrer l’approche persistence topologique avec des critères statistiques, lien avec modèles bayésiens

Autres types de données (réseaux sociaux) Co-clustering topologique

comment détecter les sous-groupes indépendants de variables dépendantes

Passage à l’échelle pour traiter des masses de donnéesLien avec l’IA symbolique

Similarité entre Complexes simpliciaux et treillis de concepts


PERSPECTIVES

Futurs possibles

Traiter des masses de données (Big Data)Agents explorateurs et exploration visuelle de

l’état de l’explorationGrammaire des compositions graphiques

interprétables pour rendre de plus en plus transparente l’IHM (pianiste virtuose faisant corps avec son piano) accroître la surface de contact

Topologie au cœur des réseauxSociaux, neuronaux, biologiques, numériques,

transport, sémantiqueSynthétiser l’information topologique pour

supprimer l’effet pelote de liens


PERSPECTIVES

Futurs possibles

Des machines conscientesL’internet des objets (objets, bâtiments, véhicules)Objets autonomes quelle réaction des humains?Besoin de contrôle de l’état cognitif des ces

machines (ce qu’elles perçoivent et ce qu’elles veulent faire, pathologies des machines conscientes…)

Assurer et rassurer le propriétaire humainConcevoir dès le départ la machine pour que ses

états mentaux soient interprétables et modifiables par les personnes habilitées (Robopsychologues d’Asimov « Menteur !» 1941)

CONCLUSION

| PAGE 71

CEA | 10 AVRIL 2012

CONCLUSION

Je suis convaincu que la topologie est au cœur de nos processus cognitifs et forme le substrat sur lequel se bâtit notre relation au monde

J’ai engagé l’exploration de cette hypothèse

Je compte poursuivre cette exploration et en exploiter les résultats pour concevoir des machines intelligente en mesure de nous assister et dont nous puissions conserver la maîtrise


ProxiVizCheckVizWinSitu

GGGSGGGSSGGG

Merci de votre attention

Technology

Soutenance hdr aupetit_2012