Неравенство Гиббса

В теории информации неравенство Гиббса — это утверждение об информационной энтропии дискретного распределения вероятностей . Несколько других оценок энтропии вероятностных распределений выводятся из неравенства Гиббса, включая неравенство Фано .Впервые он был представлен Дж. Уиллардом Гиббсом в 19 веке.

Неравенство Гиббса

Предположим, что $P=\{p_{1},\ldots ,p_{n}\}$ и $Q=\{q_{1},\ldots ,q_{n}\}$ являются дискретными распределениями вероятностей . Затем

-\sum _{i=1}^{n}p_{i}\log p_{i}\leq -\sum _{i=1}^{n}p_{i}\log q_{i}

с равенством тогда и только тогда, когда $p_{i}=q_{i}$ для $i=1,\dots n$ . ^[1]^: 68 Проще говоря, информационная энтропия распределения $P$ меньше или равна его перекрестной энтропии с любым другим распределением $Q$ .

Разница между этими двумя величинами представляет собой дивергенцию Кульбака – Лейблера или относительную энтропию, поэтому неравенство также можно записать: ^[2]^: 34

D_{\mathrm {KL} }(P\|Q)\equiv \sum _{i=1}^{n}p_{i}\log {\frac {p_{i}}{q_{i}}}\geq 0.

Обратите внимание, что использование логарифмов по основанию 2 не является обязательным, и позволяет называть величины, стоящие в каждой части неравенства, «средний сюрприз » измеряется в битах .

Доказательство

Для простоты докажем утверждение, используя натуральный логарифм, обозначаемый $ln$ , поскольку

\log _{b}a={\frac {\ln a}{\ln b}},

поэтому конкретное основание логарифма $b > 1$ , которое мы выбираем, масштабирует соотношение только на коэффициент $1/ln b$ .

Позволять $I$ обозначаем множество всех $i$ для которого p _i не равно нулю. Тогда, поскольку $\ln x\leq x-1$ для всех x > 0 с равенством тогда и только тогда, когда x=1 , мы имеем:

-\sum _{i\in I}p_{i}\ln {\frac {q_{i}}{p_{i}}}\geq -\sum _{i\in I}p_{i}\left({\frac {q_{i}}{p_{i}}}-1\right)

=-\sum _{i\in I}q_{i}+\sum _{i\in I}p_{i}=-\sum _{i\in I}q_{i}+1\geq 0

Последнее неравенство является следствием того, что p _i и q _i являются частью распределения вероятностей. В частности, сумма всех ненулевых значений равна 1. Однако некоторые ненулевые значения q _i могут быть исключены, поскольку выбор индексов обусловлен тем, что не _pi равно нулю. Следовательно, сумма q _i может быть меньше 1.

До сих пор по набору индексов $I$ , у нас есть:

-\sum _{i\in I}p_{i}\ln {\frac {q_{i}}{p_{i}}}\geq 0

,

или эквивалентно

-\sum _{i\in I}p_{i}\ln q_{i}\geq -\sum _{i\in I}p_{i}\ln p_{i}

.

Обе суммы можно распространить на все $i=1,\ldots ,n$ , то есть в том числе $p_{i}=0$ , напомнив, что выражение $p\ln p$ стремится к 0, так как $p$ стремится к 0, а $(-\ln q)$ имеет тенденцию $\infty$ как $q$ стремится к 0. Приходим к

-\sum _{i=1}^{n}p_{i}\ln q_{i}\geq -\sum _{i=1}^{n}p_{i}\ln p_{i}

Для того чтобы равенство имело место, нам потребуется

${\frac {q_{i}}{p_{i}}}=1$ для всех $i\in I$ так что равенство $\ln {\frac {q_{i}}{p_{i}}}={\frac {q_{i}}{p_{i}}}-1$ держит,
и $\sum _{i\in I}q_{i}=1$ что означает $q_{i}=0$ если $i\notin I$ , то есть, $q_{i}=0$ если $p_{i}=0$ .

Это может произойти тогда и только тогда, когда $p_{i}=q_{i}$ для $i=1,\ldots ,n$ .

Альтернативные доказательства

Альтернативно результат можно доказать, используя неравенство Йенсена , неравенство логарифмической суммы или тот факт, что расхождение Кульбака-Лейблера является формой расхождения Брегмана .

Доказательство с помощью неравенства Йенсена.

Поскольку log — вогнутая функция, у нас есть следующее:

\sum _{i}p_{i}\log {\frac {q_{i}}{p_{i}}}\leq \log \sum _{i}p_{i}{\frac {q_{i}}{p_{i}}}=\log \sum _{i}q_{i}\leq 0

При этом первое неравенство обусловлено неравенством Йенсена, а последнее равенство обусловлено той же причиной, что и в приведенном выше доказательстве.

Кроме того, поскольку $\log$ строго вогнута, то по условию равенства неравенства Йенсена мы получаем равенство, когда

{\frac {q_{1}}{p_{1}}}={\frac {q_{2}}{p_{2}}}=\cdots ={\frac {q_{n}}{p_{n}}}

и

\sum _{i}q_{i}=1

Предположим, что это соотношение $\sigma$ , тогда у нас есть это

1=\sum _{i}q_{i}=\sum _{i}\sigma p_{i}=\sigma

Где мы используем тот факт, что $p,q$ являются вероятностными распределениями. Следовательно, равенство имеет место, когда $p=q$ .

Доказательство с помощью дивергенции Брегмана.

Альтернативно это можно доказать, заметив, что $q-p-p\ln {\frac {q}{p}}\geq 0$ для всех $p,q>0$ , с соблюдением равенства iff $p=q$ . Затем, суммируя по состояниям, мы имеем $\sum _{i}q_{i}-p_{i}-p_{i}\ln {\frac {q_{i}}{p_{i}}}\geq 0$ с равенством, если и только если $p=q$ .

Это связано с тем, что КЛ-дивергенция — это дивергенция Брегмана , порожденная функцией $t\mapsto \ln t$ .

Следствие

Энтропия $P$ ограничено: ^[1]^: 68

H(p_{1},\ldots ,p_{n})\leq \log n.

Доказательство тривиально – просто положить $q_{i}=1/n$ для всех я .

См. также

Ссылки

^ Jump up to: ^а ^б Пьер Бремо (6 декабря 2012 г.). Введение в вероятностное моделирование . Springer Science & Business Media. ISBN 978-1-4612-1046-7 .
^ Дэвид Дж. К. Маккей (25 сентября 2003 г.). Теория информации, логический вывод и алгоритмы обучения . Издательство Кембриджского университета. ISBN 978-0-521-64298-9 .

[Bremaud2012-1] Jump up to: ^а ^б Пьер Бремо (6 декабря 2012 г.). Введение в вероятностное моделирование . Springer Science & Business Media. ISBN 978-1-4612-1046-7 .

[MacKay2003-2] Дэвид Дж. К. Маккей (25 сентября 2003 г.). Теория информации, логический вывод и алгоритмы обучения . Издательство Кембриджского университета. ISBN 978-0-521-64298-9 .

[1]

[2]