Дивергенция Брэгмана

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

(Различия между версиями)

Версия 14:35, 15 июля 2026

Статья написана с использованием LLM ChatGPT (GPT-5.6 Sol Medium) и проверена участником Aleksei Kovalenko 18:00, 15 июля 2026 (MSD). Промпт приводится полностью в Обсуждение:Дивергенция Брэгмана.

Содержание

1 Определение и геометрический смысл
- 1.1 Геометрическая интуиция
2 Основные свойства и тождества
3 Сопряжённость Лежандра и двойственная геометрия
4 Проекции и теорема Пифагора
5 Выбор порождающей функции
6 Важные частные случаи
7 Центроиды и разложение ожидаемого риска
8 Применения в машинном обучении
9 Сравнение с другими мерами различия
- 9.1 Брэгмановские и f-дивергенции
10 Практические преимущества
11 Ограничения и типичные ошибки
12 Новые обобщения и варианты
13 Примечания
14 Литература

Дивергенция Брэгмана (также расхождение Брэгмана, иногда расстояние Брэгмана) — неотрицательная мера различия двух точек, порождённая выпуклой функцией как ошибка её линеаризации первого порядка. В отличие от метрики, она, вообще говоря, не симметрична и не удовлетворяет неравенству треугольника. Её основное назначение — согласовать понятие близости с геометрией задачи: симплекс вероятностей естественно снабжается энтропийной геометрией, положительный ортант — логарифмической, а евклидово пространство — квадратичной.

Понятие введено Л. М. Брэгманом в 1967 году при исследовании последовательных проекций на выпуклые множества.^[1] В современной теории дивергенции Брэгмана связывают Выпуклый анализ, сопряжённость Фенхеля — Лежандра, информационную геометрию, Зеркальный спуск, экспоненциальные семейства и методы обучения статистических моделей.

Определение и геометрический смысл

Пусть $V$ — конечномерное вещественное линейное пространство, $V^*$ — сопряжённое к нему пространство, $\langle\cdot,\cdot\rangle$ — двойственное спаривание, а $\Omega\subset V$ — открытое выпуклое множество. Пусть порождающая функция $\phi:\Omega\to\mathbb R$ дифференцируема и строго выпукла. Дивергенцией Брэгмана, порождённой $\phi$ , называется функция

$D_\phi(x,y)=\phi(x)-\phi(y)-\langle\nabla\phi(y),x-y\rangle,\qquad x,y\in\Omega.$

Для собственной замкнутой выпуклой функции $\phi:V\to\mathbb R\cup\{+\infty\}$ то же определение применяют при $x\in\operatorname{dom}\phi$ и $y\in\operatorname{int}(\operatorname{dom}\phi)$ , где градиент существует. Если функция не дифференцируема, выбор субградиента даёт уже обобщённую, зависящую от этого выбора конструкцию, а не классическую дивергенцию Брэгмана.

Геометрическая интуиция

Гиперплоскость

$z=\phi(y)+\langle\nabla\phi(y),x-y\rangle$

касательна к графику $\phi$ в точке $y$ . Величина $D_\phi(x,y)$ есть вертикальный зазор между графиком функции в $x$ и этой касательной. Из выпуклости касательная не лежит выше графика, поэтому зазор неотрицателен. Асимметрия возникает потому, что касательные в $x$ и $y$ различны: обычно $D_\phi(x,y)\ne D_\phi(y,x)$ .

Если $\phi$ дважды непрерывно дифференцируема, то локально

$D_\phi(y+h,y)=\frac12\langle h,\nabla^2\phi(y)h\rangle+o(\|h\|^2).$

Следовательно, гессиан $\nabla^2\phi(y)$ задаёт зависящую от точки локальную квадратичную геометрию. Дивергенция является конечным, направленным аналогом квадрата длины, накопленного в этой геометрии, но не обязана совпадать с квадратом геодезического расстояния.

Основные свойства и тождества

Ниже предполагается, что $\Omega$ выпукло, а $\phi$ дифференцируема и выпукла на $\Omega$ . Строгая выпуклость указывается отдельно там, где она необходима.

Неотрицательность, определённость и выпуклость

$D_\phi(x,y)\ge 0$ . Это непосредственно следует из неравенства первого порядка для выпуклой функции.
Если $\phi$ строго выпукла, то $D_\phi(x,y)=0$ тогда и только тогда, когда $x=y$ . Без строгой выпуклости равенство нулю возможно для различных точек.
При фиксированном $y$ отображение $x\mapsto D_\phi(x,y)$ выпукло; при строгой выпуклости $\phi$ оно строго выпукло. По второму аргументу выпуклости в общем случае нет.
Добавление аффинной функции не меняет дивергенцию:

$D_{\phi+\langle a,\cdot\rangle+b}(x,y)=D_\phi(x,y).$

Для неотрицательных коэффициентов $\alpha_i$ выполняется линейность по генератору:

