Недавно я читала материалы о сжатии данных, и меня внезапно озарила безумная мысль: по сути своей, алгоритмы сжатия и LLM предназначены для решения одной и той же задачи.

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

Как устроено сжатие

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

Вот пример минификации:

Исходник, состоящий из 156 символов

// Sum every number in the list
function sumNumbers(numbers) {
  let total = 0;
  for (const number of numbers) {
    total += number;
  }
  return total;
}

минифицирован до 62 (на 60%) благодаря удалению комментария, укорачиванию имён переменных до однобуквенных и вырезанию пробелов, фигурных скобок и точек с запятыми.

function sumNumbers(n){let t=0;for(const r of n)t+=r;return t}

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

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

Возьмём для примера строку «AAAAAAAAABBBBCCDAAADDDDDDDDD», состоящую из девяти A, четырёх B, двух C, одной D, трёх A и девяти D: в ней есть большая избыточность. Можно закодировать эту строку в более короткую, указав количество повторений каждого символа по порядку:

Заменив каждое повторение соответствующим символом и количеством повторений, мы получим A9B4C2D1A3D9 — 12 символов, 96 бит: уменьшение на 57%.

При использовании стандартной 8-битной кодировки ASCII для исходной строки требуется 224 бита, а для сжатой строки («A9B4C2D1A3D9») всего 96. Неплохо!

Приведённая выше методика — лишь один из способов сжатия (называемый кодированием длин серий/run-length encoding), но на этом можно не останавливаться. Используемые в реальной жизни алгоритмы сжатия наподобие gzip, Brotli и так далее применяют множество разных способов сжатия данных. Давайте рассмотрим их.

Анатомия алгоритма сжатия

Современные инструменты сжатия данных можно приблизительно разбить на три части: преобразования (transform), модели (model) и энтропийные кодировщики (entropy coder). Я говорю о них так, как будто между ними есть чёткие границы, но на самом деле они могут быть немного размытыми; к тому же эти части редко применяются по отдельности.

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

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

Вот пример с уже знакомой нам строкой:

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

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

Но будем откровенны: пока всё это довольно абстрактно. Что энтропийный кодировщик делает со всеми этими вероятностями? Как они помогают ему в сжатии данных?

Ужимание данных при помощи вероятностей

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

К тому же оно попросту красиво.

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

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

Допустим, мы хотим сжать строку «ABABAAC». Можно найти вероятности каждого символа, разделив общее количество каждого на общую длину строки, то есть на 7:

Можно представить эти вероятности в интервале от 0 до 1.

Разделим интервал от 0 до 1 на секции для каждого символа; ширина каждой секции соответствует вероятности символа; все секции упорядочены по уменьшению ширины:

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

Для каждого символа строки, начиная с «A», мы уменьшаем интервал так, чтобы уместиться внутри секции этого символа. Важно то, что мы продолжаем делить этот новый интервал в соответствии с теми же самыми вероятностями, но теперь у нас есть новые интервалы меньшего размера.

Когда у нас закончились символы, остался крошечный интервал: [0.38730, 0.38855).

Разные скобки использованы намеренно. Квадратные скобки [ ] означают, что конечная точка входит в интервал, круглые ( ) означают, что она не входит в интервал. То есть [0, 1) — это «все числа от 0 до 1, включая 0, но исключая 1».

Окончательное число, описывающее весь датасет, может быть любым числом в этом интервале, и в идеале это должно быть число, требующее наименьшего количества бит. Вы можете вычислить его самостоятельно, но я не буду усложнять и сразу покажу ответ: 0.3876953125. Давайте сравним: для нашей исходной строки «ABABAAC» в сырой 8-битной кодировке требуется ASCII 56 бит, а для нашего окончательного числа нужно всего 10.

Наше окончательное число хранится не с плавающей запятой — это двоичная дробь. Числа с плавающей запятой тоже относятся к двоичным дробям, но они имеют фиксированную длину, поэтому на них приходится тратить 32 или 64 бита, даже если они не требуются. На нашу дробь нужно только 10.

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

