[RL] The Linearization Principle

<본 포스트는 UC Berkeley 교수인 Benjamin Recht 의 블로그에 올라온 글을 번역한 것입니다. 원본>

 나는 머신러닝으로 문제를 푸는데 있어 "Linearization Principle"이라고 부르는 기조를 유지한다. 이 원칙에는 많은 다양성들이 존재하지만, 간단하게 말하자면, "만얀 머신러닝 알고리즘이 실제 선형모델로 제한된 상태에서 예상치 못한 소위 미친 짓을 한다면, 복잡한 비선형 모델에서도 마찬가지로 미친 짓을 할 것이다"라는 것이다. 

 이 Linearization Principle은 머신러닝상에서의 복잡한 문제를 다루기 쉽고 간단한 문제로 분해시켜주고 해결할 간편한 방법을 제공한다. 물론 머신 러닝을 이해하는 있어 선형 모델을 활용한 문제가 충분하다고는 생각하지 않지만, 그래도 널리 활용할 수 있는 방법이라는 데에는 논의할 필요가 있다고 생각한다. 같은 방법으로 2-SAT 문제를 해결하는 것이 P=NP 를 증명하지는 않은 상태에서, 만약 3-SAT solver를 만들기를 원한다면, 2-SAT 문제 해결에 비해서 exponential time이 걸릴 것이고, 뭔가 알수 없는 무언가가 진행되고 있을것이다.

 강화학습에 Linearization Principle을 적용해보기에 앞서, 일반적인 supervised deep learning 에 모델이 얼마나 간단하게 핵심을 줄수 있는 지 몇가지 예를 들어보고자 한다. Ali가 딥러닝 상에서 관찰한 몇가지 현상들을 나에게 전달해줬는데, 여기서 그가 소개한 현상들을 통해서 선형모델을 이해하는데 어떻게 도움이 되는지에 대해서 설명해보고자 한다.

Ali가 관찰한 첫번째 현상 : 얕은 local minimizer가 sharp한 것보다는 generalize를 더 잘 시킨다?

 선형 모델이나 딥러닝 모델이나 모든 global minimizer가 동등하게 generalize시키지는 못한다. 만약 데이터의 갯수보다 두배나 더 많은 변수들을 가지고 있다고 가정해보자. 이 말은 (N-자유도를 가지는) 학습 데이터 집합에 대해서는 즉각적으로 오류가 발생하지 않고, (N-자유도를 가지는) 또다른 N개의 학습군에 대해서도 동일한 현상이 나오는 것을 의미한다. 이때, 예를 들어 학습 데이터에 약간의 노이즈를 가한 "혼란을 주기 위한(perturbed)" 학습군을 만들고 해당 학습군에는 랜덤하게 label을 입힌 상태에서 실제 데이터에서는 학습 오류가 발생하지 않도록 학습시켰다고 가정해보자. 이 모델은 실제 학습 데이터 군에 대해서는 학습 오류에 대한 global minimizer가 될 것이다. 하지만 이렇게 이상한 모델이 generalize가 잘 된다는 것도 겉에서 보기에는 이상하게 느낄 것이다.

 그러면 out-of-sample performance, 즉 샘플링하지 않은 데이터에 대한 성능을 최대화하기 위해서는 minimizer를 어떤 방식으로 구분할 수 있을까? 딥러닝에서는 쉽게 얻을 수 있는 대답이 "sharp minimizer를 선택하지 마라" 라는 것이다. 그런데 사실 나는 사람들이 어떤 것을 "sharp minimizer"라고 하는 것인지를 잘 알지 못한다. 이 내용을 twitter에도 올려봤지만, 딱 합의된 정의를 찾지 못했다. 그나마 가장 가까워 보였던 의미는 minimizer가 학습 오류가 모델의 약간의 혼란이 가해진 데이터에도 민감할 경우에 보통 sharp하다고 하는 것이었다.

 혼란이 가해진 데이터에 대한 민감성이 부족한 것은 나한테는 약간 의미가 있는 것처럼 보였다. 그리고 실제로, 선형 모델 상에서는 이런 아이디어가 머신러닝 자체 만큼이나 오래 지속되어온 개념이기도 하다. 선형모델의 혼란 데이터에 대한 민감성은 margin이라고 하는 decision boundary의 data의 거리를 통해서 측정할 수 있다.

 Margin은 왜 앞에서 소개한 이상한 모델이 generalize하기 어려운지를 직관적으로 보여준다. 간단하게 말해서 모든 데이터가 단위 norm인 상태에서 binary classification 하는 경우를 고려해보자. 만약 우리가 모든 학습 데이터 x에 대해서 \(|w^{T}x| > 1\) 인 w를 선택했을 때, 이때의 margin은 적어도 \(||w||^{-1}\) 일 것이다. 이 말은 margin이라는 것이 모든 x에 대해서 \(|w^{T}x| > 1\)인 모든 w에 대해 가장 큰 inverse Euclidean norm 이라는 것을 의미한다. 이제 앞에서 가미한 혼란이 가해진 데이터에 대해서는 음의 w와 내적을 취한 매우 가까운 데이터만 가지고 있게 된다. 이와 더불어 w의 norm은 매우 클 필요가 있게 되고, 최종적인 해는 매우 작은 margin을 갖게 될 것이다. 결론적으로 w나 데이터에 대한 혼란이 약간이라도 가해진다면, 해당 모델에 대해서는 classification의 결과도 엄청나게 변하게 될 것이다.

 그러면 만약 "shallow minimizer"라는 것이 "large margin"이라는 것을 의미한다면, 내가 알고 있는게 맞다. 사실 딥러닝 상에서는 margin의 고전적인 정의를 담고 있는 매개변수의 불변의 의미를 아직까지는 명확하게 설명하지 못하고 있다. 반대로 딥러닝 상에서의 margin에 대한 명확한 정의 를 몇가지 좋은 방법들이 소개되고 있다.

