Gradient Descent란?

기본적인 함수 최적화(optimization) 방법 중 하나인 gradient descent 방법에 관한 글입니다.

 

Gradient descent 방법은 미분의 개념을 최적화 문제에 적용한 대표적 방법 중 하나로서 함수의 local minimum을 찾는 방법 중 하나입니다. Gradient descent 방법을 다른 말로 steepest descent 방법이라고도 부릅니다.

• 기본개념은 함수의 기울기(경사)를 구하고 경사의 반대 방향으로 계속 이동시켜 극값에 이를 때까지 반복시키는 것입니다.

딥러닝 머신러닝 Task에서 Gradient Descent 종류 이런 것 보다 먼저, 일반적인 설명 수학적인 부분을 고려해가면서 공부 겸 설명을 이어가도록 하겠습니다. ( 제가 여러 책 및 블로그 등을 정리하면서 작성한 글입니다. 맨 마지막에 출처를 기재할 테니 참고하시기 바랍니다.)

 

0. gradient descent의 목적과 사용 이유

gradient descent는 함수의 최소값을 찾는 문제에서 활용된다.

함수의 최소, 최댓값을 찾으려면 “미분계수가 0인 지점을 찾으면 되지 않느냐?”라고 생각할 수 있습니다. 하지만 미분계수가 0인 지점을 찾는 방식이 아닌 gradient descent를 이용해 함수의 최솟값을 찾는 주된 이유는

• 우리가 주로 실제 분석에서 맞딱드리게 되는 함수들은 닫힌 형태(closed form)가 아니거나 함수의 형태가 복잡해 (가령, 비선형함수) 미분계수와 그 근을 계산하기 어려운 경우가 많고,
• 실제 미분계수를 계산하는 과정을 컴퓨터로 구현하는 것에 비해 gradient descent는 컴퓨터로 비교적 쉽게 구현할 수 있기 때문이다.

추가적으로,

• 데이터 양이 매우 큰 경우 gradient descent와 같은 iterative 한 방법을 통해 해를 구하면 계산량 측면에서 더 효율적으로 해를 구할 수 있다.

1. Gradient descent 방법의 직관적 이해

자신이 한치앞도 잘 안 보이는 울창한 밀림에 있을 때 산 정상으로 가기 위한 방법은 간단합니다. 비록 실제 산 정상이 어디에 있는지는 모르지만 현재 위치에서 가장 경사가 가파른 방향으로 산을 오르다 보면 언젠가는 산 정상에 다다르게 될 것입니다.

 

또는 이와 반대로 깊은 골짜기를 찾고 싶을 때에는 가장 가파른 내리막 방향으로 산을 내려가면 될 것입니다.

 

이와 같이 어떤 함수의 극대점을 찾기 위해 현재 위치에서의 gradient 방향으로 이동해 가는 방법을 gradient ascent 방법, 극소점을 찾기 위해 gradient 반대 방향으로 이동해 가는 방법을 gradient descent 방법이라 부릅니다. ( 이와 같은 설명들이 러프하게는 실제 딥러닝에서 가중치들의 최적의 해를 찾아가는 가장 기본적인 방법이라고 생각하시면 될 것 같습니다.)

 

2. Gradient(그레디언트)

기울기(gradient그레이디언트) 또는 경도란 벡터 미적분학에서 스칼라장의 최대의 증가율을 나타내는 벡터장을 뜻한다.
쉽게 말해서 미분해서 나온 결과 값 또는 딥러닝의 수학적으로는 텐서 연산의 변화율이다. 이는 다차원 입력, 즉 텐서를 입력으로 받는 함수에 변화율 개념을 확장시킨 것이라고 생각하시면 될 것 같습니다.

어떤 다변수 함수 f(x1,x2,...,xn)이 있을 때, f의 그레디언트(gradient)는

다변수 함수 (1)

와 같이 정의됩니다. 즉, 그레디언트(gradient)는 위 식과 같이 각 변수로의 일차 편미분 값으로 구성되는 벡터입니다. 그리고 이 벡터는 f의 값이 가장 가파르게 증가하는 방향을 나타냅니다. 또한 벡터의 크기는 그 증가의 가파른 정도(기울기)를 나타냅니다.

 

예를 들어, f(x,y) = x2 + y2의 그레디언트(gradient)를 구해보면

다변수 함수 (2)

이므로, (1,1)에서 f값이 최대로 증가하는 방향은 (2,2), 그 기울기는 ∥(2,2)∥= sqrt(8)입니다.

<그림 1> f(x,y) == x^2 &nbsp;+ y^2 &nbsp;그래프

또한 반대로 그레디언트(gradient)에 음수를 취하면 즉, -▽f는 f값이 가장 가파르게 감소하는 방향을 나타내게 됩니다.

 

