Модуль 6. Кодирование источника: от энтропии к реальным битам

Как читать этот модуль. Основной маршрут — §§6.1–6.8: от вероятностной модели и неравенства Крафта до арифметического кодирования, AEP, энтропийной скорости и метрик языковых моделей. §6.9 — математическое углубление про универсальное последовательное предсказание. §§6.10–6.11 возвращают теорию к оценке качества LLM и к воспроизводимому компрессионному эксперименту.

6.1. Инженерная постановка: вероятностная модель и энтропийный кодер

В предыдущих модулях величина $-\log q(x)$ появлялась прежде всего как функция потерь: чем меньшую вероятность модель назначила наблюдению, тем выше штраф. Теперь мы прочитаем ту же величину как длину описания.

Представим, что две модели оценивают один и тот же фрагмент данных $x$ и возвращают следующие вероятности этого фрагмента:

$$q_A(x)=2^{-1200}, \qquad q_B(x)=2^{-1116}.$$

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

Перейдём от вероятностей к длинам:

$$-\log_2 q_A(x)=1200, \qquad -\log_2 q_B(x)=1116.$$

У второй модели отрицательное логарифмическое правдоподобие меньше на

$$1200-1116=84\ \text{бита}.$$

Иначе говоря, модель $B$ назначает этому фрагменту идеальную информационную длину на 84 бита меньше. Чтобы получить реальный обратимый файл, к вероятностям ещё нужно подключить энтропийный кодер; его служебная избыточность будет рассмотрена ниже.

Здесь у модели и кодера разные роли.

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

Пусть источник порождает последовательность $X_{1:n}$ по распределению $P$, а авторегрессионная модель задаёт

$$q_\theta(x_{1:n}) = \prod_{t=1}^{n}q_\theta(x_t\mid x_{<t}).$$

Идеальная информационная длина конкретной последовательности под моделью равна

$$\boxed{ L_{\mathrm{ideal}}(x_{1:n};q_\theta) = -\log_2q_\theta(x_{1:n}) = \sum_{t=1}^{n}-\log_2q_\theta(x_t\mid x_{<t}) }.$$

Это та же по-токенная отрицательная логарифмическая потеря, только измеренная в битах. Если библиотека считает NLL натуральным логарифмом, достаточно разделить результат на $\ln 2$.

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

$$\frac12, \qquad \frac18, \qquad \frac14,$$

то идеальный счёт равен

$$1+3+2=6\ \text{бит}.$$

Логарифм делает здесь ту же работу, что и в Модуле 1: произведение условных вероятностей превращается в сумму кодовых затрат.

Идеальная длина, длина потока и полная длина описания

Для компрессионного эксперимента полезно держать рядом три величины.

1. Идеальная длина данных $$L_{\mathrm{ideal}}=-\log_2q_\theta(x).$$ Именно её измеряет NLL в битах.
2. Фактически выпущенный поток $$L_{\mathrm{stream}} =L_{\mathrm{ideal}}+\Delta_{\mathrm{coder}}.$$ Поправка $\Delta_{\mathrm{coder}}$ включает конечную точность вероятностей, завершение кода, заголовки и выравнивание.
3. Полная длина самостоятельного описания $$L_{\mathrm{total}} =L(\theta)+L(\text{токенизатор})+L(\text{кодер и протокол}) +L_{\mathrm{stream}}+L(\text{служебные данные}).$$ Она отвечает на вопрос, сколько стоит архив, если у декодера заранее нет модели и протокола.

Обычная валидационная функция потерь измеряет первый счёт. Практический кодер диапазонов (range coder) приближает второй. Автономный архив обязан оплатить третий.

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

6.2. Префиксные коды и неравенство Крафта—Макмиллана

Начнём с простейшего кодера: каждому символу конечного алфавита

$$\mathcal X=\{x_1,\ldots,x_m\}$$

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

Код называется префиксным (prefix code), если ни одно кодовое слово не является началом другого. Например,

$$\{0,10,110,111\}$$

— префиксный код, а