$D_{\sum_i\alpha_i\phi_i}(x,y)=\sum_i\alpha_iD_{\phi_i}(x,y).$

Дифференциальные и интегральные представления

Если $\phi\in C^2(\Omega)$ , то

$\nabla_xD_\phi(x,y)=\nabla\phi(x)-\nabla\phi(y),$

$\nabla_yD_\phi(x,y)=\nabla^2\phi(y)(y-x).$

Если отрезок между $x$ и $y$ лежит в $\Omega$ , остаток Тейлора имеет точное интегральное представление

$D_\phi(x,y)=\int_0^1(1-t)\langle x-y,\nabla^2\phi(y+t(x-y))(x-y)\rangle\,dt.$

Оно показывает, что дивергенция усредняет кривизну генератора вдоль отрезка и позволяет переводить ограничения на гессиан в двусторонние оценки.

Трёхточечное тождество

Для любых $x,y,z\in\Omega$

$D_\phi(x,z)-D_\phi(x,y)-D_\phi(y,z)=\langle\nabla\phi(y)-\nabla\phi(z),x-y\rangle.$

Это тождество заменяет евклидов «закон косинусов» и является базовым при доказательстве сходимости зеркального спуска, проксимальных методов и алгоритмов Брэгмановских проекций. В частности,

$D_\phi(x,y)+D_\phi(y,x)=\langle\nabla\phi(x)-\nabla\phi(y),x-y\rangle.$

Последняя величина неотрицательна вследствие монотонности градиента выпуклой функции.

Нормы, двойственные нормы и сильная выпуклость

Пусть $\|\cdot\|$ — норма на $V$ , а двойственная норма на $V^*$ определена как

$\|s\|_* = \sup_{\|x\|\le 1}\langle s,x\rangle.$

Если $\phi$ является $\mu$ -сильно выпуклой относительно $\|\cdot\|$ , то есть для всех допустимых $x,y$

$\phi(x)\ge\phi(y)+\langle\nabla\phi(y),x-y\rangle+\frac\mu2\|x-y\|^2,$

то

$D_\phi(x,y)\ge\frac\mu2\|x-y\|^2.$

Если градиент $\phi$ является $L$ -липшицевым из $(V,\|\cdot\|)$ в $(V^*,\|\cdot\|_*)$ , то по лемме о спуске

$D_\phi(x,y)\le\frac L2\|x-y\|^2.$

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

$\mu I\preceq\nabla^2\phi(u)\preceq LI$

для всех точек $u$ рассматриваемой выпуклой области. Для энтропийных генераторов верхняя глобальная оценка часто отсутствует у границы симплекса, хотя нижняя оценка может следовать из неравенства Пинскера. Поэтому подмена дивергенции квадратом нормы без проверки области и констант некорректна.

Связка «норма — двойственная норма — сильно выпуклый генератор» определяет сложностные оценки первого порядка. Например, на вероятностном симплексе отрицательная энтропия сильно выпукла относительно нормы $\ell_1$ , а субградиенты оцениваются в двойственной норме $\ell_\infty$ ; это устраняет лишнюю степенную зависимость от размерности, возникающую при неудачном евклидовом моделировании.

Сопряжённость Лежандра и двойственная геометрия

Сопряжённая по Фенхелю функция определяется как

$\phi^*(s)=\sup_{x\in V}\{\langle s,x\rangle-\phi(x)\}.$

Собственная замкнутая выпуклая функция называется легандровой, если она существенно гладкая и существенно строго выпуклая в смысле Рокафеллара.^[1] Существенная гладкость включает дифференцируемость во внутренности области определения и неограниченный рост нормы градиента при приближении к её границе; существенная строгая выпуклость требует строгой выпуклости на каждом выпуклом подмножестве области субдифференциала.

Для легандровой $\phi$ отображение

$\nabla\phi:\operatorname{int}(\operatorname{dom}\phi)\longrightarrow\operatorname{int}(\operatorname{dom}\phi^*)$

является взаимно однозначным, а

$(\nabla\phi)^{-1}=\nabla\phi^*.$

Точки $x$ называют прямыми координатами, а $s=\nabla\phi(x)$ — двойственными. Равенство Фенхеля — Юнга даёт представление дивергенции как разрыва двойственности:

$D_\phi(x,y)=\phi(x)+\phi^*(\nabla\phi(y))-\langle x,\nabla\phi(y)\rangle.$

Двойственная дивергенция меняет порядок аргументов:

$D_\phi(x,y)=D_{\phi^*}(\nabla\phi(y),\nabla\phi(x)).$

Именно эта смена порядка объясняет две естественные системы координат в информационной геометрии экспоненциальных семейств: натуральные параметры и параметры математического ожидания. Легандровы генераторы также обеспечивают корректное поведение зеркального отображения у границы области и служат стандартным контекстом для теории Брэгмановских проекций.^[1]

