Участник:Марина/Песочница
Материал из MachineLearning.
EM-алгоритм (англ. expectation-maximization) - алгоритм, используемый в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных. Каждая итерация алгоритма состоит из двух шагов. На E-шаге (expectation) вычисляется ожидаемое значение функции правдоподобия, при этом скрытые переменные рассматриваются как наблюдаемые. На M-шаге (maximization) вычисляется оценка максимального правдоподобия, таким образом увеличивается ожидаемое правдоподобие, вычисляемое на E-шаге. Затем это значение используется для E-шага на следующей итерации. Алгоритм выполняется до сходимости.
Как правило, ЕМ-алгоритм применяется для решения задач двух типов. К первому типу можно отнести задачи, связанные с анализом действительно неполных данных, когда некоторые статистические данные отсутствуют в силу каких-либо причин. Ко второму типу задач можно отнести те задачи, в которых функция правдоподобия имеет вид, не допускающий удобных аналитических методов исследования, но допускающий серьезные упрощения, если в задачу ввести дополнительные “ненаблюдаемые” (скрытые, латентные) переменные. Примерами прикладных задач второго типа являются задачи распознавания образов, реконструкции изображений. Математическую суть данных задач составляют задачи кластерного анализа, классификации и разделения смесей вероятностных распределений.
Содержание |
Основной алгоритм
Пусть плотность распределения на множестве имеет вид смеси
распределений:
,
,
,
где - функция правдоподобия j-й компоненты смеси,
- ее априорная вероятность.
Функции правдоподобия принадлежат параметрическому семейству распределений и отличаются только значениями параметра
.
Задача разделения смеси заключается в том, чтобы, имея выборку случайных и независимых наблюдений из смеси
, зная число
и функцию
, оценить вектор параметров
.
Идея алгоритма заключается в следующем. Искусственно вводится вспомогательный вектор скрытых переменных , обладающий двумя замечательными свойствами. С одной стороны, он может быть вычислен, если известны значения вектора параметров
. С другой стороны, поиск максимума правдоподобия сильно упрощается, если известны значения скрытых переменных.
EM-алгоритм состоит из итерационного повторения двух шагов. На E-шаге вычисляется ожидаемое значение (expectation) вектора скрытых переменных по текущему приближению вектора параметров
. На М-шаге решается задача максимизации правдоподобия (maximization) и находится следующее приближение вектора
по текущим значениям векторов
и
.
