Вейвлет-пакеты, лифтинг и применение в Deep Learning

Кажется, что вейвлеты — устаревшая теория из 90-х. На самом деле lifting scheme лежит внутри JPEG 2000 lossless, scattering transform — конкурент CNN на малых данных, а wavelet packets дали идею дилатированных свёрток (WaveNet, TCN). Этот урок раскрывает три продвинутых техники, которые делают вейвлеты живой темой 2020-х.

• JPEG 2000 lossless для медицинских снимков использует целочисленное lifting-преобразование 5/3 — без него обратимость в целых числах невозможна.
• Scattering networks Bruna-Mallat показали 0.43% ошибки на MNIST без backprop — это конкурентно с обученными CNN при на порядок меньшем числе параметров.
• DeepMind WaveNet и Bai et al. TCN моделируют речь и временные ряды через дилатированные свёртки, которые математически эквивалентны фильтрам вейвлет-пакетов.

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

• Базовая теория вейвлетов и MRA
• Гильбертовы пространства, ортонормированные базисы в L^2
• Свёрточные нейросети — общая идея фильтра и дилатации

Вейвлет-пакеты: разложение и выбор лучшего базиса

Стандартное вейвлет-преобразование разлагает только низкочастотный поддиапазон на каждом уровне. Coifman и Wickerhauser в 1992 году обобщили схему: разлагаются ОБА поддиапазона, что даёт древо 2^n листьев на уровне n. Среди всех 2^{2^n - 1} возможных базисов алгоритм best basis выбирает оптимальный по энтропии Шеннона за O(N log N).

Best-basis выигрывает для сигналов с энергией в средних частотах: музыкальные транзиенты, биомедицинские паттерны (QRS-комплекс), вибросигналы машин. DWT разрешает только низкие частоты, а пакеты — весь спектр.

Lifting scheme: вейвлеты второго поколения

Sweldens в 1996 году предложил конструировать вейвлеты прямо в сигнальной области, без преобразования Фурье. Lifting даёт целочисленные обратимые преобразования (нужны для сжатия без потерь, JPEG 2000 lossless), быстрее DWT в 2 раза, и работает на нерегулярных сетках, графах, сферах.

(1) Обратимость в целых числах: x → (s,d) → x без округлений. (2) In-place: не нужна память на копию сигнала. (3) Адаптивность: предиктор P может зависеть от данных. (4) Геометрия: работает на триангулированных сетках 3D-моделей (subdivision wavelets).

Scattering transform и WaveNet: вейвлеты внутри нейросетей

Mallat в 2012-м предложил scattering transform — каскад из CWT с модулем и усреднением. Это даёт инвариантное к переносу, стабильное к деформациям представление, обучаемое БЕЗ обратного распространения. На MNIST scattering + SVM достигает 0.43% ошибки. Параллельно WaveNet (DeepMind, 2016) использует дилатированные свёртки, которые математически эквивалентны фильтрам вейвлет-пакетов.

Дилатированная свёртка WaveNet с шагом 2^k реализует фильтр на масштабе 2^k — точно как вейвлет-пакет уровня k. Разница: WaveNet обучает фильтры из данных, а классические вейвлеты фиксированы. Современные TCN (Bai et al. 2018) — это, по сути, обучаемые wavelet packet networks.

Итоги

• Wavelet packets разлагают весь спектр; алгоритм best-basis Coifman-Wickerhauser выбирает оптимальный разрез за $O(N\log N)$ по энтропии Шеннона.
• Lifting scheme — вычислительная схема вейвлетов в сигнальной области, дающая обратимость в целых числах, in-place и работу на нерегулярных областях.
• Scattering transform — каскад $|CWT|$ + усреднение; даёт Lipschitz-устойчивость к диффеоморфизмам без обучения (Bruna-Mallat).
• Дилатированные свёртки WaveNet и TCN — обучаемые потомки wavelet packets.

Связь с другими темами

Урок 24 даёт базовую теорию вейвлетов и MRA. Урок 19 (ряды Фурье) — гармонический контрапункт: единственное разрешение vs. мультимасштабность. В курсе по DL scattering transform и дилатированные свёртки нашли применение в аудио, time-series и графовых нейросетях.

• Базовая теория вейвлетов и MRA — Предшествующий урок (trig-24)
• Ряды Фурье — Гармонический контрапункт (trig-19)
• Свёрточные нейросети — Применение scattering и дилатированных свёрток
• Сжатие без потерь JPEG 2000 — Прямое применение lifting