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

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

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

Версия 23:02, 3 января 2010

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

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

Содержание

1 Постановка задачи
2 Основной алгоритм
- 2.1 Смесь нормальных распределений
3 Недостатки ЕМ-алгоритма
4 Медианные модификации ЕМ-алгоритма
- 4.1 Первая медианная модификация
- 4.2 Вторая медианная модификация
5 Стохастический EM-алгоритм (Stochastic, 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$ компонент смеси. Эта величина является структурным параметром алгоритма!

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

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

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

Далее будут приведены конечные результаты для смеси нормальных распределений. Математическое обоснование данного метода можно посмотреть в [2].

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

Введем следующие величины:
$\pi_{ij} = \frac{g_{ij}}{\sum_{i=1}^m g_{ij}},\: i = 1, \dots, m, \: j = 1, \dots, k$ ,
имеющие смысл некой вероятности.Введем также „фиктивные“ случайные величины $\x_j,\: j = 1, \dots, k$ , принимающие значения $x_i$ с вероятностями $\pi_{ij}$ . Переупорядочим значения $x_1, \dots, x_m$ случайной величины $\x_j$ по неубыванию, одновременно переставляя соответствующие данным значениям вероятности. Пусть $\pi_{(ij)}$ - вероятность, соответствующая значению $x_{(i)}$ . Положим:

$I_j = min(i: \pi_{(1j)} + \pi_{(2j)} + \dots + \pi_{(ij)} \geq \frac12)$ .

Тогда $\mu_j = med \x_j = x_{I_j}$ .

Пусть $m_j = med|\x_j - \mu_j|$ . Тогда $\sigma_j = 1.4826m_j$ .

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

Матожидание $\mu_j$ оценивается так же, как и в первой медианной модификации. Рассмотрим дисперсию $\sigma_j$ . Обозначим $s_j = \sum_{i=1}^m \pi_{ij}|x_i - \mu_j|$ .
Тогда $\sigma_j = 1.2533s_j$ .

Стохастический EM-алгоритм (Stochastic, SEM)

CEM-алгоритм

MCEM-алгоритм

GEM-алгоритм

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

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

Позволяет решить две проблемы сразу: проблему выбора числа компонент и проблему выбора начального приближения. Идея заключается в следующем. Имея некоторый набор компонент, можно выделить объекты $x_i$ , которые хуже всего описываются смесью - это объекты с наименьшими значениями правдоподобия $p(x_i)$ . По этим объектам строится ещё одна компонента. Затем она добавляется в смесь и запускаются EM-итерации, чтобы новая компонента и старые „притёрлись друг к другу“. Так продолжается до тех пор, пока все объекты не окажутся покрыты компонентами.
Более подробное описание алгоритма можно посмотреть в статье 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»

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

@@ Строка 72: / Строка 72: @@
 Тогда <tex>\sigma_j = 1.2533s_j</tex>.
-== SEM-алгоритм ==
+== Стохастический EM-алгоритм (Stochastic, SEM) ==
 == CEM-алгоритм ==