Optimizer

딥러닝 학습 시 최대한 틀리지 않은 방향으로 학습해야 한다. 이는 loss function의 최솟값을 찾는 것을 의미한다.

이때, 최솟값을 찾아가는 것(최적화 = Optimization)을 수행하기 위한 알고리즘이 최적화 알고리즘(= Optimizer)이다.

옵티마이저는 학습 속도를 빠르고 안정적이게하는 것을 목표로 한다.

 

아래 이미지는 여러 옵티마이저들이 어떻게 오차의 최저점을 찾아가는지 그래프로 나타낸 것이다.

여러 Optimizer

---

SGD(Stochastic Gradient Descent)

다변수 미분 이론에 바탕을 둔 가장 기본이 되는 optimizer이다.

다변수 함수 $f : R^n \rightarrow R$을 생각하자.

점 $x \in R^n$에서 함수 $f$가 가장 빨리 증가하는 방향은 gradient 방향 $\nabla f(x)$이고 가장 빨리 감소하는 방향은 gradient의 반대 방향 $-\nabla f(x)$이다.

 

SGD의 점화식은 $x_{n+1}=x_n-\eta\nabla f(x_n)$으로 주어진다.

여기서 $x_n$은 n번째 점의 위치이고 $\eta$가 클수록 큰 폭으로 움직인다.

 

현재 위치인 $x_n$에서 다음 위치인 $x_{n+1}$로 가장 빨리 감소하는 방향으로 가기 위해서 $-\nabla f(x_n)$을 더해주고 이때 보폭의 크기(= 학습률)는 $\eta$를 통해 조절해준다.

---

예시를 들어보자.

함수 $f(x,y)=x^2+y^2+xy-4x-8y$에 대해 초기위치 (0,0)에서 출발하여 학습률은 1/2로 경사하강법을 적용하려 할 때 두 걸음 이동한 위치를 구하면 어떤 값이 나올까?

 

우선 초기위치 (0,0)에서의 gradient는 $\nabla f(0,0)=(-4,-8)$임을 알 수 있다. 이 gradient 값은 증가하는 방향이다.

한 걸음 이동한 위치를 위의 점화식을 이용하여 나타내면, $x_1=(0,0)-\frac{1}{2}(-4,-8)$이다. 즉, $x_1=(2,4)$이다.

한 걸음 이동한 위치 (2,4)에서의 gradient는 $\nabla f(2,4)=(4,2)$이다.

 

이제 두 걸음 이동한 위치를 식으로 나타내면 $x_2=(2,4)-\frac{1}{2}(4,2)$이다. 즉, $x_2=(0,3)$이 된다.

[SGD] 두 걸음 이동한 위치 그래프

 

위에서 설명한 SGD는 극소점이나 안장점 근처에서는 $\nabla f(x_n)$의 크기가 작아져서 보폭도 작아진다. 따라서, 점 $x_n$이 최소점이 아니라 극소점 또는 안장점에 안착할 수도 있는 문제점이 있다.

local minimum에 빠지게 되는 예시 그래프

---

Momentum

Momentum은 Gradient Descent에 현재의 관성을 추가한다. 이는 관성을 통해 local minimum이나 평원에서 빠져 나올 수 있도록 하기위해 고안된 방법이다.

 

모멘텀의 점화식은 $v_n = \alpha v_{n-1}-\eta\nabla f(x_n), v_{-1}=0, x_{n+1}=x_n+v_n$으로 주어진다.

여기서 $v_n$은 속도, $v_{n-1}$은 관성, $\alpha$는 관성계수이다. 관성 계수 $\alpha$가 클수록 속도가 관성에 더 많은 영향을 받는다.

(a): SGD의 최적해를 찾아가는 등위선, (b): Momentum의 최적해를 찾아가는 등위선

---

함수 $f(x,y)=x^2+xy$에 대해 $\eta=1$과 관성계수 $\alpha=1$로 Momentum을 적용하려 하고 초기위치 $x_0=(1,1)$에서 출발하여 세 걸음 걸어갈 때 위치를 구해보자.

 

$\nabla f(x,y)=(2x+y,x)$이다.

초기위치에서의 속도는 $v_0 = -\eta\nabla f(x_0)=(-3,-1)$이다. 이때 초기위치에서의 이동은 관성이 존재하지 않기 때문에 관성을 계산하지 않는다.

한 걸음 이동한 위치는 $x_1=x_0+v_0=(1,1)+(-3,-1)=(-2,0)$이다.

 

한 걸음 이동한 위치에서의 속도는 $v_1=\alpha v_0-\eta\nabla f(x_1)=(-3,-1)-(-4,-2)=(1,1)$이다.

