15
правок
Изменения
Оформил докозательство теоремы из шага M
# Задачи, в которых удобно вводить скрытые переменные для упрощения подсчета функции правдоподобия. Примером такой задачи может служить кластеризация
== Проблема восстановления распределения смеси Основной алгоритм ==
=== Постановка задачи ===
Плотность распределения смеси имеет вид:<br/>
<tex>p(x) = \sum\limits_{ij=1}^k \omega_j p_j(x)</tex><br/>Где <tex> \sum\limits_{ij=1}^k w_j = 1; w_j >= \geq 0; p_j(x) = \phi(x;\theta_j)</tex> - функция правдоподобия <tex>j</tex>-ой компонеты смеси, <tex>\omega_j</tex> - априорная вероятность <tex>j</tex>-ой компоненты распределения.<br/>
Перед нами стоит две задачи:<br/>
|statement=
Если известны скрытые переменные, то задача минимизации <tex>Q(\Theta)</tex> сводится к <tex>k</tex> независимым подзадачам:<br/>
<center><tex>\theta_j = argmax_\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</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_i = \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 = \arg\max\limits{\theta}\sum\limits_{i=1}^m h_{ij}*\ln\phi(x_i;\theta).</tex><br />
}}
=== Критерий остановки ===
Алгоритм EM вы полняется до сходимости, но как нам определить, что сходимость наступила?. Мы можем останавливаться, когда либо <tex>Q(\Theta)</tex>, либо <tex>H</tex> перестают сильно меняться. Но, обычно, удобней контролировать изменения значений скрытых переменных, так как они имеют смысл вероятностей и принимают значения из отрезка <tex>[0,1]</tex>. Поэтому один из возможных критериев остановки будет выглядеть так: <tex>max_{i,j} |h_{ij} - h_{ij}^{(0)}| > \delta</tex>
=== Псевдокод ===
== Использование в задаче кластеризации ==
[[Файл:kmeans.jpg|right|thumb|200px|Пример работы k-means]]
Как уже упоминалось в [[#Опредиление|Определении]], алгоритм EM подходит для решения задачи кластеризации. И одной из его имплементаций для это задачи является алгоритм <tex>k</tex>-means. В этом алгоритме в качестве скрытых переменных выступают метки классов объектов. Параметрами же являются центроиды искомых классов. Тогда на шаге E мы относим объекты к какому то одному классу на основе расстояний до центроид. А на шаге M мы пересчитываем центроиды кластеров, исходя из полученной на шаге E разметке.<br/>
Также стоит упомянуть алгоритм <tex>c</tex>-means. В нем качестве скрытых переменных выступают вероятности принадлежности объекта к классам. На шаге E мы пересчитывем вероятности принадлежности объектов, иходя из расстояния до центроид. Шаг M, идейно, остается без изменений.
== Реализация на python ==
