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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Литература)
(Исходный код)
 
(16 промежуточных версий не показаны.)
Строка 1: Строка 1:
{{TOCright}}
{{TOCright}}
-
'''EM-алгоритм с последовательным добавлением компонент''' — общий метод<ref>Неясно, что понимается под словами общий метод.</ref> нахождения функции плотности распределения объектов
+
'''EM-алгоритм с последовательным добавлением компонент''' — метод нахождения функции плотности объектов, представляющей смесь распределений.
-
<ref>Нужно найти более подробное и ясное определение (этого метода разделения смеси распределений).</ref>
+
В тех случаях, когда "форму" класса не удаётся описать каким-либо одним распределением, можно попробовать описать её смесью <tex>k</tex> распределений, каждое из которых описывается функцией правдоподобия <tex>p_j(x)</tex>.
-
. Предполагается, что она имеет вид смеси <tex>k</tex> распределений<ref>Здесь желательно объяснить более подробно.</ref>.
+
<center><tex>p(x) = \sum_{i=1}^k w_jp_j(x)</tex></center>
-
В данной статье рассматривается гауссовское распредение выборки, количество гауссианов произвольно<ref>Нужно исправить жаргонные термины на общепринятые.</ref>.
+
-
<ref>Желательно детализировать введение, в частности, указать наиболее известных авторов работавших в данной области, указать задачи, в которых используется алгоритм.</ref>
+
<tex>w_j</tex> - априорная вероятность <tex>j</tex>-й компоненты. Функции правдоподобия принадлежат параметрическому семейству распределений <tex>\varphi(x; \theta)</tex> и отличаются только значениями параметра <tex>p_j(x) = \varphi(x; \theta_j)</tex>
-
EM-алгоритм был предложен и исследован М.И.Шлезингером как инструмент для самопроизвольной классификации образов. Область его применения чрезвычайно широка: [[дискриминантный анализ]], [[кластеризация]], восстановление пропусков в данных, обработка сигналов и изображений.
+
''Задача разделения смеси'' заключается в том, чтобы, имея выборку <tex>X^m</tex> случайных и независимых наблюдений из смеси <tex>p(x)</tex>, зная число <tex>k</tex> и функцию <tex>\varphi</tex>, оценить вектор параметров <tex>\Theta = (w_1,...,w_k,\theta_1,...,\theta_k)</tex>
 +
 
 +
В данной статье рассматривается смесь гауссовских распределений выборки. Предполагается, что произвольную функцию распределения можно представить в виде их линейной комбинации. Количество компонент смеси, т.е. число гауссианов в линейной комбинации, произвольно.
 +
 
 +
 
 +
EM-алгоритм был предложен и исследован М.И.Шлезингером как инструмент для самопроизвольной классификации образов. Область его применения чрезвычайно широка: [[дискриминантный анализ]], [[кластеризация]], восстановление пропусков в данных, обработка сигналов и изображений. Алгоритм решает задачу [[исключающее или | исключающего или (XOR)]]
== Постановка задачи ==
== Постановка задачи ==
Строка 13: Строка 17:
<center><tex>p(x) = \sum_{i=1}^k w_jp_j(x) = \sum_{i=1}^k w_jN(x;\mu_j,\Sigma_j).</tex></center>
<center><tex>p(x) = \sum_{i=1}^k w_jp_j(x) = \sum_{i=1}^k w_jN(x;\mu_j,\Sigma_j).</tex></center>
 +
