Как преобразование Фурье ускоряет обучение CNN

Как практикующие глубокое обучение извлекают выгоду из открытия, сделанного 200 лет назад

Введение

Если вы изучали ряды Тейлора, вы понимаете, насколько полезно приближать сложную функцию конечным рядом более простых членов. Ряд Фурье - еще один пример разложения общей функции на суперпозицию синусоид (амплитуда / время → амплитуда / частота), что делает ее особенно подходящей для физических временных рядов, обработки сигналов и других данных о сигналах.

Хотя изображения не совсем похожи на «форму волны», преобразование Фурье, тем не менее, находит важное применение в одном из самых ценных творений глубокого обучения - сверточных нейронных сетях.

Определения

Рассмотрим сложную 2π-периодическую функцию f (x) такую, что f (x + 2π) = f (x) для всех x. Наша цель - разложить его на сумму периодических синусоид, сохранив при этом периодичность f, ключевую особенность данных сигнала. Мы знаем, что cos x имеет период 2π, но аналогично тому, как одночлены всех степеней составляют вместе с разными сдвигами и масштабами, мы можем сделать то же самое с синусоидальными членами различных периодов и амплитуд. В частности, мы составим взвешенное суммирование в форме

где каждая синусоида имеет периодичность 2π / n и смещение δ_n. Целью анализа Фурье является обнаружение этих коэффициентов. Чтобы доказать, почему это сходится, посмотрите мой полный отчет здесь (https://michaelsuntech.files.wordpress.com/2020/11/wim.pdf).

Исследование

Учитывая сложную периодическую функцию g на конечном интервале [t_1, t_2], которая может представлять (периодический) зашумленный сигнал, теория рядов Фурье позволяет нам разложить ее на сумму конечных N членов вида

Однако каждый «чистый» сигнал имеет фиксированную амплитуду, сдвиг и частоту, полученные из a_n, δ_n и n соответственно, причем большее значение n соответствует более высокой частоте.

Преобразование Фурье g на [-π, π], определенное как

где f означает частоту, вызывающую сильные всплески на частотах, на которых разложение дает высокие амплитуды. Результатом, который позволяет нам применить это к реальным проблемам, является взаимное соответствие между g и hat (g), что позволяет нам выполнить операцию на hat (g) и при этом восстановить исходный g, который в контексте мог бы редактировать один частотный канал из песни. Какая у этого временная сложность?

На практике g будет возникать при фиксированной частоте дискретизации и создавать вектор

а дискретное преобразование Фурье -

которое можно компактно описать матричным умножением hat (g) (x) = Wx таким, что

На практике умножение матриц имеет сложность O (N²), дорогостоящий процесс, но ее можно значительно уменьшить с помощью быстрого преобразования Фурье до O (N log N) (Легенда гласит, что он был впервые обнаружен Гауссом для мысленных расчетов, но опубликован только сто лет спустя). Я покажу как! Пусть N = 2N ’. Предположим, мы хотим вычислить

Наблюдать

где мы разделились

Фактически, эта операция по всем k может быть вычислена в виде матричного блока:

где

Позволяя записать вышеизложенное как

мы действительно можем проверить, WLOG 0≤ i ≤N’-1, что

Напомним, что умножение диагональной матрицы на вектор требует только O (N), поэтому, обозначая T (N) как количество вычислений, необходимых для вычисления W_N g (x), мы можем установить рекурсивное соотношение T (N) = O (N) + 2T (N ') + O (N) = O (N) + 2T (N'), и по основной теореме этого достаточно, чтобы заключить T (N) = O (N log N) . Одна удивительная особенность операции БПФ - это почти синоним обратного преобразования:

и мы можем показать

в силу того, что w ^ {n} = 1, и, следовательно,

с w ^ {l-k} = 1 тогда и только тогда, когда l = k, а все остальные l суммируются до 0, что является обычным приемом в рядах Фурье. Обозначая это обратное

в качестве «оператора Фурье» тогда имеем

Вот еще несколько приемов, которые мы можем проделать с оператором Фурье.

приравнивая к

где (Rx) _k = x_ {N-k}. Теперь мы увидим применение БПФ в машинном обучении. Если обозначить ∙, * свертку

операция, обозначая a = F_N (x), b = F_N (y), мы имеем

Эта манипуляция, кажущаяся просто уловкой, показывает, что скалярное произведение x и y в области Фурье представляет собой свертку областей Фурье x и y}. Это свойство, что не удивительно, сохраняется и в 2D, когда x, y∈ℝ ^ {N × N} представляют образец изображения и фильтр для выполнения этапа свертки x * y, важного этапа вычислений при обучении CNN, архитектуры модели. позади последних достижений в области глубокого обучения.

В 2D операция Фурье стоит O (N² log N²) = O (N² log N). Обычно фильтр w∈ℝ ^ K × K представляет собой скользящее окно по изображению для всего N² (K, K) сверток, которые стоят O (N² K²). Однако, добавляя w к размеру N × N и вычисляя

где ∙ имеет стоимость O (N²), теперь вся операция занимает всего O (N² log N)!

Вывод

Благодаря этому исследователи машинного обучения сообщили о значительном сокращении времени обучения (55 с → 0,4 с ???) с улучшенным шагом свертки O (N²K²) → O (N² log N), и у нас есть открытие Фурье. от ~ 200 лет назад, чтобы поблагодарить за это.