Изменения

'''Алгоритм EM''' (англ: . ''expectation-maximization'') {{--- }} итеративный алгоритм поиска оценок максимума правдоподобия модели, в ситуации, когда она зависит от скрытых(ненаблюдаемых) переменных.

'''E(Expectation)''' шаг {{--- }} поиск наиболее вероятных значений скрытых переменных.

'''M(MaximisationMaximization)''' шаг {{--- }} поиск наиболее вероятхын вероятных значений параметров, для полученных на шаге E значений скрытых переменных.

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

== Проблема восстановления распределения смеси Основной алгоритм ==

<tex>p(x) = \sum\limits_{ij=1}^k \omega_j w_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_jw_j</tex> {{- --}} априорная вероятность <tex>j</tex>-ой компоненты распределениясмеси.<br/>

# По заданной выборке <tex>X^m</tex> случайных и независимых наблюдений полученных из смеси <tex>p(x)</tex>, числу <tex>k</tex> и функцию функции <tex>\phi</tex>, оценить вектор параметров <tex>\Theta = (\omega_1w_1,..,\omega_kw_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 сводится к повторению шагов, указанных в [[#Определение|ОпределениеОпределении]].

<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/>

<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/>

<center><tex>\theta_j = argmax_\arg\max\limits_{\theta} \sum\limits_{i=1}^m h_{ij}*\ln \phi (x_i, ;\theta)</tex>.</center>

<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 /> <tex> \theta_j = \arg\max\limits_{\theta}\sum\limits_{i=1}^m h_{ij}*\ln\phi(x_i;\theta).</tex><br />  

Input:<tex>X^m, k, \thetaTheta^{(0)}</tex>

<tex>h_{ij} = \frac{w_jp_jw_j \phi(x_i; \theta_j)}{\sum\limits_{s=1}^k w_s p_s\phi(x_i; \theta_j)}</tex>

<tex>\theta_j = argmax_\arg\max\limits_{\theta} \sum\limits_{i=1}^m h_{ij}*ln \phi (x_i, \theta)</tex>

Until a stopping criteria criterion is satisfied Return <tex>\Theta = (\theta_j, w_j)_{j=1}^k</tex>

== Задача разделения смеси распределений = Stochastic EM-algorithm ===

=== Общий Как уже было отмечено в [[#Плюсы_и_минусы|Плюсы и минусы]], базовый алгоритм ===чувствителен к начальному приближению и могут быть ситуации, когда алгоритм "застрянет" в локальном экстремуме. Для того, чтобы предотвратить это, будем на каждой итерации алгоритма случайно "встряхивать" выборку. В этой модификации у нас добавляется шаг S, на котором мы и будем "встряхивать" выборку. И на шаге M мы будем решать уже задачу максимуму невзвешенного правдоподобия. Эта модификация хороша тем, что нечуствиетльная к начальном приблежению.

Необходимо описать плотность распределения функции на X как сумму k функций, которые можно рассматривать как элементы параметрического семейства функций <tex> p_j(x) = \phi(x;\theta_j)</tex>. Плотность распределения будет выглядеть как <br><tex>p(x) = \sum\limits_{i=1}^k \omega_j p_j(x); \sum\limits_{i=1}^k w_j = 1; w_j >= 0 </tex> <br /> где <tex>\omega_j</tex>- априорная вероятность j компоненты распределенияПример.Задача разделения Разделение смеси заключается в том, чтобы, имея выборку <tex>X^m</tex> случайных и независимых наблюдений из смеси <tex>p(x)</tex>, зная число <tex>k</tex> и функцию <tex>\phi</tex>, оценить вектор параметров <tex>\theta Гауссиана == (\omega_1,..,\omega_k,\theta_1,..,\theta_k)</tex>

E-шаг[[Файл:Gaussians2.png|right|thumb|400px|Несколько итераций алгоритма]]

<tex>p(x,\theta_j) = p(x)P(\theta_j | x) = w_jp_j(x)</tex> Каноническим примером использования EM алгоритма является задача разделения смеси гауссиана. Данные у нас получены из нормального распределения. В этом случае параметрами функций ялвяются матожидание и дисперсия.<br />Введем обозначение: <tex> g_{ij} = P(\theta_j | x_i) </tex> это и будут скрытые параметры данной задачи - апостериорная вероятность того, что обучающий объект <tex> x_i </tex> получен из <tex>j</tex>-й компоненты

По формуле Байеса справедливо равенство:<tex>\theta = (w_1,..,w_k;\;\mu_1,..,\mu_k;\;\sigma_1,..,\sigma_k)</tex> {{---}} вектор параметров, <br /><tex> g_p_j(x) = N(x;\mu_j, \sigma_j) = \frac1{\sqrt{ij2\pi}\sigma_j} = \exp \biggl(-\frac{w_jp_j(x_ix - \mu_j)^2}{2\sumsigma_j^2}\limits_{t=1}^k w_t p_t(x_ibiggr)}</tex>{{---}} плотность распределения.<br />Таким образом при зная значение параметров легко найти скрытые переменные.

Перейдем к M-шагуПосчитаем значения для каждого шага.<br/>

Посчитаем для аддитивности логарифм правдоподобияE-шаг:<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) \longrightarrow max</tex> <br />при условии <tex>\sum\limits_{i=1}^k w_j = 1; w_j >= 0</tex> имеет смысл рассматривать лагранжиан задачи:<br /><tex>\frac{\partial L} {\partial w_j} = \sum\limits_{i=1}^m \frac{p_j(x_i)}{\sum\limits_{t=1}^kw_tp_t(x_i)} - \lambda = 0.</tex><br />

Умножим на : <tex>h_{ij} = \omega_j</tex> и просуммируем уравнения для всех <tex>jfrac{w_j N(x_i, \mu_j, \sigma_j)}{\sum\limits_{s=1}^k w_s N(x_i, \mu_s, \sigma_s)}.</tex> <br />

Так как можно заменить порядок суммы: <tex> w_j = \frac{1}{m} \sum\limits_{i=1}^m h_{ij}.</tex>: <tex> \mu_j = \frac {1} {mw_j} \sum\limits_{ji=1}^k m h_{ij}x_i.</tex>: <tex> \sigma_j^2 = \frac{w_jp_j(x_i)1}{mw_j} \sum\limits_{ti=1}^kw_tp_tm h_{ij}(x_i- \mu_j)} = \lambda \sum\limits_{^2, j=1}^kw_j..k.</tex>.