<center><tex>N(x;\mu_j,\Sigma_j) = \frac{1}{\sqrt{(2\pi)^ndet\Sigma_j}}e^{-\frac{1}{2}(x-\mu_j)\Sigma_j^{-1}(x-\mu_j)^{T}}</tex></center>
Задача разделения смеси заключается в том, чтобы, имея выборку <tex>X^m</tex>
Задача разделения смеси заключается в том, чтобы, имея выборку <tex>X^m</tex>
Строка 23: Строка 28:
по текущим значениям векторов <tex>G</tex> и <tex>\Theta</tex>.
по текущим значениям векторов <tex>G</tex> и <tex>\Theta</tex>.
-
Если число компонент смеси заранее неизвестно, то применяется EM-алгоритм с последовательным добавлением компонент. Если при каком-либо <tex>k</tex> число неправильно классифицированных объектов превышает допустимое, то <tex>k</tex> увеличивается и повторяется EM(<tex>X,k_{new}</tex>).
+
Если число компонент смеси заранее неизвестно, то применяется EM-алгоритм с последовательным добавлением компонент. Предположим, что смесь содержит одну компоненту (<tex>k=1</tex>) и проделаем алгоритм EM(<tex>X,1</tex>). Найдем плохо классифицированные элементы: Если функция правдоподобия на объекте меньше своего максимального значения в R раз, то добавим элемент ко множеству U. Параметр R выбирается на основании эвристических соображений, как правило <tex>R \in [2,10]</tex>. Множество U полагается пустым и увеличивается по мере добавления в него элементов. Если размер U оказался больше <tex>m_0</tex>, то считаем, что текущее распределение плохо описывает смесь. Текущее распределение определяется только числом компонент <tex>k</tex>. Увеличим
-
<ref>Желательно более подробно написать о свойствах этого варината алгоритма. Например, когда его следует останавливать?</ref>
+
его на единицу и запустим еще раз EM(<tex>X,k+1</tex>). Алгоритм остановится, когда число плохо классифицированных объектов будет меньше <tex>m_0</tex>. Этот параметр характеризует количество элементов, по которому можно восстановить гауссовское распределение. Как правило <tex>m_0 \geq 10</tex>
 +
*'''Вход:'''
*'''Вход:'''
Строка 49: Строка 55:
Алгоритм тестируется на модельных и реальных данных.
Алгоритм тестируется на модельных и реальных данных.
===Пример 1===
===Пример 1===
-
Рассмотрим пример на модельных данных. Выборка состоит из четырех классов. Первый класс представляет собой две гауссианы с диагональной и недиагональной матрицами ковариации, остальные - одна гауссиана.
+
Рассмотрим пример на модельных данных. Выборка состоит из четырех классов. Красный класс представляет собой смесь двух гауссовских распределений с диагональной и недиагональной матрицами ковариации. Остальные классы являются одним гауссовским рапределением.
-
<ref>Переписать последнее предложение, убрать неясности. При этом должно появиться по крайней мере три новых предложения.</ref>
+
Дисперсия зеленого класса меньше дисперсий остальных, поэтому его элементы находятся ближе к центру. Дисперсия бирюзовых по одной координате больше, чем по другой, в результате чего класс визуально вытянулся. Центры классов располагаются близко, некоторые классы линейно неразделимы.
-
 
+
<source lang="matlab">
<source lang="matlab">
[X1, Y1] = gengaussdata(150, [0;0], [1/4,1/2]);
[X1, Y1] = gengaussdata(150, [0;0], [1/4,1/2]);
Строка 81: Строка 87:
Качество обучения алгоритма проверяется на той же выборке. На правом рисунке кружками показаны полученные ответы, цвет отвечает за принадлежность к соответствующему классу. Центры классов, отмечены черным кружками. Алгоритм нашел восемь гауссовских распределений вместо четырех, причем одна из красных компонент описывается сразу 4 гауссианами, в то время как остальные компоненты выборки - одной. Этот факт говорит о том, что одна гауссиана плохо приближает данное распределение, и, для уменьшения числа ошибок, следует приблизить её большим числом гауссиан.
Качество обучения алгоритма проверяется на той же выборке. На правом рисунке кружками показаны полученные ответы, цвет отвечает за принадлежность к соответствующему классу. Центры классов, отмечены черным кружками. Алгоритм нашел восемь гауссовских распределений вместо четырех, причем одна из красных компонент описывается сразу 4 гауссианами, в то время как остальные компоненты выборки - одной. Этот факт говорит о том, что одна гауссиана плохо приближает данное распределение, и, для уменьшения числа ошибок, следует приблизить её большим числом гауссиан.
Алгоритм допустил 16 ошибок, что на выборке из 820 элементов составляет менее 2%.
Алгоритм допустил 16 ошибок, что на выборке из 820 элементов составляет менее 2%.
-
 
===Пример 2===
===Пример 2===
-
В качестве второго примера возьмем два плохо разделимых класса.
+
В качестве второго примера возьмем два плохо разделимых класса. Центры классов находятся на расстоянии меньшем дисперсии каждого из них. Можно наблюдать синие элементы, расположенные ближе к центру красного класса, чем к центру своего.
[[Изображение:twobadclasses.png|400px]]
[[Изображение:twobadclasses.png|400px]]
-
 
