Upload
laure-weiss
View
103
Download
0
Embed Size (px)
Citation preview
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
2
PlanPlan
• Présentation du problème
• Sélection de variables
• Approche
• Méthodologie expérimentale
• Analyse des résultats
• Conclusion
3
CadreCadre
• Equipe CyberMove : Projet INRIA, Robotique autonome, Environnement non contrôlé, Programmation bayésienne.
• Projet Européen BIBA : Plausibilité biologique du modèle
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é
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
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 )
7
PlanPlan
• Présentation du problème
• Sélection de variables
• Approche
• Méthodologie expérimentale
• Analyse des résultats
• Conclusion
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]
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 :
10
Comparatif wrappers / filtersComparatif wrappers / filters
Wrappers Filters
Performances +Biais pris en compte
-
Vitesse - +
Théorie +/-Simplicité
+/-Explications
Spécificité - +
11
PlanPlan
• Présentation du problème
• Sélection de variables
• Approche
• Méthodologie expérimentale
• Analyse des résultats
• Conclusion
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
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)
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)
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)
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
∑θ
∑
17
PlanPlan
• Présentation du problème
• Sélection de variables
• Approche
• Méthodologie expérimentale
• Analyse des résultats
• Conclusion
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
19
ExpérimentationExpérimentation
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)
21
PlanPlan
• Présentation du problème
• Sélection de variables
• Approche
• Méthodologie expérimentale
• Analyse des résultats
• Conclusion
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
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)
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
25
ComparatifComparatif
Test FAXH AGWrapp AGXH MoCap
TpsCalc ++ -- --- + +++TxReco +++ ++ ++++ + +++NbVar - + - + paramètreExplication + + - + ++Paramètres - ++ - - --
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
27
PlanPlan
• Présentation du problème
• Sélection de variables
• Approche
• Méthodologie expérimentale
• Analyse des résultats
• Conclusion
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
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