Лучшие вопросы
Таймлайн
Чат
Перспективы

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

Из Википедии, свободной энциклопедии

Remove ads

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

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

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

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

.

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

Remove ads

Свойства

Суммиров вкратце
Перспектива

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

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

,

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

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

Remove ads

Примеры

Суммиров вкратце
Перспектива

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

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

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

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

.

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

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

.
Remove ads

Обобщение проективной двойственности

Суммиров вкратце
Перспектива

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

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

Remove ads

Обобщения дивергенции Брэгмана

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

Дивергенция Брэгмана на других объектах

Дивергенцию Брэгмана можно определить для матриц, функций и мер (распределений). Дивергенция Брэгмана для матриц включает функцию потерь Штайна[9] и энтропию Неймана[англ.]. Дивергенции Брэгмана для функций включают полную квадратичную ошибку, относительную энтропию и квадрат смещения[4]. Аналогично дивергенция Брэгмана определяется также для множеств посредством cубмодулярной функции множеств[англ.], известная как дискретный аналог выпуклой функции. Субмодулярная дивергенция Брэгмана включает ряд дискретных мер, таких как расстояние Хэмминга, точность и полнота[англ.], взаимная информация и некоторые другие меры расстояния на множествах[10][11].

Remove ads

Примечания

Литература

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads