В лекции курса EE274 Стэнфордского университета подробно рассматривается эволюция методов сжатия данных от классических марковских моделей до современных нейросетей. Преподаватели демонстрируют, как глубокая связь между машинным обучением и теорией информации позволяет использовать большие языковые модели в качестве сверхэффективных архиваторов. Главный акцент сделан на контекстно-зависимом арифметическом кодировании и парадоксах сжатия с помощью LLM, таких как Llama.
🔄 От марковских цепей к практическому сжатию 1:00
В теории информации фундаментальное значение имеет понятие стационарных процессов и цепей Маркова . Для цепи Маркова $k$-го порядка статистика следующего символа полностью определяется предыдущими $k$ символами. При этом в первом порядке текущий шаг зависит исключительно от непосредственно предшествующего.
Понимание этих структур позволяет подойти к расчету условной энтропии и предела скорости создания энтропии (entropy rate) . Этот предел показывает, сколько неопределенности (в битах) несет в себе каждый новый символ стационарного процесса, если нам известна вся его предыдущая история.
В рамках лекционного разбора домашнего задания слушателям предлагается проанализировать простую марковскую цепь . Начальный символ $U_1$ распределен по закону Бернулли с вероятностью $0.5$ (что дает энтропию в $1$ бит) . Однако последующие символы жестко зависят от предыдущих: если предыдущий символ равен $0$, то следующий гарантированно будет $1$. Если же равен $1$, то следующий с равной вероятностью окажется $0$ или $1$.
В ходе разбора задачи лектор обращает внимание на критически важный аспект стационарности:
- Марковская цепь не всегда является стационарной по определению .
- В данном примере энтропия первого символа $H(U_1)$ составляет $1$ бит, а энтропия второго $H(U_2)$ снижается примерно до $0.81$ бита . Изменение энтропии во времени однозначно доказывает нестационарность процесса.
- Стационарной данная цепь становится только в том случае, если изначально запустить ее с так называемым стационарным распределением . Для данной структуры такое распределение вероятностей начального состояния дает энтропию в $2/3$ бита .
Для сжатия подобных марковских источников можно использовать два подхода. Первый — блочное кодирование, когда мы сжимаем группы по $n$ символов с помощью кодов Хаффмана или арифметического кодирования . Однако с ростом $n$ этот метод быстро упирается в вычислительную сложность . Более того, блочное кодирование не учитывает корреляцию на границах блоков (например, между вторым и третьим символом), что делает его субэптимальным .
Второй, более элегантный путь — последовательное кодирование с учетом меняющегося контекста.
📐 Контекстно-зависимое арифметическое кодирование 15:39
Классическое арифметическое кодирование работает с числовыми интервалами . В случае независимых и одинаково распределенных (IID) символов мы берем единичный интервал $[0, 1)$ и делим его на подотрезки, пропорциональные безусловным вероятностям появления символов . Выбрав отрезок, соответствующий реальному символу, мы повторяем процедуру деления для следующего символа. В итоге длина финального интервала равна произведению вероятностей всех встреченных символов .
Контекстно-зависимое арифметическое кодирование (Context-based Arithmetic Coding) кардинально меняет этот принцип . Вместо использования фиксированных вероятностей на каждом шаге интервал делится в соответствии с условной вероятностью текущего символа, рассчитанной на основе уже известного «контекста» (предыдущих символов) .
Связь между качеством предсказания и сжатием описывается простой цепочкой рассуждений лектора:
- Точность предсказания. Чем точнее модель способна предсказать следующий символ на основе контекста, тем ближе к единице будет его условная вероятность .
- Размер интервала. Высокая вероятность символа означает, что при кодировании ему будет выделен максимально широкий подотрезок внутри текущего интервала .
- Длина кода. Поскольку длина кода в битах обратно пропорциональна размеру финального интервала ($\log_2(1/P)$), широкие интервалы обеспечивают минимальную длину результирующего битового потока .
Таким образом, задача эффективного сжатия данных напрямую сводится к построению качественной предсказательной модели .
🧠 Как большие языковые модели сжимают текст 27:05
В качестве яркой демонстрации этого принципа лектор приводит эксперимент с современной большой языковой моделью Llama от компании Meta . Модели передавали последовательно увеличивающийся контекст и анализировали распределение вероятностей для следующего слова (токена):
- При подаче одиночного слова «than» модель выдавала размытое распределение с наиболее вероятным продолжением «thanks» (около 18% вероятности) .
- Контекст «louder than» сдвигал вероятности, выводя на первое место токен «words» с вероятностью 30.4% .
- Фраза «speak louder than» поднимала вероятность слова «words» почти до 50% . При кодировании этого слова с таким контекстом пришлось бы заплатить всего около $1$ бита .
- Наконец, при полном контексте известной поговорки «Actions speak louder than» модель прогнозировала слово «words» с абсолютной уверенностью в 96.5% . Для кодирования этого слова в данном случае потребуется значительно меньше $1$ бита.
Этот пример наглядно иллюстрирует, что увеличение длины контекста в хорошей предсказательной модели ведет к экспоненциальному росту точности и, как следствие, к радикальному сокращению объема сжатых данных .
Математически эта связь безупречна. Функция потерь, используемая для обучения практически всех современных языковых моделей — это кросс-энтропия (или log loss) . Она вычисляется по той же самой формуле $\log_2(1/P)$ . По мнению лектора, предсказание в машинном обучении и сжатие в теории информации — это буквально одна и та же задача, решаемая через один и тот же математический аппарат . Любой хороший классификатор или генеративная модель потенциально является отличным архиватором .
⚖️ Адаптивное vs. Двухпроходное сжатие: Проблема синхронизации 35:06
Если у нас нет готовой модели для поступающих данных, существует два пути решения :
- Двухпроходный метод (Two-pass). Мы сначала анализируем весь объем данных, строим под них оптимальную модель (например, на основе эмпирических частот), а затем кодируем данные . Главный минус — необходимость передавать саму модель вместе с архивом, что съедает часть выигрыша , а также невозможность потоковой обработки.
- Адаптивный метод (Adaptive). Модель строится и постоянно обновляется непосредственно в процессе чтения данных шаг за шагом . Нам не нужно хранить и передавать модель, так как декодер может воссоздать ее состояние самостоятельно .
При адаптивном подходе критически важна абсолютная синхронизация состояний кодера и декодера . Декодер должен обновлять свою модель строго в той же последовательности и по тем же формулам, что и кодер . В противном случае малейшее расхождение в расчете вероятностей на любом шаге приведет к мгновенному и необратимому разрушению всего последующего потока данных .
Эта особенность создает колоссальные трудности при попытке использовать глубокие нейросети для адаптивного сжатия:
- Аппаратная недетерминированность. Современные ML-библиотеки часто используют случайность на уровне GPU или специфическое округление чисел с плавающей точкой . Модель, запущенная на одной видеокарте, может выдать чуть иные вероятности, чем на другой, что делает декомпрессию невозможной.
- Порядок операций. Разработчик должен строго следить за тем, чтобы модель не обновлялась символом $U_i$ до того, как этот символ будет закодирован . Опережающее обновление модели ломает логику декодера, у которого на данный момент просто нет этого символа .
- Проблема нулевых вероятностей. Адаптивная модель никогда не должна присваивать какому-либо символу строгую вероятность $0$, даже если он кажется абсолютно невозможным в данном языке . Если такой символ все же встретится, значение $\log_2(1/0)$ уйдет в бесконечность, и кодер аварийно завершит работу .
📉 Пределы k-го порядка и принцип минимальной длины описания 54:14
В классическом контекстном сжатии $k$-го порядка модель подсчитывает частоту появления символов после определенных цепочек длины $k$ . Эксперимент со сжатием книги «Собака Баскервилей» показывает, что при переходе от нулевого порядка (IID) к первому и второму качество сжатия заметно улучшается . Однако на третьем порядке ($k=3$) сжатие внезапно ухудшается .
Лектор объясняет этот парадокс физическими ограничениями объема данных :
- Размер таблицы контекстов растет экспоненциально как $|\mathcal{X}|^k$, где $|\mathcal{X}|$ — размер алфавита .
- Для коротких файлов объемом в несколько сотен килобайт контексты длины 3 и более становятся чрезвычайно редкими (проблема разреженности данных) . Модель просто не успевает набрать статистику по редким цепочкам символов и скатывается к неэффективному равномерному распределению.
- У классических моделей $k$-го порядка отсутствует семантическое обобщение . Например, контексты «thi» и «THI» для нее — абсолютно разные сущности, и накопленный по одному из них опыт никак не переносится на другой .
Если пойти по пути двухпроходного сжатия с ростом $k$, мы столкнемся с феноменом, когда модель начинает банально «заучивать» сжимаемый файл . В предельном случае модель $1000$-го порядка для файла из $1000$ символов выдаст вероятность $1$ для этого конкретного файла, закодировав его в $0$ бит . Но размер самой модели при этом окажется астрономическим .
Для решения этой дилеммы используется принцип минимальной длины описания (Minimum Description Length, MDL), сформулированный финским ученым Йормой Риссаненом . Согласно MDL, оптимальная архитектура сжатия должна минимизировать сумму двух величин: размера сжатых данных и размера самой модели .
Для преодоления проблемы разреженности данных в классических алгоритмах применяются более сложные подходы, такие как PPM (Prediction by Partial Matching) и CTW (Context Tree Weighting), которые умеют динамически переключаться на более короткие контексты, если длинные еще не были встречены в тексте .
🚀 Революция LLM: Сжатие без передачи модели 1:08:04
С появлением больших языковых моделей парадигма MDL может быть пересмотрена . Лектор предлагает представить гипотетический мир будущего, где тяжелая нейросеть уровня GPT-4 или Llama предустановлена на устройстве каждого пользователя . В таком сценарии нам больше не нужно включать модель в тело архива — мы можем считать, что кодер и декодер априори обладают одинаковой гигантской базой знаний.
В рамках тестов аспирант Стэнфорда Кедар Татвавади проверил эффективность сжатия текстов с помощью LLM . Результаты выявили несколько важных закономерностей:
- Влияние контекста. Небольшая модель на 430 млн параметров при контексте в 16 токенов сжимает текст хуже классического bzip2 . Но с расширением окна контекста точность предсказания резко возрастает, и качество сжатия обходит показатели лучших классических алгоритмов, приближаясь к теоретическому пределу Шеннона .
- Проблема несовпадения доменов. При попытке сжать древний индийский язык пали (записанный латиницей) модель показала результаты хуже, чем gzip и bzip2 . Это объясняется тем, что в обучающей выборке LLM тексты на пали практически отсутствовали. В то же время классические архиваторы универсальны и адаптируются к любому языку на лету .
- Феномен «галлюцинаторного» сжатия. При сжатии романа о Шерлоке Холмсе модель Llama неожиданно выдала невероятный результат — всего $0.2$ бита на символ . Причиной такой аномалии стало то, что этот классический текст целиком входил в обучающую выборку Llama . Модель фактически «вспомнила» книгу, что позволило ей предсказывать слова с почти стопроцентной точностью.
Как добавляет исследователь Пулкит Тандон, в контексте сжатия данных оверфиттинг (переобучение) модели на целевом тексте перестает быть проблемой машинного обучения и превращается в огромное преимущество . Если у вас есть возможность заранее переобучить модель под конкретный тип данных (например, под узкоспециализированные медицинские или финансовые архивы) и раздать эту модель на все узлы сети, это позволит добиться беспрецедентной степени сжатия, недоступной ни одному универсальному алгоритму .
Хотя сегодня LLM-компрессия остается чрезвычайно ресурсоемкой и медленной, работы в этом направлении (такие как недавняя статья DeepMind «Language Modeling is Compression») доказывают фундаментальную ценность сжатия как главного мерила истинного интеллекта машин .
