Практика: EM и сэмплирование

Скрытая переменная

Смесь гауссиан — это модель с латентной переменной. Каждая точка пришла из одной из $K$ компонент, но из какой именно, мы не наблюдаем:

$p(x) = \sum_{k=1}^{K} \pi_k \, \mathcal{N}(x \mid \mu_k, \Sigma_k)$

Если бы принадлежность $z_i$ была известна, задача распалась бы на $K$ независимых MLE — по формулам из урока 120, каждая в одну строку. Вся трудность именно в том, что $z_i$ скрыта, а сумма внутри логарифма не позволяет разделить слагаемые: $\log \sum_k$ не раскладывается так, как раскладывается $\sum_k \log$.

EM: два шага, которые никогда не ухудшают ответ

$$\htmlData{k=estep}{\gamma_{ik} = \frac{\pi_k \mathcal{N}(x_i \mid \mu_k, \Sigma_k)}{\sum_j \pi_j \mathcal{N}(x_i \mid \mu_j, \Sigma_j)}} \qquad\Longrightarrow\qquad \htmlData{k=mstep}{\mu_k = \frac{\sum_i \gamma_{ik} x_i}{\sum_i \gamma_{ik}}}$$

E-шаг — это правило Байеса, ничего больше: posterior скрытой переменной при текущих параметрах. M-шаг — обычное MLE, только каждая точка входит в каждую компоненту с весом $\gamma_{ik}$, а не целиком.

Ключевое свойство: log-правдоподобие не убывает ни на одной итерации. Это теорема, а не эмпирическое наблюдение, и она даёт бесплатную проверку реализации — если ваш лосс дёрнулся вверх, в коде ошибка. На семи точках сходимость выглядит так:

итерация	$\log L$	$\mu_1$	$\sigma^2$
$1$	$-11.9541$	$-1.1564$	$0.7342$
$2$	$-11.4789$	$-1.2526$	$0.5024$
$3$	$-11.0896$	$-1.2813$	$0.4297$
$4$	$-11.0376$	$-1.2841$	$0.4224$
$6$	$-11.03695$	$-1.28432$	$0.42195$
$20$	$-11.03695$	$-1.28432$	$0.42195$

Шесть итераций до пяти значащих цифр. EM сходится быстро в начале и медленно в конце — это его характерное поведение: он не использует градиент и не имеет скорости обучения, зато каждый шаг гарантированно не вреден.

В блоке 4 мы увидим, что EM — это координатный подъём по ELBO: E-шаг максимизирует по $q$, M-шаг — по параметрам. Монотонность станет очевидной, а не удивительной.

Вырожденное решение

У правдоподобия смеси есть неприятное свойство: оно не ограничено сверху. Посадите одну компоненту точно на одну точку и стягивайте её дисперсию к нулю:

$\sigma^2$ компоненты	$\log L$	плотность в точке
$10^{-4}$	$-11.26$	$39.9$
$10^{-6}$	$-8.96$	$398.9$
$10^{-8}$	$-6.65$	$3989$
$10^{-10}$	$-4.35$	$39894$
$10^{-14}$	$+0.25$	$3.99 \cdot 10^{6}$

Сравните с честным оптимумом $-11.037$: начиная примерно с $\sigma^2 = 10^{-5}$ вырожденное решение лучше по правдоподобию, а дальше уходит в $+\infty$.

То есть глобального максимума у этой задачи просто нет, и «найти MLE» здесь — некорректно поставленная задача. Что с этим делают на практике:

• нижняя граница на дисперсию (reg_covar в scikit-learn — по умолчанию $10^{-6}$);
• prior на $\Sigma$, то есть переход к MAP — обратное распределение Уишарта штрафует малые дисперсии;
• перезапуск компоненты, которая схлопнулась.

Все три — способы обойти отсутствие максимума, а не улучшить оптимизацию. И это третий раз в блоке, когда prior не подкручивает ответ, а делает задачу разрешимой: первый был ноль успехов из четырёх, второй — разделимые данные в логистической регрессии.

Условные распределения гауссианы

Для двумерной гауссианы и E-шага, и предсказание при частично известном входе делаются одной формулой:

$\mu_{Y \mid X = x} = \mu_Y + \rho \frac{\sigma_Y}{\sigma_X}(x - \mu_X), \qquad \sigma^2_{Y \mid X} = \sigma_Y^2 (1 - \rho^2)$

Поставьте срез в виджете и подвигайте $\rho$. Два наблюдения стоят того, чтобы их сделать самому:

σx

1

σy

1

корреляция ρ

0.7

показать условное сечение

маргинальное ст. откл.

1

Первое: условная дисперсия всегда не больше маргинальной и не зависит от того, где именно стоит срез. Множитель $1 - \rho^2$ — это доля дисперсии, которая остаётся необъяснённой; при $\rho = 0.7$ остаётся $51\%$, при $\rho = 0.9$ — $19\%$. Знакомая величина: $\rho^2$ — это в точности $R^2$ из линейной регрессии.

Второе: условное среднее — линейная функция $x$. Отсюда факт, который стоит держать в голове: линейная регрессия оптимальна не потому, что мир линеен, а потому, что для совместно гауссовских величин условное ожидание в самом деле линейно. Как только совместное распределение перестаёт быть гауссовым, это перестаёт быть верным.

Что делать руками

1. EM для смеси с нуля. Одномерный случай, две компоненты, семь точек из таблицы выше. Логируйте $\log L$ на каждой итерации и проверяйте монотонность assert’ом — это лучший тест на корректность E-шага.
2. Воспроизведите вырождение. Инициализируйте одну компоненту в точке данных с $\sigma^2 = 10^{-6}$ и убедитесь, что EM охотно уходит туда, а $\log L$ растёт без предела. Затем добавьте reg_covar и посмотрите, что изменится.
3. Сравните с $k$-means. Прогоните оба на одном облаке. $k$-means — это предельный случай EM, где ответственности округляются до $0$ и $1$, а дисперсии считаются равными и фиксированными. Убедитесь, что на вытянутых кластерах он проигрывает.
4. Три способа посчитать одно ожидание. Возьмите $\mathbb{E}[X^2]$ для $X \sim \mathcal{N}(0,1)$ (ответ $1$) и посчитайте: наивным Монте-Карло, importance sampling с $q = \mathcal{N}(0, 2)$, и точно. Сравните стандартные ошибки при том же $n$ — и заодно проверьте, что $n_{\text{eff}}$ у второго способа меньше $n$.
5. Условные распределения численно. Сгенерируйте $10^5$ точек из двумерной гауссианы с $\rho = 0.7$, отберите те, у которых $|x - 1| < 0.05$, и сравните их выборочные среднее и дисперсию с формулами выше. Совпасть должно до двух знаков.
6. Соберите блок целиком. Логистическая регрессия из прошлого урока обучалась MLE. Добавьте к ней L2, то есть гауссов prior, и убедитесь, что это тот же $\lambda = \sigma^2/\tau^2$ из урока про MAP. Один вывод, три урока.