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

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

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

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

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

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

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

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

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

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