Некоторое время назад я писал о языковом моделировании без нейронных сетей, где я генерировал Шекспира с использованием неограниченной n-gram модели: без весов, без обучения, только подсчёт. К счастью, я наткнулся на статью 'Language Modeling is Compression', в которой упоминалось эквивалентность сжатия и предсказания: каждая модель предсказания по своей сути является компрессором, и все алгоритмы сжатия являются моделями предсказания. Это привело к естественному вопросу: может ли gzip выполнять языковое моделирование? Без нейронной сети, без обученных параметров, ничего. Просто компрессор, который поставляется с вашей операционной системой. Вы готовите его с корпусом, подаёте обычный текстовый промпт, и он продолжает этот промпт, ища байтовые последовательности, которые сжимаются лучше всего. Вот некоторые реальные, неизменённые выходные данные после подготовки его на tiny Shakespeare:

gzipt --corpus data/tinyshakespeare.txt --prompt $'MENENIUS:\n' --length 200

MENENIUS:'Though all at once canq MARCIUS: Pray now, nocamest thou to a morsel .LARTIUS: Hence, and I' the end admire, where Gagain; and after it ag .Оказывается, в некотором роде? Это не совсем связный текст, но он явно что-то знает о тексте. Значительно больше, чем я ожидал от gzip.

Тогда как компрессор может генерировать это? Сжатие — это предсказание. Подумайте, что делает компрессор. Он тратит мало байт на данные, которые он 'ожидает', и много байт на данные, которых он не ожидает. Если я дам вам файл, состоящий из буквы A, повторённой миллион раз, вы сможете описать его одним предложением. Миллион случайных байтов, с другой стороны, не имеют структуры для эксплуатации и почти не сжимаются. Это не совпадение; это основа теории информации. Количество битов, необходимое для кодирования символа, равно $-\log_2 p$, где $p$ — вероятность, которую модель присваивает ему. Высокая вероятность означает мало битов. Следовательно, любой компрессор по своей сути скрывает внутри себя модель вероятности, независимо от того, записал ли её кто-то или нет. gzip использует DEFLATE, который сжимает следующие байты, ища совпадения с недавним текстом в скользящем окне размером 32 KiB. Если продолжение отражает что-то уже присутствующее в окне, DEFLATE кодирует его как дешёвую обратную ссылку вместо буквальных байтов. Таким образом: продолжение, которое gzip 'ожидал', потому что оно отражает текст, уже присутствующий в его окне, сжимается почти до нуля. Это даёт нам оценку. Если у меня есть некоторый контекст и я хочу знать, насколько хорош кандидат-продолжение, я просто измеряю: score(кандидат) = len(gzip(контекст + кандидат)). Чем меньше сжатая длина, тем более 'предсказан' кандидат. Для подготовки модели я включаю корпус в окно gzip. Любое продолжение, похожее на корпус, сжимается мало, и любое продолжение, не похожее на корпус, сжимается много. Генерация через поиск в луче. Оценка — одно дело; генерация — другое. Наивный подход выбора следующего отдельного байта, который лучше всего сжимается, терпит неудачу плохо, и по тонкой причине: gzip выдаёт только целочисленную длину в байтах (без дробей). Добавление одного байта часто не меняет сжатую длину вообще, поэтому многие кандидаты оказываются вничью, и сигнал теряется в шуме квантования. Решение — смотреть вперёд на весь интервал перед фиксацией. gzipt выполняет поиск в луче по последовательностям байтов. На каждом шаге текущий контекст: окно корпуса + недавний хвост (промпт + сгенерированные байты). Затем gzipt пробует возможные следующие байты. Каждый кандидат-продолжение оценивается сжатием контекст + кандидат и проверкой, сколько байт занимает сжатый результат. Цикл таков:

Промпт. Начните с промпта пользователя как начального текста для продолжения. Нет начального токена; байты промпта просто являются частью контекста, который видит gzip.

Контекст. Покажите gzip окно корпуса плюс недавний хвост промпта/сгенерированного текста.

Поиск. Сохраняйте beam_width наиболее сжимаемых частичных продолжений. Расширяйте каждое на каждый байт, встречающийся в корпусе, оценивайте все по сжатой длине, и снова сокращайте до лучших beam_width.

Повторяйте для байтов horizon.

Фиксация. Возьмите наиболее сжимаемое полное продолжение (или выберите среди финалистов, если температура положительна), добавьте его и продолжайте.

...

FAQ Q: Можно ли использовать gzip как языковую модель?

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