От функции правдоподобия к алгоритму EM (с кодовой реализацией)

1. Что такое алгоритм ЭМ

Алгоритм максимизации ожидания (алгоритм максимизации ожидания, также переводится как алгоритм максимизации ожидания) — это алгоритм нахождения оценки максимального правдоподобия или максимальной апостериорной оценки параметров в вероятностной модели, где вероятностная модель зависит от ненаблюдаемых скрытых переменных.

Алгоритм максимального ожидания вычисляется поочередно в два шага,

первый шагсостоит в том, чтобы вычислить математическое ожидание (E), используя существующую оценку скрытой переменной для вычисления ее оценки максимального правдоподобия;второй шагпредставляет собой максимизацию (M), которая максимизирует максимальное значение правдоподобия, полученное на шаге E для вычисления значения параметра. Оценки параметров, найденные на шаге M, используются в расчете следующего шага E, который непрерывно чередуется.

Оценку максимального правдоподобия можно свести к одному предложению: зная результат, вывести условие θ.

1.1 Функция правдоподобия

В математической статистике,Функция правдоподобияявляется функцией параметров в статистической модели, представляющей вероятность в параметрах модели. «Вероятность» аналогична «вероятности» или «вероятности», и оба относятся к возможности возникновения события.Максимальная вероятность эквивалентна максимально возможному значению.

Например, один из ваших одноклассников вышел с охотником на охоту, и мимо пробежал заяц. Только услышав выстрел, заяц ответил, если хочешь порассуждать, кто выпустил пулю, которая попала? Вы будете думать, что попадете с одного выстрела, а поскольку вероятность того, что охотник попадет, как правило, выше, чем у вашего одноклассника, то можно сделать вывод, что этот выстрел должен быть произведен охотником.

Вывод, сделанный в этом примере, отражает основную идею метода максимального правдоподобия.

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

1.3 Шаги решения функции максимального правдоподобия

Допустим, мы хотим отрисовать 100 человек из 100 000 человек для статистики роста, тогда вероятность отрисовки этих 100 человек равна (умножение вероятности):

L(\theta)=L(x_1,...,x_n|\theta)=\prod_{i=1}^{n}p(x_i|\theta),\theta\in\ominus

Это то, что требуется сейчас $\theta$ стоимость, то есть создание $L(\theta)$ Вероятность максимизации, то параметры в это время $\theta$ это то, о чем просят.

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

H(\theta)=lnL(\theta)=ln\prod_{i=1}^{n}p(x_i|\theta)=\sum_{i=1}^{n}lnp(x_i|\theta)

Для нахождения экстремального значения функции, благодаря знаниям в области исчисления, которые мы изучили в бакалавриате, наиболее прямая идея состоит в том, чтобы взять производную, а затем пусть производная равна 0, тогда θ, полученное путем решения этого уравнения (конечно, предпосылка состоит в том, что функция L( θ) непрерывно дифференцируема). Но что, если θ — это вектор с несколькими параметрами? Конечно, найти частную производную L(θ) по всем параметрам, то есть по градиенту, так, чтобы было n уравнений относительно n неизвестных параметров, а решением системы уравнений была крайняя точка функция правдоподобия и, наконец, значение параметра.

Общие шаги для нахождения оценки функции максимального правдоподобия:

Запишите функцию правдоподобия;
Возьмем логарифм функции правдоподобия и отсортируем;
Найдите производную, пусть производная равна 0, и получите уравнение правдоподобия;
Решите уравнение правдоподобия, и полученные параметры являются искомыми параметрами;

1.4 ЭМ-алгоритм

Две монеты A и B, предположим, что вероятность выпадения орла после случайного броска равна PA, PB соответственно. Чтобы оценить вероятность того, что эти две монеты выпадут, мы подбрасываем монеты A и B по очереди, 5 последовательных подбрасываний в каждом раунде, всего 5 раундов:

монета	результат	статистика
A	положительный и отрицательный	3 вперед - 2 назад
B	Плюсы и минусы	2 вперед - 3 назад
A	Плюсы и минусы	1 вперед - 4 назад
B	положительный и отрицательный	3 вперед - 2 назад
A	Плюсы и минусы	2 вперед - 3 назад

Монета A была подброшена 15 раз, и в первом, третьем и пятом раундах выпало 3 положительных, 1 положительный и 2 положительных результата соответственно, поэтому легко оценить PA, и, аналогично, PB также легко вычислить. (реальная стоимость),следующее:

ПА = (3+1+2) / 15 = 0,4 ПВ= (2+3)/10 = 0,5

Вопрос в том, что если мы не знаем, является ли подбрасываемая монета А или В (то есть тип монеты является скрытой переменной), а затем подбрасываем ее пять раз по очереди, мы получаем следующие результаты:

монета	результат	статистика
Unknown	положительный и отрицательный	3 вперед - 2 назад
Unknown	Плюсы и минусы	2 вперед - 3 назад
Unknown	Плюсы и минусы	1 вперед - 4 назад
Unknown	положительный и отрицательный	3 вперед - 2 назад
Unknown	Плюсы и минусы	2 вперед - 3 назад

Хорошо, вопрос становится интересным. Теперь наша цель не изменилась, по-прежнему оцениваем PA и PB, что нужно сделать?

