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

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

(Различия между версиями)

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

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

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

Содержание

1 Постановка задачи
2 Основной алгоритм
- 2.1 Смесь нормальных распределений
3 Медианные модификации ЕМ-алгоритма
- 3.1 Первая медианная модификация
- 3.2 Вторая медианная модификация
4 SEM-алгоритм
5 CEM-алгоритм
6 MCEM-алгоритм
7 GEM-алгоритм
8 Модификации с добавлением/удалением компонент
- 8.1 EM-алгоритм с добавлением компонент
- 8.2 SEM-алгоритм с удалением клмпонент

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

Пусть плотность распределения на множестве $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$ .

Е-шаг

Обозначим через $p(x,\theta_j)$ плотность вероятности того, что объект $x$ получен из $j$ -й компоненты смеси. По формуле условной вероятности

$p(x,\theta_j) = p(x)P(\theta_j |x) = w_jp_j(x)$ .

Введём обозначение

$g_{ij} \equiv P(\theta_j |x_i)$ .

Это неизвестная апостериорная вероятность того, что обучающий объект $x_i$ получен из $j$ -й компоненты смеси. Возьмём эти величины в качестве скрытых переменных.

$\sum_{j=1}^k g_{ij} = 1$ , для любого $i = 1, \dots, m$ , так как имеет смысл полной вероятности принадлежать объекту $x_i$ одной из $k$ компонент смеси. Из формулы Байеса

$g_{ij} = \frac{w_jp_j(x_i)}{\sum_{s=1}^k w_sp_s(x_i)}$ для всех $i, j$ .

М-шаг

Будем максимизировать логарифм полного правдоподобия:

$Q(\Theta) = \ln\prod_{i=1}^mp(x_i|w,\mu,\Sigma) = \sum_{i=1}^m\ln\sum_{j=1}^kw_jp_j(x_i) \rightarrow \max_{\Theta}$ .

Решая оптимизационную задачу Лагранжа с ограничением на сумму $w_j$ , находим:

$w_j = \frac1m sum_{i=1}^m g_{ij} , j = 1, \dots, k$

$\theta_j = arg max_{\theta} sum_{i=1}^m g_{ij}\ln\varphi(x_i,\theta) , j = 1, \dots, k$ .

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

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

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

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

SEM-алгоритм

CEM-алгоритм

MCEM-алгоритм

GEM-алгоритм

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

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

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

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%9C%D0%B0%D1%80%D0%B8%D0%BD%D0%B0/%D0%9F%D0%B5%D1%81%D0%BE%D1%87%D0%BD%D0%B8%D1%86%D0%B0»

@@ Строка 24: / Строка 24: @@
 Это неизвестная апостериорная вероятность того, что обучающий объект <tex>x_i</tex> получен из <tex>j</tex>-й компоненты смеси. Возьмём эти величины в качестве скрытых переменных.
-<tex>sum{j=1}^k g_(ij) = 1</tex>,  для любого  <tex>i = 1, \dots, m</tex>, так как имеет смысл полной вероятности   принадлежать объекту <tex>х_i</tex> одной из <tex>k</tex> компонент смеси.
+<tex>\sum_{j=1}^k g_{ij} = 1</tex>,  для любого  <tex>i = 1, \dots, m</tex>, так как имеет смысл полной вероятности   принадлежать объекту <tex>x_i</tex> одной из <tex>k</tex> компонент смеси.
 Из формулы Байеса <br />
-::<tex>g_{ij} = frac{w_jp_j(x_i)}{sum{s=1}^k w_sp_s(x_i)} </tex>    для всех <tex>i, j</tex>.
+::<tex>g_{ij} = \frac{w_jp_j(x_i)}{\sum_{s=1}^k w_sp_s(x_i)} </tex>    для всех <tex>i, j</tex>.
 * '''М-шаг''' <br />
+Будем максимизировать логарифм полного правдоподобия: <br />
+::<tex>Q(\Theta) = \ln\prod_{i=1}^mp(x_i|w,\mu,\Sigma) = \sum_{i=1}^m\ln\sum_{j=1}^kw_jp_j(x_i) \rightarrow \max_{\Theta}</tex>. <br />
+Решая оптимизационную задачу Лагранжа с ограничением на сумму <tex>w_j</tex>, находим: <br />
+::<tex>w_j = \frac1m sum_{i=1}^m g_{ij} , j = 1, \dots, k </tex>
+::<tex>\theta_j = arg max_{\theta} sum_{i=1}^m g_{ij}\ln\varphi(x_i,\theta) , j = 1, \dots, k </tex>.
 === Смесь нормальных распределений ===