정말 오랜만에 블로그 포스팅을 진행하는 거 같습니다.
최근 서강대학교의 권해용님과 YOLO Darknet의 코드 리뷰를 진행하고 나서, Binary Neural Network에 대해서 공부하고 있습니다. 너무 오랫동안 기록 없이 스터디만 진행해왔고, 최근 너무 방대한 내용들이 기록되지 않은 상태로 남아있어서 이제 슬슬 기록을 진행해볼까 합니다.
이번 포스팅은 [Binarized Neural Networks: Training Neural Networks with Weights and Activations Constrained to +1 to -1:: https://arxiv.org/pdf/1602.02830.pdf] 에 대해서 논문 리뷰를 진행하도록 하겠습니다.
Binary Neural Network의 구현체는 해당 링크에 있습니다.
해당 논문을 선정한 이유는 XNOR Net등의 트렌디한 논문 이전의 Binary Neural Network의 기본이 되는 논문 중에, 저희 수준에서 소화가 가능한 논문이라고 판단되어 선정하게 되었습니다.
1. Abstract
2. Binarized Neural Networks
2-1. Deterministic vs Stochastic Binarization
논문에서의 BNN은 weights과 activations를 +1과 -1로 제한합니다. 실제의 real value의 값을 +1과 -1로 제한하는 transformation method에는 Deterministic과 Stochastic 이렇게 두가지 방법이 있습니다.
Deterministic Method는 real value를 +1과 -1로 제한할 때, 다음과 방법을 사용합니다.
여기서 
Stochastic Method는 다음과 같습니다.
여기서 
논문에서는 Stochastic Method가 그냥 딱 봐도 매력적이지만, 해당 내용을 Implementation하는 과정에서 Quantizing할 때, Random bits를 만들어내는 난수 생성기가 필요한데, 이게 만들기 너무 어려우니 Deterministic Method를 사용하자 합니다.
(그거까지 하기 싫었던거지? 응? 응?)
2-2. Gradient Computation and Accumulation
일반적으로 SGD(Stochastic Gradient Descent)는 noisy steps으로 가는데, (여기서 noisy steps이라는 것은, 말 그대로 Stochastic이니까, Full Batch Data의 Gradient로 Update가 일어나는게 아니라, Global Convex방향이 아닌 그것과는 조금 다른 방향을 noisy steps이라고 이야기하는 것 같습니다.) 결국 누적된 SGD의 Gradient는 Global한 관점으로 봤을 때는, Global Convex방향으로 수렴된다고 이야기합니다.(averaged out). 따라서 저자주장은 SGD를 통해서 학습할 때, 중요한 것은 충분한 양의 gradient의 누적이라고 이야기합니다.
게다가, 우리들이 이전에 네트워크에 했던 여러가지 짓들 (Drop out 등등)이 Regularizer역활을 해서 네트워크가 generalization해지는 영향을 가져왔는데, BNNs을 학습하는 방법이 Dropout의 변형이라고 볼 수 있다고 이갸기합니다.
2-3. Propagating Gradients Through Discretization
앞에서 이야기했듯이 Deterministic하게 Quantization을 하는 방법은 다음과 같았습니다.
Gradient 
해당 식은, Gradient를 보존하고, 
BNNs의 Hidden unit에서는 비선형성을 주기 위해 
Weight Update시
이라는 값 밖의
을 가져왔을 때(알고리즘 1에 따라서 학습 중에 가중치를 클립핑 할 때),
의 값을 -1과 1값으로 projecting하는 것을 통해서 각각의 real value weights를 -1과 1사이의 값으로 제한합니다. 여기서 실수 가중치(
) 값은 binary weight에 아무런 영향을 주지 않으면서 크게 증가합니다.
weights
을 사용할 때, 이는 다음과 같이 quantize됩니다.
이것은 
2-4. Shift based Batch Normalization
다들 잘 아시다시피 Batch Normalization(BN)은 모델을 정규화하는데 도움이 될 수 있습니다. 하지만 Batch Normalization은 학습때, 많은 Multiplication(standard deviation을 계산하고 그 값으로 나누어주는 연산)이 필요하게됩니다. 이러한 연산은 ConvNet에서 꽤나 많은 부분을 차지하게 되고, 이를 줄이기 위해서 저자들은 Shift-based batch normalization(SBN)이라는 방법을 사용했습니다. 해당 알고리즘은 알고리즘 3에 설명되어 있습니다. SBN 알고리즘을 사용할 경우, 대부분의 Multiplication operation을 제외하고도 BN에 근사한 값을 계산할 수 있고, 실험적으로 기본적인 BN과 SBN을 통한 계산시의 정확도 손실을 거의 관찰하지 못했다고합니다.
알고리즘 1에서 나타난 것과 같이 SBN에 파라미터로 들어가는 값은 다음과 같습니다.
해당 식에서
이를 이용해서 Multiplcation operation없이 분산값에 근사시키는 연산을하겠다는건데, 연산 컨셉이 bit shift를 통하면, 2의 거듭제곱을 쉽게 구할 수 있으니까, 이를 통해서 어떠한 특정 수의 제곱값을 근사하는 함수로 쓸 수 있다는 겁니다.
예를들어 설명해보자면, 만약에 출력값이 4라는 값이 나온다면, AP2연산은 다음과 같은 결과를 갖습니다.
여기서 +1은 bit를 shift하는 방향인 것 같고, (+)부호가 왼쪽, (-)부호가 오른쪽 shift를 의미하는 것 같습니다. 그리고 4라는 숫자 자체는 이진수로, 100로 표현할 수 있고, 
[Batch Normalization]
2-5. Shift based AdaMax
ADAM Optimizer또한 많은 Multiplication이 필요하게 되는데, 이를 줄이기 위해서 저자들은 Shift-based AdaMax를 제안하게됩니다. AdaMax알고리즘은 알고리즘4에서 상세하게 설명되어있습니다. 여기에서도 SBN과 마찬가지로 AdaMax를 적용했을 때, Multiplication Operation을 줄이면서 정확도 손실을 관찰하지 못했다고 합니다.
여기서 궁금한 점은, 위의 SBN에서는 AP2함수를 이용해서, shift의 양을 정했다고 생각을 했는데, Sift-based AdaMax에서는 
2-6. First Layer
BNN은 오직 weights와 activation만 binarized하여 첫번째 레이어를 제외하고는 모두 Bit-wise Operation으로 해결하는 네트워크입니다. 저자들은 첫번째 레이어, 즉 Input value가 binary가 아닌 것에 대해서 major issue라고 생각하지 않는다고 이야기합니다. 해당 주장의 근거로는 예를 들어 Computer vision tasking에서 Input data라고 해봤자, 이미지(R,G,B)라 채널이 3개밖에 안되기 때문에, 이러한 입력 데이터의 표현(representation)은 모델의 표현(internal representation)에 비교했을 때, 굉장히 적다라고 주장합니다. 즉 ConvNet 전체를 놓고 봤을 때, 입력데이터의 연산은 큰 부하요소가 아니라고 생각하는 것 같습니다.
그렇다고 이를 그냥 Multiplication 연산을 하는 것은 아니고, 저자들은 fixed point number of m bits of precision(고정 소수점)의 경우에는 입력값을 처리하는게 상대적으로 쉽기 때문에, 첫번째 레이어에 대해서만 어떠한 특수한 데이터 가공을 하자는 이야기를 합니다. 저자들이 주장하는 방식은 다음과 같은데, 8-bit의 고정 소수점 입력 데이터는 다음과 같이 변환이 가능하다고 합니다.
여기서 
3. Benchmark Results
저자들은 해당 모델의 성능 비교를 위해서 Torch7과 Theano에서 MNIST, CIFAR-10, SVHN 데이터셋을 통해서 BNNs의 성능 측정을 진행했습니다. 측정 결과에 대한 요약 및 실험 방법은 다음과 같다고 합니다.
- Torch7과 Theano에서 MNIST, CIFAR-10, SVHN 벤치마크 데이터셋에 대해서 모두 state-of-the-art 결과가 나왔습니다.
- Torch7에서는 Quntization method를 stochastic을, Theano에서는 deterministic을 사용했다고 합니다.
- Torch7에서는 shift-based BN, AdaMax variant, Theano에서는 기본적인 BN과 ADAM을 사용했다고 합니다.
3-1. MLP on MNIST (Theano)
- Convolution은 사용하지 않음
- data-augmentation, preprocessing, unsupervised learning등의 기법을 사용하지 않음
- 3개의 hidden layer와 4096의 binary units을 사용함
- L2-SVM output layer를 사용했음(L2-SVM은 몇몇 benchmarks에서 Softmax보다 나은 성능을 보여줌)
- Dropout 사용
- ADAM adaptive learning rate 방법으로 square hinge loss를 최소화함
- exponentially learning rate decay사용
- mini-batch size 100과 BN을 사용
3-2. MLP on MNIST (Torch7)
- Theano 실험과 매우 유사한 구조의 아키텍쳐 사용
- dropout 사용 안함
- 2048 binary units
- shift based AdaMax 사용
- shift based BN 사용
- 1-bit right shift를 이용한 learning rate decay 사용
3-3. ConvNet on CIFAR-10(Theano)
- data pre-processing 사용 안함
- data-augmentation 사용 안함
- square hinge loss를 ADAM으로 최적화
- exponential learning rate decay
- mini-batch size 50으로 BN 사용
3-4. ConvNet on CIFAR-10(Torch7)
- shift-based AdaMax and BN 사용
- mini-batch size 200
- 1-bit right shift learning rate decay 사용
3-5. ConvNet on SVHN
- CIFAR-10과 거의 같음
- conv layer의 unit을 전반으로 줄임
- 500 epochs 대신 200을 사용(SVHN 데이터셋이 CIFAR-10보다 큼)
4. Very Power Efficient in Forward Pass
저자들은 BNNs를 사용해서 Forward Pass를 진행시, 극단적인 memory size, accesse를 줄일 수 있고, 대부분의 arithmetic operation을 bit-wise operation으로 대체할 수 있게 되었다고 합니다. 따라서 이러한 효과는 전력효율을 좋게만들어 줄 수 밖에 없고, 특히 binarized CNN의 경우에는 binary convolution kernel repetition으로 인해서 하드웨어에서의 시간복잡도를 60%이상 줄일 수 있다고 합니다. 그에 대한 평가 지표는 아래 Table에 나와있습니다.
4-1. Memory Size and Accesses
메모리 크기와 접근에 대해서는 32-bit DNNs과 BNNs를 비교했을 때, BNNs가 32배의 적은 메모리 및 메모리 접근을 필요로 했다고 보고하고 있습니다.
4-2. XNOR-Count
DNN은 Convolution과 Matrix multiplication으로 구성되어있고, Deeplearning에서의 arithmetic operation의 Key는 Multiply-Accumulate operation입니다. 그런데, BNNs는 activation과 weights들이 -1과 1로 구성이 되어있고, 그 결과 대부분의 32-bit floating point multiply accumulation들이 1-bit XNOR-count로 대체가 가능해졌다고 이야기합니다.
4-3. Exploiting Filter Repetition
로 고정될 수 있습니다. 하지만 실제 필터는 3D행렬이므로(filter의 개수를 말하는 거 같습니다), 이러한 제한 사항을 통해서 feature map이 확장되는 것을 막을 수 없답니다. 따라서 특정 Conv Layer에서 M개의 필터를 가지고 있다고 가정할 시, (
)의 크기의 4D weight matrix를 저장하게 됩니다. 결과적으로 ConvNet의 고유한 필터 개수는 
로 계산이 되어지는데, 연산 수행시 feature map에 각 필터를 적용하고 필요한 MAC Operation을 수행하는데, filter들이 binary filter이기 때문에 수많은 2D filter가 반복된다고 합니다. 이건 아마도 binary filter의 pattern이 유사한게 너무 많기 때문에 이러한 부분들이 반복된다고 이야기하는 것 같습니다. 따라서 저자들은 일반적으로 우리가 개발할 때, 전용 하드웨어 및 소프트웨어를 사용하게 되니까 각 feature map에 고유한 2D filter만 적용하고, 이를 잘 조합해서 3D Conv 결과를 얻을 수 있을 것이다라고 이야기합니다. 예를들면, 동일하진 않지만, 어떠한 특정 filter에 대해서 inverse를 해주면, 다른 하나의 filter 역활을 할 수 있으니, 하나의 필터로 2개의 필터의 표현할 가질 수 있는 것에 대해서 이야기하는 거 같습니다. 만약 이런형태로 제한된 filter의 개수로 여러가지 filter를 표현한 결과 CIFAR-10 벤치마크에서 ConvNet은 각 레이어당 평균 42%의 고유 필터만 존재하여 XNORpopcount의 연산수를 3으로 줄일 수 있었다고 보고하고 있습니다.5. Seven Times Faster on GPU at Run-Time
여기서 
이러한 3개의 instruction(accumulation, popcount, xnor)은 해당 논문 발표시의 Nvidia GPUs에서 1+4+1=6 clock cycles안에 수행되는데, 이를 통해 이론적으로 5.3배에 근사한 연산속도 향상을 볼 수 있수 있습니다. 실제 구현에서는 memory bandwidth 대 연산 비율이 6배 증가하므로, 속도향상이 매우 쉽다고 논문에서 이야기하고 있습니다.
저자들은 이를 확인해보기 위한 실험을 직접 실험을 진행했는데, 실험 내용은 다음과 같습니다.
- baseline은 최적화하지 않은 matrix multiplication kernel을 사용
- 두번째 커널(XNOR)은 SWAR method를 쓴것만 차이가 있으며, 다른 부분은 baseline과 같음
- 두개의 GPU 커널은 입력값이 +1, -1로 제한될 때는 출력값이 같으나, 그렇지 않을 경우는 다른 출력이 나옴
- XNOR kernel이 baseline kernel보다 23배 빠르며, cuBLAS보다 3.4배 빠름
