[Gradient Descent] part 3 - 1

🎯 Keyword 🎯

- Gradient Descent
- Batch Gradient Descent
- Stochastic Gradient Descent

Gradient Descent

 

이전에 설명한 Gradient Descent Algorithm은 "Batch Gradient Descent Algorithm"입니다.

 

Batch Gradient Descent Algorithm

- Linear regression model에서 목적 함수 J의 partial derivative term을 넣어서 θ0, θ1을 바꾸고 있는 것을 볼 수 있습니다.

- 비록 local optimum이 취약하지만, 어느 정도 수렴이 되어 가는 장면을 볼 수 있습니다.

- 단점 : θ0, θ1을 update하는 과정에서 sample의 개수를 모두 고려해야한다는 것입니다.
            우리가 전체 sample의 error를 계산하게 되고, 모든 sample에 대해서 전부다 acumulation을 해야 θ들을 한 번 update할 수 있

            습니다.

            즉, data sample의 개수가 증가하면 증가할 수록, 복잡도가 굉장히 커지게 됩니다.

 

 

이러한 문제를 해결하기 위해, sample의 개수 m을 1로 극단적으로 줄여서 만든 algorithm을 

Stochastic Gradient Descent (SGD)

라고 합니다.

 

- 장점 : batch gradient descent에 비해 빠르게 돌 수 있다.

- 단점 : sample 하나하나 마다 계산을 통해서 parameter를 연산하기 때문에 noise의 영향을 받기 쉽게 됩니다.
            수렴하는 과정에서 많은 oscillation이 발생하는 것을 알 수 있습니다.

 

• Gradient Descent가 시작하는 point에 따라서 local optimum을 달성하느냐, global optimum을 달성하느냐가 갈립니다.
• Saddle point와 같이 어느 한 방향으로 수렴하게 될 때, gradient 값이 0이 되어서 local optimum에 빠지게 되는 지점들이 다수 존재하는 것으로 알려져 있습니다.

 

이러한 suboptimum한 problem들을 해결 하기 위해선 어떻게 해야할까요?

 

=> 기존의 gradient descent algorithm에서 다양한 변형 algorithm들이 개발되었습니다.

 

• Momentum

과거의 Gradient가 업데이트 되어오던 방향 및 속도를 어느 정도 반영해서 현재 포인트에서 Gradient가 0이 되더라도 계속해서 학습을 진행할 수 있는 동력을 제공하는 것입니다.

 

• Method of momentum
  • Exponentially weighted moving average

 

-> low pass filtering의 연산

-> 현재 포인트에서의 saddle point나 작은 noise gradient 값에 변화가 안정적으로 수렴할 수 있게 합니다.

 

💡 설령 gradient 값이 0이 되더라도 학습을 이어서 진행할 수 있게 됩니다. 

 

 

 

-> 더 Advanced된 방식인 nesterov momentum 방식이 존재합니다.

 

• nesterov momentum
  • 기존의 방식과 달리 gradient를 먼저 평가하고 업데이트를 해주게 됩니다.
  • 그래서, 이 방식을 "look ahead gradient step"을 이용한다고 이야기 합니다.

 

 

Momemtum vs. Nesterov momentum

 

Momentum 방식은 momentum step과 gradient step을 합쳐서 actual step을 계산합니다.

Nesterov momentum 방식은 mementum step을 계산한 상태에서 "lookahead" gradient step을 계산하여 벡터 합을 계산하여 actual step을 계산합니다. 

 

 

 

• AdaGrad

각 방향으로의 learning rate를 적응적으로 조절하여 학습 효율을 높이는 방법입니다.

즉, Acumulate gradient 값을 통해 learning rate를 조절하게 됩니다.

어느 한 쪽으로 gradient 값이 크다면 이미 그 방향으로 학습이 많이 진행되었음을 의미합니다.

 

그렇다면 gradient 값이 많이 누적되어 ∆θ값이 작아져서 그만큼 수렴 속도를 줄이게 되는 것입니다.

 

단점 : gradient 값이 계속해서 누적 됨에 따라, learning rate 값이 굉장히 작아지게 된다는 것입니다.

AdaGrad

Learning rate 값이 작아진다면 ?

-> Learning rate 값이 작아지게 되면 학습이 그 지점에서 일어나지 않게 될 것입니다.

 

=> 이러한 방식을 수정한 것이 RMSProp algorithm입니다.

 

• RMSProp algorithm

r의 값을 우리가 과거에 r 만큼의  ρ(로우) factor를 곱해서 어느 정도 조절을 하게 됩니다.

과거와 같이 극단적으로 gradient 값이 누적됨에 따라서 θ값이 줄어드는 것이 아니라 어느 정도 완충된 형태로 학습 속도가 줄어듭니다.

RMSProp

 

• Adam

Adaptive moment estimation

RMSProp + Momentum 방식을 혼합한 것.

1. 첫 번째 momentum을 계산합니다.
2. RMSProp 방식으로 두 번째 momentum을 계산합니다.
3. bias를 correction합니다.
4. parameter를 업데이트 합니다.

1 ~ 4 번