Модуль 10. Алгоритмическая теория информации: кратчайшие описания, MDL и универсальное предсказание

Как читать этот модуль. Основной маршрут — §§10.1–10.8. Сначала мы перейдём от среднего числа бит для источника к длине описания одного конкретного объекта, затем свяжем эту идею с энтропией Шеннона, универсальным предсказанием, MDL и сходством через сжатие. §§10.9–10.10 — факультативные углубления об AIXI и принципе Ландауэра; их можно оставить на второй проход.

10.1. От распределения к одному конкретному объекту

Представим три файла одинакового размера — по миллиону бит каждый.

• Первый состоит из одних нулей.
• Второй содержит первые миллион двоичных знаков числа $\pi$.
• Третий получен из физического источника случайности.

На уровне сырого представления они одинаковы: в каждом ровно миллион записанных бит. Но как описания они различаются радикально. Для первого достаточно команды «напечатай миллион нулей». Для второго — программы вычисления $\pi$ и числа знаков. Для третьего, вероятнее всего, не найдётся описания существенно короче самого файла.

Здесь возникает вопрос, которого не было в классической постановке источника:

Сколько бит нужно не в среднем для распределения, а для воспроизведения именно этого объекта?

Алгоритмическая теория информации (algorithmic information theory, AIT) отвечает: нужно искать кратчайшее эффективное описание, то есть программу, которая печатает объект и останавливается.

Это не замена теории Шеннона, а другой масштаб рассмотрения.

• Энтропия начинает с распределения и спрашивает о среднем счёте за множество возможных сообщений.
• Алгоритмическая сложность начинает с конкретной строки и спрашивает о кратчайшем исполнимом объяснении этой строки.

Такой взгляд особенно полезен в ML.

Выбор модели. Сложная модель может сильнее уменьшить функцию потерь, но за саму модель тоже приходится платить. Отсюда возникает MDL-счёт «модель + данные при модели».

Анализ представлений. Высокая точность диагностического классификатора (probe) ещё не говорит, легко ли извлекается признак. Предиктивно-последовательный код учитывает, сколько примеров и сколько бит понадобилось, чтобы научиться его извлекать.

Сходство объектов. Если после передачи $x$ объект $y$ требует лишь короткого дополнения, у них есть общая алгоритмическая структура. Практическая версия этой идеи приводит к NCD.

Универсальное предсказание. Если коротким вычислимым объяснениям дать больший априорный вес, можно определить идеализированный предиктор, который конкурирует со всеми вычислимыми моделями сразу.

Сразу установим границу понятия. Краткость описания говорит о регулярности, но не измеряет смысл, истинность, полезность или красоту. Короткая программа может печатать бессодержательную строку и работать астрономически долго. Алгоритмическая теория информации измеряет описательную сложность, а не все свойства объекта одновременно.

10.2. Колмогоровская сложность и язык описания

Кратчайшая программа

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

Префиксная колмогоровская сложность строки $x$ определяется как

$$\boxed{ K_U(x) = \min_{p:\,U(p)=x}|p| }.$$

Это длина кратчайшей самоделимитирующейся программы, которая печатает $x$ и останавливается.

Индекс $U$ часто опускают, но машина не исчезает из определения. Вопрос всегда звучит так: насколько коротко объект описывается в выбранном универсальном языке?

Самоделимитирующееся буквальное описание

Для обычной, или простой, сложности $C(x)$ можно положить строку внутрь программы и добавить фиксированную команду «напечатать остаток». Поэтому

$$C(x)\le |x|+O(1).$$

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

$$\boxed{ K(x) \le |x|+K(|x|)+O(1) }.$$

Для $n=|x|$ стоимость $K(n)$ растёт лишь логарифмически; например,

$$K(n) \le \log_2 n+2\log_2\log_2 n+O(1)$$

при достаточно большом $n$. Надбавка мала по сравнению с длинной строкой, но принципиальна: именно самоделимитируемость делает веса $2^{-|p|}$ совместимыми с вероятностной суммой.

Теорема инвариантности

Теперь возникает естественное возражение. Одна и та же идея записывается на Python, C и языке машины Тьюринга разным числом бит. Не становится ли сложность просто свойством выбранного синтаксиса?

Пусть $U$ и $V$ — две оптимальные универсальные префиксные машины. Тогда существует константа $c_{U,V}$, не зависящая от $x$, такая что

$$\boxed{ |K_U(x)-K_V(x)|\le c_{U,V} }.$$

