# Сжатие данных с потерями: от основ квантования до алгоритма Ллойда и k-means

Источник: https://www.youtube.com/watch?v=YEF0iCiQlOg
Канал: Stanford Online
Опубликовано: 18.04.2024

---

В Стэнфордском университете в рамках курса EE274 по сжатию данных лектор подвел итоги изучения алгоритмов сжатия без потерь (lossless) и объявил о переходе ко второй, не менее фундаментальной части дисциплины — сжатию с потерями (lossy compression). Этот переход знаменует собой смену парадигмы: от работы с дискретными алфавитами и точным восстановлением информации к аппроксимации непрерывных сигналов реального мира, таких как изображения, аудио и видео. В центре внимания лекции оказались математические основы квантования, компромисс между скоростью передачи и искажением (Rate-Distortion), а также неожиданные глубокие связи между теорией кодирования и классическими алгоритмами машинного обучения.

## 🧩 Разбор полетов: особенности парсинга и тесты LZ77
[[JUMP:0:18]]

Лекция традиционно началась с разбора вопросов еженедельного квиза, закрепляющего материал по алгоритму сжатия LZ77. В первом задании студентам предлагалось декодировать строку по готовой таблице соответствий смещений (offsets) и длин совпадений (lengths). На выходе получилась исходная последовательность символов: `AABBBBBBAABBBCDCDCD`.

Преподаватель обратил внимание аудитории на важный концептуальный нюанс, который ранее бурно обсуждался студентами на учебной платформе Ed. Суть проблемы заключалась в том, что алгоритм парсинга (разделения строки на фразы), пройденный на предыдущих занятиях, не выдавал в точности ту таблицу, которая была представлена в задании. Лектор пояснил, что в LZ77 схема парсинга не является уникальной: можно использовать жадный (greedy) подход, «ленивый» (lazy) парсинг или методы динамического программирования. Однако ключевое преимущество алгоритма заключается в том, что независимо от выбранной стратегии кодирования, декодер всегда однозначно и безошибочно восстановит исходную строку по полученной таблице.

Второе задание квиза было сфокусировано на заполнении таблицы кодирования LZ77 для конкретной строки — фамилии одного из соавторов курса Кедара (Tatwawadi). Студенты пошагово разобрали, как распределяются уникальные символы (литералы), длины совпадений и смещения:

* Первый повторяющийся литерал `A` кодируется со смещением 2 и длиной 1.
* Уникальный символ `W` идет следом, после чего очередная буква `A` матчится на три позиции назад.
* Затем кодируется уже знакомая алгоритму пара `WA` со смещением 2 и длиной 2, не оставляя после себя незакодированных литералов на этом шаге.
* Финальная пара `DI` остается незаmatched, уходя в поток как чистые незакодированные литералы.

## 📊 Алгоритм zstd против языковых моделей: концептуальная разница
[[JUMP:4:25]]

Третий вопрос квиза содержал интересный мысленный эксперимент: что произойдет, если в обычном английском тексте заменить все буквы со сдвигом по алфавиту (каждую `A` заменить на `B`, `B` на `C` и так далее), а затем попытаться сжать этот трансформированный текст? 

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

Совершенно иначе ведут себя компрессоры на базе больших языковых моделей (LLM), которые рассматривались на девятой лекции. Компрессор на основе LLM полностью провалит задачу на измененном тексте. Лектор подчеркнул:

> «Предиктор на базе LLM хорош ровно настолько, насколько хороша его вероятностная модель. Когда вы сдвигаете символы, ваша вероятностная модель полностью ломается. Вам пришлось бы заново обучать или обновлять LLM-модель, иначе она становится абсолютно бесполезной».

В этом и заключается фундаментальное различие между схемами сжатия на основе поиска совпадений (семейство LZ) и методами вроде арифметического кодирования или рекуррентных нейросетей (RNN), где критически важно точное совпадение реального распределения вероятностей с моделью компрессора.

В завершение разбора квиза преподаватель напомнил «золотое правило», или «шаг 0.1» для инженера при решении любой практической задачи по сжатию данных:

* Перед тем как проектировать сложные нейросетевые или специализированные архитектуры, всегда пробуйте запустить стандартный компрессор (например, тот же `zstd` или `gzip`).
* Только получив этот базовый результат (baseline), стоит переходить к тяжеловесным кастомным техникам.

## 📉 Переход к непрерывному миру: основы сжатия с потерями
[[JUMP:7:20]]

Подытожив пройденный материал первой половины курса — от энтропийных блочных кодов Шеннона и Хаффмана до потоковых кодов (арифметическое кодирование, ANS) и универсального алгоритма LZ77, включая контекстно-зависимое и адаптивное кодирование для не-IID источников, — лектор официально провозгласил переход к сжатию с потерями.

