딥러닝 이론: 5-2. 최적화와 지수가중평균

milkbuttercheese·2023년 2월 9일
Dive into Deeplearning
0

Dive_into_Deeplearning

목록 보기
7/7

지수가중평균 Exponentially Weighted Average

  • 지수 가중평균이란 데이터의 이동평균을 구할 때 오래된 데이터가 미치는 영향을 지수적으로 감쇄시켜 계산하는 방식이다
  • Vt=βVt−1+(1−β)×ΘtV _{t}=\beta V _{t-1}+(1-\beta) \times \Theta _{t}
    - 이때 β\beta 는 0과 1사이 하이퍼파라미터, Θ\Theta 는 새로들어온 데이터, VtV _{t} 현재 상태변수로 볼 수 있다
  • Vt−1=βVt−2+(1−β)×Θt−1V _{t-1}=\beta V _{t-2}+(1-\beta) \times \Theta _{t-1} 인것을 고려하면
    - Vt=β(βVt−2+(1−β)×Θt−1)+(1−β)Θt−2V _{t}=\beta(\beta V _{t-2}+(1-\beta) \times \Theta _{t-1})+(1-\beta)\Theta _{t-2} 인데 이를 보면
    - Vt−2V _{t-2} 의 계수는 β2\beta ^{2} 로 현재상태 VtV _{t} 를 계산할 때 ll 만큼의 이전상태 Vt−lV _{t-l} 는 βl\beta ^{l} 만큼 가중치를 갖는다는 것을 알 수 있다. 이는 오래된 데이터일수록 기하급수적으로 영향력이 감소하게 되는 결과를 낳는다. 그러한 이유로 Exponentially 라는 뜻이 붙게 되었다
  • Vt=(1−β)∑τ=0t−1βτΘt−τV _{t}=(1-\beta)\displaystyle\sum_{\tau=0}^{t-1}{\beta ^{\tau}\Theta _{t-\tau}}
    - 유도
    - Vt=βVt−1+(1−β)×ΘtV _{t}=\beta V _{t-1}+(1-\beta) \times \Theta _{t}
    - Vt−1=βVt−2+(1−β)×Θt−1V _{t-1}=\beta V _{t-2}+(1-\beta) \times \Theta _{t-1}
    - ...
    - V1=(1−β)Θ1V _{1}=(1-\beta)\Theta _{1}
    - Vt=(1−β)Θt+β[(1−β)Θt−1+β[(1−β)Θt−2+β[...β[V0]]]]V _{t}=(1-\beta)\Theta _{t}+\beta[(1-\beta)\Theta _{t-1}+\beta[(1-\beta)\Theta _{t-2}+\beta[...\beta[V _{0}]]]]
    - Vt=(1−β)∑τ=0t−1βτΘt−τV _{t}=(1-\beta)\displaystyle\sum_{\tau=0}^{t-1}{\beta ^{\tau}\Theta _{t-\tau}}
    - 활용 : 이 VV 값은 근사적으로 11−β\displaystyle\frac{1}{1-\beta} 단계의 데이터만을 활용하여 평균을 취한것과 같다고 알려져있다. 예컨데 β=0.98\beta=0.98 이면 위 식의 값은 50으로, 대략 50일간의 데이터를 갖고 가중평균을 구한것과 유사해지는 것이다.

Momentum

Leaky Average

  • 미니배치 SGD가 연산을 가속시키는 방법으로 제시되었다.
    - gt,t−1=∂w1∣Bt∣∑i∈Btf(xi,wt−1)=1∣Bt∣∑i∈Bthi,t−1\boldsymbol{g}_{t,t-1}=\partial_{\displaystyle{\boldsymbol{w}}}\displaystyle\frac{1}{|\mathcal{B}_{t}|}\displaystyle\sum_{\displaystyle{i \in \mathcal{B}_{t}}}^{}{f(\boldsymbol{x}_{i},\boldsymbol{w}_{t-1})}=\displaystyle\frac{1}{|\mathcal{B}_{t}|}\displaystyle\sum_{\displaystyle{i \in \mathcal{B}_{t}}}^{}{\boldsymbol{h}_{i,t-1}}
    - 표기를 간단하게 하기 위하여 hi,t−1=∂wf(xi,wt−1)\boldsymbol{h} _{i,t-1}=\partial_{\displaystyle{\boldsymbol{w}}}f(\boldsymbol{x}_{i},\boldsymbol{w}_{t-1}) 로 하였다

  • 미니배치에 대한 그레디언트를 평균하는 것의 효과를 넘어 분산을 감소하기 위하여, 다음과 같은 아이디어가 고안되었다
    - vt=βvt−1+gt,t−1\boldsymbol{v}_{t}=\beta \boldsymbol{v}_{t-1}+\boldsymbol{g}_{t,t-1} for some β∈(0,1)\beta \in (0,1)
    - xt←xt−1−ηtvt\boldsymbol{x}_{t}\leftarrow \boldsymbol{x}_{t-1}-\eta _{t}\boldsymbol{v}_{t}
    - v\boldsymbol{v} 는 속도velocity라 불리며, 이는 과거의 그레디언트 값들을 참조한다
    - vt=βvt−1+gt−1,t=β(βvt−2+gt−2,t−1)+gt,t−1=⋯=∑τ=0t−1βτgt−τ,t−τ−1\boldsymbol{v}_{t}=\beta \boldsymbol{v}_{t-1}+\boldsymbol{g}_{t-1,t}=\beta(\beta\boldsymbol{v}_{t-2}+\boldsymbol{g}_{t-2,t-1})+\boldsymbol{g}_{t,t-1} = \cdots=\displaystyle\sum_{\tau=0}^{t-1}{ \beta ^{\tau}\boldsymbol{g}_{t-\tau,t-\tau-1}}
    - β\beta 값이 크게 된다면 장기간의 평균을 구한것과 비슷해지고, β\beta 값이 작게된다면, 현재 그레디언트에 적은 영향력만을 갖게 될 것이다
    - 이 새로운 그레디언트 계산법은 가장 가파른 강하방향을 가르키는 것이 아니라, 과거 그레디언트의 가중 평균을 가르치게 된다. 이는 배치에 대한 평균 그레디언트을 사용할때의 이점을 실제 평균 그레디언트를 계산하는 것보다 적은 연산으로 취할 수 있게 해준다

  • 가속화된 그레디언트 방법accelerated gradient method 혹은 모멘텀을 갖는 그레디언트gradients with momentum이라고 불리게 된다
    - 이 방법은 좋지 않은 조건ill-conditioned의 문제들(예를 들어 비용함수의 모양이 좁은 협곡과 같은 형태로, 특정 방향에서 매우 느리게 진행되는 형태)를 푸는데 좋고, 또 gradient의 업데이트가 좀 더 안정적으로 이루어진다는 장점이 있다

