Расстояние Кульбака — Лейблера

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Расстояние (расхождение) Ку́льбака—Ле́йблера (англ. Kullback–Leibler divergence, информационное расхождение, различающая информация, информационный выигрыш, относительная энтропия, РКЛ)[1] — это неотрицательнозначный функционал, являющийся несимметричной мерой удалённости друг от друга двух вероятностных распределений[2], определённых на общем пространстве элементарных событий. Часто применяется в теории информации и математической статистике.

Расхождение Кульбака–Лейблера распределения относительно (или, условно говоря, «расстояние от до ») обозначается . Первый аргумент функционала (распределение ) обычно интерпретируется как истинное или постулируемое априори распределение, второй (распределение ) — как предполагаемое (проверяемое). Распределение часто служит приближением распределения . Значение функционала можно понимать как количество неучтённой информации распределения , если было использовано для приближения . Данная мера расстояния в теории информации также интерпретируется как величина потерь информации при замене истинного распределения  на распределение .

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

.

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

Хотя расстояние Кульбака—Лейблера (РКЛ) часто рассматривается как способ измерения расстояния между вероятностными распределениями, данный функционал не является метрикой в пространстве распределений, поскольку не удовлетворяет неравенству треугольника и не удовлетворяет аксиоме симметричности: . Тем не менее, его инфинитезимальная форма, особенно его Гессиан, дает метрический тензор, который известен как информационная метрика Фишера.

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

РКЛ изначально было представлено Соломоном Кульбаком и Ричардом Лейблером в 1951 как направленное расхождение между двумя распределениями. Это обсуждается в тексте Кульбака “Информационная теория и статистика”.[1]

Расстояние Кульбака–Лейблера иногда также интерпретируют как информационный выигрыш, достигнутый, если использовано вместо . Иногда для РКЛ используют название (правда, вносящее путаницу) относительная энтропия  относительно , обозначается .

Существуют различные соглашения относительно того, как читать обозначение. Часто его называют просто расхождением между и , однако это не позволяет передать фундаментальную асимметрию в соотношении. Иногда это может быть описано как расхождение из (относительно) (чаще в контексте относительной энтропии или информационного выигрыша). Однако, в этой статье мы используем соглашение, согласно которому обозначениечитается как расхождение относительно (или, условно говоря, «расстояние из в »), которое представляется более удачным с учётом той идеи, что именно считается истинным распределением (т. е. служит основой, исходной точкой для отсчёта расстояния) и математическое ожидание берётся относительно него, а – отличающееся от него распределение, которое может пониматься как аппроксимация .

Частные определения и определения через производную Радона—Никодима[править | править вики-текст]

Для дискретных вероятностных распределений и с числом элементарных событий расхождение Кульбака–Лейблера распределения относительно распределения (или «расстояние от до ») определяется[3] как:

.

Другими словами, это математическое ожидание логарифмической разности между вероятностями и , где математическое ожидание берётся по распределению . РКЛ определено, только если , для всех (абсолютная непрерывность). Всякий раз, когда , вклад -го члена интерпретируется как ноль, потому что .

Для -мерных непрерывных распределений и , расстояние Кульбака–Лейблера задаётся выражением[4]

,

где и функции плотности распределений и соответственно, определённые на интервале .

В более общем смысле, если и – вероятностные меры на множестве , и абсолютно непрерывна относительно , тогда РКЛ от до определено как:

,

где – это производная Радона—Никодима относительно , и при условии, что выражение справа существует. Эквивалентно это может быть записано как

,

что напоминает выражение для дифференциальной энтропии, взятой со знаком минус (впрочем, сходство здесь лишь формальное).

Следует заметить, что использование производной Радона-Никодима служит формальным средством записи данных выражений, однако не раскрывает их содержательный смысл.

Функционал дивергенции Кульбака–Лейблера является безразмерным, однако его значения могут иметь различные единицы измерения. Так, если логарифмы в этих формулах берутся по основанию 2, то дивергенция (она же – информация, с точки зрения теории информации) измеряется в битах; если по основанию e (с натуральным основанием), то дивергенция (информация) измеряется в натах. Большинство формул, содержащих РКЛ, сохраняют смысл независимо от основания логарифма.

Характеризация[править | править вики-текст]

Артур Хобсон доказал, что расстояние Кульбака–Лейблера – это единственная мера разницы между вероятностными распределениями, которая удовлетворяют некоторым желательным свойствам, являющимся каноническими расширениями для появляющихся в часто используемых характеризациях энтропии.[5] Следовательно, взаимная информация – это единственная мера взаимной зависимости, которая подчиняется некоторым связанным условиям, так как она может быть определена в терминах РКЛ.

Существует также Байесовская характеризация расстояния Кульбака-Лейблера.[6]

