可分な畳み込みカーネルと計算量の話

tmtk

2018.7.18

Topics

畳み込みとは
Pythonで書く畳み込み処理
可分な畳み込みカーネル
それぞれの方法の計算量
実際の計算時間
まとめ
参考文献

こんにちは。データサイエンスチームのtmtkです。
この記事では、可分なカーネルによる畳み込みと計算量の説明をします。

畳み込みとは

はじめに畳み込みを復習します。
機械学習において、畳み込みとは以下のような処理です。いま、入力が2次元の場合を考えることにします。畳み込みカーネルを $K \in \mathbb{R}^{n_1\times n_2}$ とするとき、入力 $I \in \mathbb{R}^{N_1\times N_2}$ に対するカーネル $K$ による畳み込み $I\ast K \in \mathbb{R}^{N_1 \times N_2}$ は、 $1 \leq x \leq N_1, 1 \leq y \leq N_2$ に対して

$\displaystyle (I\ast K)(x, y) = \sum_{1 \leq k \leq n_1}\sum_{1\leq l \leq n_2} I(x+k-1, y+l-1)K(k, l)$
で定義されます。
畳み込みは、古典的な画像処理や最近流行りのディープラーニングでも用いられています。画像認識の本やディープラーニングの本に詳しいことが書かれています。

Pythonで書く畳み込み処理

Pythonで実際に畳み込み処理を書いてみます。コンピュータで処理するため、入力 $I$ とカーネル $K$ は0-originなindexを持つとします。つまり、行列として表示すると

$I = \left(\begin{matrix} I(0, 0) & \cdots & I(0, N_2-1) \\ \vdots & \ddots & \vdots \\ I(N_1-1, 0) & \cdots & I(N_1-1, N_2-1) \\ \end{matrix}\right), K = \left(\begin{matrix} K(0, 0) & \cdots & K(0, n_2-1) \\ \vdots & \ddots & \vdots \\ K(n_1-1, 0) & \cdots & K(n_1-1, n_2-1) \\ \end{matrix}\right)$
となります。
いま、入力のサイズを $N=N_1=N_2=10$ 、カーネルのサイズを $n=n_1=n_2=3$ 、入力データを $I(x, y) = 1 (0 \leq x, y \leq N-1)$ 、カーネルを $K(x, y) = 1(0 \leq x, y \leq n-1)$ とします。

N = 10
n = 3
image = [[1] * N for _ in range(N)]
kernel = [[1] * n for _ in range(n)]

すると、畳み込み $I\ast K$ を計算するPythonの関数は以下のように書くことができます。

def convolution(image, kernel):
    N1 = len(image)
    N2 = len(image[0])
    n1 = len(kernel)
    n2 = len(kernel[0])
    res = [[0] * N2 for _ in range(N1)]
    for i in range(N1):
        for j in range(N2):
            for k in range(min(n1, N1 - i)):
                for l in range(min(n2, N2 - j)):
                    res[i][j] += image[i+k][j+l] * kernel[k][l]
    return res

実際に計算してみると、

convolution(image, kernel)

以下のような畳み込み $I\ast K$ の計算結果を得ます。

[[9, 9, 9, 9, 9, 9, 9, 9, 6, 3],
 [9, 9, 9, 9, 9, 9, 9, 9, 6, 3],
 [9, 9, 9, 9, 9, 9, 9, 9, 6, 3],
 [9, 9, 9, 9, 9, 9, 9, 9, 6, 3],
 [9, 9, 9, 9, 9, 9, 9, 9, 6, 3],
 [9, 9, 9, 9, 9, 9, 9, 9, 6, 3],
 [9, 9, 9, 9, 9, 9, 9, 9, 6, 3],
 [9, 9, 9, 9, 9, 9, 9, 9, 6, 3],
 [6, 6, 6, 6, 6, 6, 6, 6, 4, 2],
 [3, 3, 3, 3, 3, 3, 3, 3, 2, 1]]

可分な畳み込みカーネル

ところで、いま与えた畳み込みカーネル $K(x, y) = 1(0 \leq x, y \leq N-1)$ は可分なカーネルの例になっています。2次元のカーネル $K \in \mathbb{R}^{n_1\times n_2}$ が可分であるとは、二つのベクトル $K_1 = (K_1(1), \ldots, K_1(n_1))^T, K_2 = (K_2(1), \ldots, K_2(n_2))^T$ によって $K = K_1 K_2^T$ と書けることをいいます。先ほどのカーネル $K(x, y) = 1(0 \leq x, y \leq N-1)$ は、

$\displaystyle K = \left(\begin{matrix}1 & \cdots & 1 \\ \vdots & \ddots & \vdots \\ 1 & \cdots & 1\end{matrix}\right) = \left(\begin{matrix} 1 \\ \vdots \\ 1\end{matrix}\right)\left(\begin{matrix} 1 \cdots 1 \end{matrix}\right) = K_1 K_2^T$
（ただし $K_1 = K_2 = (1, \ldots, 1)^T \in \mathbb{R}^n$ ）と書けるので、実際に可分なカーネルになっています。
　可分なカーネルの例としては、他にも平均値をとるカーネル
$\displaystyle K = \frac{1}{n^2}\left(\begin{matrix}1 & \cdots & 1 \\ \vdots & \ddots & \vdots \\ 1 & \cdots & 1\end{matrix}\right)$
や、ガウス関数から作られるカーネル
$\displaystyle K(x, y) = \frac{1}{2\pi\sigma^2}\exp\left(-\frac{x^2+y^2}{2\sigma^2}\right)$
などがあります。
可分なカーネル $K = K_1 K_2^T$ に対しては、以下の等式が成り立ちます。
$\displaystyle I\ast (K_1 K_2^T) = (I\ast K_1)\ast K_2^T$
証明は簡単なので省略します。
それでは、この性質を使って先ほどの畳み込みを計算してみましょう。関数convolution_separableは可分なカーネル $K=K_1K_2^T$ での畳み込み $I\ast K = I\ast (K_1K_2^T)$ を $(I\ast K_1)\ast K_2^T$ で計算する関数です。

