Cherche exercice pour apprendre Espérance-Maximisation

Bonjour,

Je cherche un exercice (réalisable en 1 ou 2 semaines par un débutant) pour me familiariser avec l'algorithme Espérance-Maximisation. Les données d'exemple seront générées par ordinateur, c'est plus simple.

Si quelqu'un connaît cet algo ainsi qu'un exercice de programmation typique pour l'assimiler, ça me serait très utile.

Merci d'avance pour votre aide.

Je dois dire que c'est une bonne question. J'ai beau utiliser cet algo, je ne suis toujours pas sûr d'avoir bien capté la théorie qui est derrière. :aie:

Oula ... il est si tordu que ça cet algo ? Tu l'utilises dans quel contexte ?

(je ne cherche pas à connaître la théorie qu'il y a derrière, juste à l'utiliser un peu pour voir en gros qu'est-ce que c'est)

Citation:

---

Envoyé par hellfoust

Oula ... il est si tordu que ça cet algo ? Tu l'utilises dans quel contexte ?

(je ne cherche pas à connaître la théorie qu'il y a derrière, juste à l'utiliser un peu pour voir en gros qu'est-ce que c'est)

---

Non l'algo n'est pas tordu, il est meme assez logique. Par contre j'ai plus de mal avec la démonstration de la convergence.

Je l'utilise pour trouver les parametres de lois de probabilités. J'ai un ensemble de données qui est généré a partir de deux (ou plus) lois, et j'essaie de retrouver les paramètres de ces lois. Ca me permet alors de classifier les données

Par exemple, les données sont générées comme ca:

Code:

---

1 2 3 4 5

Liste 1 = des valeurs de X telles que X = a1 + b1*randomgaussien() Liste 2 = des valeurs de Y telles que Y = a2 + b2*randomgaussien()   Ensemble de données E = des valeur tirées aléatoirement dans Liste1 ou Liste2

---

Donc je sais que dans E il y a des valeurs qui viennent de la liste1 et d'autres de la liste2. Mais je ne sais pas dire lesquels. Et je ne connais pas non plus a1,b1,a2 et b2. Tout ce que je connais c'est la forme des lois ( a+b*randomgaussien )

L'algo EM me permet de retrouver a1,a2,b1,b2 ainsi que la proportion des valeurs venant de la Liste1 et de la Liste2. Je peux alors dire pour chaque élément de E quelle est la probabilité qu'il vienne de Liste1 ou Liste2

Version en image :

:arrow: algorithme Expectation-maximization (EM)

Bonjour,

J'ai regardé le code java, et je ne comprend pas très bien à quoi correspond le tableau à deux dimension nommé "t". Il associe à chaque valeur d'exemple une probabilité, mais cette probabilité correspond à quoi ?

EDIT: à la probabilité d'avoir été générée par cette loi ?

Citation:

---

Envoyé par hellfoust

Bonjour,

J'ai regardé le code java, et je ne comprend pas très bien à quoi correspond le tableau à deux dimension nommé "t". Il associe à chaque valeur d'exemple une probabilité, mais cette probabilité correspond à quoi ?

EDIT: à la probabilité d'avoir été générée par cette loi ?

---

Oui c'est ca.

t[L][k] c'est la probabilité que la valeur Xk appartienne à la loi L

Bonjour,

Dans la partie maximisation, est-ce que c'est normal de rafraîchir la valeur de pi[i] avec la moyenne des probabilités que la loi ait générée la donnée ?

Ou bien est-ce une erreur de programmation et il faudrait rafraîchir pi[i] avec la multiplication de chacune des probabilités que la loi ait générée la donnée ?

Dans le premier cas, le tableau pi donne la moyenne des probabilités de chaque loi, dans le deuxième cas, il donne la vraisemblance de chaque loi.

Lignes de code en question dans l'étape de maximisation :

Code:

---

1 2 3

pi[k]=0; for(int i=0;i<N;i++) pi[k]+=t[k][i]; pi[k]/=N;

---

Hum... C'est ce dont je parlais quand je disais que démontrer la convergence n'était pas facile. :aie:


Le plus simple c'est de voir le tabealu t[][] comme une somme croisé dans un tableur:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

Law_1 Law2 Law3   X_1 : 70% 20% 10% --> somme = 100% X_2 : 20% 70% 10% --> somme = 100% X_3 : 50% 20% 30% --> somme = 100% X_4 : 10% 10% 80% --> somme = 100% ... ... ... ... X_N : ... ... ... \/ ----- ------ ------ ------ ------------ somme: N*pi_0 N*pi_1 N*pi_2 -> | N*100% | ------------

---

t[k][i] représente la probabilité que l'élément donnée X_i provienne de la Loi n°k.

Etant donné que X_i vient forcément d'une des lois, alors on a : somme_k{t[k][i]} = 1, pour chaque X_i. Et donc somme_i {somme_k{t[k][i]} } = somme_i { 1 } = N

La somme par "colonne" dans le tableau nous donne donc le "poids" (= la proportion) des éléments d'une loi dans le mélange. Et donc, en divisant par N, on trouve la valeur de pi

Ah ! Donc pi[i] c'est la proba qu'une valeur prise au hasard dans les exemples ait été générées par la i-ème loi ?

Citation:

---

Envoyé par hellfoust

Ah ! Donc pi[i] c'est la proba qu'une valeur prise au hasard dans les exemples ait été générées par la i-ème loi ?

---

Oui, on peut voir ca comme ça également.

Ok.

Un autre détail (un peu en dehors de l'algo) : toujours dans la maximisation, quand on calcule si la convergence est suffisante, on fait :

Code:

---

convergence+=(savedpi-pi[k])*(savedpi-pi[k]);

---

C'est bizarre de mettre au carré, car ça peut provoquer un résultat inattendu dans cette situation :

- il y a juste une loi qui a changée de 1e-6, c'est-à-dire que savedpi-pi[k] == 1e-6.

On est d'accord qu'il faut continuer les itérations car ce changement est bien supérieur au seuil fixé de 1e-10. Or il ne sera même pas détecté car il est mis au carré et 1e-6 * 1e-6 == 1e-12.

Ne vaut-il pas mieux prendre la valeur absolue ?

En fait, le seuil de convergence est de 1E-5. Mais, comme tu l'as remarqué, je calcule la SSD et donc il faut soit prendre la racine carré de la convergence, soit élever le seuil au carré (d'où le 1E-10).

Tu peux prendre une autre mesure de convergence si tu veux. La SSD n'est pas obligatoire.

Ok, j'ai laissé au carré.

J'ai fait une petite réécriture du code si tu veux voir.

Citation:

---

Envoyé par pseudocode

Oui c'est ca.

t[L][k] c'est la probabilité que la valeur Xk appartienne à la loi L

---

je cherche le code d'Algorithme espérance-maximisation Em sous matlab