EM алгоритм (пример)

EM алгоритм – общий метод нахождения оценок функции правдоподобия в моделях со скрытыми переменными. В данной статье рассматривается интерпретация смеси гауссовых распределений в терминах дискретных скрытых переменных.

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

Постановка задачи разделения смеси гауссовых распределений

Задана выборка X^{l} случайных и независимых наблюдений из смеси p(x) ,в которой описание i -ого элемента есть вектор x_{i} \in R^{n} . Принята модель, в которой каждая компонента смеси есть гауссина с параметрами \mu и \Sigma, и известно число компонент смеси – K,

p(x)=\sum_{k=1}^K \pi_{k}\aleph(x|\mu_{k},\Sigma_{k}).
Требуется оценить вектор параметров \theta=(\pi_{1},...,\pi_{k};\mu_{1},...,\mu_{k};\Sigma_{1},...,\Sigma_{k}), доставляющий максим функции правдоподобия,

\ln p(X|\pi,\mu,\Sigma)= \sum_{n=1}^N \ln \{ \sum_{k=1}^K \pi_{k}\aleph(x_{n}|\mu_{k},\Sigma_{k})\}.

Алгоритм отыскания оптимальных параметров

Оптимальные параметры отыскиваются последовательно с помощью итерационного EM-алгоритма. Основная идея – вводится вспомогательный вектор скрытых переменных. Это позволяет свести сложную оптимизационную задачу к последовательности итераций по пересчету коэффициентов (скрытых переменных по текущему приближению вектора параметров – E-шаг) и максимизации правдоподобия (с целью найти следующее приближение вектора – М-шаг).

  1. В начале работы алгоритма задаются параметры начального приближения, которые в данной статье получаются в результате работы алгоритма kMeans. (Данная эвристика применяется, так как kMeans требуется намного меньше итераций до достижения стабилизации, в то время как каждый шаг EM требует больших вычислительных затрат).
  2. Далее итеративно выполняется следующая пара процедур:
  • E-шаг: используя текущее значение вектора параметров \theta=(\pi_{1},...,\pi_{k};\mu_{1},...,\mu_{k};\Sigma_{1},...,\Sigma_{k}), вычисляем значение вектора скрытых переменных \gamma,

\gamma_{nk}=\frac{\pi_{k}\aleph(x_{n}|\mu_{k},\Sigma_{k})}{\sum_{j=1}^K \pi_{j}\aleph(x_{n}|\mu_{j},\Sigma_{j})}.

  • М-шаг: переоценка вектора параметров, используя текущее значение вектора скрытых переменных,

\mu^{new}_{k}=\frac{1}{N_{k}}\sum_{n=1}^N \gamma_{nk}x_{n},
\Sigma^{new}_{k}=\frac{1}{N_{k}}\sum_{n=1}^N \gamma_{nk} (x_{n}-\mu_{k}^{new})(x_{n}-\mu_{k}^{new})^{T},
\pi_{k}^{new}=\frac{N_{k}}{N},
N_{k}=\sum_{n=1}^N \gamma_{nk}, где \delta_{max}>\Delta.
Процедура останавливается после того, как норма разности векторов скрытых переменных на каждой итерации не будет превышать заданную константу,

\delta_{max}=max{\{\delta_{max},|\gamma_{nk}-\gamma^{0}_{nk}|\}}.

Пример на модельных данных

Продемонстрирована работа алгоритма на серии реальных и синтетических данных. 1) Old Faithful – гидродинамический гейзер в Yellowstone National Park. Данные содержат информацию о 272-х извержениях, каждое из которых есть пара характеризующая длительность извержения и время до следующего извержения (в минутах). Ссылка на данные. Old Faithful

300px-Old_faithful

300px-Old_faithful_data

На графике выше показаны иcходные данные. По оси x отложено значение одного признака (время извержения в мин.), по оси y – соответственно значение второго признака. Цвет точек означает принадлежность к тому или иному классу.

 

Классы определены алгоритмом абсолютно (ошибок нет), сложность задачи – легкая, так как видно что классы линейно-разделимы и расстояние между центрами классов велико.

2) Синтетические данные (легкий случай, 3 класса)


300px-Light_data

В данном примере заметно небольшое взаимное проникновение классов друг в друга, что влечет к частично ошибочной классификации (метки в результате работы алгоритма EM сравниваются с известными). Аналогично предыдущему примеру по оси абсцисс значение первого признака, по оси ординат – второго. Цвет – принадлежность классу.

3) Синтетические данные (тяжелый случай, 2 класса)


300px-Hard_data_pre

Отображение исходных данных с истинными метками классов

300px-Hard_data_result

На рисунке приведены результаты работы алгоритма на данных, изображенных на рисунке выше. Стоит заметить, что даже при сильном взаимном проникновении классов, алгоритм показывает достойный результат. Интересным является также правильная классификация нескольких точек, находящихся «глубоко» в чужом классе. На самом деле это зависит от положения центров кластеров и их формы.

 

Источник

comments powered by HyperComments