[Gradient Descent] part 2 - 3

🎯 Keyword 🎯

- Gradient Descent

Gradient Descent는 iterative하게 최적 parameter θ 를 찾아가는 과정입니다.

 

Gradient

함수를 미분하여 얻는 term으로 해당 함수의 변화하는 정도를 표현하는 값

 

우리가 최소로 하고 싶은 loss function과 error surface가 있다고 합시다.

 

1. 어떤 임의의 point에서 이 error surface에서 최소인 point를 찾아가는 것이 목적입니다.

 

2. 해당 error surface에서 최소인 point의 특징은 gradient가 0인 것입니다.

 

3. Gradient Descent에서는 error surface에서 Gradient가 0인 지점까지 θ를 바꿔 나가며 탐색합니다.

 

4. 해당 탐색 과정은 기울기가 가장 큰 방향으로 한 걸음 한 걸음 딛는 것입니다.

 

5. Gradient Descent에서는 함수의 변화도가 가장 큰 방향으로 이동하는 것입니다.

 

Gradient Descent Equation

 

위 그림에서

α는 parameter를 update 할 때, 속도를 조절할 때 사용 됩니다.

 

-> 너무 작으면 시간이 오래 걸릴 것입니다.-> 너무 크면 gradient가 0인 곳을 놓치기가 쉬워서 수렴하기가 어려워집니다.

 

• 어떤 방향으로 ?
  • Steepest gradient descent with a greedy method
    • 현재 지점에서 가장 변화도가 가장 가파른 모양으로 업데이트 해나갑니다.
• 얼마나 많이 ?
  • Step size

 

Greedy Algorithm의 특징

Gradient Descent Algorithm 은 경우에 따라 Local optimum만을 달성하기 쉽다.

 

 

• Global optimum
  • Global optimum은 전체 error surface에서 가장 최소인 값을 갖는 지점입니다.
• Local optimum
  • Local optimum은 지역에서는 최소가 될 수 있지만 전체영역을 놓고 보았을 때는 최소가 아닐 수 있는 지점입니다.

 

서로 다른 지점에서 시작을 하는 경우, 어느 하나는 Global optimum을, 어느 하나는 local optimum을 가질 수 있습니다.

 

내가 이동한 방향이 전체에서 최적화된 포인트가 아니게 될 가능성이 있습니다.

 

 

• Gradient Descent 수행 과정
  1. 최적화 하고자 하는 loss function 혹은 objective function을 세웁니다.
     
     
  2. α와 같은 algorithm 수행에 필요한 parameter를 설정합니다.
     (이렇게 사전에 설정한 parameter를 hyper parameter라고 합니다. 항상 양의 값을 갖습니다.)
     Gradient descent를 통해 학습시키고자 하는 parameter θ 는 learnable parameter라고 부릅니다.
     
     
  3. Gradient descent algorithm의 시작은 initial parameter θ0, θ1(initial point)을 설정하는 것에서부터 시작합니다.
     
     
  4. 우리의 목적 함수가 수렴할 때까지 parameter를 계속 바꿔나가는 과정을 반복해 나갑니다.
     
  5. 아래 그림과 같이 θ0, θ1, .. 에 대해 미분을 하여 식을 구할 수 있습니다.
     θ0, θ1에 대해 각각 미분한 것입니다.
     아래 그림과 같이 convergence할 때까지 반복해 나갑니다.

θ0,  θ1 미분

하나씩 자세히 보겠습니다.

 

θ0

 

1. error term으로, sample들의 모든 error를 측정한 다음에 더합니다.

2. 그 다음, hyper parameter α를 곱하여 update를 진행해 나갑니다.

 

 

θ1

 

1. θ1의 경우에는 error term 이외에도 sample을 곱하여 모두 더한다음 update를 진행해 나가게 됩니다.

 

 

 

 

Gradient Descent와 Normal Equation간의 차이

 

• Gradient Descent
  • 반복적인 과정 수행을 통해 해를 얻어 나갑니다.
  • 설령 N이 굉장히 크더라도 반복적으로 해를 구할 수 있습니다.
• Normal Equation
  • one-step으로 해를 구합니다.
    • 그러나 matrix 곱이 이루어져 우리의 sample size가 굉장히 늘어나게 되는 경우, inverse matrix 등을 구하기가 굉장히 어려워지는 문제가 발생하게 됩니다.

 

그러나 아직 남아있는 불편함을 해결하기 위해 stochastic gradient descent, mini batch algorithm을 사용하게 됩니다.

 

이러한 방법들을 통해 Gradient Descent algorithm이 Local Minina에 빠지지 않도록 합니다.