Первый тезис, который был озвучен максимально жестко: все знания, полученные при изучении сжатия без потерь, остаются применимыми. Сжатие без потерь — это просто частный случай сжатия с потерями, где уровень потерь равен строго нулю. Более того, абсолютно любой практический компрессор с потерями (будь то JPEG, MP3 или видеокодеки) внутри себя обязательно содержит финальный этап энтропийного сжатия без потерь. Сначала из сигнала убирается «лишняя» информация, а оставшиеся дискретные символы сжимаются уже знакомыми методами Хаффмана или ANS.

Главное отличие новой дисциплины — переход от дискретных источников к непрерывным. В реальности все сигналы, поступающие от сенсоров, камер, микрофонов, являются непрерывными функциями. 

На вопрос лектора, сколько информации содержится в непрерывном источнике, один из студентов предположил, что объем определяется плавающей точностью (precision) конкретной вычислительной машины. Преподаватель оспорил этот ответ, указав, что фиксируя разрядность (например, 64 бита), мы уже совершаем дискретизацию и выбрасываем часть информации. Истинный математический факт заключается в том, что непрерывный источник содержит **бесконечный** объем информации. Между любыми двумя вещественными числами находится бесконечно много других чисел.

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

## ⚖️ Скорость и искажение: фундаментальный компромисс
[[JUMP:13:30]]

Для математического описания потерь вводится важнейший параметр — искажение (distortion, $D$). Выбор функции искажения зависит от конкретного приложения. Чаще всего используются две базовые метрики:

1. Среднеквадратичная ошибка (Mean Squared Error, MSE), представляющая собой математическое ожидание квадрата разности между исходным символом $X$ и его представлением $\hat{X}$:
$$\text{MSE} = E[(X - \hat{X})^2]$$

2. Средняя абсолютная ошибка (Mean Absolute Error, MAE):
$$\text{MAE} = E[|X - \hat{X}|]$$

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

Вторым компонентом системы является скорость передачи данных (rate, $R$), то есть количество бит, выделяемых на представление одного символа источника. Между ними существует фундаментальный компромисс (Rate-Distortion tradeoff): чем больше бит ($R$) мы готовы потратить, тем меньшего искажения ($D$) можем достичь. Идеальное распределение бит стремится к так называемой границе Парето-эффективности (кривая имеет характерную плавно убывающую U-образную форму).

В инженерной практике к этому компромиссу всегда подходят с двух сторон:

* **Ограничение по искажению (Distortion-limited):** Задано максимальное искажение $D$, которое готово терпеть приложение (например, уровень качества стримингового сервиса, ниже которого пользователи начнут уходить). Задача — минимизировать скорость $R$, уложившись в этот порог.
* **Ограничение по скорости (Rate-limited):** Задана фиксированная пропускная способность канала (например, лимит мобильного интернета у пользователя, не позволяющий качать 4K-видео). Задача — перераспределить доступные биты так, чтобы минимизировать искажение $D$.

## 🔢 От округления к скалярному квантованию
[[JUMP:20:53]]

Простейший пример сжатия с потерями — обычное округление данных. Представьте датчик, измеряющий температуру в комнате в градусах Цельсия с точностью до шести знаков после запятой (например, $38.100001^\circ\text{C}$). Очевидно, что хранить все шесть знаков расточительно практически для любой прикладной задачи.

Если данные собираются для фитнес-браслета (чтобы человек просто понимал, нужно ли надеть худи перед выходом на улицу), достаточно округлить значения до целых чисел: вместо $38.1$, $36.2$, $37.9$ мы сохраняем $38$, $36$, $38$. Смена типа данных (например, из `float64` в `int`) — это уже полноценное квантование, отсекающее лишнюю точность и резко уменьшающее количество бит для последующего хранения. Однако для промышленного термостата на химическом заводе или задач материаловедения потребовалась бы значительно большая точность и меньший уровень искажений.

Строгое определение процесса дал профессор Стэнфорда Роберт Грей (Robert Gray), эксперт в этой области:

> «Квантование — это просто процесс отображения непрерывного источника в дискретный».

В процессе квантования используются следующие термины:

* **Символы или кодовые слова (codewords)** — дискретные значения, полученные после квантования.
* **Кодовая книга (codebook) или словарь** — полный набор доступных дискретных значений. Например, если мы округляем температуру и на выходе получаем только значения $35, 36, 37, 38$, то эти четыре числа и составляют нашу кодовую книгу.

