Application de la maximisation des attentes aux exemples de lancer de pièces

J'ai auto-étudié la maximisation des attentes récemment et je me suis emparé de quelques exemples simples dans le processus:

De là : Il y a trois pièces , et avec , et la probabilité respective d'atterrir sur la tête lorsqu'elle est lancée. Toss . Si le résultat est Tête, lancez trois fois, sinon lancez trois fois. Les données observées produites par et sont les suivantes: HHH, TTT, HHH, TTT, HHH. Les données cachées sont le résultat de . Estimez , et .c 1 c 2 p 0 p 1 p 2 c 0 c 1 c 2 c 1 c 2 c 0 p 0 p 1 p $c_0$$c_1$$c_2$$p_0$$p_1$$p_2$$c_0$$c_1$$c_2$$c_1$$c_2$$c_0$$p_0$$p_1$$p_2$

Et à partir d' ici : Il y a deux pièces et avec et étant la probabilité respective d'atterrir sur la tête lorsqu'elle est lancée. Chaque tour, sélectionnez une pièce au hasard et lancez-la dix fois; enregistrer les résultats. Les données observées sont les résultats du tirage fournis par ces deux pièces. Cependant, nous ne savons pas quelle pièce a été sélectionnée pour un tour particulier. Estimation et .$c_A$$c_B$$p_A$$p_B$$p_A$$p_B$

Bien que je puisse obtenir les calculs, je ne peux pas relier les façons dont ils sont résolus à la théorie EM originale. Plus précisément, pendant l'étape M des deux exemples, je ne vois pas comment ils maximisent quoi que ce soit. Il semble juste qu'ils recalculent les paramètres et d'une manière ou d'une autre, les nouveaux paramètres sont meilleurs que les anciens. De plus, les deux étapes E ne se ressemblent même pas, sans parler de l'étape E de la théorie originale.

Alors, comment fonctionnent exactement ces exemples?

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

$\newcommand{\Like}{\text{L}}\newcommand{\E}{\text{E}}$θ = ( θ A , θ B

$$\Like[\theta | X] = \Pr[X| \theta] = \sum_Z \Pr[X, Z | \theta]$$ $\theta = (\theta_A, \theta_B)$$X = (X_1, \dotsc, X_5)$$X_i$$Z = (Z_1, \dotsc, Z_5)$

Nous voulons trouver l'estimateur du maximum de vraisemblance . L'algorithme Expectation-Maximization (EM) est une de ces méthodes pour trouver (au moins local) . Il fonctionne en trouvant l'espérance conditionnelle, qui est ensuite utilisée pour maximiser . L'idée est qu'en trouvant continuellement un plus probable (c'est-à-dire plus probable) à chaque itération, nous augmenterons continuellement qui à son tour, augmentera la fonction de vraisemblance. Il y a trois choses à faire avant de continuer à concevoir un algorithme basé sur EM.$\hat{\theta}$$\hat{\theta}$$\theta$$\theta$$\Pr[X,Z|\theta]$

1. Construire le modèle
2. Calcul des attentes conditionnelles sous le modèle (E-Step)
3. Maximisez notre probabilité en mettant à jour notre estimation actuelle de (étape M)$\theta$

Construire le modèle

Avant d'aller plus loin avec EM, nous devons déterminer ce que nous calculons exactement. Dans l'étape E, nous calculons exactement la valeur attendue pour . Alors, quelle est vraiment cette valeur? Observez que La raison en est que nous avons 5 expériences à prendre en compte, et nous ne savons pas quelle pièce a été utilisée dans chacune. L'inégalité est due àlog Pr [ X , Z | θ $\log \Pr[X,Z|\theta]$

$$\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*}$$ $\log$être concave et appliquer l'inégalité de Jensen. La raison pour laquelle nous avons besoin de cette borne inférieure est que nous ne pouvons pas calculer directement l'arg max à l'équation d'origine. Cependant, nous pouvons le calculer pour la borne inférieure finale.

