Gradient Descent (concepts) (+momentum)

* 오늘도 머신러닝에서 꼭 배우고 가야 할 'Gradient Descent' 개념에 대해서 알아보고 가자 😇

 

*Gradient Descent는 일종의 최적화(optimization) algorithm 중 하나로 비용함수(비용)를 최소화하는 함수의 파라미터를 찾을 때 사용된다

 

*😔 잘 감이 오지 않음 저번에 배운 「SLR」 모델을 예로 들자면

Simple Linear Regression (concepts)

 

 

→ 과정 ③에서 우리는 관측치에 의거하여 최적의 model을 찾는다고 하였다. 이 때 SLR의 경우 intercept와 slope을 찾는 것일 텐데, 이 두 가지 최적의 값을 찾는 데서 gradient descent 방법을 사용한다!

 

→ 그럼 Gradient Descent 개념을 적용하기 위해서는 우리는 먼저 ①어떤 변수를 최적화하는 데 focus를 둘 지 생각해야 한다

≫ SLR 예시에서는 slope는 일정한 값으로 구했다 가정하고 intercept 최적화 해보자!

→ 그 다음에 우리는 gradient descent를 적용할 최소화할 ②Cost Function을 구해야 한다

≫ SLR의 경우 Cost function은 SSR(Sum of Squared Residuals)

→ 그러면 ①최적화할 변수의 변화에 따른 ②Cost Function 값을 x와 y축에 그린다

 

≫ 여기서 intercept에 따른 cost function(SSR)을 graph로 나타내면 아래와 같다

 

 

※ 여기서 주의 ※

 

→ intercept의 최적의 값(optimal value)을 구하기 위해 Least-Squares Method를 사용하면 단순히 '곡선의 기울기 = 0'이 되는 지점을 찾았을 것이다.

→ 하지만, GD(Gradient Descent)는 다름! GD는 초기 예측값(initial guess)에서 시작해 주위 몇 계단 씩 나아가면서 최소값 minimum value를 찾아나가는 과정이다. 즉! GD는 derivaitive 미분값이 0이 되는 지점이 존재하지 않는 경우여도 적용할 수 있다는 점이 장점이다

→ 여기서 ③Gradient Descent는 최적의 값으로부터 거리가 있는 값에서는 큰 step을 밟으며 진행해 나아가고, 최적의 값이 있는 근처에서는 조금씩의 step을 밟으며 최적 값을 향해 진행한다

≫ 위 SLR의 cost function 같은 경우 최적 값 근처인 0 부근일 경우 step을 조금씩 밟는다.
(최적의 값이 부근에 있기 때문에 자칫 큰 step을 밟으면 지나칠 수 있으므로!)

 

→ step의 size는 너무 크지도 않아야 하고 slope과 관련 있어야 한다

→ 즉 ④step size를 구하는 방법은 slope값에(미분값) 조그마한 learning rate 값을 곱함으로써 결정된다

→ 정해진 step size를 가지고 an 지점에서 an+1로 움직인다! (진행)

 

 

→ 그러면 언제 멈출까? ⑤step size가 거의 0부근일 때 멈춘다 (즉 slope인 미분값이 거의 0일때 멈춤)

(+) 추가로 GD는 진행 중단 전까지 몇 step을 거쳐야 하는 지 ⑥최대 step 수에 limit을 건다

→ 즉 step size가 여전히 크더라도 최대 step 수를 초과하면 GD 진행 중단 (⑤와 ⑥일 때 중단)

 

Q) 최적화할 변수가 2개 이상이라면?

 

≫ 위 SLR에서 두 변수 intercept & slope 모두 최적화하고 싶다면 각각에 대한 미분값(각 관측치에의 미분값들의 합)을 Gradient라고 한다

- 이 Gradient를 loss function의 최소지점을 향해서 낮추는(descent) 방식을 똑같이 진행한다. (그래서 이름이 'Gradient Descent!')

 

<다시 정리하면>

 

ⓐ 손실함수 loss function의 gradient(미분값)을 구한다

ⓑ random하게 첫 시작점 선택 → 해당 시작점에서의 미분값 구하기

ⓒ step size 구하기(sleop * learning rate)

ⓓ step size를 통해 움직인 새로운 지점 구하기

ⓔ ⓑ - ⓒ - ⓓ 과정을 반복!

