Участник:Onymoth/EM
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
EM-алгоритм — алгоритм, используемый в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных. Каждая итерация алгоритма состоит из двух шагов. На E-шаге (expectation) вычисляется ожидаемое значение функции правдоподобия, при этом скрытые переменные рассматриваются как наблюдаемые. На M-шаге (maximization) вычисляется оценка максимального правдоподобия, таким образом увеличивается ожидаемое правдоподобие, вычисляемое на E-шаге. Затем это значение используется для E-шага на следующей итерации. Алгоритм выполняется до сходимости.
Как правило, ЕМ-алгоритм применяется для решения задач двух типов:
- К первому типу можно отнести задачи, связанные с анализом действительно неполных данных, когда некоторые статистические данные отсутствуют в силу каких-либо причин.
- Ко второму типу задач можно отнести те задачи, в которых функция правдоподобия имеет вид, не допускающий удобных аналитических методов исследования, но допускающий серьезные упрощения, если в задачу ввести дополнительные «ненаблюдаемые» (скрытые, латентные) переменные. Примерами прикладных задач второго типа являются задачи распознавания образов, реконструкции изображений. Математическую суть данных задач составляют задачи кластерного анализа, классификации и разделения смесей вероятностных распределений.
1.2 Математическое описание алгоритма
Рассмотрим вероятностную модель с наблюдаемыми переменными [math]X[/math] и параметрами [math]\Theta[/math], для которой задано правдоподобие [math]p(X|\Theta)[/math]. Предположим, что в модели также существуют скрытые переменные [math]Z[/math], описывающие её внутреннее состояние. Тогда правдоподобие [math]p(X|\Theta)[/math] называется неполным, а правдоподобие [math]p(X, Z|\Theta)[/math] — полным. Требуется оценить вектор параметров [math]\Theta[/math].
Воспользуемся байесовским подходом: зафиксируем вектор параметров [math]\Theta^{old}[/math] и вычислим апостериорное распределение на скрытых переменных [math]p(Z|X, \Theta^{old})[/math]. В этом заключается E-шаг алгоритма.
На M-шаге новый вектор параметров находится как максимизатор матожидания логарифма полного правдоподобия по апостериорному распределению, посчитанному на предыдущем шаге: [math]\Theta^{new} = \mathbb{E}\log p(X, Z|\Theta)[/math]
