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

Материал из Алговики
Перейти к навигации Перейти к поиску

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]

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

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

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Масштабируемость алгоритма и его реализации

2.4 Динамические характеристики и эффективность реализации алгоритма

2.5 Выводы для классов архитектур

2.6 Существующие реализации алгоритма

3 Литература