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

В математике , особенно в статистике и информационной геометрии , расхождение Брегмана или расстояние Брегмана — это мера разницы между двумя точками, определяемая в терминах строго выпуклой функции ; они образуют важный класс расхождений . Когда точки интерпретируются как распределения вероятностей – в частности, либо как значения параметра параметрической модели , либо как набор данных наблюдаемых значений – результирующее расстояние является статистическим расстоянием . Самое основное расхождение Брегмана — это квадрат евклидова расстояния .

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

Дивергенции Брегмана названы в честь русского математика Льва М. Брегмана , который ввел эту концепцию в 1967 году.

Определение

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

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

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

Характеристики

• Неотрицательность : $D_{F}(p,q)\geq 0$ для всех $p$, $q$. Это следствие выпуклости $F$.
• Позитивность : Когда $F$ строго выпуклая, $D_{F}(p,q)=0$ если только $p=q$.
• Уникальность с точностью до аффинной разницы : $D_{F}=D_{G}$ если только $F-G$ является аффинной функцией.
• Выпуклость : $D_{F}(p,q)$ выпукло по первому аргументу, но не обязательно по второму. Если F строго выпукло, то $D_{F}(p,q)$ строго выпукла по первому аргументу.
  • Например, возьмем f(x) = |x|, сгладим ее до 0, затем возьмем $y=1,x_{1}=0.1,x_{2}=-0.9,x_{3}=0.9x_{1}+0.1x_{2}$, затем $D_{f}(y,x_{3})\approx 1>0.9D_{f}(y,x_{1})+0.1D_{f}(y,x_{2})\approx 0.2$.
• Линейность : Если мы думаем о расстоянии Брегмана как об операторе функции F , то оно линейно относительно неотрицательных коэффициентов. Другими словами, для $F_{1},F_{2}$ строго выпуклая и дифференцируемая, и $\lambda \geq 0$,

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

• Двойственность : если F строго выпукла, то функция F имеет выпуклую сопряженную функцию. $F^{*}$ которое также строго выпукло и непрерывно дифференцируемо на некотором выпуклом множестве $\Omega ^{*}$. Расстояние Брегмана, определенное относительно $F^{*}$ двойственен к $D_{F}(p,q)$ как

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

Здесь, $p^{*}=\nabla F(p)$ и $q^{*}=\nabla F(q)$ являются двойственными точками, соответствующими p и q.

Более того, используя те же обозначения:

$D_{F}(p,q)=F(p)+F^{*}(q^{*})-\langle p,q^{*}\rangle$

• Среднее как минимизатор : Ключевой результат о расхождениях Брегмана заключается в том, что для случайного вектора средний вектор минимизирует ожидаемое расхождение Брегмана от случайного вектора. Этот результат обобщает результат учебника о том, что среднее значение набора минимизирует общий квадрат ошибки элементов в наборе. Этот результат был доказан для векторного случая (Банерджи и др., 2005) и распространен на случай функций/распределений (Фригьик и др., 2008). Этот результат важен, поскольку он дополнительно оправдывает использование среднего значения в качестве представителя случайного набора, особенно в байесовской оценке.
• Шары Брегмана ограничены и компактны, если X замкнуто : Определите шар Брегмана с центром в точке x и радиусом r по формуле $B_{f}(x,r):=\left\{y\in X:D_{f}(y,x)\leq r\right\}$. Когда $X\subset \mathbb {R} ^{n}$ конечномерен, $\forall x\in X$, если $x$ находится в относительной внутренней части $X$, или если $X$ локально закрыто в $x$ (т. е. существует замкнутый шар $B(x,r)$ сосредоточено в $x$, такой, что $B(x,r)\cap X$ закрыто), то $B_{f}(x,r)$ ограничен для всех $r$ . Если $X$ закрыто, то $B_{f}(x,r)$ компактен для всех $r$.
• Закон косинусов :

Для любого $p,q,z$

$D_{F}(p,q)=D_{F}(p,z)+D_{F}(z,q)-(p-z)^{T}(\nabla F(q)-\nabla F(z))$

