Чи може gzip бути мовною моделлю? Генератор тексту на основі DEFLATE

Блоговий пост, опублікований на nathan.rs, ставить питання, яке звучить як жарт: чи може gzip — інструмент стиснення, що постачається майже з кожною операційною системою — працювати як мовна модель? Автор зробив gzipt: невеликий експеримент, який генерує текст, використовуючи лише компресор, без нейронної мережі та без вивчених параметрів.

Стиснення — це передбачення

Відправна точка — стаття «Language Modeling is Compression» (arXiv 2309.10668), яка формулює еквівалентність стиснення й передбачення: кожна модель передбачення за своєю суттю є компресором, а кожен алгоритм стиснення — моделлю передбачення. Інтуїція походить з теорії інформації: для кодування символу потрібно −log₂ p біт, де p — імовірність, яку модель йому приписує. Висока ймовірність означає короткий код.

gzip використовує алгоритм DEFLATE і працює з ковзним вікном у 32 КіБ. Якщо наступні байти повторюють те, що вже є у вікні, DEFLATE кодує їх дешевим зворотним посиланням. Звідси й оцінка: стиснути контекст разом із кандидатом-продовженням і виміряти довжину результату. Чим коротший результат, тим «передбачуванішим» є кандидат. Попередня подача корпусу поміщає його у вікно gzip.

Від оцінки до генерації

Оцінювання — ще не генерація. Вибір одного наступного байта, що стискається найкраще, працює погано: gzip повертає цілу кількість байтів, без дробів. Додавання одного байта часто взагалі не змінює довжину, тож багато кандидатів отримують однакову оцінку, і сигнал тоне в шумі квантування. gzipt долає це променевим пошуком (beam search): він зберігає beam_width найбільш стисливих часткових продовжень, розширює кожне кожним байтом, що трапляється в корпусі, оцінює результати за стиснутою довжиною і знову відсікає. Це повторюється на горизонті байтів, перш ніж зафіксувати найкращий фрагмент.

Важлива деталь: у контексті оцінювання залишаються лише останні байти згенерованого тексту. DEFLATE кодує близькі збіги дешевше за далекі, тож модель, яка бачила б усю історію, найдешевше потрапляла б у дослівні цикли, повторюючи щойно згенероване.

Що виходить на практиці

Після попередньої подачі корпусу tiny Shakespeare і підказки "MENENIUS:" інструмент повернув рядки, приписані Мененію, Марцію та Ларцію, — не зв'язний текст, але вплив джерела очевидний. Код — один файл чистим Python зі стандартної бібліотеки (лише zlib). У виносках автор зазначає, що автори статті пробували подібне й отримали слабкі результати, а додавання променевого пошуку суттєво покращило якість генерації.

Висновок вузький, але реальний: компресор загального призначення може нести корисну неявну модель тексту. До нейронної мовної моделі йому далеко, і автор це визнає. Проте це чиста демонстрація того, що передбачення і стиснення — одна задача, побачена з двох боків.