Распаковка арифметических кодов

Наряду с магическим числом наш распаковщик получает те же вероятности, которые мы использовали для его сжатия, поэтому он может воссоздать исходный интервал [0, 1). Для декодирования исходного сообщения он находит, в какую секцию попадает наше магическое число, и записывает этот символ. Затем он уменьшает интервал, чтобы уместить его в этой секции, и повторяет весь процесс заново.

Посмотрите сами:

Здорово, правда?

Мы увидели, как энтропийный кодировщик способен направлять наши данные при помощи множества вероятностей. Но как бы ни было замечательно арифметическое кодирование (вам ведь оно тоже понравилось, правда?), основную часть работы выполняет модель. Напомню, что сжатие любит избыточность. Что же произойдёт, если повторений символов будет больше?

Как вероятности влияют на сжатие

Вот новая строка, в которой преобладает буква A с вероятностью 0.833.

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

Первую строку нам удалось сжать в среднем в 1,38 бита/символ, а более длинную строку мы сжали в 0,82 бита/символ. Чем сильнее перекос данных (то есть чем выше вероятность некоторых символов), тем лучше коэффициент сжатия.

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

«Постойте, разве энтропия — это не понятие из физики?», — спросите вы. Всё верно! Но мы говорим об энтропии Шэннона, связанной со сжатием данных (в области теории информации). Её математическая формула почти совпадает с формулой энтропии Гиббса в термодинамике. Ну разве не круто?

Энтропия

Рассмотрим следующее предложение:

«Yesterday I saw an animal when I was walking downtown. It was a _____.» («Прогуливаясь вчера по городу, я увидела животное. Это был(-а) _____.»)

Как думаете, сколько догадок вам понадобится, чтобы заполнить пробел? Если это было простое животное наподобие птицы (bird), то вы можете угадать его с первой попытки. Но что, если ответом был «медведь» (bear)? Наверно, вам бы понадобилось довольно много попыток.

Допустим, вот все возможные варианты ответов и их вероятности, записанные в виде дробей:

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

Обратите внимание, что вероятность каждого последующего животного вдвое меньше, чем предыдущего, за исключением лисы (fox) и медведя (bear) (это вероятности, поэтому их сумма должна быть равна 1). Если бы мы гадали каждого животного по порядку, начиная от самого вероятного до наименее вероятного, то каждый раз бы имели вероятность 50/50 оказаться правыми. Следовательно, можно определить количество догадок, которые потребуются для угадывания животного (в среднем) при помощи дерева решений «да-нет». Мы начинаем с наиболее вероятного животного наверху и постепенно опускаемся вниз:

Давайте вернёмся к сжатию. Символы с наибольшими вероятностями повышают сжатие, и в дереве решений мы видим тот же паттерн: чем вероятнее животное, тем меньше догадок требуется. Если считать животных символами, а «да» и «нет» заменить на единицы и нули, то количество догадок становится точным количеством бит, необходимым для описания каждого символа. Если записать единицы и нули, необходимые для достижения каждого животного, то мы увидим, что чем распространённее животное, тем короче его «кодовое слово» (уникальная последовательность бит), а чем оно реже, тем кодовое слово длиннее.

На самом деле, такое присвоение кодовых слов символам — это ещё один тип энтропийного кодировщика, называемый кодом Хаффмана; он используется в таких популярных инструментах, как gzip и Brotli. Вместо кодирования данных в одно число, как при арифметическом кодировании, методика Хаффмана создаёт для описания каждого символа кодовые слова.

Но возникает проблема: что случится, если наши вероятности не поделены ровно пополам? Если cat имеет вероятность 0.3973, то вероятность правильности ответа cat или не cat больше не равна 50/50. Каждый путь по дереву состоит из целого количества «догадок», поэтому мы вынуждены округлять, а из-за округления придётся платить за биты, которые нам не нужны. Как узнать абсолютно наименьшее количество бит, требуемое для описания конкретного символа?