$$\{0,01,11\}$$

— нет: после чтения первого нуля декодер ещё не знает, закончился символ или началось слово 01.

Префиксность даёт мгновенное декодирование без разделителей. Но за это удобство приходится соблюдать строгий бюджет.

Теорема Крафта. Положительные целые числа $\ell_1,\ldots,\ell_m$ являются длинами некоторого двоичного префиксного кода тогда и только тогда, когда

$$\boxed{ \sum_{i=1}^{m}2^{-\ell_i}\le1 }.$$

Почему возникает неравенство Крафта

Полное бинарное дерево удобно читать как единицу ресурса. Кодовое слово длины $\ell$ занимает долю

$$2^{-\ell}$$

всех достаточно длинных двоичных продолжений. Короткое слово дорого: код длины 1 сразу откусывает половину дерева; длины 2 — четверть; длины 3 — восьмую часть.

Для кода

$$\{0,10,110,111\}$$

бюджет использован полностью:

$$\frac12+\frac14+\frac18+\frac18=1.$$

Хочется сделать частый символ короче — придётся освободить для него крупную ветвь и вытеснить другие символы глубже.

Именно поэтому не существует набора произвольно коротких кодовых слов. Неравенство Крафта — не техническая формальность, а геометрия ограниченного ресурса.

Обратная часть теоремы конструктивна: если длины укладываются в бюджет, листья можно разместить в дереве без пересечений. Для более общего класса однозначно декодируемых кодов та же необходимая оценка известна как часть теоремы Крафта—Макмиллана. В дальнейшем префиксных кодов достаточно: они дают ту же границу на среднюю длину и проще устроены.

6.3. Односимвольная теорема кодирования

Пусть $X\sim P$, где

$$p_i=P(X=x_i),$$

а символу $x_i$ назначено кодовое слово длины $\ell_i$. Средняя длина равна

$$L=\sum_i p_i\ell_i.$$

Теперь возникает центральный вопрос: насколько малым может быть $L$?

Нижняя граница средней длины кода

Для любого двоичного префиксного кода

$$\boxed{L\ge H_2(P)}.$$

Короткое доказательство стоит оставить в основном маршруте: оно показывает, из чего именно складывается цена неоптимального кода.

Положим

$$Z=\sum_i2^{-\ell_i}\le1, \qquad q_i=\frac{2^{-\ell_i}}{Z}.$$

Тогда $Q=(q_i)$ — распределение, неявно заданное длинами кода. Получаем

$$\begin{aligned} L-H_2(P) &=\sum_i p_i\log_2\frac{p_i}{2^{-\ell_i}}\\ &=D_{\mathrm{KL},2}(P\|Q)-\log_2Z\\ &\ge0. \end{aligned}$$

На этом месте удобно остановиться и прочитать формулу словами:

$$\boxed{ L-H_2(P) = \underbrace{D_{\mathrm{KL},2}(P\|Q)}_{\text{код настроен не на тот источник}} + \underbrace{(-\log_2Z)}_{\text{часть дерева не использована}} }.$$

Это доказательство — бухгалтерия префиксного кода. Зазор возникает по двум причинам: длины ведут себя так, будто источник имеет распределение $Q$, а не $P$, и код может оставить часть бюджета Крафта пустой.

Равенство $L=H_2(P)$ возможно только если

$$Q=P \qquad\text{и}\qquad Z=1.$$

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

$$p_i=2^{-\ell_i}.$$

Точный односимвольный оптимум достигается для диадических распределений, у которых все $-\log_2p_i$ являются целыми числами.

Верхняя граница: шенноновский код

Идеальные вещественные длины

$$-\log_2p_i$$

автоматически исчерпывают бюджет Крафта, потому что $\sum_i p_i=1$. Но двоичное кодовое слово не может иметь длину 2.37 бита. Округлим вверх:

$$\ell_i=\left\lceil-\log_2p_i\right\rceil.$$

Тогда

$$2^{-\ell_i}\le p_i,$$

поэтому длины удовлетворяют Крафту, а

