Zastosowanie maksymalizacji oczekiwań do przykładów rzutu monetą

Ostatnio studiowałem samemu Maksymalizację oczekiwań i w tym czasie zdobyłem kilka prostych przykładów:

Od tutaj : Istnieją trzy monety $c_0$ , i z , i odpowiednie prawdopodobieństwa do lądowania na głowie, kiedy rzucił. Rzuć . Jeśli wynikiem jest Głowa, rzuć trzy razy, w przeciwnym razie rzuć trzy razy. Obserwowane dane wytworzone przez i są następujące: HHH, TTT, HHH, TTT, HHH. Ukryte dane są wynikiem . Oszacuj , i .$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$

I stąd : Istnieją dwie monety i przy czym i są odpowiednim prawdopodobieństwem wylądowania na Głowie po rzuceniu. W każdej rundzie wybierz losowo jedną monetę i rzuć nią dziesięć razy; zapisz wyniki. Zaobserwowane dane to wyniki losowania tych dwóch monet. Nie wiemy jednak, która moneta została wybrana w danej rundzie. Oszacuj i .$c_A$$c_B$$p_A$$p_B$$p_A$$p_B$

Chociaż mogę uzyskać obliczenia, nie mogę powiązać sposobów ich rozwiązania z pierwotną teorią EM. W szczególności podczas kroku M obu przykładów nie widzę, jak coś maksymalizują. Wygląda na to, że ponownie obliczają parametry i nowe parametry są lepsze od starych. Co więcej, dwa E-Kroki nawet nie wyglądają podobnie, nie wspominając już o E-Kroku z oryginalnej teorii.

Jak dokładnie działają te przykłady?

(Ta odpowiedź używa drugiego podanego linku).

$\newcommand{\Like}{\text{L}}\newcommand{\E}{\text{E}}$ Przywołaj definicję prawdopodobieństwa: gdzie w naszym przypadku są estymatorami prawdopodobieństwa, że ​​monety odpowiednio A i B wylądują, jest naszych eksperymentów, każdy składający się z 10 rzutów, a jest monetą używaną w każdym eksperymencie.

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

Chcemy znaleźć estymator największego prawdopodobieństwa . Algorytm Expectation-Maximization (EM) jest jedną z takich metod znalezienia (przynajmniej lokalnego) . Działa poprzez znalezienie warunkowego oczekiwania, które jest następnie wykorzystywane do maksymalizacji . Chodzi o to, że stale znajdując bardziej prawdopodobne (tj. Bardziej prawdopodobne) w każdej iteracji, będziemy stale zwiększać co z kolei zwiększa funkcję prawdopodobieństwa. Istnieją trzy rzeczy, które należy zrobić, zanim przystąpisz do projektowania algorytmu opartego na EM.$\hat{\theta}$$\hat{\theta}$$\theta$$\theta$$\Pr[X,Z|\theta]$

1. Skonstruuj model
2. Oblicz oczekiwanie warunkowe w ramach modelu (E-Step)
3. Zmaksymalizuj nasze prawdopodobieństwo, aktualizując nasze aktualne oszacowanie (M-Step)$\theta$

Zbuduj model

Zanim przejdziemy dalej z EM, musimy dowiedzieć się, co dokładnie obliczamy. W kroku E obliczamy dokładnie oczekiwaną wartość dla . Jaka jest więc ta wartość? Zauważ, że Powodem jest to, że mamy na koncie 5 eksperymentów i nie wiemy, jaką monetę użyto w każdym z nich. Nierówność wynika 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$bycie wklęsłym i stosowanie nierówności Jensena. Powodem, dla którego potrzebujemy tej dolnej granicy, jest to, że nie możemy bezpośrednio obliczyć argmax do pierwotnego równania. Możemy to jednak obliczyć dla końcowej dolnej granicy.

Co to jest ? Jest prawdopodobieństwo, że zobaczymy monetę biorąc pod uwagę eksperyment i . Korzystając z prawdopodobieństw warunkowych, mamy$\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]}.$$

Chociaż poczyniliśmy pewne postępy, jeszcze nie skończyliśmy z modelem. Jakie jest prawdopodobieństwo, że dana moneta przerzuci sekwencję ? Pozwalając Teraz jest wyraźnie tylko prawdopodobieństwo pod obiema możliwościami lub . Ponieważ mamy, $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

Okej ... to nie było takie fajne, ale teraz możemy zacząć pracę nad EM. Algorytm EM zaczyna się od losowego odgadnięcia dla . W tym przykładzie mamy . Obliczamy Ta wartość jest zgodna z zawartością papieru. Teraz możemy obliczyć oczekiwaną liczbę głów w z monety , Robiąc to samo dla monety otrzymujemy, $\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.$$ Możemy to samo obliczyć dla liczby ogonów, podstawiając na . Dotyczy to wszystkich innych wartości i . Dzięki liniowości oczekiwań możemy dowiedzieć się $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

Z naszymi oczekiwanymi wartościami nadchodzi teraz krok M, w którym chcemy zmaksymalizować biorąc pod uwagę nasze oczekiwane wartości. Odbywa się to poprzez zwykłą normalizację! Podobnie jest w przypadku . Proces ten zaczyna się od E-Step i i trwa do momentu, aż wartości dla zbiegną się (lub osiągną dopuszczalny próg). W tym przykładzie mamy 10 iteracji i . W każdej iteracji wartość rośnie, ze względu na lepsze oszacowanie$\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$ .

Teraz w tym przypadku model był dość uproszczony. Sprawy mogą się znacznie skomplikować dość szybko, jednak algorytm EM zawsze będzie zbieżny i zawsze da maksymalne prawdopodobieństwo estymatora . Może to być lokalny estymator, ale aby obejść ten problem, możemy po prostu zrestartować proces EM z inną inicjalizacją. Możemy to zrobić stałą ilość razy i zachować najlepsze wyniki (tj. Te o najwyższym prawdopodobieństwie końcowym).$\hat{\theta}$