Проекции и теорема Пифагора

Пусть $C$ — непустое выпуклое множество. Левая Брэгмановская проекция точки $y$ определяется как

$P_C^\phi(y)\in\operatorname*{argmin}_{x\in C}D_\phi(x,y).$

Если $\phi$ строго выпукла, проекция единственна при условии существования. Существование, например, гарантируется, когда $C$ замкнуто, функция $D_\phi(\cdot,y)$ полунепрерывна снизу и её подуровневые множества на $C$ компактны; одной лишь замкнутости в неограниченной области без коэрцитивности недостаточно.

Если $p=P_C^\phi(y)$ , $C$ выпукло и дифференцируемость имеет место в $p$ и $y$ , условие оптимальности имеет вид

$\langle\nabla\phi(p)-\nabla\phi(y),x-p\rangle\ge 0\qquad(\forall x\in C).$

Совместно с трёхточечным тождеством оно даёт обобщённое неравенство Пифагора

$D_\phi(x,y)\ge D_\phi(x,p)+D_\phi(p,y),\qquad x\in C.$

Для аффинного $C$ , если допустимы вариации в обоих направлениях, неравенство становится равенством. Следует различать левую проекцию, минимизирующую по первому аргументу, и правую проекцию, минимизирующую по второму: из-за асимметрии их свойства и вычислительная сложность различаются.

Выбор порождающей функции

Выбор $\phi$ — это выбор геометрии, а не косметическая замена функции потерь. Практически полезный генератор должен удовлетворять нескольким требованиям.

Область определения. Она должна совпадать с ограничениями параметров: симплекс, положительный ортант, конус положительно определённых матриц или всё пространство.
Кривизна. Гессиан должен отражать направления и масштабы, в которых ошибка существенна. Слишком малая кривизна даёт слабый контроль нормы, слишком большая у границы — численную неустойчивость.
Вычислимость зеркального шага. Нужны доступные $\nabla\phi$ , $\nabla\phi^*$ и Брэгмановская проекция. Дешёвая оценка самой дивергенции не гарантирует дешёвого алгоритма.
Статистическая согласованность. Для правдоподобия экспоненциального семейства естественен генератор, связанный с логарифмической нормировочной функцией или её сопряжённой; для мультипликативного шума — масштабно-инвариантная геометрия Итакуры — Сайто.
Согласование с нормой. В анализе оптимизации $\phi$ выбирают сильно выпуклой относительно нормы, в которой ограничены допустимое множество и градиенты.

Аффинные добавки к генератору несущественны, а умножение $\phi$ на положительную константу лишь масштабирует дивергенцию. Нелинейная монотонная замена генератора, напротив, обычно меняет геометрию полностью.

Важные частные случаи

Квадрат евклидова расстояния

Для

$\phi(x)=\frac12\|x\|_2^2$

получаем

$D_\phi(x,y)=\frac12\|x-y\|_2^2.$

Это симметричный частный случай с постоянным гессианом. Если использовать $\phi(x)=\|x\|_2^2$ , множитель $1/2$ исчезает из дивергенции; обе конвенции встречаются в литературе.

Квадрат расстояния Махаланобиса

Пусть $Q$ — симметричная положительно определённая матрица и

$\phi(x)=\frac12x^{\mathsf{T}}Qx.$

Тогда

$D_\phi(x,y)=\frac12(x-y)^{\mathsf{T}}Q(x-y).$

Положительная полуопределённость $Q$ обеспечивает неотрицательность, но не строгую определённость: различные точки могут иметь нулевое расхождение вдоль ядра. Если открытая выпуклая область связна, а строго выпуклый генератор принадлежит классу $C^2$ , симметричность $D_\phi$ на всей области влечёт постоянство $\nabla^2\phi$ . Поэтому генератор квадратичен с точностью до аффинного слагаемого, а дивергенция является квадратом обобщённого евклидова расстояния.^[1]

Дивергенция Кульбака — Лейблера

На положительном ортанте для отрицательной энтропии

$\phi(x)=\sum_{i=1}^d x_i\log x_i$

возникает обобщённая дивергенция Кульбака — Лейблера

$D_\phi(x,y)=\sum_{i=1}^d\left(x_i\log\frac{x_i}{y_i}-x_i+y_i\right).$

На вероятностном симплексе линейные члены сокращаются:

$D_\phi(p,q)=\sum_{i=1}^d p_i\log\frac{p_i}{q_i}=D_{\mathrm{KL}}(p\|q).$

Используется стандартное продолжение по непрерывности: слагаемое с $p_i=0$ равно нулю, а при $p_i>0$ и $q_i=0$ значение бесконечно. Таким образом, Дивергенция Кульбака — Лейблера одновременно является дивергенцией Брэгмана на симплексе и f-дивергенцией, но это исключительный случай, а не тождество двух классов.

Расстояние Итакуры — Сайто

