[LG Aimers] Module 5.3(Supervised Learning 분류, 회귀) : Gradient Descent

 

 

1. Gradient Descent

 

 

 

 

• $\alpha$ : step size
  • $\alpha$가 작다면 : 수렴속도가 느리지만 수렴하는 형태가 안정적
  • $\alpha$가 크다면 : error surface에서 global minimum을 찾기가 힘들고, 발산하는 형태로 학습이 진행됨

 

 

위에서부터 alpha의 값이 중간, 작을 때, 클 때의 경우

 

 

• $L$이라는 function을 얼마만큼의 data로 정의하느냐에 따라 구분됨
  • Batch gradient descent (entire n)
  • Mini-batch gradient descent (k < n data)
  • Stochastic gradient descent (k < n data with unbiased gradient estimation)

 

2. Batch / Mini-Batch / Stochastic Gradient Descent: $\theta \: \leftarrow \: \theta - \alpha g$

 

 

• Loss function :  Data point에 대한 loss의 summation으로 표시
• 현재 parameter를 gradient와 반대 방향으로 업데이트
• $\Theta _{k+1} = \Theta _{k} - \gamma _{k} \nabla L(\Theta _{k})^{T} = \Theta_{k}- \gamma_{k}\sum_{n=1}^{N}\nabla L_{n}(\Theta_{k})^{T}$ 

 

parameter가 update되면서 model이 data에 fitting 되어가는 과정

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

• 매 update 순간마다 $\sum_{n=1}^{N}\nabla L_{n}(\Theta_{k})^{T}$ 를 계산하는 것이 매우 계산량이 많음

 

 

• Batch Gradient : Gradient를 모든 data point를 다 고려해서 계산하는 update
  • original full batch gradient의 noisy apporximation : mini-batch GD, SGD
  • Data가 매우 많은 상황 = 전체 gradient를 구하기 힘든 상황
  • Local Minimum , Saddle point에 취약

 

 

• Mini-batch gradient : data point가 n개 있으면 그 중 특정 subset을 구해서 그 subset에 있는 gradient만 계산해서 update 

 

 

• Stochastic Gradient Descent : subset을 구할 때 이 subset을 구한 gradient의 expectation의 original full batch gradient와 동일하도록 (original batch gradient를 잘 근사할 수 있게 다음과 같은 방식으로 디자인하기)
  • $\sum_{n=1}^{N}\nabla L_{n}(\Theta_{k})^{T} = E\left [ \sum_{n \in K}\nabla L_{n}(\Theta_{k})^{T} \right ] $
  • Batch - GD에 비해 빠르게 iteration을 돌 수 있으나, 각 sample 하나마다 parameter를 연산하기 때문에 noise의 영향을 많이 받음 -> Osciliation이 많이 발생

 

 

 

 

3. Solution : Momentum을 이용

 

 

• $Actual \: Step = Momentum \: Step + Gradient \: Step $
• 과거에 gradient가 업데이트 되어오던 방향 및 속도를 어느정도 반영해서 현재 포인트에서 Gradient가 0이 되더라도 계속해서 학습을 진행할 수 있는 동력을 제공하는 것

 

• Recursive Equation : $\nu_{t} = \rho^{k}\nu_{t-k} + (1-\rho)\left [ g_{t} + \rho g_{t-1} + ... + \rho^{k-1}g_{t-k+1} \right ]$
  • 현재 Momentum = 과거 Momentum * $\rho^{k}$ + 과거 Gradient를 누적해서 계산 (현재시점에서 멀수록 $\rho$가 연속적으로 곱해짐)
  • Update : 현재 Momentum = 직전 Momentum * $\rho$ + $(1-\rho)$ * 현재 Gradient
  • $\rho$ 가 1보다 작기 때문에 연속적으로 곱해질수록 더욱 작아짐
  • Saddle point나 작은 noise gradient값에 더 안정적으로 수렴하게끔 함

 

Momentum V_t

 

