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

Дивергенция Брэгмана (расстояние Брэгмана) — мера расстояния между двумя точками, определённая в терминах строго выпуклой функции. Они образуют важный класс дивергенций. Если точки интерпретировать как распределение вероятностей, либо как значения параметрической модели^[англ.], либо как набор наблюдаемых значений, то полученное расстояние является статистическим расстоянием^[англ.]. Самой элементарной дивергенцией Брэгмана является квадрат евклидова расстояния.

Дивергенции Брэгмана подобны метрикам, но не удовлетворяют ни неравенству треугольника, ни симметрии (в общем случае), однако они удовлетворяют обобщённой теореме Пифагора. В информационной геометрии^[англ.] соответствующее статистическое многообразие^[англ.] интерпретируется как плоское многообразие^[англ.] (или двойственное). Это позволяет обобщить многие техники оптимизации к дивергенции Брэгмана, что геометрически соответствует обобщению метода наименьших квадратов.

Дивергенция Брэгмана названа по имени Льва Мееровича Брэгмана, предложившего концепцию в 1967 году.

Формально, для непрерывно дифференцируемой строго выпуклой функции ${\displaystyle F\colon \Omega \to \mathbb {R} }$, определённой на замкнутом выпуклом множестве ${\displaystyle \Omega }$, расстояние Брэгмана определяется как разность между значением функции ${\displaystyle F}$ в точке ${\displaystyle p}$ и значением разложения Тейлора первого порядка функции ${\displaystyle F}$ в точке ${\displaystyle q}$, вычисленное в точке ${\displaystyle p}$:

${\displaystyle D_{F}(p,q)=F(p)-F(q)-\langle \nabla F(q),p-q\rangle }$.

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

Дивергенция Брэгмана неотрицательна (${\displaystyle D_{F}(p,q)\geqslant 0}$ для всех ${\displaystyle p}$ и ${\displaystyle q}$ — следствие выпуклости ${\displaystyle F}$), выпукла по первому аргументу^[2], линейна относительно неотрицательных коэффициентов (${\displaystyle D_{F_{1}+\lambda F_{2}}(p,q)=D_{F_{1}}(p,q)+\lambda D_{F_{2}}(p,q)}$ для ${\displaystyle \lambda \geqslant 0}$).

Дивергенция Брэгмана для выпуклого сопряжения ${\displaystyle F^{*}}$ заданной функции ${\displaystyle F}$ связана с ${\displaystyle D_{F}(p,q)}$:

${\displaystyle D_{F^{*}}(p^{*},q^{*})=D_{F}(q,p)}$,

где ${\displaystyle p^{*}=\nabla F(p)}$ и ${\displaystyle q^{*}=\nabla F(q)}$ — двойственные точки, соответствующие ${\displaystyle p}$ и ${\displaystyle q}$.

Ключевым результатом о дивергенции Брэгмана является то, что если дан случайный вектор, среднее векторов минимизирует ожидаемую дивергенцию Брэгмана от случайного вектора. Этот результат обобщает классический результат о том, что среднее по множеству минимизирует полную квадратичную ошибку элементов множества. Для случая векторов установелен в 2005 году^[3], на функции распределений результат распространён в 2008 году^[4].

Квадрат евклидова расстояния ${\displaystyle D_{F}(x,y)=\|x-y\|^{2}}$ является каноническим примером расстояния Брэгмана, образованного выпуклой функцией ${\displaystyle F(x)=\|x\|^{2}}$

Квадрат расстояния Махаланобиса ${\displaystyle D_{F}(x,y)={\tfrac {1}{2}}(x-y)^{T}Q(x-y)}$, которое образуется от выпуклой функцией ${\displaystyle F(x)={\tfrac {1}{2}}x^{T}Qx}$. Это можно рассматривать как обобщение квадрата евклидова расстояния.

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

${\displaystyle D_{F}(p,q)=\sum _{i}p(i)\log {\frac {p(i)}{q(i)}}-\sum p(i)+\sum q(i)}$

образуется функцией отрицательной энтропии:

${\displaystyle F(p)=\sum _{i}p(i)\log p(i)}$.

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

${\displaystyle D_{F}(p,q)=\sum _{i}\left({\frac {p(i)}{q(i)}}-\log {\frac {p(i)}{q(i)}}-1\right)}$

обобщается выпуклой функцией:

${\displaystyle F(p)=-\sum _{i}\log p(i)}$.

Ключевым средством в вычислительной геометрии является идея проективной двойственности, которая отображает точки в гиперплоскости и наоборот, сохраняя тем не менее отношения инцидентности и «выше — ниже». Есть много видов проективной двойственности — обычный вид отображает точку ${\displaystyle p=(p_{1},\ldots p_{d})}$ в гиперплоскость ${\displaystyle x_{d+1}=\sum _{1}^{d}2p_{i}x_{i}}$. Это отображение можно понимать (если отождествлять гиперплоскость с нормалью) как выпуклое сопряжённое отображение, которое переводит точку p в двойственную точку ${\displaystyle p^{*}=\nabla F(p)}$, где ${\displaystyle F}$ определяет ${\displaystyle d}$-мерный параболоид ${\displaystyle x_{d+1}=\sum x_{i}^{2}}$.

