LCNN: Lookup-based Convolutional Neural Network

cvpr
cvpr2017
compression
fast-inference
sota
sparse-convolution

(Curtis Kim) #1

Abstract

Training LCNN involves jointly learning a dictionary and a small set of linear combinations.

DNN은 Overprametriziation 으로 평가받고 있고, 이를 줄이기 위한 노력이 많습니다. 이 논문은, Convolution Operation을 적은 수의 Dictionary로 한정해 연산 비용을 줄이겠다는 컨셉.

Sparse Convolution 이라는 측면에서는 최근 리뷰한 Mobilenet 과 같은 카테고리라고 볼 수 있습니다.

요약하면 아래와 같습니다.

  • Convolutional Filter를 더 적은 수의 Dictionary로 만듦
  • Dictionary를 Input에 직접 Convolve하고 이 결과를 Linear Combination을 통해 Filter 결과를 만듦
  • 위와 같은 컨셉은 학습이 불가한 combinatorial optimization 범주이므로, 몇가지 relaxation을 추가함
    • Dictionary에서 s 개만 추출해 사용하겠다는 Loopup Indices I 와 Coefficients $C$를 합쳐 Sparse Matrix P 로 만듦
    • Dictionary에서 s 개만 사용하겠다는 것은 l0-norm 이므로 이를 l1-norm으로 relax함. 이 때 weight에 threshold function을 activation처럼 추가해 이를 유사하게 구현했음
  • 결과
    • 속도 향상이 3배(성능차 거의 없음)~30배 수준(성능하락 10%)
    • few-shot / few-iteration learning 에도 유리함

Approach

Overview

Convolutional Layer는 Convolution Filter 라는 Weight Filter로 이루어져 있고, m 을 인풋 채널, k_wk_h 를 각각 인풋 사이즈(width, height)라고 할 때

m \times k_w \times k_h

수의 weight를 갖는 Convolution Filter가 아웃풋 채널 수인 n 만큼 있는 것을 말합니다. 물론 알려진 것처럼 각각의 필터는 꼭 필요하도록 학습되지는 않고, redundant 한 정보를 갖기도 합니다.

이 논문에서는 이 불필요한 정보를 줄일 수 있다고 보고, 상대적으로 적은 수의 Convolutional Dictionary 를 정의하고, Convolutional Filter는 Convolutional Dictionary의 Linear Combination 으로 정의했습니다.

그림으로 설명하면, 가장 왼쪽의 k개의 Dictionary의 일부를 Linear Combination을 해 가운데의 Convolution Filter를 만들어낸다는 것입니다.

Details

Definitions

Dictionary : D \in \mathbb{R}^{k \times m}

  • Convolution Filter 를 만들어 낼 적은 수의 딕셔너리

Lookup Indices : I \in \mathbb{N}^{s \times k_w \times k_h}

  • k 개의 Dictionary 중 일부를 뽑아낼 lookup index의 목록

Lookup Coefficients : C \in \mathbb{R}^{s \times k_w \times k_h}

  • 뽑혀진 s개의 Dictionary를 coefficient를 통해 linear combination을 해 최종적으로 weight filter를 만듦

즉, Weight Filter(Tensor)는

