* The Marginal Value of Adaptive Gradient Methods in Machine Learning, Ashia C. Wilson et al. 2017을 바탕으로 한 리뷰
글이 나누어 져서 보시기가 불편하실까봐 한 번 더 우리가 풀 문제를 정리해보겠습니다.
Previously,
지난 시간에 $\tilde{\nabla}f(w_k):=\nabla f(w_k;x_{i_k})$가 data batch $x_{i_k}$에 대한 loss function $f$의 gradient일 때, non-adaptive, adaptive methods들을 다음과 같이 일반화했었습니다:
\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}).\end{equation*}
이 때, $H_k:=H(w_1,\cdots,w_l)$는 positive definite matrix이며, 필수적인 것은 아니지만 문제를 좀 단순화하기 위해 $H_k$를 다음과 같이 놓습니다: $$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이라고 생각하시면 됩니다.
Preconditioning의 문제점
이 논문에서는 AdaGrad, RMSProp, Adam 등의 adaptive methods가 사용하는 여러 방식의 변주들을 preconditioning이라는 단어로 묶어서 표현합니다.
Non-adaptive methods와 비교할 때 multiple global minima를 갖는 문제에서 adaptive methods는 알고리즘에 따라 서로 완전히 다른 해들이 나올 수 있다는 것을 보여주는데요. 이 때 보다 간단히 문제를 이해하기 위해 다음과 같은 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$를 찾기만 하면 되는 것이죠.
이전 글에서 Non-adaptive methods는 식 \ref{eq4}에 대해 minimum $l_2$ norm 을 갖는 해 $$w^{SGD}=X^T(XX^T)^{-1}y$$로 동일하게 수렴을 하는 반면, adaptive methods는 특별한 경우에 한하여 분석한 것이긴 합니다만 lemma 1에서 얘기한 조건이 맞는 경우, 앞서 소개한 모든 adaptive methods는 언제나 $w\propto sign(X^Ty)$인 해로 수렴한다는 것을 보여줍니다.
이번 글에서는 이 lemma에 대한 증명을 시작으로 "Adaptivity can overfit"에 대한 내용을 다뤄보도록 하겠습니다.
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)$.
증명이 생각보다 매우 쉽습니다. 먼저 이 lemma를 증명하기 위해 어떤 전략을 사용할 것인지 설명드리겠습니다. 위에 lemma에서 설정한 $Xsign(X^Ty)=cy$인 scalar 값 $c$가 존재한다는 조건이 성립한다는 것을 전제로 다음식에 대해 귀납법을 통해 증명을 할 것입니다:
$$w_k = \lambda_k sign (X^Ty).$$
먼저 이 식이 $k=0$일 때, $w_0=0$으로 initial 값을 주면 $\lambda_k=0$로 성립을 합니다. 귀납법의 첫째 단계는 통과했으니 다음 단계로 $k\leq t$일 때 assertion이 holds한다면 어떻게 되는지 확인해보시죠:
\begin{align*} \nabla R_S(w_k+\gamma_k(w_k-w_{k-1})) &= X^T(X(w_k+\gamma_k(w_k-w_{k-1}))-y) \\ &= X^T\{(\lambda_k+\gamma_k(\lambda_k-\lambda_{k-1}))Xsign(X^Ty)-y\} \\
&= \{\lambda_k +\gamma_k(\lambda_k-\lambda_{k-1}))c-1\}X^Ty \\
&= \mu_k X^Ty. \end{align*}
첫번째 등호에서 두번째 등호로 넘어가는 것은 $w_k = \lambda_k sign (X^Ty)$를 대입한 것이므로 간단합니다. 세번째 등호로 넘어가는 것 역시 가정에 의해 $Xsign(X^Ty)=cy$를 만족하는 $c$가 있으므로 이를 대입합니다. 남아 있는 것은 상수들뿐이기 때문에 여기서 $\mu_k$는 마지막 식에 의해 자연스럽게 정의됩니다.
따라서 $g_k=\nabla R_S(w_k+\gamma_k(w_k-w_{k-1}))$로 놓으면,
\begin{align*} H_k &= diag\left( \left\{ \sum_{s=1}^k \eta_s g_s \circ g_s \right\}^{1/2} \right)= diag\left( \left\{ \sum_{s=1}^k \eta_s \mu_s^2 \right\}^{1/2} |X^Ty| \right) \\&= \nu_k diag(|X^Ty|) \end{align*}
여기서 $|\cdot|$는 component-wise 절대값입니다 그리고 역시 마지막 식으로 $\nu_k$를 정의됩니다.
따라서 앞서 정의했던 $w$ update 식에 의해
\begin{align*} 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}) \\
&= \left\{ \lambda_k - \frac{\alpha_k \mu_k}{\nu_k} + \frac{\beta_k\nu_{k-1}}{\nu_k}(\lambda_k-\lambda_{k-1}\right\} sign(X^Ty) \end{align*}
가 되고 $\tilde{\nabla}f$는 위에서 구한 $\nabla R_S$를 대입한 것입니다. 이로써 마지막 줄이 결국 $k+1$에 대해서도 식이 성립하는 것을 보였으므로 증명이 끝납니다.
이 lemma에 의해 $X sign(X^Ty)=cy$를 만족하는 상수 $c$가 존재하고 $Xw = y$의 문제에 대해 $sign(X^Ty)$에 비례하는 해 $w$가 있을 경우, adaptive methods는 언제나 그 해로 수렴한다는 것입니다. 이렇게 간단한 해가 새로운 데이터에 대해 일반화가 잘 된다면 그게 더 신기한 일이겠죠. 실제로 이런 해들이 일반화에 관점에서 상당히 좋지 않다는 것을 다음 단락에서 보여줍니다.
Adaptivity can overfit
이제 생각보다 범용적인 상황의 간단한 예제에서 위에 lemma 1의 조건이 성립하는 경우 실제로 AdaGrad가 좋은 해(일반화가 잘 되는)를 찾지 못하는 것을 보여드리겠습니다.
이 예제는 간단하게 설명을 하기 위해 infinite dimensions를 사용합니다만 $n$개의 sample들에 대해 parameter dimension이 $6n$개를 만족하기만 하면 됩니다. 보통 실제 상황에서는 parameter의 수가 보통 $25n$이나 그 이상임을 생각하면, 이 예제의 설정이 이상한 것이 아닙니다.
Sample $i=1,\cdots,n$개에 대해 label $y_i$가 $p>1/2$인 확률 $p$로 $y_i=1$, $1-p$의 확률로 $y_i=-1$이고 $x$가 다음과 같은 infinite dimensional vector라고 해보겠습니다:
$$x_{ij} =\left\{\begin{array}{lll} y_i\hspace{10pt}j = 1 \\
1 \hspace{10pt}j = 2,3 \\
1 \hspace{10pt}j = 4+5(i-1),\cdots,4+5(i-1)+2(1-y_i) \\
0 \hspace{10pt} otherwise \end{array}\right.$$
$x$의 구조를 잘 살펴보시면 $x_i$의 feature라고 할만한 것은 class label을 갖는 첫번째 element뿐입니다. 다음 두 element들은 항상 1이고 그 이후로는 $x_i$에 대해
unique하기 때문에 sample의 label을 구별하는데 전혀 도움이 되지 않습니다. 예를 들어 sample $x_i$의 class가 1이면 한 slot만 1이고 class가 $-1$이면 5개 slot에 1이 들어가 마치 $x_i$에 대한 code와 같이 값이 들어가 있는 형태입니다.
즉, 첫번째 element만을 잘 뽑아내면 완벽한 classification이 가능합니다. 다만 이런 선행 정보가 전혀 없다면 adaptive methods가 $arg\min_w||Xw-y||^2$ 문제를 풀 때 이러한 classifier를 전혀 찾지 못한다는 것을 확인해보겠습니다.
먼저 이 문제가 lemma에서 얘기한 조건들을 만족한다는 것부터 보여야겠죠. $b=\sum_{i=1}^ny_i$이고 편의상 $b>0$라 할 때 (상당히 높은 확률로 large enough $n$에 대해 그럼직하죠), $u=X^Ty$라고 정의하면 $u$의 구조는 아래와 같습니다:
따라서 일단 $u$의 elements 중 값이 0인 원소가 존재하지 않아 lemma의 첫번째 조건을 만족하며, 두번째 조건 역시
*$<sign(u),x_i>=y_i+2+y_i(3-2y_i)=4y_i$이므로 scalar $c=4$가 존재합니다. 그러므로 lemma에 의해 AdaGrad의 해는 $w^{ada}\propto sign(u)$가 됩니다.
* paper에는 $<sign(u),x_i>$가 아닌 $<u,x_i>$로 되어있는데 잘못으로 보입니다.
따라서 임의의 양의 상수 $\tau$에 대해 $w^{ada}$는 언제나 0 혹은 $\pm \tau$를 원소로 갖습니다. 이제 새로운 데이터 $x^{test}$에 대해 이렇게 구한 해가 어떤 식으로 반응하는지 생각해봅시다. $x^{test}$와 $w^{ada}$ 둘 다 0이 아닌 유일한 features는 첫 3개 dimensions뿐입니다. 나머지는 서로 unique한 위치에 값을 갖기 때문에 곱하면 0일뿐이죠. 따라서 $w^{ada}$는 다음과 같이 처음 보는 데이터에 대해 항상 positive class로 분류하게 됩니다!!:
$$<w^{ada},x^{test}>=\tau(y^{test}+2)>0.$$
그럼 minimum norm solution은 어떤지 확인해볼까요? $\cal{P}$와 $\cal{N}$이 각각 positive 그리고 negative 예제들의 집합을 나타낼 때, $n_+=|\cal{P}|$이고 $n_-=|\cal{N}|$라 합시다. 이 때, symmetry에 의해 우리는 minimum norm solution이 아래와 같은 음이 아닌 상수 $\alpha_+$와 $\alpha_-$에 대해 $w^{SGD}=\sum_{i\in\cal{P}} \alpha_+ x_i -\sum_{j\in\cal{N}} \alpha_{-}x_j$ 와 같은 형태를 갖는 다는 것을 알 수 있습니다:
이 수식과 상수들을 계산하는 법은 논문의 Appendix를 참고하시면 됩니다 (논문의 주안점이 아니기 때문에 굳이 설명하지 않겠습니다).
우리가 원하는 것은 이런 해가 새로운 데이터에 대해 어떻게 반응하냐는 것이었죠? 위와 마찬가지로 $x^{test}$가 들어왔을 때, $x^{test}$와 $w^{SGD}$ 둘 다 0이 아닌 유일한 features는 첫 3개 dimensions뿐입니다:
$$<w^{SGD},x^{test}>=y^{test}(n_+\alpha_++n_-\alpha_-) + 2(n_+\alpha_+-n_-\alpha_-).$$
앞서 계산한 상수 $\alpha_+$와 $\alpha_-$에 의해 $n_+>N_-/3$일 때는 SGD는 언제나 제대로 분류를 한다는 것을 알 수 있습니다.
물론 이 예제가 약간 극단적이라 생각할 수 있습니다만, 생각보다 우리가 마주하는 기계학습 예제들의 상황과 상당히 비슷한 특징들을 잘 보여주고 있습니다. 보통 몇몇 feature들만을 사용하면 상당히 좋은 predictor를 만들 수 있지만 이를 처음부터 딱 알기는 쉽지 않습니다 (마치 첫번째 원소만 사용하면 되지만 선행지식이 없어 그렇게 classifier를 구성하지 못한 것과 같이). 게다가 많은 경우, 데이터의 feature들이 매우 sparse합니다. Training data가 finite할 경우 이런 feature들이 training data를 구별하는 것에는 매우 좋아 보일 수 있으나 사실 그 값들이 artifact로 인한 noise일 수도 있고 이에 맞춰 classifier를 만들 경우 over-fitting 현상이 생길 우려도 있기에 좋다고 할 수는 없습니다.
이 논문에서는 앞서 설명한 이론적 분석에 더불어서 실험적으로도 adaptive methods들로 구한 해들이 generalization performance가 non-adaptive methods로 구한 해에 비해 좋지 않다는 것을 확인해주는데요. 이 부분은 결과를 보시면 되기 때문에 이 글에서는 굳이 더 설명하지 않도록 하겠습니다.
내 멋대로 정리 및 결론
다시 한 번 이 논문에서 저자들이 주장하는 내용을 요약해보자면 아래와 같습니다:
- 같은 수의 hyperparameter tuning을 할 때, SGD와 SGD+momentum이 여타 adaptive methods들보다 모든 모델과 task들에 대해 dev/test set에서 우월한 결과를 보여줌.
- Adaptive methods들이 초기 학습 속도는 빠른 모습을 종종 보이긴 하지만 dev/test set에서 성능이 증가하는 것 역시 더 빠르게 더뎌지는 모습을 보임.
- Adaptive methods들이 주장하는 장점인 "less tuning needed"와는 다르게 모든 methods들에 동일한 정도의 tuning이 필요했음.
다만 GAN이나 Reinforcement Learning 분야의 경우 Adam이나 RMSProp과 같은 adaptive methods가 매우 잘 들어맞는 경우가 있고 이런 경우에 대해서는 저자들도 정확히 이유를 알지 못하겠다고 결론을 내립니다. 다음과 같이 추측을 할뿐인데요 이 부분은 뉘앙스가 애매할 수 있으므로 원문을 그대로 가져와 보겠습니다.
In our conversations with other researchers, we have surmised that adaptive gradient methods are particularly popular for training GANs [5, 18] and Q-learning with function approximation [9, 13]. Both of these applications stand out because they are not solving optimization problems. It is possible that the dynamics of Adam are accidentally well matched to these sorts of optimization-free iterative search procedures.
이 부분들은 사실 좀 애매한데요 GAN은 아마도 saddle 문제이기 때문에 이렇게 얘기하는 것 같습니다. Q-learning의 경우에도 전원석님이 답변해주신 내용을 여기에 정리해보자면 다음과 같습니다.
Deep reinforcement learning에서 RMSProp을 쓰는 주된 이유 중에 하나는 현재의 gradient update로 policy가 크게 바뀌면 앞으로 들어올 data가 망가지고 다음 policy에 악영향을 미쳐 전체 학습을 망치게 되는데 이를 방지하기 위함으로 알고 있습니다. 논문에서 최적화 문제가 아니라고 함은 아마 주어진 데이터셋이 있고 loss minimization을 하는 상황이 아니라는 걸 의미하지 않나 생각합니다.
결국 제가 보기에는 이 논문의 캐치 프레이즈였던 "SGD를 써라!"는 역시 case by case인 것으로 생각됩니다. 여전히 우리가 예측하지 못하는 혹은 보지 못하는 dark matter가 DL에는 남아있고 (물론 저자들은 자신들이 설정한 예제가 꽤나 broad한 설정이라고 주장하고 있지만) 항상 장님 코끼리 만지고 있는 것과 같이 매우 일부분의 degenerate한 경우일 수 있기에 이 논문만을 믿고 SGD만 사용하기보다는 역시 여러 시도를 해보는 수 밖에 없다는 어찌보면 싱거운? 결론에 이릅니다.
DARK MATTER IN DEEP LEARNING
하지만 여전히 이렇게 이론적으로 Deep learning의 요소들을 파헤쳐 설명하고자 하는 theoretical machine learning 분야는 참 매력적인 분야입니다. 왜 DL이 잘 working하는가를 설명하면서 새로운 디자인 방식과 같은 내용을 제안하는 연구들을 보면 매우 멋지죠. 제 꿈 중 하나가 이렇게 DL의 working principle을 이론적으로 파헤치는 것인데요 아직은 내공이 매우 부족하여 꿈으로만 그치고 있습니다. 느리더라도 거북이 같이 공부를 하다보면 언젠가는 닿을 수 있길 기대하고 있습니다.
다음 읽을거리
참고문헌:
Korean
English
