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

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

Перейти к: навигация, поиск

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.

  • Е-шаг

Обозначим через 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.

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

  1. ЕМ-алгоритм неуйстойчив по начальным данным (то есть тем, которые инициализируют вектор параметров \theta на первой итерации), так как он находит локальный экстремум, значение которого может оказаться гораздо ниже, чем глобальный максимум. В зависимости от выбора начального приближения алгоритм может сходиться к разным точкам. Также может сильно варьироваться скорость сходимости.
  2. ЕМ-алгоритм не позволяет определять количество 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.

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

SEM-алгоритм

CEM-алгоритм

MCEM-алгоритм

GEM-алгоритм

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

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

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

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

Литература

Данная статья является непроверенным учебным заданием.
Студент: Участник:Марина
Преподаватель: Участник:Константин Воронцов
Срок: 8 января 2010

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

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


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