Ali가 관찰한 두번째 현상 : Batch Normalization 계층을 삽입하면 SGD가 빨라진다?

 계층 관점에서 이렇게 하면 어떻게 될지 명확하지는 않지만, 선형 네트워크 관점에서는 standardization을 하면 확실히 SGD가 빨라진다. 여기에는 간단한 이유가 있는데, 선형 모델내의 데이터를 깨끗이 함으로써 data의 covariance(공분산)을 만족시키는 경향이 있기 때문이다. 이로 인해 SGD가 수렴할 확률을 개선하는 효과를 나타내는 것이다. 물론 선형 모델이 딥러닝 모델 내에서 계층적인 관점에서 normalization을 해야 하는 완전한 설명을 제공하는 것은 아니다. 게다가 선형 모델이 내부 covariate shift로 인해서 어려움을 겪는지도 확실하지 않다. (Ludwig Schmidt가 이 부분에 대해서 설명을 해놨다.)

Ali가 관찰한 세번째 현상 : 수많은 local optima와 saddle point가 있음에도 SGD는 성공한다?

 선형 모델은 saddle point(역자 주: 중간에 딱 막히는 지점이라고 보면 좋을거 같다.)을 가지고 있지 않지만, 만약 해당 모델이 가지고 있는 데이터 보다 더 많은 변수들을 가지고 있다면, 학습 오류는 수많은 local minimizer를 가지게 될 것이다. 실제로 위에서 소개한 바와 같이 무한한 global minimizer를 갖게되는 것이다.

 선형 모델을 위한 SGD는 전체적인 optimum으로 수렴하지 않지만, loss function을 어떤 것으로 선택했냐에 따라서 SGD는 거기에 맞는 minimizer를 찾을 수 있을 것이다. square loss를 적용하면, 그로 인한 해는 큰 margin을 가질 것이고, softmax loss를 사용하면, 매우 느리기는 하지만 margin을 최대화 시킬 수 있는 해로 수렴할 것이다.

 saddle point에 관한 부분에서는, 내 속마음으로는 saddle point를 막는 SGD 자체가 bias를 선택하는데 있어 중요한 부분이라는 것을 말하고 싶다. Ali와 내가 지난 시간에 다뤘던 내용에서 처럼 Gradient Descent 기법이 local minimum을 효율적으로 찾지 못하는 신경망의 예시를 찾기는 매우 쉽다. 아마 우리가 saddle point를 피하는 케이스에 대해서만 들을 수 있을 것이다.

