Изменения

Перейти к: навигация, поиск

EM-алгоритм

320 байт добавлено, 21 март
Исправил положение точки
Плотность распределения смеси имеет вид:<br/>
<tex>p(x) = \sum\limits_{j=1}^k w_j p_j(x)</tex>.<br/>
Где <tex> \sum\limits_{j=1}^k w_j = 1; w_j \geq 0; p_j(x) = \phi(x;\theta_j)</tex> {{---}} функция правдоподобия <tex>j</tex>-ой компонеты смеси, <tex>w_j</tex> {{---}} априорная вероятность <tex>j</tex>-ой компоненты смеси.<br/>
Перед нами стоит две задачи:<br/>
# По заданной выборке <tex>X^m</tex> случайных и независимых наблюдений полученных из смеси <tex>p(x)</tex>, числу <tex>k</tex> и функции <tex>\phi</tex>, оценить вектор параметров <tex>\Theta = (w_1,..,w_k,\theta_1,..,\theta_k)</tex>.
# Найти <tex>k</tex>.
Задачи подобного рода мы умеем решать, максимизируя логармиф правдоподобия:<br>
<tex> LQ(\Theta) = ln \prod\limits_{i=1}^mp(x_i) = \sum\limits_{i=1}^m ln\sum\limits_{j=1}^k w_j p_j(x_i; \theta_j) \longrightarrow \max\limits_{\Theta}</tex>.<br/>
Но проблeма в том, что мы не знаем как аналитически посчитать логарифм суммы. Тут нам и поможет алгоритм EM.
Основная идея алгоритма EM заключается в том, что мы добавляем скрытые переменные такие, что:<br/>
# Они могут быть выражены через <tex>\Theta</tex>.# Они помогают разбить сумму так: <tex>p (X, H|\Theta) = \prod\limits_{i=1}^k p (X|H, \Theta) p(H|\Theta)</tex>, где <tex>H</tex> {{--- }} матрица скрытых переменных.
Тогда алгоритм EM сводится к повторению шагов, указанных в [[#Определение|Определении]].
=== E-шаг ===
<tex>p(x,\theta_j) = p(x)P(\theta_j | x) = w_jp_j(x)</tex> .<br />
Скрытые переменные представляют из себя матрицу <tex>H = (h_{ij})_{m \times k}</tex>,<br/>
где <tex>h_{ij} = P(\theta_j | x_i)</tex> {{---}} вероятность того, что <tex>x_i</tex> пренадлежит <tex>j</tex>-ой компоненте.<br/>
По формуле Байеса справедливо равенство:<br />
<tex> h_{ij} = \frac{w_jp_j(x_i)}{p (x_i)} = \frac{w_jp_j(x_i)}{\sum\limits_{s=1}^k w_s p_s(x_i)}</tex>.<br/>
Также <tex>\sum\limits_{j=1}^k h_{ij} = 1</tex>.<br/>
Таким образом, зная значения вектора параметров <tex>\Theta</tex>, мы легко можем пересчитать значения скрытых переменных.<br/>
=== M-шаг ===
|statement=
Если известны скрытые переменные, то задача минимизации <tex>Q(\Theta)</tex> сводится к <tex>k</tex> независимым подзадачам:<br/>
<center><tex>\theta_j = \arg\max\limits_{\theta}\sum\limits_{i=1}^m h_{ij}*\ln\phi(x_i;\theta)</tex>.</center>
Оптимальные же веса считаются как:<br/>
<center><tex> w_j = \frac {1} {m} \sum\limits_{i=1}^m h_{ij}</tex>.</center>
|proof=
Посчитаем логарифм правдоподобия:<br>
<tex> Q(\Theta) = \sum\limits_{i=1}^m ln\sum\limits_{j=1}^k w_j p_j(x_i; \theta_j) \longrightarrow \max\limits_{\Theta}</tex>.<br/>
При условии, что<tex> \sum\limits_{j=1}^k w_j = 1; w_j \geq 0</tex> имеет смысл рассматривать Лагранжиан задачи:<br/>
<tex> L(\Theta, X^m) = \sum\limits_{i=1}^m ln \biggl( \sum\limits_{j=1}^k w_j p_j(x_i) \biggr) - \lambda \biggl(\sum\limits_{j=1}^k w_j - 1 \biggr) </tex>.<br/>
Приравняв нулю производную Лагранжиана по <tex>w_j</tex>, получим:<br/>
<tex>\frac{\partial L} {\partial w_j} = \sum\limits_{i=1}^m \frac{p_j(x_i)}{\sum\limits_{s=1}^kw_s p_s(x_i)} - \lambda = 0, j = 1..k</tex>.<br />Умножим на <tex>w_j</tex> и просуммируем уравнения для всех <tex>j</tex> :<br /><tex>\sum\limits_{j=1}^k \sum\limits_{i=1}^m \frac{w_jp_j(x_i)}{\sum\limits_{s=1}^kw_s p_s(x_i)} = \lambda \sum\limits_{j=1}^kw_j</tex> .<br />А так как <tex>\sum\limits_{j=1}^k \frac{w_jp_j(x_i)}{\sum\limits_{s=1}^kw_sp_s(x_i)} = 1</tex> и <tex>\sum\limits_{j=1}^kw_j = 1</tex>, из чего следует <tex>\lambda = m</tex> .<br />
<tex>w_j = \frac{1}{m}\sum\limits_{i=1}^m \frac{w_jp_j(x_i)}{\sum\limits_{s=1}^kw_sp_s(x_i)} = \frac{1}{m}\sum\limits_{i=1}^m h_{ij}</tex>.<br />
Приравняв к нулю производную Лагранжиана по <tex>\theta_j</tex>, схожим способом найдем:<br />
=== Критерий остановки ===
Алгоритм EM вы полняется выполняется до сходимости, но как нам определить, что сходимость наступила? Мы можем останавливаться, когда либо <tex>Q(\Theta)</tex>, либо <tex>H</tex> перестают сильно меняться. Но, обычно, удобней контролировать изменения значений скрытых переменных, так как они имеют смысл вероятностей и принимают значения из отрезка <tex>[0,1]</tex>. Поэтому один из возможных критериев остановки будет выглядеть так: <tex>\max\limits_{i,j} |h_{ij} - h_{ij}^{(0)}| > \delta</tex>.
=== Псевдокод ===
Плюсы:<br/>
* Сходится в большинтсве случаев.* Наиболее гибкое решение.* Существуют простые модификации, позволяющие уменьшить чуствительность алгоритма к шуму в данных.
Минусы:<br/>
* Чуствителен к начальному приближению. Могут быть ситуации, когда сойдемся к локальному экстремуму.* Число компонент <tex>k</tex> является [[Настройка_гиперпараметров|гиперпараметром]].
== Модификации ==
Базовый алгоритм EM является очень гибким для модификаций, позволяющих улучшить его работу. В этом разделе мы приведем краткое описаниен описание некоторых из них.
=== Generalized EM-algorithm ===
=== Stochastic EM-algorithm ===
Как уже было отмечено в [[#Плюсы_и_минусы|Плюсы и минусы]], базовый алгоритм чувствителен к начальному приближению и могут быть ситуации, когда алгоритм "застрянет" в лоакльном локальном экстремуме. Для того, чтобы предотвратить это, будем на каждой итерации алгоритма случайно "встряхивать" выборку. В этой модификации у нас добавляется шаг S, на котором мы и будем "встряхивать" выборку. И на шаге M мы будем решать уже задачу максимуму невзвешенного правдоподобия. Эта модификация хороша тем, что нечуствиетльная к начальном приблежению.
== Пример. Разделение смеси Гауссиана ==
<tex>\theta = (w_1,..,w_k;\;\mu_1,..,\mu_k;\;\sigma_1,..,\sigma_k)</tex> {{---}} вектор параметров, <br/>
<tex>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) </tex> {{- --}} плотность распределения .<br/>
Посчитаем значения для каждого шага. <br/>
E-шаг:
: <tex> h_{ij} = \frac{w_j N(x_i, \mu_j, \sigma_j)}{\sum\limits_{s=1}^k w_s N(x_i, \mu_s, \sigma_s)} .</tex>
M-шаг:
: <tex>w_j = \frac{1}{m} \sum\limits_{i=1}^m h_{ij}.</tex>: <tex> \mu_j = \frac {1} {mw_j} \sum\limits_{i=1}^m h_{ij}x_i.</tex>: <tex> \sigma_j^2 = \frac {1} {mw_j} \sum\limits_{i=1}^m h_{ij}(x_i - \mu_j)^2, j = 1..k.</tex>
== Использование в задаче кластеризации ==
[[Файл:kmeans.jpg|right|thumb|200px|Пример работы k-means]]
Как уже упоминалось в [[#Определение|Определении]], алгоритм EM подходит для решения задачи кластеризации. И одной из его имплементаций для этой задачи является алгоритм [[Алгоритм_k-Means|<tex>k</tex>-meansMeans]]. В этом алгоритме в качестве скрытых переменных выступают метки классов объектов. Параметрами же являются центроиды искомых классов. Тогда на шаге E мы относим объекты к какому-то одному классу на основе расстояний до центроид. А на шаге M мы пересчитываем центроиды кластеров, исходя из полученной на шаге E разметке.<br/>
Также стоит упомянуть алгоритм <tex>c</tex>-means<ref>[https://en.wikipedia.org/wiki/Fuzzy_clustering#Fuzzy_C-means_clustering C-means clustering, Wikipedia]</ref>. В нем качестве скрытых переменных выступают вероятности принадлежности объекта к классам. На шаге E мы пересчитывем вероятности принадлежности объектов, иходя из расстояния до центроид. Шаг M, идейно, остается без изменений.
*[[Кластеризация]]
*[[Алгоритм_k-Means|Алгоритм k-Means]]
 
==Примечания==
<references />
== Источники информации ==
# [http://dendroid.sk/2011/05/09/k-means-clustering/ k-means]
[[Категория:Машинное обучение]][[Категория: Кластеризация]]
Анонимный участник

Навигация