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

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

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

Версия 20:13, 3 января 2010

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

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

Содержание

1 Постановка задачи
2 Основной алгоритм
- 2.1 Смесь нормальных распределений
3 Недостатки ЕМ-алгоритма
4 Медианные модификации ЕМ-алгоритма
- 4.1 Первая медианная модификация
- 4.2 Вторая медианная модификация
5 SEM-алгоритм
6 CEM-алгоритм
7 MCEM-алгоритм
8 GEM-алгоритм
9 Модификации с добавлением/удалением компонент
- 9.1 EM-алгоритм с добавлением компонент
- 9.2 SEM-алгоритм с удалением клмпонент
10 Смотрите также
11 Литература

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

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

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

Далее часто будет встречаться смесь нормальных распределений, поэтому выпишем для нее результаты Е- и М-шага алгоритма:
$\theta = (w_1,...,w_k;\mu_1,...,\mu_k;\sigma_1,...,\sigma_k)$
$p_j(x) = N(x;\mu_j, \sigma_j) = \frac1{\sqrt{2\pi}\sigma_j}exp{-\frac{(x - \mu_j)^2}{2\sigma_j^2}}$

E-шаг

$g_{ij} = \frac{w_jN(x_i;\mu_j, \sigma_j)}{\sum_{s=1}^k w_sN(x_i;\mu_s, \sigma_s)}$

М-шаг

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

$\mu_j = \frac1{mw_j}\sum_{i=1}^m g_{ij}x_i$ ,

$\sigma_j^2 = \frac1{mw_j}\sum_{i=1}^m g_{ij}(x_i - \mu_j)^2,\; j = 1, \dots, k$ .

Недостатки ЕМ-алгоритма

ЕМ-алгоритм неуйстойчив по начальным данным (то есть тем, которые инициализируют вектор параметров $\theta$ на первой итерации), так как он находит локальный экстремум, значение которого может оказаться гораздо ниже, чем глобальный максимум. В зависимости от выбора начального приближения алгоритм может сходиться к разным точкам. Также может сильно варьироваться скорость сходимости.
ЕМ-алгоритм не позволяет определять количество $k$ компонент смеси. Эта величина является структурным параметром алгоритма!

В связи с этим рассмотрим некоторые модификации ЕМ-алгоритма, так или иначе противоборствующие данным недостаткам. ??????

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

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

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

SEM-алгоритм

CEM-алгоритм

MCEM-алгоритм

GEM-алгоритм

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

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

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

Смотрите также

Литература

Данная статья является непроверенным учебным заданием.

Студент: Участник:Марина

Преподаватель: Участник:Константин Воронцов

Срок: 8 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Источник — «http://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»

Категория: Непроверенные учебные задания

@@ Строка 27: / Строка 27: @@
 Из формулы Байеса <br />
 ::<tex>g_{ij} = \frac{w_jp_j(x_i)}{\sum_{s=1}^k w_sp_s(x_i)} </tex>    для всех <tex>i, j</tex>.
 * '''М-шаг''' <br />
@@ Строка 33: / Строка 32: @@
 ::<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>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>.
+::<tex>\theta_j = arg \max_{\theta} \sum_{i=1}^m g_{ij}\ln\varphi(x_i,\theta) ,\: j = 1, \dots, k </tex>.
 === Смесь нормальных распределений ===
+Далее часто будет встречаться смесь нормальных распределений, поэтому выпишем для нее результаты Е- и М-шага алгоритма: <br />
+<tex>\theta = (w_1,...,w_k;\mu_1,...,\mu_k;\sigma_1,...,\sigma_k)</tex> <br />
+<tex>p_j(x) = N(x;\mu_j, \sigma_j) = \frac1{\sqrt{2\pi}\sigma_j}exp{-\frac{(x - \mu_j)^2}{2\sigma_j^2}} </tex>
+* E-шаг <br />
+::<tex>g_{ij} = \frac{w_jN(x_i;\mu_j, \sigma_j)}{\sum_{s=1}^k w_sN(x_i;\mu_s, \sigma_s)} </tex>
+* М-шаг <br />
+::<tex>w_j = \frac1m\sum_{i=1}^m g_{ij}</tex> ,
+::<tex>\mu_j = \frac1{mw_j}\sum_{i=1}^m g_{ij}x_i</tex> ,
+::<tex>\sigma_j^2 = \frac1{mw_j}\sum_{i=1}^m g_{ij}(x_i - \mu_j)^2,\; j = 1, \dots, k</tex>.
+== Недостатки ЕМ-алгоритма ==
+# ЕМ-алгоритм неуйстойчив по начальным данным (то есть тем, которые инициализируют вектор параметров <tex>\theta</tex> на первой итерации), так как он находит локальный экстремум, значение которого может оказаться гораздо ниже, чем глобальный максимум. В зависимости от выбора начального приближения алгоритм может сходиться к разным точкам. Также может сильно варьироваться скорость сходимости.
+# ЕМ-алгоритм не позволяет определять количество <tex>k</tex> компонент смеси. Эта величина является структурным параметром алгоритма!
+В связи с этим рассмотрим некоторые модификации ЕМ-алгоритма, так или иначе противоборствующие данным недостаткам. ??????
 == Медианные модификации ЕМ-алгоритма ==
@@ Строка 57: / Строка 73: @@
 === SEM-алгоритм с удалением клмпонент ===
+== Смотрите также ==
+== Литература ==
+{{Задание|Марина|Константин Воронцов|8 января 2010}}