Gradient descent

1. Definition

비용함수 $J(\theta)$를 최소화하는 $\theta$를 구하기 위한 알고리즘.

 

Outline은 다음과 같다.

① 임의의 $\theta_{0}$, $\theta_{1}$을 설정한다(보통 0).

② $J(\theta)$를 줄이는 쪽으로 $\theta_{0}$, $\theta_{1}$값을 계속 바꾼다.

③ 기대하는 최소값에 도달할 때까지 이를 반복한다.

 

pseudocode로 표현하면 다음과 같다.

 

Repeat until convergence {

    $\theta_{j} \leftarrow \theta_{j} - \alpha\frac{\partial}{\partial\theta_{j}}J(\theta_{0}, \theta_{1})$ (for j = 0, 1)
}

$\leftarrow$는 우변에서 좌변으로의 대입을 뜻한다.

 

주의할 점은 $\theta_{0}$와 $\theta_{1}$을 동시에 update해야 한다는 것이다.

즉 다음은 틀리고,

$tmp0 \leftarrow \theta_{0} - \alpha\frac{\partial}{\partial\theta_{0}}J(\theta_{0}, \theta_{1})$

$\theta_{0} \leftarrow tmp0$

$tmp1 \leftarrow \theta_{0} - \alpha\frac{\partial}{\partial\theta_{1}}J(\theta_{0}, \theta_{1})$

$\theta_{1} \leftarrow tmp1$

 

다음은 맞다.

$tmp0 \leftarrow \theta_{0} - \alpha\frac{\partial}{\partial\theta_{0}}J(\theta_{0}, \theta_{1})$

$tmp1 \leftarrow \theta_{0} - \alpha\frac{\partial}{\partial\theta_{1}}J(\theta_{0}, \theta_{1})$

$\theta_{0} \leftarrow tmp0$

$\theta_{1} \leftarrow tmp1$

 

* 왜 미분계수를 빼는가?

미분계수는 순간변화율, 접선의 기울기의 두 가지 의미를 갖는다.

 

1) 순간변화율

Gradient descent는 $J(\theta)$가 수렴할 때까지 반복해서 $\theta_{0}$, $\theta_{1}$의 값을 바꾸는 알고리즘이다.

위의 식에서 $J(\theta)$가 수렴하려면 미분계수가 0이어야 하는데, 미분계수가 0이라는 것은 $J(\theta)$가 순간변화율이 0인 상태, 즉 수렴 상태임 의미한다. 

 

2) 접선의 기울기

점 a에서 시작한다고 하자. 현재 접선의 기울기는 그래프에서 알 수 있듯이 음수다.

따라서 $\theta_{0}$의 값은 증가한다.

 

 

이제 점 b에 위치하게 된다. 점 b에서의 접선의 기울기 역시 음수이므로 $\theta_{0}$의 값은 증가한다.

 

 

 

이제 점 c에 위치하게 된다. 역시 접선의 기울기가 음수이므로 $\theta_{0}$의 값은 증가한다.

 

 

이제 접선의 기울기가 0이 됐다. 접선의 기울기가 0이므로 $\theta_{0}$의 값은 불변한다.

$\theta_{1}$에 대해서도 같은 과정을 거쳐 접선의 기울기가 0이 되면 $J(\theta)$는 수렴하게 된다.

 

 

2. Formula

식을 다시 한 번 살펴보자.

$\theta_{j} \leftarrow \theta_{j} - \alpha\frac{\partial}{\partial\theta_{j}}J(\theta_{0}, \theta_{1})$

 

기호 $\partial$은 편미분을 의미한다. 그리고$\alpha$는 learning rate를 의미하며 양수의 값만 갖는다.

 

이 때 $\alpha$에 적당한 값을 설정해주는 것이 중요한데, 이유는 다음과 같다.

 

1. $\alpha$가 너무 작은 경우

$\theta$를 변화시켜 극값에 도달할 수는 있으나 변화폭이 너무 작아 극값에 도달하기까지 더 많은 단계를 거치게 된다.

때문에 시간이 오래 걸리게 된다.

 

 

2. $\theta$가 너무 큰 경우

$\theta$의 변화폭이 너무 커 극값에 수렴하지 않거나 발산할 수 있다.

 

 

 

3. Local optima

parameter가 이미 local optima에 있다면 미분계수가 0이 되므로 gradient descent는 parameter에 아무 영향이 없다.

따라서 local optima로 유지된다.

 

 

* gradient descent를 실행하는 도중에 learning rate 값을 바꿔야 할까?

local optima에 가까워짐에 따라 gradient descent의 변화폭은 작아진다. 따라서 learning rate를 감소시킬 필요가 없다.

 

 

4. Batch gradient descent

- 집단 기울기 하강: Gradient descent의 매 단계에서 training example 전체를 사용한다.