Gradient Descent

Gradient Descent

경사하강법은 미분을 통해 얻은 Gradient Vector를 빼서 Weight를 업데이트하여 cost function을 줄이는 알고리즘이다.

 

Loss fucntion의 기울기를 미분을 통해 구하고 경사의 절댓값이 낮은 쪽으로 계속 이동시켜 극값에 이를 때까지 반복시킨다.

 

Formula

• $f(x)$: 최소값을 만드는 것이 목표인 Loss function
• $x_{i}$: i번째 업데이트된 weights
• $x_{0}$: x의 초기값
• $\eta$: Learning Rate

 

위의 과정을 반복하여 $f(x)$의 값이 정해진 값 보다 작아질 때까지 이를 반복한다.

 

#gradient: grad function
#eps: epsilon

var = init
grad = gradient(var)
while (abs(grad) > eps):
  var = var - lr * grad
  grad = gradient(var)

 

실제 데이터에서는 다변수 데이터가 대부분이고, 이 때 변수는 벡터로 각 변수에 대해 편미분을 적용하여야 한다.

 

다변수 함수에서는 각 변수에 대해 편미분을 한 그래디언트 벡터를 사용하여 경사 하강법을 진행한다.

 

 

그래디언트 벡터 nabla f 는 각 변수에 대해 편미분 한 벡터를 모은 것이다.

convex loss function에 대한 그래디언트 벡터를 시각화하면 다음과 같다.

 

 

-1을 곱해주면 이는 각 지점 (x, y)에서 f가 최소인 지점을 향하는 벡터 값이 된다.

Pseudo code로 이를 나타내면 이번엔 모든 변수의 크기를 계산할 수 있는 norm 함수가 추가되어야 한다.

 

#gradient: grad function
#eps: epsilon
#norm: calculate L2 norm

var = init
grad = gradient(var)
while (norm(grad) > eps):
  var = var - lr * grad
  grad = gradient(var)

 

 

위 방식이 오차를 줄일 수 있는 이유는 다음과 같다.

 

 

 

세타0와 세타가 근사하다는 가정하에 first-order 테일러 전개의 값은 cost function과 유사하다. cost function에 세타0를 대입한 값이 세타를 대입한 값보다 커야하기 때문에 두번째 수식이 도출된다.

세번째 수식에서 매우작은 epsilon값이 우변에 곱해지게 되는데 이는 초기 가정을 뒷받침하며, 비례식을 등식으로 만드는 변수로 learning rate에 해당한다.

 

 

SGD

확률적 경사 하강법(Stochastic Gradient Descent)은 모든 데이터를 사용하지 않고 일부를 활용하여 weights를 업데이트한다.

 

미니 배치를 활용할 때 loss function은 모든 데이터를 사용하였을 때와 그래프의 개형이 다를 수 있다. 

 

위와 같이 non-convex function의 경우 모든 데이터를 사용하는 경사 하강법을 통해 얻을 수 있는 loss function은 유일하며 위와 같이 local minina에 갇히게 된다.

따라서 SGD를 사용하는 것이 효율적이다.

 

 

매번 다른 미니 배치를 활용하기 때문의 곡선의 모양은 위와 같이 달라지며 가중치가 업데이트되는 정도도 곡선에 따라 기울기가 다르기 때문에 gradient의 차이로 인해 달라지게 된다.

볼록하지 않은 목적식에도 사용이 가능하며 모든 데이터를 보지 않고도 다음 업데이트 방향을 정하기 때문에 머신러닝 학습에 SGD가 더 효율적이다.

 

 

 

Reference

[1] 네이버 부스트캠프 임성빈 교수님 - AI MATH 경사하강법