Для положительных координат и логарифмического барьера

$\phi(x)=-\sum_{i=1}^d\log x_i$

получаем

$D_\phi(x,y)=\sum_{i=1}^d\left(\frac{x_i}{y_i}-\log\frac{x_i}{y_i}-1\right).$

Эта дивергенция масштабно-инвариантна при одновременном покоординатном масштабировании аргументов и особенно полезна для спектров мощности, аудиосигналов и моделей мультипликативного шума. Название «расстояние» историческое: симметрии и неравенства треугольника нет.

Матричные генераторы

На конусе положительно определённых матриц генератор

$\phi(X)=-\log\det X$

задаёт LogDet-дивергенцию

$D_\phi(X,Y)=\operatorname{tr}(Y^{-1}X)-\log\det(Y^{-1}X)-d.$

Она учитывает геометрию ковариационных и прецизионных матриц. Для генератора на основе отрицательной квантовой энтропии возникает матричная относительная энтропия. Эти конструкции требуют контроля спектра: приближение к вырожденной матрице может приводить к бесконечным значениям и плохо обусловленным вычислениям.

Центроиды и разложение ожидаемого риска

Пусть случайный вектор $X$ интегрируем, $\mu=\mathbb E X$ принадлежит области определения, и все ниже стоящие ожидания конечны. Тогда для любого допустимого $y$

$\mathbb E D_\phi(X,y)=\mathbb E D_\phi(X,\mu)+D_\phi(\mu,y).$

Если $\phi$ строго выпукла, единственным минимумом ожидаемой дивергенции по второму аргументу является обычное среднее $\mu$ . Для конечной взвешенной выборки центр равен

$c=\frac{\sum_iw_ix_i}{\sum_iw_i}.$

Напротив, минимум по первому аргументу, при легандровой $\phi$ и существовании ожидания двойственных координат, удовлетворяет

$\nabla\phi(c)=\mathbb E\nabla\phi(X).$

Смешение этих двух задач — распространённая ошибка. Характеризация «среднее как минимизатор» тесно связана с точными разложениями смещения и разброса. Результат 2025 года утверждает: если непрерывная неотрицательная функция потерь с тождеством неразличимости допускает чистое аддитивное разложение «неустранимый шум — смещение — разброс» для всех допустимых распределений меток и предсказаний, то она является обобщённой дивергенцией Брэгмана после обратимой замены координат; для стандартной дивергенции дополнительная замена координат не нужна.^[1]

Применения в машинном обучении

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

В кластеризации алгоритм Bregman $k$ -means минимизирует

$\sum_{j=1}^k\sum_{x_i\in C_j}D_\phi(x_i,c_j).$

При фиксированных центрах объект относят к кластеру с наименьшей дивергенцией; при фиксированном разбиении центр обновляют арифметическим средним, если центр стоит во втором аргументе. Каждая из двух операций не увеличивает целевую функцию, поэтому алгоритм сходится к локальному минимуму за конечное число изменений разбиения при конечной выборке и однозначном разрешении равенств. Глобальная оптимальность, как и для обычного $k$ -means, не гарантируется.

Выбор генератора объединяет евклидов $k$ -means, информационную кластеризацию и варианты с расстоянием Итакуры — Сайто. Теория регулярных экспоненциальных семейств связывает жёсткую и мягкую Брэгмановскую кластеризацию с оцениванием смесей максимальным правдоподобием.^[1]

Экспоненциальные семейства и вероятностные модели

Регулярное минимальное экспоненциальное семейство имеет плотность

$p_\theta(z)=h(z)\exp\{\langle\theta,T(z)\rangle-A(\theta)\},$

где $A$ — строго выпуклая логарифмическая нормировочная функция, а $\nabla A(\theta)=\mathbb E_\theta T(Z)$ . Для двух параметров

$D_{\mathrm{KL}}(p_\theta\|p_\eta)=D_A(\eta,\theta).$

Порядок аргументов справа обращён. В координатах средних $\mu=\nabla A(\theta)$ та же величина выражается через $A^*$ благодаря двойственности Лежандра. Поэтому максимизация правдоподобия, согласование моментов и некоторые задачи байесовского оценивания допускают интерпретацию как Брэгмановские проекции. Это утверждение относится к регулярным минимальным семействам и не переносится автоматически на сингулярные или неминимальные параметризации.

Современные концентрационные оценки для общих многомерных экспоненциальных семейств также удобно формулируются через двойственные дивергенции Брэгмана между истинным параметром и выборочной оценкой.^[1]

Зеркальный спуск

Пусть требуется минимизировать выпуклую функцию $f$ на замкнутом выпуклом множестве $K$ . Шаг зеркального спуска с генератором $h$ имеет вид

$x_{t+1}=\operatorname*{argmin}_{x\in K}\left\{\eta_t\langle g_t,x\rangle+D_h(x,x_t)\right\},\qquad g_t\in\partial f(x_t).$

