Просмотр

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

У вас нет прав на выполнение этой операции по следующим причинам:

• Запрошенное действие могут выполнять только участники из групп emailconfirmed, Администраторы.
• Вы должны подтвердить ваш адрес электронной почты перед правкой страниц. Пожалуйста, введите и подтвердите ваш адрес эл. почты на странице настроек.

Вы можете просмотреть и скопировать исходный текст этой страницы:

{{well|Статья написана с использованием LLM '''Gemini Pro 3.1''' и проверена участником [[Участник:Nikita Zinoviсh|Nikita Zinoviсh]] 01:45, 16 июля 2026 (MSD)}} == Введение == В задачах [[Обучение без учителя|обучения без учителя]] (таких как кластеризация или понижение размерности) мы часто предполагаем, что наблюдаемые данные порождены некоторым вероятностным процессом, который зависит от ненаблюдаемых, или [[Скрытая переменная|скрытых переменных]]. Переход от эвристических алгоритмов к строгим [[Генеративная модель|генеративным моделям]] позволяет не только находить структуру в данных, но и оценивать уверенность в предсказаниях, а также генерировать новые объекты. Однако введение скрытых переменных делает прямое применение классических методов статистики вычислительно невозможным. В данной статье строго математически рассматривается проблема оценки параметров в моделях со скрытыми переменными. Будет показано, как невозможность прямой оптимизации приводит нас к необходимости введения нижней границы обоснованности (Evidence Lower Bound, или ELBO) и как её поочередная максимизация порождает [[EM-алгоритм]] (Expectation-Maximization). == Математическая постановка задачи == Пусть задана наблюдаемая выборка <tex> X = \{x_1, \dots, x_N\} </tex>, состоящая из независимых одинаково распределенных случайных величин. Мы предполагаем, что каждому объекту <tex> x_i </tex> соответствует вектор ненаблюдаемых скрытых (латентных) переменных <tex> z_i </tex>. Обозначим множество всех скрытых переменных как <tex> Z = \{z_1, \dots, z_N\} </tex>. Задана вероятностная модель совместного распределения наблюдаемых и скрытых переменных, параметризованная вектором параметров <tex> \theta </tex>: :<tex> p(X, Z \mid \theta) = \prod_{i=1}^N p(x_i, z_i \mid \theta) </tex> Стандартный подход к поиску параметров — [[Метод максимального правдоподобия|метод максимального правдоподобия]] (MLE). Наша цель — максимизировать маргинальное правдоподобие (обоснованность, evidence) данных <tex> p(X \mid \theta) </tex>. Для удобства максимизируют его логарифм: :<tex> \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 </tex> (Если скрытые переменные дискретны, интеграл заменяется на сумму). '''Проблема:''' Логарифм нелинеен. В приведенном выше выражении сумма (или интеграл) по скрытым переменным находится ''под знаком логарифма''. Из-за этого аналитически вычислить градиент по <tex> \theta </tex> и приравнять его к нулю в большинстве случаев невозможно. Прямое вычисление требует маргинализации по всем возможным конфигурациям <tex> Z </tex>, что ведет к комбинаторному взрыву или необходимости брать неберущиеся многомерные интегралы. == Вариационная нижняя оценка (ELBO) == Чтобы обойти проблему суммы под логарифмом, вводится вспомогательное произвольное распределение <tex> q(Z) </tex> над скрытыми переменными. Мы можем переписать логарифм маргинального правдоподобия, умножив и разделив совместную вероятность на <tex> q(Z) </tex>: :<tex> \ln p(X \mid \theta) = \ln \int q(Z) \frac{p(X, Z \mid \theta)}{q(Z)} dZ </tex> Рассматривая интеграл как [[Математическое ожидание|математическое ожидание]] по распределению <tex> q(Z) </tex>, применим [[Неравенство Йенсена|неравенство Йенсена]] для вогнутой функции логарифма (<tex> \ln \mathbf{E}[f] \geq \mathbf{E}[\ln f] </tex>): :<tex> \ln p(X \mid \theta) \geq \int q(Z) \ln \frac{p(X, Z \mid \theta)}{q(Z)} dZ </tex> Правая часть этого неравенства называется '''вариационной нижней оценкой''' или '''ELBO''' (Evidence Lower Bound). Обозначим её как <tex> \mathcal{L}(q, \theta) </tex>: :<tex> \mathcal{L}(q, \theta) = \int q(Z) \ln \frac{p(X, Z \mid \theta)}{q(Z)} dZ </tex> === Связь ELBO и KL-дивергенции === Чтобы лучше понять смысл ELBO, рассмотрим разницу между истинным логарифмом правдоподобия и нижней оценкой: :<tex> \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 </tex> Внесем <tex> \ln p(X \mid \theta) </tex> под интеграл (так как интеграл от <tex> q(Z) </tex> равен 1) и используем правило Байеса <tex> p(X, Z \mid \theta) = p(Z \mid X, \theta) p(X \mid \theta) </tex>: :<tex> \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 </tex> :<tex> \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 </tex> Полученное выражение — это в точности [[Расстояние Кульбака-Лейблера|дивергенция Кульбака-Лейблера]] (KL-дивергенция) между распределением <tex> q(Z) </tex> и истинным [[Апостериорная вероятность|апостериорным распределением]] <tex> p(Z \mid X, \theta) </tex>. Итак, мы получаем фундаментальное тождество: :<tex> \ln p(X \mid \theta) = \mathcal{L}(q, \theta) + \mathrm{KL}(q(Z) || p(Z \mid X, \theta)) </tex> Поскольку KL-дивергенция всегда неотрицательна (<tex> \mathrm{KL} \geq 0 </tex>), <tex> \mathcal{L}(q, \theta) </tex> действительно является нижней оценкой для логарифма правдоподобия. == Обобщенный EM-алгоритм == Вместо того чтобы напрямую максимизировать сложный логарифм маргинального правдоподобия, EM-алгоритм осуществляет [[Метод координатного спуска|координатный подъем]] (максимизацию) по функции ELBO <tex> \mathcal{L}(q, \theta) </tex>. Алгоритм итеративно обновляет распределение <tex> q </tex> и параметры <tex> \theta </tex>. === E-шаг (Expectation) === На итерации <tex> t </tex> вектор параметров зафиксирован и равен <tex> \theta^{(t)} </tex>. Мы хотим максимизировать <tex> \mathcal{L}(q, \theta^{(t)}) </tex> по распределению <tex> q(Z) </tex>. Из фундаментального тождества видно, что при фиксированном логарифме правдоподобия максимизация ELBO эквивалентна ''минимизации'' KL-дивергенции. Минимум KL-дивергенции равен нулю и достигается тогда и только тогда, когда распределения совпадают: :<tex> q^{(t+1)}(Z) = p(Z \mid X, \theta^{(t)}) </tex> Таким образом, на E-шаге мы находим истинное апостериорное распределение скрытых переменных при текущих параметрах. В этот момент ELBO "касается" логарифма правдоподобия: <tex> \mathcal{L}(q^{(t+1)}, \theta^{(t)}) = \ln p(X \mid \theta^{(t)}) </tex>. === M-шаг (Maximization) === Теперь фиксируем <tex> q(Z) = q^{(t+1)}(Z) </tex> и максимизируем ELBO по параметрам <tex> \theta </tex>: :<tex> \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 </tex> Второе слагаемое (энтропия <tex> q </tex>) не зависит от <tex> \theta </tex>, поэтому мы можем его отбросить при оптимизации. Остается максимизировать математическое ожидание полного логарифма правдоподобия, которое традиционно обозначают как <tex> Q(\theta, \theta^{(t)}) </tex>: :<tex> Q(\theta, \theta^{(t)}) = \int p(Z \mid X, \theta^{(t)}) \ln p(X, Z \mid \theta) dZ </tex> :<tex> \theta^{(t+1)} = \arg\max_\theta Q(\theta, \theta^{(t)}) </tex> '''Доказательство корректности:''' На E-шаге мы подтянули нижнюю границу к значению функции: <tex> \ln p(X \mid \theta^{(t)}) = \mathcal{L}(q^{(t+1)}, \theta^{(t)}) </tex>. На M-шаге мы увеличиваем саму границу: <tex> \mathcal{L}(q^{(t+1)}, \theta^{(t+1)}) \geq \mathcal{L}(q^{(t+1)}, \theta^{(t)}) </tex>. Поскольку <tex> \ln p(X \mid \theta^{(t+1)}) \geq \mathcal{L}(q^{(t+1)}, \theta^{(t+1)}) </tex>, из этого строго следует, что каждая итерация EM-алгоритма не уменьшает маргинальное правдоподобие: :<tex> \ln p(X \mid \theta^{(t+1)}) \geq \ln p(X \mid \theta^{(t)}) </tex> == Практический пример: Разделение смеси гауссовских распределений (GMM) == Рассмотрим задачу мягкой кластеризации с помощью [[Модель гауссовской смеси|смеси гауссовских распределений]] (GMM). Даны точки <tex> X </tex>. Предполагается, что существует <tex> K </tex> кластеров. Скрытая переменная <tex> z_i \in \{1, \dots, K\} </tex> указывает, из какого кластера сгенерирована точка <tex> x_i </tex>. Параметры модели: <tex> \theta = \{\pi_k, \mu_k, \Sigma_k\}_{k=1}^K </tex>, где <tex> \pi_k </tex> — априорная вероятность кластера, <tex> \mu_k </tex> и <tex> \Sigma_k </tex> — вектор средних и матрица ковариации гауссовского распределения кластера <tex> k </tex>. Совместное правдоподобие одной точки: <tex> p(x_i, z_i=k \mid \theta) = \pi_k \mathcal{N}(x_i \mid \mu_k, \Sigma_k) </tex>. '''E-шаг:''' Вычисляем <tex> q^{(t+1)}(Z) </tex>, то есть апостериорные вероятности принадлежности точек кластерам (матрицу «ответственностей» <tex> \gamma_{ik} </tex>): :<tex> \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)} </tex> '''M-шаг:''' Максимизируем функцию <tex> Q </tex> по <tex> \theta </tex>. Приравнивая производные к нулю, получаем аналитические формулы обновления параметров. Обозначив эффективное число точек в кластере <tex> k </tex> как <tex> N_k = \sum_{i=1}^N \gamma_{ik} </tex>, получим: :<tex> \pi_k^{(t+1)} = \frac{N_k}{N} </tex> :<tex> \mu_k^{(t+1)} = \frac{1}{N_k} \sum_{i=1}^N \gamma_{ik} x_i </tex> :<tex> \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}} </tex> Этот процесс является теоретически обоснованным вероятностным обобщением эвристического [[Алгоритм k-means|алгоритма K-средних]] (где вероятности <tex> \gamma_{ik} </tex> принимают только жесткие значения 0 или 1). == См. также == * [[Метод максимального правдоподобия]] * [[Алгоритм k-means]] * [[Модель гауссовской смеси]] * [[Вариационный байесовский вывод]] * [[Скрытая марковская модель]] == Литература == * ''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.

• Шаблон:Mbox
• Шаблон:Well

Возврат к странице EM-алгоритм и ELBO.