Максимизация энтропии на конечном носителе: равномерное распределение и условие равенства

Здравствуйте! В предыдущем уроке мы доказали строгую вогнутость энтропии: при нетривиальном смешивании разных распределений неопределённость строго возрастает относительно средней энтропии компонент. Теперь используем это свойство для фундаментального экстремального результата.

На конечном алфавите, если никаких ограничений, кроме списка допустимых исходов, нет, наиболее неопределённым является равномерный источник. Сегодня важно не только увидеть интуицию, но и получить точное доказательство и аккуратно разобрать условие равенства. Это будет также полезной опорой для сжатия данных: ${\log }_{2}k$ окажется предельным числом бит неопределённости одного символа из алфавита размера $k$.

---

Точная формулировка

Пусть доступный алфавит содержит $k$ исходов:

$$\mathcal{X}=\{1,\dots ,k\},k<\infty .$$

Распределение $p$ на нём имеет вид

$$p=(p_1,\dots ,p_k),p_i\ge 0,\sum _{i=1}^k{p}_i=1.$$

Равномерное распределение обозначим $u$:

$$u_i=\frac{1}{k},i=1,\dots ,k.$$

Теорема. Для любого распределения $p$ на фиксированном алфавите из $k$ символов

$$\boxed{H(p)\le {\log }_{2}k.}$$

Причём

$$\boxed{H(p)={\log }_{2}k⟺p=u.}$$

То есть равенство достигается только тогда, когда каждый исход имеет вероятность $1/k$.

В натах формулировка та же, меняется лишь основание логарифма:

$$H_{\mathrm{nat}}(p)\le \ln k,$$

а максимум по-прежнему достигается только на $u$.

Случай $k=1$ тривиален: существует ровно одно распределение, энтропия равна $0={\log }_{2}1$. Далее будем считать, что $k\ge 2$.

---

Почему симметрия подсказывает ответ

Энтропия не зависит от названий исходов. Если переставить координаты вероятностного вектора, набор слагаемых

$$-p_i{\log }_2{p}_i$$

лишь переупорядочится, поэтому значение $H(p)$ не изменится.

Например, распределения

$$p=(0.7,0.2,0.1)$$

и

$$q=(0.1,0.7,0.2)$$

имеют одинаковую энтропию. С точки зрения неопределённости неважно, какой именно символ получил вероятность $0.7$; существенно только распределение вероятностных масс.

Равномерное распределение выделяется тем, что оно полностью симметрично относительно любых таких переименований. Более того, его можно получить усреднением всех циклических перестановок произвольного $p$. А вогнутость энтропии говорит, что усреднение не уменьшает энтропию.

Это и есть основная идея доказательства.

---

Доказательство через циклические сдвиги и строгую вогнутость

Для удобства перенумеруем символы как $0,\dots ,k-1$. Определим циклический сдвиг распределения $p$:

$$(T^{j}p{)}_i=p_{(i-j)\mathrm{mod}k},j=0,\dots ,k-1.$$

Например, при $k=3$:

$$p=(p_0,p_1,p_2),$$

его сдвиги равны

$$Tp=(p_2,p_0,p_1),$$ $$T^{2}p=(p_1,p_2,p_0).$$

Каждый сдвиг содержит те же вероятности, только в другом порядке. Следовательно,

$$H(T^{j}p)=H(p)$$

для любого $j$.

Теперь усредним все $k$ сдвигов:

$$\bar{p}=\frac{1}{k}\sum _{j=0}^{k-1}{T}^{j}p.$$

Посмотрим на одну координату $i$:

$$\begin{array}{rl}{\bar{p}}_i& =\frac{1}{k}\sum _{j=0}^{k-1}(T^{j}p{)}_i\\ & =\frac{1}{k}\sum _{j=0}^{k-1}{p}_{(i-j)\mathrm{mod}k}.\end{array}$$

Когда $j$ пробегает все значения от $0$ до $k-1$, индекс $(i-j)\mathrm{mod}k$ тоже пробегает каждый индекс ровно один раз. Поэтому

$${\bar{p}}_i=\frac{1}{k}\sum _{\ell =0}^{k-1}{p}_{\ell }=\frac{1}{k}.$$

Значит,

$$\bar{p}=u.$$

Теперь применим вогнутость энтропии к конечной смеси. Из предыдущего урока следует её обобщённая форма:

$$H\left(\sum _{j=0}^{k-1}{\lambda }_j{q}_j\right)\ge \sum _{j=0}^{k-1}{\lambda }_{j}H(q_j),$$

где

$${\lambda }_j\ge 0,\sum _{j=0}^{k-1}{\lambda }_j=1.$$

