EM-алгоритм и ELBO

Материал из MachineLearning.

Статья написана с использованием LLM Gemini Pro 3.1 и проверена участником Nikita Zinoviсh 01:45, 16 июля 2026 (MSD)

Содержание

1 Введение
2 Математическая постановка задачи
3 Вариационная нижняя оценка (ELBO)
- 3.1 Связь ELBO и KL-дивергенции
4 Обобщенный EM-алгоритм
- 4.1 E-шаг (Expectation)
- 4.2 M-шаг (Maximization)
5 Практический пример: Разделение смеси гауссовских распределений (GMM)
6 См. также
7 Литература

Введение

В задачах обучения без учителя (таких как кластеризация или понижение размерности) мы часто предполагаем, что наблюдаемые данные порождены некоторым вероятностным процессом, который зависит от ненаблюдаемых, или скрытых переменных. Переход от эвристических алгоритмов к строгим генеративным моделям позволяет не только находить структуру в данных, но и оценивать уверенность в предсказаниях, а также генерировать новые объекты.

Однако введение скрытых переменных делает прямое применение классических методов статистики вычислительно невозможным. В данной статье строго математически рассматривается проблема оценки параметров в моделях со скрытыми переменными. Будет показано, как невозможность прямой оптимизации приводит нас к необходимости введения нижней границы обоснованности (Evidence Lower Bound, или ELBO) и как её поочередная максимизация порождает EM-алгоритм (Expectation-Maximization).

Математическая постановка задачи

Пусть задана наблюдаемая выборка $X = \{x_1, \dots, x_N\}$ , состоящая из независимых одинаково распределенных случайных величин. Мы предполагаем, что каждому объекту $x_i$ соответствует вектор ненаблюдаемых скрытых (латентных) переменных $z_i$ . Обозначим множество всех скрытых переменных как $Z = \{z_1, \dots, z_N\}$ .

Задана вероятностная модель совместного распределения наблюдаемых и скрытых переменных, параметризованная вектором параметров $\theta$ :

$p(X, Z \mid \theta) = \prod_{i=1}^N p(x_i, z_i \mid \theta)$

Стандартный подход к поиску параметров — метод максимального правдоподобия (MLE). Наша цель — максимизировать маргинальное правдоподобие (обоснованность, evidence) данных $p(X \mid \theta)$ . Для удобства максимизируют его логарифм:

$\ln p(X \mid \theta) = \ln \int p(X, Z \mid \theta) dZ = \sum_{i=1}^N \ln \int p(x_i, z_i \mid \theta) dz_i$

(Если скрытые переменные дискретны, интеграл заменяется на сумму).

Проблема: Логарифм нелинеен. В приведенном выше выражении сумма (или интеграл) по скрытым переменным находится под знаком логарифма. Из-за этого аналитически вычислить градиент по $\theta$ и приравнять его к нулю в большинстве случаев невозможно. Прямое вычисление требует маргинализации по всем возможным конфигурациям $Z$ , что ведет к комбинаторному взрыву или необходимости брать неберущиеся многомерные интегралы.

Вариационная нижняя оценка (ELBO)

Чтобы обойти проблему суммы под логарифмом, вводится вспомогательное произвольное распределение $q(Z)$ над скрытыми переменными. Мы можем переписать логарифм маргинального правдоподобия, умножив и разделив совместную вероятность на $q(Z)$ :

$\ln p(X \mid \theta) = \ln \int q(Z) \frac{p(X, Z \mid \theta)}{q(Z)} dZ$

Рассматривая интеграл как математическое ожидание по распределению $q(Z)$ , применим неравенство Йенсена для вогнутой функции логарифма ( $\ln \mathbf{E}[f] \geq \mathbf{E}[\ln f]$ ):

$\ln p(X \mid \theta) \geq \int q(Z) \ln \frac{p(X, Z \mid \theta)}{q(Z)} dZ$