kernel1 = [1]*n
kernel2 = [1]*n
def convolution_separable(image, kernel1, kernel2):
    N1 = len(image)
    N2 = len(image[0])
    n1 = len(kernel1)
    n2 = len(kernel2)
    res = [[0] * N2 for _ in range(N1)]
    tmp = [[0] * N2 for _ in range(N1)]
    for i in range(N1):
        for j in range(N2):
            for k in range(min(n1, N1 - i)):
                tmp[i][j] += image[i+k][j] * kernel1[k]
    for i in range(N1):
        for j in range(N2):
            for l in range(min(n2, N2 - j)):
                res[i][j] += tmp[i][j+l] * kernel2[l]
    return res
convolution_separable(image, kernel1, kernel2)

[[9, 9, 9, 9, 9, 9, 9, 9, 6, 3],
 [9, 9, 9, 9, 9, 9, 9, 9, 6, 3],
 [9, 9, 9, 9, 9, 9, 9, 9, 6, 3],
 [9, 9, 9, 9, 9, 9, 9, 9, 6, 3],
 [9, 9, 9, 9, 9, 9, 9, 9, 6, 3],
 [9, 9, 9, 9, 9, 9, 9, 9, 6, 3],
 [9, 9, 9, 9, 9, 9, 9, 9, 6, 3],
 [9, 9, 9, 9, 9, 9, 9, 9, 6, 3],
 [6, 6, 6, 6, 6, 6, 6, 6, 4, 2],
 [3, 3, 3, 3, 3, 3, 3, 3, 2, 1]]

先ほどの計算方法と同じ結果を得ることができます。

それぞれの方法の計算量

それぞれの計算方法について、処理時間を見積もってみましょう。
最初の方法では、関数convolutionに四重ループ

    for i in range(N1):
        for j in range(N2):
            for k in range(min(n1, N1 - i)):
                for l in range(min(n2, N2 - j)):

があり、ループが約 $N_1\times N_2 \times n_1 \times n_2$ 回実行されます。いま、 $N = \max(N_1, N_2), n = \max(n_1, n_2)$ とおけば、ループの回数は $N^2n^2$ 回以下です。そのため、この関数の処理時間は $N^2n^2$ にほぼ比例すると考えることができます。このような状況をさして、この関数は時間計算量が $O(N^2n^2)$ であるといいます。
それに対して、可分なカーネルに対する畳み込みでは、関数convolution_separableに以下の2つの三重ループがあります。

    for i in range(N1):
        for j in range(N2):
            for k in range(min(n1, N1 - i)):

    for i in range(N1):
        for j in range(N2):
            for l in range(min(n2, N2 - j)):

そのため、このconvolution_separableの処理時間は $2\times N^2n$ にほぼ比例すると考えることができ、時間計算量は $O(N^2n)$ です（ $O(f(n))$ と書くときは、定数倍を無視します）。
したがって、計算量がそれぞれ $O(N^2n^2), O(N^2n)$ で、前者より後者のほうが小さいため、 $n$ が大きいとき関数convolutionよりconvolution_separableのほうが計算時間が短くなることが予想できます。

実際の計算時間

それでは、時間計算量が実際の計算時間に及ぼす影響を観察するため、どれくらいの処理時間がかかるのか計測してみます。
　計算環境はCore i7が載っている普通のパソコン上の仮想マシンです。 $N_1 = N_2 = N=1000$ として、 $n_1 = n_2 = n$ を変動させながら、畳み込み処理にかかった時間をIPythonのマジックコマンド%timeで計測します。

N = 1000
image = [[1] * N for _ in range(N)]

たとえば、 $n = 10$ のとき、次のようなコードで処理時間を算出します。

n = 10
%time convolution(image, [[1] * n for _ in range(n)])
%time convolution_separable(image, [1]*n, [1]*n)

結果は以下のようになります。関数convolutionの処理時間が $n^2$ に比例していることと、関数convolution_separableの処理時間が $n$ に比例していることが観察できます。

ここから推定すると、 $n = 500$ のとき、convolutionの処理時間はおよそ10時間程度かかってしまうのにたいして、convolution_separableの処理時間はたったの2分程度になります。時間計算量が $O(N^2n^2), O(N^2n)$ と異なるため、 $n$ が大きくなると処理時間の差も大きくなっていきます。
このように、大きいデータを処理するとき、時間計算量を考慮することは重要です。

まとめ

この記事では、可分なカーネルでの畳み込みの効率的な計算方法と、それによる時間計算量の差について説明しました。可分なカーネルでの畳み込みは、通常の畳み込みよりも高速に計算することができます。時間計算量の差は大きなデータになると実際の処理時間の差に如実に現れてくるので、時間計算量を考慮したアルゴリズムを設計することが大切です。