Цепное правило энтропии для последовательности случайных величин

Здравствуйте! В предыдущем уроке мы разобрали цепное правило для двух переменных:

$$H(X,Y)=H(X)+H(Y\mid X).$$

Оно разделяет неопределённость пары на неопределённость первого наблюдения и среднюю дополнительную неопределённость второго, когда первое уже известно. Теперь сделаем следующий шаг: применим ту же идею к целой последовательности $X_1,\dots ,X_n$.

Это центральная конструкция для последовательных источников, марковских процессов и авторегрессивных моделей. В частности, именно она позволяет разложить неопределённость текста на неопределённость каждого очередного токена с учётом его префикса.

---

От факторизации вероятности к разложению энтропии

Пусть $X_{1:n}$ обозначает последовательность случайных величин:

$$X_{1:n}=(X_1,X_2,\dots ,X_n).$$

Для конкретной реализации $x_{1:n}$ обычное цепное правило вероятности даёт:

$$p(x_{1:n})=p(x_1)\prod _{t=2}^{n}p(x_t\mid x_{1:t-1}).$$

Иными словами, вероятность всей последовательности выражается через вероятность первого элемента и условные вероятности каждого следующего элемента при уже известной истории.

Возьмём отрицательный логарифм. Произведение превращается в сумму:

$$-{\log }_{2}p(x_{1:n})=-{\log }_{2}p(x_1)-\sum _{t=2}^n{\log }_{2}p(x_t\mid x_{1:t-1}).$$

Левая часть — surprisal конкретной полной последовательности. Правая часть говорит: неожиданность всей последовательности складывается из неожиданностей её шагов, причём на шаге $t$ мы уже знаем префикс $x_{1:t-1}$.

Теперь усредним по всем последовательностям, порождённым распределением $p$. Получаем цепное правило энтропии:

$$\boxed{H(X_{1:n})=H(X_1)+\sum _{t=2}^{n}H(X_t\mid X_{1:t-1})}$$

или, если договориться, что $X_{<t}=X_{1:t-1}$, в более компактной форме:

$$\boxed{H(X_{1:n})=\sum _{t=1}^{n}H(X_t\mid X_{<t})}$$

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

$$H(X_1\mid X_{<1})=H(X_1).$$

Смысл формулы стоит читать буквально:

• $H(X_1)$ — неопределённость первого элемента;
• $H(X_2\mid X_1)$ — дополнительная неопределённость второго после наблюдения первого;
• $H(X_3\mid X_1,X_2)$ — то, что ещё неизвестно о третьем элементе после первых двух;
• сумма — неопределённость всей последовательности как единого объекта.

---

Последовательность как пошаговое раскрытие неопределённости

Для трёх переменных цепное правило имеет вид:

$$H(X_1,X_2,X_3)=H(X_1)+H(X_2\mid X_1)+H(X_3\mid X_1,X_2).$$

Это можно получить, применив уже знакомое правило дважды:

$$H(X_1,X_2,X_3)=H(X_1)+H(X_2,X_3\mid X_1),$$ $$H(X_2,X_3\mid X_1)=H(X_2\mid X_1)+H(X_3\mid X_1,X_2).$$

Важны две вещи.

Совместная энтропия не зависит от порядка записи, слагаемые — зависят

Величина

$$H(X_1,X_2,X_3)$$

не меняется, если переставить переменные. Но разложение меняется. Для любой перестановки $\pi$:

$$H(X_1,\dots ,X_n)=\sum _{t=1}^{n}H(X_{\pi (t)}\mid X_{\pi (1)},\dots ,X_{\pi (t-1)}).$$

То есть «общий бюджет неопределённости» один и тот же, но он распределяется между этапами наблюдения по-разному.

Для языковой модели порядок не произволен: токены поступают слева направо. Поэтому естественно использовать именно

$$H(X_t\mid X_{<t}).$$

Нельзя молча выбрасывать дальнюю историю

Формула всегда содержит весь префикс:

$$H(X_t\mid X_{1:t-1}).$$

Заменить его на

$$H(X_t\mid X_{t-1})$$

можно лишь при дополнительном предположении первого порядка Маркова:

$$p(x_t\mid x_{1:t-1})=p(x_t\mid x_{t-1}).$$

Тогда:

$$H(X_t\mid X_{1:t-1})=H(X_t\mid X_{t-1}).$$

Это точное упрощение для марковского источника, а не общая эвристика. В естественном языке или в сложной траектории агента дальний контекст часто меняет распределение следующего шага, поэтому отброс истории может существенно завысить реальную неопределённость.