• Закон параллелограмма : для любого $\theta ,\theta _{1},\theta _{2}$,

$B_{F}\left(\theta _{1}:\theta \right)+B_{F}\left(\theta _{2}:\theta \right)=B_{F}\left(\theta _{1}:{\frac {\theta _{1}+\theta _{2}}{2}}\right)+B_{F}\left(\theta _{2}:{\frac {\theta _{1}+\theta _{2}}{2}}\right)+2B_{F}\left({\frac {\theta _{1}+\theta _{2}}{2}}:\theta \right)$

Обобщенная теорема Пифагора для дивергенции Брегмана.

• Проекция Брегмана : для любого $W\subset \Omega$, определим «проекцию Брегмана» $q$ на $W$:

$P_{W}(q)={\text{argmin}}_{\omega \in W}D_{F}(\omega ,q)$. Затем

• • если $W$ выпукла, то проекция единственна, если она существует;
  • если $W$ непусто, замкнуто, выпукло и $\Omega \subset \mathbb {R} ^{n}$ конечномерна, то проекция существует и единственна.
• Обобщенная теорема Пифагора :

Для любого $v\in \Omega ,a\in W$,

$D_{F}(a,v)\geq D_{F}(a,P_{W}(v))+D_{F}(P_{W}(v),v).$

Это равенство, если $P_{W}(v)$ находится в относительной внутренней части $W$.

В частности, это всегда происходит, когда $W$ является аффинным множеством.

• Отсутствие неравенства треугольника: поскольку расхождение Брегмана по сути является обобщением квадрата евклидова расстояния, неравенство треугольника отсутствует. Действительно, $D_{F}(z,x)-D_{F}(z,y)-D_{F}(y,x)=\langle \nabla f(y)-\nabla f(x),z-y\rangle$, который может быть положительным или отрицательным.

Доказательства

• Неотрицательность и положительность: используйте неравенство Йенсена .
• Уникальность с точностью до аффинной разницы: исправьте некоторые ошибки $x\in \Omega$, то для любого другого $y\in \Omega$, мы имеем по определению $F(y)-G(y)=F(x)-G(x)+\langle \nabla F(x)-\nabla G(x),y-x\rangle$.
• Выпуклость в первом аргументе: по определению, и используйте выпуклость F. То же самое для строгой выпуклости.
• Линейность по F, закон косинусов, закон параллелограмма: по определению.
• Двойственность: См. рисунок 1.
• Шары Брегмана ограничены и компактны, если X замкнуто:

Исправить $x\in X$ . Включите аффинное преобразование $f$ , так что $\nabla f(x)=0$.

Возьми немного $\epsilon >0$, такой, что $\partial B(x,\epsilon )\subset X$. Затем рассмотрим «радиально-направленную» производную $f$ на евклидовой сфере $\partial B(x,\epsilon )$.

$\langle \nabla f(y),(y-x)\rangle$ для всех $y\in \partial B(x,\epsilon )$.

С $\partial B(x,\epsilon )\subset \mathbb {R} ^{n}$ компактен, достигает минимальной стоимости $\delta$ в какой-то момент $y_{0}\in \partial B(x,\epsilon )$.

С $f$ строго выпуклая, $\delta >0$. Затем $B_{f}(x,r)\subset B(x,r/\delta )\cap X$.

С $D_{f}(y,x)$ является $C^{1}$ в $y$, $D_{f}$ является непрерывным в $y$, таким образом $B_{f}(x,r)$ закрыто, если $X$ является.

• Проекция $P_{W}$ четко определен, когда $W$ является замкнутым и выпуклым.

Исправить $v\in X$. Возьми немного $w\in W$ , тогда пусть $r:=D_{f}(w,v)$. Затем нарисуйте мяч Брегмана. $B_{f}(v,r)\cap W$. Он замкнут и ограничен, поэтому компактен. С $D_{f}(\cdot ,v)$ непрерывна и строго выпукла на ней и ограничена снизу $0$, он достигает на нем уникального минимума.

• Пифагорово неравенство.

