Участник:Марина/Песочница

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
Строка 3: Строка 3:
Как правило, ЕМ-алгоритм применяется для решения задач двух типов. К первому типу можно отнести задачи, связанные с анализом действительно неполных данных, когда некоторые статистические данные отсутствуют в силу каких-либо причин. Ко второму типу задач можно отнести те задачи, в которых функция правдоподобия имеет вид, не допускающий удобных аналитических методов исследования, но допускающий серьезные упрощения, если в задачу ввести дополнительные “ненаблюдаемые” (скрытые, латентные) переменные. Примерами прикладных задач второго типа являются задачи распознавания образов, реконструкции изображений. Математическую суть данных задач составляют задачи кластерного анализа, классификации и разделения смесей вероятностных распределений.
Как правило, ЕМ-алгоритм применяется для решения задач двух типов. К первому типу можно отнести задачи, связанные с анализом действительно неполных данных, когда некоторые статистические данные отсутствуют в силу каких-либо причин. Ко второму типу задач можно отнести те задачи, в которых функция правдоподобия имеет вид, не допускающий удобных аналитических методов исследования, но допускающий серьезные упрощения, если в задачу ввести дополнительные “ненаблюдаемые” (скрытые, латентные) переменные. Примерами прикладных задач второго типа являются задачи распознавания образов, реконструкции изображений. Математическую суть данных задач составляют задачи кластерного анализа, классификации и разделения смесей вероятностных распределений.
-
== Основной алгоритм ==
+
== Постановка задачи ==
Пусть плотность распределения на множестве <tex>X</tex> имеет вид смеси <tex>k</tex> распределений: <br />
Пусть плотность распределения на множестве <tex>X</tex> имеет вид смеси <tex>k</tex> распределений: <br />
::<tex>p(x) = \sum_{j=1}^k w_jp_j(x)</tex> , <tex>\sum_{i=1}^k w_j = 1</tex> , <tex>w_j\geq 0</tex>, <br />
::<tex>p(x) = \sum_{j=1}^k w_jp_j(x)</tex> , <tex>\sum_{i=1}^k w_j = 1</tex> , <tex>w_j\geq 0</tex>, <br />
Строка 12: Строка 12:
Задача разделения смеси заключается в том, чтобы, имея выборку <tex>X^m</tex> случайных и независимых наблюдений из смеси <tex>p(x)</tex>, зная число <tex>k</tex> и функцию <tex>\varphi</tex>, оценить вектор параметров <tex>\Theta = (w_1,...,w_k,\theta_1,...,\theta_k)</tex>.
Задача разделения смеси заключается в том, чтобы, имея выборку <tex>X^m</tex> случайных и независимых наблюдений из смеси <tex>p(x)</tex>, зная число <tex>k</tex> и функцию <tex>\varphi</tex>, оценить вектор параметров <tex>\Theta = (w_1,...,w_k,\theta_1,...,\theta_k)</tex>.
 +
== Основной алгоритм ==
Идея алгоритма заключается в следующем. Искусственно вводится вспомогательный вектор скрытых переменных <tex>G</tex>, обладающий двумя замечательными свойствами. С одной стороны, он может быть вычислен, если известны значения вектора параметров <tex>\Theta</tex>. С другой стороны, поиск максимума правдоподобия сильно упрощается, если известны значения скрытых переменных.
Идея алгоритма заключается в следующем. Искусственно вводится вспомогательный вектор скрытых переменных <tex>G</tex>, обладающий двумя замечательными свойствами. С одной стороны, он может быть вычислен, если известны значения вектора параметров <tex>\Theta</tex>. С другой стороны, поиск максимума правдоподобия сильно упрощается, если известны значения скрытых переменных.
EM-алгоритм состоит из итерационного повторения двух шагов. На E-шаге вычисляется ожидаемое значение (expectation) вектора скрытых переменных <tex>G</tex> по текущему приближению вектора параметров <tex>\Theta</tex>. На М-шаге решается задача максимизации правдоподобия (maximization) и находится следующее приближение вектора <tex>\Theta</tex> по текущим значениям векторов <tex>G</tex> и <tex>\Theta</tex>.
EM-алгоритм состоит из итерационного повторения двух шагов. На E-шаге вычисляется ожидаемое значение (expectation) вектора скрытых переменных <tex>G</tex> по текущему приближению вектора параметров <tex>\Theta</tex>. На М-шаге решается задача максимизации правдоподобия (maximization) и находится следующее приближение вектора <tex>\Theta</tex> по текущим значениям векторов <tex>G</tex> и <tex>\Theta</tex>.
 +
 +
=== Смесь нормальных распределений ===
== Медианные модификации ЕМ-алгоритма ==
== Медианные модификации ЕМ-алгоритма ==

Версия 19:12, 3 января 2010

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

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

Содержание

Постановка задачи

Пусть плотность распределения на множестве X имеет вид смеси k распределений:

p(x) = \sum_{j=1}^k w_jp_j(x) , \sum_{i=1}^k w_j = 1 , w_j\geq 0,

где p_j(x) - функция правдоподобия j-й компоненты смеси, w_j - ее априорная вероятность.
Функции правдоподобия принадлежат параметрическому семейству распределений \varphi(x; \theta) и отличаются только значениями параметра p_j(x) = \varphi(x; \theta_j).

Задача разделения смеси заключается в том, чтобы, имея выборку X^m случайных и независимых наблюдений из смеси p(x), зная число k и функцию \varphi, оценить вектор параметров \Theta = (w_1,...,w_k,\theta_1,...,\theta_k).

Основной алгоритм

Идея алгоритма заключается в следующем. Искусственно вводится вспомогательный вектор скрытых переменных G, обладающий двумя замечательными свойствами. С одной стороны, он может быть вычислен, если известны значения вектора параметров \Theta. С другой стороны, поиск максимума правдоподобия сильно упрощается, если известны значения скрытых переменных.

EM-алгоритм состоит из итерационного повторения двух шагов. На E-шаге вычисляется ожидаемое значение (expectation) вектора скрытых переменных G по текущему приближению вектора параметров \Theta. На М-шаге решается задача максимизации правдоподобия (maximization) и находится следующее приближение вектора \Theta по текущим значениям векторов G и \Theta.

Смесь нормальных распределений

Медианные модификации ЕМ-алгоритма

Первая медианная модификация

Вторая медианная модификация

SEM-алгоритм

CEM-алгоритм

MCEM-алгоритм

GEM-алгоритм

Модификации с добавлением/удалением компонент

EM-алгоритм с добавлением компонент

SEM-алгоритм с удалением клмпонент

Личные инструменты