2017년 5월 29일 월요일

초짜 대학원생의 입장에서 이해하는 The Marginal Value of Adaptive Gradient Methods in Machine Learning (1)

* The Marginal Value of Adaptive Gradient Methods in Machine Learning, Ashia C. Wilson et al. 2017을 바탕으로 한 리뷰

안녕하세요 한동안 뜸했습니다. 일주일 간의 파키스탄 출장이 끝나서 어제 돌아왔네요. 이 논문은 출장 중 페이스북을 보다가 최근에 흥미로운 논문 한 편이 공유되었길래 저장해뒀던 것인데요 돌아오는 비행기 안에서 시간을 보낼거리를 찾다가 상당히 재미있게 읽어 글로 정리를 해봅니다.

논문 내용을 마치 광고 글처럼 요약해보자면,
"Gradient descent (GD)나 Stochastic gradient descent (SGD)를 이용하여 찾은 solution이 다른 adaptive methods (e.g. AdaGrad, RMSprop, and Adam)으로 찾은 solution보다 훨씬 generalization 측면에서 뛰어나다."
"그러니까 adaptive methods 괜히 쓰지 말고 SGD를 써라!"
....응? 진짜?


엄청난 떡밥이죠ㅋㅋ 강렬한 캐치 프레이즈 때문에 도무지 읽지 않을 수 없었습니다.

이 논문은 아무리 생각해도 제목을 잘못 지은 것 같습니다. 아니면 제가 영어 독해 감이 떨어져서 위에 내용으로 바로 이해가 안 되는 것일까요? 누가 앞서 광고글처럼 초록 부분의 내용을 요약해서 올려주지 않으셨었더라면 그냥 제목 보고는 읽지 않고 넘어갔을 것 같은 느낌입니다.

생각보다는 쉽게 논리적으로 이유를 설명하고 실험적으로도 근거를 제시하는데 읽다보면 설득이 되는 자신을 발견할 수 있습니다..(아니면 "아 그래 더 이상은 optimizer choice에 신경쓰고 싶지 않아..."라는 악마의 속삭임 때문일지도...)

(아...이 그림이 preview로 올라가겠네 ㅋㅋ)

Introduction


이 논문에서 다루고자 하는 내용은 다음과 같습니다:
"최적화 문제에 대해 두 가지 다른 optimizer들이 존재할 때 generalization 능력이 상대적으로 어떤 차이가 있을까?"
Generalization, 즉 일반화 능력이란 것은 쉽게 얘기하자면 network가 training dataset으로 학습한 solution이 test dataset에서 얼마나 잘 적용되는지(error가 낮은지)를 얘기합니다.

그런데 adaptive gradient methods라고 하여 학습 시간이 빠르다는 장점 때문에 최근 많이들 쓰이고 있는 Adam과 같은 알고리즘 등이 이런 generalization 상황 즉, out-of-sample이 들어왔을 때 얼마나 잘 동작하는지에 대해서는 아직 잘 알려져 있지 않습니다.

그래서 이 논문에서는 adaptive methods와 non-adaptive methods가 실제로 상당히 다른 solution을 찾고 generalization property도 매우 다르다는 것을 보여줍니다.

이를 설명하기 위해 아주 linearly separable한 (즉, large margin을 갖는 해가 존재하는) 단순한 binary classification 문제에서 AdaGrad, RMSProp, Adam 등의 optimizer들은 모두 (학습이 되지 않은) 새로운 데이터에 대해 하나의 class로만 잘못 분류하는 해로 수렴하는 반면 SGD는 새로운 데이터에 대해서도 zero error를 갖는 해로 잘 수렴하는 것을 보여줍니다.

이어 실험적으로도 이를 뒷받침하는데요 이를 통해 세 가지 발견을 하였다고 정리합니다:

  1. 같은 수의 hyperparameter tuning을 할 때, SGD와 SGD+momentum이 여타 adaptive methods들보다 모든 모델과 task들에 대해 dev/test set에서 우월한 결과를 보여줌.
  2. Adaptive methods들이 초기 학습 속도는 빠른 모습을 종종 보이긴 하지만 dev/test set에서 성능이 증가하는 것 역시 더 빠르게 더뎌지는 모습을 보임.
  3. Adaptive methods들이 주장하는 장점인 "less tuning needed"와는 다르게 모든 methods들에 동일한 정도의 tuning이 필요했음.

특히 1번에 대해 첨언한 부분이 인상적인데요 adaptive methods의 training loss가 non-adaptive methods의 loss와 비교했을 때 같거나 더 낮은 경우에도 여전히 non-adaptive methods들이 generalization 측면에서 나은 것을 확인하였다고 합니다.

