Adaptive Gradient Optimizer

Adagrad(Adaptive Gradient) Optimizer는 목적함수 \(f\)의 최솟값을 찾는 알고리즘으로 기본 철학 및 아이디어는 다음과 같다.

  • 변수들이 update하는 방향과 크기를 목적함수 \(f\)의 gradient와 이전 단계에서의 변화량을 고려하려 결정한다. 이전 단계에서 변화량이 큰 변수들은 update를 작게하고 변화량이 작은 변수들은 update를 크게 한다. 즉, 변화를 크게했던 변수들은 최솟값 근처에 도달했을 것이라고 생각하고 update 크기를 작게하고 변화를 작게했던 변수들에 대해서는 최솟값에 도달하기 위해서 더 큰 값으로 update 한다(소득 재분배 같은 느낌).

Adagrad Optimizer는 다음과 같이 목적함수 \(f\)의 최솟값을 찾는다.

  • 초기값 \(x_0\)와 적당한 Learning rate \(\alpha\), \(\varepsilon\) 설정
  • \(n\geq 0\)인 정수에 대해서 \(a_{n+1}\)과 \(x_{n+1}\)은 다음과 같이 정의
\[a_{n+1} := a_n + \nabla f(x_n)\odot \nabla f(x_n) , \quad a_0 := 0\] \[x_{n+1} := x_n - \frac{\alpha}{\sqrt{a_{n+1}+\varepsilon}} \odot \nabla f(x_n)\]

\(\varepsilon\)은 분모에 0이 되는 것을 방지하는 수로 보통 0.01 정도의 작은 값을 대입한다. 여기서, 벡터 \(a_{n+1}\)과 상수 \(\varepsilon\)의 합은 broad casting해서 연산한 \(a_{n+1} + \varepsilon\cdot (1,1,...,1)\) 을 의미하고 \(\odot\)은 element wise 곱을 의미한다. 예를 들어서 \((1,2,3) \odot (1,2,3) = (1,4,9)\) 이다. 즉, Adagrad Optimizer에서 update 방향은 (\(-\nabla f\)) 벡터 방향이 아니라 (\(-\nabla f\))와 Adaptive 벡터와의 element wise 곱 방향이다.

Adagrad의 단점은 학습 초기에 변수들이 update하는 양이 learning rate \(\alpha\)와 비슷한 값이기 때문에 초기 update 속도가 느리다. 또한 학습을 진행하면서 \(a_n\)들이 계속 증가해 update하는 양이 지나치게 작아져서 제대로 update가 되지 않는 문제가 있다.


방정식 \(2\cdot x=10\) 의 근을 Adagrad 알고리즘을 이용해서 찾아보자.

  • 목적함수 \(f(x):=(2x-10)^2\) 정의
  • 초기값 \(x_0 = 0\), Learning rate \(\alpha=0.05\), \(\varepsilon = 0.01\)로 설정

