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

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

(Перенаправлено с EM-алгоритм)

Содержание

1 Постановка задачи
2 Основной алгоритм
- 2.1 Смесь нормальных распределений
- 2.2 Недостатки основного алгоритма
3 Медианные модификации ЕМ-алгоритма
- 3.1 Первая медианная модификация
- 3.2 Вторая медианная модификация
4 Стохастический EM-алгоритм (Stochastic, SEM)
5 Классификационный EM-алгоритм (Classification, CEM)
6 Обобщенный EM-алгоритм (Generalized, GEM)
7 Модификации с добавлением/удалением компонент
- 7.1 EM-алгоритм с добавлением компонент
- 7.2 SEM-алгоритм с удалением компонент
8 Краткое резюме
9 Смотрите также
10 Литература

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

Как правило, ЕМ-алгоритм применяется для решения задач двух типов.

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

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

Пусть плотность распределения на множестве $X$ имеет вид смеси $k$ распределений:

$p(x) = \sum_{j=1}^k w_jp_j(x),\quad \sum_{i=1}^k w_j = 1,\quad 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$ .

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

На М-шаге решается задача максимизации правдоподобия (maximization) и находится следующее приближение вектора $\Theta$ по текущим значениям векторов $G$ и $\Theta$ .

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

$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$ .

Таким образом, M-шаг сводится к вычислению весов компонент $w_j$ как средних арифметических и оцениванию параметров компонент $\theta_j$ путём решения $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 \biggl(-\frac{(x - \mu_j)^2}{2\sigma_j^2}\biggr)$ — плотность распределения.

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 = \mathrm{med} \x_j = x_{I_j}$ .

Пусть $m_j = \mathrm{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 = \mathrm{arg}\max_{\theta} \sum_{i=1}^m g_{ij}\ln\varphi(x_i,\theta)$ ,

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

$\theta_j = \mathrm{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-алгоритму с фиксированным числом компонент.

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

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