$$\ell_i< -\log_2p_i+1.$$

Следовательно, существует префиксный код со средней длиной

$$\boxed{ H_2(P)\le L<H_2(P)+1 }.$$

Число $+1$ — не фундаментальная потеря на каждый символ. Это плата за то, что в односимвольном коде каждая длина должна быть целой. В §6.5 мы отложим округление до конца длинного блока и разделим эту постоянную на число символов.

Код, построенный по неверной модели

Пусть данные идут из $P$, а код строится по модели $Q$:

$$\ell_Q(x)=\left\lceil-\log_2q(x)\right\rceil,$$

причём $q(x)>0$ на носителе $P$. Тогда

$$H_2(P,Q) \le L_Q < H_2(P,Q)+1.$$

Используя

$$H_2(P,Q)=H_2(P)+D_{\mathrm{KL},2}(P\|Q),$$

получаем

$$\boxed{ H_2(P)+D_{\mathrm{KL},2}(P\|Q) \le L_Q < H_2(P)+D_{\mathrm{KL},2}(P\|Q)+1 }.$$

Теперь операционный смысл KL становится совсем буквальным:

при идеальном дробном кодировании $D_{\mathrm{KL},2}(P\|Q)$ — средняя доплата в битах за использование неверной вероятностной модели.

Односимвольный префиксный код добавляет к этой доплате менее одного бита округления.

6.4. Хаффман, арифметическое кодирование и кодирование диапазонов

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

Хаффман округляет длину каждого символа. Арифметический кодер откладывает округление до конца сообщения.

Код Хаффмана

Алгоритм Хаффмана строит оптимальный бинарный префиксный код для известного конечного распределения.

1. Берём два узла с наименьшими вероятностями.
2. Объединяем их в узел с суммарной вероятностью.
3. Повторяем, пока не останется корень дерева.

Для

$$P=(0.40,0.20,0.15,0.15,0.10)$$

один из оптимальных кодов имеет длины

$$(1,3,3,3,3),$$

поэтому

$$L=2.20\ \text{бит/символ}, \qquad H_2(P)\approx2.1464\ \text{бит/символ}.$$

Зазор невелик. Но целочисленная гранулярность особенно заметна у сильно скошенного бинарного источника:

$$P=(0.99,0.01).$$

Любой непустой двоичный префиксный код тратит по одному биту на символ, тогда как

$$H_2(P)=h_2(0.01)\approx0.0808.$$

Это не провал Хаффмана и не нарушение теоремы. Алгоритм оптимален в своём классе; слишком груб сам класс односимвольных целых длин.

Арифметическое кодирование

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

Пусть

$$p(A)=0.5, \qquad p(B)=0.3, \qquad p(C)=0.2.$$

Разобьём $0,1)$ на интервалы

$$A:[0,0.5), \quad B:[0.5,0.8), \quad C:[0.8,1).$$

Для строки ACB получаем

$$[0,1) \to[0,0.5) \to[0.40,0.50) \to[0.45,0.48).$$

Ширина финального интервала равна

$$0.03=p(A)p(C)p(B)=p(ACB).$$

![

Идеальная информационная длина строки:

$$-\log_2 0.03\approx5.06\ \text{бит}.$$

Но передать нужно не просто точку внутри $0.45,0.48)$, а конечный двоичный префикс, все продолжения которого остаются внутри целевого интервала. Пятибитное число

$$0.01111_2=\frac{15}{32}=0.46875$$

лежит внутри, однако префикс 01111 задаёт весь диадический интервал

$$\left[\frac{15}{32},\frac{16}{32}\right),$$

который выходит за правую границу $0.48$.

Зато шестибитный интервал

$$\left[\frac{29}{64},\frac{30}{64}\right) = [0.453125,0.46875)$$

целиком помещается внутри финального. Ему соответствует префикс 011101.

Эта маленькая деталь полезна: арифметический код передаёт не «удачно выбранное вещественное число», а конечное двоичное описание, по которому декодер однозначно остаётся в нужном интервале.