\(f'(x) = 4(2x-10)\)이므로 \(a_1\)과 \(x_1\)은 다음과 같이 구할 수 있다.

\[a_1 = a_0 + (f'(x_0))^2 = 0 + 1600 = 1600\]

그리고

\[\begin{align*} x_1 &= x_0 - \frac{\alpha}{\sqrt{a_1 +\varepsilon}} \cdot f'(x_0) \\ &= 0 - \frac{0.05}{\sqrt{1600+0.01}} \cdot (-40)=0.0499998. \end{align*}\]

같은 방법으로 \(a_2\)과 \(x_2\)은 다음과 같이 구할 수 있다.

\[a_2 = a_1 + (f'(x_1))^2 = 1600 + 1568.1601267 = 3168.1601267,\]

그리고

\[\begin{align*} x_2 &= x_1 - \frac{\alpha}{\sqrt{a_2 +\varepsilon}} \cdot f'(x_1) \\ &= 0.0499998 - \frac{0.05}{\sqrt{3168.1601267+0.01}} \cdot (-39.6000016)=0.085177. \end{align*}\]

반복적으로 이 같은 작업을 수행하면 \(x_n\)의 수열을 다음과 같이 얻을 수 있다.

\[(x_n) = (0, 0.0499998, 0.085177, 0.11381, 0.138548, 0.16063, ...)\]

\(x_n\)이 5로 수렴해야 하는데 초기에 업데이트 되는 속도가 Gradient DescentMomentum 알고리즘과 비교해서 수렴 속도가 느린 것을 확인 할 수 있다(초기 변화량은 learning rate와 비슷하다).


TensorFlow code

# 방정식 2*x = 10 을 만족하는 x 찾기
# x 초깃값 = 0

import tensorflow as tf
import matplotlib.pyplot as plt

%matplotlib inline

X = tf.Variable(0.)
Y = tf.constant(10.)
H = 2 * X

# learning rate = 0.05, epsilon = 0.01
loss = tf.square(H-Y)
optimize = tf.train.AdagradOptimizer(0.05, initial_accumulator_value=0.01).minimize(loss)


sess = tf.Session()
sess.run(tf.global_variables_initializer())
sequence = []

for i in range(10):
    print("x_%i = %s" %(+i, sess.run(X)))
    sess.run(optimize)
    sequence.append(sess.run(X))

plt.suptitle("Sequence of x", fontsize=20)
plt.ylabel("x value")
plt.xlabel("Steps")
plt.plot(sequence, "o")

RMSProp Optimizer

RMSProp Optimizer는 Adagra Optimizer가 학습을 계속 진행할 수록 update하는 지나치게 작아져서 update가 제대로 이루어지지 않는 문제를 해결하기 위해서 제안된 알고리즘으로 \(a_{n+1}\)을 \(a_n\)과 \(\nabla f(x_n)\odot \nabla f(x_n)\)의 합으로 정의하는 것이 아닌 다음과 같이 지수이동평균(Exponential Moving Average), decay rate(\(\gamma\)) 으로 정의한다.

\[a_{n+1} := \gamma \cdot a_n + (1-\gamma)\nabla f(x_n)\odot \nabla f(x_n) , \quad a_0 := 0\] \[x_{n+1} := x_n - \frac{\alpha}{\sqrt{a_{n+1}+\varepsilon}} \odot \nabla f(x_n)\]

Decay rate \(\gamma\)는 보통 0.9나 0.99로 설정한다.


방정식 \(2\cdot x=10\) 의 근을 RMSProp 알고리즘으로 찾아보자.

  • 초기값 \(x_0 = 0\), Learning rate \(\alpha=0.05\), decay rate \(\gamma = 0.9\), \(\varepsilon = 0.01\)로 설정
\[a_1 = \gamma\cdot a_0 + (1-\gamma)\cdot(f'(x_0))^2 = 0.9 \cdot 0 + 0.1\cdot 1600 = 160,\] \[x_1 = x_0 - \frac{\alpha}{\sqrt{a_1 +\varepsilon}} \cdot f'(x_0) = 0 - \frac{0.05}{\sqrt{160+0.01}} \cdot (-40)=0.1580645.\]

같은 방법으로 \(a_2\)와 \(x_2\)는 다음과 같이 구할 수 있다.

\[a_2 = \gamma\cdot a_1 + (1-\gamma)\cdot(f'(x_1))^2 = 0.9 \cdot 160 + 0.1\cdot 1500.4377207 = 294.0437721,\] \[x_2 = x_1 - \frac{\alpha}{\sqrt{a_2 +\varepsilon}} \cdot f'(x_1) = 0.1580645 - \frac{0.05}{\sqrt{294.0437721+0.01}} \cdot (-38.735484)=0.2710091.\]

Adagrad 알고리즘 보다 초반에 빠르게 최적값으로 수렴하는 것을 확인 할 수 있다.


TensorFlow code

\(x_n\)의 계산값과 TensorFlow의 출력값과 약간의 오차가 존재한다.

# 방정식 2*x = 10 을 만족하는 x 찾기
# x 초깃값 = 0

import tensorflow as tf
import matplotlib.pyplot as plt

%matplotlib inline

X = tf.Variable(0.)
Y = tf.constant(10.)
H = 2 * X

# learning rate = 0.05, decay = 0.9, epsilon = 0.01
loss = tf.square(H-Y)
optimize = tf.train.RMSPropOptimizer(0.05, decay=0.9, epsilon=0.01).minimize(loss)


sess = tf.Session()
sess.run(tf.global_variables_initializer())
sequence = []

for i in range(10):
    print("x_%i = %s" %(+i, sess.run(X)))
    sess.run(optimize)
    sequence.append(sess.run(X))

plt.suptitle("Sequence of x", fontsize=20)
plt.ylabel("x value")
plt.xlabel("Steps")
plt.plot(sequence, "o")