Редактирование: EM-алгоритм

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 19: Строка 19:
  
 
Плотность распределения смеси имеет вид:<br/>
 
Плотность распределения смеси имеет вид:<br/>
<tex>p(x) = \sum\limits_{j=1}^k w_j p_j(x)</tex>.<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/>
 
Где <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/>
 
Перед нами стоит две задачи:<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>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>.
 
# Найти <tex>k</tex>.
  
Строка 30: Строка 30:
  
 
Задачи подобного рода мы умеем решать, максимизируя логармиф правдоподобия:<br>
 
Задачи подобного рода мы умеем решать, максимизируя логармиф правдоподобия:<br>
<tex> Q(\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/>
+
<tex> L(\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.
 
Но проблeма в том, что мы не знаем как аналитически посчитать логарифм суммы. Тут нам и поможет алгоритм EM.
Строка 38: Строка 38:
 
Основная идея алгоритма EM заключается в том, что мы добавляем скрытые переменные такие, что:<br/>
 
Основная идея алгоритма EM заключается в том, что мы добавляем скрытые переменные такие, что:<br/>
  
# Они могут быть выражены через <tex>\Theta</tex>.
+
# Они могут быть выражены через <tex>\Theta</tex>
# Они помогают разбить сумму так: <tex>p (X, H|\Theta) = \prod\limits_{i=1}^k p (X|H, \Theta) p(H|\Theta)</tex>, где <tex>H</tex> {{---}} матрица скрытых переменных.
+
# Они помогают разбить сумму так: <tex>p (X, H|\Theta) = \prod\limits_{i=1}^k p (X|H, \Theta) p(H|\Theta)</tex>, где <tex>H</tex> - матрица скрытых переменных.
  
 
Тогда алгоритм EM сводится к повторению шагов, указанных в [[#Определение|Определении]].
 
Тогда алгоритм EM сводится к повторению шагов, указанных в [[#Определение|Определении]].
Строка 45: Строка 45:
 
=== E-шаг ===  
 
=== E-шаг ===  
  
<tex>p(x,\theta_j) = p(x)P(\theta_j | x) = w_jp_j(x)</tex>.<br />
+
<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 = (h_{ij})_{m \times k}</tex><br/>
 
где <tex>h_{ij} = P(\theta_j | x_i)</tex> {{---}} вероятность того, что <tex>x_i</tex> пренадлежит <tex>j</tex>-ой компоненте.<br/>
 
где <tex>h_{ij} = P(\theta_j | x_i)</tex> {{---}} вероятность того, что <tex>x_i</tex> пренадлежит <tex>j</tex>-ой компоненте.<br/>
  
 
По формуле Байеса справедливо равенство:<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> 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>\sum\limits_{j=1}^k h_{ij} = 1</tex><br/>
  
Таким образом, зная значения вектора параметров <tex>\Theta</tex>, мы легко можем пересчитать значения скрытых переменных.<br/>
+
Таким образом, зная значения вектора параметров <tex>\Theta</tex>, мы легко можем пересчитать значения скрытых переменных<br/>
  
 
=== M-шаг ===  
 
=== M-шаг ===  
Строка 62: Строка 62:
 
|statement=
 
|statement=
 
Если известны скрытые переменные, то задача минимизации <tex>Q(\Theta)</tex> сводится к <tex>k</tex> независимым подзадачам:<br/>
 
Если известны скрытые переменные, то задача минимизации <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>
+
<center><tex>\theta_j = \arg\max\limits_{\theta}\sum\limits_{i=1}^m h_{ij}*\ln\phi(x_i;\theta)</tex></center>
 
Оптимальные же веса считаются как:<br/>
 
Оптимальные же веса считаются как:<br/>
<center><tex> w_j = \frac {1} {m} \sum\limits_{i=1}^m h_{ij}</tex>.</center>
+
<center><tex> w_j = \frac {1} {m} \sum\limits_{i=1}^m h_{ij}</tex></center>
 
|proof=
 
|proof=
 
Посчитаем логарифм правдоподобия:<br>
 
Посчитаем логарифм правдоподобия:<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> 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> \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> 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>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>\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>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 \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>\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>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 />
 
Приравняв к нулю производную Лагранжиана по <tex>\theta_j</tex>, схожим способом найдем:<br />
Строка 87: Строка 87:
 
=== Критерий остановки ===  
 
=== Критерий остановки ===  
  
Алгоритм EM выполняется до сходимости, но как нам определить, что сходимость наступила? Мы можем останавливаться, когда либо <tex>Q(\Theta)</tex>, либо <tex>H</tex> перестают сильно меняться. Но, обычно, удобней контролировать изменения значений скрытых переменных, так как они имеют смысл вероятностей и принимают значения из отрезка <tex>[0,1]</tex>. Поэтому один из возможных критериев остановки будет выглядеть так: <tex>\max\limits_{i,j} |h_{ij} - h_{ij}^{(0)}| > \delta</tex>.
+
Алгоритм EM вы полняется до сходимости, но как нам определить, что сходимость наступила? Мы можем останавливаться, когда либо <tex>Q(\Theta)</tex>, либо <tex>H</tex> перестают сильно меняться. Но, обычно, удобней контролировать изменения значений скрытых переменных, так как они имеют смысл вероятностей и принимают значения из отрезка <tex>[0,1]</tex>. Поэтому один из возможных критериев остановки будет выглядеть так: <tex>\max\limits_{i,j} |h_{ij} - h_{ij}^{(0)}| > \delta</tex>
  
 
=== Псевдокод ===  
 
=== Псевдокод ===  
Строка 105: Строка 105:
 
Плюсы:<br/>
 
Плюсы:<br/>
  
* Сходится в большинтсве случаев.
+
* Сходится в большинтсве случаев
* Наиболее гибкое решение.
+
* Наиболее гибкое решение
* Существуют простые модификации, позволяющие уменьшить чуствительность алгоритма к шуму в данных.
+
* Существуют простые модификации, позволяющие уменьшить чуствительность алгоритма к шуму в данных
  
 
Минусы:<br/>
 
Минусы:<br/>
  
* Чуствителен к начальному приближению. Могут быть ситуации, когда сойдемся к локальному экстремуму.
+
* Чуствителен к начальному приближению. Могут быть ситуации, когда сойдемся к локальному экстремуму
* Число компонент <tex>k</tex> является [[Настройка_гиперпараметров|гиперпараметром]].
+
* Число компонент <tex>k</tex> является гиперпараметром.
  
 
== Модификации ==  
 
== Модификации ==  
  
Базовый алгоритм EM является очень гибким для модификаций, позволяющих улучшить его работу. В этом разделе мы приведем краткое описание некоторых из них.
+
Базовый алгоритм EM является очень гибким для модификаций, позволяющих улучшить его работу. В этом разделе мы приведем краткое описаниен некоторых из них.
  
 
=== Generalized EM-algorithm ===  
 
=== Generalized EM-algorithm ===  
Строка 124: Строка 124:
 
=== Stochastic EM-algorithm ===
 
=== Stochastic EM-algorithm ===
  
Как уже было отмечено в [[#Плюсы_и_минусы|Плюсы и минусы]], базовый алгоритм чувствителен к начальному приближению и могут быть ситуации, когда алгоритм "застрянет" в локальном экстремуме. Для того, чтобы предотвратить это, будем на каждой итерации алгоритма случайно "встряхивать" выборку. В этой модификации у нас добавляется шаг S, на котором мы и будем "встряхивать" выборку. И на шаге M мы будем решать уже задачу максимуму невзвешенного правдоподобия. Эта модификация хороша тем, что нечуствиетльная к начальном приблежению.  
+
Как уже было отмечено в [[#Плюсы_и_минусы|Плюсы и минусы]], базовый алгоритм чувствителен к начальному приближению и могут быть ситуации, когда алгоритм "застрянет" в лоакльном экстремуме. Для того, чтобы предотвратить это, будем на каждой итерации алгоритма случайно "встряхивать" выборку. В этой модификации у нас добавляется шаг S, на котором мы и будем "встряхивать" выборку. И на шаге M мы будем решать уже задачу максимуму невзвешенного правдоподобия. Эта модификация хороша тем, что нечуствиетльная к начальном приблежению.  
  
 
== Пример. Разделение смеси Гауссиана ==  
 
== Пример. Разделение смеси Гауссиана ==  
Строка 133: Строка 133:
  
 
<tex>\theta = (w_1,..,w_k;\;\mu_1,..,\mu_k;\;\sigma_1,..,\sigma_k)</tex> {{---}} вектор параметров, <br/>
 
<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/>
+
<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/>
 
Посчитаем значения для каждого шага. <br/>
Строка 139: Строка 139:
 
E-шаг:
 
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>
+
: <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-шаг:
 
M-шаг:
  
: <tex>w_j = \frac{1}{m} \sum\limits_{i=1}^m h_{ij}.</tex>
+
: <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> \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>
+
: <tex> \sigma_j^2 = \frac {1} {mw_j} \sum\limits_{i=1}^m h_{ij}(x_i - \mu_j)^2, j = 1..k</tex>
  
 
== Использование в задаче кластеризации ==
 
== Использование в задаче кластеризации ==
Строка 151: Строка 151:
 
[[Файл:kmeans.jpg|right|thumb|200px|Пример работы k-means]]
 
[[Файл:kmeans.jpg|right|thumb|200px|Пример работы k-means]]
  
Как уже упоминалось в [[#Определение|Определении]], алгоритм EM подходит для решения задачи кластеризации. И одной из его имплементаций для этой задачи является алгоритм [[Алгоритм_k-Means|<tex>k</tex>-Means]]. В этом алгоритме в качестве скрытых переменных выступают метки классов объектов. Параметрами же являются центроиды искомых классов. Тогда на шаге E мы относим объекты к какому-то одному классу на основе расстояний до центроид. А на шаге M мы пересчитываем центроиды кластеров, исходя из полученной на шаге E разметке.<br/>
+
Как уже упоминалось в [[#Определение|Определении]], алгоритм EM подходит для решения задачи кластеризации. И одной из его имплементаций для этой задачи является алгоритм <tex>k</tex>-means. В этом алгоритме в качестве скрытых переменных выступают метки классов объектов. Параметрами же являются центроиды искомых классов. Тогда на шаге 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, идейно, остается без изменений.
+
Также стоит упомянуть алгоритм <tex>c</tex>-means. В нем качестве скрытых переменных выступают вероятности принадлежности объекта к классам. На шаге E мы пересчитывем вероятности принадлежности объектов, иходя из расстояния до центроид. Шаг M, идейно, остается без изменений.
  
  
Строка 240: Строка 240:
 
*[[Кластеризация]]
 
*[[Кластеризация]]
 
*[[Алгоритм_k-Means|Алгоритм k-Means]]
 
*[[Алгоритм_k-Means|Алгоритм k-Means]]
 
==Примечания==
 
<references />
 
  
 
== Источники информации ==
 
== Источники информации ==
Строка 252: Строка 249:
 
# [http://dendroid.sk/2011/05/09/k-means-clustering/ k-means]
 
# [http://dendroid.sk/2011/05/09/k-means-clustering/ k-means]
  
[[Категория: Машинное обучение]]
+
[[Категория:Машинное обучение]]
[[Категория: Кластеризация]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: