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

Пусть ${\displaystyle F:\Omega \to \mathbb {R} }$ будет непрерывно дифференцируемой строго выпуклой функцией, определённой на замкнутом выпуклом множестве ${\displaystyle \Omega }$.

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

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

• Неотрицательность: ${\displaystyle D_{F}(p,q)\geqslant 0}$ для всех p, q. Это следствие выпуклости F.
• Выпуклость: Функция ${\displaystyle D_{F}(p,q)}$ выпукла по первому аргументу, но не обязательно выпукла по второму (см. статью Баушке и Борвейна[1])
• Линейность: Если мы рассматриваем расстояние Брэгмана как оператор от функции F, то он линеен относительно неотрицательных коэффициентов. Другими словами, для строго выпуклых и дифференцируемых ${\displaystyle F_{1},F_{2}}$ и ${\displaystyle \lambda \geqslant 0}$,

${\displaystyle D_{F_{1}+\lambda F_{2}}(p,q)=D_{F_{1}}(p,q)+\lambda D_{F_{2}}(p,q)}$

• Двойственность: Функция F имеет выпуклое сопряжение ${\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)}$ являются двойственными точками, соответствующими p и q.

• Среднее как минимум: Ключевым результатом о дивергенции Брэгмана является то, что если дан случайный вектор, среднее векторов минимизирует ожидаемую дивергенцию Брэгмана от случайного вектора. Этот результат обобщает результат из учебников, что среднее по множеству минимизирует полную квадратичную ошибку элементов множества. Этот результат доказал для случая векторов Банерджи с соавторами[2] и распространили на случай функций/распределений Фриджик с соавторами[3].

• Квадрат евклидова расстояния ${\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)}$, где F определяет d-мерный параболоид ${\displaystyle x_{d+1}=\sum x_{i}^{2}}$.

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

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

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

Список обычных матричных дивергенций Брэгмана можно найти в таблице 15.1 в статье Нока, Магдалоу, Браиса, Нильсена[11].

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