ЕМ-алгоритм, его модификации и обобщения

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

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

Марина (Обсуждение | вклад)
(Новая: '''EM-алгоритм''' (англ. expectation-maximization) - алгоритм, используемый в математической статистике для нахождени...)
К следующему изменению →

Версия 13:41, 4 января 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 Классификационный EM-алгоритм (Classification, CEM)
7 Обобщенный EM-алгоритм (Generalized, GEM)
8 Модификации с добавлением/удалением компонент
- 8.1 EM-алгоритм с добавлением компонент
- 8.2 SEM-алгоритм с удалением компонент
9 Краткое резюме
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) = \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)

Классический ЕМ-алгоритм относится к так называемым „жадным“ алгоритмам, то есть он бросается на первый попавшийся локальный максимум, который, как уже упоминалось, может сильно отличаться от глобального. Одним из способов борьбы является как бы случайное, но целенаправленное „встряхивание“ выборки на каждой итерации. Такая рандомизация „выбивает“ оптимизационный процесс из локальных максимумов, так что:

SEM работает относительно быстро, и его результаты практически не зависят от начального приближения;
как правило, SEM находит экстремум $Q(\Theta)$ , близкий к глобальному.

Пусть вся выборка $X^m$ разбита на кластеры $K_j,\: j = 1, \dots, k$ : каждый элемент $x_i$ относится к единственному(!) кластеру $K_j$ , то есть утверждается, что данный элемент взят из $j$ компоненты смеси.

S-шаг

На первом этапе SEM-алгоритма производится так называемое стохастическое моделирование. Для каждого $i = 1, \dots, m$ генерируется вектор $y_i = (y_{i1}, y_{i2, \dots, y_{ik}})$ как реализация случайного вектора из полиномиального распределения с параметрами 1 и $g_{ij}$ , где $g_{ij}$ - это вероятность того, что величина $y_{ij}$ равна 1. По векторам $y_i$ определяется разбиение выборки $X^m$ на кластеры $K_j$ и соответствующие численности кластеров $\nu_1, \dots, \nu_k$ .

Е-шаг

Остается без изменений.

М-шаг

Пересчитываются веса:

$w_j = \frac{\nu_j}{m}$

и вместо максимизации взвешенного правдоподобия:

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

решается задача обычного невзвешенного правдоподобия:

$\theta_j = arg \max_{\theta} \sum_{x_i \in K_j} \ln\varphi(x_i,\theta)$ .

Для SEM-алгоритма также существуют медианные модификации. Ознакомиться с ними можно в [2].

Классификационный EM-алгоритм (Classification, CEM)

Этот алгоритм совпадает с SEM-алгоритмом, за исключением того, что вместо S-шага используется детерминированное правило, эквивалентное классификации по принципу максимума апостериорной вероятности, то есть $x_i$ приписывается тому кластеру, номер которого совпадает с номером наибольшего из чисел $g_{i1}, \dots, g_{ik}$ . Формулы для оценок параметров аналогичны SEM-алгоритму.

Обобщенный EM-алгоритм (Generalized, GEM)

В тех случаях, когда максимизация функционала $Q(\Theta)$ ,имеющего смысл полного правдоподобия, по каким-либо причинам затруднена, применяется подход, в котором достаточно лишь сместиться в сторону максимума значения функционала, сделав одну или несколько итераций на М-шаге. Этот алгоритм также обладает неплохой сходимостью.

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

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

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

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

Решает проблему выбора компонент и „застоя“ в локальном максимуме.

До начала работы алгоритма фиксируются два числа:

$K$ - максимально возможное число компонент, которое определяется соображениями практической интерпретируемости полученного результата;
$\nu_0$ -минимально допустимое число наблюдений в одном кластере, которое выбирают исходя из минимально допустимой значимости компонент. Если нецелесообразно считать значимыми компоненты, веса которых меньше некоторого заданного (малого) значения $\alpha$ , то $\nu_0 = \alpha m$ , где $m$ - объем выборки.

Начальное число компонент смеси равно $K$ . Далее это число может только уменьшаться:
в результате стохастического моделирования на S-шаге SEM-алгоритма могут возникнуть кластеры, для которых $\nu_j \leq \nu_0$ . Тогда данный кластер аннулируется, то есть

Переопределяются апостериорные вероятности $g_{ij}$ .
Элементы выборки, попавшие в аннулированные классы, перераспределяются по „достаточно представительным“ кластерам.
Переопределяется число компонент смеси.

Формулы для оценок параметров аналогичны SEM-алгоритму с фиксированным числом компонент.

Краткое резюме

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

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

Литература

К.В.Воронцов „Лекции по статистическим (байесовским) алгоритмам классификации“
В.Ю.Королев „ЕМ-алгоритм, его модификации и их применение к задаче разделения смесей вероятностных рспределений“.

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

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

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

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

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

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

Источник — «http://recognition.su/wiki/index.php?title=%D0%95%D0%9C-%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%2C_%D0%B5%D0%B3%D0%BE_%D0%BC%D0%BE%D0%B4%D0%B8%D1%84%D0%B8%D0%BA%D0%B0%D1%86%D0%B8%D0%B8_%D0%B8_%D0%BE%D0%B1%D0%BE%D0%B1%D1%89%D0%B5%D0%BD%D0%B8%D1%8F»

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