По закону косинуса, $D_{f}(w,v)-D_{f}(w,P_{W}(v))-D_{f}(P_{W}(v),v)=\langle \nabla _{y}D_{f}(y,v)|_{y=P_{W}(v)},w-P_{W}(v)\rangle$, что должно быть $\geq 0$, с $P_{W}(v)$ сводит к минимуму $D_{f}(\cdot ,v)$ в $W$, и $W$ является выпуклым.

• Пифагорово равенство, когда $P_{W}(v)$ находится в относительной внутренней части $X$.

Если $\langle \nabla _{y}D_{f}(y,v)|_{y=P_{W}(v)},w-P_{W}(v)\rangle >0$, то поскольку $w$ находится в относительном интерьере, мы можем перейти от $P_{W}(v)$ в направлении, противоположном $w$, чтобы уменьшить $D_{f}(y,v)$ , противоречие.

Таким образом $\langle \nabla _{y}D_{f}(y,v)|_{y=P_{W}(v)},w-P_{W}(v)\rangle =0$.

Классификационные теоремы

• Единственные симметричные расходимости Брегмана на $X\subset \mathbb {R} ^{n}$ представляют собой квадраты обобщенных евклидовых расстояний ( расстояние Махаланобиса ), то есть, $D_{f}(y,x)=(y-x)^{T}A(y-x)$ для некоторой положительной определенности $A$.

Доказательство

Дивергенция Брегмана интерпретируется как области.

Для любого $x\neq y\in X$ , определять $r=\|y-x\|,v=(y-x)/r,g(t)=f(x+tv)$ для $t\in [0,r]$ . Позволять $z(t)=x+tv$.

Затем $g'(t)=\langle \nabla f(z(t)),v\rangle$ для $t\in (0,r)$ , и поскольку $\nabla f$ является непрерывным, также для $t=0,r$ .

Тогда из диаграммы мы видим, что для $D_{f}(x;z(t))=D_{f}(z(t);x)$ для всех $t\in [0,r]$ , мы должны иметь $g'(t)$ линейный по $t\in [0,r]$.

Таким образом, мы находим, что $\nabla f$ изменяется линейно в любом направлении. По следующей лемме $f$ является квадратичным. С $f$ также строго выпукла, она имеет вид $f(x)+x^{T}Ax+B^{T}x+C$ , где $A\succ 0$.

Лемма : Если $S$ является открытым подмножеством $\mathbb {R} ^{n}$ , $f:S\to \mathbb {R}$ имеет непрерывную производную и, учитывая любой отрезок $[x,x+v]\subset S$ , функция $h(t):=\langle \nabla f(x+tv),v\rangle$ линейна по $t$ , затем $f$ является квадратичной функцией.

Идея доказательства: для любой квадратичной функции $q:S\to \mathbb {R}$ , у нас есть $f-q$ все еще имеет такую ​​​​линейность производной, поэтому мы вычтем несколько квадратичных функций и покажем, что $f$ становится нулевым.

Идея доказательства может быть полностью проиллюстрирована для случая $S=\mathbb {R} ^{2}$ , поэтому мы доказываем это в данном случае.

По производной-линейности, $f$ является квадратичной функцией на любом отрезке прямой в $\mathbb {R} ^{2}$. Вычтем четыре квадратичные функции такие, что $g:=f-q_{0}-q_{1}-q_{2}-q_{3}$ становится тождественно нулевым на оси x, оси y и $\{x=y\}$ линия.

Позволять $q_{0}(x,y)=f(0,0)+\nabla f(0,0)\cdot (x,y),q_{1}(x,y)=A_{1}x^{2},q_{2}(x,y)=A_{2}y^{2},q_{3}(x,y)=A_{3}xy$, за удачно выбранный $A_{1},A_{2},A_{3}$. Теперь используйте $q_{0}$ чтобы удалить линейный член, и использовать $q_{1},q_{2},q_{3}$ соответственно, чтобы удалить квадратичные члены вдоль трех линий.