이 외에도 위에서 분석한 결과들을 바탕으로 deep learning practitioner들을 위해서 자기들이 수행한 다양한 tasks(CIFAR-10 Image classification, Character-level language modeling on the novel War and Peace, discriminative parsing, generative parsing on Penn Treebank)에서 learning rate나 decay term의 tuning을 좀 더 단순하게 할 수 있는 방식을 제안하였다고 합니다. 기존에 공개된 코드를 가지고 다양한 tasks에 적용을 한 결과다보니 이 역시도 이런 hyperparameter tuning에 지친 분들에게 꽤나 솔깃한 내용일 수 밖에 없습니다.

Background


본격적으로 들어가기 전에 약간 notation들에 익숙해질 필요가 있기에 소개를 하고 넘어갑니다. 일반적으로 risk를 최소화하기 위해 사용되는 최적화 알고리즘들을 보면 stochastic gradient methods 혹은 stochastic momentum methods임을 알 수 있습니다.

Stochastic gradient methods는 $\tilde{\nabla}f(w_k):=\nabla f(w_k;x_{i_k})$가 data batch $x_{i_k}$에 대한 loss function $f$의 gradient일 때,
\begin{equation}w_{k+1}=w_k-\alpha_k\tilde{\nabla}f(w_k)\label{eq1}\end{equation}로 쓰이죠. 다른 갈래인 stochastic momentum methods는 학습을 가속하기 위해 소개된 종류의 테크닉입니다:
\begin{equation}w_{k+1}=w_k-\alpha_k\tilde{\nabla}f(w_k+\gamma_k(w_k-w_{k-1}))+\beta_k(w_k-w_{k-1}).\label{eq2}\end{equation}
여기서 식 \ref{eq2}는 $\gamma_k=0$일 때는 Polyak's heavy-ball method (HB)가 되고 $\gamma_k=\beta_k$일 때는 Nesterov's Accelerated Gradient method (NAG)가 됩니다.

식 \ref{eq1}과 \ref{eq2}의 잘 알려진 변주로는 adaptive gradient 그리고 adaptive momentum methods라 하여 전체 iterates $(w_1,\cdots,w_k)$에 대한 local distance measure를 사용한 방법들이 존재합니다. 유명한 예로는 AdaGrad, RMSProp, Adam 등이 있고
\begin{equation}w_{k+1}=w_k-\alpha_kH_k^{-1}\tilde{\nabla}f(w_k+\gamma_k(w_k-w_{k-1}))+\beta_kH_k^{-1}H_{k-1}(w_k-w_{k-1})\label{eq3}\end{equation}로 표현할 수 있습니다. 이 때, $H_k:=H(w_1,\cdots,w_l)$는 positive definite matrix입니다.

필수적인 것은 아니지만 $$H_k=diag\left(\left\{\sum_{i=1}^k\eta_ig_i\circ g_i\right\}^{1/2}\right)$$로 보통 나타내집니다. 여기서 $\circ$는 Hadamard product이고 $g_k=\tilde{\nabla}f(w_k+\gamma(w_k-w_{k-1}))$이며, $\eta_k$는 각 알고리즘마다 특화된 coefficients set이라고 생각하시면 됩니다.

이 논문에서는 $H_k$가 이런 형태로 정의되어 있다고 생각하고 논리를 전개해나갑니다. 각각의 알고리즘 마다의 parameter setting은 다음 table에 잘 정리되어있습니다. Adaptive methods는 data의 geometry에 따라 알고리즘을 조금씩 바꿔나가는 반면 stochastic gradient descent와 그 변주들은 parameter space로부터 비롯한 $l_2$ geometry를 사용하는 것으로 해석할 수 있고 이는 $H_k=I$인 것과 같습니다.
(* 이 부분은 직관적으로는 알겠지만 명료하지 못한 부분인데 설명이나 링크를 보충해주실 수 있는 분이 있다면 댓글로 알려주시면 감사하겠습니다.)



따라서 정리해보자면 "일반화(generalization)"라는 것은 좀 더 넓은 population에서의 알고리즘이 찾아낸 해 $w$의 성능을 의미합니다. 그리고 성능은 보통 학습에 사용되는 함수 $f$보다는 다른 loss function으로 정의되곤 하죠. 분류 문제를 예를 들자면 보통 cross-entropy 대신 classification error로 generalization을 정의하는 것을 보실 수 있습니다.

