Stochastic Gradient Descent

오차역전파(back propagation), 경사 하강법(gradient descent)는 현재 많은 딥러닝 알고리즘들의 기저이다.
알고리즘의 성능은 훈련셋의 크기와 높은 상관관계를 가진다.

그렇지만 훈련셋의 크기가 커질수록 한 번의 학습과정에 필요한 연산 과정 또한 많아진다.
모든 학습과정에서 모든 데이터를 다룰 수 있으면 이상적이지만 그 과정의 비용이 단점이 된다.

100점을 얻고자 한다면 이 방법이 더 적절할수 있지만 이는 더 가능성이 없을 수 있다. boundary 가 없는 domain 에서의 global minimum 을 찾는 것은 불가능할지도 모르기 때문이다.

"출처 https://commons.wikimedia.org/wiki/File:Extrema_example.svg"

큰 훈련셋의 경우 다음과 같은 가정을 할 수 있다.
$∇f_{i}(x_{t})≈∇f(x_{t})$
풍부한 집단에서 표본집단이 모집단을 모방한다는 가정하에 Gradient Descent 는 Stochastic Gradient Descent 로 발전할 수 있다.

"출처 Deep Learning, Ian Goodfellow, Yoshua Bengio, and Aaron Courville, Book in preparation for MIT Press http://www.deeplearningbook.org , 2016"

Learning rate

위 알고리즘에서 가장 중요한 부분은 learning rate $\epsilon_k$이다. 위 알고리즘이 수렴하기 위해선 다음 두 조건이 필요하다.

$\sum^\infty_{k=1}{\epsilon_k}=\infty \\ \sum^\infty_{k=1}{\epsilon_k ^2} < \infty$

위 조건이 의미하는 바는 $\epsilon_k$가 감소하지만 학습의 유의미한 진행을 보장해야 한다는 것이다. 자명한 예시로 $\frac{1}{k}$를 떠올릴 수 있다.

완벽한 정답의 함수공간을 찾을 수 있다면 좋겠지만 우리가 딥러닝을 이용하는 이유는 주어진 문제나 데이터가 잘 짜여진 것인지 확신할 수 없고 주어진 domain 위에 완벽한 정답이 존재하는지 조차 확신할 수 없는 문제에서 강점이 있기 때문이다. 다시 말해, 정답이 아닌 최적값을 찾는 것에 집중되어있고 이때 오차의 허용값, 임계값을 사용한다.

"MIT Press book, Deep Learning" 교재에 따르면 다음의 learning rate 공식을 사용한다고 한다.

$\epsilon_k = (1 - \frac{k}{\tau})\epsilon_0 + (\frac{k}{\tau})\epsilon_\tau$

위 식은 $\tau$ 번의 반복 학습 과정에서 학습률이 $\epsilon_0$ 에서 $\epsilon_\tau$로 점차 바뀌는 것을 선형 보간법으로 나타낸 것이다.

주로 $\epsilon_{\tau}$ 는 $\epsilon_{0}$ 의 1% 정도로 사용한다. 그렇다면 $\epsilon_{0}$ 을 어떻게 정할지만 알면 된다.

initial learning rate $\epsilon_{0}$ 가 너무 크거나 너무 작은 경우 모두 cost 가 높을 수 있다. 적당한 값을 찾기 위해 100 번 정도의 반복 후 가장 좋은 perfomance 의 학습률보다 조금 높게 설정하는 것을 추천하고 있다. 다음의 포스팅에서 starting point 와 learning rate (step size) 에 따른 oscillation 을 볼 수 있다.

Properties

SGD 의 가장 큰 장점으로는 훈련셋의 크기가 커짐에 따라 훈련에 소요되는 시간이 커지지 않는다는 것이있다. 훈련셋의 크기와 관계없이 수렴성이 보장이 될 때, convergence rate 를 정의할 수 있다.

여기서 convergence rate 는 excess error $J(\theta) - min_{\theta '}J(\theta')$ 로 정의된다. 이는 현재의 cost 와 가능한 가장 작은 cost 와의 차이이다. SGD 가 convex 한 문제에 적용될 경우 $k$ iteration 이후 excess error 는 $O(\frac{1}{\sqrt{k}})$, strongly convex 일 경우 $O(\frac{1}{k})$ 이다.

SGD 이후 Local minima 를 빠져나오며 더 빠른 학습을 위해 Momentum, Nesterov Momentum, AdaGrad, RMSProp, Adam 등의 Optimazation Algorithms 이 생겨났다.

references
The schoastic method : "https://fa.bianp.net/teaching/2018/eecs227at/stochastic_gradient.html"
MIT Press book, Deep Learning : "https://www.deeplearningbook.org"