高速フーリエ変換で畳み込みを高速化する方法 3. 離散フーリエ変換と畳み込みとは？

tmtk

2018.8.1

Topics

巡回畳み込みとは
離散フーリエ変換と巡回畳み込み
高速フーリエ変換で巡回畳み込みを高速化できる
高速フーリエ変換と巡回畳み込みの応用例
まとめ
参考文献

こんにちは。データサイエンスチームのtmtkです。
前回までの記事（1.離散フーリエ変換入門、2.高速フーリエ変換(FFT)入門）では、離散フーリエ変換と、それを高速に計算するアルゴリズムである高速フーリエ変換を紹介しました。今回の記事では、離散フーリエ変換を用いて畳み込みを高速に計算する話を紹介します。

巡回畳み込みとは

離散フーリエ変換と相性のよい処理として、巡回畳み込みという処理があります。巡回畳み込みの定義は以下のとおりです。
　[latex]N[/latex]を自然数として、[latex]x, y \in \mathbb{C}^N[/latex]を[latex]N[/latex]次元ベクトルとする。ただし、[latex]x(t+N) = x(t), y(t+N) = y(t) \, (t \in \mathbb{Z})[/latex]で[latex]x, y[/latex]を拡張し、周期[latex]N[/latex]をもつ整数値複素関数[latex]\mathbb{Z} \to \mathbb{C}[/latex]と同一視する。このとき、[latex]x, y[/latex]の巡回畳み込み[latex]x \ast y \in \mathbb{C}^N[/latex]を

[latex]\displaystyle (x\ast y)(t) = \sum_{s = 1}^N x(t-s)y(s) \,(t=1, \ldots, N)[/latex]
で定義します。
巡回畳み込みは、離散フーリエ変換と次のような関係があります。

離散フーリエ変換と巡回畳み込み

離散フーリエ変換と巡回畳み込みに関して、次が成り立ちます。

[latex]\displaystyle \mathcal{F}(x\ast y)= \left(\mathcal{F}(x)\right) \left(\mathcal{F}(y)\right)[/latex]
（ただし、[latex]\left(\mathcal{F}(x)\right) \left(\mathcal{F}(y)\right)[/latex]はベクトルの要素ごとの積（アダマール積）とします）。すなわち、巡回畳み込みの離散フーリエ変換は、離散フーリエ変換の要素ごとの積で計算できます。この性質は直接の計算により容易に証明することができます。

高速フーリエ変換で巡回畳み込みを高速化できる

高速フーリエ変換を使うと、巡回畳み込みの計算を高速化することが可能です。
巡回畳み込みは、定義にしたがって素朴に計算すると[latex](x \ast y)(t)[/latex]を計算するのに[latex]N[/latex]回の掛け算と[latex]N-1[/latex]回の足し算が必要です。それを次元の数[latex]N[/latex]回だけ繰り返し計算するので、全体の計算量は[latex]O\left( \left(N+\left(N-1\right)\right)\times N\right) = O(N^2)[/latex]になります。
　一方で、先ほど離散フーリエ変換と巡回畳み込みの性質から

[latex]\displaystyle x\ast y = \mathcal{F}^{-1}\mathcal{F}(x\ast y)= \mathcal{F}^{-1}\left(\left(\mathcal{F}(x)\right) \left(\mathcal{F}(y)\right)\right)[/latex]
が成り立ちます。すなわち、巡回畳み込みを計算するには、[latex]x, y[/latex]の離散フーリエ変換を計算し、それらの要素ごとの積を計算し、その逆離散フーリエ変換を計算すればいいです。この方法だと、計算量が各ステップで[latex]O(N\log N), O(N), O(N\log N)[/latex]なので、全体の時間計算量は[latex]O(N\log N)[/latex]になります。
つまり、高速フーリエ変換を使うことで、巡回畳み込みの計算量が[latex]O(N^2)[/latex]から[latex]O(N\log N)[/latex]に削減できます。

高速フーリエ変換と巡回畳み込みの応用例

巡回畳み込みを高速フーリエ変換で高速化することの応用例として、機械学習における畳み込みへの応用を紹介します。
機械学習において、畳み込みとは以下のような処理です。いま、入力が1次元の場合を考えることにします。畳み込みカーネルを[latex]K \in \mathbb{R}^n[/latex]とするとき、入力[latex]I \in \mathbb{R}^N[/latex]に対するカーネル[latex]K[/latex]による畳み込み[latex]I\oast K \in \mathbb{R}^N[/latex]は、[latex]1 \leq t \leq N[/latex]に対して

[latex]\displaystyle (I\oast K)(t) = \sum_{s=1}^n I(t+s-1)K(s) [/latex]
で定義されます。（通常は[latex]I\ast K[/latex]と書かれますが、ここでは巡回畳み込みと区別するために[latex]I\oast K[/latex]と書くことにします。）
畳み込みは、古典的な画像処理や最近流行りのディープラーニングでも用いられています。画像認識の本やディープラーニングの本に詳しいことが書かれています。
さて、この畳み込みは巡回畳み込みを使って計算することができます。例として、[latex]I = (I(1), I(2), I(3), I(4))^T, K = (K(1), K(2))^T[/latex]の場合を考えます。[latex]5[/latex]次元ベクトル[latex]\tilde I, \tilde K[/latex]を[latex]\tilde I = (I(1), I(2), I(3), I(4), 0)^T, \tilde K = (0, 0, 0, K(2), K(1))^T[/latex]で定めれば、巡回畳み込み[latex]\tilde I \ast \tilde K[/latex]は
[latex]\tilde I \ast \tilde K = (I(1)K(1)+I(2)K(2), I(2)K(1)+I(3)K(2), I(3)K(1)+I(4)K(2), I(4)K(1), I(1)K(2))^T[/latex]
と計算されます。これの第1要素から第4要素までを抜き出したものが、畳み込み[latex]I\oast K[/latex]と一致します。このようにして、機械学習における畳み込みを巡回畳み込みを使って計算することができます。
機械学習における畳み込みの計算量は[latex]O(Nn)[/latex]ですが、高速フーリエ変換と巡回畳み込みを応用することで計算量を[latex]O(N\log N)[/latex]にすることができます。これは、データのサイズ[latex]N[/latex]が大きく、かつカーネルのサイズ[latex]n[/latex]がデータのサイズ[latex]N[/latex]に近い場合に有効です。
その他にも、多倍長整数の掛け算などを高速フーリエ変換を使って高速化できるようです。