Мотивировка[править | править вики-текст]

В теории информации, теорема Крафта–Макмиллана устанавливает, что любую непосредственно декодируемую схему кодирования для кодировки сообщения для идентификации одного значения ,  можно рассматривать как представление неявного распределения вероятностей  над , где – длина кода для в битах. Поэтому, РКЛ может быть интерпретировано, как ожидаемая дополнительная длина сообщения с нулевой отметки, которая должна быть передана, если код, который является оптимальным для данного (неправильного) распределения Q, используется, по сравнению с использованием кода на основе истинного распределения P.

, где перекрестная энтропия P и Q, энтропия P.

Отметим также, что существует связь между РКЛ и "функцией скорости" в теории больших отклонений[7][8]

Свойства[править | править вики-текст]

  • Расстояние Кульбака–Лейблера всегда неотрицательно, это результат, который известен как неравенство Гиббса, почти всюду. Энтропия H(P), таким образом, задаёт минимальное значение перекрестной энтропии H(P,Q), ожидаемое число дополнительных битов, требуемых когда используется код, основанный на Q, а не на P. Поэтому РКЛ представляет собой ожидаемое число дополнительных битов, которые должны быть переданы, чтобы определить значение , если используется код, соответствующий распределению вероятностей Q, а не "истинному" распределения P.
  • Расстояние Кульбака-Лейблера не симметрично: .
  • Расстояние Кульбака-Лейблера остается строго определенным для непрерывных распределений, и кроме того инвариантно относительно замены переменных. Например, если сделана замена переменной x на переменную y(x), тогда, так как  и , РКЛ может переписано:

,

где и . Несмотря на предположение, что преобразование было непрерывным, это не необходимо в данном случае. Это также показывает, что РКЛ задаёт величину согласованную с размерностью, так как если x – размерная переменная, то P(x) и Q(x) также имеют размерность, так как является безрамерной величиной. Тем не менее, выражение под логарифмом остаётся безразмерным, как и должно. Поэтому расстояние Кульбака-Лейблера можно рассматривать, в некотором смысле, как более фундаментальную величину, чем некоторые другие свойства в теории информации[9] (такие как собственная информация или энтропия Шеннона), которые могут стать неопределёнными или отрицательными для недискретных вероятностей.

  • РКЛ аддитивна для независимых распределений во многом таким же образом, как энтропия Шеннона. Если являются независимыми распределениями с совместным распределением и, аналогично, , то

Расстояние Кульбака–Лейблера для многомерного нормального распределения[править | править вики-текст]

Допустим, что мы имеем два многомерных нормальных распределения, со средними   и с (обратимыми) матрицами ковариаций . Если два распределения имеют одинаковую размерность k, то РКЛ между распределениями следующее[10]:

Логарифм в последнем члене должен быть взят по основанию e, так как все члены, кроме последнего, являются натуральными логарифмами выражений, которые являются либо любыми множителями функции плотности, либо, в противном случае, возникают естественным образом. Поэтому уравнение дает результат, измеряемый в натах. Целиком разделив это выражение на loge2, получим распределение в битах.

Отношение к метрикам[править | править вики-текст]

Можно было бы назвать РКЛ “метрикой” в пространстве вероятностных распределений, но это было бы некорректно, так как оно не симметрично, и не удовлетворяет неравенству треугольника. Все-таки, будучи предварительной метрикой, она порождает топологию в пространстве вероятностных распределений. Более конкретно, если – это последовательность распределений такая, что ,  тогда говорят, что . Из неравенства Пинкера  следует, что – , где последнее нужно для для сходимости по вариации.

Согласно Альфреду Реньи (1970, 1961).[11][12]

Информационная метрика Фишера[править | править вики-текст]

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

,

где – малое изменение в j-м направлении, а соответствующая скорость изменения распределения вероятностей. Так как РКЛ имеет абсолютный минимум, равный 0, при P=Q, то есть то РКЛ имеет второй порядок малости по параметрам . Более формально, как и для любого минимума, первая производная расхождения обращается в ноль

и разложение Тейлора начинается со второго порядка малости

,

где Гессиан должен быть неотрицательным. Если позволить изменяться (и опуская подиндекс 0), то Гессиан определяет (возможно, вырожденную) метрику Римана в пространстве параметра , называемую информационной метрикой Фишера.

Отношение к другим величинам информационной теории.[править | править вики-текст]

Многие другие величины информационной теории могут быть интерпретированы как применение расстояния Кульбака–Лейблера к частным случаям.

Собственная информация является РКЛ вероятностного распределения P(i) из символа Кронекера, представляющего определённость в том, что i=m – то есть число дополнительных бит, которые должны быть переданы для определения i, если только вероятностное распределение P(i) доступно для получателя, не факт, что i=m.