[[Изображение:twobadclasses_sorted.png|400px]]
[[Изображение:twobadclasses_sorted.png|400px]]
<br/>
<br/>
-
Благодаря тому, что алгоритм выделил четыре гауссианы в синем классе, некоторые его элементы, далеко забравшиеся в чужой класс, были классифицированы правильно.
+
Алгоритм выделил четыре гауссовских распределения в синем классе. Благодаря этому, хорошо классифицировались некоторые синие элементы, находящиеся ближе к красному классу.
-
<ref>Желательно переписать и развить предложение. Создается впечатление, что Пример 2 является частью Примера 1. Исключить двусмысленное "далеко забраться".</ref>
+
 
=== Ирисы Фишера ===
=== Ирисы Фишера ===
Строка 123: Строка 127:
[[Изображение:Ireses_sorted&centers.png|300px]]
[[Изображение:Ireses_sorted&centers.png|300px]]
-
Алгоритм хорошо отделил ирисы setosa от остальных, но допустил достаточное<ref>Достаточное для чего?</ref>число ошибок при разделении ирисов versicolor и virginica. Это произошло потому, что алгоритм изначально решал задачу кластеризации и лишь потом задачу классификации, приписывая каждому кластеру номер наиболее хорошо приближаемого им класса. Для разделения
+
Алгоритм хорошо отделил ирисы setosa от остальных, но допустил 30% ошибок при разделении ирисов versicolor и virginica. Это произошло потому, что алгоритм изначально решал задачу кластеризации и лишь потом задачу классификации, приписывая каждому кластеру номер наиболее хорошо приближаемого им класса. Для разделения последних двух классов можно использовать [[Линейный классификатор|линейные алгоритмы классификации]], либо решать с помощью [[EM алгоритм (пример)|EM-алгоритма]], используя все четыре признака.
-
<ref>Разделения или отделения, я правильно заменил слово?</ref>
+
-
последних двух классов можно использовать [[Линейный классификатор|линейные алгоритмы классификации]], либо решать с помощью [[EM алгоритм (пример)|EM-алгоритма]], используя все четыре признака.
+
== Исходный код ==
== Исходный код ==
-
Скачать листинги алгоритмов можно здесь [http://mlalgorithms.svn.sourceforge.net/viewvc/mlalgorithms/EMwithAddingComponents EMk.m, emlearn.m, emtest.m]
+
Скачать листинги алгоритмов можно здесь [http://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/Group674/Pavlov2009EMwithAdding]
== Смотри также ==
== Смотри также ==
* [[EM алгоритм (пример)|EM алгоритм]]
* [[EM алгоритм (пример)|EM алгоритм]]
 +
* [[ЕМ-алгоритм, его модификации и обобщения]]
* [[Метод ближайших соседей]]
* [[Метод ближайших соседей]]
* [[Линейный классификатор]]
* [[Линейный классификатор]]
Строка 142: Строка 145:
*[[Журавлёв, Юрий Иванович]] Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. 1978 Т. 33.С. 5–68.
*[[Журавлёв, Юрий Иванович]] Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. 1978 Т. 33.С. 5–68.
*Jordan M. I., Xu L. Convergence results for the EM algorithm to mixtures of experts architectures: Tech. Rep. A.I. Memo No. 1458: MIT, Cambridge, MA, 1993.
*Jordan M. I., Xu L. Convergence results for the EM algorithm to mixtures of experts architectures: Tech. Rep. A.I. Memo No. 1458: MIT, Cambridge, MA, 1993.
 +
*Шлезингер М., Главач В. Десять лекций по статистическому и структурному распознаванию. - Киев: Наукова думка, 2004. ISBN 966-00-0341-2
 +
*Шлезингер М. И. О самопроизвольном различении образов // Читающие автоматы. - Киев, Наукова думка, 1965
-
{{Задание|Кирилл Павлов|В.В.Стрижов|28 мая 2009}}
+
{{ЗаданиеВыполнено|Кирилл Павлов|В.В.Стрижов|28 мая 2009|Pavlov99|Strijov}}
-
[[Категория:Учебные материалы]]
+
-
==Замечания==
+
[[Категория:Оценивание вероятностных распределений]]
-
<references/>
+
[[Категория:Байесовская теория классификации]]
-
[[Категория:Классификация]]
+
[[Категория:Практика и вычислительные эксперименты]]
-
[[Категория:Прикладная статистика]]
+

Текущая версия

Содержание

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

p(x) = \sum_{i=1}^k w_jp_j(x)

w_j - априорная вероятность 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)

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


EM-алгоритм был предложен и исследован М.И.Шлезингером как инструмент для самопроизвольной классификации образов. Область его применения чрезвычайно широка: дискриминантный анализ, кластеризация, восстановление пропусков в данных, обработка сигналов и изображений. Алгоритм решает задачу исключающего или (XOR)

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

Задана выборка \{(\mathbf{x}_i,y_i)\}_{i=1}^m, в которой X^m = \{\mathbf{x}_i\}_{i=1}^m - множество объектов, Y^m = \{\mathbf{y}_i\}_{i=1}^m - множество ответов. Предполагается, что на множестве объектов задана плотность распределения 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).
N(x;\mu_j,\Sigma_j) = \frac{1}{\sqrt{(2\pi)^ndet\Sigma_j}}e^{-\frac{1}{2}(x-\mu_j)\Sigma_j^{-1}(x-\mu_j)^{T}}

