[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를 구함.

---

1-1. 수식

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

$$\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.

---

1-2. GD와 Convex Objective Function

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

• 현재 parameters의 모델에서
  loss function를 가장 급격하게 감소시키는 parameters의 local 변화 방향을 나타냄.
• loss function이 parameters에 대해 convex인 경우에는
  최적의 해(global solution)에 해당하는 모델의 parameters에 수렴가능함.
• global minizers 중 하나에 수렴하려면, 적절한 step size와 충분한 iteration이 필요함.

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

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

---

1-3. GD와 Linear Regression

Linear Regression 의 loss function (or objective function) 인 Mean Squared Error (MSE)는 다음과 같음:

$$\begin{aligned}L(\boldsymbol{\omega}; X, \mathbf{y}) &= \frac{1}{N}\sum_{i=1}^{N}\left(y^{(i)} - \mathbf{x}^{(i)\top}\boldsymbol{\omega}\right)^2 \\ &= \frac{1}{N}\|\mathbf{y} - X\boldsymbol{\omega}\|^2 \end{aligned}$$

 

이 MSE objective function은

• model의 parameters에 대해 convex function 이므로
• GD method에서 적절한 learning rate (or step size)와 충분한 iteration을 취하면
• OLS의 objective function의 global minimizers(=global optima) 중 하나에 수렴 가능함.

주의할 것은 global optima 나 global minizers로 복수로 표현한 이유는,

• OLS의 training set으로 만들어지는 desgin matrix $X$가 full column rank이면 minimizer가 유일하나
• rank deficient이면 global minimizer가 여러 개일 수 있으므로
• objective function을 최소화하는 optimization problem의 solution이 항상 유일한 것은 아니기 때문임.

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

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

---

1-4. GD와 Deep Learning

Deep Learning의 학습 역시 다음과 같이 loss function을 최소화하는 optimization problem으로 볼 수 있음.

$$\mathbf{w}^{*} \in \arg\min_{\mathbf{w}} L(\mathbf{w}; X, \mathbf{y})$$

여기서 $\mathbf{w}$는 network 전체의 parameters를 의미하며 일반적으로는 $\mathbf{\theta}$로 기재되는 경우가 더 많음..

 

다만 Deep Learning의 loss function은
여러 층의 linear transformation과 non-linear activation function의 합성으로 이루어지므로,
일반적으로 model parameters $\mathbf{w}$에 대해 convex function이 아님.

따라서 GD 계열 method를 사용하더라도,
Linear Regression처럼 항상 global minimizer에 수렴한다고 보장할 수는 없으며,
초기 random initialization과 학습 조건에 따라 서로 다른 local minimum 또는 saddle point 부근으로 수렴할 수 있음.

그럼에도 불구하고 Deep Learning에서는

• closed-form solution이 거의 없고
• parameter 수와 dataset 규모가 매우 크기 때문에,

backpropagation으로 계산한 gradient를 이용하여 parameters를 반복적으로 갱신하는
iterative optimization method인 GD 계열이 표준으로 사용됨.

기본적인 update는 다음과 같음.

$$\mathbf{w}_{t+1} = \mathbf{w}_{t} - \eta \nabla_{\mathbf{w}} L(\mathbf{w}_t; X, \mathbf{y})$$

 

실제 Deep Learning에서는

• 전체 dataset을 update 한 번에 사용하는 Batch Gradient Descent보다는,
• mini-batch를 이용하여 gradient를 근사하는
  • SGD,
  • Momentum,
  • RMSProp,
  • Adam,
  • AdamW 등의 GD 계열 optimizer가 주로 사용됨. 

이는 한 번의 parameter update 비용을 줄이면서도 대규모 dataset에 대해 효율적으로 학습할 수 있게 해 주기 때문임

https://dsaint31.me/mkdocs_site/ML/ch09/op_summary/#gradient-optimizers

BME

---

2. 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 (방향도함수)