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

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

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

Версия 13:37, 2 мая 2009

Содержание

1 Постановка задачи
2 Алгоритм отыскания оптимальных параметров
3 Вычислительный эксперимент
4 Исходный код
5 Смотри также
6 Литература

EM-алгоритм с последовательным добавлением компонент (пример) — общий метод нахождения функции плотности распределения объектов. Предполагается, что она имеет вид смеси $k$ распределений. В данной статье рассматривается гауссовское распредение выборки, количество гауссианов произвольно.

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

Задана выборка $\{(\mathbf{x}_i,y_i)\}_{i=1}^{\ell}$ , в которой $X^{\ell}$ = $\{\mathbf{x}_i\}_{i=1}^{\ell}$ - множество объектов, $Y^{\ell}$ = $\{\mathbf{y}_i\}_{i=1}^{\ell}$ - множество ответов. Предполагается, что объекты имеют плотность распределения $p(x)$ , представимую в виде смеси $k$ гауссиан с параметрами $\mu$ и $\Sigma$ .

$p(x) = \sum_{i=1}^k w_jp_j(x) = \sum_{i=1}^k w_jN(x;\mu_j,\Sigma_j)$

Задача разделения смеси заключается в том, чтобы, имея выборку $X^m$ случайных и независимых наблюдений из смеси $p(x)$ оценить вектор параметров $\theta = (w_1,...,w_k,\mu_1,...,\mu_k,\Sigma_1,...,\Sigma_k)$ доставляющий максимум функции правдоподобия

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

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

Оптимальные параметры отыскиваются последовательно с помощью EM-алгоритма. Идея заключается во введении вспомогательного вектора скрытых переменных $G$ , обладающего двумя замечательными свойствами. С одной стороны, он может быть вычислен, если известны значения вектора параметров $\Theta$ , с другой стороны, поиск максимума правдоподобия сильно упрощается, если известны значения скрытых переменных. EM-алгоритм состоит из итерационного повторения двух шагов. На E-шаге вы- числяется ожидаемое значение (expectation) вектора скрытых переменных $G$ по те- кущему приближению вектора параметров $\Theta$ . На М-шаге решается задача максими- зации правдоподобия (maximization) и находится следующее приближение вектора $\Theta$ по текущим значениям векторов $G$ и $\Theta$ . Если число компонент смеси заранее не известно, то применяется EM-алгоритм с последовательным добавлением компонент. Если при каком-либо $k$ число неправильно классифицированных объектов превышает допустимое, то $k$ увеличивается и повторяется EM( $X,k_{new}$ )

Вход:

Выборка $X^m = \{x_1,...,x_m\}$ ; $R$ - максимальный допустимый разброс правдоподобия объектов; $m_0$ - минимальная длина выборки, по которой можно восстановить плотность; $\delta$ - параметр критерия останова;

Выход:

$k$ - число компонент смеси; $\Theta = (w_j,\mu_j,\Sigma_j)_{j=1}^k$

Алгоритм

1. начальное приближение - одна компонента:
     $k:=1; \qquad w_1:=1; \qquad \mu_1=\frac{1}{w_1}\sum_{i=1}^m g_{i1}x_i; \qquad \Sigma_1 = \frac{1}{mw_1}\sum_{i=1}^m g_{i1}(x_i-\mu_j)(x_i-\mu_j)^{T};$
2. для всех $k:= 2,3,4...$
3.      выделить объекты с низким правдоподобием
         $U:= \{x_i \in X^m\ | ~ p(x_i) < \frac{max_j ~ p(x_j)}{R} \}$
4.      Если $|U|<m_0$ то выход из цикла по $k$
5.      Начальное приближение для $k$ компоненты:
         $w_k:=\frac{1}{m}|U|; \qquad \mu_k=\frac{1}{mw_k}\sum_{i=1}^m g_{ik}x_i; \qquad \Sigma_k = \frac{1}{mw_k}\sum_{i=1}^m g_{ik}(x_i-\mu_j)(x_i-\mu_j)^{T};$
         $w_j:=w_j(1-w_k) \qquad j = 1,...,k-1;$
6.     $EM(X^m,k,\Theta,\delta);$

Вычислительный эксперимент

Алгоритм тестируется на модельных и реальных данных

Рассмотрим пример модельных данных. Выборка состоит из 4 классов. Первый класс представляет собой две гауссианы с диагональной и недиагоныльной матрицами ковариации, остальные - одна гауссиана.

