Изменения

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

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

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

Необходимо описать плотность распределения функции на 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>

=== Постановка задачи === Плотность распределения смеси имеет вид:<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> 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/> Но пробл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>p(x,\theta_j) H = p(xh_{ij})P(_{m \theta_j | x) = w_jp_j(x)times k}</tex> ,<br />Введем обозначение: где <tex> g_h_{ij} = P(\theta_j | x_i) </tex> это и будут скрытые параметры данной задачи {{-- апостериорная -}} вероятность того, что обучающий объект <tex> x_i </tex> получен из пренадлежит <tex>j</tex>-й компоненты ой компоненте.<br/>

<tex> g_h_{ij} = \frac{w_jp_j(x_i)}{p (x_i)} = \frac{w_jp_j(x_i)}{\sum\limits_{ts=1}^k w_t p_tw_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> сводится к M<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 />

Посчитаем для аддитивности логарифм правдоподобия:<br /><tex> Q(\Theta) w_j = ln \prod\limits_frac{i=1}^mp(x_i) = {m}\sum\limits_{i=1}^m ln\sum\limits_frac{j=1}^k w_j p_jw_jp_j(x_i) \longrightarrow max</tex> <br />при условии <tex>}{\sum\limits_{is=1}^k w_j = 1; w_j >kw_sp_s(x_i)} = 0</tex> имеет смысл рассматривать лагранжиан задачи:<br /><tex>\frac{\partial L1} {\partial w_jm} = \sum\limits_{i=1}^m \frac{p_j(x_i)}{\sum\limits_h_{t=1ij}^kw_tp_t(x_i)} - \lambda = 0.</tex>.<br />

Умножим на Приравняв к нулю производную Лагранжиана по <tex>\omega_j</tex> и просуммируем уравнения для всех <tex>jtheta_j</tex> , схожим способом найдем:<br />

<tex>\sumtheta_j = \arg\max\limits_{j=1\theta}^k \sum\limits_{i=1}^m \frach_{w_jp_j(x_i)ij}{*\sumln\limits_{t=1}^kw_tp_tphi(x_i;\theta)} = \lambda \sum\limits_{j=1}^kw_j.</tex> <br />

А так как <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 />

<tex>\omega_j = \frac{1}{m}\sum\limits_{i=1}^m \frac{w_jp_j(x_i)}{\sum\limits_{t=1}^kw_tp_t(x_i)} Критерий остановки == \frac{1}{m}\sum\limits_{i=1}^mg_{ij}</tex><br />

Приравняв к нулю лагранжиан по Алгоритм EM выполняется до сходимости, но как нам определить, что сходимость наступила? Мы можем останавливаться, когда либо <tex>Q(\theta_jTheta)</tex> схожим способом найдем, либо <tex>H</tex> перестают сильно меняться. Но, обычно, удобней контролировать изменения значений скрытых переменных, так как они имеют смысл вероятностей и принимают значения из отрезка <tex>[0,1]</tex>. Поэтому один из возможных критериев остановки будет выглядеть так:<br tex>\max\limits_{i,j} |h_{ij} - h_{ij}^{(0)}| > \delta</tex>.

=== Псевдокод ===   Input:<tex>X^m, k, \Theta^{(0)}</tex> Repeat '''E-step''': for all i = 1..m; j = 1..k: <tex>h_{ij} = \frac{w_j \phi(x_i; \theta_j)}{\sum\limits_{s=1}^k w_s \phi(x_i; \theta_j)}</tex> '''M-step''': for all j = 1..k: <tex> \theta_j = \arg\max\limitslimits_{\theta}\sum\limits_{i=1}^mg_m h_{ij}\*ln(\phi(x_i, \theta)</tex> <tex>w_j = \frac {1} {m} \sum\limits_{i=1}^m h_{ij}</tex> Until a stopping criterion is satisfied Return <tex>\Theta = (\theta_j, w_j)_{j=1}^k</tex> === Плюсы и минусы ===  Плюсы:<br/> * Сходится в большинтсве случаев.* Наиболее гибкое решение.* Существуют простые модификации, позволяющие уменьшить чуствительность алгоритма к шуму в данных. Минусы:<br/> * Чуствителен к начальному приближению. Могут быть ситуации, когда сойдемся к локальному экстремуму.* Число компонент <tex>k</tex> является [[Настройка_гиперпараметров|гиперпараметром]]. == Модификации ==  Базовый алгоритм EM является очень гибким для модификаций, позволяющих улучшить его работу. В этом разделе мы приведем краткое описание некоторых из них. === Generalized EM-algorithm ===  Осоновная идея этой модификации заключается в том, что на шаге M мы не будем пытаться найти наилучшее решение. Это применимо в случаях, когда максимизация <tex>Q(\Theta)</tex> является сликшом дорогой, поэтому нам достаточно сделать лишь несколько итераций, для того, чтобы сместиться в сторону максимума значения <tex>Q(\Theta)</tex>. Эта модификация имеет неплохую сходимость. === Stochastic EM-algorithm === Как уже было отмечено в [[#Плюсы_и_минусы|Плюсы и минусы]], базовый алгоритм чувствителен к начальному приближению и могут быть ситуации, когда алгоритм "застрянет" в локальном экстремуме. Для того, чтобы предотвратить это, будем на каждой итерации алгоритма случайно "встряхивать" выборку. В этой модификации у нас добавляется шаг S, на котором мы и будем "встряхивать" выборку. И на шаге M мы будем решать уже задачу максимуму невзвешенного правдоподобия. Эта модификация хороша тем, что нечуствиетльная к начальном приблежению.  == Пример. Разделение смеси Гауссиана ==  [[Файл:Gaussians2.png|right|thumb|400px|Несколько итераций алгоритма]] Каноническим примером использования EM алгоритма является задача разделения смеси гауссиана. Данные у нас получены из нормального распределения. В этом случае параметрами функций ялвяются матожидание и дисперсия.<br/> <tex>\theta = (w_1,..,w_k;\;\mu_1,..,\mu_k;\theta;\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>-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, идейно, остается без изменений.

<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, однако есть данные, с которыми он не справляется без дополнительных преобразований.

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