Maintenant, qu'est-ce que ? C'est la probabilité que nous voyions la pièce expérience et . En utilisant les probabilités conditionnelles, nous avons,C X i θ Pr [ Z i = C | X i , θ ] = Pr [ X i , Z i = C | θ $\Pr[Z_i=C|X_i,\theta]$$C$$X_i$$\theta$

$$\Pr[Z_i=C| X_i, \theta] = \frac{\Pr[X_i, Z_i = C|\theta]}{\Pr[X_i|\theta]}.$$

Bien que nous ayons fait quelques progrès, nous n'en avons pas encore fini avec le modèle. Quelle est la probabilité qu'une pièce donnée retourne la séquence ? Laisser Maintenant est clairement que la probabilité dans les deux possibilités de ou . Puisque nous avons, h i = # têtes dans  X i Pr [ X i , Z i = C | θ ] = $X_i$$h_i = \#\text{heads in } X_i$ Pr[Xi| θ]Zi=AZi=BPr[Zi=A]=Pr[Zi=B]=1/

$$\Pr[X_i, Z_i = C| \theta] = \frac{1}{2} \cdot \theta_C^{h_i} (1 - \theta_C)^{10 - h_i},\ \text{ for } \ C \in \{A, B\}.$$ $\Pr[X_i|\theta]$$Z_i=A$$Z_i=B$$\Pr[Z_i = A] = \Pr[Z_i = B] = 1/2$ $$\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 ... ce n'était pas si amusant, mais nous pouvons commencer à faire du travail EM maintenant. L'algorithme EM commence par faire une supposition aléatoire pour . Dans cet exemple, nous avons . Nous calculons Cette valeur correspond à ce qui est dans le papier. Maintenant, nous pouvons calculer le nombre attendu de têtes dans partir de la pièce , Faire la même chose pour la pièce nous obtenons, θ 0 = ( 0,6 , 0,5 ) Pr [ Z 1 = A | X 1 , θ ] = 1 / deux ⋅ ( 0,6 5 ⋅ 0,4 5$\theta$$\theta^0 = (0.6,0.5)$

$$\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))} \approx 0.45.$$ $X_1 = (H,T,T,T,H,H,T,H,T,H)$$A$B E [ # têtes par pièce  B | X 1 , θ ] = h 1 ⋅ Pr [ Z 1 = B | X 1 , θ ] = 5 ⋅ 0,55 ≈ 2,8. h 1 $$\E[\# \text{heads by coin }A | X_1, \theta] = h_1 \cdot \Pr[Z_1=A|X_1,\theta] = 5 \cdot 0.45 \approx 2.2.$$ $B$ $$\E[\# \text{heads by coin }B | X_1, \theta] = h_1 \cdot \Pr[Z_1=B|X_1,\theta] = 5 \cdot 0.55 \approx 2.8.$$ Nous pouvons calculer la même chose pour le nombre de queues en substituant à . Cela continue pour toutes les autres valeurs de et . Grâce à la linéarité des attentes, nous pouvons comprendre $h_1$X i h i 1 ≤ i ≤ 5 E [ # têtes par pièce  A | X , θ ] = 5 ∑ i = 1 E [ # têtes par pièce  A | X i , θ $10 - h_1$$X_i$$h_i$ $1 \leq i \leq 5$ $$\E[\#\text{heads by coin } A|X ,\theta] = \sum_{i=1}^5 \E[\# \text{heads by coin }A | X_i, \theta]$$

M-Step

Avec nos valeurs attendues en main, vient maintenant l'étape M où nous voulons maximiser compte tenu de nos valeurs attendues. Cela se fait par simple normalisation! De même pour . Ce processus recommence avec l'E-Step et et continue jusqu'à ce que les valeurs de convergent (ou jusqu'à un certain seuil autorisé). Dans cet exemple, nous avons 10 itérations et . À chaque itération, la valeur de augmente, en raison de la meilleure estimation deθ 1 A = E [ # se dirige vers  X  avec la pièce  A | X , θ $\theta$

$$\theta_A^1 = \frac{E[\#\text{heads over } X \text{ by coin } A|X ,\theta]}{E[\#\text{heads and tails over } X \text{ by coin } A|X ,\theta]} = \frac{21.3}{21.3 + 9.6} \approx 0.71.$$ $B$$\theta^1$$\theta$$\hat{\theta} = \theta^{10} = (0.8, 0.52)$$\Pr[X,Z|\theta]$$\theta$ .

Maintenant, dans ce cas, le modèle était assez simpliste. Les choses peuvent devenir beaucoup plus compliquées assez rapidement, mais l'algorithme EM convergera toujours et produira toujours un estimateur de vraisemblance maximum . Il peut s'agir d'un estimateur local , mais pour contourner ce problème, nous pouvons simplement redémarrer le processus EM avec une initialisation différente. Nous pouvons le faire un nombre de fois constant et conserver les meilleurs résultats (c'est-à-dire ceux avec la probabilité finale la plus élevée).$\hat{\theta}$