Before reivew
오랜만에 X-Review 입니다. 오늘의 주제는 gradient descent를 기반으로하는 optimization algorithm들의 전체적인 concept을 살펴보고자 준비했습니다. 주제가 optimization이다 보니 어쩔 수 없이 Review에 수식이 많이 들어갔습니다. 최대한 이해하실 수 있도록 문장으로도 서술을 해놨으니 천천히 읽으시면 큰 무리는 없을 거라 생각이 듭니다. 저는 이제 Adam 같은 경우는 그냥 막연하게 SGD 보다 좋더라 이렇게 알고 있어서 막 사용하고 있었는데 이번 기회에 optimization을 정리해보면서 또 많이 배워갈 수 있었습니다.
Introduction
Gradient descent 알고리즘은 Neural Network를 최적화 시키는 방법으로 가장 흔하게 사용되는 방법입니다. 하지만 이런 알고리즘은 가끔 black-box optimizer로써 사용이 되기도 합니다. 명확한 이해와 설명없이 그냥 경험적인 이유로 사용하는 경우가 종종 있습니다. 본 paper의 목표는 제목에서도 느낄 수 있듯이 다양한 gradient descent optimization 알고리즘들을 알아보고 어떻게 선택할지에 대한 이해를 가져다 주는 것입니다. Gradient descent 알고리즘은 objective function : J(\theta ) 을 최소화 하는 방법으로 사용이 되고 있습니다. 본격적으로 Gradient Descent를 설명하기 전에 간단한 미적분 얘기를 하고 넘어가겠습니다.
- Gradient and Multivariable Function
보통 Gradient Descent 알고리즘을 설명할 때 사용하는 가장 간단한 그림입니다. 현재 위치에서 기울기 방향으로 weight를 조금씩 움직여줘서 minimum에 도달하게 한다!! 이런 방식입니다. 이런 일변수 함수는 기울기의 방향이 왼쪽 오른쪽 두가지 뿐입니다. 하지만 사실 Objective Function 같은 경우는 저렇게 독립변수를 하나만 가지지 않습니다. 아래의 그림과 같이 여러개의 각각 독립적인 weight를 가지는 Multivariable Function 다변수 함수로 구성이됩니다. 다변수 함수 같은 경우는 어느 지점에서 기울기의 방향이 사방 팔방으로 튈 수 있습니다. 이럴때 바로 Gradient는 단순한 기울기가 아닌 어느 지점에서 최대 증가 방향으로의 기울기입니다. 우리는 Objective function의 최소지점을 찾아야 하니 최대 증가 방향의 반대 방향으로 조금씩 움직여주겠다 라는 것이 Gradient Descent의 아이디어 입니다.
weight=weight-\nabla_{\theta } Loss(\theta ) : weight update rule
Gradient Descent variants
본 Paper에서 소개하는 3가지 Gradient Descent 알고리즘이 있습니다. 핵심은 사용할 Data의 양과 Speed 입니다.
- Batch Gradient Descent
Batch Gradient Descent는 하나의 Parameter를 Update 해줄 때 전체 train dataset을 이용하여 Update 해주는 방식입니다. 당연히 전체 train dataset을 이용하니 방향성은 정확하겠지만 수렴속도가 굉장히 느리다는 단점이 있습니다. 본 Paper에서 Loss 함수가 Convex 하다면 반드시 Global Optimum에 도달할 수 있고 , Non-Convex 하다면 Local Optimum에는 반드시 도달할 수 있다고 나와있습니다.
- Stochastic Gradient Descent
Stochastic Gradient Descent는 하나의 Parameter를 Update 해줄 때 하나의 sample train data를 이용하여 Update 해주는 방식입니다. 당연히 데이터를 하나만 사용하니 전체적인 속도는 굉장히 빠르다는 장점이 있습니다. 다만 하나의 sample data만을 사용하기 때문에 방향이 전체적으로 변동성을 크게 가지게됩니다. 이러한 변동성때문에 Stochastic Gradient Descent 같은 경우는 local minima에 빠져도 꽤 잘 빠져나올 수 있다고 합니다. 하지만 변동성이 크기 때문에 정확한 값에 수렴을 할 수가 없을 수도 있습니다.
- Mini-Batch Gradient Descent
이제 이 Mini-Batch Gradient Descent는 Batch + Stochastic의 중간 버전이라고 생각하시면 됩니다. 적당한 그룹의 Batch-size를 설정하여 어느 정도 변동성을 줄이고 속도 또한 가져가는 Data양과 Speed 사이의 Trade-off 관계를 충족시킨 알고리즘이라고 보시면 됩니다.
Challenges
이런 Gradient Descent 알고리즘의 한계는 무엇이 있을 까요?
- Learning rate의 설정 문제입니다.. learning rate가 너무 작으면, 수렴하는데 오랜 시간이 필요하고 반대로 너무 크면, 최소값 근처에서 변동하거나 심지어 벗어날 수 있어 수렴을 방해합니다.
- 동일한 learning rate가 모든 parameter 갱신에 적용됩니다. 만약 data가 sparse하고 features가 제각각 다른 빈도수를 지니고 있으면, 이 모든 것들을 동일한 정도로 update하면 안됩니다. 드물게 발생하는 feature에 대해서는 크게 크게 update 해야합니다.
- Global Optimum이 아닌 local minima와 안장점(saddle point) 빠질 위험이 있습니다. 안장점은 평면으로 둘러싸여 있어 기울기가 0인 지점을 의미합니다. 이런 안장점을 빠져나오는 데에도 Gradient Descent가 힘을 못쓴다고 합니다.
Gradient descent optimization algorithms
이제 앞서 얘기한 한계점들을 극복하기 위해 고안된 다른 optimization 알고리즘들에 대해 알아보도록 하겠습니다.
momentum
쉽게 얘기하면 관성을 이용한다고 표현합니다. 단순히 Gradient 방향으로만 움직이는 것이 아니라 이전 step 방향까지 고려해서 update 하는 방식입니다. 경사면에서 굴러가는 공의 방향과 속도를 바꾸는게 어렵듯이 , SGD에 관성을 추가하여 갑자기 방향을 바꾸기 어렵게하고 이전과 동일한 방향으로 나아갈 때는 가속이 작용되도록 합니다.
방향을 바꾸기 어렵기 때문에 진동이 감소하고 , 동일한 방향에 대해서는 가속이 붙기 때문에 수렴속도가 증가하게 됩니다.
또한 local minima에 빠져도 기존에 가던 관성이 존재하기 때문에 local minima를 뛰쳐나올 가능성도 증가하게 됩니다.
- v_{t}=\gamma v_{t}+\eta \nabla_{\theta } J(\theta )
- \theta =\theta -v_{t}
하지만 단점도 존재합니다. 경사가 급한 내리막길에서는 관성이 크게 작용하여 가속이 심하게 붙을 것 입니다. 경사를 타고 내려와 이제 global minima에 안착을 하고 싶은데 속도가 너무 빨라서 다시 그 minima를 벗어나 다른곳으로 뛰쳐나갈 위험이 존재합니다. 즉 , 브레이크를 걸어야 하는 상황입니다. 이런 문제점을 보완한것이 NAG , Nesterov acclerated gradient 입니다.
Nesterov accelerated gradient
방식은 Momentum과 비슷한데 Gradient를 계산하는 방식이 조금 다릅니다.
Momentum 방식에서는 momentum 방향과 Gradient 방향을 각각 구한뒤 합쳐주는 방식이지만 Nesterov 방식에서는 일단 Momentum 방향으로 먼저 움직여주고 그 자리에서 Gradient 방향으로 update하는 방식을 취하고 있습니다. 이렇게 하면 어떤 점이 좋냐 먼저 Momentum 같은 경우에는 멈춰야 하는 시점임에도 불구하고 관성으로 인해 멀리 벗어날 수 있다는 단점이 존재합니다. 하지만 NAG 같은 경우는 momentum 방향으로 움직이고 그 자리에서 어느 방향으로 이동 할지를 결정하는 구조이기 때문에 보다 더 신중하다고 볼 수 있습니다.
- v_{t}=\gamma v_{t-1}+\eta \nabla_{\theta } J(\theta -\gamma v_{t-1})
- \theta =\theta -v_{t}
내리막 길에서 momentum 과 Gradient에 힘입어 그대로 쭉 내려가는 것이 아니라 momentum 만큼만 먼저 내려가 보고 그 위치가 minima 근처라면 이제 Gradient는 작을 테니깐 그제서야 제자리를 찾아가주는 좀 더 현명한 알고리즘이라고 보시면 되겠습니다.
Adagrad
이제는 살짝 방향이 달라집니다. 이전까지는 momentum을 기반으로한 알고리즘이었다면 이제 핵심은 adaptive learning rate 입니다.
한줄로 요약하면 빈번하게 등장하는 parameter는 적게 갱신하고 , 드물게 등장하는 parameter는 크게 크게 갱신을 해주는 방법입니다. 갱신를 자주 해준 parameter들의 경우는 optimum에 가까이 있을 확률이 높기 때문에 작은 크기로 이동하면서 세밀한 값을 조정하고, 적게 변화한 변수들은 optimum 값에 도달하기 위해서는 많이 이동해야할 확률이 높기 때문에 먼저 빠르게 loss 값을 줄이는 방향으로 이동하려는 방식이라고 생각할 수 있습니다.
- G_{t}=G_{t-1}+(\nabla_{\theta_{t} } J(\theta_{t,i} ))^{2}
- \theta_{t+1} =\theta_{t} -\frac{\eta }{\sqrt{G_{t}+\epsilon } } \odot \nabla_{\theta_{t} } J(\theta_{t} )
G_{t}라는 변수가 등장하는 데 설명을 드리면 본 Paper 상에서는 n by n 행렬의 대각행렬이라고 표현을 해주는 데 n by n 행렬의 대각 성분은 결국 n 개의 성분이 존재하는 vector가 됩니다.
따라서 G_{t} 를 n개의 element를 가지는 vector로 정의해주겠습니다. 여기서 n은 parameter의 갯수입니다.
G_{t}가 재귀적으로 약간 고등학교 수학시간때 배운 점화식 형태로 정의가 되어있는데 쉽게 표현해주면 어느 시점 t 까지 각각 parameter들의 Gradient 제곱을 누적 합 해준것이라고 보시면 됩니다. 제곱을 더해주는 이유는 음수가 나와서 값이 줄어들면 정확한 비교가 힘들기 때문에 제곱을 해준 것입니다.
즉 , 학습을 시작했을 때 부터 현재 학습이 진행되고 있는 시점 t 까지 각각 parameter들이 얼만큼 갱신 됐는지를 알려주는 값이라고 생각하시면 됩니다.
- \theta =<w_{1},w_{2},\cdots w_{n-1},w_{n}>
- G=<\sum^{t}_{k=0} (\frac{\partial J(\theta )}{\partial w_{1,k}} )^{2},\sum^{t}_{k=0} (\frac{\partial J(\theta )}{\partial w_{2,k}} )^{2},\cdots ,\sum^{t}_{k=0} (\frac{\partial J(\theta )}{\partial w_{n,k}} )^{2}>
예를 들어 G1이 비교적 큰 값을 가지고 있다 라는 말은 \theta =<w_{1},w_{2},\cdots w_{n-1},w_{n}> 중에서 w1이 자주 갱신 됐다는 얘기일테고 G3가 비교적 작은 값을 가지고 있다 라는 말은 w3가 적게 갱신 됐다는 얘기입니다.
이제 이 G_{t}라는 값을 learning rate에 나눠 줌으로써 G_{t}가 크면 자주 갱신 된 값이므로 적은 learning rate를 가지도록 G_{t}가 작으면 적게 갱신 된 값이므로 큰 learning rate를 가지도록 조정해주는 것 입니다.
장점으로는 learning_rate를 이제 신경써주지 않아도 된다고 합니다. 자동으로 맞춰주기 때문에 0.01 정도로만 초기화 시켜두고 신경써주지 않습니다. 다만 G_{t}에는 계속 제곱 항이 더해지기 때문에 학습이 오래 진행되다 보면 step size가 너무 작아져 거의 움직이지 않는 다는 단점이 존재합니다. 이를 보완하여 고친 알고리즘이 Adadelta 와 RMSProp 입니다.
RMSProp
Adagrad의 문제는 학습 시간이 길어지면 G_{t} 에 계속 Gradient의 제곱 항이 더해지므로 G_{t} 값이 계속 커지게 되고 결국 Learning rate가 매우 작아져 step이 멈춰 버립니다.
지금 말씀드릴 RMSProp는 논문으로 나온 방법은 아니고 제프리 힌턴 교수님이 코세라 강의중에 고안하신 방법입니다.
G_{t}를 구해줄 때 막연하게 제곱을 쭉쭉 더해주는 것이 아니라 일종의 가중치를 곱해줘서 G_{t}가 적정크기로 존재할 수 있도록 제한 해준 알고리즘 입니다.
- \theta_{t+1} =\theta_{t} -\frac{\eta }{\sqrt{G_{t}+\epsilon } } \odot \nabla_{\theta_{t} } J(\theta_{t} )
- G_{t}=\gamma G_{t-1}+(1-\gamma )(\nabla_{\theta } J(\theta ))^{2}
\gamma 라는 decaying factor라는 weight들을 곱해줌으로 써 train을 오래하도 G_{t}가 계속 해서 커지지 않습니다. 따라서 learning rate가 0으로 작아져버리는 문제는 어느정도 해소가 됩니다.
본 Paper에서 얘기하는 최적화 알고리즘이 아직 많이 남아있고 수식도 더 복잡하니 남아 있는 알고리즘 분석과 Conclusion은 다음주에 마무리 짓는 것으로 하겠습니다.