나쁜 조건의 문제 An Ill-conditioned Problem

  • 모멘텀 방법의 기하학적 특성을 잘 이해하기 위하여, 조금 좋지 않은 형태의 목적함수를 제시한다
  • f(x)=0.1x12+2x22f(\boldsymbol{x})=0.1 x _{1} ^{2}+2 x _{2} ^{2} 로 x1x _{1} 에 비해 x2x _{2} 스케일이 훨씬 커, 매우 납작한 형태의 타원이다
  • x2x _{2} 의 스케일이 크기 때문에, 그레디언트가 x2x _{2} 방향으로 훨씬 큰폭으로 진동하는 모습을 보여진다. 그 결과 다음과 같은 불편한 선택지가 남는다
    1. 학습률을 줄여 해가 x2x _{2} 방향으로 발산하는 것을 막고, x1x _{1} 의 극값으로의 느린 수렴을 기다리는 것
    2. 학습률을 높여 x1x _{1} 방향으로 빠르게 진행하는 대신, x2x _{2} 에서 발산하는 것
import torch 
from d2l import torch as d2l 

eta= 0.4 
def f_2d(x1,x2):
    return 0.1 * x1 ** 2 + 2 * x2 ** 2 

def gd_2d(x1,x2,s1,s2):
    return (x1-eta * 0.2 * x1, x2-eta * 4 *x2,0,0)
