cdjs의 코딩 공부방

* 모든 코드는 제 깃허브 (cdjs1432/DeepLearningBasic: Deep Learning from scratch)에서 확인할 수 있습니다.

이번 시간에는 Convolution 연산 (Forward, Backward)에 대해 다뤄보겠습니다.

Convolution 연산은 본질은 굉장히 단순합니다. filter를 왼쪽에서 오른쪽으로, 위에서 아래로 이미지에 대고 점곱을 하면 되기 때문입니다.

하지만, 이는 생각보다 그리 단순하지 않습니다.

우선, 위의 이미지의 경우는 단순히 1장의 1-Channel 이미지의 예시이기 때문에 간단하게 대략 이미지의 크기만큼만 연산을 해 주면 됩니다.

하지만, 우리가 train할 때 사용하는 이미지는 4차원 (batch_size, channel, h, w)이므로 연산이 매우 복잡해 집니다.

예를 들어, 위의 2차원 이미지는 단순히 2중 for문으로 구현이 가능하지만, 4차원의 경우에는 4중 for문이 필요하게 됩니다.

또, 시간 복잡도도 너무 커집니다.

저번 차시에 썼던 out_h, out_w를 가져와서 설명해 보겠습니다.

간단하게 생각해서, pad=0, stride=1인 경우, out_w는  1 + w - fw가 되고, out_h는 1 + h - fh가 됩니다.

이 때, 이미지 크기 h, w에 대하여, 단 한 장의 2차원 이미지의 연산을 위해서 out_w * out_h만큼의 점곱 연산이 필요합니다.

MNIST dataset의 이미지 크기가 28*28인 것을 생각해 보면, (3, 3) 필터를 사용하였을 경우 단 한장의 이미지의 convolution을 위해서는 무려 26*26, 즉 676회의 점곱 연산이 필요합니다.

만약 50000개의 이미지 전체를 모두 Convolution 연산을 한다면, 676*50000, 즉 33,800,000회라는 무시무시한 양의 연산이 필요하게 됩니다.

만약 Convolution Layer가 두개가 겹쳐져서 Channel이 32개가 되었다면? 저 횟수의 32배를 연산해야 하는 것이죠.

게다가 컴퓨터 (또는 numpy libarary)는 점곱 연산은 아주 빠르게 수행하지만, 해당 점곱을 각각의 배열에 집어넣고 더하고... 하는 과정은 상대적으로 느리게 수행됩니다.

따라서, 점곱 연산의 횟수를 줄이는 것이 시간 복잡도와, 우리 코드의 복잡도 모두를 해결할 수 있습니다.

그렇다면 어떻게 시간 복잡도를 최적화 할 수 있을까요? 잠시 생각해 봅시다.

우선, 위 연산의 본질을 생각해 봅시다.
필터의 각각의 부분 (위 이미지에선 1, 2, 3, -4, 7, 4, 2, -5, 1)은 사실, 이미지의 특정 픽셀들과만 연산을 하게 됩니다.
가령, 필터 왼쪽 위 1은 이미지의 우측 하단 부분을 아예 연산하지 않습니다.

즉, filter의 각 부분은 애초에 이미지의 어떤 부분과 곱셈을 수행하는지 정해져 있다는 것입니다.

그렇다면, filter의 각 부분에 연산해야 할 부분만을 빼서, 각 필터와의 단 한번의 곱셈으로 바꾸면 어떨까요?

filter의 각 부분에 해당하는 부분들을 각각 배서, filter와의 점곱으로 연산을 하면 단 한번의 점곱으로 마무리 지을 수 있지 않을까요?

해당 방식을 구체화 한 것이 바로 Im2col 알고리즘입니다.

Im2col 방식은, 말 그대로 Image를 Column으로 바꾸는 알고리즘입니다.

4차원 이미지인 input image와 filter를 둘 다 2차원 행렬로 만들어서, 점곱으로 연산이 가능하게 하는 것입니다.

