Cherche exercice pour apprendre Espérance-Maximisation

Invité · 02/07/2010, 17h48

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.

**pseudocode** · 02/07/2010, 22h27

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.

Invité · 03/07/2010, 07h50

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)

**pseudocode** · 03/07/2010, 11h57

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

algorithme Expectation-maximization (EM)

Invité · 05/07/2010, 14h05

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 ?

**pseudocode** · 05/07/2010, 18h57

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

Invité · 06/07/2010, 12h06

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 Java :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**pseudocode** · 06/07/2010, 15h30

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

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

Invité · 06/07/2010, 16h04

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 ?

**pseudocode** · 06/07/2010, 16h07

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.

Invité · 06/07/2010, 17h07

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 Java :

Sélectionner tout - Visualiser dans une fenêtre à part

			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 ?

**pseudocode** · 06/07/2010, 18h14

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.