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?

probability-theory statistics

— IcySnow
źródło

W pierwszym przykładzie, ile mamy przypadków tego samego eksperymentu? W drugim przykładzie, jakie jest prawo „losowego wybierania jednej monety”? Ile rund obserwujemy?

— Raphael

Pliki PDF, które podłączyłem, rozwiązują te dwa przykłady krok po kroku. Jednak tak naprawdę nie rozumiem zastosowanego algorytmu EM.

— IcySnow

@IcySnow, czy rozumiesz pojęcie oczekiwania i warunkowego oczekiwania zmiennej losowej?

— Nicholas Mancuso

Rozumiem podstawowe oczekiwanie zmiennej losowej i prawdopodobieństwo warunkowe. Nie znam jednak przewidywania warunkowego, jego pochodnej i wystarczającej statystyki.

— IcySnow,

(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.

L [θ | X] = Pr [X | θ] = \sum_{Z} Pr [X, Z | θ]

$\Like[\theta | X] = \Pr[X| \theta] = \sum_Z \Pr[X, Z | \theta]$

θ = (θ_{A}, θ_{B})

$\theta = (\theta_A, \theta_B)$

X = (X_{1}, \dots, X_{5})

$X = (X_1, \dotsc, X_5)$

X_{i}

$X_i$

Z = (Z_{1}, \dots, Z_{5})

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

Skonstruuj model
Oblicz oczekiwanie warunkowe w ramach modelu (E-Step)
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{aligned} \log Pr [X, Z | θ] & = \sum_{i = 1}^{5} \log \sum_{C \in {A, B}} Pr [X_{i}, Z_{i} = C | θ] \\ = \sum_{i = 1}^{5} \log \sum_{C \in {A, B}} Pr [Z_{i} = C | X_{i}, θ] \cdot \frac{Pr [X_{i}, Z_{i} = C | θ]}{Pr [Z_{i} = C | X_{i}, θ]} \\ \geq \sum_{i = 1}^{5} \sum_{C \in {A, B}} Pr [Z_{i} = C | X_{i}, θ] \cdot \log \frac{Pr [X_{i}, Z_{i} = C | θ]}{Pr [Z_{i} = C | X_{i}, θ]} . \end{aligned}

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

$\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}, θ] = \frac{Pr [X_{i}, Z_{i} = C | θ]}{Pr [X_{i} | θ]} .

$\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 | θ] = \frac{1}{2} \cdot θ_{C}^{h_{i}} (1 - θ_{C})^{10 - h_{i}}, for C \in {A, B} .

$\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} | θ]

$\Pr[X_i|\theta]$

Z_{i} = A

$Z_i=A$

Z_{i} = B

$Z_i=B$

Pr [Z_{i} = A] = Pr [Z_{i} = B] = 1 / 2

$\Pr[Z_i = A] = \Pr[Z_i = B] = 1/2$

Pr [X_{i} | θ] = 1 / 2 \cdot (Pr [X_{i} | Z_{i} = A, θ] + Pr [X_{i} | Z_{i} = B, θ]) .

$\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}, θ] = \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.

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

$X_1 = (H,T,T,T,H,H,T,H,T,H)$

A

$A$

E [# heads by coin A | X_{1}, θ] = h_{1} \cdot Pr [Z_{1} = A | X_{1}, θ] = 5 \cdot 0.45 \approx 2.2.

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

$B$

E [# heads by coin B | X_{1}, θ] = h_{1} \cdot Pr [Z_{1} = B | X_{1}, θ] = 5 \cdot 0.55 \approx 2.8.

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

$h_1$

10 - h_{1}

$10 - h_1$

X_{i}

$X_i$

h_{i}

$h_i$

1 \leq i \leq 5

$1 \leq i \leq 5$

E [# heads by coin A | X, θ] = \sum_{i = 1}^{5} E [# heads by coin A | X_{i}, θ]

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

θ_{A}^{1} = \frac{E [# heads over X by coin A | X, θ]}{E [# heads and tails over X by coin A | X, θ]} = \frac{21.3}{21.3 + 9.6} \approx 0.71.

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

$B$

θ^{1}

$\theta^1$

θ

$\theta$

\hat{θ} = θ^{10} = (0.8, 0.52)

$\hat{\theta} = \theta^{10} = (0.8, 0.52)$

Pr [X, Z | θ]

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

— Nicholas Mancuso
źródło

Jeśli jakieś części nie są jasne, mogę również spróbować je rozwinąć.

— Nicholas Mancuso,

Teraz robi się o wiele wyraźniej. Naprawdę nie rozumiem, dlaczego oczekiwana liczba głów do monety A została obliczona jako: E [# główki do monety A | X1, θ] = h1⋅Pr [Z1 = A | X1, θ] = 5⋅0,45 ≈2,2? Problem wymieniony w pierwszym pliku PDF jest bardziej skomplikowany. Jeśli nie masz nic przeciwko, czy możesz również wykonać kilka przykładowych obliczeń? Wielkie dzięki za odpowiedź.

— IcySnow

@IcySnow, jeśli chodzi o obliczenia: głosi . Powodem jest to, że można pomyśleć o istnieniu innej zmiennej losowej wskaźnika, jeśli użyto A. Obliczenie oczekiwań względem zmiennych wskaźnikowych jest proste prawdopodobieństwo tego zdarzenia.

E [# heads by coin A | X_{1}, θ] = \sum_{# heads in X_{1}} Pr [Z_{1} = A | X_{1}, θ] = 5 \cdot Pr [Z_{1} = A | X_{1}, θ]

$E[\# \text{ heads by coin }A|X_1,\theta] = \sum_{\#\text{ heads in }X_1} \Pr[Z_1 = A| X_1, \theta] = 5 \cdot \Pr[Z_1 = A| X_1, \theta]$

— Nicholas Mancuso

Przepraszam za powolną odpowiedź. Dzięki tobie mogę teraz naprawdę zrozumieć logikę dwóch przykładów monet, po wielokrotnym przejrzeniu twojej odpowiedzi. Chciałbym zadać jeszcze jedną ostatnią rzecz dotyczącą tego pytania: Przykład zaczynający się od strony 8 w tym slajdzie cs.northwestern.edu/~ddowney/courses/395_Winter2010/em.ppt pokazuje, że w M-Step musimy najpierw obliczyć pochodna funkcji logarytmu wiarygodności i użyj jej, aby zmaksymalizować oczekiwanie. Dlaczego coś takiego nie jest w M-Steps przykładów rzucania monetą? Ponieważ te M-Stepy nie wyglądają, jakby coś maksymalizowały

— IcySnow

Jestem zdezorientowany pierwszym wyświetlonym równaniem po „Konstruowaniu modelu”. Czy możesz wyjaśnić, skąd to się wzięło? Wygląda mi na

, więc suma wewnętrzna wynosi 1 dla każdego

, więc cała prawa strona staje się zerowa. Jestem pewien, że coś mi umknęło - czy możesz wyjaśnić, w jaki sposób doszedłeś do tego równania?

Pr [Z_{i} = A | X_{i}, θ] + Pr [Z_{i} = B | X_{i}, θ] = 1

$\Pr[Z_i=A|X_i,\theta]+\Pr[Z_i=B|X_i,\theta]=1$

i

$i$

— DW