Правая часть этого неравенства называется вариационной нижней оценкой или ELBO (Evidence Lower Bound). Обозначим её как $\mathcal{L}(q, \theta)$ :

$\mathcal{L}(q, \theta) = \int q(Z) \ln \frac{p(X, Z \mid \theta)}{q(Z)} dZ$

Связь ELBO и KL-дивергенции

Чтобы лучше понять смысл ELBO, рассмотрим разницу между истинным логарифмом правдоподобия и нижней оценкой:

$\ln p(X \mid \theta) - \mathcal{L}(q, \theta) = \ln p(X \mid \theta) - \int q(Z) \ln \frac{p(X, Z \mid \theta)}{q(Z)} dZ$

Внесем $\ln p(X \mid \theta)$ под интеграл (так как интеграл от $q(Z)$ равен 1) и используем правило Байеса $p(X, Z \mid \theta) = p(Z \mid X, \theta) p(X \mid \theta)$ :

$\ln p(X \mid \theta) - \mathcal{L}(q, \theta) = \int q(Z) \left( \ln p(X \mid \theta) - \ln \frac{p(Z \mid X, \theta) p(X \mid \theta)}{q(Z)} \right) dZ$

$\ln p(X \mid \theta) - \mathcal{L}(q, \theta) = - \int q(Z) \ln \frac{p(Z \mid X, \theta)}{q(Z)} dZ = \int q(Z) \ln \frac{q(Z)}{p(Z \mid X, \theta)} dZ$

Полученное выражение — это в точности дивергенция Кульбака-Лейблера (KL-дивергенция) между распределением $q(Z)$ и истинным апостериорным распределением $p(Z \mid X, \theta)$ . Итак, мы получаем фундаментальное тождество:

$\ln p(X \mid \theta) = \mathcal{L}(q, \theta) + \mathrm{KL}(q(Z) || p(Z \mid X, \theta))$

Поскольку KL-дивергенция всегда неотрицательна ( $\mathrm{KL} \geq 0$ ), $\mathcal{L}(q, \theta)$ действительно является нижней оценкой для логарифма правдоподобия.

Обобщенный EM-алгоритм

Вместо того чтобы напрямую максимизировать сложный логарифм маргинального правдоподобия, EM-алгоритм осуществляет координатный подъем (максимизацию) по функции ELBO $\mathcal{L}(q, \theta)$ . Алгоритм итеративно обновляет распределение $q$ и параметры $\theta$ .

E-шаг (Expectation)

На итерации $t$ вектор параметров зафиксирован и равен $\theta^{(t)}$ . Мы хотим максимизировать $\mathcal{L}(q, \theta^{(t)})$ по распределению $q(Z)$ . Из фундаментального тождества видно, что при фиксированном логарифме правдоподобия максимизация ELBO эквивалентна минимизации KL-дивергенции. Минимум KL-дивергенции равен нулю и достигается тогда и только тогда, когда распределения совпадают:

$q^{(t+1)}(Z) = p(Z \mid X, \theta^{(t)})$

Таким образом, на E-шаге мы находим истинное апостериорное распределение скрытых переменных при текущих параметрах. В этот момент ELBO "касается" логарифма правдоподобия: $\mathcal{L}(q^{(t+1)}, \theta^{(t)}) = \ln p(X \mid \theta^{(t)})$ .

M-шаг (Maximization)

Теперь фиксируем $q(Z) = q^{(t+1)}(Z)$ и максимизируем ELBO по параметрам $\theta$ :

$\mathcal{L}(q^{(t+1)}, \theta) = \int q^{(t+1)}(Z) \ln p(X, Z \mid \theta) dZ - \int q^{(t+1)}(Z) \ln q^{(t+1)}(Z) dZ$

Второе слагаемое (энтропия $q$ ) не зависит от $\theta$ , поэтому мы можем его отбросить при оптимизации. Остается максимизировать математическое ожидание полного логарифма правдоподобия, которое традиционно обозначают как $Q(\theta, \theta^{(t)})$ :