---

Небольшой марковский источник: три связанных бита

Пусть $X_1$ — честный бит:

$$P(X_1=0)=P(X_1=1)=\frac{1}{2}.$$

Каждый следующий бит с вероятностью $0.9$ повторяет предыдущий и с вероятностью $0.1$ меняется:

$$P(X_t=X_{t-1})=0.9,P(X_t\ne X_{t-1})=\mathrm{0.1.}$$

Так как бит симметрично «переключается», маргинально каждый из $X_1,X_2,X_3$ остаётся честным:

$$H(X_1)=H(X_2)=H(X_3)=1\text{ бит}.$$

Однако из этого не следует, что энтропия тройки равна $3$ битам. Переменные зависимы: зная предыдущий бит, следующий обычно предсказуем.

Условная энтропия перехода равна бинарной энтропии шума:

$$\begin{array}{rl}H(X_t\mid X_{t-1})& =-h_2(0.1)\text{ с корректным знаком в определении}\\ & =-\left[0.9{\log }_{2}0.9+0.1{\log }_{2}0.1\right]\\ & \approx 0.469\text{ бита}.\end{array}$$

Поскольку источник первого порядка Маркова:

$$H(X_3\mid X_1,X_2)=H(X_3\mid X_2)\approx \mathrm{0.469.}$$

Значит:

$$\begin{array}{rl}H(X_1,X_2,X_3)& =H(X_1)+H(X_2\mid X_1)+H(X_3\mid X_1,X_2)\\ & =1+0.469+0.469\\ & \approx 1.938\text{ бита}.\end{array}$$

Хотя каждый отдельный бит имеет энтропию $1$ бит, вся тройка содержит менее двух бит совместной неопределённости. Наблюдение предыдущих значений устраняет большую часть неопределённости следующих.

Посмотрим на две конкретные последовательности.

Для $000$:

$$p(000)=0.5\cdot 0.9\cdot 0.9=0.405,$$ $$-{\log }_{2}p(000)=1-{\log }_{2}0.9-{\log }_{2}0.9\approx 1.304\text{ бита}.$$

Для $011$:

$$p(011)=0.5\cdot 0.1\cdot 0.9=0.045,$$ $$-{\log }_{2}p(011)=1-{\log }_{2}0.1-{\log }_{2}0.9\approx 4.474\text{ бита}.$$

Вторая последовательность неожиданнее: после нулевого первого бита происходит редкая смена на единицу. Цепное правило для энтропии — это среднее такой пошаговой декомпозиции surprisal по всем возможным траекториям.

---

---

Условное цепное правило: известный контекст вне последовательности

Иногда последовательность не начинается «с нуля»: есть внешний контекст $C$. Например, для генерации ответа контекстом могут быть system prompt, пользовательский запрос, retrieved documents и предыдущие сообщения.

Тогда применяется условная версия:

$$\boxed{H(X_{1:n}\mid C)=\sum _{t=1}^{n}H(X_t\mid C,X_{<t})}$$

Она выражает среднюю неопределённость последовательности после того, как контекст уже наблюдён.

Это важно читать осторожно. Условная энтропия усредняется по возможным значениям $C$. Для некоторого конкретного контекста $c$ энтропия следующего токена

$$H(X_t\mid C=c,X_{<t}=x_{<t})$$

может оказаться высокой или низкой. Величина

$$H(X_t\mid C,X_{<t})$$

усредняет такие локальные неопределённости по распределению контекстов и историй.

---

Вычисление разложения по совместному тензору в PyTorch

Для небольшой дискретной модели можно явно хранить совместное распределение как тензор. В примере ниже ось $0$ соответствует $X_1$, ось $1$ — $X_2$, ось $2$ — $X_3$.

import torch


def entropy_bits(p: torch.Tensor) -> torch.Tensor:
    """Entropy of any normalized discrete probability tensor, in bits."""
    p = torch.as_tensor(p, dtype=torch.float64)

    if (p < 0).any():
        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.where(p > 0, p.log2(), torch.zeros_like(p))
    return -(p * log_p).sum()


def prefix_entropy(p_joint: torch.Tensor, t: int) -> torch.Tensor:
    """
    H(X_1, ..., X_t), where p_joint has one axis per variable.
    t is a one-based prefix length.
    """
    if not 1 <= t <= p_joint.ndim:
        raise ValueError("t must be between 1 and the number of variables.")

    suffix_dims = tuple(range(t, p_joint.ndim))
    p_prefix = p_joint.sum(dim=suffix_dims) if suffix_dims else p_joint
    return entropy_bits(p_prefix)


