Участник:Victoria Evstefeeva

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

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

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

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

• К первому типу можно отнести задачи, связанные с анализом действительно неполных данных, когда некоторые статистические данные отсутствуют в силу каких-либо причин.

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

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

Задача отыскания наиболее правдопободных оценок параметров смесей вероятностных распределений является одним из самых популярных приложений ЕМ-алгоритма.

Базовым предположением в рамках данной задачи является то, что плотность наблюдаемой случайной величины [math]\displaystyle{ Χ }[/math] имеет вид:

[math]\displaystyle{ f_{θ}^{X}=Σ_{i=1}^{k}p_{i}ψ_{i}(x; t_{i}), }[/math]

где [math]\displaystyle{ k\geqslant 1 }[/math] - известное натуральное число, [math]\displaystyle{ ψ_{1}, ..., ψ_{k} }[/math] - известные плотности распределения, неизвестный параметр [math]\displaystyle{ θ }[/math] имеет вид [math]\displaystyle{ θ=(p_{1}, ..., p_{k}, t_{1},..., t_{k}), }[/math] причем [math]\displaystyle{ p_{i}\geqslant 0, }[/math] [math]\displaystyle{ i = 1, ..., k, }[/math] [math]\displaystyle{ p_{1}+...+p_{k}=1, }[/math] [math]\displaystyle{ t_{i}, }[/math] [math]\displaystyle{ i=1,...,k, }[/math] - вообще говоря, многомерные параметры. Плотности [math]\displaystyle{ ψ_{1}, ..., ψ_{k} }[/math] будем называть компонентами смеси, параметры [math]\displaystyle{ p_{1}, ..., p_{k} }[/math] будем называть весами соответствующих компонент.

Задачей разделения смеси принято называть задачу статистического оценивания параметров [math]\displaystyle{ θ=(p_{1}, ..., p_{k}, t_{1},..., t_{k}), }[/math] по известным реализациям случайно величины [math]\displaystyle{ Χ }[/math].

Оценивание параметров смешанных пуассоновских моделей сводится к оцениванию смешивающего распределения. Традиционно с этой целью используется классический ЕМ алгоритм. В случае Пуассон трехточечного распределения случайной величины [math]\displaystyle{ Χ }[/math] функция плотности представимая в виде:

[math]\displaystyle{ f_{θ}^{X}=Σ_{i=1}^{3}p_{i}ψ_{i}(x; λ_{i}), }[/math]

где [math]\displaystyle{ ψ_{i}(x; λ_{I}) = \frac{λ_{i}^{x}e^{-λ_{I}}}{x!} }[/math] - плотность пуассоновского распределения относительно считающей меры с параметром [math]\displaystyle{ λ_{i} }[/math].

Литература

↑ В.Ю. Королев "Вероятностно-статистические методы декомпозиции волатильности хаотических процессов".

↑ В. Ю. Королев, А. Ю. Корчагин, А. И. Зейфман "Теорема Пуассона для схемы испытаний Бернулли со случайной вероятностью успеха и дискретный аналог распределения Вейбулла".

↑ http://www.machinelearning.ru/wiki/index.php?title=EM-алгоритм