Entropy

Entropy reflects the uncertainty of a probability distribution. It is a quantitive estimation of the amount of information stored in the distribution.

Entropy of discrete distributions

If \(p_k = \mathbb P(\xi = x_k)\) is pmd of a discrete random variable \(\xi\) then its entropy is calculated as

\[ \mathbb H\xi = -\mathbb E \big(\log p(\xi)\big) = -\sum\limits_k p_k \log p_k. \]

The logarithm base can be any number greater than \(1\). In practice two bases are used:

• binary logarithm, then \(\mathbb H\xi\) is measured in bits

• natrural lograrithm, then \(\mathbb H\xi\) is measured in nats

Note

When dealing with entopy, often expression of the form \(0\cdot \log 0\) may arise. By definition it is settled to \(0\).

Entropy of \(\mathrm{Bern}(p)\)

If \(\xi \sim \mathrm{Bern}(p)\) then

\[ \mathbb H\xi = -(1 - p)\log(1 - p) - p\log p. \]

Минимальное значение (нулевое) энтропия принимает при \(p = 0\) или \(p=1\). Исход такого вырожденного эксперимента заранее известен, поэтому наблюдение значения случайной величины не несёт никакой новой информации.

Максимальное значение энтропии достигается в точке \(\frac12\), что вполне соответствует тому, что при \(p=\frac12\) предсказать исход эксперимента сложнее всего.

Entropy of \(\mathrm{Bin}(p)\)

If \(\xi \sim \mathrm{Bin}(p)\), then

\[ \mathbb H\xi = -\sum\limits_{k=0}^n \binom n k p^k (1-p)^{n-k}\Big(\log \binom nk + k\log p + (n-k) \log(1-p)\Big). \]

It can hardly be calculated in closed form.

Entropy of \(\mathrm{Geom}(p)\)

If \(\xi \sim \mathrm{Geom}(p)\), then

\[ \mathbb H\xi = -\sum\limits_{k=1}^\infty q^{k-1}p\big(\log p + (k-1)\log q\big). \]

Unlike for the binomial disribution, this entropy can be easily calculated in closed form (see exercises below).

Entropy of \(\mathrm{Pois}(\lambda)\)

If \(\xi \sim \mathrm{Pois}(\lambda)\), then

\[ \mathbb H\xi = \sum\limits_{k=0}^\infty e^{-\lambda}\frac{\lambda^k}{k!}\big(\lambda - k\log \lambda + \log k!\big) = \lambda - \lambda \log\lambda + e^{-\lambda}\sum\limits_{k=0}^\infty\frac{\lambda^k \log k!}{k!}. \]

It turns out that

\[ \mathbb H\xi = \frac 12\log(2\pi e \lambda) - \frac 1{12\lambda} + \mathcal O\Big(\frac 1{\lambda^2}\Big), \quad \lambda \to +\infty. \]

Differential entropy

Entropy of a continuous random variable is sometimes called differential entropy. Given pdf \(p_\xi(x)\), entropy of \(\xi\) is calculated by the formula

\[ \mathbb H\xi = -\int p_{\xi}(x) \log p_{\xi}(x)\, dx. \]

Note

В дальнейшем мы будем использовать одинаковый термин энтропия как для дискретных, так и для непрерывных случайных величин, для краткости опуская слово дифференциальная в последнем случае. Кроме того, энтропию распределения \(p\), заданного через pmf или pdf, будем обозначать \(\mathbb H[p]\). Такое обозначение позволяет избежать привязки к случайной величине там, где это излишне. Если \(\xi \sim p(x)\), то обозначения \(\mathbb H\xi\) и \(\mathbb H[p]\) эквивалентны. Также отметим, что энтропию можно записать в виде математического ожидания:

\[ \mathbb H[p] = \mathbb E_{\xi \sim p(x)} \log\frac 1{p(\xi)}. \]

Entropy in ML

Entropy is used in decision trees as an information criterion.

KL divergence

Kullback–Leibler divergence measures distance between two probability distributions. KL divergence is calculated as

\[\mathbb{KL}(p\vert\vert q) = \sum\limits_k p_k\log\frac{p_k}{q_k}\]

in discrete case and as

\[\mathbb{KL}(p\vert\vert q) = \int p(x)\log \frac{p(x)}{q(x)}dx\]

in continuous one. Another representation:

\[ \mathbb{KL}(p\vert\vert q) = \int p(x)\log \frac 1{q(x)}dx - \int p(x)\log\frac 1{p(x)}dx =\underbrace{\mathbb E_{\xi \sim p(x)} \frac 1{\log q(\xi)}}_{\text{cross-entropy}} - \underbrace{\mathbb E_{\xi \sim p(x)} \frac1{\log p(\xi)}}_{\text{entropy}}. \]

Дивергенция Кульбака-Лейблера в некотором роде играет роль расстояния между распределениями. В частности, \(\mathbb{KL}(p\vert\vert q)\geqslant 0\), причём дивергенция равна нулю, только если распределения совпадают. Но при этом она не является симметричной: вообще говоря, \(\mathbb{KL}(p\vert\vert q)\ne \mathbb{KL}(q\vert\vert p)\).

Exercises

1. Prove that \(0\leqslant \mathbb H\xi \leqslant \log n\) if \(\Omega = \{1, 2, \ldots, n\}\). For which distribution do these inequalities turn into equalities?

2. Calculate entropy of \(\mathrm{Geom}(p)\) in closed form.

3. Find entropy of \(U[a, b]\).

4. Calculate entropy of \(\mathcal N(\mu, \sigma^2)\).

5. Calculate entropy of \(\mathrm{Exp}(\lambda)\).

6. Calculate entropy of \(\mathrm{Gamma}(\alpha, \beta)\).

7. Find KL divergence between \(\mathrm{Geom}(p)\) and \(\mathrm{Geom}(q)\), \(0 < p, q < 1\). Is \(\mathbb{KL}(p, p) = 0\)? Does equality \(\mathbb{KL}(p, q) = \mathbb{KL}(q, p)\) hold?

8. Find KL divergence between \(p(x) = \mathcal N(x \vert \mu, \sigma^2)\) и \(q(x) = \mathcal N(x \vert \nu, \tau^2)\).

9. Find KL divergence between \(p(x) = \mathrm{Exp}(x \vert \lambda)\) и \(q(x) = \mathrm{Exp}(x \vert \mu)\).