Если заменить параболоид на любую выпуклую функцию, то получится другое двойственное отображение, которое сохраняет инцидентность и свойства «выше — ниже» стандартной проективной двойственности. Из этого вытекает, что естественные двойственные концепции вычислительной геометрии наподобие диаграммы Вороного и триангуляций Делоне сохраняют своё значение в пространствах с расстоянием, определённым произвольной дивергенцией Брэгмана. Алгоритмы «нормальной» геометрии распространяются естественным образом на эти пространства^[5].

Дивергенции Брэгмана можно интерпретировать как предельные случаи косых дивергенций Йенсена^[6]). Дивергенции Йенсена можно обобщить с помощью сравнительной выпуклости, а обобщение предельных случаев этих косых дивергенций Йенсена приводит к обобщённым дивергенциям Брэгмана (см. статью Нильсена и Нока^[7]). Хордовая дивергенция Брэгмана^[8] получается, если взять хорду вместо касательной.

Дивергенцию Брэгмана можно определить для матриц, функций и мер (распределений). Дивергенция Брэгмана для матриц включает функцию потерь Штайна^[9] и энтропию Неймана^[англ.]. Дивергенции Брэгмана для функций включают полную квадратичную ошибку, относительную энтропию и квадрат смещения^[4]. Аналогично дивергенция Брэгмана определяется также для множеств посредством cубмодулярной функции множеств^[англ.], известная как дискретный аналог выпуклой функции. Субмодулярная дивергенция Брэгмана включает ряд дискретных мер, таких как расстояние Хэмминга, точность и полнота^[англ.], взаимная информация и некоторые другие меры расстояния на множествах^[10][11].

• H. Bauschke, J. Borwein. Joint and separate convexity of the Bregman Distance // Inherently Parallel Algorithms in Feasibility and Optimization and their Applications / D. Butnariu, Y. Censor, S. Reich (editors). — Elsevier, 2001.
• R. Nock, B. Magdalou, E. Briys, F. Nielsen. Mining Matrix Data with Bregman MatrixDivergences for Portfolio Selection // Matrix Information Geometry. — 2012.
• Ehsan Amid, Manfred K. Warmuth, Rohan Anil, Tomer Koren. Robust Bi-Tempered Logistic Loss Based on Bregman Divergences // Conference on Neural Information Processing Systems. — 2019.
• Arindam Banerjee, Srujana Merugu, Inderjit S. Dhillon, Joydeep Ghosh. Clustering with Bregman divergences // Journal of Machine Learning Research. — 2005. — Т. 6. — С. 1705–1749.
• Брэгман Л. М. Релаксационный метод нахождения общей точки выпуклых множеств и его применение для решения задач выпуклого программирования // Ж. вычисл. матем.и матем. физ.. — 1967. — Т. 7, № 3.
• Bela A. Frigyik, Santosh Srivastava, Maya R.Gupta. Functional Bregman Divergences and Bayesian Estimation of Distributions // IEEE Transactions on Information Theory. — 2008. — Т. 54, вып. 11. — С. 5130–5139. — doi:10.1109/TIT.2008.929943. — arXiv:cs/0611123. Архивировано 12 августа 2010 года.
• Rishabh Iyer, Jeff Bilmes. Submodular-Bregman divergences and Lovász-Bregman divergences with Applications // . — 2012.
• Bela A. Frigyik, Santosh Srivastava, Maya R. Gupta. An Introduction to Functional Derivatives. — University of Washington, Dept. of Electrical Engineering, 2008. — (UWEE Tech Report 2008-0001). Архивировано 17 февраля 2017 года.
• Peter Harremoës. Divergence and Sufficiency for Convex Optimization // Entropy. — 2017. — Т. 19, вып. 5. — С. 206. — doi:10.3390/e19050206. — Bibcode: 2017Entrp..19..206H. — arXiv:1701.01010.
• Frank Nielsen, Richard Nock. The dual Voronoi diagrams with respect to representational Bregman divergences // Proc. 6th International Symposium on Voronoi Diagrams. — IEEE, 2009. — doi:10.1109/ISVD.2009.15.
• Frank Nielsen, Richard Nock. On the Centroids of Symmetrized Bregman Divergences. — 2007.
• Frank Nielsen, Jean-Daniel Boissonnat, Richard Nock. On Visualizing Bregman Voronoi diagrams // Proc. 23rd ACM Symposium on Computational Geometry (video track). — 2007. — doi:10.1145/1247069.1247089.
• Jean-Daniel Boissonnat, Frank Nielsen, Richard Nock. Bregman Voronoi Diagrams // Discrete and Computational Geometry. — 2010. — Т. 44, вып. 2. — С. 281–307. — doi:10.1007/s00454-010-9256-1.
• Frank Nielsen, Richard Nock. On approximating the smallest enclosing Bregman Balls // Proc. 22nd ACM Symposium on Computational Geometry. — 2006. — С. 485–486. — doi:10.1145/1137856.1137931.
• Frank Nielsen, Sylvain Boltz. The Burbea-Rao and Bhattacharyya centroids // IEEE Transactions on Information Theory. — 2011. — Т. 57, вып. 8. — С. 5455–5466. — doi:10.1109/TIT.2011.2159046. — arXiv:1004.5049.
• Frank Nielsen, Richard Nock. Generalizing Skew Jensen Divergences and Bregman Divergences With Comparative Convexity // IEEE Signal Processing Letters. — 2017. — Т. 24, вып. 8. — С. 1123–1127. — doi:10.1109/LSP.2017.2712195. — Bibcode: 2017ISPL...24.1123N. — arXiv:1702.04877.