Применение максимизации ожиданий к примерам подбрасывания монет

В последнее время я самостоятельно изучал максимизацию ожиданий и собрал в процессе несколько простых примеров:

От сюда : Есть три монеты $c_0$ , $c_1$ и $c_2$ с $p_0$ , $p_1$ и $p_2$ соответствующей вероятностью для посадки на голове , когда кинули. Бросок $c_0$ . Если результат - голова, бросьте $c_1$ три раза, иначе бросьте $c_2$ три раза. Наблюдаемые данные, полученные с помощью $c_1$ и $c_2$ выглядят так: HHH, TTT, HHH, TTT, HHH. Скрытые данные - результат $c_0$ . Оценка $p_0$ ,$p_1$ и$p_2$ .

И отсюда : есть две монеты $c_A$ и $c_B$ где $p_A$ и $p_B$ являются соответствующей вероятностью посадки на голову при подбрасывании. В каждом раунде выбирайте одну монету случайным образом и подбрасывайте ее десять раз; запишите результаты. Наблюдаемые данные представляют собой результаты броска, представленные этими двумя монетами. Однако мы не знаем, какая монета была выбрана для определенного раунда. Расчетный $p_A$ и $p_B$ .

Хотя я могу получить расчеты, я не могу связать способы их решения с оригинальной теорией ЭМ. В частности, во время M-Step обоих примеров я не вижу, как они максимизируют что-либо. Просто кажется, что они пересчитывают параметры и каким-то образом новые параметры лучше, чем старые. Более того, два E-шага даже не похожи друг на друга, не говоря уже об E-Step оригинальной теории.

Так как именно эти примеры работают?

(Этот ответ использует вторую ссылку, которую вы дали.)

$\newcommand{\Like}{\text{L}}\newcommand{\E}{\text{E}}$ Напомним определение вероятности: где в нашем случае являются оценками вероятности того, что монеты A и B соответственно приземляются, являются результатами наших экспериментов, каждый состоит из 10 сальто, а - монета, используемая в каждом эксперименте.θ = ( θ 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)$

Мы хотим найти оценку максимального правдоподобия . Алгоритм Expectation-Maximization (EM) является одним из таких методов поиска (по крайней мере локального) . Он работает, находя условное ожидание, которое затем используется для максимизации . Идея состоит в том, что, непрерывно находя более вероятную (т.е. более вероятную) на каждой итерации, мы будем постоянно увеличивать что, в свою очередь, увеличивает функцию правдоподобия. Перед тем, как приступить к разработке алгоритма на основе ЭМ, необходимо сделать три вещи. ; & thetas ; & thetasthetasPr[X,Z| θ$\hat{\theta}$$\hat{\theta}$$\theta$$\theta$$\Pr[X,Z|\theta]$

1. Построить модель
2. Вычислить условное ожидание по модели (E-Step)
3. Увеличьте нашу вероятность, обновив нашу текущую оценку (M-Step)$\theta$

Построить модель

Прежде чем мы продолжим работу с EM, нам нужно выяснить, что именно мы вычисляем. На шаге E мы вычисляем точно ожидаемое значение для . Так что же это за ценность на самом деле? Заметьте, что Причина в том, что у нас есть 5 экспериментов, и мы не знаем, какая монета использовалась в каждом. Неравенство связано с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$будучи вогнутым и применяя неравенство Дженсена. Причина, по которой нам нужна эта нижняя граница, заключается в том, что мы не можем напрямую вычислить arg max для исходного уравнения. Однако мы можем вычислить его для окончательной нижней границы.

Теперь, что такое ? Это вероятность того, что мы видим монету учетом эксперимента и . Используя условные вероятности, мы имеем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]}.$$

Хотя мы добились определенного прогресса, мы еще не закончили с моделью. Какова вероятность того, что данная монета перевернула последовательность ? Пусть Теперь , очевидно , только вероятность при обеих возможностях или . Поскольку имеем h i = # головы в  X i Pr [ X i , Z i = C | θ ] = $X_i$$h_i = \#\text{heads in } X_i$ Pr[Xi| θ]Zя=Zя=BPr[Zя=]=Pr[Zя=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

Ладно ... это было не так весело, но мы можем начать делать кое-какую работу сейчас. Алгоритм EM начинается с некоторого случайного предположения для . В этом примере мы имеем . Мы вычисляем Это значение совпадает с тем, что есть в статье. Теперь мы можем вычислить ожидаемое количество голов в из монеты , Делая то же самое для монеты мы получаем, $\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.$$ Мы можем вычислить то же самое для количества хвостов, подставив для . Это продолжается для всех других значений и . Благодаря линейности ожидания мы можем вычислить $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]$$

М-Шаг

Теперь, когда у нас есть ожидаемые значения, наступает этап М, на котором мы хотим максимизировать учетом ожидаемых значений. Это делается простой нормализацией! Точно так же для . Этот процесс начинается снова с E-шага и и продолжается до тех пор, пока значения для сходятся (или до некоторого допустимого порога). В этом примере у нас есть 10 итераций и . На каждой итерации значение увеличивается из-за лучшей оценки$\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$ .

Теперь в этом случае модель была довольно упрощенной. Все может стать намного сложнее довольно быстро, однако алгоритм EM всегда будет сходиться и всегда будет давать оценку максимального правдоподобия . Это может быть локальная оценка, но чтобы обойти это, мы можем просто перезапустить EM-процесс с другой инициализацией. Мы можем делать это постоянное количество раз и сохранять лучшие результаты (т. Е. Те, которые имеют наивысшую конечную вероятность).$\hat{\theta}$