Участник:Onymoth/EM

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

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

Как правило, ЕМ-алгоритм применяется для решения задач двух типов:

• К первому типу можно отнести задачи, связанные с анализом действительно неполных данных, когда некоторые статистические данные отсутствуют в силу каких-либо причин.
• Ко второму типу задач можно отнести те задачи, в которых функция правдоподобия имеет вид, не допускающий удобных аналитических методов исследования, но допускающий серьезные упрощения, если в задачу ввести дополнительные «ненаблюдаемые» (скрытые, латентные) переменные. Примерами прикладных задач второго типа являются задачи распознавания образов, реконструкции изображений. Математическую суть данных задач составляют задачи кластерного анализа, классификации и разделения смесей вероятностных распределений.

1.2 Математическое описание алгоритма

Рассмотрим вероятностную модель с наблюдаемыми переменными $X$ и параметрами $\Theta$, для которой задано правдоподобие $p(X|\Theta)$. Предположим, что в модели также существуют скрытые переменные $Z$, описывающие её внутреннее состояние. Тогда правдоподобие $p(X|\Theta)$ называется неполным, а правдоподобие $p(X, Z|\Theta)$ — полным. Требуется оценить вектор параметров $\Theta$.

Воспользуемся байесовским подходом: зафиксируем вектор параметров $\Theta^{old}$ и вычислим апостериорное распределение на скрытых переменных $p(Z|X, \Theta^{old})$. В этом заключается E-шаг алгоритма.

На M-шаге новый вектор параметров находится как максимизатор матожидания логарифма полного правдоподобия по апостериорному распределению, посчитанному на предыдущем шаге: $\Theta^{new} = \mathbb{E}\log p(X, Z|\Theta)$