[ML] Gradient Descent Method: 경사하강법

Gradient Descent Method (경사하강법) : 

https://www.linkedin.com/pulse/understanding-gradient-descent-algorithm-its-role-linear-mhango-kjbvf/

1. 정의 및 수식

Steepest Gradient Descent Method로도 불리는

Gradient Descent Method(경사하강법)는 여러 Optimization 방법  중 가장 많이 사용되는 방법들  중 하나임.

• training set $X$와 현재 $t$에서의 모델의 parameters $\boldsymbol{\omega}_t$의
• Loss function $L(\boldsymbol{\omega}_t, X)$에서
• 모델의 parameters $\boldsymbol{\omega}_t$에 대한 Gradient vector $\nabla_{\boldsymbol{\omega}} L(\boldsymbol{\omega}_t,X)$를 구하고,
• 이 Gradient vector의 반대방향 (negative, $-$)으로 (=The direction of descending gradient!)
• learning rate $\eta$와 해당 gradien vector의 norm에 의해 결정되는 정도만큼
• 모델의 parameter를 수정(update)하는 과정을 반복하여

현재의 training set에서 loss function을 최소화 하는 모델의 parameters를 구함.

---

이를 수식으로 표현하면 다음과 같음.

$$\boldsymbol{\omega_{t+1}} = \boldsymbol{\omega_{t}} - \eta \nabla_{\boldsymbol{\omega}} L(\boldsymbol{\omega}_{t},X)$$

• $\boldsymbol{\omega}_{t}$ : iteration (or time) $t$에서의 model parameter vector
• $\eta$ : learning rate
• $X$ : training set 
• $L(\boldsymbol{\omega}_{t},X)$ : loss function (=cost function, object function)
• $\nabla_{\omega} L(\boldsymbol{\omega}_{t},X)$ : gradient vector ($=\dfrac{\partial L(\boldsymbol{\omega}_{t},X)}{\partial \boldsymbol{\omega}}$). 정확히는 loss function의 local graident.

 

Gradient vector의 반대방향($-\nabla_{\boldsymbol{\omega}}L(\boldsymbol{\omega}_t,X)$)은

현재 parameters의 모델에서 loss function를 가장 급격하게 감소시키는 parameters의 변화 방향을

나타내기 때문에

loss function에 convex인 경우 항상 최적의 해(global solution)에 해당하는 모델의 parameters를 구함.

2023.06.24 - [.../Math] - [Math] Gradient (구배, 기울기, 경사, 경도) Vector

[Math] Gradient (구배, 기울기, 경사, 경도) Vector

 

단, loss function이 "convex가 아닐 경우"

• 초기 random하게 설정되는 모델의 parameters의 값들에 따라
• 결정되는 local minimum에 해당하는 모델의 parameters를 구하게 되므로
• 항상 global solution을 구한다는 보장이 없음.

---

Batch, Mini-batch, and Stochastic GD

최초의 Gradient Descent (GD)는 gradient vector를 구할 때,

traing set의 모든 instances를 사용하여 구함 (각 instance에 대한 gradient vector들의 평균에 해당!).

때문에 Batch Gradient Descent라고도 불림 : 이때 batch 는 whole training set을 의미한다.

Deep Learning에서 8, 16, 32 등의 instances로 구성되는 batch는
GD의 관점에서는 사실 mini-batch라고 부르는 게 맞으나
앞뒤 문맥에 따라 해석해야함.

 

Batch GD는 모든 training set을 통해 한번의 update가 일어나기 때문에

• converge speed가 느리고,
• local minima에 빠지기 쉽다는 단점이 있음.

이에 반해,

• training set의 일부만을 random하게 선택하여 한번의 update를 수행하는 mini-batch GD 또는 
• training set에서 하나의 instance를 random하게 선택하여 한번의 update가 수행되는 stochastic GD는

보다 빠른 학습 및 local minimum 탈출이 가능하다는 장점을 가짐.

(단, optimum solution에서 fluctuation이 있다는 단점은 있음)

 

GD는 Gradient기반의 Optimizers의 기반이 되는 알고리즘이며, 여러 형태의 개선된 버전이 존재함.

https://dsaint31.me/mkdocs_site/ML/ch09/op_summary/

BME

---

Learning rate 의 중요성

GD에서 hyper-parameter인 leraning rate $\eta$에 의해

한번의 iteration을 통해 parameters $\boldsymbol{\omega}$가 업데이트 되는 정도가 결정됨.

• learning rate가 지나치게 작으면, optimized parameters에 이르는데 너무 많은 iterations가 필요함 (느린 수렴속도)
• 반대로 지나치게 크면, loss 값의 iteration에 따른 변화를 나타내는 learning curve가 수렴(converge)하지 않고 발산(diverge)하게 되어 최적의 모델 parameters를 구하지 못하게 됨.

https://www.jeremyjordan.me/nn-learning-rate/

문제는 적절한 learning rate가 경우에 따라 항상 다르기 때문에 각 프로젝트마다 tuning이 반드시 필요함.

 

Learning rate를 hyper-parameter가 아닌
이차미분에 해당하는 Hessian을 이용하여 구하도록 개선한 방법이 Newton Raphson Method임.

2022.06.07 - [Computer/ETC] - [ML] Newton-Raphson Method

[ML] Newton-Raphson Method

---

참고하면 좋은 자료들

2023.07.08 - [.../Math] - [Math] Linear Programming and Quadratic Programming

[Math] Linear Programming and Quadratic Programming

 

2023.06.23 - [.../Math] - [Math] Partial Derivatives (편도함수)

[Math] Partial Derivatives (편도함수)

 

2023.06.23 - [.../Math] - [Math] Directional Derivative (방향도함수)

[Math] Directional Derivative (방향도함수)