Механика проста. На машине $U$ можно один раз написать интерпретатор для $V$, а затем присоединять к нему любую $V$-программу. Стоимость интерпретатора фиксирована и не растёт вместе с объектом.

Теорема позволяет говорить о $K(x)$ с точностью до аддитивной константы. Для больших объектов это сильная устойчивость. Для коротких строк константа может быть сопоставима с самой сложностью, поэтому абсолютное значение без указания машины не превращается в физическую константу объекта.

Условная сложность

Если декодеру уже известен объект $y$, определяют

$$\boxed{ K(x\mid y) = \min_{p:\,U(p,y)=x}|p| }.$$

Это длина кратчайшего дополнительного описания $x$ при доступном $y$.

Если $x$ и $y$ — две версии репозитория, то $K(x\mid y)$ может быть близка к длине короткого разностного описания (patch), хотя каждый репозиторий сам по себе велик. Именно эта идея позже превратится в алгоритмическую меру сходства.

Что именно измеряет $K(x)$

Две строки одинаковой длины могут занимать разные места на шкале описательной сложности:

• миллион нулей задаётся числом повторов;
• периодическая строка — шаблоном и числом повторов;
• первые $n$ цифр $\pi$ — алгоритмом и значением $n$;
• типичная строка из независимых честных битов требует почти буквального описания.

Здесь важно отделить длину программы от времени её исполнения. Короткая программа может вычислять результат чрезвычайно долго. И наоборот, большой файл весов может быстро выдавать ответы. Колмогоровская сложность измеряет длину описания, а не вычислительную стоимость.

Есть и ещё одна полезная неожиданность. Поток псевдослучайного генератора с коротким начальным значением (seed) имеет короткое алгоритмическое описание: генератор, начальное значение и длина потока. Но gzip может не сжать его вообще. Практический компрессор ищет ограниченный набор закономерностей; $K(x)$ оптимизируется по всем программам.

10.3. Несжимаемость, невычислимость и реальные компрессоры

Почему большинство строк нельзя заметно сжать

Рассмотрим все $2^n$ бинарных строк длины $n$. Программ длины меньше $n-c$ существует меньше $2^{n-c}$. Каждая завершившаяся программа печатает не более одной строки. Следовательно,

$$\#\left\{ x\in\{0,1\}^n: K(x)<n-c \right\} < 2^{n-c}.$$

Доля строк, которые можно сжать хотя бы на $c$ бит, меньше

$$\boxed{2^{-c}}.$$

Например, сжимаемых минимум на $20$ бит строк среди всех строк фиксированной длины меньше одной миллионной доли. Структурированные объекты занимают очень малую часть пространства всех возможных битовых последовательностей.

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

Почему идеальный счёт нельзя вычислить

Предположим, что существует алгоритм, точно вычисляющий $K(x)$. Тогда по числу $m$ можно перебрать строки и найти первую строку $x_m$, для которой

$$K(x_m)>m.$$

Но программа «получи $m$, найди первую такую строку и напечатай её» имеет длину

$$K(m)+O(1)=O(\log m),$$

что для большого $m$ намного меньше $m$. Получается короткое описание объекта, который по построению не должен иметь короткого описания. Противоречие.

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

$$\boxed{K(x)\text{ невычислима}.}$$

При этом $K(x)$ полувычислима сверху. Можно параллельно запускать всё больше программ, и всякий раз, когда находится более короткая программа для $x$, улучшать текущую верхнюю оценку. Нельзя только узнать, что найденная программа уже кратчайшая: некоторые ещё более короткие кандидаты могут остановиться через неизвестно сколько времени.

Невычислимость здесь не техническая неприятность, которую исправит более быстрый процессор. Она является частью самой конструкции.

Что дают gzip, zstd и LZMA

Пусть конкретный компрессор выдаёт поток $C(x)$, а фиксированный декомпрессор без потерь восстанавливает $x$. Тогда программа «запусти этот декомпрессор на $C(x)$» даёт

$$\boxed{ K(x) \le |C(x)|+c_C },$$

где $c_C$ оплачивает декомпрессор, формат и соглашения о входе.

Значит, реальный компрессор даёт вычислимую верхнюю границу на $K(x)$. Но он не даёт известной гарантии близости к идеалу.

Если файл плохо сжимается, возможны разные причины:

