Anwenden von Expectation Maximization auf Beispiele für Münzwürfe

Ich habe in letzter Zeit die Expectation Maximization selbst studiert und mir dabei einige einfache Beispiele geschnappt:

Ab hier : Es gibt drei Münzen , und mit , und der jeweiligen Wahrscheinlichkeit, auf dem Kopf zu landen, wenn sie geworfen werden. Werfen Sie . Wenn das Ergebnis Head ist, wirf dreimal, andernfalls wirf dreimal. Die beobachteten Daten, die von und sind wie folgt: HHH, TTT, HHH, TTT, HHH. Die versteckten Daten sind das Ergebnis von . Schätzen Sie , und .$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$

Und von hier : Es gibt zwei Münzen und wobei und die jeweilige Wahrscheinlichkeit für die Landung auf dem Kopf sind, wenn sie geworfen werden. Wähle in jeder Runde eine Münze nach dem Zufallsprinzip und wirf sie zehnmal. Notieren Sie die Ergebnisse. Die beobachteten Daten sind die Wurfergebnisse dieser beiden Münzen. Wir wissen jedoch nicht, welche Münze für eine bestimmte Runde ausgewählt wurde. Schätzen Sie und .$c_A$$c_B$$p_A$$p_B$$p_A$$p_B$

Obwohl ich die Berechnungen erhalten kann, kann ich die Art und Weise, wie sie gelöst werden, nicht mit der ursprünglichen EM-Theorie in Beziehung setzen. Insbesondere sehe ich während des M-Schritts in beiden Beispielen nicht, wie sie etwas maximieren. Es scheint nur, dass sie die Parameter neu berechnen, und irgendwie sind die neuen Parameter besser als die alten. Darüber hinaus sehen sich die beiden E-Steps nicht einmal ähnlich, ganz zu schweigen vom E-Step der ursprünglichen Theorie.

Wie genau funktionieren diese Beispiele?

(Diese Antwort verwendet den zweiten von Ihnen angegebenen Link.)

$\newcommand{\Like}{\text{L}}\newcommand{\E}{\text{E}}$ Erinnern Sie sich an die Definition der Wahrscheinlichkeit: , wo in unserem Fall sind die Schätzer für die Wahrscheinlichkeit , dass Münzen A und B jeweils Landköpfe, , um die Ergebnisse unserer Experimente wobei jeder besteht aus 10 Flips und ist die in jedem Experiment verwendete Münze.θ = ( θ A , θ B ) X = ( X 1 , ... , X 5 ) X i Z = ( Z 1 , ... , Z 5

$$\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)$

Wir wollen den Maximum-Likelihood-Schätzer . Der Expectation-Maximization (EM) -Algorithmus ist eine solche Methode, um (zumindest lokal) . Es funktioniert, indem es die bedingte Erwartung findet, die dann verwendet wird, um zu maximieren . Die Idee ist, dass wir durch kontinuierliches Finden eines wahrscheinlicheren (dh wahrscheinlicheren) in jeder Iteration kontinuierlich erhöhen, was wiederum die Wahrscheinlichkeitsfunktion erhöht. Vor dem Entwurf eines EM-basierten Algorithmus müssen drei Schritte ausgeführt werden. & thgr; & thgr;& thgr;Pr[X,Z| θ$\hat{\theta}$$\hat{\theta}$$\theta$$\theta$$\Pr[X,Z|\theta]$

1. Konstruieren Sie das Modell
2. Bedingte Erwartung unter dem Modell berechnen (E-Step)
3. Maximieren Sie unsere Wahrscheinlichkeit, indem Sie unsere aktuelle Schätzung von (M-Step) aktualisieren.$\theta$

Konstruieren Sie das Modell

Bevor wir mit EM weitermachen, müssen wir herausfinden, was genau wir berechnen. Im E-Schritt berechnen wir genau den erwarteten Wert für . Also, was ist dieser Wert wirklich? Beachten Sie, dass Der Grund dafür ist, dass wir 5 Experimente durchführen müssen und nicht wissen, welche Münzen in den einzelnen verwendet wurden. Die Ungleichung ist auflog 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$konkav sein und Jensens Ungleichung anwenden. Der Grund, warum wir diese Untergrenze brauchen, ist, dass wir das arg max nicht direkt mit der ursprünglichen Gleichung berechnen können. Wir können es jedoch für die letzte Untergrenze berechnen.

Was ist nun ? Es ist die Wahrscheinlichkeit, dass wir bei Experiment und Münze . Mit bedingten Wahrscheinlichkeiten haben wirC X i & thgr ; 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]}.$$

Obwohl wir einige Fortschritte erzielt haben, sind wir mit dem Modell noch nicht fertig. Mit welcher Wahrscheinlichkeit hat eine bestimmte Münze die Sequenz ? Lassen Sie Jetzt ist eindeutig nur die Wahrscheinlichkeit , unter den beiden Möglichkeiten der oder . Da ist, ist h i = # Köpfe in  X i Pr [ X i , Z i = C | θ ] = $X_i$$h_i = \#\text{heads in } X_i$

$$\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

Okay ... das hat nicht so viel Spaß gemacht, aber wir können jetzt mit der EM-Arbeit beginnen. Der EM-Algorithmus beginnt mit einer zufälligen Schätzung für . In diesem Beispiel haben wir . Wir berechnen Dieser Wert stimmt mit dem überein, was in der Zeitung steht. Jetzt können wir die erwartete Anzahl von Köpfen in aus Münze , berechnen Tun wir dasselbe für Münze , $\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$ $$\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.$$ Wir können dasselbe für die Anzahl der Schwänze berechnen, indem wir durch ersetzen . Dies wird für alle anderen Werte von und fortgesetzt . Dank der Linearität der Erwartung können wir herausfinden, $h_1$$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

Mit unseren erwarteten Werten kommt nun der M-Schritt, bei dem wir unter Berücksichtigung unserer erwarteten Werte maximieren möchten . Dies geschieht durch einfache Normalisierung! Das gleiche gilt für . Dieser Prozess beginnt erneut mit dem E-Schritt und thgr; und setzt sich fort, bis die Werte für thgr; konvergieren (oder bis zu einem zulässigen Schwellenwert). In diesem Beispiel haben wir 10 Iterationen und . Bei jeder Iteration steigt der Wert von aufgrund der besseren Schätzung von$\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$ .

In diesem Fall war das Modell ziemlich simpel. Die Dinge können ziemlich schnell viel komplizierter werden, jedoch wird der EM-Algorithmus immer konvergieren und wird immer einen Schätzer für die maximale Wahrscheinlichkeit erzeugen . Es kann ein lokaler Schätzer sein, aber um dies zu umgehen, können wir den EM-Prozess einfach mit einer anderen Initialisierung neu starten. Wir können dies eine konstante Anzahl von Malen tun und die besten Ergebnisse beibehalten (dh diejenigen mit der höchsten endgültigen Wahrscheinlichkeit).$\hat{\theta}$