$\forall (x,y)\in \mathbb {R} ^{2}$ не в начале координат, существует линия $l$ через $(x,y)$ который пересекает оси X, Y и $\{x=y\}$ линия в трех разных точках. С $g$ квадратичен по $l$ , и равен нулю в трех разных точках, $g$ тождественно равен нулю $l$ , таким образом $g(x,y)=0$. Таким образом $f=q_{0}+q_{1}+q_{2}+q_{3}$ является квадратичным.

Следующие две характеристики предназначены для расхождений на $\Gamma _{n}$, множество всех вероятностных мер на $\{1,2,...,n\}$, с $n\geq 2$.

Определите расхождение на $\Gamma _{n}$ как любая функция типа $D:\Gamma _{n}\times \Gamma _{n}\to [0,\infty ]$, такой, что $D(x,x)=0$ для всех $x\in \Gamma _{n}$, затем:

• Единственное расхождение по $\Gamma _{n}$ это одновременно и дивергенция Брегмана, и f-дивергенция - это дивергенция Кульбака – Лейблера .
• Если $n\geq 3$, то любое расхождение Брегмана на $\Gamma _{n}$ которое удовлетворяет неравенству обработки данных , должно быть расхождением Кульбака – Лейблера. (На самом деле достаточно более слабого предположения о «достаточности».) Контрпримеры существуют, когда $n=2$.

Учитывая расхождение Брегмана $D_{F}$, его «противоположность», определяемая $D_{F}^{*}(v,w)=D_{F}(w,v)$, как правило, не является расхождением Брегмана. Например, дивергенция Кульбака-Лейбера является одновременно дивергенцией Брегмана и f-дивергенцией. Ее обратная дивергенция также является f-дивергенцией, но согласно приведенной выше характеристике обратная КЛ-дивергенция не может быть дивергенцией Брегмана.

Примеры

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

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

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

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

При ограничении симплексом последние два члена сокращаются, давая обычное расхождение Кульбака – Лейблера для распределений.

• Расстояние Итакура –Сайто ,

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

генерируется выпуклой функцией

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

Обобщающая проективная двойственность

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

Если теперь мы заменим параболоид произвольной выпуклой функцией, мы получим другое двойственное отображение, которое сохраняет свойства инцидентности и «сверху-внизу» стандартного проективно-двойственного отображения. Это означает, что естественные двойственные понятия в вычислительной геометрии, такие как диаграммы Вороного и триангуляции Делоне, сохраняют свое значение в пространствах расстояний, определяемых произвольной расходимостью Брегмана. Таким образом, алгоритмы «нормальной» геометрии распространяются непосредственно на эти пространства (Буассоннат, Нильсен и Нок, 2010).

Обобщение расходимостей Брегмана.

Дивергенции Брегмана можно интерпретировать как предельные случаи искаженных дивергенций Йенсена (см. Nielsen and Boltz, 2011). Дивергенции Йенсена можно обобщить с помощью сравнительной выпуклости, а предельные случаи этих искаженных обобщений Йенсена дают обобщенную дивергенцию Брегмана (см. Nielsen and Nock, 2017).Расхождение хорд Брегмана получается, если вместо касательной взять хорду.

Расхождение Брегмана на других объектах

Расхождения Брегмана также можно определить между матрицами, между функциями и между мерами (распределениями). Расхождения Брегмана между матрицами включают потери Штейна и энтропию фон Неймана . Расхождения Брегмана между функциями включают общую квадратическую ошибку, относительную энтропию и квадратичное смещение; см. ссылки Frigyik et al. ниже приведены определения и свойства. Аналогичным образом дивергенции Брегмана также были определены над множествами через субмодулярную функцию множества , которая известна как дискретный аналог выпуклой функции . Субмодулярные дивергенции Брегмана включают в себя ряд дискретных мер расстояния, таких как расстояние Хэмминга , точность и отзыв , взаимная информация и некоторые другие меры расстояния, основанные на наборах (более подробную информацию и свойства субмодулярного Брегмана см. в Iyer & Bilmes, 2012).

Список общих матричных расходимостей Брегмана см. в таблице 15.1.

Приложения

В машинном обучении дивергенции Брегмана используются для расчета логистических потерь с двумя темпами, которые работают лучше, чем функция softmax с зашумленными наборами данных.

