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

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

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

Версия 14:16, 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 гауссианы в синем классе, некоторые его элементы, далеко забравшиеся в чужой класс, были классифицированы правильно.

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

load 'iris2.data'
X = iris2(:,[3,4]);
Y = [ones([50,1]);2*ones([50,1]);3*ones([50,1])];
hold off
drawdata(X,Y,'*');
title('Irises classification')
xlabel('petal width, cm');
ylabel('petal length, cm');
legend('Iris Setosa','Iris Versicolour','Iris Virginica','Location','NorthWest');
[W,M,Sigma,k,Ytheta] = emlearn(X, Y, [2,20,0.0005])
[Yanswer] = emtest(X, M, Sigma, Ytheta);
drawdata(X,Yanswer,'o')

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

У каждого объекта есть 4 признака: длина лепестка, ширина лепестка, длина чашелистика, ширина чашелистика Для удобства изображения результатов будем использовать первые два признака.

Алгоритм хорошо отделил ирисы setosa от остальных, но допустил достаточное число ошибок при разделении ирисов versicolor и virginica. Это произошло потому, что алгоритм изначально решал задачу кластеризации и лишь потом задачу классификации, приписывая каждому кластеру номер наиболее хорошо приближаемого им класса. Для отделения последних двух классов можно использовать Линейные алгоритмы классификации, либо решать с помощью EM, но используя все 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»

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

@@ Строка 75: / Строка 75: @@
 *В качестве второго примера возьмем 2 плохо разделимых класса.
 [[Изображение:twobadclasses.png|400px]]
@@ Строка 83: / Строка 84: @@
 *Реальные данные
-Проверку алгоритма проведем на классической задаче: Ирисы Фишера
+<source lang="matlab">
-Объектами являются 3 типа ирисов: setosa, versicolor, virginica
+load 'iris2.data'
+X = iris2(:,[3,4]);
+Y = [ones([50,1]);2*ones([50,1]);3*ones([50,1])];
+hold off
+drawdata(X,Y,'*');
+title('Irises classification')
+xlabel('petal width, cm');
+ylabel('petal length, cm');
+legend('Iris Setosa','Iris Versicolour','Iris Virginica','Location','NorthWest');
+[W,M,Sigma,k,Ytheta] = emlearn(X, Y, [2,20,0.0005])
+[Yanswer] = emtest(X, M, Sigma, Ytheta);
+drawdata(X,Yanswer,'o')
+</source>
+Проверку алгоритма проведем на классической задаче: [http://archive.ics.uci.edu/ml/datasets/Iris Ирисы Фишера]
+Объектами являются 3 типа ирисов: [http://ru.wikipedia.org/wiki/%D0%98%D1%80%D0%B8%D1%81_%D1%89%D0%B5%D1%82%D0%B8%D0%BD%D0%B8%D1%81%D1%82%D1%8B%D0%B9 setosa], [http://en.wikipedia.org/wiki/Iris_versicolor versicolor], virginica
 [[Изображение:setosa.jpg|275px]]
@@ Строка 97: / Строка 112: @@
 [[Изображение:Ireses_sorted&centers.png|300px]]
-Алгоритм хорошо отделил ирисы setosa от остальных, но допустил достаточное число ошибок при разделении ирисов versicolor и virginica. Это произошло потому, что алгоритм изначально решал задачу кластеризации и лишь потом задачу классификации, приписывая каждому кластеру номер наиболее хорошо приближаемого им класса. Для отделения последних двух классов можно использовать линейные алгоритмы, либо решать с помощью EM, но используя все 4 признака.
+Алгоритм хорошо отделил ирисы setosa от остальных, но допустил достаточное число ошибок при разделении ирисов versicolor и virginica. Это произошло потому, что алгоритм изначально решал задачу кластеризации и лишь потом задачу классификации, приписывая каждому кластеру номер наиболее хорошо приближаемого им класса. Для отделения последних двух классов можно использовать [[Линейный классификатор | Линейные алгоритмы классификации]], либо решать с помощью [[EM алгоритм (пример) | EM]], но используя все 4 признака.
 == Исходный код ==

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

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

Версия 14:16, 2 мая 2009

Содержание

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

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

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

Исходный код

Смотри также

Литература

Просмотры

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

Навигация

Поиск

Инструменты