Оказывается, это можно вычислить при помощи математики:

Напомню, что логарифм — это операция, обратная возведению в степень. Например, 2⁴ задаёт вопрос «Чему равно 2 в степени 4?». log₂(16) задаёт вопрос «2 в какой степени равно 16?».

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

Значение среднего −log₂(вероятность) всех наших символов даст нам энтропию.

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

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

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

Но как нам этого добиться?

Важность контекста

Пока мы работали только с очень простым типом модели, которому важна только частотность символов. count / total_symbols = вероятность.

Но на вероятность символа может сильно влиять контекст. Например, во всём английском языке вероятность буквы U примерно равна 0.028. Однако, если ей предшествует Q, вероятность подскакивает примерно до 0.999.

Ого!

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

• U: −log₂(0.028) ≈ 5158 бит.

• U (которой предшествует Q): −log₂(0.999) ≈ 0,001 бита.

Использование единого контекста для определения вероятности символа называется моделью первого порядка. Она отвечает на вопрос «Какова вероятность символа в конкретном контексте?». При первом порядке в качестве контекста используется предыдущий символ, но можно расширить эту систему до второго, третьего, четвёртого и так далее порядка, которые будут учитывать предыдущие N символов.

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

Давайте посмотрим, что происходит в случае применения арифметического кодирования к строке «TO BE OR NOT TO BE» с использованием модели первого порядка. Обратите внимание, что с каждым кодируемым символом новые интервалы содержат разное множество вероятностей.

Хорошо, но насколько использование моделей N-ного порядка влияет на сжатие?

Взгляните:

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

А вы знаете, что ещё очень хорошо справляется с предсказанием?

Моделирование языка и сжатие

Если бы я сказала, что сферы LLM и сжатия частично пересекаются, то это было бы сильным преуменьшением. В 2023 году Google DeepMind даже выпустила статью, в которой говорится, что моделирование языка и сжатие — это два взгляда на одну и ту же задачу.

Подобное заявление может показаться странным. В конце концов, при работе с LLM мы обычно вводим промпт, а ИИ-чатбот даёт нам ответ на него. В чём это похоже на сжатие?

Да, вроде бы непохоже, но не торопитесь с выводами.

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

Рассмотрим пример:

Заодно давайте разберёмся с терминологией. Строго говоря, LLM возвращают не слова, а токены: числа, обозначающие слова или части слов. Токены — это вокабуляр, который используют LLM для парсинга контекста и генерации ответов.

А теперь задумаемся: хотя энтропийные кодировщики создают окончательный сырой поток данных, в них ничто нельзя изменить для получения более качественных результатов. Они неизменны, детерминированы и не создают потерь. Если нужно повысить сжатие, то необходимо изменить модель так, чтобы получить повышенные вероятности на символ. Иными словами, нам нужен более качественный предсказатель. А с предсказаниями лучше всех справляются LLM:

Использование LLM для сжатия похоже на их использование для генерации текста, только в первом случае мы не выбираем следующее слово. Почему? Потому что мы не стремимся сгенерировать новый текст. Нам уже известно следующее слово! Вот, как это работает: зная предыдущие токены (то есть на основании контекста), модель говорит: «Вот токены, которые, по моему мнению, идут дальше, и их вероятности». Затем она смотрит на реальный следующий символ. Та вероятность, которую назначила модель, определяет затраты на него в битах. Если модель хорошо обучена, то токен, вероятность которого она считает наибольшей, будет реальным следующим символом.

При просмотре этого видео обратите внимание, что общее количество бит (в самом верху) увеличивается на основании вероятности каждого закодированного токена. Количество бит, необходимых для описания каждого токена, определяется как −log₂(вероятность).