Дивергенция Брегмана используется в формулировке зеркального спуска , которая включает в себя алгоритмы оптимизации, используемые в машинном обучении, такие как градиентный спуск и алгоритм хеджирования .

Ссылки

• Банерджи, Ариндам; Меругу, Сруджана; Диллон, Индерджит С.; Гош, Джойдип (2005). «Кластеризация с расхождениями Брегмана» . Журнал исследований машинного обучения . 6 : 1705–1749.
• Брегман, LM (1967). «Релаксационный метод поиска общих точек выпуклых множеств и его применение к решению задач выпуклого программирования». Вычислительная математика и математическая физика СССР . 7 (3): 200–217. дои : 10.1016/0041-5553(67)90040-7 .
• Фригиик, Бела А.; Шривастава, Сантош; Гупта, Майя Р. (2008). «Функциональные расхождения Брегмана и байесовская оценка распределений» (PDF) . Транзакции IEEE по теории информации . 54 (11): 5130–5139. arXiv : cs/0611123 . дои : 10.1109/TIT.2008.929943 . S2CID   1254 . Архивировано из оригинала (PDF) 12 августа 2010 года.
• Айер, Ришаб; Билмс, Джефф (2012). «Субмодулярные расходимости-Брегмана и расходимости Ловаса-Брегмана с приложениями». Конференция по нейронным системам обработки информации .
• Фригиик, Бела А.; Шривастава, Сантош; Гупта, Майя Р. (2008). Введение в функциональные производные (PDF) . Технический отчет UWEE 2008-0001. Вашингтонский университет, факультет электротехники. Архивировано из оригинала (PDF) 17 февраля 2017 года . Проверено 20 марта 2014 г.
• Харремоэс, Питер (2017). «Расхождение и достаточность для выпуклой оптимизации» . Энтропия . 19 (5): 206. arXiv : 1701.01010 . Бибкод : 2017Entrp..19..206H . дои : 10.3390/e19050206 .
• Нильсен, Франк; Нок, Ричард (2009). «Двойственные диаграммы Вороного относительно репрезентативных расходимостей Брегмана» (PDF) . Учеб. 6-й Международный симпозиум по диаграммам Вороного . IEEE. дои : 10.1109/ИСВД.2009.15 .
• Нильсен, Франк; Нок, Ричард (2007). «О центроидах симметризованных расходимостей Брегмана». arXiv : 0711.3242 [ cs.CG ].
• Нильсен, Франк; Буассонна, Жан-Даниэль; Нок, Ричард (2007). «Визуализация диаграмм Брегмана-Вороного» (PDF) . Учеб. 23-й симпозиум ACM по вычислительной геометрии (видеотрек) . дои : 10.1145/1247069.1247089 .
• Буассонна, Жан-Даниэль ; Нильсен, Франк; Нок, Ричард (2010). «Диаграммы Брегмана-Вороного» . Дискретная и вычислительная геометрия . 44 (2): 281–307. arXiv : 0709.2196 . дои : 10.1007/s00454-010-9256-1 . S2CID   1327029 .
• Нильсен, Франк; Нок, Ричард (2006). «Об аппроксимации наименьших объемлющих шаров Брегмана». Учеб. 22-й симпозиум ACM по вычислительной геометрии . стр. 485–486. дои : 10.1145/1137856.1137931 .
• Нильсен, Франк; Больц, Сильвен (2011). «Центроиды Бурбеа-Рао и Бхаттачарья». Транзакции IEEE по теории информации . 57 (8): 5455–5466. arXiv : 1004.5049 . дои : 10.1109/TIT.2011.2159046 . S2CID   14238708 .
• Нильсен, Франк; Нок, Ричард (2017). «Обобщение косых расхождений Дженсена и расхождений Брегмана со сравнительной выпуклостью». Письма об обработке сигналов IEEE . 24 (8): 1123–1127. arXiv : 1702.04877 . Бибкод : 2017ISPL...24.1123N . дои : 10.1109/ЛСП.2017.2712195 . S2CID   31899023 .