Может ли gzip быть языковой моделью?

Автор задался вопросом, который на первый взгляд кажется абсурдным: может ли gzip — тот самый архиватор, что уже установлен в вашей системе, — работать как языковая модель? Никаких нейросетей, никаких обученных весов, только сжатие. Толчком послужила статья «Language Modeling is Compression» с её ключевой мыслью: всякая модель предсказания есть по сути компрессор, а всякий алгоритм сжатия — модель предсказания.

Сжатие — это предсказание

Логика проста. Компрессор тратит мало байтов на то, что «ожидает», и много — на то, чего не ждёт. Миллион повторяющихся букв A описывается одной фразой, а миллион случайных байтов почти не сжимается. Это не совпадение, а сердцевина теории информации: число битов для кодирования символа равно \(-\log_2 p\), где \(p\) — приписанная ему вероятность. Значит, внутри любого компрессора уже спрятана вероятностная модель, даже если её никто не записывал явно.

gzip использует алгоритм DEFLATE, который ищет совпадения с недавним текстом в скользящем окне размером 32 КиБ. Если продолжение повторяет то, что уже есть в окне, оно кодируется дешёвой обратной ссылкой вместо самих байтов. Отсюда и мера качества кандидата: длина сжатого context + candidate. Чем короче результат, тем лучше «предсказано» продолжение. Достаточно поместить в окно корпус текстов — и всё похожее на него станет сжиматься коротко.

Генерация через лучевой поиск

Оценивать — одно, генерировать — другое. Наивный выбор одного лучшего следующего байта проваливается: gzip выдаёт лишь целую длину в байтах, без дробей. Добавление одного символа часто вовсе не меняет длину, и сигнал тонет в шуме квантования. Решение — заглядывать вперёд на целый отрезок. Программа gzipt ведёт лучевой поиск по последовательностям байтов, продлевая лучшие варианты и отсекая слабые.

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

Результат, полученный после «затравки» на маленьком корпусе Шекспира, не назвать связным текстом, но он явно что-то знает об источнике — куда больше, чем автор ожидал от архиватора. Оригинальная статья тоже пробовала этот приём, но добавление лучевого поиска заметно улучшило качество. Весь код — один файл на чистом стандартном Python (только zlib), а название GziPT, по признанию автора, оказалось слишком хорошим, чтобы от него отказаться.

Источник: Hacker News