Upload
vukhanh
View
217
Download
0
Embed Size (px)
Citation preview
CNAM Paris - RCP209 25/09/2013
M. Crucianu 1
25/09/2013 RCP209 1
Cours : Michel Crucianu (PU)Fouad Badran (PU)MezianeYacoub (MCF)Marin Ferecatu (MCF)
TP : Meziane Yacoub
http://idf.pleiad.net/index.php
Apprentissage, réseaux de neurones et modèles graphiques
25/09/2013 RCP209 2
Objectifs de l’enseignement
Méthodes décisionnelles basées sur l’apprentissage à partir des données : réseaux de neurones, Machines à Vecteurs Supports (SVM), méthodes (réseaux) graphiques ; leur utilisation dans desapplications réelles
Suite de l’UE RCP208 « Reconnaissance des formes et réseaux de neurones »
→ Fouille de données (data mining) : recherche de régularités ou de relations inconnues a priori dans de grands volumes de données
→ Reconnaissance des formes (pattern recognition) = (sens strict) identifier à quelle catégorie appartient une « forme » décrite par des données brutes
CNAM Paris - RCP209 25/09/2013
M. Crucianu 2
25/09/2013 RCP209 3
Contenu de l’ensemble du cours
Estimation de fonctions de densité (2, MC)
Cartes auto-organisatrices appliquées aux données quantitatives,
catégorielles et mixtes (2, MY)
Perceptrons multicouches : fonctions d’erreur, maximum de
vraisemblance, modèle multi-expert (1, MY)
Apprentissage, généralisation, régularisation (1 MY, 1 MC)
Machines à vecteurs supports (SVM), ingénierie des noyaux (2, MF)
Chaînes de Markov cachées (2, FB)
Introduction aux réseaux bayesiens (2, FB)
25/09/2013 RCP209 4
Travaux pratiques (TP)
ContenuEstimation de fonctions de densitéCartes auto-organisatrices appliquées aux données quantitatives, catégorielles et mixtesPerceptrons multicouchesMachines à vecteurs supports, ingénierie des noyauxTravail suivi sur le mini-projet
Logiciel privilégié : Matlab (http://www.mathworks.fr) ou, comme alternative gratuite, Octave (http://www.gnu.org/software/octave/)
D’autres solutions sont envisageables, suivant les préférences et les disponibilités des auditeurs
Weka (Java) : http://sourceforge.net/projects/weka/Divers logiciels statistiques
CNAM Paris - RCP209 25/09/2013
M. Crucianu 3
25/09/2013 RCP209 5
Évaluation
Note finale : moyenne entre
Examen final
Mini-projets réalisés en partie durant les TP (juin + septembre)Sujets proposés courant avril, choix arrêtés fin avril
3 étapesCompréhension du problème (fin mai)
Analyse des données (fin juin)
Finalisation du projet et envoi d’un bref mémoire (septembre)
25/09/2013 RCP209 6
Bibliographie générale
Dreyfus, G., J. Martinez, M. Samuelides, M. Gordon, F. Badran, S. Thiria, Apprentissage statistique : Réseaux de neurones - Cartes topologiques - Machines à vecteurs supports. Éditions Eyrolles, 2008.
Hand D. J., H. Mannila, P. Smyth. Principles of Data Mining. MIT Press, 2001.
Hastie T., R. Tibshirani, J. H. Friedman. The Elements of StatisticalLearning. Springer, 2003.
Naïm P., P.-H. Wuillemin, Ph. Leray, O. Pourret, A. Becker. Réseaux bayesiens. Eyrolles, 2004.
Schölkopf B., A. Smola. Learning with Kernels. MIT Press, 2002.
CNAM Paris - RCP209 25/09/2013
M. Crucianu 4
25/09/2013 RCP209 7
Michel Crucianu(avec contributions de Jean-Philippe Tarel)
http://cedric.cnam.fr/~crucianm/ml.html
Apprentissage, réseaux de neurones et modèles graphiques
Chapitre 1 : Estimation de fonctions de densité
25/09/2013 RCP209 8
Estimation de fonctions de densité
Objectif : à partir d’observations, estimer la loi qui les a généréesSoit un ensemble d’observations dansL’observation est une réalisation de la variable aléatoireOn considère que les variables sont indépendantes et identiquement distribuées (i.i.d.) suivant la densité de probabilité et on cherche à estimer cette densité à partir des observationsNotation : la valeur de dans sera notée
A quoi sert l’estimation de fonctions de densité ?Mettre en évidence des régularités présentes dans les donnéesDécision bayesienne – approche générative : modéliser et, avec , obtenir les probabilités a posteriori
{ }nxx ,,1 K=D
X∈x
X
( )xjcP( )jcP( )jcp x
iXix
( )xp
( )Xf,,,1, niX i K=
( )Xf
CNAM Paris - RCP209 25/09/2013
M. Crucianu 5
25/09/2013 RCP209 9
Méthodes d’estimation de densités
Non paramétriques : absence d’hypothèses sur les lois1. Estimation par histogramme
2. Méthode des noyaux de Parzen
3. Méthode des kn plus proches voisins (non abordée dans la suite)
Paramétriques : hypothèses sur la nature des lois (appartenance à une famille paramétrée) → estimation des paramètres de ces lois
Maximisation de la vraisemblance
Maximisation de l’a posteriori
Modèles de mélanges
Algorithme Expectation-Maximization (EM)
EM appliqué aux mélanges gaussiens
25/09/2013 RCP209 10
Estimation par histogramme
Sans hypothèses sur les lois qui régissent
Principe de l’estimation : (n obs. au total, k dans v )
Division de l’espace en volumes v, comptage des observations v fixé, n augmente : l’estimation s’améliore (la variance diminue), mais représente une moyenne sur vn fixé, v diminue : la précision par rapport à x s’améliore, mais la qualité d’estimation se dégrade (la variance augmente)
Conditions nécessaires :
(précision)
(estimation)
(estimation)
( )xp
( )vnkf ≅xˆ
0lim =∞→ nn
v
∞=∞→ nn
klim
0lim =∞→
nknn
nv23=n
observationsk = 5
k = 2
CNAM Paris - RCP209 25/09/2013
M. Crucianu 6
25/09/2013 RCP209 11
Exemple : loi uniforme, v = 1/10
n = 20 n = 2 000n = 200
n = 20 000 n = 200 000 n = 2 000 000
25/09/2013 RCP209 12
Exemple : loi uniforme, n = 2 000
v = 1/10 v = 1/40v = 1/20
v = 1/80 v = 1/160 v = 1/320
CNAM Paris - RCP209 25/09/2013
M. Crucianu 7
25/09/2013 RCP209 13
Exemple d’application
Détection de la chaussée
(source : J.-Ph. Tarel, LCPC)
25/09/2013 RCP209 14
Considérons d’abord des (hyper)cubes de coté (et dimension d )Définissons une première fonction-fenêtre (ou noyau)
( étant la composante j de )
Densité autour de ?
→ Pour l’hypercube
Le volume est
Le nombre d’observations situées à l’intérieur est
Méthode des fenêtres de Parzen
( )⎩⎨⎧ <∀
=ϕ sinon 0
21 , si 1 juju
nh
1=⎟⎠
⎞⎜⎝
⎛ −ϕ
n
i
hxx
dnn hv =
∑=
⎟⎠
⎞⎜⎝
⎛ −ϕ=
n
i n
in h
k1
xx
ϕ
(d = 2)
x+observations
nh
nhnv
x
ju u
CNAM Paris - RCP209 25/09/2013
M. Crucianu 8
25/09/2013 RCP209 15
Méthode des fenêtres de Parzen (2)
→L’estimateur sera alors
qui possède (« largeur » de la fenêtre) comme seul paramètre
( ) ∑=
⎟⎠
⎞⎜⎝
⎛ −ϕ=
n
i n
idn
n hhnf
1
1ˆ xxx
nh
→ résultat global : somme des fenêtres centrées sur les observations !
( ) ⎟⎠
⎞⎜⎝
⎛ =n
nn v
nkf xˆ
25/09/2013 RCP209 16
Méthode des fenêtres de Parzen (3)
Conditions suffisantes pour que l’estimateur soit lui-même une densité :
L’approche peut être généralisée en considérant d’autres noyaux :
Normal (gaussien) :
Cauchy :
Exponentiel :
Triangulaire :
( ) dR∈∀≥ϕ uu ,0
( ) 1=ϕ∫d
dR
uu
( )( )
uuu
T
ed21
221 −
π=ϕ
( ) ( )uuu T+π
=ϕ1
1
( ) ( ) uu −=ϕ e21
( ) { }uu −=ϕ 1,0max-5 -4 -3 -2 -1 0 1 2 3 4 5
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
-5 -4 -3 -2 -1 0 1 2 3 4 50.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
CNAM Paris - RCP209 25/09/2013
M. Crucianu 9
25/09/2013 RCP209 17
Fenêtres de Parzen : exemple
Densités obtenues avec un échantillon de 5 vecteurs de et des noyaux gaussiens d’écart-types 2 (gauche), 1 (centre) et 0,5 (droite)
La « largeur » du noyau a plus d’impact que le type de noyau !Choix de la largeur : nombreuses méthodes, dont la validation croisée
[Duda, Hart, Stork, 2001]
2R
25/09/2013 RCP209 18
Fenêtres de Parzen : convergence
Conditions de convergence :continue dans
( est bornée)
et (par ex. , )
Nature de la convergence :
Moyenne :
Variance :
( )xp x
( ) ∞<ϕ uu
sup ( )uϕ
( ) 0lim =ϕ∞→
uuu
d
0lim =∞→ nn
h 0lim =∞→
dnn
hn
( ) ( )xx ppnn=
∞→lim
( ) 0lim 2 =σ∞→
xnn
nhhn 0= nhhn ln0=
CNAM Paris - RCP209 25/09/2013
M. Crucianu 10
25/09/2013 RCP209 19
Estimation paramétrique
On considère que la densité recherchée appartient à une famille paramétrée par des vecteurs et on indique cette dépendance en écrivant au lieu de
L’échantillon étant issu de variables i.i.d., nous pouvons écrire
Comme fonction de , est la vraisemblance (likelihood) de par rapport à l’échantillon
Il est en général plus facile de travailler avec le logarithme de la vraisemblance (log-likelihood)
( )θxpΩ∈θ
( )xp
D( ) ( )∏
=
=n
iipp
1
θxθD
( )θDpθθ D
( ) ( )[ ] ( )[ ]∑=
=≡n
iippl
1lnln θxθθ D
25/09/2013 RCP209 20
Un cas simple : loi normale 1D
Considérons le cas suivant :
La famille paramétrée candidate est celle des lois normales ,
donc
R=X( )μ,σN
[ ] Tσμ=θ
échantillon
densitéscandidates
R
0 μ
( )θDp
( )θl μ
( fixé)σ
CNAM Paris - RCP209 25/09/2013
M. Crucianu 11
25/09/2013 RCP209 21
Maximum de vraisemblance (MV)
L’estimation la plus en accord avec les observations est celle qui correspond au maximum de la vraisemblance Le logarithme en base e étant une fonction monotone croissante, le maximum de la vraisemblance est atteint pour le même que le maximum de Exemple : pour le cas normal unidimensionnel considéré,
donc en dérivant on obtient
( )θDpθ̂ D
θ̂( )θl
( ) ( )[ ] ( )∑∑==
⎥⎦⎤
⎢⎣⎡ μ−
σ−πσ−==
n
ii
n
ii xxpp
1
22
1 212lnlnln θθD
( )[ ]( )∑
∑=
= μ−σ
=μ∂
∂ n
ii
n
i ix
xp
12
1 1ln θ
( )[ ]( )∑
∑=
= μ−σ
+σ
−=σ∂
∂ n
ii
n
i ixnxp
1
23
1 1ln θ
25/09/2013 RCP209 22
Maximum de vraisemblance (2)
Les dérivées partielles sont nulles
et
pouret
(on vérifie que la solution correspond bien à un maximum)Remarques :
L’estimation pour est non biaisée (son espérance sur tous les échantillons de taille n est égale à la vraie valeur de )L’estimation de est en revanche biaisée (mais asymptotiquement non biaisée) ; une estimation non biaisée est
( )xxn
n
ii ==μ ∑
=1
1ˆ
( ) 0ˆˆ1
12 =μ−
σ ∑=
n
iix ( ) 0ˆ
ˆ1
ˆ 1
23 =μ−
σ+
σ− ∑
=
n
iixn
( )∑=
μ−=σn
iix
n 1
22 ˆ1ˆ
μμ
2σ
( )∑=
μ−−
=σn
iix
n 1
22 ˆ1
1ˆ
CNAM Paris - RCP209 25/09/2013
M. Crucianu 12
25/09/2013 RCP209 23
Explication du biais
La moyenne d’un échantillon est une variable aléatoire
d’espérance et de variance
La variance d’un échantillon est une variable aléatoire d’espérance
or , donc
et
par conséquent,
∑=
=n
iix
nx
1
1
( ) ( )XExE = ( ) ( )XVn
xV 1=
( )∑=
−=n
ii xx
nv
1
21
( ) ( ) ( ) ( ) ( )222
1
2
1
2 11 xExExExn
Exxn
EvE i
n
ii
n
ii −=−⎟
⎠
⎞⎜⎝
⎛=⎟
⎠
⎞⎜⎝
⎛−= ∑∑
==
( ) ( ) ( )XVXExE i += 22( ) ( ) ( )22iii xExExV −=
( ) ( ) ( ) ( ) ( ) ( )XVnXExVxExE 1222 +=+=
( ) ( ) ( ) ( ) ( ) ( ) ( )( )XVXVn
nXVn
XEXVXEvE ≠−
=−−+=1122
25/09/2013 RCP209 24
Exemple 2 – lois normales multidimensionnelles :
La famille paramétrée candidate est celle des lois normales
Dans ce cas, le maximum de la vraisemblance est donné par
et
Ici encore, l’estimation de est non biaisée mais celle de lamatrice de variances-covariances est biaisée (simplement asymptotiquement non biaisée) ; une estimation non biaisée est
Maximum de vraisemblance (3)
dR=X( )Σμ,N
∑=
=n
iin 1
1ˆ xμ ( )( )∑=
−−=n
i
Tiin 1
ˆˆ1ˆ μxμxΣ
μΣ
( )( )∑=
−−−
=n
i
Tiin 1
ˆˆ1
1ˆ μxμxΣ
( )( )
)()(21
2
1
21 μ−Σμ−− −
Σπ=θ
xx
d
T
exp
CNAM Paris - RCP209 25/09/2013
M. Crucianu 13
25/09/2013 RCP209 25
Maximum a posteriori (MAP)
Si on connaît la densité de probabilité a priori pour , , il est préférable de choisir la solution qui maximise la probabilité a posteriori ( ) ( ) ( )θθθ ppp DD ∝
θ ( )θpθ̂
( )θp
θ
θ
( )θDp (comme fonction de ,non normalisée)
θ
θ
( )Dθp
25/09/2013 RCP209 26
Modèles de mélange
On s’intéresse à des densités de probabilité qui sont des mélanges additifs de plusieurs densités décrites par des lois élémentaires (par exemple, lois normales multidimensionnelles)
avecm : nombre de composantes du mélange
: densité qui définit une composante (supposée appartenir à une famille paramétrée par )
: coefficients de mélange tels que: représentation vectorielle des coefficients de mélange: vecteur qui représente tous les
( ) ( )∑=
α=m
jjjj pp
1, θxθαx
( )jjp θx
jαjθ
11
=α∑ =
m
j j
jθθα
CNAM Paris - RCP209 25/09/2013
M. Crucianu 14
25/09/2013 RCP209 27
Exemple d’application : compression
256 couleurs 128 couleurs 64 couleurs
(source : J.-Ph. Tarel, LCPC)
25/09/2013 RCP209 28
Exemple d’application : compression
32 couleurs
32 couleurs 16 couleurs 8 couleurs
(source : J.-Ph. Tarel, LCPC)
CNAM Paris - RCP209 25/09/2013
M. Crucianu 15
25/09/2013 RCP209 29
Modèles de mélange : estimation MV
On considère un ensemble d’observations de issues de variables i.i.d. suivant la densité de probabilitéOn cherche à trouver qui maximisent la vraisemblance
À partir de l’expression de , on obtient l’expression à maximiser (ici, le logarithme de la vraisemblance)
sous la contrainte
En raison de la présence d’une somme sous le logarithme, on ne peut pas obtenir de solution analytique à ce problème de maximisation, il faut donc avoir recours à des méthodes d’optimisation itérative pour déterminer
{ }nxx ,,1 K=D( )θαx ,p
dR
( )θα ˆ,ˆ
( ) ( )∏=
=n
iipp
1
,, θαxθαD
( )θαx ,p
( ) ( )∑ ∑= =
⎥⎦
⎤⎢⎣
⎡α=
n
i
m
jjijj pp
1 1
ln,ln θxθαD
( )θα ˆ,ˆ
11
=α∑ =
m
j j
25/09/2013 RCP209 30
Expectation-Maximization
Algorithme itératif, introduit dans [DLR77]Une solution au problème général de l’estimation MV des paramètres d’une distribution à partir de données incomplètes ouprésentant des valeurs manquantes
Pré-requis : considérons
est l’ensemble des données observées
correspond aux données manquantes
sera associé à , à et à
Données suivant la densité
z yx
( ) ( ) ( ) ( )( ) ( )θyθyx
θxθxyθyxθz
pp
pppp
,
,,
∝
∝=
oD
mD
{ }mo DDD ,=
oD mDD
CNAM Paris - RCP209 25/09/2013
M. Crucianu 16
25/09/2013 RCP209 31
Expectation-Maximization (2)
On cherche le paramètre qui maximise la vraisemblance
ou son logarithme
Question : comment maximiser la vraisemblance
quand les données sont manquantes ?
Si suit une densité , et on peut écrire
( ) ( ) ( ) ( ) ( )∫∫ ==yy
yθyyyθθ dpqdqpp ooo DDD lnlnln
( )θop Dln( )θop D
*θ
mD
( )θop D
( ) 1=∫y
yy dq( )yqY
( ) ( ) ( ) ( ) ( )[ ]∫ +−−∝y
yyyθyθyy dqqppq oo lnln,ln,ln DD
( ) ( )( )
( )
( ) ( )( )
( ) ( )( )4444 34444 214444 34444 21
θyy
y
θ
y
yθy
yyyy
θyy
,KL,
,ln
,ln
opq
o
ql
o dp
qqdq
pq
D
DD
∫∫ +=
( )q∀∀ ,θ
( ) ( ) ( )θθyθy ooo ppp DDD ,, ∝
25/09/2013 RCP209 32
Expectation-Maximization (3)
Comme ,
→ Algorithme EM :Initialisation : choix de Itérer
Étape E : calculer en considérant Étape M : identifier maximisant
jusqu’à la convergence
( ) ( )( ) 0,KL ≥θyy opq D ( ) ( )θθ ,ln qlp o ≥D
1+tθ
0θ
( )tql θ, ( ) ( )topq θyy ,D≈
( ) 1, +tql θ
( )tql θ,
( ) 1, −tql θ
2+tθ 1+tθtθ
( )θop Dln
θ
(inconnue !)
( )tql θ,
1−tθ
CNAM Paris - RCP209 25/09/2013
M. Crucianu 17
25/09/2013 RCP209 33
Expectation-Maximization (4)
Déterminer avec fixé à revient à calculer
Difficulté : présence en général d’extrema locaux vers lesquels l’algorithme peut converger (plutôt que vers un maximum global)
Types d’utilisations de EM :Valeurs et/ou variables manquantes dans les données (exemple : difficultés d’observation)Introduction de variables cachées, dont les valeurs manquent, permettant de simplifier l’expression de la vraisemblance ( au lieu de ) et donc la détermination d’un maximum( )θoDpln
( )θ,ql
( )[ ] ( )∫=y
yθyθy dpp too ,,ln DD
( ) ( )[ ]tomo
t pEQm
θθθθ ,,ln; DDDD=
( )θ,ql ( )yq ( )top θy ,D
25/09/2013 RCP209 34
EM pour modèles de mélange
Données manquantes si l’observation a été générée par la composante du mélangeLe vecteur des paramètres à identifier est dans ce cas
Le caractère i.i.d. des variables dont sont issues les observations
implique
et, pour une instance des données non observées,
Enfin, les valeurs manquantes étant dans un ensemble discret,
{ } { } jymyY inii =∈= ,,,1:1 K ix
j
⎥⎦⎤
⎢⎣⎡θα
( ) ( ) ( )∑ ∏∑ == ⎥⎦⎤
⎢⎣⎡=
y
n
itt
iin
i iitt yPypQ
11,,,,ln,;, θαxθαxθαθα
( ) ( )∑ ==
n
i iimo ypp1
,,ln,,ln θαxθαDD
( ) ( )∏ ==
n
itt
iitt yPP
1,,,, θαxθαy oD
( )nyy ,,1 K=y
CNAM Paris - RCP209 25/09/2013
M. Crucianu 18
25/09/2013 RCP209 35
EM pour modèles de mélange (2)
Par la définition des données manquantes,
Aussi, la distribution de la variable manquante est donnée par
Nous pouvons ainsi obtenir l’expression de , à maximiser par la méthode des multiplicateurs de Lagrange tenant compte de la contrainte
( ) ( )( )∑ =
α
α= m
jtjij
tj
tyiy
tytt
iip
pyP iii
1
,,θx
θxθαx
( )ttQ θαθα ,;,
( ) ( ) ( ) ( )iii yiyyiiiii pyPypyp θxθαθαxθαx α== ,,,,,
11
=α∑ =
m
j j
25/09/2013 RCP209 36
EM pour mélange gaussien
Considérons des composantes lois normales multidimensionnelles
Données manquantes : si l’observation a été générée par la composante du mélangeLogarithme de la vraisemblance totale ( correspond aux ) :
Espérance du logarithme de la vraisemblance :
{ } { } jymyY inii =∈= ,,,1:1 K ix
j
( ) ( ) ( )∑∑==
α==n
iyiyy
n
iiimo iii
pypp11
ln,,ln,,ln θxθαxθαDD
( ) ( ) ( )( )∑ ∏
∑∑ =
=
= α
α⎥⎦⎤
⎢⎣⎡ α=
y
n
i m
jtjij
tj
tyiy
tyn
i yiyytt
p
ppQ iii
iii 1
1
1ln,;,
θx
θxθxθαθα
( )( )
( ) ( )jjT
jepj
djjj
μxΣμx
ΣΣμx
−−− −
π=
1
21
21221,
jj Σμ ,θ
CNAM Paris - RCP209 25/09/2013
M. Crucianu 19
25/09/2013 RCP209 37
EM pour mélange gaussien (2)
Après quelques calculs on obtient
avec
Les équations de mise à jour résultantes sont
Exemples : [Akaho]
( )∑=
+ =αn
i
tti
tj jP
n 1
1 ,,1 θαx( )( )∑
∑=
=+ = n
itt
i
n
itt
iitj
jP
jP
1
11
,,
,,
θαx
θαxxμ
( )( )( )( )∑
∑=
=++
+−−
= n
itt
i
n
i
Ttji
tji
ttit
jjP
jP
1
111
1
,,
,,
θαx
μxμxθαxΣ
( ) ( ) ( ) ( )∑∑∑∑= == =
+α=m
j
n
ijij
tti
m
j
n
ij
tti
tt pjPjPQ1 11 1
ln,,ln,,,;, θxθαxθαxθαθα
( ) ( ) ( )∑ =αα=
m
ltlil
tl
tjij
tj
tti ppjP
1,, θxθxθαx
25/09/2013 RCP209 38
Exemple : 2 gaussiennes 2Daprès 1 itération
après 4 itérations
après > 5 itérations
[Akaho]
CNAM Paris - RCP209 25/09/2013
M. Crucianu 20
25/09/2013 RCP209 39
Exemple : données peu structurées
Résultats très différents obtenus avec 4 initialisations différentes[Akaho]
25/09/2013 RCP209 40
Mélanges et classification automatique
Si on considère que chaque composante d’un mélange représente un groupe (cluster), trouver les paramètres du modèle permet d’identifier les groupes ( sera affecté à la composante
) et de modéliser chaque groupeApproche CML (Classification Maximum Likelihood) : on introduit des vecteurs-indicateurs , avec si est généré par la composante et sinon (voir aussi [CG92])Centres mobiles et EM pour modèles de mélange :
Mélange de lois normales multidimensionnelles avec matrices de variances-covariances identité et si et seulement si est plus proche de
⇒ L’estimation des paramètres du modèle (seuls restent les ) se réduit à l’algorithme de classification par centres mobiles
( )θαx ˆ,ˆ,maxarg*ij
jPj =ix
iq 1=ijq0=ijq
ixj
,,1 jnj ∀=α
jμ
( ) 1ˆ,ˆ, =θαxijPix jμ
CNAM Paris - RCP209 25/09/2013
M. Crucianu 21
25/09/2013 RCP209 41
Choix du nombre de composantes
Difficulté : pour un modèle de mélange, le maximum de la vraisemblance augmente en général avec le nombre de composantes, la vraisemblance ne peut donc pas servir au choix du nombre de composantes (sélection de modèle)
Types de méthodes (voir la synthèse [OBM05]) : Tests d’hypothèses : inspirés par LRTS (likelihood ratio test statistic, ne s’applique pas tel quel) pour m composantes vs. m+1 composantesCritères d’information : pénaliser proportionnellement au nombre de paramètres (par exemple AIC, BIC)Évaluer le degré de séparation entre composantes (les composantes peu séparées seront fusionnées) : mesure d’entropie (par exemple[CS96]), critères issus de la classification floueModifications de EM (par exemple [FJ02]) pour estimer le nombre de composantes en même temps que les paramètres
25/09/2013 RCP209 42
Exemple : nombre de composantes
Nombre adéquat
Nom
bre
trop
élev
é ?
[Akaho]
Nom
bre
trop
faib
le ?
CNAM Paris - RCP209 25/09/2013
M. Crucianu 22
25/09/2013 RCP209 43
Paramétrique vs. non paramétrique
Avantages des méthodes paramétriques :Si les hypothèses sont valides, bonne estimation avec des échantillons de taille comparativement faibleAprès construction du modèle, faible coût de l’estimation de la densité en un point précis
Avantages des méthodes non paramétriques :Généralité due à l’absence d’hypothèses sur le nombre et les types de loisConvergence garantie vers la vraie densité… si l’échantillon estsuffisant !Paramètre unique… mais difficile à choisir ! De plus, une même valeur peut ne pas convenir à l’ensemble du domaine
25/09/2013 RCP209 44
Références
[Akaho] Akaho S. Applet mélange de gaussiennes. (actuellement sur http://cedric.cnam.fr/~crucianm/appletMixMod.html)
[CG92] G. Celeux, G. Govaert. A classification EM algorithm for clustering and twostochastic versions. Computational Statistics & Data Analysis, 14, 315-332, 1992.
[CS96] G. Celeux, G. Soromenho. An Entropy Criterion for Assessing the Number of Clusters in a Mixture Model. Classification Journal, vol. 13, pp. 195-212, 1996.
[DLR77] A. P. Dempster, N. M. Laird, D. B. Rubin. Maximum Likelihood fromIncomplete Data via the EM Algorithm. Journal of the Royal Statistical Society, Series B, vol. 39, 1:1-38, 1977.
[FJ02] Figueiredo, M. A. and Jain, A. K. 2002. Unsupervised Learning of Finite Mixture Models. IEEE Trans. Pattern Anal. Mach. Intell. 24, 3 (Mar. 2002), 381-396.
[OBM05] A. Oliveira-Brochado, F. V. Martins. Assessing the Number of Components in Mixture Models: a Review. FEP Working Papers 194, Universidade do Porto, 2005.