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

Data Science

2018.8.1

Topics

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

巡回畳み込みとは

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

\displaystyle (x\ast y)(t) = \sum_{s = 1}^N x(t-s)y(s) \,(t=1, \ldots, N)

で定義します。
巡回畳み込みは、離散フーリエ変換と次のような関係があります。

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

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

\displaystyle \mathcal{F}(x\ast y)= \left(\mathcal{F}(x)\right) \left(\mathcal{F}(y)\right)

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

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

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

\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)

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

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

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

\displaystyle (I\oast K)(t) = \sum_{s=1}^n I(t+s-1)K(s)

で定義されます。(通常はI\ast Kと書かれますが、ここでは巡回畳み込みと区別するためにI\oast Kと書くことにします。)
畳み込みは、古典的な画像処理や最近流行りのディープラーニングでも用いられています。画像認識の本やディープラーニングの本に詳しいことが書かれています。
さて、この畳み込みは巡回畳み込みを使って計算することができます。例として、I = (I(1), I(2), I(3), I(4))^T, K = (K(1), K(2))^Tの場合を考えます。5次元ベクトル\tilde I, \tilde K\tilde I = (I(1), I(2), I(3), I(4), 0)^T, \tilde K = (0, 0, 0, K(2), K(1))^Tで定めれば、巡回畳み込み\tilde I \ast \tilde K
\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

と計算されます。これの第1要素から第4要素までを抜き出したものが、畳み込みI\oast Kと一致します。このようにして、機械学習における畳み込みを巡回畳み込みを使って計算することができます。
機械学習における畳み込みの計算量はO(Nn)ですが、高速フーリエ変換と巡回畳み込みを応用することで計算量をO(N\log N)にすることができます。これは、データのサイズNが大きく、かつカーネルのサイズnがデータのサイズNに近い場合に有効です。
その他にも、多倍長整数の掛け算などを高速フーリエ変換を使って高速化できるようです。

まとめ

この記事では、巡回畳み込みを定義し、フーリエ変換の積が巡回畳み込みの離散フーリエ変換と等しいことを紹介しました。また、その応用として、機械学習における畳み込みを高速フーリエ変換を使って高速化できることを紹介しました。

参考文献

tmtk

データ分析と機械学習とソフトウェア開発をしています。 アルゴリズムとデータ構造が好きです。

Recommends

こちらもおすすめ

Special Topics

注目記事はこちら