Меню Главная Случайная статья Настройки Дивергенция Брэгмана Материал из https://ru.wikipedia.org Дивергенция Брэгмана (расстояние Брэгмана) — мера расстояния между двумя точками, определённая в терминах строго выпуклой функции. Они образуют важный класс дивергенций. Если точки интерпретировать как распределение вероятностей, либо как значения параметрической модели[англ.], либо как набор наблюдаемых значений, то полученное расстояние является статистическим расстоянием[англ.]. Самой элементарной дивергенцией Брэгмана является квадрат евклидова расстояния. Дивергенции Брэгмана подобны метрикам, но не удовлетворяют ни неравенству треугольника, ни симметрии (в общем случае), однако они удовлетворяют обобщённой теореме Пифагора. В информационной геометрии[англ.] соответствующее статистическое многообразие[англ.] интерпретируется как плоское многообразие[англ.] (или двойственное). Это позволяет обобщить многие техники оптимизации к дивергенции Брэгмана, что геометрически соответствует обобщению метода наименьших квадратов. Дивергенция Брэгмана названа по имени Льва Мееровича Брэгмана, предложившего концепцию в 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]. Содержание 1 Свойства 2 Примеры 3 Обобщение проективной двойственности 4 Обобщения дивергенции Брэгмана 5 Дивергенция Брэгмана на других объектах 6 Примечания 7 Литература Свойства Дивергенция Брэгмана неотрицательна (${\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]. Примечания Amid, Warmuth, Anil, Koren, 2019, с. 14987—14996. Bauschke, Borwein, 2001. Banerjee, Merugu, Dhillon, Ghosh, 2005. 1 2 Frigyik, Srivastava, Gupta, 2008. Boissonnat, Nielsen, Nock, 2010. Nielsen, Boltz, 2011. Nielsen, Nock, 2017. Nielsen, Frank; Nock, Richard (2018). The Bregman chord divergence. arXiv:1810.09113 [cs.LG]. Ознакомиться с термином Stein’s loss можно в статье https://www.jstor.org/stable/2241373?seq=1 Архивная копия от 17 ноября 2020 на Wayback Machine Iyer, Bilmes, 2012. Nock, Magdalou, Briys, Nielsen, 2012, с. 373—402. Литература 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 года. Peter Harremos. Divergence and Sufficiency for Convex Optimization // Entropy. — 2017. — Т. 19, вып. 5. — С. 206. — doi:10.3390/e19050206. — . — arXiv:1701.01010. Frank Nielsen, Richard Nock. On the Centroids of Symmetrized Bregman Divergences. — 2007. 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, 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. — . — arXiv:1702.04877.