이러한 그레디언트의 특성은 어떤 함수를 지역적으로 선형 근사(linear approximation)하거나 혹은 함수의 극점(최댓값, 최솟값 지점)을 찾는 용도로 활용될 수 있습니다.

 

 

Gradient 벡터

그런데 생각해보자면 딥러닝에서는 입력값이 이차원 공간의 점이 아니라,  n차원 공간의 점인 벡터입니다. 그래프를 따라 왼쪽, 오른쪽으로만 이동하는 것이 아니라, n차원이기 때문에 굉장히 많은 방향으로 이동할 수 있을 것입니다. 이 경우 단순한 미분으로는 함수값의 변화을 측정하기 힘든 부분이 있습니다.

 

따라서 이처럼 벡터가 입력값인 다변수 함수의 경우, 편미분(partial differentiation)을 사용합니다.

이때 e_i는 i번째 값만 1이고 나머지는 0인 단위벡터(I)를 의미합니다.

 

3차원공간 상에 다음과 같이 다변수 함수를 표현한다고 생각해보면

 

출처 :https://blogik.netlify.app/BoostCamp/U_stage/05_gradient_descent/

이 때, 오른쪽의 그림을 등고선으로 옮기면 다음과 같습니다.

출처 : https://blogik.netlify.app/BoostCamp/U_stage/05_gradient_descent/

• gradient 벡터 ∇f(x,y) 는 각 점 (x,y)에서 가장 빨리 증가하는 방향과 같다.
• gradient 벡터 −∇f는 ∇(−f)와 같고, 이는 각 점 (x,y)(x,y)에서 가장 빨리 감소하는 방향과 같다.

이는 임의의 차원 d 에서도 성립한다.

 

 

3. Gradient descent 방법

최적화 알고리즘 중 하나로 널리 알려진 gradient descent 방법은 이러한 그레디언트의 특성을 이용하여 어떤 비용 함수의 값을 최소화시키기 위한 파라미터 값을 아래와 같이 점진적으로 찾는 방법입니다. 여기서 말하는 '어떤 비용 함수'라 함은 딥러닝에서 사용하는 Cost function을 뜻하며, 다른 말로는 손실 함수, loss function을 뜻 합니다.

식 (3)

즉, 어떤 초기값  x0 = (x10,..., xn0)부터 시작하여 위 식에 따라 gradient 반대 방향으로 x를 조금씩 이동시키면 f(x)가 극소가 되는 x를 찾을 수 있다는 방법이 gradient descent 방법입니다.

 

☞ 만일 함수의 극소점이 아니라 극대점을 찾는 것이 목적이라면 식 (3) 대신에 아래의 식 (4)를 이용하여 x를 업데이트합니다 (gradient ascent 방법)

식 (4)

<그림 2> gradient descent 방법 (그림출처:&nbsp;위키피디아)

식 (3)에서 λ는 알고리즘의 수렴 속도를 조절하는 파라미터로서 step size 또는 learning rate라 불립니다.

 

Gradient descent 방법의 문제점은 쉽게 생각할 수 있듯이 local minimum에 빠지는 것입니다. 즉, 이쪽이 산 정상인 줄 알고 열심히 올라갔더니 막상 여기는 작은 언덕 정도이고 바로 옆에 훨씬 높은 산이 있는 경우입니다.

 

Gradient descent 방법의 또 하나의 문제점은 해에 근접할수록 |∇f|가 0에 가까워지기 때문에 수렴 속도가 느려진다는 것입니다. 그렇다고 수렴 속도를 조절하는 step size 파라미터 λ를 너무 크게 하면 알고리즘이 발산할 수 있는 문제점이 있습니다 (step size를 자동으로 adaptive 하게 조절하는 방법도 있습니다).

 

4. gradient descent의 수식 유도

앞서서 이야기한 '어떤 비용 함수의 값을 최소화시키기 위한 파라미터 값을 아래와 같이 점진적으로 찾는 방법'인 gradient descent는 함수의 기울기(즉, gradient)를 이용해 x의 값을 어디로 옮겼을 때 함수가 최솟값을 찾는지 알아보는 방법이라고 할 수 있습니다. 기울기가 양수라는 것은 x 값이 커질수록 함수 값이 커진다는 것을 의미하고, 반대로 기울기가 음수라면 x값이 커질 수록 함수의 값이 작아진다는 것을 의미한다고 볼 수 있습니다. ( 여기서 우리가 찾는 것은 손실 함수의 최솟값을 얼마나 잘 찾는 것이 목표가 됩니다.)

또, 기울기의 값이 크다는 것은 가파르다는 것을 의미하기도 하지만, 또 한편으로는(일반적으로) x의 위치가 최솟값/최댓값에 해당되는 x 좌표로부터 멀리 떨어져 있는 것을 의미하기도 합니다.

 