А так как <tex>\sum\limits_{j=1}^k \frac{w_jp_j(x_i)}{\sum\limits_{t=1}^kw_tp_t(x_i)} Использование в задаче кластеризации = 1</tex> и <tex>\sum\limits_{j=1}^kw_j = 1</tex>, из чего следует <tex>\lambda = m</tex> <br />

Приравняв к нулю лагранжиан по Как уже упоминалось в [[#Определение|Определении]], алгоритм EM подходит для решения задачи кластеризации. И одной из его имплементаций для этой задачи является алгоритм [[Алгоритм_k-Means|<tex>\theta_jk</tex> схожим способом найдем:-Means]]. В этом алгоритме в качестве скрытых переменных выступают метки классов объектов. Параметрами же являются центроиды искомых классов. Тогда на шаге E мы относим объекты к какому-то одному классу на основе расстояний до центроид. А на шаге M мы пересчитываем центроиды кластеров, исходя из полученной на шаге E разметке.<br />

Также стоит упомянуть алгоритм <tex> \theta_j = \arg\max\limits{\theta}\sum\limits_{i=1}^mg_{ij}\ln(\phi(x_i;\theta)).c</tex>-means<br ref>[https://en.wikipedia.org/wiki/Fuzzy_clustering#Fuzzy_C-means_clustering C-means clustering, Wikipedia]</ref>. В нем качестве скрытых переменных выступают вероятности принадлежности объекта к классам. На шаге E мы пересчитывем вероятности принадлежности объектов, иходя из расстояния до центроид. Шаг M, идейно, остается без изменений.

<font color="green"># Создаем datasets с использованием стандартных sklearn.datasets</font>

<font color="green"># Создаем анизатропно разделенные данные</font>

<font color="green"># Выставляем параметры для matplotlib.pyplot</font>

<font color="green"># Варьируем значение количества классов в зависимости от данных, ведь для нас это гиперпараметр</font>

<font color="green"># Нормализация данных</font>

<font color="green"># Непосредственно наш алгоритм - Gaussian Mixture</font>

<font color="green"># Для сравнения берем алгоритм - Kk-means</font>

clustering_algorithms = ({ ('GaussianMixtureReal distribution': None, 'Gaussian Mixture': gmm), ('KMeansk-Means', : two_means) )}

if algorithm is not None: algorithm.fit(X)

y_pred = y if algorithm is None else algorithm.predict(X)

[[Файл:Prog.png|thumb|250px|Результат программы]] Как и следовало ожидать, алгоритм EM работает на некоторых данных лучше чем k-means, однако есть данные, с которыми он не справляется без дополнительных преобразований.

[[Категория:Машинное обучение]][[Категория: Кластеризация]]