Для стандартной идеализированной конструкции можно выбрать длину

$$\ell_{\mathrm{AC}}(x_{1:n}) \le \left\lceil-\log_2q(x_{1:n})\right\rceil+1 < -\log_2q(x_{1:n})+2.$$

Округление теперь платится один раз за сообщение, а не на каждом символе.

Условные вероятности и авторегрессионные модели

У фиксированного источника интервалы делятся одной и той же таблицей вероятностей. У языковой модели таблица меняется после каждого токена:

$$q_\theta(x_t\mid x_{<t}).$$

После $n$ шагов ширина выбранного интервала равна

$$\prod_{t=1}^{n}q_\theta(x_t\mid x_{<t}) =q_\theta(x_{1:n}),$$

а идеальная длина —

$$-\log_2q_\theta(x_{1:n}) = \sum_{t=1}^{n}-\log_2q_\theta(x_t\mid x_{<t}).$$

Вот и вся механика связи между языковым моделированием и сжатием: модель обновляет вероятности, а кодер обновляет интервал.

Реальные реализации чаще используют кодирование диапазонов (range coding) или Asymmetric Numeral Systems (ANS). Чтобы декодирование было точным, кодер и декодер должны одинаково воспроизводить:

• дискретизированные вероятности;
• токенизатор и порядок словаря;
• начальный контекст, EOS и правила сброса;
• конечную арифметику и обработку границ.

Поэтому фактический поток близок к NLL-длине, но не обязан отличаться от неё одной универсальной константой для любого программного стека. Конечная точность может давать малую накопительную избыточность; заголовки и служебные данные добавляют отдельную цену.

6.5. Длинные последовательности: блочное кодирование, AEP и энтропийная скорость

Односимвольный код спотыкается о целые длины. Длинный блок позволяет распределить одну единицу округления между многими символами.

Блочный код без потерь

Пусть $X_1,\ldots,X_n$ независимы и одинаково распределены. Рассмотрим весь блок $X^n$ как один суперсимвол. Тогда

$$H(X^n)=nH(X).$$

По односимвольной теореме для распределения блоков существует префиксный код с

$$H(X^n)\le L_n<H(X^n)+1.$$

Разделив на $n$, получаем

$$\boxed{ H(X) \le \frac{L_n}{n} < H(X)+\frac1n }.$$

Это код переменной длины (variable-length) с нулевой ошибкой: исходный блок восстанавливается точно, а средняя цена на символ стремится к энтропии.

Теперь утверждение «энтропия достижима» получает точный смысл. Мы не строим слово длины 2.37 бита для отдельного символа; мы кодируем длинный блок и позволяем дробным длинам взаимно компенсироваться.

AEP и концентрация удельной информационной длины

Для i.i.d.-источника с конечным алфавитом

$$-\frac1n\log_2p(X^n) = \frac1n\sum_{t=1}^{n}-\log_2p(X_t) \xrightarrow{\mathrm{a.s.}} H_2(X).$$

Это асимптотическое свойство равнораспределённости (Asymptotic Equipartition Property, AEP).

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

Определим типичное множество

$$A_\varepsilon^{(n)} = \left\{ x^n: \left|- \frac1n\log_2p(x^n)-H_2(X) \right|<\varepsilon \right\}.$$

При больших $n$ оно обладает тремя свойствами:

1. в нём сосредоточена вероятность, сколь угодно близкая к единице;
2. каждая типичная последовательность имеет вероятность порядка $2^{-nH_2(X)}$;
3. число типичных последовательностей имеет порядок $2^{nH_2(X)}$.