• SGD + Momentum : 
  • $\nu \: \leftarrow \: \rho\nu - \alpha g$
  • $\theta \: \leftarrow \: \theta + \nu$

 

• Update되는 Learnable Parameter에 Momentum을 곱하여 반영
• Local Minimum이나 Saddle Point 에서 Gradient가 0이 되는 지점이 발생하더라도, 과거에 이어오던 Momentum을 반영하여 계속해서 학습을 진행할 수 있도록 해줌

 

 

 

 

 

• Nesterov Momentum : 
  • $ \nu \: \leftarrow \: \rho\nu - \alpha \nabla_{\theta}J(\theta + \rho \nu) $
  • $\theta \: \leftarrow \: \theta + \nu$

 

 

 

•  $Actual \: Step = Momentum \: Step + Lookahead \: Gradient \: Step$
• Gradient를 먼저 평가하고 업데이트를 해주게 됨 : lookahead gradient step을 이용
•  Gradient : $\nabla_{\theta}J(\theta)$
• Lookahead Gradient : $\nabla_{\theta}J(\theta + \rho \nu)$

 

 

• AdaGrad  : accumulated gradient를 이용하여 learning rate를 조절
  • 각 방향으로의 learning rate를 적응적으로 조절하여 학습효율을 높이는 방법
  • $r \leftarrow \: r + g \cdot g$
  • $\Delta \theta \leftarrow \: \frac {\alpha} {\sqrt{r + \varepsilon}} \cdot g$
  • $\theta \leftarrow \: \theta - \Delta \theta$

 

 

• gradient $g$가 누적이 되면서 $r$이 점점 커짐 -> $\Delta \theta$가 줄어들음
• gradient $g$가 크다 : 해당 방향으로의 학습이 많이 진행됨 -> 수렴속도가 점점 줄음

 

• 단점 : gradient 값이 누적되면서 learning rate 값이 굉장히 작아짐 -> 학습이 일어나지 않게된다

 

 

 

• RMSProp
  • $r \leftarrow \: \rho r + (1-\rho) g \cdot g$
  • $\Delta \theta \leftarrow \: \frac {\alpha} {\sqrt{r + \varepsilon}} \cdot g$
  • $\theta \leftarrow \: \theta - \Delta \theta$

 

• $r, g \cdot g$에 각각 $\rho, 1-\rho$를 곱하기 때문에 반영비가 들어감
• r의 값을 어느정도 조질하게 됨 : gradient가 극단적으로 누적되면서 learning rate가 줄어드는 것이 아니라, 어느정도 완충된 상태로 learning rate가 줄어듬

 

 

 

 

 

• Adam : RMSProp + Momentum
  • First Moment from Momentum : $s \leftarrow \: \rho_{1} s + (1-\rho_{1}) g \cdot g$
  • Second Moment from RMSProp : $r \leftarrow \: \rho_{2} r + (1-\rho_{2}) g \cdot g$
  • Correct the bias : $s^{'} \leftarrow \: \frac {s} {1-\rho_{1}} $, $r^{'} \leftarrow \: \frac {r} {1-\rho_{2}} $
  • $\Delta \theta \leftarrow \: \frac {\alpha} {\sqrt{r^{'} + \varepsilon}} \cdot s^{'}$
  • $\theta \leftarrow \: \theta - \Delta \theta$

 

 

 

 

 

 

 

• Learning rate scheduling
  • hyperparameter $\alpha$를 학습과정에 따라 조정

 

 

 

 

• Overfitting : Model 과적합 문제
  • Model이 지나치게 복잡하여, 학습 Parameter의 숫자가 많아서 제한된 학습 샘플에 너무 과하게 학습이 되는 것

 

 

 

 

 

• Solution
  • Feature의 개수 줄이기 
  • Regularization 
    • 학습과정에서 모델의 복잡도에 대한 페널티를 줘서 모델이 overfitting되지 않도록함
    • 모델은 가급적 적은 수의 parameter를 사용하면서 주어진 문제 sample들을 fitting할 것