1. объект действительно близок к алгоритмически несжимаемому;
2. его закономерность не входит в класс, который умеет находить компрессор;
3. файл слишком мал и служебные расходы доминируют;
4. формат или предобработка скрывают полезную структуру.

Полезная инженерная формулировка звучит так:

Компрессор — это исполнимая теория регулярности. Его длина кода показывает, какие закономерности умеет использовать именно эта теория.

Математическое замечание: случайность бесконечной последовательности

Для бесконечных последовательностей недостаточно проверить один длинный префикс. Случайность по Мартину-Лёфу требует прохождения всех эффективных статистических тестов нулевой меры. Теорема Левина—Шнорра связывает это определение с префиксной сложностью: бинарная последовательность $\omega$ случайна по Мартину-Лёфу тогда и только тогда, когда существует константа $c$, для которой

$$K(\omega_{1:n})\ge n-c$$

для всех $n$. В дальнейшем нам в основном понадобятся конечные объекты, но это показывает, что алгоритмическая случайность — не синоним «архиватор не нашёл повторов».

10.4. Связь с энтропией Шеннона

Шеннон и Колмогоров начинают с разных сторон.

• Шеннон фиксирует распределение $P$ и ищет среднюю длину кода.
• Колмогоров фиксирует объект $x$ и ищет кратчайшее исполнимое описание.

Тем не менее для вычислимого источника эти два счёта встречаются в среднем.

Пусть $P$ — вычислимое распределение на конечных строках, а $K(P)$ — длина программы, которая вычисляет его вероятности с нужной точностью. Тогда

$$\boxed{ H_2(P) \le \mathbb E_{X\sim P}[K(X)] \le H_2(P)+K(P)+O(1) }.$$

Нижняя граница

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

$$H_2(P) \le \mathbb E_P K(X).$$

Верхняя граница

Можно передать два объекта:

1. программу, описывающую распределение $P$;
2. код строки $x$ длиной примерно $-\log_2P(x)$ бит.

Отсюда

$$K(x) \le K(P)-\log_2P(x)+O(1).$$

После усреднения второй член превращается в энтропию.

Для i.i.d.-блока $X_{1:n}$ точнее написать

$$H_2(X_{1:n}) \le \mathbb E K(X_{1:n}) \le H_2(X_{1:n})+K(P)+K(n)+O(1).$$

Если источник фиксирован и $H_2(X_{1:n})=nH_2(X)$, то

$$\frac1n\mathbb E K(X_{1:n}) \longrightarrow H_2(X).$$

Стоимость описания источника и длины блока распределяется по всё большему числу символов и исчезает на один символ.

Вот точный мост между двумя теориями:

Энтропия — типичная средняя алгоритмическая сложность длинных сообщений из известного вычислимого источника; $K(x)$ позволяет обсуждать отдельный объект, когда источник не задан заранее.

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

10.5. Алгоритмическая вероятность и универсальное предсказание

Программы как гипотезы

Префиксность позволяет провести мысленный эксперимент: подбрасывать честную монету и читать получившиеся биты как программу. Программа длины $|p|$ получает вес

$$2^{-|p|}.$$

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

Для программ, которые печатают конечную строку $x$ и останавливаются, определим алгоритмическую вероятность

$$m_U(x) = \sum_{p:\,U(p)=x}2^{-|p|}.$$

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

$$\boxed{ -\log_2m_U(x) = K_U(x)+O(1) }.$$

Иначе говоря,

$$m_U(x)\asymp2^{-K_U(x)}.$$

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

Предсказание продолжения

Для последовательного предсказания удобнее взять универсальную монотонную машину, которая читает бесконечный поток честных случайных битов. Определим $M(x)$ как вероятность того, что её выход начинается с префикса $x$. Эквивалентно можно просуммировать веса минимальных входных префиксов, уже достаточных для печати $x$:

$$\boxed{ M(x) = \sum_{p:\,p\text{ минимален и }U(p)\sqsupseteq x} 2^{-|p|} }.$$

Знак $U(p)\sqsupseteq x$ означает, что выведенная строка начинается с $x$; требование минимальности не позволяет повторно считать все продолжения одного и того же входного префикса.

Это полумера (semimeasure): часть входной массы может соответствовать программам, которые остановились после $x$ или никогда не выдали следующий символ, поэтому

$$M(x) \ge M(x0)+M(x1).$$

Отношения $M(xa)/M(x)$ задают условные веса продолжений; при необходимости их нормируют, чтобы получить обычное распределение следующего символа.

