L'application Expectation Maximization à pièce Toss exemples

Question

J'ai auto-train d'étudier l'Expectation Maximization ces derniers temps, et moi-même attrapé quelques exemples simples dans le processus:

De : Il y a trois pièces $ c_0 $, $ c_1 $ et $ c_2 $ avec $ p_0 $, $ p_1 $ et $ p_2 $ la probabilité respective pour l'atterrissage sur la tête lorsque ballotté. $ $ Toss c_0. Si le résultat est le chef, lancer c_1 $ $ trois fois, sinon lancer c_2 $ $ trois fois. Les données observées produites par $ c_1 $ et $ c_2 $ est comme ceci: HHH, TTT, HHH, TTT, HHH. Les données cachées est le résultat de $ c_0 $. Estimez $ p_0 $, $ p_1 $ et $ p_2 $.

Et de : Il y a deux pièces $ C_A $ et $ C_B $ avec $ P_A $ et $ P_b $ étant la probabilité respective pour l'atterrissage sur la tête lorsque ballotté. Chaque tour, sélectionnez une pièce au hasard et toss dix fois; enregistrer les résultats. Les données observées sont les résultats de ces Toss fournis par deux pièces. Cependant, nous ne savons pas quelle pièce a été sélectionnée pour un tour particulier. Estimation $ P_A $ et $ P_b $.

Alors que je peux obtenir les calculs, je ne peux rapporter la façon dont ils sont résolus à la théorie d'origine EM. Plus précisément, au cours de l'étape M des deux exemples, je ne vois pas comment ils maximiser quoi que ce soit. Il semble juste qu'ils sont recalculant les paramètres et en quelque sorte, les nouveaux paramètres sont mieux que les anciens. De plus, les deux E-étapes ne regardent même pas semblables les uns aux autres, pour ne pas mentionner E-étape de la théorie originale.

Alors, comment faire exactement ces travaux exemples?

Answer 1

(Cette réponse utilise le deuxième lien que vous avez donné.)

$ \ newcommand {\ Comme} {\ text {L}} \ newcommand {\ e} {\ texte {e}} $ Rappel de la définition de la probabilité: $$ \ Comme [\ theta | X] = \ Pr [X | \ Theta] = \ sum_Z \ Pr [X, Z | \ Theta] $$ où dans notre cas $ \ theta = (\ theta_A, \ theta_B) $ sont les estimateurs de la probabilité que les pièces A et B, respectivement les têtes de terre, $ X = (X_1, \ dotsc, X_5) $ étant les résultats de nos expériences, composées chacune de 10 $ X_i $ flips et $ Z = (z_1, \ dotsc, Z_5) $ étant la pièce de monnaie utilisée dans chaque expérience.

Nous voulons trouver estimateur du maximum de vraisemblance $ \ hat {\ theta} $. Le Expectation-Maximisation algorithme (EM) est une telle méthode pour trouver (au moins local) $ \ hat {\ theta} $. Ça marche en trouvant l'espérance conditionnelle, qui est ensuite utilisé pour maximiser $ \ theta $. L'idée est qu'en trouvant toujours un plus probable (à savoir plus probable) $ \ theta $ à chaque itération, nous allons augmenter sans cesse $ \ Pr [X, Z | \ theta $] qui, à son tour, augmente la fonction de vraisemblance. Il y a trois choses qui doivent être faites avant d'aller de l'avant la conception d'un algorithme EM.

1. Construire le modèle
2. Calculer l'espérance conditionnelle dans le cadre du modèle (étape E)
3. Maximisez nos chances en mettant à jour notre estimation actuelle de $ \ theta $ (M-Step)

Construire le modèle

Avant d'aller plus loin avec EM nous avons besoin de savoir exactement ce qu'il nous est informatique. Dans l'étape E, nous calculons exactement la valeur attendue pour $ \ log \ Pr [X, Z | \ theta] $. Alors, quelle est cette valeur, vraiment? Observe ceci $$ \ begin {align *} \ Log \ Pr [X, Z | \ theta] & = \ {sum_ i = 1} ^ 5 \ log \ sum_ {C \ in \ {A, B \}} \ Pr [X_i, Z_I = C | \ Theta] \\ & = \ {Sum_ i = 1} ^ 5 \ log \ sum_ {C \ in \ {A, B \}} \ Pr [Z_I = C | X_i, \ theta] \ cdot \ frac {\ Pr [X_i, Z_I = C | \ Theta]} {\ Pr [Z_I = C | X_i, \ theta]} \\ & \ Geq \ {sum_ i = 1} ^ 5 \ sum_ {C \ in \ {A, B \}} \ Pr [Z_I = C | X_i, \ theta] \ cdot \ log \ frac {\ Pr [X_i, Z_I = C | \ Theta]} {\ Pr [Z_I = C | X_i, \ theta]}. \ End {align *} $$ La raison est que nous avons 5 expériences pour expliquer, et nous ne savons pas quelle pièce a été utilisé dans chacun. L'inégalité est due à $ \ log $ étant concave et l'application de l'inégalité de Jensen. La raison pour laquelle nous avons besoin que la limite inférieure est que nous ne pouvons pas calculer directement la arg max à l'équation d'origine. Cependant, nous pouvons calculer pour la limite inférieure finale.