Без ограничений он эквивалентен шагу в двойственных координатах

$\nabla h(x_{t+1})=\nabla h(x_t)-\eta_tg_t.$

Если $h$ единично сильно выпукла относительно $\|\cdot\|$ , $\|g_t\|_*\le G$ , $D_h(x^*,x_1)\le R^2$ , шаг постоянен и все минимизаторы существуют, стандартный анализ даёт для усреднения $\bar x_T=T^{-1}\sum_{t=1}^Tx_t$

$f(\bar x_T)-f(x^*)\le\frac{R^2}{\eta T}+\frac{\eta G^2}{2}.$

При $\eta=\sqrt2R/(G\sqrt T)$ правая часть равна $\sqrt2RG/\sqrt T$ . Энтропийный генератор на симплексе приводит к мультипликативным весам, а квадратичный — к проекционному градиентному спуску. Метод введён Немировским и Юдиным и развит как нелинейный проекционный метод.^[1]^[1]

Относительная гладкость и Брэгмановские проксимальные методы

Евклидова липшицевость градиента слишком сильна для функций с быстро растущей кривизной. Функция $f$ называется $L$ -гладкой относительно выпуклой функции $h$ , если $Lh-f$ выпукла. Для дифференцируемых функций это эквивалентно

$D_f(x,y)\le L D_h(x,y)$

на рассматриваемой выпуклой области. При наличии вторых производных эквивалентное условие имеет вид

$\nabla^2f(x)\preceq L\nabla^2h(x).$

Эта идея позволяет анализировать первый порядок без глобальной евклидовой константы гладкости и выбирать опорную геометрию по кривизне целевой функции.^[1] Брэгмановские проксимально-градиентные и чередующиеся методы применяются также к структурированным невыпуклым задачам, но их гарантии требуют отдельных предпосылок — относительной гладкости, достаточного убывания, ограниченности итераций и, часто, свойства Курдыки — Лоясевича; классическая выпуклая теория сама по себе здесь неприменима.

Вариационный вывод

В вариационном выводе минимизируют отрицательную нижнюю оценку правдоподобия или дивергенцию между приближённым и целевым распределениями. Если вариационное семейство экспоненциально, функция лог-нормировки задаёт естественную Брэгмановскую геометрию параметров; зеркальные и Брэгмановские проксимальные шаги интерпретируются как регуляризованное согласование моментов. Важен порядок аргументов: прямая и обратная KL-дивергенции имеют различное статистическое поведение, а обратная KL в общем случае не является классической дивергенцией Брэгмана в тех же вероятностных координатах.

Для регуляризованной минимизации дивергенции Реньи над экспоненциальным семейством в 2025 году были получены детерминированные и стохастические Брэгмановские проксимально-градиентные схемы с интерпретацией как ослабленного согласования моментов.^[1] Это современное применение общей геометрии, а не новое определение классической дивергенции.

Матричная факторизация и представление данных

В неотрицательной матричной факторизации матрицу данных $V$ приближают произведением $WH$ , минимизируя покомпонентную дивергенцию

$\sum_{i,j}D_\phi(V_{ij},(WH)_{ij}).$

Квадратичная, обобщённая KL- и Итакура — Сайто-функции потерь соответствуют различным моделям шума. Для разделимого генератора вычисление цели стоит линейно по числу наблюдаемых элементов; главные затраты приходятся на матричные произведения и решение блочных подзадач. Обобщённые задачи приближения матриц с Брэгмановскими потерями охватывают NMF, совместную кластеризацию и задачи близости матриц.^[1]^[1]

Обучение вероятностных моделей и функции потерь

Если экспоненциальное семейство регулярно и минимально, а наблюдаемая достаточная статистика принадлежит области сопряжённого потенциала (либо дивергенция корректно продолжена на её границу), отрицательное логарифмическое правдоподобие можно записать, с точностью до членов, не зависящих от параметра, как дивергенцию Брэгмана между достаточной статистикой и средним параметром. Это связывает Максимальное правдоподобие, правильные правила оценки, калибровку вероятностей и предсказание условного среднего. Однако не всякая функция потерь и не всякая дивергенция распределений имеет Брэгмановскую форму; необходимы соответствующая выпуклая потенциальная функция и согласованная параметризация.

Сравнение с другими мерами различия