![

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

Индексирование типичного множества даёт другой вариант теоремы кодирования: код фиксированной скорости (fixed-rate) со скоростью немного выше $H(X)$ и вероятностью ошибки, стремящейся к нулю. Это не то же самое, что предыдущий код переменной длины с нулевой ошибкой. Нетипичные строки здесь либо объявляются ошибками, либо получают отдельный механизм исключений (escape).

Источники с зависимостями

Для текста важна не энтропия отдельного токена, а то, сколько нового остаётся после знания прошлого. Для стационарного источника естественной величиной служит энтропийная скорость

$$h = \lim_{n\to\infty}\frac1nH(X_{1:n}),$$

когда предел существует.

Для стационарного эргодического источника с конечным алфавитом теорема Шеннона—Макмиллана—Бреймана даёт

$$-\frac1n\log_2p(X_{1:n}) \xrightarrow{\mathrm{a.s.}} h.$$

Именно $h$ задаёт асимптотическую стоимость источника с зависимостями. Маргинальная энтропия $H(X_1)$ может быть значительно выше: она не использует контекст и каждый раз платит за неопределённость заново.

6.6. Метрики языковой модели: PPL, BPC и BPB

Перплексия, биты на символ и биты на байт — это один и тот же кодовый счёт, разделённый на разные единицы.

Пусть текст превратился в $m$ токенов $t_{1:m}$. Средняя по-токенная NLL в битах равна

$$\widehat L_{\mathrm{token}} = -\frac1m\sum_{i=1}^{m} \log_2q_\theta(t_i\mid t_{<i}).$$

Тогда

$$\operatorname{PPL} =2^{\widehat L_{\mathrm{token}}}.$$

Перплексия — это средняя кодовая длина, у которой логарифм экспоненцировали обратно.

Если модель в среднем тратит 3 бита на токен, её PPL равна $2^3=8$. В специальном равномерном случае это действительно похоже на восемь равновероятных продолжений. Для произвольного распределения PPL лучше читать как экспоненту средней логарифмической цены, а не как буквальное число кандидатов.

Нормировки: на токен, символ и байт

Token PPL зависит от того, что называется токеном. Если одна и та же вероятность сообщения просто перегруппирована из шести токенов в три пары, суммарные биты не меняются, но средняя длина на новую единицу удваивается.

Например:

$$L_{\mathrm{total}}=12\ \text{бит}.$$

Для шести токенов:

$$2\ \text{бита/токен}, \qquad \operatorname{PPL}_{\mathrm{token}}=4.$$

Для трёх пар:

$$4\ \text{бита/пару}, \qquad \operatorname{PPL}_{\mathrm{pair}}=16.$$

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

$$\operatorname{BPC} = \frac{-\log_2q_\theta(t_{1:m})}{N_{\mathrm{chars}}},$$

или

$$\operatorname{BPB} = \frac{-\log_2q_\theta(t_{1:m})}{N_{\mathrm{bytes}}}.$$

BPB обычно воспроизводимее: байты требуют лишь зафиксировать исходный файл. BPC дополнительно зависит от того, что считается символом — байт, Unicode code point или графемой.

Сравнимость метрик и роль токенизации

BPC и BPB не становятся неизменными при замене токенизатора вместе с моделью. Новый токенизатор меняет длину контекста, словарь, вычислительную задачу и обычно само распределение $q_\theta$.

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

Поэтому BPC/BPB делают сравнение содержательнее, но не отменяют протокол. Нужно по-прежнему фиксировать корпус, кодировку, Unicode-нормализацию, границы документов, доступный контекст и способ обработки длинных последовательностей.

6.7. Языковая модель как часть компрессора

Теперь соберём конструкцию полностью.

Кодер и декодер заранее разделяют:

• параметры модели;
• токенизатор или другое обратимое представление входа;
• способ вычисления и квантования вероятностей;
• энтропийный кодер;
• правила начала, конца и сброса контекста.

Кодер видит следующий символ, получает $q_\theta(\cdot\mid x_{<t})$ и сужает интервал. Декодер, уже восстановив тот же префикс, вычисляет то же распределение и понимает, какой символ выбрал битовый поток.

В таком протоколе

$$L_{\mathrm{stream}}(x_{1:n}) \approx -\log_2q_\theta(x_{1:n}),$$

а после усреднения по данным из $P$:

$$\mathbb E_P[-\log_2Q_\theta(X)] = H_2(P)+D_{\mathrm{KL},2}(P\|Q_\theta).$$

Именно поэтому снижение отложенной логарифмической потери (log loss) на одном и том же распределении означает сокращение ожидаемого кода данных.

Здесь есть одна инженерная тонкость. Если токенизация нормализует текст необратимо, компрессор восстанавливает нормализованный текст, а не исходные байты. Для настоящего архива без потерь представление входа должно быть обратимым; иначе само преобразование и потерянные детали нужно отдельно включить в служебные данные.

Эксперимент Delétang et al.

В работе Language Modeling Is Compression (ICLR 2024) предварительно обученные модели соединялись с арифметическим кодером и применялись к байтовым потокам текста, изображений и аудио.

В таблице 1 статьи все наборы имели размер 1 GB и для Transformer-моделей разбивались на независимые блоки по 2048 байта. Для Chinchilla 70B приведены следующие необработанные коэффициенты сжатия (raw compression rates) — отношение длины сжатого кода данных к исходному размеру без стоимости весов:

• $8.3\%$ на enwik9;
• $48.0\%$ на grayscale-патчах ImageNet;
• $21.0\%$ на LibriSpeech.

Результат действительно впечатляет: модель, предварительно обученная преимущественно на тексте, назначала полезные вероятности и нетекстовым байтовым последовательностям.

Но правильная интерпретация уже содержится в самом протоколе. Эксперимент показывает способность к вероятностному предсказанию байтов в конкретных 2048-байтовых блоках. Он не является доказательством семантического понимания изображения или речи. И необработанный коэффициент отвечает на вопрос: «насколько короток код данных, если модель уже бесплатна для обеих сторон?»

В аннотации статьи сообщаются несколько лучшие числа $43.4\%$ и $16.4\%$ для ImageNet и LibriSpeech. Чтобы не смешивать режимы, здесь и на диаграмме используются значения из таблицы 1 вместе с её явным 2048-байтовым протоколом.

6.8. Размер модели, законы масштабирования и полная длина описания

Валидационная функция потерь задаёт хороший вопрос:

сколько бит нужно данным, если модель уже лежит у кодера и декодера?

Автономный архив задаёт более строгий:

кто заплатит за саму модель?

Для двухчастного описания

$$\boxed{ L_{\mathrm{two\mbox{-}part}}(\theta,x) = L(\theta)+L(x\mid\theta) }.$$

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

Delétang et al. считают веса нейросетей по 2 байта на параметр. Для Chinchilla 70B это примерно 140 GB только весов. На корпусе размером 1 GB код данных enwik9 занимает около $0.083$ GB, но полный двухчастный счёт становится примерно

$$140+0.083\ \text{GB},$$

то есть adjusted compression rate из таблицы равна примерно $14008.3\%$.

Это не опровержение пользы больших моделей. Если одна модель многократно используется для огромного потока данных, стоимость весов амортизируется. Но вопрос «хороший ли это предиктор?» и вопрос «хороший ли это самостоятельный архив для данного объёма?» имеют разные ответы.

Законы масштабирования и длина описания

Если отложенная кросс-энтропия уменьшается с масштабом, то уменьшается и длина кода данных при уже известной модели. Это точное и полезное чтение кривой масштабирования (scaling curve).

Более сильный вывод требует дополнительных предпосылок. Из гладкой степенной кривой само по себе не следует, что

$$D_{\mathrm{KL}}(P\|Q_\theta)\to0$$

или что подогнанная асимптота обязательно равна «истинной энтропии языка».

Причины не экзотические:

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

Точная формула по-прежнему сильна:

$$H(P,Q_\theta) = H(P)+D_{\mathrm{KL}}(P\|Q_\theta).$$

Но чтобы прочитать эмпирическую асимптоту как $H(P)$, нужно отдельно обосновать, что KL-разрыв действительно исчезает для конкретно заданного источника и режима контекста.

6.9. Математическое углубление: универсальное кодирование, последовательная логарифмическая потеря и ICL

Можно пропустить при первом чтении. Здесь связь «предсказание = код» расширяется на ситуацию, когда источник заранее неизвестен и предиктор адаптируется по ходу последовательности.

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

$$q_t(x_t\mid x_{<t}).$$

Его суммарная логарифмическая потеря в битах равна

$$L_n =-\sum_{t=1}^{n}\log_2q_t(x_t\mid x_{<t}).$$

Это одновременно идеальная длина последовательного кода. Онлайн-предсказание по логарифмической потере и последовательное сжатие — одна и та же бухгалтерия.

Смесь конечного числа моделей

Пусть имеются модели $P_1,\ldots,P_K$ с априорными весами

$$w_j>0, \qquad \sum_jw_j=1.$$

Байесовская смесь задаёт

$$Q(x_{1:n}) = \sum_{j=1}^{K}w_jP_j(x_{1:n}).$$

Для любой модели $j$

$$Q(x_{1:n})\ge w_jP_j(x_{1:n}),$$

поэтому

$$\boxed{ -\log_2Q(x_{1:n}) \le -\log_2P_j(x_{1:n}) + \log_2\frac1{w_j} }.$$

При равномерных весах смесь проигрывает лучшей модели из конечного класса не более $\log_2K$ бит на всю последовательность.

Это красивый результат универсального предсказания: не зная заранее, какая гипотеза окажется лучшей, мы платим за адаптацию конечным сожалением (regret). Но форма гарантии зависит от класса. Lempel—Ziv, CTW, байесовские смеси и другие универсальные кодеры имеют разные предпосылки и разные скорости избыточности; одной универсальной формулы $O(\log n)$ для всех источников нет.

Связь с in-context learning и её ограничения

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

Теоретические работы дают более содержательные механизмы при специальных предпосылках. Xie et al. выводят неявный байесовский вывод для распределения предварительного обучения в виде смеси HMM. Hahn и Goyal связывают возникновение ICL со структурой и композиционностью обучающих данных.

Эти результаты не превращают произвольную LLM в оптимальный универсальный байесовский предиктор для любого промпта. Корректный измеримый вопрос звучит скромнее:

насколько быстро уменьшается последовательная логарифмическая потеря при добавлении релевантного контекста и относительно какого класса сравнения измеряется сожаление?

6.10. Связь качества сжатия и возможностей модели

Связь

$$\text{лучшее вероятностное предсказание} \Longrightarrow \text{более короткий код данных без потерь}$$

является математическим утверждением. Переход от него к фразе «лучший компрессор умнее» уже требует выбрать определение способностей и протокол измерения.

Hutter Prize использует сжатие без потерь фиксированного 1 GB файла enwik9 как тест поиска структуры в большом текстовом корпусе. Официальный размер результата включает не только сжатые данные, но и программу, которая их восстанавливает. Поэтому конкурсная постановка ближе к полной длине описания, чем к NLL при бесплатной модели.

Huang et al. в работе Compression Represents Intelligence Linearly (COLM 2024) сравнили 31 публичную базовую LLM на 12 тестах знаний, программирования и математического рассуждения. В их протоколе средний результат на тестах коррелировал со средней BPC внешних корпусов с коэффициентом Пирсона около $-0.93$.

Это сильный эмпирический сигнал: хорошее моделирование распределения внешних данных действительно может служить метрикой возможностей без разметки. Но сама работа показывает зависимость силы связи от согласования корпуса с оцениваемой областью. А более позднее исследование моделей для кода (Xuyang et al., 2025) сообщило в своём протоколе скорее логарифмическую, чем универсально линейную зависимость.

Поэтому полезный вывод выглядит так:

эффективность сжатия на отложенном корпусе — содержательная безразметочная метрика качества вероятностной модели и возможный прокси некоторых способностей; форма связи зависит от домена, моделей и тестов и не является общим определением интеллекта.

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

6.11. Практический протокол оценки LLM как компрессора

Перед публикацией числа «модель получила 1.1 BPB» стоит зафиксировать весь договор между кодером и декодером.

1. Исходные данные. Точный файл, версия, лицензия и контрольная сумма.
2. Предобработка. Кодировка, Unicode-нормализация, переносы строк и удаление служебных областей.
3. Единица. Bits/token, BPC или BPB; для BPC — что считается символом.
4. Токенизатор. Версия, специальные токены и обратимость к исходным байтам.
5. Границы. Как задаются BOS, EOS, длина сообщения и сброс контекста.
6. Контекстная политика. Независимые блоки, скользящее окно или непрерывный поток; каждая целевая позиция должна быть посчитана ровно один раз.
7. Модель. Точная ревизия, base или instruction-tuned версия, численная точность и режим вычисления.
8. Вероятности кодера. Как логиты превращаются в целочисленные частоты; совпадает ли процедура у кодера и декодера.
9. Что измерено. Эквивалентная NLL-длина или реально выпущенный битовый поток.
10. Стоимость модели. Считаются ли веса и токенизатор заранее разделяемыми или входят в архив.
11. Контаминация. Мог ли оценочный файл присутствовать в предварительном обучении.
12. Сравнимость. Получили ли все методы один исходный байтовый поток и одинаковый доступный контекст.

Особенно легко ошибиться при оценке авторегрессионной модели со скользящим окном (sliding window). Библиотечная функция потерь обычно сравнивает

$$\texttt{logits[:, :-1]} \quad\text{с}\quad \texttt{labels[:, 1:]},$$

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

Хороший отчёт публикует отдельно:

• эквивалентное NLL число бит;
• размер фактического сжатого потока;
• служебные накладные расходы;
• стоимость модели, если она включена.

Тогда фраза «LLM сжимает данные» становится не аналогией, а воспроизводимым инженерным результатом.

6.13. Заключение

В начале модуля $-\log q$ была знакомой функцией потерь. Теперь у неё появился физически проверяемый смысл: это идеальный счёт в битах, который вероятностная модель выставляет наблюдаемой последовательности.

Основную конструкцию можно собрать в одну строку:

$$\boxed{ \text{вероятностная модель} + \text{энтропийный кодер} = \text{компрессор без потерь} }.$$

Неравенство Крафта показало, почему короткие кодовые слова конкурируют за конечный бюджет. Теорема Шеннона разложила избыточность кода на несовпадение модели и неиспользованный ресурс. Хаффман дал лучший односимвольный префиксный код, а арифметическое кодирование позволило отложить округление до конца сообщения. AEP объяснило, почему длинные последовательности получают устойчивую удельную длину, а энтропийная скорость перенесла результат на источники с зависимостями.

Для ML главное следствие особенно простое:

меньшая отложенная логарифмическая потеря означает более короткий ожидаемый код данных — при том же источнике, той же единице и том же протоколе.

Дальше начинается инженерная честность. PPL зависит от токена; BPC и BPB требуют общего байтового протокола; фактический поток имеет кодовые накладные расходы; самостоятельный архив оплачивает модель; хороший компрессор является сильным предиктором, но не получает автоматически сертификат общего интеллекта.

Теория здесь не разрушает красивую связь предсказания и сжатия. Она делает её сильнее: показывает точное равенство, точную цену несовпадения и точное место, где к коду данных добавляется остальная система.

Основные источники

• C. E. Shannon, «A Mathematical Theory of Communication» (1948).
• D. A. Huffman, «A Method for the Construction of Minimum-Redundancy Codes» (1952).
• T. Cover, J. Thomas, «Elements of Information Theory», глава 5.
• G. Delétang et al., «Language Modeling Is Compression», ICLR 2024.
• Y. Huang et al., «Compression Represents Intelligence Linearly», COLM 2024.
• S. Xuyang, X. Luo et al., «Is Compression Really Linear with Code Intelligence?» (2025).
• S. M. Xie et al., «An Explanation of In-Context Learning as Implicit Bayesian Inference», ICLR 2022.
• M. Hahn, N. Goyal, «A Theory of Emergent In-Context Learning as Implicit Structure Induction» (2023).
• M. Hutter, «Human Knowledge Compression Contest» — официальные правила enwik9.