[X1, Y1] = gengaussdata(150, [0;0], [1/4,1/2]);
[X2, Y2] = gengaussdata(150, [4;0], [1 5/6;5/6 1]);
[X4, Y4] = gengaussdata(120, [2;4], [1/10;1/10]);
[X3, Y3] = gengaussdata(200, [-2,2], [1/3, 1/3]);
[X5, Y5] = gengaussdata(200, [2,2], [1.25, 1/20]);
X=[X1;X2;X3;X4;X5];
%Y are answers (numbers of classes)
Y=[Y1;Y2;Y3+1;Y4+2;Y5+3];
hold off
drawdata(X,Y,'*');
%learning algorithm
[W,M,Sigma,k,Ytheta] = emlearn(X, Y, [2,40,0.001])
 
%testing and geting answers from algorithm
[Yanswer] = emtest(X, M, Sigma, Ytheta);
 
drawdata(X,Yanswer,'o');
 
%printing centers of classes according to algorithm decision
printcenters(M);

Истинное распределение классов показано на рисунке слева. Одинаковым цветом помечены элементы одного класса. Как можно заметить, некоторые представители "красныйх", "бирюзовых" и "синих" перемешались.

Качество обучения алгоритма проверяется на той же выборке. На правом рисунке кружками показаны полученные ответы, цвет отвечает за принадлежность к соответствующему классу. Центры классов, отмечены черным кружками. Алгоритм нашел восемь гауссовских распределений вместо четырех, причем одна из красных компонент описывается сразу 4 гауссианами, в то время как остальные компоненты выборки - одной. Этот факт говорит о том, что одна гауссиана плохо приближает данное распределение, и, для уменьшениея числа ошибок, следует приблизить её большим числом гауссиан. Алгоритм допустил 16 ошибок, что на выборке из 820 элементов составляет менее 2%.

В качестве второго примера возьмем 2 плохо разделимых класса.

Благодаря тому, что алгоритм выделил 4 гауссианы в синем классе, некоторые его элементы, далеко забравшиеся в чужой класс, были классифицированы правильно.

Реальные данные

Проверку алгоритма проведем на классической задаче: Ирисы Фишера Объектами являются 3 типа ирисов: setosa, versicolor, virginica

Iris Setosa

Iris Versicolor

Iris Virginica

У каждого объекта есть 4 признака: длина листа, ширина листа, длина чашелистика, ширина чашелистика

Исходный код

Скачать листинги алгоритмов можно здесь EMk.m, emlearn.m, emtest.m

Смотри также

Литература

К. В. Воронцов, Лекции по статистическим (байесовским) алгоритмам классификации

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

Студент: Участник:Кирилл Павлов

Преподаватель: Участник:В.В.Стрижов

Срок: 28 мая 2009

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

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

Источник — «http://machinelearning.ru/wiki/index.php?title=EM-%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D0%BC_%D0%B4%D0%BE%D0%B1%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5%D0%BC_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82_%28%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%29»

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

@@ Строка 73: / Строка 73: @@
 Качество обучения алгоритма проверяется на той же выборке. На правом рисунке кружками показаны полученные ответы, цвет отвечает за принадлежность к соответствующему классу. Центры классов, отмечены черным кружками. Алгоритм нашел восемь гауссовских распределений вместо четырех, причем одна из красных компонент описывается сразу 4 гауссианами, в то время как остальные компоненты выборки - одной. Этот факт говорит о том, что одна гауссиана плохо приближает данное распределение, и, для уменьшениея числа ошибок, следует приблизить её большим числом гауссиан.
 Алгоритм допустил 16 ошибок, что на выборке из 820 элементов составляет менее 2%.
+*В качестве второго примера возьмем 2 плохо разделимых класса.
+[[Изображение:twobadclasses.png|thumb]]
+[[Изображение:twobadclasses_sorted.png|thumb]]
+<br/>
+Благодаря тому, что алгоритм выделил 4 гауссианы в синем классе, некоторые его элементы, далеко забравшиеся в чужой класс, были классифицированы правильно.
+*Реальные данные
+Проверку алгоритма проведем на классической задаче: Ирисы Фишера
+Объектами являются 3 типа ирисов: setosa, versicolor, virginica
+[[Изображение:setosa.jpg|300 × 206]]
+Iris Setosa <br/>
+[[Изображение:versicolor.jpg|242 × 206]]
+Iris Versicolor
+[[Изображение:virginica.jpg|238 × 200]]
+Iris Virginica
+У каждого объекта есть 4 признака: длина листа, ширина листа, длина чашелистика, ширина чашелистика
 == Исходный код ==

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

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

Версия 13:37, 2 мая 2009

Содержание

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

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

Вычислительный эксперимент

Исходный код

Смотри также

Литература

Просмотры

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

Навигация

Поиск

Инструменты