Расхождение Брегмана - Bregman divergence

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

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

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

Определение

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

Расстояние Брегмана, связанное с F для очков ${displaystyle p,qin Omega }$ разница между значением F в точке п и значение первого порядка Расширение Тейлора из F вокруг точки q оценивается в точке п:

${displaystyle D_{F}(p,q)=F(p)-F(q)-langle abla F(q),p-qangle .}$

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

• Неотрицательность: ${displaystyle D_{F}(p,q)geq 0}$ для всех p, q. Это следствие выпуклости F.
• Выпуклость:${displaystyle D_{F}(p,q)}$ выпукла по первому аргументу, но не обязательно по второму (см. ^[1])
• Линейность: Если мы подумаем о расстоянии Брегмана как об операторе функции F, то она линейна по неотрицательным коэффициентам. Другими словами, для ${displaystyle F_{1},F_{2}}$ строго выпуклый и дифференцируемый, и ${displaystyle lambda geq 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^{*}=abla F(p)}$ и ${displaystyle q^{*}=abla F(q)}$ - двойственные точки, соответствующие p и q.

• Имею ввиду как минимизатор: Ключевым результатом о расходимостях Брегмана является то, что для заданного случайного вектора средний вектор минимизирует ожидаемое расхождение Брегмана от случайного вектора. Этот результат обобщает результат учебника о том, что среднее значение набора минимизирует общую квадратичную ошибку для элементов набора. Этот результат был доказан для векторного случая (Banerjee et al. 2005) и распространен на случай функций / распределений (Frigyik et al. 2008). Этот результат важен, поскольку он дополнительно оправдывает использование среднего как представителя случайного набора, особенно при байесовской оценке.

Примеры

• Квадратное евклидово расстояние ${displaystyle D_{F}(x,y)=|x-y|^{2}}$ является каноническим примером расстояния Брегмана, порожденного выпуклой функцией ${displaystyle F(x)=|x|^{2}}$
• Квадрат Расстояние Махаланобиса, ${displaystyle D_{F}(x,y)={ frac {1}{2}}(x-y)^{T}Q(x-y)}$ которое порождается выпуклой функцией ${displaystyle F(x)={ frac {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)}}-1ight)}$

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

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

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

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

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

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

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

Список распространенных матричных расхождений Брегмана см. В таблице 15.1 дюйм.^[3]

Приложения

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

использованная литература

1. «Совместная и раздельная выпуклость расстояния Брегмана», Х. Баушке и Дж. Борвейн, в Д. Бутнариу, Ю. Цензоре и С. Райхе, редакторах, По сути, параллельные алгоритмы в технико-экономическом обосновании и оптимизации и их приложения, Elsevier 2001
2. Нильсен, Франк; Нок, Ричард (2018). «Расхождение аккордов Брегмана». arXiv:1810.09113 [cs.LG ].
3. «Матричная информационная геометрия», Р. Нок, Б. Магдалу, Э. Брайс и Ф. Нильсен, pdf, из этого книга
4. Эхсан Амид, Манфред К. Вармут, Рохан Анил, Томер Корен (2019). «Надежная двухмерная логистическая потеря, основанная на расхождениях Брегмана». Конференция по нейронным системам обработки информации. С. 14987-14996. pdf

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

внешняя ссылка