W_{[:,r,c]} = \sum_{t=1}^sC_{[t,r,c]} \cdot D_{[I_{[t,r,c],:}} \forall r,c

로 정의됩니다. 다시한번 풀어 설명하면, Dictionary D 에서 사용될 인덱스인 Loopup indices I 를 통해 꺼내온 후, Cofficients C 와 Linear Combination을 해 최종 필터를 만듭니다.

Speedup

개념적으로 적은 수의 Dictionary를 사용하니 전체적으로 Operation 수가 적어질 것 같다는 데까지는 동의할 수 있습니다. 논문에서는 이를 한번 더 빠르게 만듭니다.

Dictionary로 부터 Convolution Filter를 복원한 뒤 연산

하는 것이 아니라,

Dictionary를 Input Tensor에 연산한 뒤 Coefficients를 통해 Linear Combination으로 연산

하는 것을 제안합니다. Dictionary의 수가 Convolution Filter보다 적으니, 이렇게 하면 더 적은 연산양을 사용해 동일한 연산을 사용하게 됩니다. 이는 수식으로 표현하면 아래와 같고, 논문을 참고하세요.

image

이는 Sparse Matrix Multiplication이므로 OpenBlas 등을 이용해 빠르게 구현할 수 있습니다.

Training

문제는 Loopup Indices I 가 0, 1으로 표현되는 행렬이므로, Convolution Filter들로부터 Looup Indices $I$와 Coefficients $C$를 구하는 일은 Combinatorial Optimization이 되며, 논문에서는 ‘intractable’ 하다고 표현하고 있습니다. 따라서 이를 relax해서 end-to-end로 트레이닝할 수 있는 방법을 논문에서는 소개하고 있습니다.

relax하기 위해 먼저 dense matrix를 sparse matrix로 변경합니다. 즉 IC 를 합쳐 Sparse Tensor인 P 를 만듭니다.

image

그리고 이 P 를 convolution operation을 그대로 적용하되 P에 0이 아닌 값을 가질 수 있는 갯수를 s 로 제한하자는 것입니다. 문제는 l0-norm이 트레이닝이 불가한 함수라는 점이므로, 이 논문에서는 한 번 더 relax를 합니다.

l1-norm으로의 relax를 하면서, 한가지 조건을 넣습니다. weight의 크기가 threshold 이하인 경우 0으로 취급하겠다는 것입니다. l1-norm은 전체적인 벡터 크기는 줄일 수 있지만, non-zero element의 수를 줄일 수는 없기 때문에 이러한 조건을 넣은 것으로 보입니다.

image

위와 같은 threshold function을 weight 각각에 적용하게 되는데, 이는 activation function을 weight에 걸어버린 것 같아 신기하다는 생각을 했습니다. 또, 한번 0으로 변경된 weight는 이후 학습 과정에서 0을 벗어날 수 없으므로, 학습이 진행될수록 0인 element가 많아지게 된다는 점도 주목해야 합니다.

Results

Alexnet

image

ResNet-18

image

Trade-off

image

Few-shot Learning / Few-Iteration Learning

Dictionary가 일종의 Generalization을 돕는 역할을 해 few-shot learning이나 few-iteration learning에도 도움이 된다고 밝혔습니다.


Implementation

Torch Codes by Author

저자의 구현 내용을 보면, 디테일하게 이해할 수 있습니다.
저자는 트레이닝 코드만 공개하고
인퍼런스에 최적화된 코드는 공개하지 않았습니다.

우선 트레이닝을 위해 Sparse Convolution을 이용해 구현한 부분을 보겠습니다. 토치는 lua라는 언어를 이용하고, 기본적으로 2d convolution layer를 아래와 같이 제공합니다.

module = nn.SpatialConvolution(nInputPlane, nOutputPlane, kW, kH, [dW], [dH], [padW], [padH])

제공된 위 함수를 이용해서 아래와 같이 저자는 구현했습니다.

self.poolconv = cudnn.SpatialConvolution(nInputPlane, poolSize, 1, 1, 1, 1, padW, padH):noBias()
self.alignconv = cudnn.SpatialConvolution(poolSize, nOutputPlane, kW, kH, dW, dH, 0, 0)
self.m = nn.Sequential():add(self.poolconv):add(self.alignconv)

즉,

  • self.poolconv — dictionary를 이용하여 input layer에 convolution하는 부분
  • self.alignconv — 논문의 S Matrix에 Sparse한 P Matrix를 convolve 하는 부분

입니다. 논문에서 밝힌 것처럼 상대적으로 적은 수의 dictionary를 input layer에 convolve 하고, 이 때 얻어진 plane들에 대해 weight sum을 적절히 하도록 구현되어 있는 것입니다.

그런데 이 때 P Matrix는 Sparse Matrix로 특정 개수만 weight로 값을 갖고 나머지는 0으로 설계되어 있던 IC 를 Relax에 l1 norm을 추가한 것이므로 아래와 같은 regularizer가 추가됩니다.

   if self.lambda ~= 0 then
      self.gradRegularizer = self.gradRegularizer or self.alignconv.weight.new():resizeAs(self.alignconv.weight)
      self.gradRegularizer:sign(self.alignconv.weight)

      local lambda = self.lambda * self.sparseTh
      self.alignconv.gradWeight:add(lambda, self.gradRegularizer)
   end

   -- backprop the gradient through the threshold function
   self.alignconv.gradWeight[self.zeroMask] = 0

lambda 만큼의 weight을 갖으면서 weight sign 방향으로 gradient를 backpropagate 해주는 이유는 논문 내에서 아래의 수식을 그대로 구현한 것입니다.

image

참고로 zeroMask는 forward 할 때 threshold 아래의 weight를 0으로 만들었기 때문에, 해당 부분에 대해서는 gradient를 주지 않기 위해 처리된 부분입니다.

Tensorflow

직접 구현되고 있는 Github 입니다.

Tensorflow에서는 구조 상 조금 더 개발이 용이할 수 있습니다. Tensorflow 내에 제공되는 Convolutional Layer 구현 부분은 아래입니다.

self.kernel = self.add_variable(name='kernel',
                                    shape=kernel_shape,
                                    initializer=self.kernel_initializer,
                                    regularizer=self.kernel_regularizer,
                                    trainable=True,
                                    dtype=self.dtype)

앞서 소개한 것처럼 kernel weight에 activation function을 씌운 것 같은 개념이라고 했으므로 아래처럼 구현하면 됩니다.

# activation for kernel weight
self.kernel_pre = self.add_variable(name='kernel_pre',
                                    shape=kernel_shape,
                                    initializer=self.kernel_initializer,
                                    regularizer=self.kernel_regularizer,
                                    trainable=True,
                                    dtype=self.dtype)
conv_th = tf.ones_like(self.kernel_pre) * self.sparse_th
conv_zero = tf.zeros_like(self.kernel_pre)
cond = tf.less(tf.abs(self.kernel_pre), conv_th)
self.kernel = tf.where(cond, conv_zero, self.kernel_pre, name='kernel')

그리고 이렇게 구현된 lookup-convolution 에는 kernel regularizer로 l1-norm을 주면 논문에서 소개한 training 부분이 구현됩니다.

추가로, Inference 하는 코드는 텐서플로우의 기본 Operation으로만 작성하면 성능이 나오지 않기 때문에, 아래와 같이 Custom Operation으로 작성했고, 이는 필터의 Sparsity라는 특성을 활용한 것입니다. 역시 Eigen과 같은 라이브러리를 이용하면 최적화할 수 있는 여지가 더 있기는 합니다.

    for (int batch_idx = 0; batch_idx < input.shape().dim_size(0); batch_idx ++) {
        for (int sparse_idx = 0; sparse_idx < weight_indices.shape().dim_size(0); sparse_idx ++) {
            int sparse_oc = index_tensor(sparse_idx, 0);
            int sparse_p = index_tensor(sparse_idx, 1);
            int sparse_ic = sparse_p / (dense_shape_[1] * dense_shape_[2]);
            int sparse_ix = (sparse_p % (dense_shape_[1] * dense_shape_[2])) / dense_shape_[1];
            int sparse_iy = (sparse_p % (dense_shape_[1] * dense_shape_[2])) % dense_shape_[1];

            int sparse_v = values_tensor(sparse_idx);

            for (int row = 0; row < input.shape().dim_size(0); row += strides_[0]) {
                int out_row = row / strides_[0];
                for (int col = 0; col < input.shape().dim_size(1); col += strides_[1]) {
                    int out_col = col / strides_[1];

                    output_tensor(batch_idx, out_row, out_col, sparse_oc) += input_tensor(batch_idx, row + sparse_ix, col + sparse_iy, sparse_ic) * sparse_v;
                }
            }

        }
    }
```