Если же модель плохо обучена, то за это приходится расплачиваться. Например, если наш контекст равен «The rain in», то плохо обученная модель могла бы присвоить токену «Bermuda» вероятность 0.82, но реальное следующее слово — это «Spain», которому она присвоила вероятность 0.02. Напомню, что чем ниже вероятности, тем больше бит им требуется, поэтому модель наказывается за неверную догадку:

Эти различия мы можем наблюдать и при арифметическом кодировании. Вспомним, что при кодировании каждого символа у нас остаётся всё меньший и меньший интервал. Кодирование символов с малыми вероятностями (как когда модель делает плохие догадки) делает интервалы ещё меньше. Окончательное число должно умещаться внутри этих интервалов, и чем меньше интервал, тем больше точности ему требуется. Больше точность = больше разрядов = больше бит.

Примечание: на самом деле, итоговое число округляется вверх, потому что компьютеры не могут хранить «частичные биты».

Тем не менее, даже древние LLM, считающиеся по современным стандартам ужасными, могут обеспечивать достаточно впечатляющие коэффициенты сжатия. Вот сравнение модели первого порядка с GPT-2 при арифметическом кодировании знаменитой цитаты из Чарльза Диккенса:

Но если LLM так замечательно сжимают данные, то почему мы не используем их везде?

Сжатие в реальном мире

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

Возьмём для примера ответы HTTP: когда браузер запрашивает веб-страницу, он отправляет заголовок вида Accept-Encoding: gzip, br, сообщающий серверу, какие форматы сжатия он может декодировать (gzip, Brotli и т.д.). Перед отправкой ответа сервер выбирает один из них для сжатия.

Допустим, сервер использует для сжатия ответа gzip. Когда браузер получает этот ответ, то при помощи маленькой встроенной модели он декодирует сжатый gzip битовый поток в HTML, CSS и JavaScript. Дополнительно затрачиваемые ресурсы очень малы. Если же мы использовали бы для этой работы LLM, то и в браузере, и на сервере требовались бы многогигабайтные копии LLM. Это уже высокая цена за хорошее сжатие, а ведь мы ещё не запускали модель. Для сжатия (и распаковки) данных потребовалась бы куча ресурсов, а скорость загрузки страниц деградировала бы до неприемлемой. Представьте, что для сжатия и распаковки каждой таблицы стилей, скрипта и JSON необходимо было бы запускать LLM. Ужас.

Для задачи столь тривиальной, как сжатие HTTP-ответов, применение LLM комически несоразмерно: учитывая размер модели, мы добавляем гигабайты для экономии нескольких килобайт. Но даже если бы мы хотели сжимать датасеты, огромные даже по сравнению с размером LLM, потребовался бы астрономический объём вычислительных ресурсов.

Две стороны одной монеты

На данный момент сжатие данных до уровня их энтропии — уже решённая задача. Арифметическое кодирование, разработанное в конце 1970-х, превышающее теоретический предел всего на пару бит, и современные энтропийные кодировщики конкурируют по скорости и занимаемой памяти, а не по коэффициенту сжатия.

Нерешённой ещё задачей остаётся то, насколько малой мы можем сделать энтропию. Более совершенные модели (предсказатели) помогают нам снизить этот показатель. С этим замечательно справляются LLM (если не учитывать затраты на дополнительные ресурсы), но очень интересно то, что они обучаются для минимизации именно этого числа бит на символ. В терминологии LLM оно называется кросс-энтропией, но в основе её лежит та же формула. То есть в сфере сжатия энтропия определяет, насколько сильно мы можем уменьшить данные, а в моделировании языка это число, которое мы уменьшаем, чтобы модель лучше справлялась с предсказаниями. Если вам любопытны подробности, то рекомендую изучить статью Криса Олаха.

Однако в конечном итоге, и LLM, и алгоритмы сжатия — это предсказатели. Это две реализации одной и той же математической идеи. Сжатие — это предсказание, а LLM — это алгоритмы сжатия.