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

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

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

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