Здесь есть техническое различие, которое полезно один раз назвать явно. Конечная алгоритмическая вероятность $m_U(x)$ связана с префиксной сложностью $K_U(x)$. Последовательная полумера $M(x)$ естественно связана с монотонной машиной и монотонной сложностью. Популярная формула «вероятность порядка $2^{-K}$» передаёт общую идею, но строгие теоремы требуют не смешивать варианты машин.

Универсальное доминирование

Пусть $\mu$ — вычислимая вероятностная модель источника. Универсальная полумера включает программу, вычисляющую $\mu$, поэтому существует константа, для которой

$$\boxed{ M(x) \ge 2^{-K(\mu)-O(1)}\mu(x) }$$

для каждого конечного префикса $x$.

Возьмём минус логарифм:

$$-\log_2M(x) \le -\log_2\mu(x)+K(\mu)+O(1).$$

Эту формулу удобно прочитать как счёт:

Универсальный предиктор платит за незнание вычислимого источника не линейно с длиной данных, а один раз — длиной описания источника, с точностью до константы.

Для последовательности условных предсказаний отношение правдоподобий раскладывается по времени. В ожидаемой форме суммарный условный KL-разрыв между истинным предиктором $\mu$ и нормированной версией универсального предиктора ограничен величиной порядка $K(\mu)$ бит. Поэтому для любого фиксированного вычислимого источника средняя избыточная логарифмическая потеря на шаг стремится к нулю.

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

Почему это не практический алгоритм

Чтобы точно вычислить $M(x)$, пришлось бы узнать, какие программы когда-нибудь напечатают нужный префикс. Это снова приводит к проблеме остановки. Универсальная полумера нижнеполувычислима, но невычислима как обычная функция.

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

Индукция Соломонова — не архитектура, которую можно просто реализовать. Это нормативный предел: как выглядело бы последовательное предсказание, если бы можно было байесовски усреднить все вычислимые объяснения с алгоритмическим приоритетом простых программ.

10.6. MDL в машинном обучении

Невычислимость $K(x)$ не отменяет идею короткого описания. Она меняет инженерную задачу: вместо неизвестного идеального языка мы проектируем конкретный код и сравниваем модели внутри него.

Принцип минимальной длины описания (Minimum Description Length, MDL) формулируется так:

Предпочитайте модель, которая даёт самое короткое полное описание данных.

Двухчастный код: модель и остаток

Для гипотезы $h$ и набора данных $D$ простейший счёт имеет вид

$$\boxed{ L(D,h) = L(h)+L(D\mid h) }.$$

Первый член оплачивает модель. Второй — то, что остаётся передать после её получения.

Пусть модель $A$ стоит $100$ бит и кодирует данные за $1200$ бит. Модель $B$ стоит $300$ бит, но уменьшает длину данных до $850$ бит. По одной функции потерь $B$ выигрывает на $350$ бит; после оплаты модели её общий счёт всё равно меньше:

$$L_A=1300, \qquad L_B=1150.$$

Если вероятностная модель задаёт $p_h(D)$ и используется согласованный энтропийный кодер, то

$$L(D\mid h) \approx -\log_2p_h(D).$$

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

Как код связан с априорным распределением и регуляризацией

Для дискретного класса моделей априорное распределение $\pi(h)$ задаёт префиксные длины

$$L(h)=-\log_2\pi(h).$$

Тогда минимизация

$$-\log p_h(D)-\log\pi(h)$$

совпадает с MAP-выбором модели с точностью до основания логарифма.

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

Отсюда следует аккуратное чтение регуляризации. Гауссовское априорное распределение в фиксированной евклидовой параметризации приводит к квадратичному MAP-штрафу. Это полезная связь, но не доказательство того, что любой weight decay является канонической длиной описания нейросети. Код должен быть определён, а не подразумеваться.

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

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

1. Первые метки отправляются простым базовым кодом.
2. Обе стороны обучают модель на уже переданных примерах.
3. Следующий блок кодируется вероятностями этой модели.
4. После его получения модель переобучается, и процесс повторяется.

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

$$\boxed{ L_{\mathrm{preq}} = L(y_{1:n_0}) + \sum_j - \log_2 q_{\theta(D_{<j})} (y_{B_j}\mid x_{B_j}) }.$$

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

