Теория информации
Теорема Уайнера-Зива
Цели урока
- Сформулировать теорему WZ и объяснить 'бесплатность' боковой информации для гауссового источника
- Описать конструкцию вложенных решёток для WZ-кодирования
- Связать WZ с Distributed Video Coding и кодеком DISCOVER
- Объяснить связь Information Bottleneck с WZ-теоремой
Предварительные знания
Как кодер, не знающий боковую информацию Y, может кодировать X так же эффективно, как если бы Y было известно? Зачем нужны вложенные решётки?
- H.264/AVC: каждый Intra-кадр - практическая реализация WZ при декодировании с контекстом
- DISCOVER DVC: IP-камеры с WZ-кодированием - кодирование в 50 раз дешевле H.264
- VAE с beta-регуляризацией - прямая реализация WZ/IB через нейросети
- Federated learning: WZ-принцип для эффективной передачи градиентов
От SW до WZ: 3 года и обобщение
Слепян-Вольф (1973) - сжатие без потерь. Уайнер и Зив расширили задачу: что если допустить потери и боковая информация только у декодера? Публикация 1976 года в IEEE Transactions on Information Theory. Шокирующий результат для гауссового источника: оптимальная скорость та же, что если бы кодер тоже видел Y. Практические коды долго не существовали. Zamir, Shamai, Erez (2002): вложенные решётки. Distributed Video Coding (DVC): первое широкое применение WZ. DISCOVER (EPFL, 2006) - полный WZ-видеокодек. Нейросетевые WZ-кодеки (2020+) превзошли DISCOVER. Tishby (1999): Information Bottleneck - переформулировка WZ для ML.
Теорема Уайнера-Зива: боковая информация бесплатна
1976 год. Аарон Уайнер и Якоб Зив публикуют 'The Rate-Distortion Function for Source Coding with Side Information at the Decoder'. Главный результат: для гауссовых источников оптимальная скорость R*(D) = R_{X|Y}(D) - такая же, как если бы кодер тоже видел боковую информацию Y. Боковая информация у декодера эквивалентна боковой информации у обоих. Парадокс.
H.264/AVC Intra-кадры: каждый кадр кодируется с опорным кадром у декодера. Это задача WZ: кодер не может использовать опорный кадр (он нужен для последующего декодирования на другом устройстве), но декодер его имеет. Теорема WZ говорит: оптимальная скорость при этом такая же, как если бы кодер видел опорный кадр. H.264 приближается к этой границе через motion compensation.
Выигрыш WZ: G = R(D) - R*(D) >= 0. Для гауссова X с MSE: G = 1/2 * log(1 + P/sigma^2) при D -> 0. Это взаимная информация I(X;Y). При высокой корреляции (P >> sigma^2): G -> 1/2 * log(P/sigma^2) - большой выигрыш. При нулевой корреляции (P=0): G=0, боковая информация бесполезна.
Что означает результат WZ для гауссового источника 'кодер платит только за шум N'?
X = Y + N. Декодер знает Y, не знает N. Оптимальный кодер: кодировать только N через rate-distortion. R*(D) = 1/2*log(sigma^2/D) - это R(D) для N~N(0,sigma^2). Боковая информация Y не требует дополнительных бит от кодера, хотя кодер её не видит.
Вложенные решётки: конструкция WZ-кодека
Теорема WZ - существование; вложенные решётки (nested lattice codes) - конструкция. Предложены Zamir, Shamai, Erez (2002). Идея: мелкая решётка для точного квантования, грубая - для 'бинирования'. Декодер с боковой информацией разрешает неоднозначность бина.
Scalar WZ-кодирование: простейший практический вариант. Квантователь с несколькими порогами, каждый порог соответствует ячейке решётки. При SNR=20 дБ (rho=0.99) scalar WZ с 4 битами даёт PSNR на 3 дБ выше, чем равномерный квантователь без боковой информации.
В чём роль мелкой и грубой решётки в WZ-кодировании?
Аналогия со SW: мелкая решётка Lambda_f = точное квантование; грубая Lambda_c/Lambda_f = бинирование. Кодер передаёт номер бина = log|Lambda_c/Lambda_f| = nR*(D) бит. Декодер знает Y, находит правильный представитель в Lambda_f внутри бина Lambda_c.
WZ в видеокодировании: DISCOVER и Distributed Video Coding
Distributed Video Coding (DVC) - класс видеокодеков, где кодирование простое, а декодирование сложное. Это инверсия H.264: там кодер сложный (motion estimation), декодер простой. DVC применяется там, где кодер имеет ограниченные вычисления: IP-камеры, мобильный видеозахват.
DISCOVER против H.264
DISCOVER (2006, EPFL/IST): полный DVC кодек на основе WZ. Параметры: Bande 4:2:0, QCIF (176x144), блоки 16x16. Сравнение при 256 кбит/с: H.264 Intra PSNR = 32.5 дБ, DISCOVER PSNR = 30.8 дБ (хуже на 1.7 дБ). Но: сложность кодирования DISCOVER в 50 раз меньше. Применение: IP-камеры низкого качества, сенсоры с батарейным питанием, body cameras без GPU.
Нейросетевой WZ (2020-2024): замена синдромного BP-декодирования на нейросетевой декодер. Архитектура: боковая информация Y_side + синдром -> CNN-декодер -> восстановленный кадр. Преимущество: обучение на реальных данных учитывает статистику конкретного видеоконтента. Google Brain (2022): нейросетевой DVC превосходит DISCOVER на 2-3 дБ при той же скорости.
Почему в DVC кодирование проще, а декодирование сложнее, чем в H.264?
H.264 кодер: motion estimation = дорогая операция (перебор блоков). H.264 декодер: простое применение вектора движения. DVC: кодер = DCT + синдром (дёшево). Декодер = построение боковой информации через интерполяцию + BP-декодирование синдрома (дорого). Теорема WZ гарантирует, что при хорошей боковой информации скорость близка к оптимальной.
Обобщения WZ и связь с информационной бутылочным горлышком
WZ обобщается на несколько классов задач. Многотерминальный WZ: несколько источников с боковой информацией у декодеров. Обратная WZ (reverse WZ): кодер знает боковую информацию, декодер - нет. Это задача 'Heegard-Berger', решена частично. Связь с information bottleneck (Tishby): IB минимизирует I(X;Z) при I(Z;Y) >= R - это WZ-задача с другим знаком.
Deep Variational Information Bottleneck (Alemi et al., 2017): нейросетевая реализация IB. Encoder: f_theta(x) -> z (нейросеть). Loss: I(X;Z) - beta * I(Z;Y) оценивается через вариационные нижние границы. По сути это WZ-кодирование: найти минимальное представление Z, содержащее информацию о Y. VAE (бета=1) - специальный случай. На практике: увеличение beta улучшает robustness к adversarial примерам.
Как Information Bottleneck Tishby связан с теоремой Уайнера-Зива?
WZ: min I(X;U) - I(U;Y) при E[d(X,X-hat)] <= D. IB: min I(X;Z) - beta*I(Z;Y). При beta=1: то же, но с релевантностью I(Z;Y) вместо искажения D. Lagrangian WZ: R*(D) = min over lambda [I(X;U) - I(U;Y) + lambda * D]. Структурно идентично. Это объясняет успех VAE (beta=1): он решает WZ-задачу в пространстве данных.
Связь с другими темами
Теорема WZ синтезирует SW (сжатие без потерь с боковой информацией) и R(D)-теорию (сжатие с потерями). Гауссов случай: R*(D) = 1/2*log(sigma_N^2/D) - только шум кодируется. Вложенные решётки - практическая конструкция. В ML: IB-принцип Tishby = WZ при beta=1; VAE = нейросетевой WZ-кодер. DVC использует WZ для видео с боковой информацией у декодера. Нейросетевые WZ-кодеки: encoder обучается минимизировать R*(D) без явных решёток.
- Related Topics — Связанная тема
Итоги
- WZ: кодер без Y, декодер с Y. R*(D) = min I(X;U) - I(U;Y) по марковским U-X-Y
- Гауссов WZ: R*(D) = 1/2*log(sigma_N^2/D) - только шум N кодируется, Y бесплатна
- Вложенные решётки Lambda_f ⊂ Lambda_c: мелкая = квантование, грубая = бинирование
- WZ при D=0: совпадает с SW. Связь с IB: WZ = IB при beta=1
Вопросы для размышления
- Почему 'боковая информация бесплатна' в WZ - это принципиально другой результат, чем просто 'корреляция уменьшает энтропию'?
- Как вложенные решётки решают проблему 'кодер не видит Y, но должен угадать нужный бин'?
- В чём практический компромисс DVC: почему IP-камеры выбирают этот кодек вместо H.264?