Если размер кодовой книги равен $N$, то для передачи индекса конкретного кодового слова нам потребуется всего $\lceil\log_2 N\rceil$ бит. Таким образом, если в кодовой книге 4 элемента, для трансляции любого значения нужно всего 2 бита (при допущении равномерного распределения).

## 📈 Квантование Гауссова источника и MMSE-оценщик
[[JUMP:35:07]]

Для демонстрации математического аппарата квантования лектор предложил рассмотреть стандартную непрерывную случайную величину — Гауссов (нормальный) источник с нулевым средним значением и единичной дисперсией. Предположим, что бюджет на кодирование жестко ограничен всего **1 битом на символ**.

Поскольку распределение Гаусса симметрично относительно нуля, наиболее интуитивное решение при бюджете в 1 бит (дающем всего два доступных состояния) — кодировать знак числа (плюс или минус). Если число положительное, мы отправляем на декодер условную единицу, если отрицательное — ноль.

Но какое конкретное значение должен восстановить декодер, получив сигнал о том, что исходное число было больше нуля? Какое кодовое слово минимизирует среднеквадратичную ошибку (MSE)?

Математический ответ на этот вопрос дает знаменитый в теории обработки сигналов **минимальный среднеквадратичный оценщик (Minimum Mean Square Estimator, MMSE)**. Оптимальным значением восстановления является условное математическое ожидание исходной величины $X$ при условии, что она попала в данную область квантования (в нашем случае, $X > 0$):
$$\hat{X} = E[X \mid X > 0]$$

Поскольку плотность вероятности стандартного Гауссова распределения равна $f(X) = \frac{1}{\sqrt{2\pi}} e^{-X^2/2}$, а область интегрирования из-за симметрии сужается вдвое (что удваивает плотность на положительной полуоси), расчет интеграла дает точный результат:
$$\hat{X}_+ = \sqrt{\frac{2}{\pi}} \approx 0.798$$

Для отрицательной половины значение симметрично: $-\sqrt{2/\pi}$. Таким образом, оптимальная кодовая книга для 1-битного сжатия Гауссова источника по критерию MSE состоит всего из двух чисел: $\pm\sqrt{2/\pi}$.

Общая схема такой коммуникации выглядит следующим образом:

```
[Непрерывный источник X] 
       │
       ▼
[Определение знака ( thresholds)] ──► Передача индекса (0 или 1) 
       │
       ▼
[Декодер: подстановка из Codebook] ──► Выходное значение (±√2/π)
```

## 📐 Скалярное квантование против векторного
[[JUMP:48:32]]

Описанный выше процесс называется **скалярным квантованием**, поскольку алгоритм обрабатывает каждый символ источника по отдельности. Скалярный квантователь полностью определяется двумя сущностями: порогами принятия решений (decision thresholds) и квантованными значениями кодовой книги. При этом области квантования вовсе не обязаны быть одинаковыми по ширине — их геометрия диктуется исключительно минимизацией выбранной функции искажения.

Однако, проводя параллели с блочным кодированием из первой половины курса, возникает закономерный вопрос: можно ли добиться лучшего сжатия, если объединять символы в блоки и квантовать их совместно? Это подводит к концепции **векторного квантования (Vector Quantization, VQ)**.

Рассмотрим блок из двух символов ($k = 2$) при сохранении того же бюджета скорости — 1 бит на символ. Это дает нам право использовать $2 \times 1 = 2$ бита на весь блок, что позволяет расширить кодовую книгу до $2^2 = 4$ кодовых векторов. Переходя на двумерную плоскость Гауссова распределения ($X_1, X_2$), мы можем распределить эти четыре кодовых слова разными способами:

* **Разделение по квадрантам:** Простейший способ — провести границы по осям координат. Кодовые слова расположатся в центрах четырех квадрантов на одинаковом удалении от центра.
* **Разделение со смещением осей:** Можно повернуть оси на любой угол. Из-за сферической симметрии двумерного Гауссова распределения эффективность кодирования (уровень MSE) останется абсолютно идентичной. Декодеру все равно, под каким углом лежат векторы, ведь он оперирует только индексами кодовой книги.
* **«Жадный» подход с центром в начале координат:** Можно поместить одно кодовое слово строго в ноль (оригин), а остальные три распределить по кругу на одинаковом расстоянии друг от друга. Границы решений в таком случае станут радиальными линиями (разделяющими гиперплоскостями). С помощью численного моделирования в Jupyter-ноутбуке лектор продемонстрировал, что такое распределение для Гауссова источника является субоптимальным.

## 🐝 Эффективность решеток и предел сложности
[[JUMP:1:08:50]]

Векторное квантование обладает колоссальным преимуществом перед скалярным по двум причинам:

