Теория информации
Теория скорость-искажение
Цели урока
- Определить функцию R(D) через оптимизацию взаимной информации
- Вывести и применить формулу R(D) для гауссова источника
- Понять водопадное распределение и теорему кодирования с искажением
- Связать R(D)-теорию с нейросетевым сжатием и VAE
Предварительные знания
- Дифференциальная энтропия
- Взаимная информация и KL-дивергенция
Какова минимальная скорость для передачи гауссова источника с заданным MSE? Как оптимально распределить биты между несколькими компонентами?
- Netflix 4K-видео при 2 Мбит/с находится в 3 дБ от предела Shannon R(D)
- Квантование весов нейросетей (int4/int8) - прямое R(D)-приложение
- JPEG 2000 использует водопадное распределение по вейвлет-субполосам
- бета-VAE задаёт точку на кривой rate-distortion через параметр beta
От исходников к пределу
Клод Шеннон в 1948 году заложил основы теории информации. Теорема кодирования с искажением появилась в 1959 году - 'Coding theorems for a discrete source with a fidelity criterion'. Это был шаг от двоичной передачи к непрерывным источникам. Шеннон показал: любой источник можно описать функцией R(D), и ниже неё кодировать без превышения искажения D принципиально невозможно. Берггер в 1971 году систематизировал теорию в монографии 'Rate Distortion Theory'. Практическое применение пришло с JPEG (1992), JPEG 2000 (2000) и H.265 (2013) - все они работают вблизи, но не на границе R(D).
Функция скорость-искажение R(D)
Netflix сжимает 15 петабайт видеоконтента с использованием H.265 (HEVC): при целевом битрейте 2 Мбит/с для 4K-видео кодек работает в 3 дБ от границы R(D) по Шеннону. Три децибела - это цена за то, что формулу 1959 года до сих пор не удалось побить полностью.
Квантование нейросетей - прямое применение R(D)-теории. Каждый весовой тензор - случайный источник с дисперсией sigma^2. R(D) предсказывает минимальный битрейт для заданной точности восстановления. Именно поэтому int4-квантование дает 4 бит/вес без катастрофической потери точности: модели оказываются близко к гауссовскому источнику.
R(D) - нижняя граница по Шеннону: никакой кодер не может передать источник с искажением D за меньше R(D) бит/символ. Верхняя граница отдельно - реальные кодеки работают между ними.
Что означает R(D) = 0 для дискретного источника?
R(D_max) = 0: при D >= D_max оптимальный декодер выдаёт фиксированную константу (среднее или медиану), не получая ни одного бита. Бесконечно большое искажение разрешено - информация не нужна.
R(D) для гауссова источника и водопадное распределение
1959 год. Шеннон публикует 'Coding theorems for a discrete source with a fidelity criterion'. Среди результатов - явная формула R(D) для гауссова источника. Её красота: закрытая форма без интеграла минимизации.
JPEG 2000 и водопадное распределение
JPEG 2000 декомпозирует изображение вейвлет-преобразованием на субполосы с разными дисперсиями. Затем water-filling распределяет биты: низкочастотная субполоса (sigma^2 = 100) получает 3 бит/коэф, высокочастотная (sigma^2 = 0.01) - ноль. Именно это объясняет, почему JPEG 2000 при малом битрейте выглядит мягче, чем классический JPEG: он оптимально молчит там, где глазу всё равно.
Чему равна функция R(D) для гауссова источника N(0, sigma^2) при MSE-искажении?
Для N(0, sigma^2) с MSE: R(D) = 1/2 * log2(sigma^2/D) при 0 <= D <= sigma^2. Коэффициент 1/2 - от того, что гауссов источник непрерывный. Формула R(D) = 1/2 * log2(1 + sigma^2/D) - это пропускная способность канала, не R(D) источника.
Теорема кодирования с искажением
Теорема Шеннона о R(D) симметрична теореме кодирования по каналу. Для каналов: надёжная передача возможна тогда и только тогда, когда R < C. Для источников: кодирование с искажением D возможно тогда и только тогда, когда R >= R(D). Две стороны одной монеты - дуальность теорий.
Разрыв между R(D) и реальными кодеками называется 'rate-distortion gap'. H.265 отстаёт от теоретической границы на 2-4 дБ в PSNR при типичных битрейтах. AV1 сократил этот разрыв примерно на 30% по сравнению с H.265.
VAE (Variational Autoencoder) - это реализация теоремы кодирования с искажением в нейросетях. Скрытый вектор z - это код. MSE-реконструкция плюс KL-дивергенция - это rate-distortion tradeoff. Бета-VAE с параметром beta задаёт точку на кривой R(D): большее beta = меньше R, больше D.
Что гарантирует прямая часть теоремы R(D)?
Прямая часть: при R > R(D) существует последовательность (n, 2^{nR})-кодов с искажением <= D + epsilon при достаточно большом n. Это гарантия существования - конструктивно такие коды строятся случайным выбором кодовых слов.
R(D) на практике: перцептуальные меры и нейросетевое сжатие
MSE - удобная математика, но плохая модель восприятия. Человек видит структуру, не пиксели. В 2020 году Google Brain опубликовал 'High-Fidelity Generative Image Compression': нейросетевой кодек бьёт H.265 при 0.1 бит/пиксель. Секрет - GAN-функция потерь вместо MSE, то есть другая d(x, x-hat) в формуле R(D).
Нейросетевое сжатие и бета-VAE
balle2018 (Google Brain, 2018) - нейросетевой кодек на основе вариационного автоэнкодера. Архитектура: encoder f_theta(x) -> z, quantizer Q(z) -> z_hat, decoder g_phi(z_hat) -> x_hat. Функция потерь: R + lambda*D = -log p(z_hat) + lambda * MSE(x, x_hat). Параметр lambda соответствует точке на кривой R(D): lambda=0.01 -> низкий битрейт, lambda=0.1 -> высокое качество. При 0.1 бит/пиксель результат субъективно лучше JPEG 2000 в 2 раза.
Теорема R(D) гарантирует существование оптимального кода, но не его эффективную конструкцию. Для произвольного источника и произвольного d(x,x-hat) даже вычисление R(D) - NP-сложная задача. Только для гауссова источника с MSE есть закрытая формула.
Почему нейросетевые кодеки с perceptual loss иногда превосходят H.265 по субъективному качеству?
R(D) - теорема для любой меры d(x,x-hat). MSE технически удобна, но не моделирует зрение. Нейросетевые кодеки меняют d на перцептуальную - и оптимизируют R(D) уже для этой меры. H.265 оптимизирован под MSE/PSNR, поэтому при перцептуальной оценке проигрывает.
Связь с другими темами
R(D)-теория объединяет: теорию взаимной информации (через определение R(D) = min I(X;X-hat)), метод типичных последовательностей (доказательство теоремы), водопадный алгоритм (из теории портфелей Келли). В ML: beta-VAE - прямая реализация R(D)-трейдоффа, информационная бутылочная горлышка (Tishby, 1999) обобщает R(D) на задачи с релевантностью. Дуальность с пропускной способностью: C = sup_px R(0) по каналу; R(D) = inf по источнику при данном D.
- Related concepts — Связанная тема
Итоги
- R(D) = min I(X;X-hat) по всем условным распределениям с ожидаемым искажением <= D
- Гауссов источник с MSE: R(D) = 1/2 * log2(sigma^2/D) - единственная закрытая формула
- Водопадное распределение: биты идут туда, где sigma_i^2 > theta; слабые компоненты молчат
- Теорема: при R > R(D) надёжное сжатие с искажением D возможно; при R < R(D) - нет
Вопросы для размышления
- Почему для гауссова источника R(D) имеет закрытую форму, а для большинства источников - нет?
- Как выбор меры искажения d(x, x-hat) влияет на оптимальность кодека для конкретного приложения?
- В чём разница между R(D)-теорией источника и теоремой пропускной способности канала?