두 걸음 이동한 위치는 $x_2=x_1+v_1=(-2,0)+(1,1)=(-1,1)$이 된다.

 

위와 동일하게 계산해보면 두 걸음 이동한 위치에서의 속도는 $v_2=(2,2)$가 나오게 되고 세 걸음 이동한 위치는 $x_3=(1,3)$이 나오게 된다.

[Momentum] 세 걸음 이동한 위치 그래프

---

AdaGrad(Adaptive Gradient)

일정한 learning rate를 사용하지 않고 변수마다 그리고 step마다 learning rate가 바뀐다. 각 가중치에 각각의 learning rate를 사용한다는 뜻이다.

시간이 지날수록 learning rate는 줄어드는데 큰 변화를 겪은 변수의 learning rate는 대폭 작아지고 작은 변화를 겪은 변수의 learning rate는 소폭으로 작아진다. 큰 변화를 겪은 변수는 이미 최적에 가까워졌고 작은 변화를 겪은 변수는 최적에 아직 멀다고 생각하기 때문이다.

 

AdaGrad의 점화식은 $h_n=h_{n-1}+\nabla f(x_n)\odot\nabla f(x_n), h_{-1}=0, x_{n+1}=x_n-\eta\frac{1}{\sqrt{h_n}}\odot\nabla f(x_n)$이다.

여기서 $\odot$은 Hadamard product라고 불리우는 연산으로 벡터, 행렬을 좌표별 곱하기를 한다.

---

함수 $f(x,y)=x^2+xy$에 대해 $\eta=\frac{1}{2}$로 AdaGrad를 적용하려 할 때, 초기위치 $x_0=(1,1)$에서 두 걸음 걸어간 위치를 구해보자.

$\nabla f(x,y)=(2x+y,x)$이다.

벡터 $h_0=\nabla f(x_0)\odot\nabla f(x_0)=(3,1)\odot(3,1)=(9,1)$이다. $h_{-1}=0$이기에 생략했다.

한 걸음 이동한 위치는 $x_1=x_0-\eta\frac{1}{\sqrt{h_0}}\odot\nabla f(x_0)=(1,1)-\frac{1}{2}(\frac{1}{3},1)\odot(3,1)=(\frac{1}{2},\frac{1}{2})$이다.

 

벡터 $h_1=h_0+\nabla f(x_1)\odot\nabla f(x_1)=(9,1)+(\frac{3}{2},\frac{1}{2})\odot(\frac{3}{2},\frac{1}{2})=(9,1)+(\frac{9}{4},\frac{1}{4})=(\frac{45}{4},\frac{5}{4})$이다.

두 걸음 이동한 위치는 $x_2=x_1-\eta\frac{1}{\sqrt{h_1}}\odot\nabla f(x_1)=(\frac{1}{2},\frac{1}{2})-\frac{1}{2}(\frac{2}{3\sqrt{5}},\frac{2}{\sqrt{5}})\odot(\frac{3}{2},\frac{1}{2})=(\frac{1}{2}-\frac{1}{2\sqrt{5}},\frac{1}{2}-\frac{1}{2\sqrt{5}})$이다.

[AdaGrad] 두 걸음 이동한 위치 그래프

---

RMSProp

AdaGrad는 step이 많이 진행되면 누적치 $h_n$이 너무 커지기에 학습률이 너무 작아져 학습이 거의 되지 않는 문제가 있다. 이를 보완하기 위해 RMSProp은 이전 누적치와 현재 gradient의 좌표별 제곱의 가중치 평균을 생각한다.

이는 AdaGrad보다 최근 값을 더 반영하게 해준다.

 

RMSProp의 점화식은 $h_n=\gamma h_{n-1}+(1-\gamma)\nabla f(x_n)\odot\nabla f(x_n),h_{-1}=0, x_{n+1}=x_n-\eta\frac{1}{\sqrt{h_n}}\odot\nabla f(x_n)$이다.

forgetting factor(decay rate)인 $\gamma$가 클수록 과거가 중요하고 작을수록 현재가 중요하다.

---

함수 $f(x,y)=xy$에 대해 $\eta=1$과 $\gamma=\frac{3}{4}$로 RMSProp을 적용하려 한다. 초기위치 $x_0=(1,2)$에서 출발하여 두 걸음 이동한 위치를 구해보자.

$\nabla f(x,y)=(y,x)$이다.

벡터 $h_0=\frac{3}{4}(0,0)+\frac{1}{4}\nabla f(x_0)\odot\nabla f(x_0)=\frac{1}{4}(2,1)\odot(2,1)=(1,\frac{1}{4})$이다.

