[Machine Learning] Gradient Descent

해당 내용은 Andrew Ng 교수님의 Machine Learning 강의(Coursera)를 정리한 내용입니다.

- Gradient Descent 경사 하강법

Gradient Descent Algorithm은 Cost Function의 최소값을 구하는 알고리즘이다(즉, 최소가 되도록 하는 을 구하는 알고리즘이다). 이 알고리즘은 Linear Regression 뿐만 아니라 대부분의 머신러닝에서 실제로 사용되는 알고리즘이다. 

 

Gradient Descent 알고리즘은 다음과 같은 방법으로 진행된다. 

1. Start with some  (say )

2. Keep changeing  to reduce  until we hopefully end up at a minimum

즉, 임의의 초기값으로 시작하여, 최소의 Cost Function 값을 찾을 때까지 을 변경시킨다. 임의의 초기값을 기준으로 최소가 되는 점을 찾아나는 알고리즘이다.

초기값에서 시작을 해서 주위를 둘러보며 최소값으로 향하는 가장 빠른 길을 찾아서 최소값을 찾아내지만, 초기값이 다르다면 다른 결과(다른 지역적 최소값)를 도출할 수도 있다.

 

 

Gradient Descent Algorithm을 수학적으로 정의하면 아래와 같다.

repeat until convergence {

}

 

• : 할당 연산자(ex, a := b 는 b의 값에 a를 할당한다는 의미 / e.g. a := a + 1 -> a값에 1을 더해준다는 의미)
• : Learning Rate
• : Derivative Term(미분 계수)

:= 는 할당받는 것을 의미한다. 즉, 알고리즘에서는 에 을 대입한다는 의미이다. 

는 Learning Rate 이며, 위 그래프처럼 시작점에서 최소점을 찾아나갈 때, 얼마나 큰 걸음으로 찾아나갈 것인가를 나타내는 양의 상수이다. 이 값을 클수록 한 Step에 움직이는 길이가 길어진다. 

는 비용함수를 에 대해 미분한 함수이다. 하지만 비용함수는  총 2가지 변수에 의해 영향을 받고 있다. 우리는 이러한 대입 과정을 지속하는데, 아래의 오른쪽 그림처럼 대입을 하게되면 의 값을 대입할 때 비용함수가 이미 영향을 받으므로(새로운 으로 계산하게 된다) 왼쪽의 경우처럼 Simultaneous하게 update를 해주어야 한다.

 

[Derivative Term과 Learning Rate]

상수 는 Learning Rate이며 양의 정수이다. Learning Rate와 Derivative Term이 같이 사용되었을 때 어떤 의미를 갖는 지 예제를 통해서 살펴보자.

위 그림과 같이 미분 계수항이 양수이면, 값이 점점 줄어들면서 최소로 향하는 모습이라는 것을 알 수 있다. 이것이 기울기 하강(Negative Slope)이다.

위 그림과 같이 미분 계수항이 음수이면, 값이 점점 증가하면서 최소로 향하는 모습을 볼 수 있다. 이것이 기울기 상승(Positive Slope)이다. 

 

 

만약 Learning Rate가 너무 작다면 수렴(Convergence)하는데에 너무 오래 걸리는 문제가 발생하고, 너무 크다면 최소값에 이르지 못해 수렴하지 못하거나 발산(diverge)하는 문제가 발생할 수 있다. 그러므로 적절한 Learning Rate를 선택하는 것이 중요하다.

 

Gradient Descent 알고리즘이 Local Optima(기울기가 0)에 이르면 미분 계수항이 0이 되므로 더 이상 업데이트되지 않으며, 값을 유지하게 된다.

 

대부분의 경우에 local minimum value에 가까워질수록 미분계수의 값이 0에 가까워 지면서 조금씩 점진적으로 업데이트 되기 때문에 Learning Rate를 수동으로 변경하지 않아도 된다.

 

[Gradient Descent for Linear Regression]

우리는 이제 Gradient Descent를 Linear Regression에 적용해보려고 한다.

즉, Gradient Descent 알고리즘을 Cost Function에 적용하여 최소화시킬 것이다. 이 과정에서 가장 중요한 것은 미분계수이며, 예시에서는 두 개의 파라미터가 존재하기 때문에 2개의 함수가 각각 나오게 되며, 아래와 같은 결과가 나오게 된다.

그리고 위 식을 Gradient descent algorithm에 적용하면 다음과 같다.

중요한 것은 을 동시에 구해서 동시에 업데이트해야 한다는 것이다.

 

 

앞에서 기울기 하강(Nagative Slope)이 Local Optima에 민감하다는 것을 보았다. 따라서, 초기값의 위치에 따라서 최적의 최소값이 달라진다는 것을 언급했다. 그러나 Linear Regression의 Cost Function은 항상 아래와 같은 모양이 된다. 

항상 Bowl-Shaped Function을 갖게 되고, 여기서 Local Optima(Logical Minimum)이 없이 Global Optima(Global Minimum)만 갖게되어 Linear Regression은 항상 Global Optima로 수렴하게 되어있다. 그래서 이러한 규칙을 따라서 알고리즘을 진행하면 결국 최소값에 도달하게 된다.

[Batch Gradient Descent]

우리가 배운 Gradient Descent 알고리즘의 다른 이름은 Batch Gradient Descent이다.

여기서 Batch의 의미는 total training set을 의미한다.(보편적인 batch와는 다른 의미이지만 혼용해서 사용한다)

즉, 매 단계마다 모든 training set을 활용한다는 의미이며, 실제로 이 알고리즘에서 미분계수를 계산할 때, 모든 Training Set에 대하여 계산하고 있다. 모든 Data Set을 사용하지 않는 알고리즘도 존재한다.