위 이미지를 예시로 설명하겠습니다.

위 이미지에서는 빨간색, 초록색, 파란색으로 channel을 구분하고 있습니다.

첫 번째 channel의 filter인 F0은 D0, D1, D3, D4와만 연산이 되니, 해당 이미지 값들을 빼서 하나의 Column으로 만들어 줍니다.

이 행동을 모든 filter F0, F1, F2, F3에 반복해 줍니다.

그렇게 하면 오른쪽처럼 이미지의 Column이 생성됩니다.

또, 이를 각각의 filter마다, 각각의 channel마다 반복해 주면, 행렬 두개가 만들어지게 됩니다.

(참고로, 모든 필터의 각각의 부분은 모두 동일한 부분과만 연산하므로, filter의 행렬은 filter를 reshape한 것과 동일한 결과가 나오게 됩니다.)

이 방법은 사실, 원래 단 한번씩만 등장하던 이미지의 픽셀값이 여러 번 중복되어 여러번 나타나기 때문에 공간 복잡도가 커지게 된다는 단점이 있습니다.

하지만, 그렇게 해서 낭비되는 공간보다 아낄 수 있는 시간 복잡도가 훨씬 높기에(원본 conv의 약 200배 속도), 이 방식은 자주 사용됩니다.

이제, 이 Im2col 함수를 코드로 구현해 볼까요?

def im2col(input_data, filter_h, filter_w, stride=1, pad=0):
    N, C, H, W = input_data.shape
    out_h = (H + 2 * pad - filter_h) // stride + 1
    out_w = (W + 2 * pad - filter_w) // stride + 1

    img = np.pad(input_data, [(0, 0), (0, 0), (pad, pad), (pad, pad)], 'constant')
    col = np.zeros((N, C, filter_h, filter_w, out_h, out_w))

    for y in range(filter_h):
        y_max = y + stride * out_h
        for x in range(filter_w):
            x_max = x + stride * out_w
            col[:, :, y, x, :, :] = img[:, :, y:y_max:stride, x:x_max:stride]

    col = col.transpose(0, 4, 5, 1, 2, 3).reshape(N * out_h * out_w, -1)
    return col

코드를 살펴봅시다.

우선, input data에서 이미지의 개수, channel, 그리고 가로세로 길이를 구한 뒤 out_h, out_w를 지정해 줍니다.

그 뒤, input_data에 padding을 해 줍니다. (np.pad...)

다음으로, 이미지의 행렬을 담을 col을 ((이미지 크기, channel, filter 세로, filter 가로, out 세로, out 가로))의 크기로 만들어 줍니다.

이 크기로 만들어 주는 이유는, 어차피 모든 이미지 개수(N)와 channel(C)마다 동일한 연산을 해 줄 것이고, filter 하나의 행렬의 크기가 바로 (filter_h, filter_w)이기 때문입니다.

그리고, filter_h와 filter_w의 크기에 대하여, for loop를 돌아줍니다.

각 filter의 원소마다 연산해 줄 이미지를 추출하기 위함입니다.

col[:, :, y, x, :, :] = img[:, :, y:y_max:stride, x:x_max:stride]가 바로 이미지를 추출하는 부분입니다.

y:y_max:stride는, y에서부터 y_max까지, stride식 건너뛰면서 index를 추출하라는 의미입니다.

(참고로, col의 순서를 위처럼 한 것도 이런 대입 연산이 필요하기 때문입니다.)

마지막으로, 이 column을 reshape해주기 위해 transpose해 줍니다.

이렇게 transpose하지 않으면 reshape 시에 원래 우리가 의도했던 행렬이 아니라, 어딘가 뒤틀린 행렬이 됩니다.

이렇게 만들어진 col을 return하면, 이 함수의 일이 끝나게 됩니다.

