Энтропия

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

Энтропия

Энтропия — мера неопределенности или мера хаоса какой-то системы. Обозначается буквой H\H.

Чем больше неопределенность системы, тем больше нужно информации для кодирования её состояния. Получается, что энтропия служит еще и мерой информации, необходимой для описания состояния системы.

Можно определить энтропию Шеннона как

H(Ω)   ⁣=def   ⁣−∑ω   ⁣∈   ⁣ΩP⁡(ω)⋅log⁡P⁡(ω)\H(\Omega) \defeq - \sum\limits_{\omega \;\! \in \;\! \Omega} \prob(\omega) \cdot \log \prob(\omega)

Для непрерывного случая с носителем XX и плотностью распределения f(x)f(x)

H   ⁣=def   ⁣−∫Xf(x)⋅log⁡f(x)dx\H \defeq - \int\limits_{X} f(x) \cdot \log f(x) dx

Откуда взялась эта формула?

Давайте попробуем оценить количество информации, необходимое для кодирования одного исхода.

Посмотрим на nn испытаний, среди которых a≈pna \approx pn удачных и b≈(1−p)⋅nb \approx (1-p) \cdot n неудачных. Результаты испытаний для известных aa и bb кодируются последовательностью бит. Всего таких последовательностей (na)=n!a!⋅b!\binom{n}{a} = \frac{n!}{a! \cdot b!}. Значит, для кодирования каждой последовательности достаточно log⁡n!a!⋅b!\log \frac{n!}{a! \cdot b!} бит.

Получается, что в среднем для кодирования результатов одного исхода понадобится в среднем 1nlog⁡n!a!⋅b!\frac{1}{n} \log \frac{n!}{a! \cdot b!} бит. По формуле Стирлинга log⁡n!=nlog⁡n−n+O(log⁡n)\log n! = n \log n - n + O(\log n),

1n⋅log⁡n!a!⋅b!=1n⋅(log⁡n!−log⁡a!−log⁡b!)≈−plog⁡p−(1−p)⋅log⁡(1−p)\frac{1}{n} \cdot \log \frac{n!}{a! \cdot b!} = \frac{1}{n} \cdot \big(\log n! - \log a! - \log b!\big) \approx - p \log p - (1-p) \cdot \log (1-p)

Например, у системы «брошенная монетка» с распределением вероятностей (12,12)\big(\frac{1}{2}, \frac{1}{2}\big), энтропия

H=2⋅12⋅log⁡22=1\H = 2 \cdot \frac{1}{2} \cdot \log_2 2 = 1

А у системы «брошенная ненормальная монетка» с распределением вероятностей (14,34)\big(\frac{1}{4}, \frac{3}{4}\big) энтропия

H=14⋅log⁡24+34⋅log⁡243≈0.56\H = \frac{1}{4} \cdot \log_2 4 + \frac{3}{4} \cdot \log_2 \frac{4}{3} \approx 0.56

Энтропия нормальной монетки больше энтропии ненормальной. Значит, сообщение о результате броска нормальной монетки несет больше информации, чем сообщение о результате броска ненормальной.

Свойства энтропии

Энтропия системы равна нулю только тогда, когда система состоит из одного состояния.

Действительно, сообщение о состоянии такой системы не несет вообще никакой информации. Мы и так это знали.

Энтропия системы с nn состояниями ограничена числом log⁡n\log n.

H=∑i=1npilog⁡1pi   ⁣⩽   ⁣log⁡(∑i=1npi⋅1pi)=log⁡n\H = \sum\limits_{i=1}^n p_i \log \frac{1}{p_i} \;\! \le \;\! \log \bigg( \sum\limits_{i=1}^n p_i \cdot \frac{1}{p_i} \bigg) = \log n

Если XX и YY — независимые системы, то H(X⋅Y)=H(X)+H(Y)\H(X \cdot Y) = \H(X) + \H(Y).

Примеры распределений

Энтропия равномерного распределения uniform⁡[a,b]\uniform [a, b]

H=∫ab1b−a⋅log⁡(b−a)dx=log⁡(b−a)\H = \int\limits_a^b \frac{1}{b-a} \cdot \log (b-a) dx = \log (b-a)

Энтропия нормального распределения N(μ,σ2)\N (\mu, \sigma^2) с плотностью f(x)=12πσe−(x−μ)22σ2f(x) = \frac{1}{\sqrt{2\pi} \sigma} e^{- \frac{(x-\mu)^2}{2\sigma^2}}

H=−∫−∞∞12πσe−(x−μ)22σ2⋅log⁡(12πσe−(x−μ)22σ2)dx=12log⁡(2πσ2)+12\H = - \int\limits_{-\oo}^{\oo} \frac{1}{\sqrt{2\pi} \sigma} e^{- \frac{(x-\mu)^2}{2\sigma^2}} \cdot \log \bigg( \frac{1}{\sqrt{2\pi} \sigma} e^{- \frac{(x-\mu)^2}{2\sigma^2}} \bigg) dx = \frac{1}{2} \log (2 \pi \sigma^2) + \frac{1}{2}

Энтропия показательного распределения Exp⁡(λ)\Exp (\lambda) с плотностью f(x)=λe−λxf(x) = \lambda e^{-\lambda x}

H=−∫0∞λe−λx⋅log⁡(λe−λx)dx=1−log⁡λ\H = - \int\limits_{0}^{\oo} \lambda e^{-\lambda x} \cdot \log \big( \lambda e^{-\lambda x} \big) dx = 1 - \log \lambda

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

Пусть у нас есть две системы pp и qq. Как понять, насколько qq отличается от pp?

Кросс-энтропия

Кросс-энтропия служит показателем информации, необходимой для распознания одного исхода, если схема кодирования базируется не на истинном распределении pp, а на другом распределении qq.

Эту сложную фразу можно записать как

H(p,q)   ⁣=def   ⁣−∑xp(x)⋅log⁡q(x)=−∫Xp(x)⋅log⁡q(x)dx\H(p, q) \defeq - \sum\limits_x p(x) \cdot \log q(x) = - \int\limits_X p(x) \cdot \log q(x) dx

Если распределение qq близко к распределению pp, то кросс-энтропия H(p,q)\H(p, q) близка к обычной энтропии H(p)\H(p), а полное совпадение H(p,q)=H(p)\H(p, q) = \H(p) происходит в случае, когда распределения pp и qq совпадают почти всюду.

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

Теперь мы можем измерять степень различия двух распределений.

Расстоянием Кульбака-Лейблера между двумя распределениями pp и qq называется величина

KL(p,q)   ⁣=def   ⁣H(p,q)−H(p)=−∑xp(x)⋅log⁡p(x)q(x)\KL(p, q) \defeq \H(p, q) - \H(p) = - \sum\limits_x p(x) \cdot \log \frac{p(x)}{q(x)}

Расстояние Кульбака-Лейблера говорит об увеличении среднего количества информации, если при кодировании использовать распределение qq вместо истинного распределения pp.

Принцип максимальной энтропии

Среди всех распределений на заданном носителе мы хотим иметь дело с имеющим наибольшую энтропию.

Довольно естественно: чем больше энтропия, тем более «произвольное» у нас распределение.