EM-алгоритм

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

Часто EM-алгоритм используют для разделения смеси гауссиан.

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

Положим  — плотность вероятности (в непрерывном случае) или функция вероятности (в дискретном случае) полного набора данных с параметрами :  Эту функцию можно понимать как правдоподобие всей модели, если рассматривать её как функцию параметров . Заметим, что условное распределение скрытой компоненты при некотором наблюдении и фиксированном наборе параметров может быть выражено так:

,
используя расширенную формулу Байеса и формулу полной вероятности. Таким образом, нам необходимо знать только распределение наблюдаемой компоненты при фиксированной скрытой  и вероятности скрытых данных .

EM-алгоритм итеративно улучшает начальную оценку , вычисляя новые значения оценок  и так далее. На каждом шаге переход к  от  выполняется следующим образом:

 

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

 вычисляется следующим образом:

 
то есть это условное матожидание  при условии .

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

Альтернативное описание 
При определённых обстоятельствах удобно рассматривать EM-алгоритм как два чередующихся шага максимизации.
Рассмотрим функцию:
 
где q — распределение вероятностей ненаблюдаемых переменных Z; pZ|X(· |x;θ) — условное распределение ненаблюдаемых переменных при фиксированных наблюдаемых x и параметрах θ; H — энтропия и DKL — расстояние Кульбака-Лейблера.

Тогда шаги EM-алгоритма можно представить как:
 E(xpectation) шаг: Выбираем q, чтобы максимизировать F:
 
 M(aximization) шаг: Выбираем θ, чтобы максимизировать F:

Примеры использования 
 k-means — алгоритм кластеризации, построенный на идее EM-алгоритма
 Метод упругих карт для нелинейного сокращения размерности данных
 Алгоритм Баума-Велша — алгоритм для оценки параметров скрытых марковских моделей

Примечания

Ссылки 
 Демонстрация разделения смеси гауссиан с помощью EM-алгоритма
 Реализация на Java

Алгоритмы оптимизации
Кластерный анализ