def col2im(col, input_shape, filter_h, filter_w, stride=1, pad=0):
    N, C, H, W = input_shape
    out_h = (H + 2 * pad - filter_h) // stride + 1
    out_w = (W + 2 * pad - filter_w) // stride + 1
    col = col.reshape(N, out_h, out_w, C, filter_h, filter_w).transpose(0, 3, 4, 5, 1, 2)

    img = np.zeros((N, C, H + 2 * pad + stride - 1, W + 2 * pad + stride - 1))
    for y in range(filter_h):
        y_max = y + stride * out_h
        for x in range(filter_w):
            x_max = x + stride * out_w
            img[:, :, y:y_max:stride, x:x_max:stride] += col[:, :, y, x, :, :]

    return img[:, :, pad:H + pad, pad:W + pad]

이 im2col의 자매품? 으로, col2im이라는 함수도 있습니다.

Convolution의 backward 연산에 활용되는 함수로, im2col로 만들어진 column에서 원본 이미지로 바꿔주는 함수입니다.

위의 im2col을 거의 그대로 반대로 했을 뿐이므로, 설명은 생략하겠습니다.

이렇게, Convolution 연산의 준비가 모두 끝났습니다! 이제 직접 Convolution 연산을 구현해 봅시다.

    def forward(self, x):
        # Convolution Calculation
        self.x = x
        fn, fc, fh, fw = self.param.shape
        n, c, h, w = x.shape

        out_h = int(1 + (h + 2 * self.pad - fh) / self.stride)
        out_w = int(1 + (w + 2 * self.pad - fw) / self.stride)

        # Conv Input Size: (Channel, Filter_num, kernel_h, kernel_w)
        # Change this using im2col
        col = im2col(x, self.kernel_size[0], self.kernel_size[1], self.stride, self.pad)
        col_param = self.param.reshape((fn, -1)).T

        self.col = col
        self.col_param = col_param
        out = np.dot(col, col_param)
        out = out.reshape(n, out_h, out_w, -1).transpose(0, 3, 1, 2)
        return out

윗부분 (~out_w... 부분까지)는 지금까지 계속 설명해 왔던 것이므로 설명을 생략하고, 연산 부분만 간단히 보겠습니다.

우선, im2col 함수를 활용하여 input_data인 x를 column으로 바꿔 줍니다.

그리고, Convolution parameter, 즉 filter 또한 행렬로 바꿔주어야 합니다.

그런데 이 연산은 매우 간단하게 수행이 가능한데, 위에서 봤듯이 filter의 경우는 그냥 filter의 개수만큼 쭉 펴주기만 하면 됩니다.

그리고 그냥 점곱을 한번 해 주면, 간단하게 output 값이 나오게 됩니다.

이제, 이 output 값을 원래 크기대로 reshape 및 transpose해주기만 하면, forward 연산은 종료됩니다.

    def backward(self, dout):
        fn, c, fh, fw = self.param.shape
        dout = dout.transpose(0, 2, 3, 1).reshape(-1, fn)

        self.grad = np.dot(self.col.T, dout)
        self.grad = self.grad.transpose(1, 0).reshape(fn, c, fh, fw)

        dcol = np.dot(dout, self.col_param.T)
        dx = col2im(dcol, self.x.shape, fh, fw, self.stride, self.pad)

        return dx

backward 연산도 비교적 간단합니다.

forward와 반대로, 들어온 dout 값을 transpose한 뒤 reshape해 줍니다.

그리고, MulLayer의 backward함수와 동일하게 (어차피 곱하기만 하므로...) grad를 구해주면 됩니다.

사실 연산 자체는 점곱을 하는 MulLayer와 동일하지만, 단지 transpose와 reshape, col2im만 더해졌다고 보면 됩니다.

이렇게, Convolution Layer의 forward와 backward 연산을 마칩니다.

다음 시간에는 Pooling Layer (Maxpooling, Average Pooling...)을 구현해 보겠습니다.