Дивергенция Брегмана - 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} + лямбда F_ {2}} (p, q) = D_ {F_ {1}} (p, q) + лямбда 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) = {гидроразрыв {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)}} - сумма p (i) + сумма 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ночь)}$

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

${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} = сумма 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]

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

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