한 걸음 이동한 위치는 $x_1=x_0-\eta\frac{1}{\sqrt{h_0}}\odot\nabla f(x_0)=(1,2)-(1,2)\odot(2,1)=(-1,0)$이다.

 

벡터 $h_1=\frac{3}{4}h_0+\frac{1}{4}\nabla f(x_1)\odot\nabla f(x_1)=(\frac{3}{4},\frac{3}{16})+\frac{1}{4}(0,1)=(\frac{3}{4},\frac{7}{16})$이다.

두 걸음 이동한 위치는 $x_2=x_1-\eta\frac{1}{\sqrt{h_1}}\odot\nabla f(x_1)=(-1,0)-(\frac{2}{\sqrt{3}},\frac{4}{\sqrt{7}})\odot(0,-1)=(-1,0)-(0,-\frac{4}{\sqrt{7}})=(-1,\frac{4}{\sqrt{7}})$이다.

[RMSProp] 두 걸음 이동한 위치 그래프

 

---

Adam(Adaptive Momentum Estimation)

Momentum과 RMSProp 두가지 방식을 합쳐 놓았다. 현재 가장 많이 쓰이는 optimizer이다.

가중치 $\beta_1$으로 Momentum을 변형하여 점화식 $m_n=\beta_1m_{n-1}+(1-\beta_1)\nabla f(x_n),m_{-1}=0$을 생각하고 가중치 $\beta_2$로 AdaGrad를 변형하여 점화식 $v_n=\beta_2v_{n-1}+(1-\beta_2)\nabla f(x_n)\odot\nabla f(x_n),v_{-1}=0$을 생각한다.

초기치가 $m_{-1}=0,v_{-1}=0$때문에 가중치 $\beta_1,\beta_2$가 1에 가까우면 0에 편향된다.

이를 보정한 값 $\hat{m}_n=\frac{m_n}{1-{\beta_1}^{n+1}},\hat{v}_n=\frac{v_n}{1-{\beta_2}^{n+1}}$을 생각한다.

점의 이동은 점화식 $x_{n+1}=x_n-\eta\frac{1}{\hat{v}_n}\odot\hat{m}_n$을 따른다.

---

함수 $f(x,y)=xy$에 대해 $\eta=1$과 $\beta_1=\beta_2=\frac{1}{2}$로 Adam을 적용하려 한다. 초기위치 $x_0=(1,2)$에서 출발하여 두 걸을 이동한 위치를 구해보자.

$\nabla f(x,y)=(y,x)$이다.

$m_0=\beta_1m_{-1}+(1-\beta_1)\nabla f(x_0)=\frac{1}{2}(0,0)+\frac{1}{2}(2,1)=(1,\frac{1}{2})$이며,

$v_0=\beta_2v_{-1}+(1-\beta_2)\nabla f(x_0)\odot\nabla f(x_0)=\frac{1}{2}(0,0)+\frac{1}{2}(2,1)\odot(2,1)=(2,\frac{1}{2})$이다.

$\hat{m}_0=\frac{m_0}{1-\beta_1}=(2,1)$이고 $\hat{v}_0=\frac{v_0}{1-\beta_2}=(4,1)$이다.

 

이제 한 걸음 이동한 위치를 구해보면 $x_1=x_0-\eta\frac{1}{\sqrt{\hat{v}_0}}\odot\hat{m}_0=(1,2)-(\frac{1}{2},1)\odot(2,1)=(0,1)$이 나오게 된다.

 

위와 동일한 과정으로 식을 세워 풀어나가 보자.

$m_1=\beta_1m_0+(1-\beta_1)\nabla f(x_1)=(\frac{1}{2},\frac{1}{4})+\frac{1}{2}(1,0)=(1,\frac{1}{4})$이고

$v_1=\beta_2v_0+(1-\beta_2)\nabla f(x_1)\odot\nabla f(x_1)=(1,\frac{1}{4})+\frac{1}{2}(1,0)\odot(1,0)=(\frac{3}{2},\frac{1}{4})$이다.

$\hat{m}_1=\frac{m_1}{1-{\beta_1}^2}=(\frac{4}{3},\frac{1}{3})$이고 $\hat{v}_1=\frac{v_1}{1-{\beta_2}^2}=(2,\frac{1}{3})$이다.

 

두 걸음 이동한 위치는 $x_2=x_1-\eta\frac{1}{\sqrt{\hat{v}_1}}\odot\hat{m}_1=(0,1)-(\frac{1}{\sqrt{2}},\sqrt{3})\odot(\frac{4}{3},\frac{1}{3})=(-\frac{2\sqrt{2}}{3},1-\frac{1}{\sqrt{3}})$이다.

[Adam] 두 걸음 이동한 위치 그래프