EM Алгоритм для пуассон трехточечного распределения

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

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

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

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

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

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

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

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

Базовым предположением в рамках данной задачи является то, что плотность наблюдаемой случайной величины $Χ$ имеет вид:

$f_{θ}^{X}=Σ_{i=1}^{k}p_{i}ψ_{i}(x; t_{i}),$

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

Задачей разделения смеси принято называть задачу статистического оценивания параметров $θ=(p_{1}, ..., p_{k}, t_{1},..., t_{k}),$ по известным реализациям случайно величины $Χ$. Оценивание параметров смешанных пуассоновских моделей сводится к оцениванию смешивающего распределения. Традиционно с этой целью используется классический ЕМ алгоритм. В случае Пуассон трехточечного распределения случайной величины $Χ$ функция плотности относительно считающей меры имеет вид:

$f_{λ, p}^{X}=Σ_{i=1}^{k}p_{i}\frac{λ_{i}^{x}e^{-λ_{i}}}{x!},$

где $λ$ - трехточечная случайная величина, то есть принимает значения $λ_{1}, λ_{2}, λ_{3}$ с вероятностями $p_{1}, p_{2}, p_{3}$ соответственно.

Итерационный ЕМ-алгоритм для оценивания неизвестных параметров $p_1,p_2,p_3,λ1,λ_2,λ_3$ определяется следующим образом. Дана выборка $X_1, ..., X_n$ независимых одинаково распределенных случайных величин таких, что

$P(X_i = k)=\frac{1}{k!}Σ_{j=1}^{3}p_{j}λ_{j}^{k}e^{-λ_{j}}, k = 0,1,2,...,$

где $p_j \geqslant 0, λ_j \gt 0, j = \{1, 2, 3\}$ - неизвестные параметры, $p_1+p_2+p_3=1$

Пусть $p^{(m)}_1, p^{(m)}_2 , p^{(m)}_3, λ_1^{(m)}, λ_2^{(m)}, λ_3^{(m)}$ – оценки этих параметров, полученные на $m$-й итерации.

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

1 шаг алгоритма - вычисление условного математического ожидания:

$g_{ij}^{(m)} = \frac{p_j^{(m)}e^{-λ_j^{(m)}}(λ_j^{(m)})^{X_i}}{Σ_{j=1}^{3}p_je^{-λ_j^{(m)}}(λ_j^{(m)})^{X_i}}, i=1,..., n$

2 шаг алгоритма - оценивание неизвестных параметров:

$p_j^{(m+1)}=\frac{1}{n}Σ_{i=1}^{n}g_{ij}^{(m)}, j = \{1, 2, 3\}$

$λ_j^{(m+1)}=\frac{Σ_{i=1}^{n}X_ig_{ij}^{(m)}}{Σ_{i=1}^{n}g_{ij}^{(m)}}, j = \{1, 2, 3\}$

3 Литература

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

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

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