Взаимная информация

является РКЛ произведения P(X)P(Y) двух маргинальных вероятностных распределений из совместного вероятностного распределения P(X,Y) – т.е. ожидаемое число дополнительных битов, которые должны быть посланы, чтобы определить X и Y, если они закодированы, используя только их маргинальное распределение вместо совместного распределения. Эквивалентно, если совместная вероятность P(X,Y) известна, это ожидаемое число дополнительных битов, которые должны быть в среднем отправлены для определения Y, если значение X уже не известны получателю.

Энтропия Шеннона

это число битов, которые должны быть переданы для идентификации X из N одинаково вероятных исходов, это меньше, чем РКЛ равномерного распределения Pu(X) из истинного распределения P(X) – т.е. меньше ожидаемого числа сохраненных битов, которые должны быть отправлены, если значение X закодировано согласно с равномерным распределением Pu(X), а не истинным распределение P(X).

Условная энтропия

это число битов, которые должны быть переданы для идентификации X из N одинаково вероятных исходов, это меньше, чем РКЛ произведения распределений  из истинного совместного распределения P(X,Y) — т.е. меньше ожидаемого числа сохраненных битов, которые должны быть отправлены, если значение X закодировано согласно с равномерным распределением , а не с условным распределением P(X | Y) данных X и Y.

Перекрестная энтропия между двумя вероятностными распределениями измеряет среднее число битов, необходимых для определения события из множества возможных, если использована схема кодирования, основанная на данном распределении вероятности Q, а не “истинного” распределения P. Перекрестная энтропия для двух распределений P и Q над тем же вероятностным пространством определяется так:

Расстояние Кульбака–Лейблера и Байесовская модификация[править | править вики-текст]

В Байесовской статистике Расстояние Кульбака-Лейблера может быть использовано как мера информационного выигрыша при переходе от априорного к апостериорному вероятностному распределению. Если обнаружен некоторый новый факт Y=y, оно может быть использовано для модификации (априорного) распределения вероятностей для в новое (апостериорное) распределение вероятностей используя Теорему Байеса:

Это распределение имеет новую энтропию

которая может быть меньше или больше, чем изначальная энтропия . Однако, с точки зрения нового распределения вероятностей можно оценить, что использование исходного кода, основанного на вместо нового кода, основанного на , добавило бы ожидаемое число битов  - к длине сообщения. Это, таким образом, представляет собой количество полезной информации, или информационного выигрыша, касательно , которое было получено при обнаружении, что Y=y.

Если впоследствии приходит еще один фрагмент данных, , то вероятностное распределение для x может быть обновлено далее, чтобы дать новое лучшее предположение . Если исследовать заново информационный выигрыш для использования , а не , оказывается, что это может быть больше или меньше, чем предполагалось ранее: , может быть или , чем , и поэтому общий информационный выигрыш не выполняет неравенство треугольника:

, может быть , или чем

Все, что можно сказать, что в среднем, беря среднее, используя , обе стороны будут давать среднее значение.

Экспериментальная модель Байеса[править | править вики-текст]

Широко распространённая цель в экспериментальной модели Байеса – максимизировать ожидаемое РКЛ между априорным и апостериорным распределениями.[13] Когда апостериорное приближено к Гауссовому распределению, модель, максимизирующая ожидаемое РКЛ, называется Байеса d-оптимальное.

Различающая информация[править | править вики-текст]

Расстояние Кульбака-Лейблера может также быть интерпретировано как ожидаемая различающая информация для над : средняя информация на одну выборку для различия в пользу гипотезы , против гипотезы , когда гипотеза верна[14]. Еще одно имя для этой величины, данное Ирвингом Джоном Гудом, это ожидаемая масса доказательства для над , ожидаемая из каждой выборки.

Ожидаемая масса доказательства для над это не то же что информационный выигрыш, ожидаемый, например, для вероятностного распределения p(H) гипотезы, .

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

В шкале энтропии информационного выигрыша очень маленькая разница между почти уверенностью и полной уверенностью – кодирование с почти полной уверенностью вряд ли потребует больше битов, чем кодирование с полной уверенностью. С другой стороны, в logit шкале подразумевается вес доказательств, и разница между двумя огромна, едва ли не бесконечна. Это может отражать разницу между почти уверенностью (на вероятностном уровне), скажем, в том, что Гипотеза Римана верна, и с полной уверенностью, что она верна, потому что имеется математическое доказательство. Две разные шкалы функции потерь для неопределенности обе являются полезными, согласно с тем, насколько хорошо каждая отражает конкретные обстоятельства рассматриваемой проблемы в задаче.

Принцип минимальной различающей информации[править | править вики-текст]

