Algorithme EM

student2
student2
dans Probabilités, théorie de la mesure
Bonjour,

En vue de l' examen qui arrive sous deux jours je m'aperçois ne pas du tout comprendre l'algorithme EM présenté de la manière suivante : http://www.lsta.upmc.fr/sangnier/files/5MS102/notes.pdf

Si $D_{\theta}$ représente la densité jointe du couple $(X,Y)$ je ne comprends pas ce que vient faire la v.a. $Z:=Y|X$ dans l'histoire.
Soit il y a un veritable bord... dans les notations soit je suis complètement largué.
En tout cas je ne syis pas fou et on voit apparaître du $D_{\theta*}(X,Y)$ ainsi que du $\dfrac{dD_{\theta}}{d(\mu \times \nu)}(X,Z)$ ce qui me perturbe beaucoup, il faut savoir si $D$ est la probabilité jointe correspondant au couple $(X,Y)$ ou au couple $(X,Z)$...

Si quelqu'un peut me débloquer ce serait très sympas....
https://snag.gy/p6uRZG.jpg

Réponses

  • reuns
    reuns
    EM c'est un algorithme de minimisation alternée.

    Minimisation alternée : si tu veux minimiser $\min_{W,H}\|WH-X\|^2$ ce n'est pas évident car c'est ni linéaire ni quadratique en $(W,H)$. Par contre c'est quadratique en $W$ et $H$ séparément, donc tu peux prendre un couple $(W,H)$ initial au hasard, puis résoudre $\min_{W}\|WH-X\|^2$ et $\min_{H}\|WH-X\|^2$ alternativement, jusqu'à converger vers un optimum local.

    Dans le cas du mélange de gaussiennes GMM, on cherche à maximiser la probabilité d'observer les $x_i$ étant donné notre modèle GMM, en supposant que le vecteur observé $x= (x_1,\ldots,x_n)$ est i.id. comme ça la log-probabilité devient une somme $\log P(x | \theta) = \sum_i \log P(x_i|\theta)$. Et notre modèle c'est que $P(X|\theta) = \sum_{j=1}^J P(Y_i = j |\theta) P(X | Y_i=j,\theta)$ où $j$ est la $j$-ème Gaussienne. Ce modèle ça veut juste dire que la pdf de $X$ c'est une somme de $j$ gaussiennes, et $\theta$ contient les $J$ moyennes et (matrices de) variances des gaussiennes ainsi que la PDF de $Y$.

    Normalement on devrait maximiser tout en même temps, mais ça sera compliqué et à part la descente de gradient on ne saura pas faire. On va plutôt utiliser un algorithme de minimisation alternée :

    - étant donné $\theta$ il est facile de choisir par quelle Gaussienne un $x_i$ a été tiré.

    - étant donné les $x_i$ qui ont été tirés par la $j$ème Gaussienne, il est facile d'estimer la moyenne et la variance de cette Gaussienne, et il est facile d'estimer $P(Y = j)$ pour chaque $j$.

    Au final ça donne ce qui est expliqué ici.

    Avec les notations de ton cours : quand on tire un $X$ avec le GMM, $Y$ c'est la loi qui dit par quelle Gaussienne on va tirer notre $X$, puis $(X | Y = j)$ c'est une loi Gaussienne $\mathcal{N}(\mu_j,\Sigma_j)$, et même si on n'observe que $X$ la vraie variable aléatoire "mélange de Gaussienne" c'est $(X,Y)$.
    Et dans notre algorithme de minimisation alternée, à chaque étape on va chercher par quelle Gaussienne notre $x_i$ observé a été tiré, donc on est en train de regarder la variable aléatoire $Z = Y|X$.
  • student2
    student2
    Merci beaucoup reuns. Le problème c' est que je ne comprends toujours pas en quoi ca p4ouve la coherence des notations: lorsque l' enseignant utilise la même lettre D pour la probabilité jointe de (X,Y) et de (X,Z) ca me pète à la figure...
  • student2
    student2
    Bon après maintes relectures je penses simplement que l'enseignant a mélangé les lettres et que $Z$ et $Y$ désignent la même chose...

    Quand on lit l'extrait on est confus car on dispose du couple $(X,Y)$ où
    - $X$ désigne la réalisation d'un mélange de gaussiennes
    - la variable (latente car inobservable?) $Y$ qui désigne la la distribution/proportion des classes/marginales gaussiennes impliquées dans le mélange gaussienn notée $P(Y=j)=\pi_j$ dans l'extrait.
    - $X|Y$ qui est une famille de variables aléatoires, tel que $X|Y=j \sim \cal{N}(x;\mu_j,\sigma_j)$ est la réalisation de l'une des gaussiennes impliquées dans le mélange
    - $Y|X=x$ qui désigne la va dont distribution de probabilité quantifie le degré d'appartenance/la vraissemblance a une classe donnée sachant que l'on se trouve en $X=x$. Si l'on disposait d'une estimation des paramètres on pourrait estimer les $Y$ par la "règle de Bayes" qui affecte la classe ayant la plus grande vraissemblance (ie) $argmax_jP(Y=j|X=x)$.
  • student2
    student2
    Voici une ébauche de ce que j'ai compris:

    Algorithme EM

    Comme toujours on souhaite maximiser la vraisemblance « marginale » (on verra pourquoi on l’appel comme cela lors de la reformulation du problème sous forme complétée) de ce qu’on observe ; soit X. L’objectif est donc de maximiser la log vraisemblance marginale !
    Mais la log-vraisemblance de nos observations issues de $X$ (qui est donné par un modèle de mélange) est compliquée à car fait intervenir une somme dans le log.
    L’astuce consiste à « reformuler/modéliser le problème » précédent en injectant des variables latentes. On fait ainsi apparaitre une densité jointe $f_{(X,Y)}$ dont la log vraisemblance nous donne une expression analytique beaucoup plus simple à maximiser pourvue que l’on connaisse nos variables latentes.
    On se dit donc que l’on pourrait maximiser cette log-vraisemblance jointe en estimant/approchant notre variable latente (à priorie inconnue). Mais comment approcher notre variable latente en usant un maximum des informations dont on dispose? Il suffit d’approcher $Y$ par son esperance conditionnellement/sachant $X$ (puisque l’on observe bien nos observations).
    L’objectif maintenant est donc de maximiser ,par rapport aux paramètres de la loi de mélange ( ie les proportions de chacune des gaussiennes ainsi que leur moyennes et variances) l’esperance conditionnelle (sachant X) de la log-vraisemblance jointe. On a là encore un problème assez complexe que l’on pourrait simplifier en procédant par itération !
    On remarque que le calcul de cette esperance conditionnelle nous ramène à chercher la probabilité conditionnelle $P(y_i=j| X=x_i)$.

    L’expression simple (par le théorème de Bayes) nous montre que cette quantité dépend des paramètres à priori inconnues aussi (ie les paramètres utiles pour définir notre modèle de mélange :) On se dit qu’il faut donc fixer des paramètres courants pour cette probabilité conditionnelle, tout en laissant la valeure des paramètres inchangées dans le reste de l’expression de l’esperance conditionnelle. On est donc en mesure de calculer ) l’esperance conditionnelle (sachant X) de la log-vraisemblance jointe après avoir fixer les paramètres courants. On obtient ainsi Q(theta,theta^t) fonction de theta (nos paramètres) , quantité que l’on maximisera par la suite pour obtenir nos paramètres à l’iteration t+1.

    Ainsi en combinant les deux astuces précédentes on arrive à l’algorithme EM
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 13

AzothLirone93pozzarssi +9 Invités