Машинное обучение вики
Advertisement

EM-алгоритм (англ. expectation-maximization)  алгоритм, используемый в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных. Каждая итерация алгоритма состоит из двух шагов. На E-шаге (expectation) вычисляется ожидаемое значение функции правдоподобия, при этом скрытые переменные рассматриваются как наблюдаемые. На M-шаге (maximization) вычисляется оценка максимального правдоподобия, таким образом увеличивается ожидаемое правдоподобие, вычисляемое на E-шаге. Затем это значение используется для E-шага на следующей итерации. Алгоритм выполняется до сходимости.

Идея, суть, смысл[]

Положим, что модель распределения наблюдаемых объектов описывается не только с помощью некоторых параметров , но и с использованием скрытых переменных . В таком случае логарифм правдоподобия наблюдаемой выборки записывается в виде . В методе максимального правдоподобия этот логарифм максимизируется по параметру . Однако максимизировать логарифм от суммы некруто: получаются аналитически нерешаемые уравнения, локальные оптимумы и куча прочих неприятностей... Идея!

Давайте придумаем способ для каждого фиксированного находить оптимальную оценку снизу для , т. е. , максимизировать ее по параметру, а затем проделывать все заново до сходимости!

Ок, пускай у нас есть некоторое распределение на скрытых переменных:

. Тогда

.

Неравенство здесь откуда? А, это ж Йенсен для строго вогнутого логарифма от случайной величины , которая принимает значения с вероятностями . Вот мы получили нижнюю оценку для .

Давайте теперь эту оценку сделаем оптимальной для некоторого фиксированного . Вспомним, что Йенсен обращается в равенство для строго вогнутых функций тогда и только тогда, когда случайная величина, относительно которой записывается неравенство, почти всюду совпадает со своим матожиданием. Ага, ну тогда: . Из чего немедленно следует, что .

Отлично! Теперь эту оптимальную оценку мы, как и обещали, будем максимизировать по параметру:

.

Мы там выкинули часть не зависящую от параметра, разбив логарифм частного на разность логарифмов.

Все, вот, собственно, и весь алгоритм. Часть с настройкой распределения на скрытых переменных при фиксированном параметре называется E-шагом, а часть с оптимизацией по параметру нижней оценки при фиксированном распределении на скрытых переменных — M-шагом. Сам алгоритм приведен тут.

Свойства, комментарии, замечания[]

Ну и что, норм алгоритм? А то! Оказывается, получаемые оценки параметра дают неубывающую последовательность значений логарифма правдоподобия . Мда? Да! Ведь для любых соседних и выполняются следующие соотношения: . Это справедливо в силу того, что оценка точна при и является обычной оценкой снизу при прочих значениях параметра, а также в силу M-шага.

Вот, значит, мы получили неубывающую, ограниченную сверху (логарифм от ограниченного правдоподобия ограничен, вау) последовательность чисел. Значит, куда-то она сходится. Ну и хорошо.

Что можно сказать по этому поводу?

  • Имеем в виду, что распределение на скрытых переменных не зависит от параметра на M-шаге, так как зафиксировано на E-шаге.
  • Итерировать можно до сходимости по аргументу, по правдоподобию, по числу итераций.
  • Так как EM сходится к локальному оптимому, было бы неплохо запустить его из нескольких начальных приближений, а затем взять лучший результат (по величине логарифма правдоподобия) в качестве окончательной оценки параметра.
  • Есть еще такая штука, как Generalized EM. Тут идея такова, что для сходимости на M-шаге не обязательно искать прям точь-в-точь аргмаксимум. По сути достаточно даже грубого одношагового приближения. Ну лан, будем знать.
  • EM, как вы, мальчики и девочки, наверное, заметили, применяется для ML-оптимизации. Но его можно применять и для нахождения MAP-оценок (об этом далее).
  • Если хотите, рассматривайте EM как покоординатный подъем, мне-то что.

Случай независимых наблюдений[]

А что, если ? Ну, например, если скрытая переменная отвечают за компоненту смеси, из которой происходит объект, или если скрытая переменная — недостающие переменные в независимых и одинаково распределенных наблюдаемых объектах. О, ну тогда совсем другое дело:

  • E-шаг: 

.

  • M-шаг:  .

Регуляризация (тут же про MAP)[]

Ок, давайте добавим регуляризатор к нашему логарифму правдоподобия: . Давайте не будем переписывать все заново, а методом пристального взгляда осознаем, что нижняя оценка станет такой: , поэтому E-шаг вообще никак не изменится: мы полагаем оптимальным распределением на скрытых переменных все то же при некотором фиксированном (действительно, при фиксированном параметре регуляризационная добавка есть просто добавление константы, поэтому оптимум никуда не сдвинется). На M-шаге мы совершим все те же действия, на каждом этапе таща за собой регуляризационную добавку, поэтому конечный результат: . В итоге измененный алгоритм получится таким.

Хорошо, но что насчет MAP-оценки? А в чем суть оценки Maximum A Posteriori? Мы полагаем (Байесовский подход), что параметр — это не что-то строго фиксированное, а тоже в некотором роде случайная величина. Поэтому мы прямо так и говорим: пусть — случайная величина с априорным распределением . Тогда по аналогии с методом максимального правдоподобия мы будем максимизировать следующую функцию правдоподобия: . Если приглядеться, то это только что рассмотренный ML с регуляризацией . А посему все (касаемо EM) проделывается в полной аналогии. А вот и результат.

Вывод для гауссиан[]

Для смеси нормальных распределений полный вывод можно найти по этой ссылке. Затруднения возникают в связи с необходимостью дифференцирования определителей и прочих логарифмов от них, которые появляются в лагранжиане для M-шага; Китов расправляется с этим безобразием при помощи лемм. В остальном всё следует определениям в лоб и требует просто аккуратного расписывания.

P. S.[]

Сорри за корявые формулы, ох уж эта педивикия...

Advertisement