Именно так работает MDL-анализ представлений (MDL probing). Вопрос «можно ли извлечь свойство мощным классификатором?» заменяется вопросом «сколько бит нужно, чтобы передать метки, используя это представление и заранее зафиксированный протокол обучения?». Работа Voita и Titov рассматривает онлайн- и вариационные коды как практические способы оценить этот счёт.

Что означает результат MDL

MDL не устраняет моделирующие решения; оно заставляет их записать. Сравнение зависит от:

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

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

10.7. Сходство через совместное сжатие

Если $x$ и $y$ разделяют структуру, знание одного должно сокращать описание другого. Условная сложность превращает эту мысль в расстояние.

Теоретическое нормализованное информационное расстояние (normalized information distance, NID) имеет вид

$$\operatorname{NID}(x,y) = \frac{ \max\{K(x\mid y),K(y\mid x)\} }{ \max\{K(x),K(y)\} }$$

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

Поскольку $K$ невычислима, на практике используют длины конкретного компрессора $C$:

$$\boxed{ \operatorname{NCD}_C(x,y) = \frac{ C(xy)-\min\{C(x),C(y)\} }{ \max\{C(x),C(y)\} } }.$$

Например, если

$$C(x)=1000, \qquad C(y)=900, \qquad C(xy)=1300$$

байт, то

$$\operatorname{NCD}_C(x,y) = \frac{1300-900}{1000} =0.4.$$

Идея понятна: после оплаты более короткого объекта совместное сообщение требует ещё сравнительно небольшого дополнения.

Реальный компрессор может быть чувствителен к порядку конкатенации, поэтому часто сравнивают $C(xy)$ и $C(yx)$ и берут минимум или среднее. Из-за заголовков и несовершенства компрессора практическая NCD может немного выходить за идеальный диапазон $[0,1]$.

Что именно видит NCD

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

Но практическая метрика наследует индуктивное смещение компрессора:

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

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

10.8. LLM и универсальное предсказание

LLM и предиктор Соломонова принадлежат одной карте: оба назначают вероятности продолжениям последовательности. Но они находятся на этой карте в очень разных точках.

Точная общая часть

Для фиксированных весов, токенизатора и контекста языковая модель задаёт вычислимое распределение

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

Если передать эти вероятности арифметическому или интервальному кодеру (range coder), получится обратимый компрессор. Поэтому

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

— точное операциональное утверждение. Работа Language Modeling Is Compression показывает, что большие предиктивные модели действительно можно оценивать как компрессоры разных типов данных; для самостоятельного архива, как мы обсуждали в M6, нужно дополнительно учитывать стоимость модели и протокола.

Концептуальная связь

Индукция Соломонова усредняет все вычислимые объяснения, взвешивая их по длине программы. LLM реализует одно большое конечное распределение, обученное на конечных данных конкретным алгоритмом оптимизации.

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

Это даёт полезную интерпретацию: контекст играет роль данных, а модельное предсказание — роль приближённого апостериорного предиктивного распределения (posterior predictive). Но область теоремы определяется устройством предобучающего распределения и класса задач.

Где заканчивается соответствие

Обычная LLM:

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

Поэтому наиболее точная формулировка такова:

LLM — вычислимый последовательный предиктор и потенциальный компрессор. Индукция Соломонова — невычислимый универсальный эталон, относительно которого можно обсуждать широту априорного распределения и адаптацию, но которому конкретная LLM не эквивалентна.

Эта граница не обесценивает сравнение. Она делает его полезным: мы видим точное общее ядро — вероятностное предсказание и кодирование — и отдельно перечисляем свойства, которых конечная обученная модель не получает автоматически.

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

10.9. Математическое углубление: AIXI

Предсказатель отвечает на вопрос «что произойдёт дальше?». Агенту нужно дополнительно решить, что сделать.

AIXI соединяет два компонента:

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

Схематически, после истории $h_{<t}$ агент выбирает

$$a_t \in \arg\max_a \mathbb E_\xi \left[ \sum_{k=t}^{\infty}\gamma_k r_k \middle| h_{<t},a_t=a \right],$$

где $\xi$ — универсальная смесь сред, а $\gamma_k$ задают горизонт или дисконтирование.

Что даёт эта конструкция

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

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

Поэтому AIXI полезна как нормативная схема универсального байесовского RL. Она показывает, как алгоритмическая вероятность могла бы войти не только в прогноз, но и в принятие решений.

Почему это не верхняя граница интеллекта

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