1. Оно способно напрямую эксплуатировать линейные и нелинейные зависимости (корреляцию) между компонентами вектора. Если величины $X_1$ и $X_2$ сильно скоррелированы (например, всегда имеют одинаковый знак), то вместо прямоугольной сетки скалярного квантователя (скажем, на 36 ячеек), векторный квантователь может разместить кодовые слова только вдоль диагонали распределения (сократив число ячеек до 18 при том же качестве), что экономит до полубита на символ.
2. Даже для абсолютно независимых и одинаково распределенных (IID) источников векторные границы решений оказываются эффективнее скалярных квадратных сеток.

Математически доказано, что разбиение пространства на правильные шестиугольники — **гексагональная (сотовая) решетка** (также известная как квантование Вороного) — дает среднеквадратичную ошибку (MSE) примерно на 4% ниже, чем классическая квадратная сетка скалярного квантователя при той же скорости передачи данных. При увеличении размерности пространства до трех и более измерений можно строить еще более сложные и эффективные упаковочные многогранники.

Однако за эту математическую красоту приходится платить вычислительной сложностью. Как и блочные коды в lossless-сжатии, оптимальное векторное квантование требует экспоненциального роста вычислений и памяти для хранения гигантских многомерных кодовых книг.

Лектор сослался на классическую работу знаменитого ученого Якова Зива (Jacob Ziv, соавтора LZ77), посвященную универсальному квантованию. Зив математически доказал, что при любом, сколь угодно сложном дизайне, оптимальный скалярный квантователь проигрывает векторному по скорости кодирования не более чем на **0.754 бита на символ**. 

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

## 🤖 Алгоритм Ллойда-Макса и кластеризация k-means
[[JUMP:1:15:33]]

Главная сложность при проектировании квантователя заключается в том, что пороговые границы и значения кодовой книги взаимосвязаны (intertwined): кодовые слова зависят от геометрии областей решений, а сами области строятся на основе поиска ближайших кодовых слов. Разрешить этот замкнутый круг помогает итеративный подход.

Лектор обратился к аудитории с вопросом, не напоминает ли им эта концепция что-то из параллельных дисциплин. Студенты мгновенно узнали в этом описании задачу кластеризации.

> «Мы занимаемся ровно кластеризацией. Имея набор точек, мы пытаемся определить области решений (кластеры), внутри которых находится одно квантованное значение».

В компрессии и теории обработки сигналов этот метод оптимизации называется **алгоритмом Ллойда-Макса** (Lloyd-Max) или Обобщенным алгоритмом Ллойда (Generalized Lloyd Algorithm, GLA). В сфере машинного обучения (Machine Learning) он же известен под культовым названием **алгоритм k-means (k-средних)**. Алгоритм k-means является частным случаем обобщенного метода Ллойда, оптимизированным под среднеквадратичную ошибку. Исторически работа Ллойда была написана очень давно, задолго до ее официальной публикации в 1982 году.

Итерационный процесс k-means / Ллойда-Макса устроен по шагам:

1. Инициализация: случайным образом выбираются $N$ начальных центроидов (будущих кодовых слов).
2. Шаг разбиения (Partition): каждая точка обучающей выборки ассоциируется с ближайшим к ней центроидом, формируя границы кластеров.
3. Шаг обновления (Update): для каждого полученного кластера вычисляется новый геометрический центр (новое кодовое слово), минимизирующий искажение.
4. Повторение циклов до тех пор, пока центроиды не перестанут смещаться (конвергенция).

В финальной части лекции преподаватель продемонстрировал работу Jupyter-ноутбука, где алгоритм k-means запускался на двумерном Гауссовом распределении для получения кодовых книг разного размера ($N=4$, $N=8$). График наглядно показал, как по мере итераций среднее искажение монотонно падает, формируя реальную экспериментальную кривую Rate-Distortion.

Более того, лектор продемонстрировал работу квантования на реальных изображениях из датасета MNIST. В этом случае размерность вектора $k$ составляла не 2, а $28 \times 28 = 784$ измерения (по числу пикселей в картинке). Проведенная кластеризация позволила получить отчетливые визуальные центроиды, представляющие собой усредненные прототипы рукописных цифр, что по сути является базовым примером применения векторного квантования для эффективного сжатия изображений с потерями.

Полученная в результате симуляций экспериментальная синяя кривая искажения была сопоставлена с красной линией — теоретическим пределом Шеннона для Гауссова источника ($D(R) = \sigma^2 2^{-2R}$). Изучению того, почему ни один алгоритм в мире принципиально не способен преодолеть этот фундаментальный теоретический барьер, будет посвящена следующая лекция профессора Цахи Вайсмана (Tsachy Weissman).