Мера	Симметрия и метрические свойства	Геометрия и инвариантность	Типичная стоимость для плотных векторов размерности $d$	Характерные применения
Дивергенция Брэгмана	Обычно несимметрична; неравенство треугольника обычно не выполняется; квадрат евклидова расстояния также не является метрикой	Задаётся выпуклым потенциалом и его локальным гессианом; двойственно плоская геометрия для легандровых генераторов	$O(d)$ для разделимого генератора; проекция или матричный гессиан могут быть существенно дороже	Зеркальный спуск, кластеризация, экспоненциальные семейства, матричная факторизация
Евклидово расстояние	Симметрично и является метрикой	Однородная изотропная геометрия, инвариантность к ортогональным преобразованиям	$O(d)$	Ближайшие соседи, геометрические данные, метод наименьших квадратов
Квадрат расстояния Махаланобиса	Симметричен, но без квадратного корня не является метрикой	Постоянная анизотропная квадратичная геометрия; требует положительно определённой матрицы	$O(d^2)$ с плотной матрицей, $O(d)$ с диагональной	Учёт ковариации, метрическое обучение, гауссовские модели
$f$ -дивергенция	Обычно несимметрична и не является метрикой	Сравнивает распределения через отношение плотностей; удовлетворяет неравенству обработки данных при стандартных предпосылках	$O(d)$ для дискретных распределений; для непрерывных зависит от интегрирования или оценивания	Проверка гипотез, теория информации, сравнение распределений, генеративные модели
Дивергенция Кульбака — Лейблера	Несимметрична и не является метрикой	Одновременно $f$ -дивергенция и Брэгмановская дивергенция отрицательной энтропии на симплексе; инвариантна при достаточных статистиках	$O(d)$ в дискретном случае при общей опоре	Максимальное правдоподобие, вариационный вывод, кодирование, информационная геометрия

Брэгмановские и f-дивергенции

Для выпуклой функции $f:(0,\infty)\to\mathbb R$ с $f(1)=0$ дискретная $f$ -дивергенция имеет вид

$D_f(P\|Q)=\sum_i q_i f\!\left(\frac{p_i}{q_i}\right).$

Она определена на распределениях и строится из отношения плотностей. Дивергенция Брэгмана строится из касательной к потенциалу на линейном или выпуклом пространстве параметров. Поэтому классы имеют разные инвариантности: $f$ -дивергенции подчиняются неравенству обработки данных, а произвольные дивергенции Брэгмана — нет. На конечном алфавите KL-дивергенция является, с точностью до положительного множителя и аффинных нормировок, единственной дивергенцией, принадлежащей обоим классам; для инвариантности относительно достаточных преобразований имеются уточнения, зависящие от размера алфавита.^[1]

Практические преимущества

Дивергенция Брэгмана практически предпочтительнее метрического расстояния, когда направленность ошибки содержательна и структура области важнее универсальной метрической индексации.

На симплексе энтропийная геометрия сохраняет положительность и нормировку без евклидовой проекции и приводит к простым мультипликативным обновлениям.
Для положительных интенсивностей KL- и Итакура — Сайто-потери согласуются с пуассоновским и мультипликативным типами шума лучше квадратичной ошибки.
В задачах с неоднородной кривизной относительная гладкость позволяет получить шаги и оценки там, где глобальная евклидова гладкость отсутствует.
Для экспоненциальных семейств дивергенция непосредственно выражает различие логарифмических правдоподобий и переводит оценивание в геометрию натуральных и средних параметров.
Брэгмановская проекция на некоторые множества имеет закрытую форму, хотя соответствующая евклидова проекция может быть дорогой или разрушать структуру.

Если же нужны симметричный поиск ближайших соседей, метрические деревья, интерпретируемые физические длины или гарантии, основанные на неравенстве треугольника, обычная метрика часто предпочтительнее.

Ограничения и типичные ошибки

Называть дивергенцию расстоянием без оговорки. В общем случае отсутствуют симметрия и неравенство треугольника; даже квадрат евклидова расстояния не является метрикой.
Игнорировать порядок аргументов. Он влияет на центроиды, проекции, робастность и поведение у границы. В KL-дивергенции перестановка аргументов меняет задачу.
Выбирать генератор только по знакомой формуле. Область определения, статистическая модель шума и стоимость зеркальной проекции важнее внешнего сходства.
Не проверять строгую или сильную выпуклость. Выпуклость даёт лишь неотрицательность; строгая выпуклость нужна для разделения точек, сильная — для квадратичной нижней оценки и стандартных скоростей сходимости.
Экстраполировать локальные оценки на всю область. Гессиан энтропии и логарифмического барьера неограничен у границы; константы гладкости и эквивалентности норм обычно зависят от компактного подмножества.
Забывать о границе и нулевых координатах. KL- и Итакура — Сайто-дивергенции могут быть бесконечны. На практике нужны согласованные правила продолжения, ограничение снизу или параметризация, сохраняющая положительность; произвольное добавление малого числа меняет целевую функцию.
Предполагать выпуклость по обоим аргументам. Гарантирована выпуклость только по первому аргументу. Оптимизация по второму может быть невыпуклой.
Считать любую обратную дивергенцию Брэгмановской. Функция $D_\phi(y,x)$ обычно не представима как $D_\psi(x,y)$ в тех же координатах; корректное обращение связано с переходом к $\phi^*$ и двойственным координатам.
Игнорировать вычислительную стоимость. Для плотного квадратичного генератора стоимость может быть квадратичной по размерности, для матричного LogDet — включать факторизацию матрицы, а для сложного множества основная цена приходится на проекцию.
Переносить выпуклые гарантии на невыпуклые модели. В NMF, глубоких моделях и вариационных семействах дивергенция не устраняет невыпуклость параметризации и не гарантирует глобального минимума.

