Участник:Victoria Evstefeeva: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
(Содержимое страницы заменено на «Виктория Евстефеева, 416 группа. [https://algowiki-project.org/ru/EM_Алгоритм_для_пуассо…»)
 
(не показана 31 промежуточная версия этого же участника)
Строка 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>.
 
 
 
=== Вычислительное ядро алгоритма ===
 
 
 
=== Макроструктура алгоритма ===
 
 
 
=== Схема реализации последовательного алгоритма ===
 
 
 
=== Последовательная сложность алгоритма ===
 
 
 
=== Информационный граф ===
 
 
 
=== Ресурс параллелизма алгоритма ===
 
 
 
=== Входные и выходные данные алгоритма ===
 
 
 
=== Свойства алгоритма ===
 
 
 
== Программная реализация алгоритма ==
 
=== Особенности реализации последовательного алгоритма ===
 
 
 
=== Локальность данных и вычислений ===
 
=== Возможные способы и особенности параллельной реализации алгоритма ===
 
 
 
=== Масштабируемость алгоритма и его реализации ===
 
 
 
=== Динамические характеристики и эффективность реализации алгоритма ===
 
=== Выводы для классов архитектур ===
 
 
 
=== Существующие реализации алгоритма ===
 
 
 
== Литература ==
 
 
 
↑ В.Ю. Королев "Вероятностно-статистические методы декомпозиции волатильности хаотических процессов".
 
↑ В. Ю. Королев, А. Ю. Корчагин, А. И. Зейфман "Теорема Пуассона для схемы испытаний Бернулли со случайной вероятностью успеха и дискретный аналог распределения Вейбулла"
 
↑ http://www.machinelearning.ru/wiki/index.php?title=EM-алгоритм
 

Текущая версия на 22:45, 2 декабря 2017