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

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

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

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

Введение[править | править вики-текст]

Расстояние Кульбака-Лейблера от до обозначается , это, другими словами, количество оставшейся информации, когда Q было использовано для приближения P. Данная мера расстояния в теории информации может интерпретироваться, как величина потерь информации при замене истинного распределения  на распределение .

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

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

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

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

Определение[править | править вики-текст]

Для дискретного вероятностного распределения и , Расстояние Кульбака-Лейблера из в определено[3] так:

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

Для распределения и непрерывных случайных величин, Расстояние Кульбака-Лейблера определено как интеграл:[4]

где p и q – плотности и .

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

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

где мы узнаем энтропию относительно .

Продолжая в этом случае, если – любая мера на , для которой и существует (имеется в виду что p и q абсолютно непрерывны относительно ), тогда РКЛ от до дается как

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

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

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

Артур Хобсон доказал, что Расстояние Кульбака-Лейблера - это единственная мера разницы между вероятностными распределениями, которая удовлетворяют некоторым желательным свойствам, являющимся каноническими расширениями для появляющихся в часто используемых характеристиках энтропии.[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.