Идея РКЛ как различающей информации привела Кульбака к предположению Принципа Минимальной различающей информации (Principe Minimum Discrimination Information - MDI): учитывая новые факты, новое распределение следует выбрать, из тех, которые трудно отличить от первоначального распределения ; потому что новые данные производят так мало информационного выигрыша как только возможно.

Например, если мы имеем априорное распределение p(x,a) над x и a, и потом изучим истинное распределение a и u(a). РКЛ между новым совместным распределением для x и a, q(x|a) u(a), и прежнего априорного распределения было бы:

т.е. сумма РКЛ p(a) априорного распределения для a из обновленного распределения u(a), плюс ожидаемое значение (используемое вероятностное распределение u(a)) РКЛ априорного условного распределения p(x|a) из нового распределения p(x|a). (Заметьте что часто позднее ожидаемое значение называется условное РКЛ (или условная относительная энтропия) и обозначается [15]. Это минимизирует, если q(x|a) = p(x|a)  над  общим содержанием u(a). И мы замечаем что этот результат объединяет теорему Байеса, если новое распределение u(a) это по факту функция, уверенно представляющая, что a имеет одно частное значение.

Минимальная различающая информация может быть рассмотрена как расширение Принципа безразличия Лапласа (другое его название - принцип недостаточного основания) и Принципа максимума энтропии Джейнса. В частности, это естественное расширение принципа максимума энтропии из дискретного до непрерывного распределения, для которого энтропия Шеннона прекращается, чтобы быть очень удобной (см. дифференциальная энтропия), но РКЛ продолжает быть столь же актуальной.

В инженерной литературе, MDI иногда называется Принцип минимума перекрестной энтропии. Минимизация РКЛ m из p в отношении m эквивалентна минимизации перекрестной энтропии p и m, так который подходит, если попытаться выбрать точное приближенное значение до p.

Пример использования[править | править вики-текст]

Пусть по выборке из распределения некоторой случайной величины требуется восстановить плотность её распределения, заданную в виде параметрического семейства , где - аргумент функции, - неизвестный параметр. Оценка параметра может быть найдена как решение задачи минимизации расстояния Кульбака — Лейблера между плотностью и эмпирической плотностью распределения, считающейся «истинной»,

,

где - функция Дирака:

.

Нетрудно видеть, что решение этой задачи приводит к оценке максимального правдоподобия для параметра . В случае если фактическая плотность распределения случайной величины не принадлежит семейству , найденная оценка параметра называется квазиправдоподобной и обеспечивает наилучшую аппроксимацию фактического распределения, представленного выборкой, среди распределений с плотностями с точки зрения расстояния Кульбака — Лейблера.

Примечания[править | править вики-текст]

  1. 1 2 Kullback S. Information Theory and Statistics. — John Wiley & Sons, 1959.
  2. Kullback S., Leibler R.A. On information and sufficiency // The Annals of Mathematical Statistics. 1951. V.22. № 1. P. 79-86.
  3. MacKay, David J.C. Information Theory, Inference, and Learning Algorithms. — First ed.. — Cambridge University Press, 2003. — С. p. 34.
  4. Bishop C. Pattern Recognition and Machine Learning. — 2006. — С. p. 55.
  5. Hobson, Arthur. Concepts in statistical mechanics.. — Gordon and Breach. — New York, 1971. — ISBN 0677032404.
  6. Baez, John; Fritz, Tobias. Theory and Application of Categories 29. — С. "A Bayesian characterization of relative entropy", p. 421–456..
  7. И.Н. Санов. О вероятности больших отклонений случайных величин. — 1957. — С. 11-44.
  8. Novak S.Y. Extreme Value Methods with Applications to Finance ch. 14.5. — Chapman & Hall. — 2011. — ISBN 978-1-4398-3574-6.
  9. Relative Entropy. videolectures.net. Проверено 14 июня 2016.
  10. Duchi J. "Derivations for Linear Algebra and Optimization". — С. 13.
  11. Rényi A. Probability Theory. — 1970. — ISBN 0-486-45867-9..
  12. Rényi, A. "On measures of entropy and information". — 4th Berkeley Symposium on Mathematics, Statistics and Probability 1960, 1961. — С. 547–561.
  13. Chaloner, K.; Verdinelli, I. "Bayesian experimental design: a review". — Statistical Science 10, 1995. — 273–304 с.
  14. Press, W.H.; Teukolsky, S.A.; Vetterling, W.T.; Flannery, B.P. (2007). "Section 14.7.2. Kullback–Leibler Distance". Numerical Recipes: The Art of Scientific Computing (3rd ed.). Cambridge University Press. ISBN 978-0-521-88068-8 .
  15. Thomas M. Cover, Joy A. Thomas. Elements of Information Theory. — John Wiley & Sons. — 1991. — С. p.22.