Maintenant, quelle est $ \ Pr [Z_I = C | X_i, \ theta] $? Il est la probabilité que l'on voit COÍN $ C $ donnée expérience $ X_i $ et $ \ theta $. En utilisant des probabilités conditionnelles nous avons, $$ \ Pr [Z_I = C | X_i, \ theta] = \ frac {\ Pr [X_i, Z_I = C | \ theta]} {\ Pr [X_i | \ theta]}. $$

Alors que nous avons fait des progrès, nous ne sommes pas fait avec le modèle pour l'instant. Quelle est la probabilité qu'une pièce de monnaie donnée retournée la séquence $ X_i $? Laisser $ h_i = \ # \ texte {} têtes dans X_i $ $$ \ Pr [X_i, Z_I = C | \ Theta] = \ Frac {1} {2} \ cdot \ ^ {theta_C h_i} (1 - \ theta_C) ^. {10 - h_i}, \ \ texte {for} \ C \ in \ {A, B \} $$ Maintenant $ \ Pr [X_i | \ theta] $ est clairement que la probabilité dans les deux possibilités de $ Z_I = A $ ou $ Z_I = B $. Depuis $ \ Pr [Z_I = A] = \ Pr [Z_I = B] = 1/2 $ que nous avons, $$ \ Pr [X_i | \ theta] = 1/2 \ cdot (\ Pr [X_i | Z_I = A, \ theta] + \ Pr [X_i | Z_I = B, \ theta]). $$

E-Step

D'accord ... qui n'a pas été tellement amusant, mais nous pouvons commencer à faire un travail EM maintenant. L'algorithme EM commence en faisant une estimation aléatoire pour $ \ theta $. Dans cet exemple, nous avons $ \ theta ^ 0 = (0.6,0.5) $. nous calculons $$ \ Pr [z_1 = A | X_1, \ theta] = \ frac {1/2 \ cdot (0,6 ^ 5 \ cdot 0,4 ^ 5)} {1/2 \ cdot ((0,6 ^ 5 \ cdot 0,4 ^ 5 ) + (0,5 ^ 5 \ cdot 0,5 ^ 5))} \ environ 0,45. $$ Ces lignes de valeur avec ce qui est dans le document. Maintenant, nous pouvons calculer le nombre attendu de têtes dans X_1 $ = (H, T, T, T, H, H, T, H, T, H) à partir de $ $ A $ pièce, $$ \ E [\ # \ texte {} têtes par pièce A | X_1, \ theta] = h-1 \ cdot \ Pr [z_1 = A |. X_1, \ theta] = 5 \ cdot 0,45 \ environ 2,2 $$ Faire la même chose pour pièce $ B $ que nous obtenons, $$ \ E [\ # \ texte {têtes par pièce} B | X_1, \ theta] = h-1 \ cdot \ Pr [z_1 = B |. X_1, \ theta] = 5 \ cdot 0,55 \ environ 2,8 $$ Nous pouvons calculer la même chose pour le nombre de queues par les sous-marinstituting $ $ pour 10 h-1 $ - $ h_1. Cela continue pour toutes les autres valeurs de $ X_i $ et h_i $ $ $ 1 \ leq i \ leq 5 $. Merci à la linéarité de l'attente, nous pouvons comprendre $$ \ E [\ # \ texte {} têtes par pièce A | X, \ theta] = \ {sum_ i = 1} ^ 5 \ E [\ # \ texte {têtes par pièce} A | X_i, \ theta] $$

M-Step

Avec nos valeurs attendues en main, vient maintenant l'étape M où nous voulons maximiser $ \ Theta $ compte tenu de nos valeurs attendues. Cela se fait par simple normalisation! $$ \ theta_A ^ 1 = \ frac {E [\ # \ texte {} têtes sur X \ texte {} par pièce A | X, \ theta]} {E [\ # \ texte {têtes et queues sur} X \ texte {} par pièce A |. X, \ theta]} = \ frac {} {21,3 21,3 + 9,6} \ environ 0,71 $$ De même pour $ B $. Ce processus commence à nouveau avec le E-Step et $ \ theta $ ^ 1 et continue jusqu'à ce que les valeurs pour $ \ theta $ Converge (ou à un seuil alloweable). Dans cet exemple, nous avons 10 itérations et $ \ hat {\ theta} = \ theta ^ {10} = (0,8, 0,52) $. Dans chaque itération la valeur de $ \ Pr [X, Z | \ theta]. $ Augmente, en raison de la meilleure estimation de $ \ theta $

Dans ce cas, le modèle est assez simpliste. Les choses peuvent être bien plus compliquée assez rapidement, mais l'algorithme EM sera toujours converger, et sera toujours produit un estimateur de probabilité maxmimum $ \ hat {\ theta} $. Il peut être un locale estimateur, mais contourner ce que nous pouvons simplement relancer le processus EM avec une initialisation différente. nous peut faire une quantité constante de temps et de retenir les meilleurs résultats (à savoir, ceux qui ont le plus forte probabilité finale).