Берём

$${\lambda }_j=\frac{1}{k},q_j=T^{j}p.$$

Тогда

$$\begin{array}{rl}H(u)& =H\left(\frac{1}{k}\sum _{j=0}^{k-1}{T}^{j}p\right)\\ & \ge \frac{1}{k}\sum _{j=0}^{k-1}H(T^{j}p)\\ & =\frac{1}{k}\sum _{j=0}^{k-1}H(p)\\ & =H(p).\end{array}$$

Но для равномерного распределения

$$\begin{array}{rl}H(u)& =-\sum _{i=1}^k\frac{1}{k}{\log }_2\frac{1}{k}\\ & =-k\cdot \frac{1}{k}{\log }_2\frac{1}{k}\\ & ={\log }_{2}k.\end{array}$$

Следовательно,

$$H(p)\le {\log }_{2}k.$$

Неравенство доказано.

Почему равенство возможно только для uniform

Нам нужна строгая часть вогнутости из прошлого урока. Для смеси с положительными весами равенство в неравенстве вогнутости возможно лишь тогда, когда все смешиваемые распределения совпадают.

В нашем доказательстве это означает:

$$T^{0}p=T^{1}p=\cdots =T^{k-1}p.$$

Достаточно уже условия

$$Tp=p.$$

Но оно говорит, что

$$p_0=p_1=\cdots =p_{k-1}.$$

Так как координаты суммируются к единице, каждая из них должна быть равна $1/k$. Иными словами,

$$p=u.$$

Обратно, если $p=u$, то очевидно

$$H(p)={\log }_{2}k.$$

Таким образом, условие равенства полностью установлено:

$$\boxed{H(p)={\log }_{2}k⟺p_i=\frac{1}{k}\text{для всех }i.}$$

---

Бинарный случай как проверка теоремы

При $k=2$ распределение имеет форму

$$p=(1-q,q),$$

а его энтропия равна бинарной энтропии:

$$h_2(q)=-q{\log }_{2}q-(1-q){\log }_2(1-q).$$

Общий результат в этом случае принимает вид

$$h_2(q)\le {\log }_{2}2=1,$$

и равенство достигается только при

$$q=\frac{1}{2}.$$

Крайние случаи особенно наглядны:

$$h_2(0)=h_2(1)=0.$$

Если исход детерминирован, неопределённости нет. Если два исхода равновероятны, один наблюдаемый символ несёт максимально возможную для бинарного алфавита неопределённость: один бит.

---

Энтропийный дефицит: насколько распределение далеко от uniform

Максимум ${\log }_{2}k$ полезно рассматривать не просто как верхнюю границу, а как точку отсчёта. Определим энтропийный дефицит:

$$\Delta (p)={\log }_{2}k-H(p).$$

Из теоремы следует:

$$\Delta (p)\ge 0,$$

и

$$\Delta (p)=0⟺p=u.$$

Через несколько модулей вы встретите KL-дивергенцию. Уже сейчас можно заметить точное алгебраическое тождество:

$$\begin{array}{rl}{D}_{\mathrm{KL}}(p\Vert u)& =\sum _{i=1}^k{p}_i{\log }_2\frac{p_i}{u_i}\\ & =\sum _{i=1}^k{p}_i{\log }_2{p}_i+{\log }_{2}k\\ & ={\log }_{2}k-H(p).\end{array}$$

То есть

$$\boxed{\Delta (p)=D_{\mathrm{KL}}(p\Vert u).}$$

Пока это следует воспринимать как полезную идентичность, а не как новое определение, на котором строится доказательство: неотрицательность KL-дивергенции мы строго докажем позже. Тогда доказательство максимальности uniform станет одной строкой:

$$H(p)={\log }_{2}k-D_{\mathrm{KL}}(p\Vert u)\le {\log }_{2}k.$$

И условие равенства также будет сразу следовать из того, что KL-дивергенция обращается в ноль только для совпадающих распределений.

---

Тонкость: фиксированный алфавит и фактический носитель

Фраза «на алфавите из $k$ символов» обычно допускает нулевые вероятности. Например,

$$p=(0.5,0.5,0,0)$$

можно считать распределением на алфавите размера $4$, хотя фактически оно использует только два символа. Тогда

$$H(p)=1,{\log }_{2}4=2,$$

поэтому оно не максимизирует энтропию на полном четырёхсимвольном алфавите.

Если же обозначить число символов с ненулевой вероятностью как

$$m=\left|\{i:p_i>0\}\right|,$$

то можно применить теорему к этому уменьшенному носителю:

