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

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

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

Дивергенция Брэгмана названа по имени Льва Мееровича Брэгмана, предложившего концепцию в 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].

Примечания

1. Amid, Warmuth, Anil, Koren, 2019, с. 14987—14996.
2. Bauschke, Borwein, 2001.
3. Banerjee, Merugu, Dhillon, Ghosh, 2005.
4. Frigyik, Srivastava, Gupta, 2008.
5. Boissonnat, Nielsen, Nock, 2010.
6. Nielsen, Boltz, 2011.
7. Nielsen, Nock, 2017.
8. Nielsen, Frank; Nock, Richard (2018). "The Bregman chord divergence". arXiv:1810.09113 [cs.LG].
9. Ознакомиться с термином Stein’s loss можно в статье https://www.jstor.org/stable/2241373?seq=1 Архивная копия от 17 ноября 2020 на Wayback Machine
10. Iyer, Bilmes, 2012.
11. Nock, Magdalou, Briys, Nielsen, 2012, с. 373—402.

Литература

• 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.