Preconditioning의 문제점


논문에서는 adaptive methods들의 이런 변주들을 preconditioning이라는 단어로 묶어 얘기하며 이들의 문제점을 지적합니다. 그 일환으로 우리가 풀고자 하는 문제가 multiple global minima를 갖을 때, 다른 알고리즘을 사용하면 완전히 다른 해들이 나올 수 있다는 것을 보여줍니다. 

서론에서 얘기했듯이 이를 좀 더 쉽게 보여주기 위해서 문제를 간단히 binary least-square classification 문제로 설정하여 보겠습니다:
\begin{equation}\min_w R_S[w]:=||Xw-y||^2_2.\label{eq4}\end{equation}
위의 문제에서 $X$는 $d$ dimensional feature들이 $n$개 sample에 대해 있는 $n \times d$ matrix이며 $y$는 $\{-1,1\}$를 label set으로 갖는 $n$ dimensional vector입니다. 우리는 이제 가장 적합한 linear classifier $w$를 찾기만 하면 되는 것이죠. 

문제에서 $d>n$일 때, 즉 문제의 parameter가 equation 수보다 많은 경우 loss가 0이게 하는 global minimizer가 무한히 존재하는 것은 자명합니다. 그러면 이제 

"어떤 알고리즘이 개중 어떤 해를 찾고 학습에 사용되지 않은 data를 보여줄 때 가장 잘 generalize하는 것은 어떤 해일 것인가?" 

에 대한 질문이 남는데요 이 질문에 대해서 non-adaptive methods와 adaptive methods가 어떤 전략으로 해를 구하는지 보겠습니다.

Non-adaptive methods


대부분의 non-adaptive methods는 식 \ref{eq4}에 대해 동일한 해를 찾습니다:
$$w^{SGD}=X^T(XX^T)^{-1}y.$$
이 유일한 해는 minimum Euclidean norm을 갖는 해로 SGD, SGD+momentum, mini-batch SGD, Nesterov's method, conjugate gradient method 등 대부분의 non-adaptive methods들이 모두 이 minimum norm 해로 수렴을 합니다.

Minimum norm solution이 $Xw=y$의 해 중 가장 큰 margin을 갖고 있다는 것을 생각하면 이는 generalization 관점에서 상당히 괜찮은 성질을 갖고 있다는 것을 의미합니다. 애초에 SVM 등의 연구에서 margin maximizing solution을 찾는 것이 왜 좋은 지에 대해서는 많은 연구가 되어있으니까요.

Adaptive methods


그럼 adaptive methods들은 어떨까요? 위의 경우와는 달리 이런 methods의 일반해를 구하는 것은 쉽지 않지만 최소한 특별한 경우들에 대해 어떤 결과들이 나오는지 분석해볼 수는 있습니다. 그래서 이 논문에서는 몇 가지 다양한 경우의 상황에 대해 adaptive methods가 $l_2$ norm이 아닌 $l_\infty$ norm이 작은 solution으로 수렴하는 것을 보여줍니다. 

Suppose $X^Ty$ has no components equal to $0$ and there exists a scalar $c$ such that $X sign(X^Ty)=cy$. Then, when initialized at $w_0=0$, AdaGrad, Adam, and RMSProp all converge to the unique solution $w\propto sign(X^Ty)$.
즉, $X sign(X^Ty)=cy$를 만족하는 상수 $c$가 존재하고 $Xw = y$의 문제에 대해 $sign(X^Ty)$에 비례하는 해 $w$가 있을 경우 adaptive gradient methods는 언제나 이 해로 수렴한다는 것입니다.

사실 그렇다면 이 문제의 해를 구하기 위해 굳이 최적화 문제를 풀 필요도 없다는 것을 뜻합니다. 이미 analytic하게 구할 수 있으므로, 조건만 맞다면 그냥 저 수식을 계산하여 $w$를 찾기만 하면 되니까요.

음 그런데 이렇게 찾은 $w$가 좋은 해라고 하기는 어렵겠죠. 이렇게 단순한 해가 일반적인 상황에서 모두 잘 동작한다면 그게 더 놀라운 일이니까요. 논문에서는 실제로도 이런 종류의 해들이 generalization 측면에서 성능이 안 좋다는 것을 보여줍니다.

이 lemma에 대한 증명과 "Adaptivity can overfit" 내용은 다음 편에서 다루도록하겠습니다.

다음 읽을거리



참고문헌:



작성자: 시간:
라벨: ,

댓글 1개:

피드 구독하기: 댓글 (Atom)