$$H(p)\le {\log }_{2}m\le {\log }_{2}k.$$

Равенство в первой границе означает uniform на фактическом носителе:

$$p_i=\frac{1}{m}$$

для активных символов. Чтобы достичь глобального максимума ${\log }_{2}k$ на исходном алфавите, необходимо одновременно иметь $m=k$, то есть положительную и одинаковую вероятность у каждого из $k$ символов.

---

Численная проверка в PyTorch

Следующий код вычисляет энтропию, максимум для заданного размера алфавита и KL-дивергенцию до uniform. Он проверяет тождество

$${\log }_{2}k-H(p)=D_{\mathrm{KL}}(p\Vert u).$$

import torch


def entropy_bits(p: torch.Tensor) -> torch.Tensor:
    """Shannon entropy of a 1D discrete distribution, in bits."""
    p = torch.as_tensor(p, dtype=torch.float64)

    if p.ndim != 1:
        raise ValueError("Expected a 1D probability vector.")
    if torch.any(p < 0):
        raise ValueError("Probabilities must be non-negative.")
    if not torch.isclose(p.sum(), torch.tensor(1.0, dtype=p.dtype)):
        raise ValueError("Probabilities must sum to 1.")

    log_p = torch.zeros_like(p)
    positive = p > 0
    log_p[positive] = torch.log2(p[positive])

    return -(p * log_p).sum()


def kl_to_uniform_bits(p: torch.Tensor) -> torch.Tensor:
    """D_KL(p || uniform) in bits."""
    p = torch.as_tensor(p, dtype=torch.float64)
    k = p.numel()
    u_prob = 1.0 / k

    positive = p > 0
    return (
        p[positive] * torch.log2(p[positive] / u_prob)
    ).sum()


p = torch.tensor([0.70, 0.20, 0.10], dtype=torch.float64)
k = p.numel()

h_p = entropy_bits(p)
h_max = torch.log2(torch.tensor(float(k)))
gap = h_max - h_p
kl_uniform = kl_to_uniform_bits(p)

print(f"H(p)                 = {h_p:.6f} bits")
print(f"Maximum log2(k)       = {h_max:.6f} bits")
print(f"Entropy deficit       = {gap:.6f} bits")
print(f"KL(p || uniform)      = {kl_uniform:.6f} bits")

assert h_p <= h_max + 1e-12
assert torch.allclose(gap, kl_uniform, atol=1e-12)

u = torch.full((k,), 1.0 / k, dtype=torch.float64)
assert torch.allclose(entropy_bits(u), h_max, atol=1e-12)

Для этого примера максимум равен

$${\log }_{2}3\approx 1.585$$

бит, тогда как распределение $p=(0.7,0.2,0.1)$ имеет меньшую энтропию. Разница совпадает с KL-дивергенцией от $p$ к равномерному распределению.

В контексте классификатора с $k$ классами равномерный выход softmax означает

$$p_i=\frac{1}{k}$$

для всех классов. Если вероятности получены как

$$p_i=\frac{\exp (z_i)}{{\sum }_j\exp (z_j)},$$

то это происходит тогда и только тогда, когда все логиты равны с точностью до общей константы:

$$z_1=z_2=\cdots =z_k.$$

Следовательно, предиктивная энтропия softmax ограничена сверху величиной ${\log }_{2}k$. Однако высокий уровень этой энтропии означает только близость к равномерности в данном предсказании; он сам по себе ещё ничего не говорит о калибровке модели или о правильности её ответа.

---

Итог

На конечном алфавите размера $k$ энтропия Шеннона удовлетворяет границе

$$\boxed{H(p)\le {\log }_{2}k.}$$

Главная логика доказательства такова:

• все циклические перестановки распределения $p$ имеют ту же энтропию;
• их равновесная смесь в точности даёт uniform;
• по вогнутости энтропия смеси не меньше средней энтропии компонент;
• по строгой вогнутости равенство возможно, только если все циклические сдвиги совпадают;
• инвариантность относительно сдвига заставляет все вероятности быть равными.

Поэтому

$$\boxed{H(p)={\log }_{2}k⟺p_i=\frac{1}{k}\text{ для всех }i.}$$

Также полезно запомнить форму будущей связи:

$${\log }_{2}k-H(p)=D_{\mathrm{KL}}(p\Vert u).$$

Энтропийный дефицит относительно максимума — это в точности расхождение с равномерным распределением.

На этом завершается модуль о базовых свойствах энтропии Шеннона. Далее мы перейдём от меры неопределённости к её операциональному смыслу: энтропия задаёт фундаментальный предел сжатия дискретного источника.