Участник:Victoria Evstefeeva - История изменений

Victoria Evstefeeva: Содержимое страницы заменено на «Виктория Евстефеева, 416 группа. [https://algowiki-project.org/ru/EM_Алгоритм_для_пуассо…»

2017-12-02T19:45:02Z

Содержимое страницы заменено на «Виктория Евстефеева, 416 группа. [https://algowiki-project.org/ru/EM_Алгоритм_для_пуассо…»

← Предыдущая версия		Версия от 19:45, 2 декабря 2017
Строка 1:		Строка 1:
	~~== Свойства и структура алгоритмов ==~~		Виктория Евстефеева, 416 группа.

	~~=== Общее описание алгоритма ===~~		[https://algowiki-project.org/ru/EM_Алгоритм_для_пуассон_трехточечного_распределения ЕМ алгоритм для пуассон-трехточечного распределения]

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


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

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

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

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

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

	~~<center><math>f_{θ}^{X}=Σ_{i=1}^{k}p_{i}ψ_{i}(x; t_{i}),</math><~~/~~center>~~

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

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

	~~<center><math>f_{λ, p}^{X}=Σ_{i=1}^{k}p_{i}\frac{λ_{i}^{x}e^{-λ_{i}}}{x!},</math></center>~~

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

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

	~~<center><math>P(X_i = k)=\frac{1}{k!}Σ_{j=1}^{3}p_{j}λ_{j}^{k}e^{-λ_{j}}, k = 0,1,2,...,</math></center>~~
	~~где <math>p_j \geqslant 0, λ_j > 0, j = \{1, 2, 3\}</math> - неизвестные параметры, <math>p_1+p_2+p_3=1</math>~~


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


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

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

	~~<center><math>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</math></center>~~

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

	~~<center><math>p_j^{(m+1)}=\frac{1}{n}Σ_{i=1}^{n}g_{ij}^{(m)}, j = \{1, 2, 3\}</math></center>~~


	~~<center><math>λ_j^{(m+1)}=\frac{Σ_{i=1}^{n}X_ig_{ij}^{(m)}}{Σ_{i=1}^{n}g_{ij}^{(m)}}, j = \{1, 2, 3\}</math></center>~~

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

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

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

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

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

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

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

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

	~~== Программная реализация алгоритма ==~~
	~~=== Особенности реализации последовательного алгоритма ===~~

	~~=== Локальность данных и вычислений ===~~
	~~=== Возможные способы и особенности параллельной реализации алгоритма ===~~

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

	~~=== Динамические характеристики и эффективность реализации алгоритма ===~~
	~~=== Выводы для классов архитектур ===~~

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

	~~== Литература ==~~

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

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

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

Victoria Evstefeeva: /* Математическое описание алгоритма */

2017-10-30T09:43:55Z