Ali가 관찰한 네번째 현상 : Dropout 방식은 다른 randomization 기법에 비해서 잘 동작한다?

 Wager와 그외 연구자들은 선형 모델상에서 Dropout 기법은 가중치가 가해진(weighted) ridge regression의 한 형태에 지나지 않는다는 것을 보여줬었다. Dropout 기법은 딥러닝 모델상에서 의심할 여지가 없을 만큼 뭔가 다른 부분이 있지만, 랜덤하게 혼란을 가한 backpropagation도 일종의 regularization처럼 동작하는 것도 그렇게 놀랍지 않다.  "다른 randomization 기법에 비해서 잘 동작하든 안하든" 딥러닝 업계에서 위의 사실은 아직도 명확하게 정의되어 있지 않다.

Ali가 관찰한 다섯번째 현상 : 딥러닝 네트워크는 랜덤 라벨을 기억할 수 있지만, 더불어 generalize 시킬수도 있다?

 위에서 이야기 했던 바와 같이, 위의 사실은 선형 모델에 대해서는 사실이다. 이 내용은 ICLR에서 S. Bengio와 hardt, Vinyals,Zhang에 의해서 크게 논쟁을 불러왔던 paper의 주제였다. 일반적인 neural net은 수많은 계수들이 존재하기 때문에 우리가 원하는 어떠한 패턴이라도 학습을 시킬 수 있고, Imagenet과 같이 엄청 큰 모델일 지라도 그런 형태를 띤다.

 또한 과소평가된(underdetermined) 선형 모델에 대해서도 위의 내용은 사실이다. 고차원의 선형 모델도 학습 데이터에 대해서 완벽하게 적응된 상태에서 큰 margin을 가지더라도 generalize가 된다.

 하나의 치트키 : Adam 알고리즘?

5000개가 넘는 논문들이 deep neural net을 빨리 학습시키기 위해 Adam 알고리즘을 사용했다. Adam 알고리즘의 광신자들은 adam 알고리즘을 사용하면 빠르게 수렴하고, 최고의 성능을 보여주며, hyperparameter를 일일이 튜닝할 필요가 없다는 것을 내세운다. 사실 Becca Roelofs, Nati Srebro, Mitchell Stern, 그리고 Ashia Wilson이 진행한 연구에서도 발견한 것은 Adam 알고리즘을 사용하면 일반적인 SGD에 비해서 hyperparameter에 민감해질 뿐만 아니라, SGD보다도 더 안 좋은 테스트 에러를 계속 보여준다는 것이다.

Adam 알고리즘이 왜 이렇게 나쁘게 동작하는지 이해하기 위해서 경험적으로 축적한 벤치마크를 사용하는 것이 어려웠기 때문에, 우리는 다시 되돌아가서 과소평가된 선형 모델에 대해 튜닝해봤다. 이 경우, 어디서 adam 알고리즘이 수렴하는지를 계속 파악할 수 있었다. 이를 통해 Adam 알고리즘은 랜덤으로 뽑는 것보다 안좋은 predictor를 만들어내고, Gradient Descent는 큰 마진과 더불어 generalization 을 완벽히 수행한 간단한 생성 모델을 만들어낼 수 있었다.

강화학습을 위한 Linearization

Linearization Principle이 neural net의 모든 성향을 설명하기는 어렵지만, 우리가 이상하게 여겼던 특성들의 대다수를 명확하게 설명해준다. 결국 위에서 소개한 대부분의 현상들이 선형모델에 적용가능한 기법들에 기반을 두고 있는 것이다.

 내가 생각하기에는 Linearization Principle을 도움 삼아서 같은 정의도 강화학습에 적용할 수 있을 것 같다. 다음 포스트에서 강화학습에서 가장 적절한 선형 베이스라인이 그 위대한 "Linear Quadratic Regulator(LQR)"라는 것을 설명해보고자 한다.