![](https://d2l.ai/_images/output_momentum_e3683f_3_1.svg)
d2l.show_trace_2d(f_2d,d2l.train_2d(gd_2d))
  • 학습률 η=0.4\eta=0.4
  • 학습률 η=0.6\eta=0.6
eta= 0.6 
d2l.show_trace_2d(f_2d,d2l.train_2d(gd_2d))

Momentum 방법

(I guess)물리적 직관

  • F=mx=mx¨\boldsymbol{F}=m \boldsymbol{x}=m \boldsymbol{{\ddot{x}}}

  • V=mghV=mgh

  • 중력만을 고려한 물체의 운동(마찰 고려 X)
    - T+V=12mx˙2+mgh=E(const)T+V=\displaystyle\frac{1}{2}m \boldsymbol{\dot{x}} ^{2}+mgh=E(const)
    - E=12mx˙2+mgf(x)E=\displaystyle\frac{1}{2}m \boldsymbol{\dot{x}} ^{2}+mgf(\boldsymbol{x})
    - ∂E∂t=mx˙⋅x¨+mg∂f∂x∂x∂t=mx¨⋅x˙+mgx˙⋅∇xf(x)=0\cfrac{\partial {E}}{\partial {t}}=m \boldsymbol{\dot{x}} \cdot \boldsymbol{\ddot{x}}+mg \cfrac{\partial {f}}{\partial {\boldsymbol{x}}}\cfrac{\partial {\boldsymbol{x}}}{\partial {t}}=m \boldsymbol{\ddot{\boldsymbol{x}}}\cdot \boldsymbol{\dot{x}}+mg \boldsymbol{\dot{x}} \cdot \nabla_{\displaystyle{\boldsymbol{x}}}{f(\boldsymbol{x})}=0
    - m(x¨+g∇xf(x))⋅x˙=0m( \boldsymbol{\ddot {x}}+g\nabla_{\displaystyle{\boldsymbol{x}}}{f(\boldsymbol{x})})\cdot \boldsymbol{\dot{x}}=0
    - x¨=−g∇xf(x)\boldsymbol{\ddot{x}}=-g \nabla_{\displaystyle{\boldsymbol{x}}}{f(\boldsymbol{x})}
    - x˙=x˙0−∫0t∇xf(x(t′))dt′\boldsymbol{\dot{x}}=\boldsymbol{\dot{x}}_{0}-\displaystyle\int_{0}^{t}{\nabla_{\displaystyle{\boldsymbol{x}}}{f(\boldsymbol{x}(t'))}}dt'

  • 기존 Momentum 식과의 대조
    - −vt=−(βvt−1+gt−1,t=β(βvt−2+gt−2,t−1)+gt,t−1)=⋯=−∑τ=0t−1βτgt−τ,t−τ−1-\boldsymbol{v}_{t}=-(\beta \boldsymbol{v}_{t-1}+\boldsymbol{g}_{t-1,t}=\beta(\beta\boldsymbol{v}_{t-2}+\boldsymbol{g}_{t-2,t-1})+\boldsymbol{g}_{t,t-1}) = \cdots=-\displaystyle\sum_{\tau=0}^{t-1}{ \beta ^{\tau}\boldsymbol{g}_{t-\tau,t-\tau-1}}
    - gt,t−1=∂w1∣Bt∣∑i∈Btf(xi,wt−1)\boldsymbol{g}_{t,t-1}=\partial_{\displaystyle{\boldsymbol{w}}}\displaystyle\frac{1}{|\mathcal{B}_{t}|}\displaystyle\sum_{\displaystyle{i \in \mathcal{B}_{t}}}^{}{f(\boldsymbol{x}_{i},\boldsymbol{w}_{t-1})}
    - x˙=−∫0t∇xf(x(t′))dt′\boldsymbol{\dot{x}}=-\displaystyle\int_{0}^{t}{\nabla_{\displaystyle{\boldsymbol{x}}}{f(\boldsymbol{x}(t'))}}dt' (초기 속도가 없다고 가정할 경우)
    - Momentum 방법의 식은 [τ−1,τ][\tau-1,\tau] 의 시간 간격단위로 쪼개어, 각 시간 단위에 중력 가속도 g\boldsymbol{g} 를 곱한 것으로 해석할 수 있다. 다만 이 경우 적분의 정의를 고려하면 gt−τ,t−τ+1(t∗)=∫t−τt−τ+1gt−τ,t−τ+1(t′)dt′\boldsymbol{g} _{t-\tau,t-\tau+1}(t ^{*})=\displaystyle\int_{t-\tau}^{t-\tau+1}{\boldsymbol{g}_{t-\tau,t-\tau+1}(t')dt'} 을 만족시키는 t∗∈[t−τ,t−τ+1]t ^{*} \in [t-\tau,t-\tau+1] 를 각 구간마다 설정했어야 할 텐데, 그렇지 않다는 점에서 첫번째로 다른점이고, 물리방정식은 마찰력을 고려하지 않았다는 점이 두번째로 다른점이다. 모멘텀 방법은 시간이 τn\tau ^{n} 만큼 경과했을 때마다 중력의 영향력을 βn\beta ^{n} 만큼 감쇄시킨 것으로 해석하였는데, 이것이 실제 마찰을 고려한 물체의 운동과 어느정도 상관관계가 있는지는 좀 더 공부해봐야 할 것같다

  • (마찰,중력에너지를 고려한 물체의 운동)
    - E=12mx˙2+mgf(x)+∫Q(x˙)dtE= \displaystyle\frac{1}{2}m \boldsymbol{\dot{x}} ^{2}+mgf(\boldsymbol{x})+\displaystyle\int_{}^{}{Q(\boldsymbol{\dot{x}})dt} EE: consant
    - ∂E∂t=mx˙⋅x¨+mg∂f∂x∂x∂t+Q(x˙)\cfrac{\partial {E}}{\partial {t}}=m \boldsymbol{\dot{x}}\cdot \boldsymbol{\ddot{x}}+mg \cfrac{\partial {f}}{\partial {\boldsymbol{x}}}\cfrac{\partial {\boldsymbol{x}}}{\partial {t}}+Q(\boldsymbol{\dot{x}})
    - 이때 Q(x˙)=−γx˙2Q(\boldsymbol{\dot{x}})=-\gamma \boldsymbol{\dot{x}} ^{2} 라고하자
    - mx˙⋅(x¨+g∇f−γx˙)=0m \boldsymbol{\dot{x}}\cdot (\boldsymbol{\ddot{x}}+g \nabla_{\displaystyle{\boldsymbol{}}}{f}-\gamma \boldsymbol{\dot{x}})=0
    - x¨+g∇f(x)−γx˙=0\boldsymbol{\ddot{x}}+g \nabla_{\displaystyle{}}{f(\boldsymbol{x})}-\gamma \boldsymbol{\dot{x}}=0

  • 모멘텀 방법은 위와 같은 문제를 해결하는 좋은 해결책이 된다
  • 최적화 경로를 잘 살펴보다보면 과거에 대한 gradient를 평균하는 것이 잘 작동할 수 있을 것이라는 직감이 생긴다. x1x _{1} 방향으로 이동하는 거리가 쌓여 더 먼 저기를 이동하게 되고, x2x _{2} 는 진동 반대방향의 그레디언트와 더해져 상쇄되게 된다.
  • 식은 다음과 같은 공식이 된다
    - vt←βvt−1+gt,t−1\boldsymbol{v}_{t} \leftarrow \beta \boldsymbol{v}_{t-1}+\boldsymbol{g}_{t,t-1}
    - xt←xt−1−ηtvt\boldsymbol{x}_{t}\leftarrow \boldsymbol{x}_{t-1}-\eta _{t}\boldsymbol{v}_{t}
    - 이때 보면 알수 있듯이, β=0\beta=0 이라면 기존 경사하강법과 동일하게 된다
def momentum_2d(x1,x2,v1,v2):
    v1= beta * v1 + 0.2 * x1 
    v2= beta * v2 + 4 * x2 
    return x1- eta*v1, x2-eta *v2,v1,v2 

eta, beta =0.6,0.5 
d2l.show_trace_2d(f_2d,d2l.train_2d(momentum_2d))

  • 모멘텀 상수momentum term β\beta가 낮아지자 좀 더 빠른 속도로 수렴하는 것을 볼 수 있다
eta, beta= 0.6,0.25
d2l.show_trace_2d(f_2d,d2l.train_2d(momentum_2d))

효울적인 샘플 가중치

  • 기존의 정의된 속도velocity vt=∑τ=0t−1βτgt−τ,t−τ+1\boldsymbol{v}_{t}=\displaystyle\sum_{\tau=0}^{t-1}{\beta ^{\tau}\boldsymbol{g}_{t-\tau,t-\tau+1}} 와 무한등비급수 ∑τ=0∞βτ=11−β\displaystyle\sum_{\tau=0}^{\infty }{\beta ^{\tau}}=\displaystyle\frac{1}{1-\beta} 를 보자.
  • 어떻게 스텝 사이즈 η\eta 와 관성계수 γ\gamma momentum term 을 조절할까? 다음의 예시를 보자
d2l.set_figsize()
betas=[0.95,0.9,0.6,0]
for beta in betas: 
    x= torch.arange(40).detach().numpy()
    d2l.plt.plot(x,beta ** x , label=f'beta={beta:.2f}')
d2l.plt.xlabel('time')
d2l.plt.legend()

Theoretical Analysis

Quadratic Convex Function

  • 다음희 함수를 quadratic function이라고 부른다
    - h(x)=12xTQx+xTc+bh(\boldsymbol{x})=\displaystyle\frac{1}{2}\boldsymbol{x}^{T}\boldsymbol{Q}\boldsymbol{x}+\boldsymbol{x}^{T}\boldsymbol{c}+b
    - 이때 Q\boldsymbol{Q} 가 positive-definite라면, Q\boldsymbol{Q} 의 고유값은 항상 양수일 것이고, 이것의 minimizer는 x∗=−Q−1c\boldsymbol{x}^{*}=-\boldsymbol{Q} ^{-1}\boldsymbol{c} 일 것이다
    - [∂h∂x]i=∂∂xi(12xjQjkxk)+∂∂xi(xjcj)+∂∂xi(b)[\cfrac{\partial {h}}{\partial {\boldsymbol{x}}}]_{i}=\cfrac{\partial {}}{\partial {x}_{i}}(\displaystyle\frac{1}{2}x _{j}Q _{jk}x _{k})+\cfrac{\partial {}}{\partial {x _{i}}}(x _{j}c _{j})+\cfrac{\partial {}}{\partial {x _{i}}}(b)
    - [∂h∂xi]=12(Qikxk+xjQji)+ci[\cfrac{\partial {h}}{\partial {x _{i}}}]=\displaystyle\frac{1}{2}(Q _{ik}x _{k}+x _{j}Q _{ji})+c _{i}
    - [∂h∂xi]=12([Qx]i+[Qx]i)+ci[\cfrac{\partial {h}}{\partial {x _{i}}}]=\displaystyle\frac{1}{2}([\boldsymbol{Q}\boldsymbol{x}]_{i}+[\boldsymbol{Q}\boldsymbol{x}]_{i})+c _{i}
    - ∂h∂x=Qx+c=0\cfrac{\partial {h}}{\partial {\boldsymbol{x}}}=\boldsymbol{Q}\boldsymbol{x}+\boldsymbol{c}=0 , x=−Q−1c\boldsymbol{x}=-\boldsymbol{Q} ^{-1}\boldsymbol{c}
    - 이때 최솟값은
    - h(x∗)=12(−Q−1c)TQ(−Q1c)+(−Q−1c)Tc+bh(\boldsymbol{x}^{*})=\displaystyle\frac{1}{2}(-\boldsymbol{Q} ^{-1}\boldsymbol{c})^{T}\boldsymbol{Q}(-\boldsymbol{Q} ^{1}\boldsymbol{c})+(-\boldsymbol{Q} ^{-1}\boldsymbol{c})^{T}\boldsymbol{c}+b
    - h(x∗)=12(cTQ−1Q(Q−1c)−cT(Q)−1c+bh(\boldsymbol{x}^{*})=\displaystyle\frac{1}{2}(\boldsymbol{c}^{T}\boldsymbol{Q} ^{-1}\boldsymbol{Q} (\boldsymbol{Q} ^{-1}\boldsymbol{c})-\boldsymbol{c}^{T} (\boldsymbol{Q}) ^{-1}\boldsymbol{c}+b
    - h(x∗)=12cTQ−1c−cTQ−1c+b=−12cTQ−1c+bh(\boldsymbol{x}^{*})=\displaystyle\frac{1}{2}\boldsymbol{c}^{T}\boldsymbol{Q} ^{-1}\boldsymbol{c}-\boldsymbol{c}^{T}\boldsymbol{Q} ^{-1}\boldsymbol{c}+b=-\displaystyle\frac{1}{2}\boldsymbol{c}^{T}\boldsymbol{Q} ^{-1}\boldsymbol{c}+b
    - 12(x−Q−1c)TQ(x−Q−1c)+b−12cTQ−1c\displaystyle\frac{1}{2}(\boldsymbol{x}-\boldsymbol{Q} ^{-1}\boldsymbol{c})^{T}\boldsymbol{Q}(\boldsymbol{x}-\boldsymbol{Q} ^{-1}\boldsymbol{c})+b-\displaystyle\frac{1}{2}\boldsymbol{c}^{T}\boldsymbol{Q} ^{-1}\boldsymbol{c}
    - =12(xT−cTQ−1)(Qx−c)+b−12cTQ−1c=\displaystyle\frac{1}{2}(\boldsymbol{x}^{T}-\boldsymbol{c}^{T}\boldsymbol{Q} ^{-1})(\boldsymbol{Q}\boldsymbol{x}-\boldsymbol{c})+b-\displaystyle\frac{1}{2}\boldsymbol{c}^{T}\boldsymbol{Q} ^{-1}\boldsymbol{c}
    - =12()=\displaystyle\frac{1}{2}()

  • =12(xTQx+cTQ−1c−xTc−cTx)=\displaystyle\frac{1}{2}(\boldsymbol{x}^{T}\boldsymbol{Q}\boldsymbol{x}+\boldsymbol{c}^{T}\boldsymbol{Q} ^{-1}\boldsymbol{c}-\boldsymbol{x}^{T}\boldsymbol{c}-\boldsymbol{c}^{T}\boldsymbol{x})

  • Ref & I guess) 대칭행렬의 역행렬은 대칭행렬인가?
    - 증명
    - QQ−1=I\boldsymbol{Q}\boldsymbol{Q} ^{-1}=\boldsymbol{I}
    - [Q]ij=[Q]ji[\boldsymbol{Q}]_{ij}=[\boldsymbol{Q}]_{ji}
    - [QQ−1]ik=δik=[Q]ij[Q−1]jk=[Q]ji[Q−1]jk=[Q−1Q]ik=[Q]ji[Q−1]kj[\boldsymbol{Q}\boldsymbol{Q} ^{-1}]_{ik}=\delta _{ik}=[\boldsymbol{Q}]_{ij}[\boldsymbol{Q} ^{-1}]_{jk}=\boldsymbol{[\boldsymbol{Q}]}_{ji}[\boldsymbol{Q} ^{-1}]_{jk}=[\boldsymbol{Q} ^{-1}\boldsymbol{Q}]_{ik}=[\boldsymbol{Q}]_{ji}[\boldsymbol{Q} ^{-1}]_{kj}

Adagrad

  • 언어모델을 학습시킨다고 하자. 좋은 정확도를 얻기 위해선 학습률을 O(t−1/2)\mathcal{O}(t ^{-1/2}) 보다 낮게 하는 것이 좋다. 비주기적으로 희박하게 등장하는 피쳐들이 있는 모델을 생각하자. 이는 자연어 모델, 개인화된 협업 필터링과 같은 추천시스템에서 종종 등장하는 일이다
  • 빈도가 적은 피쳐와 연관된 파라미터들은 해당 피쳐가 등장할때만이 유의미한 업데이트가 가능하다. 이런 상황에서는 보편적으로 등장하는 피쳐의 수렴으로 인해 학습이 조기 종료될 가능성이 높다. 빈번하게 등장하는 피처에겐 학습률이 지나치게 느리게 감소하고, 드물게 등장하는 피쳐에게는 너무나 빠르게 감소하는 일이 된 것이다
  • 이런 문제를 해결하기 위해선 피처들이 얼마나 등장하는지 셀 필요가 있다. 또 학습률을 보편적으로 부과하는게 아닌 각 피처별로 다르게 두어야 한다
    - 즉 η=η0t+c\eta=\displaystyle\frac{\eta _{0}}{\sqrt{t+c}} 꼴에서 ηi=η0s(i,t)+c\eta _{i}=\displaystyle\frac{\eta _{0}}{\sqrt{s(i,t)+c}} 가 되어야 하는것이다.
    - 이때 s(i,t)s(i,t) 는 피쳐 ii 의 시간 tt 에서의 카운트 횟수이다
    - 그러나 학습은 실패하는 경우가 종종 있는데, 이는 데이터가 희소해서가 아닌, 데이터의 그레디언트값이 매우 크거나 작을때 발생한다
  • Adagrad는 s(i,t)s(i,t) 로 단순하게 카운트하기 보단 이전 관측치의 그레디언트 제곱값을 합하여 계산한다
    - s(i,t+1)=s(i,t)+(∂xf(x))2s(i,t+1)=s(i,t)+(\partial_{\displaystyle{\boldsymbol{x}}}f(\boldsymbol{x})) ^{2} 인 것이다
    - 이는 gradient의 크기를 자동적으로 조절해준다는 이점을 갖고 있다
    - 그레디언트 값이 크게나오는 좌표값들은 스케일링 다운해지는 반면, 작은 그레디언트값을 갖는 좌표들은 더 큰 값을 갖도록 조정되는 것이다. 이는 실제로 추천시스템과 비슷한 문제들에서 상당히 유효하게 기능한다

AdaGrad 알고리즘

  • st=st−1+gt2{s}_{t}={s}_{t-1}+\boldsymbol{g}_{t} ^{2}

  • xt=xt−1−ηst+ϵgt\boldsymbol{x}_{t}=\boldsymbol{x}_{t-1}- \displaystyle\frac{\eta}{\sqrt{s _{t}+\epsilon}} \boldsymbol{g}_{t}
    - AdaGrad는 각각의 매개변수에 적응적으로 학습률을 조정하며 학습을 진행한다
    - AdaGrad의 sts _{t} 기울기를 제곱하여 계속 더해가기 때문에 학습이 진행될수록 ηst+ϵ\displaystyle\frac{\eta}{\sqrt{s _{t}+\epsilon}} 는 점점 더 작아질 수 밖에 없다. 어느 순간에 도달하면 학습이 진행되지 않는다는 문제가 발생하여, 다른 알고리즘이 개발되었다

  • f(x)=0.1x12+2x22f(x)=0.1x _{1} ^{2}+2 x _{2} ^{2}

import math
import torch 
from d2l import torch as d2l 

def adagrad_2d(x1,x2,s1,s2):
    eps  =1e-6 
    g1,g2 = 0.2 * x1 , 4 * x2 
    s1 += g1 **2 
    s2 += g2 **2 
    x1 -= eta /math.sqrt(s1+eps) * g1 
    x2 -= eta /math.sqrt(s2+eps) * g2 
    return x1,x2,s1,s2 

def f_2d(x1,x2):
    return 0.1 * x1 ** 2 + 2 * x2 **2 

eta= 0.4
d2l.show_trace_2d(f_2d,d2l.train_2d(adagrad_2d))


"""result)
epoch 20, x1: -2.382563, x2: -0.158591
"""

  • 학습률을 2로 늘린다면 좀 더 좋은 행동을 보인다
eta =2 
d2l.show_trace_2d(f_2d,d2l.train_2d(adagrad_2d))

"""result)
epoch 20, x1: -0.002295, x2: -0.000000
"""

Adagrad 코드 구현

import math
import torch
from d2l import torch as d2l

def init_adagrad_sates(feature_dim):
    s_w =torch.zeros((feature_dim,1))
    s_b = torch.zeros(1)
    return ((s_w,s_b))

def adagrad(params,states,hyperparameters):
    eps= 1e-6
    for p ,s in zip(params,states):
        with torch.no_grad():
            s[:] += torch.square(p.grad)
            p[:] -= hyperparameters['lr'] * p.grad /torch.sqrt(s+eps)
        p.grad.data.zero_()

data_iter ,feature_dim = d2l.get_data_ch11(batch_size=10)
d2l.train_ch11(adagrad,init_adagrad_sates(feature_dim),
               {'lr':0.1}, data_iter, feature_dim)
  • pytorch.optim.Adagrad 코드 사용
trainer = torch.optim.Adagrad
d2l.train_concise_ch11(trainer,{'lr':0.1},data_iter)

"""result)
loss: 0.243, 0.050 sec/epoch
"""

RMSProp

  • 학습률이 O(t−1/2)\mathcal{O}(t ^{-1/2}) 꼴로 점점 감소한다는 문제는 Adagrad의 핵심 문제이다
  • convex 문제에 관해선 일반적으로 괜찮은 학습방법일지 몰라도, nonvex한 문제들에 관해선 적합하지 않다. 그럼에도 Adagrad의 성분간 다르게 학습률을 적용시키는 방식은 매우 좋은 아이디어였으므로, 이 장점을 살린 다른 최적화 알고리즘을 만들고자 하였다
  • Tieleman과 Hinton은 RMSProp 알고리즘을 이 학습률 감소 문제와 coordinate-adaptive learning rates의 문제를 분리하여 보기 시작하였다
    - 학습률 감소 문제는 Adagrad가 상태벡터 st\boldsymbol{s}_{t}가 그레디언트 제곱을 계속 더하면서 발생한 문제였다. 따라서st\boldsymbol{s}_{t} 가 정규화의 부족으로 선형적으로 계속 성장한다는 문제가 있다
    - 이러한 문제를 해결하기 위하여 st/ts _{t}/t 를 사용한다.
    - reasonable한 분포들의 그레디언트들은 수렴할 것이다
    - 문제는 이 알고리즘이 사용된다면, 기존 모든 값들을 저장하면서 진행되기 때문에 학습에 있어 매우 긴 시간이 걸릴 것이라는 점이다
    - 이러한 대안으로서 모멘텀 방법을 활용한다
    - st←γst−1+(1−γ)gt2\boldsymbol{s}_{t} \leftarrow \gamma \boldsymbol{s}_{t-1}+(1-\gamma)\boldsymbol{g}_{t} ^{2}
    - xt←xt−1−ηst+ϵ⊙gt\boldsymbol{x}_{t} \leftarrow \boldsymbol{x}_{t-1}-\displaystyle\frac{\eta}{\sqrt{\boldsymbol{s}_{t}+\epsilon}}\odot \boldsymbol{g}_{t}
    - 상수 ϵ>0\epsilon>0 는 기본적으로 10−610 ^{-6} 보다 작게 사용하여, divison-zero 문제를 피하기 위해 사용된다
    - st=(1−γ)gt2+γst−1=⋯=(1−γ)∑n=0t−1γngt−n2\boldsymbol{s}_{t}=(1-\gamma)\boldsymbol{g}_{t} ^{2}+\gamma \boldsymbol{s}_{t-1}= \cdots=(1-\gamma)\displaystyle\sum_{n=0}^{t-1 }{\gamma ^{n} \boldsymbol{g} _{t-n} ^{2}}
import math
import torch
from d2l import torch as d2l

d2l.set_figsize()
gammas= [0.95,0.9,0.8,0.7]
for gamma in gammas :
    x= torch.arange(40).detach().numpy()
    d2l.plt.plot(x,(1-gamma)*gamma ** x ,label=f'gamma]{gamma:.2f}')
d2l.plt.xlabel(('time'));

RMSProp 코드 구현

def rmsprop_2d(x1,x2,s1,s2):
    g1,g2, eps = 0.2 *x1, 4*x2, 1e-6
    s1= gamma * s1 + (1-gamma) * g1 ** 2
    s2= gamma * s2 + (1-gamma) * g2 ** 2
    x1 -= eta/ math.sqrt(s1+eps) * g1
    x2 -= eta/ math.sqrt(s2+eps) * g2
    return x1,x2,s1,s2

def f_2d(x1,x2):
    return 0.1 * x1 ** 2 + 2 * x2 **2

eta, gamma =0.4, 0.9
d2l.show_trace_2d(f_2d, d2l.train_2d(rmsprop_2d))
  • 이제 RMSProp을 딥러닝 네트워크에서 활용해보자
def init_rmsprop_states(feature_dim):
    s_w = torch.zeros((feature_dim,1))
    s_b = torch.zeros(1)
    return (s_w,s_b)

def rmsprop(params, states, hyperparams):
    gamma, eps =hyperparams['gamma'], 1e-6
    for p,s in zip(params,states):
        with torch.no_grad():
            s[:] = gamma * s +(1-gamma) * torch.square(p.grad)
            p[:] -= hyperparams['lr'] * p.grad /torch.sqrt(s+eps)
            p.grad.data.zero_()

"""학습률 eta=0.01, 가중치 텀 gamma=0.9로 두자"""
data_iter,feature_dim =d2l.get_data_ch11(batch_size=10)
d2l.train_ch11(rmsprop, init_rmsprop_states(feature_dim),
               {'lr':0.01, 'gamma':0.9},data_iter,feature_dim)

Adam

ref.지수가중평균 Exponentially Weighted Average 계산식

ref.(Vt=βVt−1+(1−β)×ΘtV _{t}=\beta V _{t-1}+(1-\beta) \times \Theta _{t} 이면 Vt=(1−β)∑τ=0t−1βτΘt−τV _{t}=(1-\beta)\displaystyle\sum_{\tau=0}^{t-1}{\beta ^{\tau}\Theta _{t-\tau}})

  • 알고리즘 형태
    - 아담은 2개의 상태변수를 활용한다.
    - vt←β1vt−1+(1−β1)gt\boldsymbol{v}_{t} \leftarrow \beta _{1}\boldsymbol{v}_{t-1}+(1-\beta _{1})\boldsymbol{g}_{t}
    - st←β2st−1+(1−β2)gt2\boldsymbol{s}_{t} \leftarrow \beta _{2}\boldsymbol{s}_{t-1}+(1-\beta _{2})\boldsymbol{g}_{t} ^{2}
    - xt=xt−1−g′t\boldsymbol{x}_{t}=\boldsymbol{x}_{t-1}-\boldsymbol{g'}_{t}
    - ∑i=0t−1βi=1−βt1−β\displaystyle\sum_{i=0}^{t-1}{\beta ^{i}}=\displaystyle\frac{1-\beta ^{t}}{1-\beta} 라는 사실을 활용하여 각 텀을 re-normalizating 하자
    - v^t=vt1−β1t\hat{\boldsymbol{v}}_{t}=\displaystyle\frac{\boldsymbol{v}_{t}}{1-\beta _{1} ^{t}} 그리고, s^t=st1−β2t\hat{\boldsymbol{s}}_{t}=\displaystyle\frac{\boldsymbol{s}_{t}}{1-\beta _{2} ^{t}}
    - g′t=ηv^ts^t+ϵ\boldsymbol{g'}_{t}=\displaystyle\frac{\eta \hat{\boldsymbol{v}}_{t}}{\sqrt{\hat{\boldsymbol{s}}_{t}}+\epsilon} 의 형태로, RMSProp과 매우 유사하게 정의내린다
    - 그 결과 Adam 알고리즘은 그레디언트에 대한 지수평균을 한 상태변수 vt\boldsymbol{v}_{t} 가 스텝 방향 을 조정하는 역할을(크기도 바꾸기도 함)(Momentum의 기능), 그레디언트 제곱의 지수평균을 한 상태변수 st\boldsymbol{s}_{t} 가 스텝 크기를 점차 줄여나가는 역할을(RMSProp의 기능) 한다
%matplotlib inline
import torch
from d2l import torch as d2l


def init_adam_states(feature_dim):
    v_w, v_b = torch.zeros((feature_dim, 1)), torch.zeros(1)
    s_w, s_b = torch.zeros((feature_dim, 1)), torch.zeros(1)
    return ((v_w, s_w), (v_b, s_b))

def adam(params, states, hyperparams):
    beta1, beta2, eps = 0.9, 0.999, 1e-6
    for p, (v, s) in zip(params, states):
        with torch.no_grad():
            v[:] = beta1 * v + (1 - beta1) * p.grad
            s[:] = beta2 * s + (1 - beta2) * torch.square(p.grad)
            v_bias_corr = v / (1 - beta1 ** hyperparams['t'])
            s_bias_corr = s / (1 - beta2 ** hyperparams['t'])
            p[:] -= hyperparams['lr'] * v_bias_corr / (torch.sqrt(s_bias_corr)
                                                       + eps)
        p.grad.data.zero_()
    hyperparams['t'] += 1

data_iter, feature_dim = d2l.get_data_ch11(batch_size=10)
d2l.train_ch11(adam, init_adam_states(feature_dim),
               {'lr': 0.01, 't': 1}, data_iter, feature_dim);

""" result)
loss: 0.243, 0.109 sec/epoch
"""

trainer = torch.optim.Adam
d2l.train_concise_ch11(trainer,{'lr':0.01},data_iter)
"""result)
loss: 0.243, 0.052 sec/epoch"""

Yogi 알고리즘

  • Adam이 second moment 추정인 st\boldsymbol{s}_{t} 가 갑자기 폭등하여 수렴이 실패하는 문제가 종종 발생하였다
  • 이에 따라서 st\boldsymbol{s}_{t} 를 다르게 정의한 알고리즘을 고안하였는데, 이를 Yogi라고 명명 되었다
  • st←st−1+(1−β2)(gt2−st−1)\boldsymbol{s}_{t} \leftarrow \boldsymbol{s}_{t-1}+(1-\beta _{2})(\boldsymbol{g}_{t} ^{2}-\boldsymbol{s}_{t-1})
    - 만약 gt2\boldsymbol{g}_{t} ^{2} 가 높은 분산값을 갖거나 업데이트 횟수가 희박하다면, st\boldsymbol{s}_{t} 는 과거의 값을 지나치게 빠르게 망각해버릴 수 있다.
    - 이러한 문제를 해결하기 위해 gt2−st−1\boldsymbol{g}_{t} ^{2}-\boldsymbol{s}_{t-1} 대신 gt2⊙sgn(gt2−st−1)\boldsymbol{g}_{t} ^{2} \odot sgn(\boldsymbol{g}_{t} ^{2}-\boldsymbol{s}_{t-1}) 로 다시 대체되었다
    - 이제 업데이트의 크기는 더이상 편차의 값에만 의존하지 않는다
  • st←st−1+(1−β2)gt2⊙sgn(gt2−st−1)\boldsymbol{s}_{t} \leftarrow \boldsymbol{s}_{t-1}+(1-\beta _{2})\boldsymbol{g}_{t} ^{2} \odot sgn(\boldsymbol{g}_{t} ^{2}-\boldsymbol{s}_{t-1}) 이다
def yogi(params, states, hyperparams):
    beta1, beta2 , eps = 0.9 , 0.999, 1e-3
    for p, (v,s) in zip(params, states):
        with torch.no_grad():
            v[:] = beta1 * v + (1-beta1) * p.grad
            s[:] = s + (1-beta2) * torch.sign(
                torch.square(p.grad)-s) * torch.square(p.grad)
            v_bias_corr = v/ (1-beta1 ** hyperparams['t'])
            s_bias_corr = s/ (1-beta2 ** hyperparams['t'])
            p[:] -= hyperparams['lr'] * v_bias_corr / (torch.sqrt(s_bias_corr)+eps)
        p.grad.data.zero_()
        hyperparams['t'] +=1

data_iter,feature_dim =d2l.get_data_ch11(batch_size=10)
d2l.train_ch11(yogi, init_adam_states(feature_dim),
               {'lr':0.01, 't':1},data_iter,feature_dim)

profile
milkbuttercheese
안녕하세요!
이전 포스트

딥러닝 이론: 5-1. 최적화

0개의 댓글