Shift-CNN
Shift: A Zero FLOP, Zero Parameter Alternative to Spatial Convolutions
CVPR 2017
Bichen Wu, Alvin Wan∗ , Xiangyu Yue∗ , Peter Jin, Sicheng Zhao, Noah Golmant, Amir Gholaminejad, Joseph Gonzalez, Kurt Keutzer UC Berkeley
Introduction
기존의 CNN은 대개 $3 \times 3$ Filter를 sliding window 기법에 따라 이미지에 적용함으로써 공간정보를 활용했다. 그런데 이 방법은 filter가 반복하는 횟수만큼, 그리고 filter의 크기에 비례하여 연산량이 급격하게 증가하는 단점이 있다. 때문에 연산량도 줄이고 성능도 향상/유지 시킬수 있는 ShiftNet을 제안한다.
Method
입력된 채널마다 Shift 를 적용시켜 공간정보를 섞은 후 $1*1$ conv를 적용시킨다. 기존의 CNN이라면 필터단위로 공간정보를 취합하여 conv했지만 여기서는 단 하나의 공간위치만을 사용한다. Shift 연산에 따라 특정 채널의 값이 0이 될수도 있다.
Shift Operation
Shift kernel은 각 채널의 feature가 어느 방향으로 움직일지를 결정한다. $D_{k}$ = 3 일때, 총 9가지의 방향이 나온다.
해당 방향대로 데이터값이 이동하며, 빈 부분은 0으로 채워진다.
Shif Kernel
Shift kernel size가 $D_{k}$이고 채널이 $M$ 일 때, 가능한 shift 방향의 경우의 수는 $(D_{k}^{2})^{M}$ 가 나온다. 모든 경우에 대해 최적의 해를 구하기 어려우므로 연산량을 줄이기 위해 $M$개의 채널을 $D_{k}^{2}$로 나누는 일종의 해싱기법을 이용한다.
$D_{k}= 2, M=10$ 일 때 총 4개의 방향이 나오고 각 방향에는 2개의 채널이 할당되고 남은 2개의 채널은 'center' 그룹으로 shift 하지 않는다. ( 이때 RoundDown($ \frac{M}{D_{k}^{2}}$) 개의 그룹이 나온다.)
하지만 여전히 어떤 그룹에 어떤 채널을 할당되어야 최적의 해가 나오는지 알 수 없다. 때문에 input과 output이 channel-order에 invariant할 수 있도록 permutation 을 추가한다.
Permutation operator $P_{1}$는 discrete (이산)하므로 최적화가 어렵기 때문에, point-wise convolution으로 mapping 하여 $\hat{P}_{\pi 1}$ 형태로 활용한다.
Permutation $P_{1}$은 전단사함수 ( 모든 경우에 대해 여집합 없이 1:1 대응이 가능) 이므로 $P_{1} \circ P_{\pi 1} $ 과 $\hat{P}_{\pi 1}$ 또한 전단사 관계이다. 따라서 $\hat{P}_{\pi 1}$ 를 직접 활용하여 학습 할 수 있다.
Shift kernel $K_{\pi}$는 $\hat{P}_{\pi 1}$과 $\hat{P}_{\pi 2}$ 사이의 sandwitch가 되어 모든 경우의 shift, permutation에 동일한 결과를 보인다.
** 이산적이면 최적화하기 어렵고, 불연속이기 때문에 미분할 수 없다.