29
1 Vers la découverte de nouvelles Vers la découverte de nouvelles modalités sensori-motrices. modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Pierre Dangauthier Dangauthier DEA I.V.R. 24 Juin 2003 Sélection Automatique Sélection Automatique de Variables de Variables Pertinentes Pertinentes

1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

Embed Size (px)

Citation preview

Page 1: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

1

Vers la découverte de nouvelles Vers la découverte de nouvelles modalités sensori-motrices.modalités sensori-motrices.

Encadrants : Pierre BessièreAnne Spalanzani

Pierre DangauthierPierre DangauthierDEA I.V.R.

24 Juin 2003

Sélection Automatique de Sélection Automatique de Variables PertinentesVariables Pertinentes

Sélection Automatique de Sélection Automatique de Variables PertinentesVariables Pertinentes

Page 2: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

2

PlanPlan

• Présentation du problème

• Sélection de variables

• Approche

• Méthodologie expérimentale

• Analyse des résultats

• Conclusion

Page 3: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

3

CadreCadre

• Equipe CyberMove : Projet INRIA, Robotique autonome, Environnement non contrôlé, Programmation bayésienne.

• Projet Européen BIBA : Plausibilité biologique du modèle

Page 4: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

4

ObjectifsObjectifs

• Automatiser la découverte de nouvelles modalités sensori-motrices

• Trouver des relations entre variables

• Exemples Robot BIBA

• Laser ultrasons

Balle Rouge• Vision capteur de proximité

Page 5: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

5

De la balle rouge au cube vertDe la balle rouge au cube vert

• 59 variables : 16 proximètres, 16 photomètres, vitesse et position des roues, position caméra, variables internes…

Découverte d’une nouvelle modalité sensorielle

Page 6: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

6

ContexteContexte

• Programmation bayésienne des robots [Lebeltel03]

Description

Question

Spécification

Identification

et Proximètres : X9 … X24

Formes paramétriques

Variables pertinentes

Décomposition

P (X9 ... X24 ,θ ) = P (θ ) P (X i θ )i= 9

24

∏Modèle capteur

Histogrammes de Laplace

TC

TxXP kii xX

kii +

+== = ,