ⓕ step size가 너무 작아졌거나 & 최대 step 수 도달할 때까지 계속 진행한다

 

Q) Stochastic Gradient Descent는? - 전체 dataset의 cost function 값을 구하기 어렵다는 문제

 

→ GD와 다르게 Stochastic GD의 경우 매 step마다 주어진 data가 너무 많은 문제를 해결하고자 랜덤하게 일부 data에 대한 cost function의 값을 사용한다 

 

Q) 학습률 𝜂의 적절성?

 

→ 학습률이 너무 낮으면 알고리즘이 수렴되는 지점을 찾기 위해 너무나도 많은 반복 과정을 거쳐야 해서 시간 지연 문제

→ 학습률이 너무 크면 극소값, 즉 최소가 되는, 우리가 원하는 지점을 놓칠 가능성이 커서 계산을 계속 반복하게 됨

 

- 예시를 보면 learning rate이 0.1로 더 클 경우 훨씬 적은 step 수로 도달했음을 알 수 있다. -

---

(+) Momentum

 

"an extension to the gradient descent optimization algorithm that allows the search to build inertia in a direction in the search space and overcome the oscillations of noisy gradients and coast across flat spots of the search space"

≫ 즉! gradient descent algorithm의 경우 국소 최솟값에서 머무르는 한계가 발생할 수 있는데, 여기에 momentum을 더한다면 noisy한 gradient의 주변 진동을 극복해 찾는 공간 search space를 가로질러 그 이상의 공간으로 움직여서 최소가 되는 지점을 찾을 수 있게 해주는 게 장점!

 

"It is designed to accelerate the optimization process, e.g. decrease the number of function evaluations required to reach the optima, or to improve the capability of the optimization algorithm, e.g. result in a better final result."

≫ 더 좋은 성능(결과)을 내기 위해 기존 optimization process에 효율을 더 가하는 방식!

 

"Momentum involves maintaining the change in the position and using it in the subsequent calculation of the change in position. If we think of updates over time, then the update at the current iteration or time (t) will add the change used at the previous time (t-1) weighted by the momentum hyperparameter, as follows:

 

change_x(t) = step_size * f'(x(t-1)) + momentum * change_x(t-1)

 

The update to the position is then performed as before.

 

x(t) = x(t-1) – change_x(t)

 

The change in the position accumulates magnitude and direction of changes over the iterations of the search, proportional to the size of the momentum hyperparameter. For example, a large momentum (e.g. 0.9) will mean that the update is strongly influenced by the previous update, whereas a modest momentum (0.2) will mean very little influence."

≫ 구체적인 식을 보자면, momentum으로 가해진 크기에 의해 기존 position의 위치변화 정도를 변화시킬 수 있다!

 

Q. 그럼 momentum은 어떨 때 유용할까?

 

1> Momentum is most useful in optimization problems where the objective function has a large amount of curvature (e.g. changes a lot), meaning that the gradient may change a lot over relatively small regions of the search space.

≫ 비용함수가 매우 큰 곡선, 즉 변화의 크기가 큰 형태일 때 정말 심하게 변하는 gradient를 momentum을 통해 잠재울 수 있는 효과!

 

2> It is also helpful when the gradient is estimated, such as from a simulation, and may be noisy, e.g. when the gradient has a high variance.

≫ graident 자체가 큰 변화폭을 가질 때 momentum을 통해 그 정도를 잠재울 수 있음!

 

3> Finally, momentum is helpful when the search space is flat or nearly flat, e.g. zero gradient. The momentum allows the search to progress in the same direction as before the flat spot and helpfully cross the flat region.

≫ 혹은 그 반대로 search 공간 자체가 적어서 gradient가 잘 못나갈 때 그 공간을 벗어나게 하기 위해 momentum 사용 가능!

---

* simulation 출처) https://developers.google.com/machine-learning/crash-course/fitter/graph

* 출처1) 갓StatQuest - PARTY MORE STUDY LESS https://www.youtube.com/watch?v=sDv4f4s2SB8 

* 출처2) https://machinelearningmastery.com/gradient-descent-for-machine-learning/

* 출처3) https://machinelearningmastery.com/gradient-descent-with-momentum-from-scratch/

* 썸네일 출처) https://www.codetd.com/en/article/12814773