Очевидно, в это время у нас есть дополнительная скрытая переменная типа монеты, задайте ее как z, которую можно рассматривать как 5-мерный вектор (z1, z2, z3, z4, z5), представляющий монету, используемую для каждого броска, Например, z1 представляет собой монету, использованную при первом броске, А или В.

Однако, если эта переменная z неизвестна, невозможно оценить PA и PB, поэтому мы должны сначала оценить z, прежде чем мы сможем далее оценить PA и PB.
Но чтобы оценить z, мы должны знать PA и PB, чтобы мы могли использовать правило вероятности максимального правдоподобия для оценки z. Разве это не проблема курицы и яйца? Как ее решить?

Ответ состоит в том, чтобы сначала случайным образом инициализировать PA и PB, использовать их для оценки Z, затем на основе z или в соответствии с методом вероятности максимального правдоподобия оцениваются новые PA и PB, а затем циклически, если вновь оцененные PA и ПБ и наша правда большой разницы не имеют, покаPA и PB сходятся к своим истинным значениям.

Мы могли бы также сделать это, сначала присвоив значение PA и PB, например: Вероятность выпадения монеты А орлом PA = 0,2 Вероятность того, что монета B выпадет орлом, PB = 0,7.

Затем мы смотрим, какая монета, скорее всего, будет подброшена в первом раунде. Если это монета А, то вероятность выпадения 3 орлов и 2 решек равна 0,2.0.20.20.80,8 = 0,00512 Если это монета B, то вероятность выпадения 3 орлов и 2 решек равна 0,7.0.70.70.30,3=0,03087 Затем найдите соответствующие вероятности в остальных 4 раундах по очереди. Сделайте форму следующим образом:

количество раундов	Если монета А	Если монета Б
1	0,00512, т.е. 0,2 0,2 0,2 0,8 0,8, 3 положительных - 2 отрицательных	0,03087, 3 вперед - 2 назад
2	0,02048, что составляет 0,2 0,2 0,8 0,8 0,8, 2 положительных - 3 отрицательных	0,01323, 2 вперед - 3 назад
3	0,08192, т.е. 0,2 0,8 0,8 0,8 0,8, 1 положительный - 4 отрицательный	0,00567, 1 вперед - 4 назад
4	0,00512, т.е. 0,2 0,2 0,2 0,8 0,8, 3 положительных - 2 отрицательных	0,03087, 3 вперед - 2 назад
5	0,02048, что составляет 0,2 0,2 0,8 0,8 0,8, 2 положительных - 3 отрицательных	0,01323, 2 вперед - 3 назад

Согласно правилу максимального правдоподобия: Скорее всего монета B в 1 раунде Скорее всего монета А во 2 раунде Скорее всего монета А в 3 раунде Скорее всего, монета B в 4-м раунде Скорее всего монета А в 5 раунде

Мы складываем более высокую вероятность, то есть, скорее всего, будет А, то есть количество раз 2, 1 и 2, которые оказываются положительными во 2-м, 3-м и 5-м раундах, и делим на общее количество раз A бросается 15 (A бросает три раунда, по 5 раз каждый), как оценка z, B вычисляется аналогично. Затем мы можем оценить новые PA и PB в соответствии с правилом вероятности максимального правдоподобия.

ПА = (2+1+2)/15 = 0,33 ПВ = (3+3)/10 = 0,6

Таким образом, постоянная итерация продолжает приближаться к истинному значению, что является магией алгоритма EM.

Можно ожидать, что мы будем продолжать следовать изложенным выше идеям, использовать предполагаемые PA и PB для оценки z, а затем использовать z для оценки новых PA и PB, После повторных итераций мы можем, наконец, получить PA = 0,4, PB = 0,5, в это время Как бы ни выполнялись итерации, значения PA и PB останутся неизменными на уровне 0,4 и 0,5, поэтому мы нашли оценки максимального правдоподобия PA и PB.

Подытожим этапы расчета:

Произвольно инициализируйте параметры распределения θ
Шаг E, найти функцию Q, для каждого i вычислить апостериорную вероятность скрытой переменной (фактически ожидание скрытой переменной) на основе параметров модели предыдущей итерации, как текущее оценочное значение скрытой переменной :

$Q_i(z^{(i)})=p(z^{(i)}|x^{(i)};\theta)$
M шагов, найдите значение параметра, когда функция Q максимизируется) Максимизируйте функцию правдоподобия, чтобы получить новые значения параметра

$\theta=argmax\sum_{i}\sum_{z^{(i)}}Q_i(z^{(i)})log\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}$
Затем цикл повторяет шаги 2 и 3 до сходимости.

Подробный процесс вывода см. в ссылках в конце документа.

2. Какие модели решаются с помощью алгоритма EM?

Модели, решаемые с помощью алгоритма EM, обычно имеют GMM или совместную фильтрацию, а k-средние фактически принадлежат EM. Алгоритм EM определенно сойдется, но он может сойтись к локальному оптимуму. Поскольку количество суммируемых членов будет увеличиваться экспоненциально с увеличением количества скрытых переменных, это вызовет проблемы при вычислении градиента.

3. Реализация кода

Алгоритм ЭМ модели гауссовой смеси

【Машинное обучение легко понять серия статей】

4. Ссылки

Как популярно понять алгоритм EM

автор:@mantchs

Гитхаб:GitHub.com/NLP-love/ml…

Приглашаются все желающие присоединиться к обсуждению! Улучшайте этот проект вместе! Номер группы: [541954936]