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

Question

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

Из здесь: Есть три монеты $ 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 $.

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

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

Answer 1

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

$ newcommand { like} { text {l}} newcommand { e} { text {e}} $ Напомнить определение правдоподобия: $$ like [ theta | X] = pr [x | theta] = sum_z pr [x, z | theta] $$, где в нашем случае $ theta = ( theta_a, theta_b) $ являются оценками вероятности того, что монеты A и B соответственно землевладельцы, $ x = (x_1, dotsc, x_5) $ Результаты наших экспериментов, каждый $ x_i $, состоящий из 10 флипов, и $ z = (z_1, dotsc, z_5) $, является монетой, используемой в каждом эксперименте.

Мы хотим найти оценку максимального вероятности $ hat { theta} $. Алгоритм ожидания максимизации (EM) является одним из таких методов, чтобы найти (по крайней мере, локальный) $ hat { theta} $. Он работает, находя условное ожидание, которое затем используется для максимизации $ theta $. Идея состоит в том, что, постоянно найдя более вероятную (то есть более вероятную) $ theta $ в каждой итерации, мы постоянно увеличим $ pr [x, z | theta] $, что, в свою очередь, увеличивает функцию вероятности. Есть три вещи, которые необходимо сделать, прежде чем продвигать алгоритм на основе ЭМ.

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

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

Прежде чем мы пойдем дальше с ними, нам нужно выяснить, что именно мы вычисляем. В E-шаге мы вычисляем именно ожидаемое значение для $ 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*} $$ Причина в том, что у нас есть 5 экспериментов для учета, и мы не знаем, какая монета использовалась в каждой. Неравенство связано с тем, что $ log $ является вогнутым и применением неравенства Дженсена. Причина, по которой нам нужна эта нижняя граница, заключается в том, что мы не можем напрямую вычислить ARG MAX для исходного уравнения. Однако мы можем вычислить его для окончательной нижней границы.

Что такое $ 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]}. $$

Хотя мы добились некоторого прогресса, мы еще не закончили с моделью. Какова вероятность того, что данная монета перевернула последовательность $ x_i $? Letting $ 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 $ , 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)} Приблизительно 0,45. $$ Это значение выходит с тем, что находится в статье. Теперь мы можем вычислить ожидаемое количество голов в $ x_1 = (H, T, T, T, H, H, T, H, T, H) $ из Coin $ a $, $$ e [ text {Heads by Coin} a | X_1, theta] = h_1 cdot pr [z_1 = a | x_1, theta] = 5 cdot 0.45 axtx 2,2. # Text {Heads By Coin} B | X_1, theta] = h_1 cdot pr [z_1 = b | x_1, theta] = 5 cdot 0.55 aopx 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 монета} a | X_i, theta] $$

M-шаг

С нашими ожидаемыми значениями в руках, теперь наступает M шаг, где мы хотим максимизировать $ theta $, учитывая наши ожидаемые значения. Это делается простой нормализацией! $$ theta_a^1 = frac {e [# text {ware over} x text {от coin} a | x, theta]} {e [# text {Heads and Tails Over} x Text {by Coin} a | x, theta]} = frac {21,3} {21,3 + 9,6} приблизительно 0,71. $$ также для $ b $. Этот процесс снова начинается с E-Step и $ theta^1 $ и продолжается до тех пор, пока значения для $ theta $ не спустится (или к некоторому допустимому порогу). В этом примере у нас есть 10 итераций и $ hat { theta} = theta^{10} = (0,8, 0,52) $. В каждой итерации стоимость $ pr [x, z | theta] $ увеличивается из -за лучшей оценки $ theta $.

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