<그림 3> 기울기가 양수일 때와 음수일 때의 비교

---

위에서 간단하게만 설명했으니 이제 선형회귀를 예로 들면서 설명해보도록 하겠습니다.

풀이

선형회귀의 목적식 (5)

선형회귀의 목적은 이를 최소화하는 β를 찾는 것이다. 따라서 목적식을 β로 미분한다음, 주어진 β에서 미분값을 뺀다면, 경사하강법 알고리즘으로 최소에 해당하는 점을 구할 수 있다.

선형회귀
행렬 X에 m개의 변수와 n개의 샘플이 있고, 각 샘플에 대한 결과값인 y가 있는 상태를 가정하자 이때, Xβ=^y≈yXβ=y^≈y
를 만족하는 β를 찾고자 하는 것이 선형회귀분석이다.
하지만 어떤 β으로도 Xβ=yXβ=y를 만족시키는 건 거의 불가능하므로 목적함수를 설정하는데, 이는 y−^y의 L2 Norm을 최소화하는 것으로 한다.

minβ||y−^y||2minβ||y−y^||2
즉, ||y−^y||2||y−y^||2 를 최소화하는 β를 구하는 것이 목표이다.

다음과 같은 Grdient 벡터를 구해보자.

β=(β1,β2,⋯,βd)

 

 

이 때 β 의 k번째 계수에 해당하는 βk​를 가지고 목적식을 편미분하는 식을 풀어서 보면 아래와 같은 식이 됩니다.

 

여기서 조심할 점은, 일반적인 수학의 L_2 - norm과 풀이 방식이 살짝 다르다는 것입니다.

여기서 사용하는 L_2-norm은 모델 학습에 사용되는 것이므로, n개의 데이터셋을 가지고 있다는 가정하에 출발합니다. 따라서 단순히 바로 합산해서 루트를 씌워주는 합산식을 쓸게 아니라 먼저 1/n으로 평균을 내준뒤에 사용하셔야 합니다.

 

이 때에 사용되는 loss(cost fuction)는 RMSE(Root Mean Squared Error)입니다. 다음과 같은 도출과정을 따르고 있습니다.

• SE(Sqaured Error)는 각 데이터별로 정답과 예측 벡터의 차이를 L_2-norm의 제곱으로 계산한다.
• MSE (Mean Squared Error)는 SE를 데이터의 숫자만큼 나누어준다.(평균내기)
• RMSE (Root Mean Squared Error)는 MSE에 제곱근을 취해준다.

사실 정확히 쓰면 기대값 기호를 붙여

식 (6)

라고 써야하지만, norm의 기호가 원래 확장성이 있기도 하고, 관용적으로 RSME를 L_2-norm처럼 쓴다고 합니다.

 

이를 계산하여 정리하면 다음과 같습니다.

식 (7)

 

식 (8)

식 8번을 최소화하면 식이 좀 더 간결해진다.

 

경사하강법의 한계

위의 알고리즘은 다음과 같은 이유로 모든 상황에서 작동하지는 않는다.

• 이론적으로 경사하강법을 사용하려면 목적함수가 모든 지점에서 미분 가능해야하며, 볼록한(convex) 형태를 가져야 한다.
• 선형회귀의 경우 목적식 ∥y−Xβ∥2은 회귀계수 β에 대해 볼록함수이므로 알고리즘을 충분히 돌리면 수렴이 보장된다.
• 하지만 비선형회귀 문제의 경우 목적식이 볼록하지 않을 수 있으므로 수렴이 항상 보장되지 않는다.
• Learning Rate 값이 너무 작거나 커서 지역적인 극소 위치로 수렴할 경우 전체 목적식에 대한 최솟값을 보장하지 못한다.

 

다음 장에서는 경사하강법의 종류와 각각의 장단점에 대해서 설명하도록 하겠습니다.

 

 

출처 :

https://darkpgmr.tistory.com/133

Gradient Descent 탐색 방법

 

https://glanceyes.tistory.com/entry/%EB%AF%B8%EB%B6%84%EA%B3%BC-%EA%B2%BD%EC%82%AC%ED%95%98%EA%B0%95%EB%B2%95Gradient-Descent?category=1069509 

미분과 경사하강법(Gradient Descent)

 

https://blogik.netlify.app/BoostCamp/U_stage/05_gradient_descent/

경사하강법(Gradient Descent)의 기초와 이해

 

https://velog.io/@naem1023/Gradient-descent-%EC%A6%9D%EB%AA%85

Gradient descent 증명

https://enfow.github.io/study/deep-learning/2020/01/18/gradiend_descent/

Gradient Descent · Enfow's Blog

https://angeloyeo.github.io/2020/08/16/gradient_descent.html

경사하강법(gradient descent) - 공돌이의 수학정리노트