1)( ,

ArgMaxθ P(θ X9 ... X24 )

Page 7: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

7

PlanPlan

• Présentation du problème

• Sélection de variables

• Approche

• Méthodologie expérimentale

• Analyse des résultats

• Conclusion

Page 8: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

8

Sélection de variablesSélection de variables

Critère d’arrêtNon

ValidationOui

Sous-ensembleretenu

Un sous-ensemble

EvaluationExplorationde l’espace

Classificateur

ApprentissageCalcul TauxReco

[LiuYu02]

[Kohavi94]

Notion de corrélation

[Hall98]

Page 9: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

9

Évaluer un sous-ensembleÉvaluer un sous-ensemble

• Evaluation variable par variable Feature ranking : insuffisant [Guyon03]

• Evaluation sous-ensemble Formule de Ghiselli [Ghi64]

ji

iS

rkkk

rkr

,

,,

)1( −+=

)()(

),(2

YHXH

YXICIS

+=

H(X) = − P(X)log P(X)X

∑∑−=X Y YPXP

YXPYXPYXI )

)()(

),(log(),(),(

[Kullback51]

DKL ( p1, p2) = p1(x)logp1(x)

p2(x)x

• Evaluation de corrélationStatistique du 2

X-H :

Page 10: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

10

Comparatif wrappers / filtersComparatif wrappers / filters

Wrappers Filters

Performances +Biais pris en compte

-

Vitesse - +

Théorie +/-Simplicité

+/-Explications

Spécificité - +

Page 11: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

11

PlanPlan

• Présentation du problème

• Sélection de variables

• Approche

• Méthodologie expérimentale

• Analyse des résultats

• Conclusion

Page 12: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

12

4 Algorithmes simples 4 Algorithmes simples

• Rank XH et Rank2

Type : filter Complexité :

• Test2 Type : filter : Test statistique Complexité : N calcul de p-valeur +

• Wrappers exhaustifs Type : wrapper avec k=N (et k=N/2)

Complexité :

O(NC2)

O(2N TC)€

O(NC2)

Légende: N = #Variables k = #Variables retenues C = #Valeurs T = #Exemples G = #Générations I = #Individus

Page 13: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

13

FAXH et FA2FAXH et FA2

• Type : filters• Exploration: Forward addition [Koller96]

• Évaluation : Ghiselli + CIS ou statistique du 2

• Critère d’arrêt : fin de croissance des scores

• Complexité :

O(N 3C2)

Page 14: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

14

AGWrapAGWrap

• Type : wrapper• Exploration: Algorithme génétique

[Spalanzani99]

• Évaluation : taux de reconnaissance [Yang98]

• Critère d’arrêt : Nombre de générations

• Complexité :

O(G.I.T.C.k)

Page 15: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

15

AGXHAGXH

• Type : filter

• Exploration : Algorithme génétique

• Évaluation : Ghiselli + CIS

• Critère d’arrêt : Nombre de générations

• Complexité :• [Hall98]

O(G.I.T.C.k)

Page 16: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

16

MoCapMoCap

• Type : filter• Exploration : Backward Elimination [Koller96]

• Critère d’arrêt : nombre de variables

• Complexité : • Évaluation : KL-distance symétrisée modèle capteur

O(N 2C2)

Δ( p1, p2) = DKL ( p1, p2) + DKL (p2, p1)

P (X0 ... XN−1 ,θ ) = P (θ ) P (X i θ )i= 0

N−1

Pj (X0 ... XN−1 ,θ ) = P (θ ) P (X j ) P (X i θ )i= 0i≠ j

N−1

Δ(P,Pj ) = P(θ) log[P(X j )

P(X j θ)] −[P(X j ) − P(X j θ)]

X j

∑θ

Page 17: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

17

PlanPlan

• Présentation du problème

• Sélection de variables

• Approche

• Méthodologie expérimentale

• Analyse des résultats

• Conclusion

Page 18: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

18

Méthodologie de testMéthodologie de test

• Provenance des données Simulateur logiciel : maîtrise Robot Koala

• Critères de comparaison NbVar, TxReco, TpsCalc, Pouvoir explicatif, #paramètres.

• Protocole expérimental 11 fichiers de données et 11 fichiers de test pour validation Résultats bruts et moyenne

• Liste des expériences 7 expériences simples pour tests et 4 réalistes

Page 19: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

19

ExpérimentationExpérimentation

Page 20: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

20

Méthodologie de testMéthodologie de test

• Provenance des données Simulateur logiciel : maîtrise Robot Koala

• Critères de comparaison NbVar, TxReco, TpsCalc, Pouvoir explicatif, #paramètres.

• Protocole expérimental 11 fichiers de données et 11 fichiers de test pour validation Résultats bruts et moyenne

• Liste des expériences 7 expériences simples pour tests et 4 réalistes (dont 2 du robot)

Page 21: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

21

PlanPlan

• Présentation du problème

• Sélection de variables

• Approche

• Méthodologie expérimentale

• Analyse des résultats

• Conclusion

Page 22: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

22

Résultats 1/3Résultats 1/3Fichier Critère Test EX EXN2 FAXH FA AGWrapp AGXH MoCap ALL

1 NbVar 2 1 1 2 2 2 1 1 2TxReco 1 1 1 1 1 1 1 1 1

2t TpsCalc 0,0017 0,27 0,14 0,0028 0,0026 2,7 0,31 0,0029 0,00142 NbVar 1 1 2 1 1 3 1 2 4

TxReco 1 1 1 1 1 1 0,18 1 1t3b TpsCalc 0,0016 2,05 0,72 0,0035 0,0031 3,9 0,18 0,0031 0,00243 NbVar 4 9 5 8 1 11 8 5 11

TxReco 0,56 0,79 0,62 0,76 0,24 0,81 0,79 0,62 0,818p3b TpsCalc 0,0043 664 236 0,14 0,0072 13 0,42 0,0089 0,006

4 NbVar 9 13 8 16 1 12 15 8 16TxReco 0,74 64 0,57 0,77 0,25 0,81 0,78 0,65 0,77

8p8p TpsCalc 0,0098 15000 2000 0,72 0,012 13 0,49 0,018 0,015 NbVar 13 9 8 8 1 14 8 8 16

TxReco 0,93 0,91 0,9 0,9 0,32 0,93 0,88 0,9 0,928p8l TpsCalc 0,01 17000 3000 0,34 0,012 14 0,33 0,015 0,0088

6 NbVar 15 9 1 11 9 11 23TxReco 0,91 0,9 0,5 0,93 0,86 0,92 0,89

l23 TpsCalc 0,012 0,55 0,014 15 0,39 0,024 0,0127 NbVar 2 2 1 4 2 2 5

TxReco 0,94 0,94 0,58 0,95 0,68 0,94 0,942s3b TpsCalc 0,0022 0,0077 0,0037 4,8 0,18 0,0036 0,003

8 NbVar 5 2 1 6 2 9 19TxReco 0,81 0,83 0,78 0,81 0,37 0,78 0,74

19s TpsCalc 0,0063 0,028 0,011 7,5 0,25 0,018 0,019 NbVar 8 5 1 10 5 11 23

TxReco 0,79 0,8 0,42 0,82 0,79 0,78 0,7423l TpsCalc 0,0088 0,16 0,014 12 0,32 0,023 0,01310 NbVar 45 15 1 35 15 29 58

TxReco 0,19 0,25 0,05 0,33 0,25 0,27 0,19rob1 TpsCalc 2,8 390 2,1 1500 19 2,6 1,211 NbVar 45 15 1 37 15 29 58

TxReco 0,89 0,8 0,4 0,91 0,8 0,87 0,89rob2 TpsCalc 3,1 535 3,4 3000 29,4 1,03 1,3

2

2

Page 23: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

23

Résultats 2/3Résultats 2/3

% AGWrapp AGXH FAXH FA2  Test2 ModCap ALL

NbVar 52 25 25 3 59 41 100

TxReco 106 87 102 64 104 103 100

TpsCalc 2273 23 401 3 2 1 1

Moyennes sur les fichiers d’exemples réalistes (N> 20)

• Wrappers : trop lents• FA2 : termine trop tôt• Test2 : garde trop de variables• FAXH : trop lent si N grand (N3)

Page 24: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

24

Résultats 3/3Résultats 3/3

• AGXH et MoCap

% AGXH ModCap     ModCap     ModCap8

NbVar 25 41 23 26

TxReco 87 103 99 97

TpsCalc 23 1 1 1

• Avec un même k, MoCap est plus performant et beaucoup plus rapide• Mais problème d’autonomie

N2

N4

Page 25: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

25

ComparatifComparatif

Test FAXH AGWrapp AGXH MoCap

TpsCalc ++ -- --- + +++TxReco +++ ++ ++++ + +++NbVar - + - + paramètreExplication + + - + ++Paramètres - ++ - - --

Page 26: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

26

Retour sur la balle rougeRetour sur la balle rouge

• AGXH, FAXH et ModCapN/4 sont équivalents

• FAXH lent

• Problème de MoCap (critère d'arrêt)

• ==> AGXH le mieux adapté

AGXH FAXH AGWrapp MoCapN/4 ALL

Proximètres (sur 16) 6 7 13 6 16Autres capteurs (sur 42) 9 8 24 8 42TxReco 0,8 0,8 0,91 0,76 0,89

Page 27: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

27

PlanPlan

• Présentation du problème

• Sélection de variables

• Approche

• Méthodologie expérimentale

• Analyse des résultats

• Conclusion

Page 28: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

28

ContributionContribution

• Un premier pas vers la découverte automatique de nouvelles modalités sensori-motrices

• Proposition de plusieurs algorithmes de « feature selection »

• Comparaison méthodique dans le cadre de robotique autonome

Page 29: 1 Vers la découverte de nouvelles modalités sensori-motrices. Encadrants : Pierre Bessière Anne Spalanzani Pierre Dangauthier DEA I.V.R. 24 Juin 2003 Sélection

29

PerspectivesPerspectives

• Perspectives techniques Autre critère d’arrêt pour MoCap Variables continues

• Un deuxième pas vers la découverte de nouvelles modalités Période de recherche Corrélations dans le domaine moteur