Некоторые классические свойства оптимальности также слабее, чем звучат вне контекста. В классе всех вычислимых сред каждая политика может оказаться Pareto-optimal в слишком широком смысле; самооптимизация возможна лишь для классов сред, допускающих самооптимизирующиеся политики. Leike и Hutter показывают, что неудачный выбор универсальной машины способен радикально изменить поведение агента.

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

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

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

Рассмотрим симметричную однобитную память, которая до стирания с равными вероятностями находится в состояниях $0$ и $1$. Операция erase переводит оба состояния в один стандартный ноль:

$$0\mapsto0, \qquad 1\mapsto0.$$

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

$$\boxed{ Q_{\min}=k_BT\ln2 }.$$

При $T\approx300\,\mathrm K$:

$$Q_{\min} \approx 2.87\times10^{-21}\ \mathrm J.$$

Ландауэр связал этот предел именно с логической необратимостью вычислительной операции. Эксперимент Bérut и соавторов реализовал однобитную память на коллоидной частице и показал приближение среднего тепловыделения к пределу при медленном стирании.

Эту формулу легко применить слишком прямолинейно. Нельзя оценить энергию одного токена LLM, просто умножив $k_BT\ln2$ на число FLOP. Для такого перехода пришлось бы определить:

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

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

Полезно держать четыре разных счёта отдельно:

• $K(x)$ — длина кратчайшей программы;
• вычислительная сложность — время и память алгоритма;
• предел Ландауэра — минимальная термодинамическая цена определённого стирания;
• энергопотребление ускорителя — свойство конкретной аппаратуры и нагрузки.

10.12. Ключевые выводы модуля

Алгоритмическая теория информации меняет исходный вопрос. Вместо «сколько бит в среднем требует источник?» она спрашивает:

Какова длина кратчайшего эффективного описания этого объекта?

Основной объект модуля — префиксная колмогоровская сложность

$$K(x) = \text{длина кратчайшей самоделимитирующейся программы для }x.$$

Из неё складывается единая линия.

1. Большинство длинных строк несжимаемо. Коротких программ просто недостаточно, чтобы описать заметную долю всех строк.
2. Идеальная сложность невычислима. Реальные компрессоры дают исполнимые верхние границы и отражают собственный класс закономерностей.
3. Шеннон и Колмогоров согласуются в среднем. Для вычислимого источника ожидаемая $K$ равна энтропийному счёту с добавочной стоимостью описания источника.
4. Алгоритмическая вероятность превращает краткость в априорный вес. Универсальная смесь один раз оплачивает описание вычислимого источника и затем конкурирует с ним по последовательной логарифмической потере.
5. MDL делает идею практической. Код «модель + данные при модели» позволяет сравнивать подгонку, сложность и скорость обучения в битах.
6. Совместное сжатие даёт меру сходства. NCD полезна тогда, когда выбранный компрессор видит общую структуру объектов.
7. LLM находится на той же карте предсказания и сжатия, но не является индукцией Соломонова. Точное общее ядро — условные вероятности и энтропийное кодирование; универсальные гарантии не переносятся автоматически.

Самая важная инженерная привычка этого модуля:

Когда объект называют «простым» или «сложным», уточняйте язык описания, декодер, точность, вычислительные ресурсы и включённые расходы.

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

1. A. N. Kolmogorov, «Three Approaches to the Quantitative Definition of Information», 1965.
2. R. J. Solomonoff, «A Formal Theory of Inductive Inference, Part I» и Part II, 1964.
3. M. Li, P. Vitányi, «An Introduction to Kolmogorov Complexity and Its Applications», 4-е изд., 2019.
4. J. Rissanen, «Modeling by Shortest Data Description», 1978; P. Grünwald, «The Minimum Description Length Principle», 2007.
5. E. Voita, I. Titov, «Information-Theoretic Probing with Minimum Description Length», 2020.
6. R. Cilibrasi, P. Vitányi, «Clustering by Compression», 2003/2005.
7. M. Hutter, «Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability», 2005.
8. J. Leike, M. Hutter, «Bad Universal Priors and Notions of Optimality», 2015; «On the Computability of AIXI», 2015/2018.
9. G. Delétang et al., «Language Modeling Is Compression», 2023/2024.
10. S. M. Xie et al., «An Explanation of In-context Learning as Implicit Bayesian Inference», 2021/2022.
11. R. Landauer, «Irreversibility and Heat Generation in the Computing Process», 1961; A. Bérut et al., «Experimental Verification of Landauer's Principle Linking Information and Thermodynamics», 2012.