$Q(\theta, \theta^{(t)}) = \int p(Z \mid X, \theta^{(t)}) \ln p(X, Z \mid \theta) dZ$

$\theta^{(t+1)} = \arg\max_\theta Q(\theta, \theta^{(t)})$

Доказательство корректности: На E-шаге мы подтянули нижнюю границу к значению функции: $\ln p(X \mid \theta^{(t)}) = \mathcal{L}(q^{(t+1)}, \theta^{(t)})$ . На M-шаге мы увеличиваем саму границу: $\mathcal{L}(q^{(t+1)}, \theta^{(t+1)}) \geq \mathcal{L}(q^{(t+1)}, \theta^{(t)})$ . Поскольку $\ln p(X \mid \theta^{(t+1)}) \geq \mathcal{L}(q^{(t+1)}, \theta^{(t+1)})$ , из этого строго следует, что каждая итерация EM-алгоритма не уменьшает маргинальное правдоподобие:

$\ln p(X \mid \theta^{(t+1)}) \geq \ln p(X \mid \theta^{(t)})$

Практический пример: Разделение смеси гауссовских распределений (GMM)

Рассмотрим задачу мягкой кластеризации с помощью смеси гауссовских распределений (GMM). Даны точки $X$ . Предполагается, что существует $K$ кластеров. Скрытая переменная $z_i \in \{1, \dots, K\}$ указывает, из какого кластера сгенерирована точка $x_i$ .

Параметры модели: $\theta = \{\pi_k, \mu_k, \Sigma_k\}_{k=1}^K$ , где $\pi_k$ — априорная вероятность кластера, $\mu_k$ и $\Sigma_k$ — вектор средних и матрица ковариации гауссовского распределения кластера $k$ . Совместное правдоподобие одной точки: $p(x_i, z_i=k \mid \theta) = \pi_k \mathcal{N}(x_i \mid \mu_k, \Sigma_k)$ .

E-шаг: Вычисляем $q^{(t+1)}(Z)$ , то есть апостериорные вероятности принадлежности точек кластерам (матрицу «ответственностей» $\gamma_{ik}$ ):

$\gamma_{ik} = p(z_i = k \mid x_i, \theta^{(t)}) = \frac{\pi_k \mathcal{N}(x_i \mid \mu_k, \Sigma_k)}{\sum_{j=1}^K \pi_j \mathcal{N}(x_i \mid \mu_j, \Sigma_j)}$

M-шаг: Максимизируем функцию $Q$ по $\theta$ . Приравнивая производные к нулю, получаем аналитические формулы обновления параметров. Обозначив эффективное число точек в кластере $k$ как $N_k = \sum_{i=1}^N \gamma_{ik}$ , получим:

$\pi_k^{(t+1)} = \frac{N_k}{N}$

$\mu_k^{(t+1)} = \frac{1}{N_k} \sum_{i=1}^N \gamma_{ik} x_i$

$\Sigma_k^{(t+1)} = \frac{1}{N_k} \sum_{i=1}^N \gamma_{ik} (x_i - \mu_k^{(t+1)})(x_i - \mu_k^{(t+1)})^{\mathrm{T}}$

Этот процесс является теоретически обоснованным вероятностным обобщением эвристического алгоритма K-средних (где вероятности $\gamma_{ik}$ принимают только жесткие значения 0 или 1).

См. также

Литература

Christopher M. Bishop. Pattern Recognition and Machine Learning. — Springer, 2006. — Глава 9 (Mixture Models and EM).
Kevin P. Murphy. Machine Learning: A Probabilistic Perspective. — MIT Press, 2012. — Глава 11 (Mixture models and the EM algorithm).
Воронцов К. В. Математические методы обучения по прецедентам (Курс лекций). — МФТИ, 2007.

Источник — «http://recognition.su/wiki/index.php?title=EM-%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%B8_ELBO»