Rate-Distortion Theory

Почему фотография весит 3 МБ в PNG, но 300 КБ в JPEG «хорошего качества» и выглядит так же? Rate-Distortion Theory даёт точный ответ: за счёт каких бит идёт «оплата» и что получаем взамен.

• **Netflix** использует per-title encoding: для каждого фильма подбирает свою кривую R-D с учётом сложности сцен. «Простые» фильмы сжимаются сильнее без потери воспринимаемого качества.
• **LLM токенизация** - это lossy-сжатие: BPE-токены представляют слова приближённо. Информационный ботлнек (Information Bottleneck) связывает это с R-D теорией.
• **Нейросетевые кодеки** (Google Balle, ELIC, 2022) начали превосходить AV1 при низких битрейтах - впервые за 20 лет прорыв в эффективности сжатия изображений.

Предварительные знания

• Communication Channel and Capacity

Функция скорость-искажение

При lossy-сжатии мы намеренно теряем точность ради меньшего размера. Rate-Distortion Theory отвечает на вопрос: «какой минимальный размер файла при допустимом искажении D?». Функция R(D) даёт нижнюю границу: нельзя сжать ниже R(D) бит/символ при среднем искажении D. Для гауссовского источника R(D) = ½ log₂(σ²/D) - красивая формула, связывающая дисперсию, искажение и скорость.

**Rate-distortion function R(D):** R(D) = min_{p(x̂|x): E[d(X,X̂)]≤D} I(X;X̂). Для гауссовского источника X~N(0,σ²) при MSE-искажении: R(D) = max(0, ½ log₂(σ²/D)) бит/символ. Обратная функция: D(R) = σ² · 2^{−2R}. Удвоение скорости R уменьшает искажение в 4 раза.

Квантование

Квантование - базовый инструмент lossy-сжатия: непрерывные (или многоразрядные) значения заменяются на дискретные кодовые слова. Скалярное квантование работает с каждым элементом отдельно, векторное квантование (VQ) - с группами. Алгоритм Ллойда-Макса минимизирует MSE-искажение при фиксированном числе уровней квантования.

**Скалярный квантизатор:** разбивает диапазон на R=2^b ячеек, каждой значению присваивает центроид. Оптимальный (Lloyd-Max): границы ячеек - середины центроидов, центроиды - средние значения в ячейке. Правило 6 дБ: каждый дополнительный бит квантования снижает MSE в 4 раза (≈6 дБ SNR).

Lossy сжатие: JPEG и MP3

JPEG и MP3 - не просто «квантование файла», а трёхэтапная трансформационная цепочка: сначала transform (DCT/MDCT) переводит сигнал в частотную область, затем квантование с перцептуальными весами убирает то, что человек не заметит, и наконец энтропийное кодирование сжимает результат без потерь. Перцептуальная модель - ключ: зрение нечувствительно к высоким частотам, слух маскирует тихие звуки рядом с громкими.

**JPEG:** 8×8 блок → DCT → квантование Q-таблицей → zigzag → RLE → Хаффман. Коэффициент сжатия ~10:1 при хорошем качестве. **MP3:** перекрывающийся MDCT → субполосное фильтрование → психоакустическая модель → квантование → Хаффман. Типично 192 кбит/с вместо 1411 кбит/с (CD).

Компромисс скорость-качество

Rate-distortion компромисс - фундаментальное ограничение: кривая R(D) показывает, что при сжатии ниже определённой скорости потери неизбежно растут. Современные кодеки (HEVC, AV1) приближаются к теоретической кривой R(D). Нейросетевые кодеки (2020-е) начинают пробиваться выше кривой «классических» методов в определённых метриках качества (LPIPS, SSIM).

**Rate-distortion компромисс на практике:** Кривая R(D) - теоретическая граница. Реальные кодеки выше неё (хуже). Расстояние до кривой называется «coding gap». AV1 на 30-50% эффективнее H.264 при том же качестве. Нейросетевые кодеки (VCT, ELIC) превосходят AV1 при низких битрейтах.

Ключевые идеи

• **R(D) function:** нижняя граница - при допустимом искажении D нельзя сжать ниже R(D) бит/символ. Для гауссового источника: R(D) = ½ log₂(σ²/D).
• **Квантование:** отображение непрерывных значений в дискретные. Каждый бит квантования → +6 дБ SNR (MSE ÷ 4).
• **JPEG/MP3:** transform (DCT/MDCT) → перцептуальное квантование → энтропийное кодирование. Перцептуальная модель - ключ к качеству.
• **Нейросетевые кодеки** приближаются к кривой R(D) быстрее, чем классические методы, за счёт мощной модели источника.

Связанные темы

Rate-Distortion Theory связывает сжатие с информацией и машинным обучением:

• Канал связи и пропускная способность — Rate-distortion - «сестринская» теория: там R(C) для надёжности, здесь R(D) для качества
• Information Theory в ML — Information Bottleneck и ELBO - применения R-D теории к обучению нейросетей
• Сжатие данных: JPEG, H.265, LLM — Практические реализации R-D теории в стандартах и нейросетях

Вопросы для размышления

• Почему нейросетевые кодеки могут быть эффективнее классических? Что такого они «знают» о структуре изображений?
• JPEG работает на блоках 8×8. Как это связано с rate-distortion теорией и почему не 16×16 или 4×4?
• Токенизация LLM - это lossy-сжатие? Как применить R-D framework к оценке качества токенизатора?

Связанные уроки

• prob-10-continuous
• stat-03-mle