T32.md

Алгоритмы EM. k-means. c-means. GMM

EM (Expectation-Maximization)

Введение

Алгоритм EM исходит из задачи восстановления $N$ вероятностных распределений (или: смеси генеративных распределений), где функция плотности представляет из себя сумму взвешенных компонент смеси. В этой задаче возникает две проблемы: изначально, мы не знаем, сколько у нас компонент; нам необходимо восстановить все плотности распределений. Мы знаем как решать такие задачи путем максимизации логарифма правдоподобия:

$$ \mathcal{L}{(\delta)} = \sum_{i = 1}^{m}{\left(\ln{\left(\sum_{j = 1}^{k}{(w_jp_j(x_i; \delta_j))}\right)}\right)} \to \text{max}_{\delta} $$

Непонятно, что делать с логарифмом суммы, поэтому мы не можем найти аналитическое решение.

Алгоритм EM

Основная идея Expectation-Maximization: вместо того, чтобы считать подобные логарифмы, давайте добавим скрытые переменные такие, что:

1. они могут быть выражены с помощью целевых переменных $\delta$;
2. они могут помочь разделить сумму.

$$ p(X, H | \theta) = \prod_{i = 1}^{k}{p{(X|H, \theta)p{(H|\theta)}}} $$

Что такое скрытые переменные? Скрытые переменные связаны со всеми параметрами смеси распределений, которые мы пытаемся найти. Самый простой способ установить скрытые переменные: определить степень принадлежности точки каждой компоненте.

Схема алгоритма - повторение двух шагов:

• $H \gets \text{E-Step}{(\theta)}$ (ожидание), поиск наиболее вероятностных значений скрытых переменных. Здесь мы будем искать скрытые переменные $H = (h_{ij}){m \times k'}$, где $h{ij}$ - степени вероятности того, что $x_i$ принадлежит $j$-му компоненту.

• $\theta \gets \text{M-Step}{(H, \theta)}$ (максимизация), оценка искомых параметров распределений с помощью скрытых переменных. Здесь мы сводим задачу минимизации $\mathcal{L}{(\theta)}$ можно свести к $k$ независимым подзадачам:

  $$ \theta_{j} = \argmax_{\theta}{\left(\sum_{i = 1}^{m}{h_{ij}\cdot\ln{\varphi{(x_i, \theta)}}}\right)} $$

  и оптимальные веса равны $w_j = \dfrac{1}{m} \cdot \sum_{i = 1}^{m}{h_{ij}}$.

• Повторяем эти два шага, пока не будет удовлетворено одно из критериев остановки.

EM GMM

GMM - это алгоритм EM, который работает на гауссовских моделях, то есть, изначально у нас были какие-то параметры, а затем мы пересчитываем для всех объектов скрытые объекты и адаптируем параметры распределения и повторяем так до сходимости.

Кластеризация

Задача кластеризации состоит в том, чтобы разделить набор объектов одного типа на группы так, чтобы объекты в этих группах имели похожие свойства. В данном случае, мы формализуем похожесть с абстрактной мерой. То есть,

• $\mathcal{D}$ - набор данных, состоящих из объектов из $X$
• $\rho: X \times X \to [0, +\infty)$ - метрока на $X$

Наша задача: найти алгоритм $a : X \to Y$, где $Y$ - множество кластеров, фактически, нужен такой алгоритм, который строит нам это разбиение.

Алгоритм k-means

k-means - наиболее применяемый и простой алгоритм кластеризации, разбивает данные на $k$ кластеров, где $k$ - внешний параметр.

Алгоритм k-means:

1. Разбросать $k$ центров по пространству случайным образом.
2. Точка относится к тому кластеру, к центру которого она ближе всего.
3. Померили расстояния от всех точек до каждого центра, установили метку того центра, к которому точка (или объект) ближе всего.
4. Переместили центры кластеров к их средним координатам (на самом деле: вычисляется не средний, а центр масс).
5. Повторяем алгоритм, пока центры не перестанут перемещаться.

Как найти число кластеров? Например, воспользоваться оценкой внутренней оценки качества.

Какие есть проблемы?

• Нам приходится по сути перебирать размеры кластеров.
• Каждый раз мы пытаемся строить эллиптические кластеры, сложные формы не обрабатываются.
• Алгоритм содержит случайность - могут быть разные результаты.

Алгоритм c-means

Почти такой же алгоритм как k-means, но в отличии от него каждая точка может принадлежать сразу нескольким кластерам - в качестве ответа мы получаем вероятности принадлежности ко всем кластерам.