Gradient Descent

What is Gradient Descent?

이전 시간에 리뷰했던 Linear Regression에서 우리는 데이터에 대한 cost function(or loss, error)를 정의하여 cost function의 기울기 베타를 적절하게 조절하여 Training data에 맞는 cost function을 만들었습니다. 이때, '기울기를 어떻게 optimal 하게 만드냐'에 대한 문제로 cost function을 베타에 대해 미분하여 미분 값이 0에 가까워지는 베타를 찾아 적절한 기울기를 찾을 수 있었습니다. 물론 이후에 overfitting을 방지하기 위해 라쏘나 릿지 같은 방법에 대해 다뤘습니다.

 

하지만 이런 방법은 simple model에 대해서만 한정적이고 조금 더 복잡한 모델에 대해서는 단순한 미분만으로 찾을 수 없다고 했습니다. 요즘 많은 머신러닝 모델들은 복잡한 모델들이 많은데 이런 모델에 대한 최적화 문제를 풀 수 있게 나온 방법이 바로 Gradient Descent 방법입니다. 그럼 이제부터 Gradient Descent에 대해 리뷰해보겠습니다.

 

---

Local maxima & Global maxima or Local minima & Global minima

위 complex model에 있는 여러 봉우리 중에 임의의 한 봉우리를 가져와 탑 뷰로 내려다보면 아래와 같은 등고선을 볼 수 있습니다. Gradient Descent 방법은 간단합니다. 랜덤 한 포인트 starting point(x_0)를 찍고 그래프 기울기를 따라 극소점 또는 극대점을 찾습니다. 아래의 그림은 서서히 값을 증가시키며 x_0 -> x_1 -> x_2 -> x_3 -> x_4 순으로 극대점을 찾습니다. 한 봉우리에 대한 극대점을 찾았는데, 여러 봉우리도 존재하기 때문에 국소적인 곳에 대한 극대점을 찾았으므로, 이를 Local Maxima라고 합니다. 그리고 여러 봉우리 중 가장 큰 극대점을 Global Maxima 라고 합니다. 

 

출처: https://en.wikipedia.org/wiki/Gradient_descent

 

조금 더 직관적으로 설명드리자면, 여러 가지 (1,2,3,4,5) 봉우리가 있고 이때 랜덤 한 starting point(P)를 찍고 경사에 따라서 최대점 혹은 최소점을 찾으면 됩니다. 이때 cost function을 P에 대한 a와 b를 각각 편미분을 하면 각각의 값들이 나오고 이 값들을 하나의 vector로 정의하면 이를 Gradient라고 합니다.  수식으로 풀면 아래와 같습니다. 

 

 

 

vector는 방향을 가리키는 성질을 가지고 있는데, 이때 이 vector는 cost function이 증가하는 방향을 가리킵니다.

---

Gradient & differential

간단한 예제로 풀어보겠습니다. 아래의 그림은 1개의 파라미터(a)로 구성되어 있는 그래프입니다. a = 2라는 지점과 a = 5라는 지점에서 미분을 했을 때 각각 -0.5, 2라는 순간 변화량을 알 수 있습니다. 이 순간 변화량으로 a가 2일 때 -0.5 만큼 감소했고, a가 5일 때 2만큼 증가했음을 알 수 있습니다. 이런 식으로 다양한 모델 파라미터에 대해 편미분을 하면 각각의 관점에서의 순간 변화량을 구할 수 있습니다. 

 

 

만약에 모델 파라미터가 a,b,c,d로 총 4개를 가지고 있을 때 각각에 대한 순간 변화량을 구할 수 있고, 그 순간 변화량들로 이루어진 vector가 Gradient라고 합니다.

 

a, b, c, d에 대한 각각의 순간 변화량

매개변수들의 순간변화량의 벡터는 Gradient이다.

 

그렇다면 이제 우리는 Gradient에 대해 알았고 특성 또한 알고있습니다. 'vector는 cost function이 증가하는 방향을 가리킨다' 이번에는 국소점 즉 최소점을 찾아보겠습니다. a = 2에 대해 Gradient를 구했을 때, Gradient는 항상 증가하는 곳을 향해 양수를 가리키므로 우리는 아래의 그림처럼 음수 방향으로 천천히 값을 내리면서 최소점을 찾아야 합니다. (양수일 때는 음수로 즉, 부호 반대)

 

 

음수 방향으로 값을 천천히 내릴 때 일정한 값으로 천천히 내려야 하는데 일정한 값을 우리는 Step size (µ) (or, learning rate or typically less.. ex. 0.1)라고 부릅니다. (이 값은 hyperparmeter로 프로그래머가 임의로 값을 정해줘야 합니다.) 공식은 아래와 같습니다. 

 

---

threshold

초기에는 변화량이 굉장히 크지만 갈수록 변화량의 변화는 작아지는데 이때 적절한 최소점을 찾았다면 이제 Gradient descent를 멈춰야 하고 우리는 적절한 임계치(threshold)를 정해줘야 합니다. 이런 임계치를 구하기 위해서는 수많은 테스트 과정 속에서 찾아내거나 혹은 같은 연구분야에서 일반적으로 쓰이는 수치를 사용하면 됩니다.

 

 



결국 Gradient descent 방법은 high-dimensional space에서 랜덤 한 starting point를 선택하여 Gradient를 구하고 Gradient의 반대 방향으로 작은 step size를 곱하고 빼주며 일정한 간격으로 cost function이 수렴할때까지 반복하는 알고리즘입니다. 하지만 이런 방법의 치명적인 단점은 우리가 랜덤한 지점에서 시작하기 때문에 현재 구한 최소점이 Local minima 인지 Global minima 인지 구별할 수 없습니다. 

 

참고: https://towardsdatascience.com/a-visual-explanation-of-gradient-descent-methods-momentum-adagrad-rmsprop-adam-f898b102325c

 

 

본 글은 Hanyang University Computer and Software - Dong-Kyu Chae 교수님 수업 자료를 바탕으로 구성하였습니다.

 

Reference

https://en.wikipedia.org/wiki/Gradient_descent

https://towardsdatascience.com/a-visual-explanation-of-gradient-descent-methods-momentum-adagrad-rmsprop-adam-f898b102325c