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

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

Дивергенция Брэгмана названа по имени Льва Мееровича Брэгмана, предложившего концепцию в 1967 году.

Формально, для непрерывно дифференцируемой строго выпуклой функции , определённой на замкнутом выпуклом множестве , расстояние Брэгмана определяется как разность между значением функции в точке и значением разложения Тейлора первого порядка функции в точке , вычисленное в точке : .

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

Свойства Дивергенция Брэгмана неотрицательна ( для всех и  — следствие выпуклости ), выпукла по первому аргументу, линейна относительно неотрицательных коэффициентов ( для ).

Дивергенция Брэгмана для выпуклого сопряжения заданной функции связана с :

,

где и  — двойственные точки, соответствующие и .

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

Примеры Квадрат евклидова расстояния является каноническим примером расстояния Брэгмана, образованного выпуклой функцией

Квадрат расстояния Махаланобиса , которое образуется от выпуклой функцией . Это можно рассматривать как обобщение квадрата евклидова расстояния.

Обобщённая дивергенция Кульбака — Лейблера:

образуется функцией отрицательной энтропии: .

Расстояние Итакуры — Сайто:

обобщается выпуклой функцией: .

Обобщение проективной двойственности Ключевым средством в вычислительной геометрии является идея проективной двойственности, которая отображает точки в гиперплоскости и наоборот, сохраняя тем не менее отношения инцидентности и «выше — ниже». Есть много видов проективной двойственности — обычный вид отображает точку в гиперплоскость . Это отображение можно понимать (если отождествлять гиперплоскость с нормалью) как выпуклое сопряжённое отображение, которое переводит точку p в двойственную точку , где определяет -мерный параболоид .

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

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

Дивергенция Брэгмана на других объектах Дивергенцию Брэгмана можно определить для матриц, функций и мер (распределений). Дивергенция Брэгмана для матриц включает функцию потерь ШтайнаОзнакомиться с термином Stein’s loss можно в статье https://www.jstor.org/stable/2241373?seq=1 и . Дивергенции Брэгмана для функций включают полную квадратичную ошибку, относительную энтропию и квадрат смещения. Аналогично дивергенция Брэгмана определяется также для множеств посредством , известная как дискретный аналог выпуклой функции. Субмодулярная дивергенция Брэгмана включает ряд дискретных мер, таких как расстояние Хэмминга, , взаимная информация и некоторые другие меры расстояния на множествах.

Примечания

Литература

Категория:Геометрические алгоритмы Категория:Статистическое расстояние