Stochastic Gradient Descent Methods

이 포스팅은 Machine Learning의 optimizer로 가장 많이 사용하는 optimization method인 stochastic gradient methods에 관한 내용이다. 사실 거의 모든 ML분야에서 사용하기 때문에 매우 일반적인 기술이 필요한것이 사실이다. wiki에 보면 SGD와 ML에서 자주 사용하는 optimization methods에 대해 잘 기술되어 있다. 그러나, 보다 specific한 입장에서 이것을 살펴보는 것이 이해측면에서 더 유리할 때가 많으므로, 대상을 정하기로 하고 reinforcement learning에서 value function approximation을 위한 관점에서 이에 대해 살펴보기로 하자.

v(s)를 예측하기 위한 approximation function을 \hat{v} (s, \boldsymbol{\theta})이라고 할때, 좋은 방법중 하나는 실제 sample의 결과를 이용하여 error를 최소화 하는 방법이다. Stochastic Gradient Descent methods는  이 error를 최소화하는 방향으로 weight vector \boldsymbol{\theta}를 조정하는 방법을 사용한다.

rl-eq9-49-5

여기서 \alpha는 step-size parameter이며, \nabla f(\boldsymbol{\theta})는 weight vector component에 관한 partial derivative vector이다.

rl-eq9-6

SGD methods가 “gradient descent” method라고 불리우는 이유는 parameter(weight)가 error함수의 negative gradient와 비례하여 변하기 때문이다. 특히, 이 방법을 stochastic하게 선택된 하나의 example에 대해서만 적용하기 때문에 “stochastic”이라는 용어를 사용한다. 이 방법을 여러 sample에 대해서 적용하다 보면, 전체적으로 MSVE와 같은 평균 성능지표를 최소화하는 방향으로 움직이게 된다.

한편, step-size parameter를 사용하여 weight의 수정을 조금씩만 하는 이유를 고려할 필요가 있다. 가장 근본적인 이유는 SGD가 특정 sample의 error 결과를 이용하여 weight parameter를 수정하기 때문에 한 sample기준으로 모든 parameter를 수정하는 것은 바람직하지 않기 때문이다. 즉, error를 줄이는 것은 모든 sample을 고려하여 평균 error를 줄이는 뱡향이로 가려면,  parameter수정에 있어 여러 sample들간의 balance를 생각해야 한다.

이제, target output을 U_t \in \mathbb{R}이라고 할때, 이것이 true value v_{\pi} (S_t)가 아닌 경우에 대해 생각해 보자. 이 경우 우리는 앞서 보인 exact  update를 수행할수 없으나, v_{\pi} (S_t)대신에 U_t 를 사용해서 다음과 같이 parameter update를 할 수 있다.

RL eq9.7.png

만약, U_t 가 unbiased etimate이라고 한다면, parameter \theta\alpha가 점차 감소하는 값을 갖는한 local optimum에 도달할 수 있다. 예를 들어 policy\pi를 따라 environment와 interaction을 하여 얻은 state의 실제값은 return값의 기대치이기 때문에 Monte Carlo target U_t \doteq G_t는 v_{\pi} (S_t) 의 unbiased estimate값이다. 그러므로 state-value prediction의 Monte Carlo version은  local optimal solution에 수렴하게된다. 이 algorithm의 pseudocode는 아래와 같다.

rl-gradient-monte-carlo-algorithm

그렇지만, targetU_t를 위해 v_{\pi} (S_t) bootstrapping방법을 사용한다면, 수렴이 보장되지 않는다. Target value자체가 bootstrapping을 통한 parameter \theta에 따라 변하기 때문이다. 그러므로 bootstrapping methods는 본질적으로 gradient method라고 보기 어렵다. 수학적으로 target의 parameter(weight)에 대한 변화에 의한 효과를 무시하기 때문이다. 그러므로 이것을 semi-gradient method라고 부른다.

비록 semi-gradient method가 모든 경우에 대한 수렴이 보장되지 않지만, linear case와 같은 많은 중요한 경우에 수렴이 된다. 더군다나, 학습속도가 빠르고, update를 위해 episode종료시점까지 기다릴 필요 없이 online 학습을 가능하게 해주므로 더 선호된다. Target으로 U_t = R_{t+1} + \gamma \hat{v}(S_{t+1}, \theta)를 사용하는 semi-gradient TD(0) method에 대한 algorithm을 아래 나타내었다.

rl-semi-gradient-td0-algorithm

Advertisements

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중