Задача разделения смеси заключается в том, чтобы, имея выборку 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=1) и проделаем алгоритм EM(X,1). Найдем плохо классифицированные элементы: Если функция правдоподобия на объекте меньше своего максимального значения в R раз, то добавим элемент ко множеству U. Параметр R выбирается на основании эвристических соображений, как правило R \in [2,10]. Множество U полагается пустым и увеличивается по мере добавления в него элементов. Если размер U оказался больше m_0, то считаем, что текущее распределение плохо описывает смесь. Текущее распределение определяется только числом компонент k. Увеличим его на единицу и запустим еще раз EM(X,k+1). Алгоритм остановится, когда число плохо классифицированных объектов будет меньше m_0. Этот параметр характеризует количество элементов, по которому можно восстановить гауссовское распределение. Как правило m_0 \geq 10


  • Вход:

Выборка 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);

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

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

Пример 1

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

[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);

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

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

Пример 2

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


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


Ирисы Фишера

Проверку алгоритма проведем на классической задаче: Ирисы Фишера Объектами являются три типа ирисов: 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')

Алгоритм хорошо отделил ирисы setosa от остальных, но допустил 30% ошибок при разделении ирисов versicolor и virginica. Это произошло потому, что алгоритм изначально решал задачу кластеризации и лишь потом задачу классификации, приписывая каждому кластеру номер наиболее хорошо приближаемого им класса. Для разделения последних двух классов можно использовать линейные алгоритмы классификации, либо решать с помощью EM-алгоритма, используя все четыре признака.

Исходный код

Скачать листинги алгоритмов можно здесь [1]

Смотри также

Литература

  • К. В. Воронцов, Лекции по статистическим (байесовским) алгоритмам классификации
  • Bishop C. - Pattern Recognition and Machine Learning (Springer, 2006)
  • The on-line textbook: Information Theory, Inference, and Learning Algorithms, by David J.C. MacKay includes simple examples of the EM-algorithm such as clustering using the soft K-means algorithm, and emphasizes the variational view of the EM-algorithm.
  • Журавлёв, Юрий Иванович Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. 1978 Т. 33.С. 5–68.
  • Jordan M. I., Xu L. Convergence results for the EM algorithm to mixtures of experts architectures: Tech. Rep. A.I. Memo No. 1458: MIT, Cambridge, MA, 1993.
  • Шлезингер М., Главач В. Десять лекций по статистическому и структурному распознаванию. - Киев: Наукова думка, 2004. ISBN 966-00-0341-2
  • Шлезингер М. И. О самопроизвольном различении образов // Читающие автоматы. - Киев, Наукова думка, 1965


Данная статья была создана в рамках учебного задания.
Студент: Кирилл Павлов
Преподаватель: В.В.Стрижов
Срок: 28 мая 2009


В настоящее время задание завершено и проверено. Данная страница может свободно правиться другими участниками проекта MachineLearning.ru.

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

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