Несимметричность также затрудняет метрическую индексацию и построение универсальных приближённых структур ближайших соседей. Численная устойчивость зависит от обусловленности гессиана, а статистическая робастность не следует из самого Брэгмановского представления: например, логарифмические потери чувствительны к вероятностям, близким к нулю.

Новые обобщения и варианты

Следующие конструкции следует отделять от классического определения 1967 года.

Функциональные дивергенции Брэгмана заменяют конечномерную функцию строго выпуклым функционалом и градиент — производной Фреше или Гато. Они применяются непосредственно к функциям и распределениям; корректность требует указания функционального пространства и вида производной.^[1]
Субградиентные обобщения допускают негладкий генератор и определяют расхождение относительно выбранного субградиента. Однозначность теряется, поэтому свойства классической конструкции необходимо доказывать заново.
Масштабированные дивергенции Брэгмана включают преобразование данных и положительный масштаб; специальная теорема позволяет представлять некоторые более общие и даже внешне невыпуклые искажения через обычную дивергенцию после преобразования.^[1]
Относительная гладкость и относительная сильная выпуклость сравнивают две функции через их Брэгмановские дивергенции. Это не новая дивергенция, а современная система предпосылок для анализа алгоритмов первого порядка.
Матричные, квантовые и операторные варианты используют выпуклые спектральные функции. В некоммутативном случае порядок множителей и область операторов существенны; скалярные тождества нельзя переносить формально.

Развитие после 2010-х годов сосредоточено главным образом не на замене исходного определения, а на адаптации геометрии к относительной гладкости, составным и невыпуклым задачам, стохастическим алгоритмам и вариационному выводу. Для каждого варианта необходимо явно указывать пространство, регулярность генератора и тот аргумент, по которому выполняется оптимизация.

Примечания

Литература

Bregman L. M. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming // USSR Computational Mathematics and Mathematical Physics. — 1967. — Т. 7. — № 3. — С. 200—217.
Rockafellar R. T. Convex Analysis. — Princeton: Princeton University Press, 1970. — 451 с.
Bauschke H. H.; Combettes P. L. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. — 2nd ed.. — Cham: Springer, 2017. — 619 с.
Bauschke H. H.; Borwein J. M. Legendre functions and the method of random Bregman projections // Journal of Convex Analysis. — 1997. — Т. 4. — № 1. — С. 27—67.
Nemirovski A. S.; Yudin D. B. Problem Complexity and Method Efficiency in Optimization. — New York: Wiley, 1983. — 388 с.
Beck A.; Teboulle M. Mirror descent and nonlinear projected subgradient methods for convex optimization // Operations Research Letters. — 2003. — Т. 31. — № 3. — С. 167—175.
Banerjee A.; Merugu S.; Dhillon I. S.; Ghosh J. Clustering with Bregman divergences // Journal of Machine Learning Research. — 2005. — Т. 6. — С. 1705—1749.
Amari S.-I. Information Geometry and Its Applications. — Tokyo: Springer, 2016. — 374 с.
Lu H.; Freund R. M.; Nesterov Y. Relatively smooth convex optimization by first-order methods, and applications // SIAM Journal on Optimization. — 2018. — Т. 28. — № 1. — С. 333—354.
Frigyik B. A.; Srivastava S.; Gupta M. R. Functional Bregman divergence and Bayesian estimation of distributions // IEEE Transactions on Information Theory. — 2008. — Т. 54. — № 11. — С. 5130—5139.
Jiao J.; Courtade T. A.; No A.; Venkat K.; Weissman T. Information measures: the curious case of the binary alphabet // IEEE Transactions on Information Theory. — 2014. — Т. 60. — № 12. — С. 7616—7626.
Dhillon I. S.; Tropp J. A. Matrix nearness problems with Bregman divergences // SIAM Journal on Matrix Analysis and Applications. — 2007. — Т. 29. — № 4. — С. 1120—1146.
Chowdhury S. R.; Saux P.; Maillard O.-A.; Gopalan A. Bregman deviations of generic exponential families // Proceedings of Thirty Sixth Conference on Learning Theory. — 2023. — Т. 195. — С. 394—449.
Guilmeau T.; Chouzenoux E.; Elvira V. Regularized Rényi divergence minimization through Bregman proximal gradient algorithms // Journal of Machine Learning Research. — 2025. — Т. 26. — С. 1—56.
Heskes T. Bias-variance decompositions: the exclusive privilege of Bregman divergences // Journal of Machine Learning Research. — 2025. — Т. 26. — С. 1—30.

