1632
правки
Изменения
м
M(Maximisation) шаг - пересчет параметров# Задачи с неполными данными.# Задачи, находя максимум в которых удобно вводить скрытые переменные для упрощения подсчета функции правдоподобия исходя из распределения скрытых переменных, полученных на E - шаге. Примером такой задачи может служить кластеризация.
----=== Постановка задачи ===
== k-means как EM алгоритм ==Перед нами стоит две задачи:<br/>
Скрытыми переменными в данной задаче являются классы# По заданной выборке <tex>X^m</tex> случайных и независимых наблюдений полученных из смеси <tex>p(x)</tex>, числу <tex>k</tex> и функции <tex>\phi</tex>, оценить вектор параметров <tex>\Theta = (w_1,..,w_k,\theta_1, к которым относятся объекты для кластеризации. Сами же параметры это центры масс классов. На шаге E - распределяются все объекты по классам исходя из расстояния от центра, на шаге M находится оптимальное месторасположение центра\theta_k)</tex>.# Найти <tex>k</tex>.
Аналогично рассматривается и алгоритм c-means. Скрытые переменные здесь будут вероятности принадлежности к классам, которые находятся на E-шаге по расстоянию от центра. Центр так же рассчитывается на M-шаге исходя из скрытых переменных.=== Проблема ===
----Но проблeма в том, что мы не знаем как аналитически посчитать логарифм суммы. Тут нам и поможет алгоритм EM.
Суть Необходимо описать плотность распределения функции на X как сумму k функций, которые можно рассматривать как элементы параметрического семейства функций <tex> p_j(x) = \phi(x;\theta_j)</tex>. Плотность распределения будет выглядеть как <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> где <tex>\omega_j</tex> - априорная вероятность j компоненты распределения.Задача разделения смеси Основная идея алгоритма EM заключается в том, чтобы, имея выборку <tex>X^m</tex> случайных и независимых наблюдений из смеси <tex>p(x)</tex>, зная число <tex>k</tex> и функцию <tex>\phi</tex>, оценить вектор параметров <tex>\theta = (omega_1 .. \omega_kчто мы добавляем скрытые переменные такие, \theta_1 .. \theta_k)что:<br/tex>
Введем обозначение: <tex> g_{ij} = P(\theta_j | x_i) </tex> это Как и будут скрытые параметры данной задачи следовало ожидать, алгоритм EM работает на некоторых данных лучше чем k- апостериорная вероятность тогоmeans, что обучающий объект <tex> x_i </tex> получен из <tex>j</tex>-й компоненты однако есть данные, с которыми он не справляется без дополнительных преобразований.
По формуле Байеса справедливо равенство <tex> g_{ij} = \frac{w_jp_j(x_i)}{\sum\limits_{t=1}^См. также ==*[[Кластеризация]]*[[Алгоритм_k-Means|Алгоритм k w_t p_t(x_i)}</tex>Таким образом при зная значение параметров легко найти скрытые переменные.-Means]]
Перейдем к M-шагу:==Примечания==<references />
Посчитаем для аддитивности логарифм правдоподобия:<tex> Q(\Theta) = ln \mul\limits_{i=1}^mp(x_i) Источники информации = \sum\limits_{i=1}^mln\sum\limits_{j=1}^kw_jp_j(x_i) -> max\limits{Theta} </tex>
при условии <tex>\sum\limits_{i=# Материалы лекции про кластеризацию курса "Машинное обучение" университета ИТМО, 2019 год# [http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1}^k w_j .pdf Математические методы обучения по прецедентам К. В. Воронцов]# [http://www.machinelearning.ru/wiki/index.php?title= 1; w_j >= 0<EM-%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC Статья про EM-алгоритм на machinelearning.ru]# [https://machinelearningmastery.com/expectation-maximization-em-algorithm/tex> имеет смысл расcматривать лагранжиан задачиA Gentle Introduction to Expectation-Maximization]# [http://dendroid.sk/2011/05/09/k-means-clustering/ k-means]
<tex>\frac{\partial L} {\partial w_j} = \sum\limits_{i=1}^m \frac{w_jp_j(x_i)}{\sum\limits_{t=1}^kw_tp_t(x_i)} - \lambda = 0</tex>[[Категория: Машинное обучение]][[Категория: Кластеризация]]
rollbackEdits.php mass rollback
== Определение == '''Алгоритм EM ''' (англ. ''expectation- maximization'') {{---}} итеративный алгоритм поиска оценок максимума правдоподобия параметров для решения задачмодели, в ситуации, где некоторые переменные не являются наблюдаемымикогда она зависит от скрытых (ненаблюдаемых) переменных.
Алгоритм ищет параметры модели итеративно, каждая итерация состоит из двух шагов:
'''E(Expectation) ''' шаг{{---}} поиск наиболее вероятных значений скрытых переменных. '''M (Maximization)''' шаг {{---}} поиск наиболее вероятных значений параметров, в котором находится распределение для полученных на шаге E значений скрытых переменных используя значение наблюдаемых переменных и текущего значения параметров. EM алгоритм подходит для решения задач двух типов:
== Основной алгоритм ==
Плотность распределения смеси имеет вид:<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> 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>\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 />
<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\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\limits_{\theta} \sum\limits_{i=1}^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;\;\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>ph_{ij} = \frac{w_j N(xx_i, \mu_j,\theta_jsigma_j) }{\sum\limits_{s= p1}^k w_s N(xx_i, \mu_s, \sigma_s)P}.</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 - \theta_j 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, идейно, остается без изменений. == Реализация на python == В пакете sklearn алгоритм EM представлен объектом GaussianMixture. Проиллюстрируем его работу на примере задачи кластеризации и сравним его с алгоритмом <tex>k</tex>-means: [[Файл:em_clustering.png|thumb| x600px|Результат выполнения программы]] '''import''' numpy as np '''import''' matplotlib.pyplot as plt '''from''' sklearn '''import''' cluster, datasets, mixture '''from''' sklearn.preprocessing '''import''' StandardScaler '''from''' itertools '''import''' cycle, islice np.random.seed(12) <font color="green"># Создаем datasets с использованием стандартных sklearn.datasets</font> n_samples = 2000 random_state = 170 noisy_circles = datasets.make_circles(n_samples=n_samples, factor=.5, noise=.05) noisy_moons = datasets.make_moons(n_samples=n_samples, noise=.05) blobs = datasets.make_blobs(n_samples=n_samples, random_state=8) varied = datasets.make_blobs(n_samples=n_samples, cluster_std=[1.0, 2.5, 0.5], random_state=random_state) <font color="green"># Создаем анизатропно разделенные данные</font> X, y = datasets.make_blobs(n_samples=n_samples, random_state=random_state) transformation = [[0.6, -0.6], [-0.4, 0.8]] X_aniso = np.dot(X, transformation) aniso = (X_aniso, y) <font color="green"># Выставляем параметры для matplotlib.pyplot</font> plt.figure(figsize=(9 * 2 + 3, 12.5)) plt.subplots_adjust(left=.02, right=.98, bottom=.001, top=.96, wspace=.05, hspace=.01) plot_num = 1 defaul_n = 3 <font color="green"># Варьируем значение количества классов в зависимости от данных, ведь для нас это гиперпараметр</font> datasets = [ (varied, defaul_n), (aniso, defaul_n), (blobs, defaul_n), (noisy_circles, 2)] for i_dataset, (dataset, n_cluster) in enumerate(datasets): X, y = dataset <font color="green"># Нормализация данных</font> X = StandardScaler().fit_transform(X) <font color="green"># Непосредственно наш алгоритм - Gaussian Mixture</font> gmm = w_jp_jmixture.GaussianMixture(xn_components=n_cluster, covariance_type='full') <font color="green"># Для сравнения берем алгоритм - k-means</texfont> two_means = cluster.KMeans(n_clusters=n_cluster) clustering_algorithms = { 'Real distribution': None, 'Gaussian Mixture': gmm, 'k-Means': two_means } for name, algorithm in clustering_algorithms: # Этап обучения if algorithm is not None: algorithm.fit(X) # Применяем алгоритм y_pred = y if algorithm is None else algorithm.predict(X) # Рисуем результаты plt.subplot(len(datasets), len(clustering_algorithms), plot_num) if i_dataset == 0: plt.title(name, size=18) colors = np.array(list(islice(cycle(['#377eb8', '#ff7f00', '#4daf4a']), int(max(y_pred) + 1)))) plt.scatter(X[:, 0], X[:, 1], s=10, color=colors[y_pred]) plt.xlim(-2.5, 2.5) plt.ylim(-2.5, 2.5) plt.xticks(()) plt.yticks(()) plot_num += 1 plt.show()
