Introduction

이번 포스트에서 소개시켜 드릴 논문은,  아주 쉽고, 간단하며, 효과적인! 아이디어로! ICML2017에 accept된! 논문이 있어 공유해드립니다.

이 논문의 아이디어는, Neural Network를 학습시킬때, forward propagation은 그대로 유지하되, backpropagation 실행시, selective한 gradient로 학습을 합니다. 이렇게 함으로서, 이득은 3가지가 있다합니다.

  1. 학습 가속화: Backpropagation하는 gradient의 사이즈들이 워낙 작아져서 한번 업데이트 할시, 1-4%의 parameter들만 변화 된다합니다.
  2. Accuracy 향상: 극소수의 parameter가 업데이트 되지만, 정확성은 향상 됩니다.
  3. Overfitting 저하: 모델이 학습도중 overfitting될 가능성을 낮춰줍니다.

아래 그림을 보시면 visually 어떤식으로 backpropagation이 이뤄지는지 볼수 있습니다.

meProp0.png

meProp의 , me는 “minimal effort“를 뜻합니다.

Methods

이번 섹션에선, 조금 더 자세히 sparsified backpropagation이 어떻게 이뤄지는지 살펴 보겠습니다.

exp6.png

forward propagation은 기존의 backpropagation과 spasified backpropagation 둘 다 동일하게 이뤄집니다. 다만, sparsified backpropagation은 위 diagram마지막 그림에서 보이시듯이, 선택된 output gradient, \frac{dL}{dy} 의해서만, 이뤄집니다.

이 \frac{dL}{dy} output gradient는 어떻게 선택되는지 궁금하실텐데요, 정말 간단한 sorting algorithm으로 |\frac{dL}{dy}| absolute한 magnitude를 찾아, 가장 parameter update에 impact가 있는 k수의 gradient들만 나열하여 업데이트 합니다.  이를 “top_k” algorithm이라 칭하는데요,  min-heap을 기초로한 time complexity O(n log k)와 space complexity, O(k)로 갖춘 메모리의 조금 더 focus를 둔 알고리즘 입니다.

top_k에서 쓰이는 k는, 매 레이어 마다 바뀔수 있는 hyperparameter입니다. 모든 레이어가 다 다른 사이즈의 output을 내뱉기 때문에, k가 매번 똑같다면 어떤 레이어에선 너무 큰 information loss일수도 있겠죠?

 

Experiments

meProp에서 알고리즘을 검증하기 위해 다양한 데이터 셋(MNIST, Wall Street Journal, Penn Treebank corpus)를 이용하였습니다. 실험을 위해 LSTM, Multi-Layer Perceptron을 주로 사용하였고, Adam과 AdaGrad 옵티마이져 기반으로 실험을 수행 하였습니다. meprop1.png

실험 Task는, parsing, Image Recognition, 그리고 POS-Tagging Task를 적용하였습니다.

Table 1의 실험결과에 Backpropagation time은, linear transformation만 추가되었고, non linear한 부분은, 생략되었습니다(전체 computation에서 1-2%밖에 차지하지 않기에 큰 차이는 없을겁니다). Dev Acc는 저희가 흔히 알고 있는 Training Accuracy라고 생각하시면 됩니다.

첫번째로 가장 눈에 띄는 결과는, Backpropagation time인데요, 보시다싶히, 69배, 18배, 41배 등등 연산 속도가 어마어마하게 빨라졌습니다. 물론 생각해보면 당연한 결과이죠. 1-4%만의 parameter만 매번 업데이트 되기 때문에 이정도의 가속은 기대해볼수 있었겠죠!

meprop2.png

위 테이블을 보시면, 전체적인 time gain을 볼수 있는데요, 각 task/model마다, ~3배정도의 time gain이 있었다 볼수 있습니다.

Training Accuracy와 Test Accuracy 둘 다 조금씩 높아진건 아마도 학습시, noisy한 gradient들을 생략하였기에 보다 더 살짝 좋은 minima로 갈수 있는 가능성이 있다 생각이 드네요.

meProp3.png

위 실험 3개 또한 meProp이 얼마나 robust한 알고리즘인지 입증하는데요,
왼쪽의 실험은, k대 hidden unit 비율 혹은, backpropagation ratio(e.g. hidden unit =500 , k =5는 backpropagation ratio = 1%) 를 다양하게 바꿔가며 실험 했을시에 결과가 어떻게 바뀌는지 보여줍니다. 보시다싶히, 본 실험 안에선, 거의 항상 성능 향상을 보여줍니다.
Figure 가운데 실험은, meProp이 k를 랜덤하게 세팅하는 것 과, top_k를 이용하는거의 차이를 보여주어 top_k gradient들이 얼마나 중요한 정보를 담고 있는지 보여줍니다.
마지막으로, 오른쪽의 실험은, hidden unit의 갯수대비 k를 다르게할때 baseline도 같은 hidden unit세팅을 이용하여 meProp은, 적거나 큰 hidden unit 갯수에 dependent한 알고리즘이 아니라는 사실을 보여줍니다.

이 외에도, Dropout과 함께 regularize했을시, hidden dimension을 바꿔봤을시, 그리고 layer를 늘려봤을시 모두 다 긍정적인 향상이 있었기에, robustness가 어느정도 입증됬다 볼수 있습니다. 좀 더 큰 dataset에서의 결과를 봤었다면 훨씬 더욱 많은 믿음이 생겼을 듯 싶네요.

Conclusion

이번 포스트에서 만나본 minimal effort(meProp) 알고리즘은, 정말 쉽고 간단한 방법으로 speed, accuracy and regularization까지 함께 도와주었습니다. 지금 제 앞에 있는 뉴럴넷에도 효과적일지는 물론 직접 적용해보고 실험을 해봐야 명확한 답을 얻을수 있겠지만, simple하다는 이유로, 저 말고도 많은 사람들이 적용해보지 않을까 싶습니다.

References

meProp: Sparsified Back Propagation for Accelerated Deep Learning with Reduced Overfitting, Sun et al 2017, ICML2017.

Dropout: a simple way to prevent neural networks from overfitting, Srivastava et al 2014, Journal of Machine Learning Research.

Posted by:Chris Dongjoo Kim

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s