Источник — «http://recognition.su/wiki/index.php?title=%D0%94%D0%B8%D0%B2%D0%B5%D1%80%D0%B3%D0%B5%D0%BD%D1%86%D0%B8%D1%8F_%D0%91%D1%80%D1%8D%D0%B3%D0%BC%D0%B0%D0%BD%D0%B0»

Категории: Математические функции | Машинное обучение | Энциклопедия анализа данных | Выпуклая оптимизация | Теория информации

@@ Строка 1: / Строка 1: @@
-{{well|Статья написана с использованием LLM ChatGPT (GPT-5.6 Sol Medium) и проверена участником [[Участник:Aleksei Kovalenko|Aleksei Kovalenko]] 18:00, 15 июля 2026 (MSD). Промпт приводится полностью в [[Обсуждение:Дивергенция Брэгмана]].}}
+{{well|Статья написана с использованием LLM ChatGPT (GPT-5.6 Sol Medium) и проверена участником [[Участник:Aleksei Kovalenko|Aleksei Kovalenko]] 18:00, 15 июля 2026 (MSD). Промпт приводится полностью в Обсуждение:Дивергенция Брэгмана.}}
 {{TOCright}}
 '''Дивергенция Брэгмана''' (также '''расхождение Брэгмана''', иногда '''расстояние Брэгмана''') — неотрицательная мера различия двух точек, порождённая выпуклой функцией как ошибка её линеаризации первого порядка. В отличие от [[Метрика|метрики]], она, вообще говоря, не симметрична и не удовлетворяет неравенству треугольника. Её основное назначение — согласовать понятие близости с геометрией задачи: симплекс вероятностей естественно снабжается энтропийной геометрией, положительный ортант — логарифмической, а евклидово пространство — квадратичной.
-Понятие введено Л. М. Брэгманом в 1967 году при исследовании последовательных проекций на выпуклые множества.<ref>{{статья |автор = Bregman L. M. |заглавие = The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming |ссылка = https://doi.org/10.1016/0041-5553(67)90040-7 |издание = USSR Computational Mathematics and Mathematical Physics |год = 1967 |том = 7 |номер = 3 |страницы = 200—217 }}</ref> В современной теории дивергенции Брэгмана связывают [[Выпуклый анализ]], [[Сопряжённая функция|сопряжённость Фенхеля — Лежандра]], [[Информационная геометрия|информационную геометрию]], [[Метод зеркального спуска (оптимизация)|Зеркальный спуск]], [[Экспоненциальное семейство|экспоненциальные семейства]] и методы обучения статистических моделей.
+Понятие введено Л. М. Брэгманом в 1967 году при исследовании последовательных проекций на выпуклые множества.<ref>{{статья |автор = Bregman L. M. |заглавие = The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming |ссылка = https://doi.org/10.1016/0041-5553(67)90040-7 |издание = USSR Computational Mathematics and Mathematical Physics |год = 1967 |том = 7 |номер = 3 |страницы = 200—217 }}</ref> В современной теории дивергенции Брэгмана связывают [[Выпуклый анализ]], [[Сопряжённая функция|сопряжённость Фенхеля — Лежандра]], [[Информационная геометрия|информационную геометрию]], [[Зеркальный спуск]], [[Экспоненциальное семейство|экспоненциальные семейства]] и методы обучения статистических моделей.
 == Определение и геометрический смысл ==
@@ Строка 171: / Строка 171: @@
 Пусть <tex>Q</tex> — симметричная положительно определённая матрица и
-:: <tex>\phi(x)=\frac12x^\mathsf TQx.</tex>
+:: <tex>\phi(x)=\frac12x^{\mathsf{T}}Qx.</tex>
 Тогда
-:: <tex>D_\phi(x,y)=\frac12(x-y)^\mathsf TQ(x-y).</tex>
+:: <tex>D_\phi(x,y)=\frac12(x-y)^{\mathsf{T}}Q(x-y).</tex>
 Положительная полуопределённость <tex>Q</tex> обеспечивает неотрицательность, но не строгую определённость: различные точки могут иметь нулевое расхождение вдоль ядра. Если открытая выпуклая область связна, а строго выпуклый генератор принадлежит классу <tex>C^2</tex>, симметричность <tex>D_\phi</tex> на всей области влечёт постоянство <tex>\nabla^2\phi</tex>. Поэтому генератор квадратичен с точностью до аффинного слагаемого, а дивергенция является квадратом обобщённого евклидова расстояния.<ref>{{статья |автор = Boissonnat J.-D.; Nielsen F.; Nock R. |заглавие = Bregman Voronoi diagrams: properties, algorithms and applications |ссылка = https://doi.org/10.1007/s00454-010-9256-1 |издание = Discrete & Computational Geometry |год = 2010 |том = 44 |номер = 2 |страницы = 281—307 }}</ref>