def chain_rule_terms(p_joint: torch.Tensor) -> tuple[torch.Tensor, torch.Tensor]:
    """
    Returns:
      prefix_entropies[t - 1] = H(X_1, ..., X_t)
      terms[t - 1] = H(X_t | X_1, ..., X_{t-1})
    """
    prefix_entropies = torch.stack([
        prefix_entropy(p_joint, t)
        for t in range(1, p_joint.ndim + 1)
    ])

    terms = torch.cat([
        prefix_entropies[:1],
        prefix_entropies[1:] - prefix_entropies[:-1],
    ])

    return prefix_entropies, terms

Построим совместное распределение для описанного марковского источника:

transition = torch.tensor([
    [0.9, 0.1],  # P(X_t | X_{t-1}=0)
    [0.1, 0.9],  # P(X_t | X_{t-1}=1)
], dtype=torch.float64)

p_x123 = torch.zeros(2, 2, 2, dtype=torch.float64)

for x1 in range(2):
    for x2 in range(2):
        for x3 in range(2):
            p_x123[x1, x2, x3] = (
                0.5
                * transition[x1, x2]
                * transition[x2, x3]
            )

prefix_h, chain_h = chain_rule_terms(p_x123)

print("Prefix entropies:", prefix_h)
print("Chain-rule terms:", chain_h)
print("Joint entropy:", entropy_bits(p_x123))
print("Sum of terms:", chain_h.sum())

Ожидаемый результат с небольшими различиями округления:

Prefix entropies: tensor([1.0000, 1.4690, 1.9380])
Chain-rule terms: tensor([1.0000, 0.4690, 0.4690])
Joint entropy: tensor(1.9380)
Sum of terms: tensor(1.9380)

Проверка цепного правила должна быть инвариантом теста:

assert torch.allclose(
    entropy_bits(p_x123),
    chain_h.sum(),
    atol=1e-12,
)

assert torch.allclose(
    chain_h[0],
    entropy_bits(p_x123.sum(dim=(1, 2))),
    atol=1e-12,
)

Здесь условные члены вычислены как разности энтропий префиксов:

$$H(X_t\mid X_{<t})=H(X_{1:t})-H(X_{<t}).$$

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

---

Связь с авторегрессивными языковыми моделями

Авторегрессивная модель задаёт распределение над продолжением через локальные распределения следующего токена:

$$q_{\theta }(x_{1:T})=\prod _{t=1}^T{q}_{\theta }(x_t\mid x_{<t}).$$

Поэтому её отрицательное лог-правдоподобие на конкретной последовательности также раскладывается по токенам:

$$-\log q_{\theta }(x_{1:T})=\sum _{t=1}^T-\log q_{\theta }(x_t\mid x_{<t}).$$

Это формально похоже на цепное правило энтропии, но объекты различны:

Величина	Что усредняется	Какое распределение используется
$H_p(X_{1:T})$	Последовательности из истинного распределения	Истинное $p$
$-\log q_{\theta }(x_{1:T})$	Одна наблюдаемая последовательность	Модельное $q_{\theta }$
Ожидаемый token-level NLL	Данные из $p$	Оценки модели $q_{\theta }$

Если модель совпадает с истинным распределением, ожидаемый NLL равен энтропии источника. Если не совпадает, появляется дополнительный член, который позднее будет описан через cross-entropy и KL-дивергенцию.

Практически цепное правило объясняет, почему token-level метрики можно агрегировать по последовательности: каждый токен вносит собственную условную неожиданность, а сумма соответствует неожиданности всей строки при выбранной модели.

---

Итог

Цепное правило энтропии переносит знакомое двухпеременное разложение на последовательности:

$$H(X_{1:n})=\sum _{t=1}^{n}H(X_t\mid X_{<t}).$$

Главные выводы:

• совместная неопределённость последовательности равна сумме дополнительных неопределённостей на каждом шаге;
• для конкретной последовательности аналогично раскладывается surprisal;
• порядок переменных меняет отдельные условные слагаемые, но не их сумму;
• полную историю можно заменить последним состоянием только при обоснованной марковской структуре;
• для авторегрессивной модели эта же факторизация лежит в основе последовательностного log-likelihood и token-level NLL.

В следующем уроке мы сменим фокус: рассмотрим энтропию как функцию распределения и докажем её вогнутость. Это свойство затем позволит строго показать, почему равномерное распределение имеет максимальную энтропию на фиксированном конечном носителе.