[기계학습 4강] Gradient Method

※이 내용들은 edwith(KAIST Open Online Course)의 인공지능 및 기계학습 개론 1 Chap. 4강 내용을 기반으로 재구성하였음을 먼저 밝힙니다.※

 

저번 시간에 이어 Logistic Regression을 최적화하는 $\hat{\theta}$는 closed form solution이 아니라 open form solution이었다. 이를 approximate하게 구하기 위해서는 Gradient Descent Algorithm을 통해 해결해야 한다. 

 

 

Gradient Descent Algorithm에서 가장 접근하기 쉬운 것이 Taylor Expansion이다. 테일러 급수는 어떤 점에서 무한 번 미분가능한 함수를 그 점에서 미분계수 값으로 계산할 수 있는 무한급수로 표현된 함수로 나타내는 것이다.

 

Taylor Expansion

---

$f(x) = f(a) + \frac{f'(a)}{1!}(x - a)^n + \frac{f''(a)}{2!}(x-a)^2 + \cdots$
$= \sum_{n=0}^{\infty} \frac{f^{(n)}(a)}{n!}(x-a)^n$

 

Taylor Expansion의 예로$e^x$에 대해 a=0 일 때를 살펴보자.

 

$e^x = \frac{f^{(0)}(0)}{0!} + \frac{e^0}{1!}(x-0)^1 + \frac{e^0}{2!}(x-0)^2 + \cdots$ 뒤에 무한대까지 덧셈을 진행해주지 않더라도 근사하게 함수를 그릴 수 있는데 위의 식에 대하여 n=2, n=4일 때를 살펴보면

 

확인할 수 있다.

 

 

이제 앞서 말한 gradient descent/ascent를 살펴보자.

 

 

Gradient Descent/Ascent

---

 gradient descent/ascent는

 

• 구별가능한 함수 f(x)와 이 함수의 초기 파라미터 $x_1$이 주어졌을 때
• $x_1$이라는 점을 크거나 작게 움직이며
• 얼마만큼의 속력과 방향으로 나아갈 것인지를 결정하며 나아간다. (중요한 것은 방향이 중요하다.)

 

$f(x) = f(a) + \frac{f'(a)}{1!}(x-a) + O(\left \| x-a \right \|^2)$

 

위와 같은 특징을 지니며 위의 식과 같이 나타나는데 a에서의 접선의 방정식과 big-oh notation을 더해준 것과 같다. 여기서 big-oh notation의 의미는 간단하게 표현하자면 뒤에 나오는 무한대의 식들을 다 합친 값도 제약을 시켜서 무시하기 위해 쓰인 것이다. a를 $x_1$로 $x = x_1 + hu$로 가정해보자. 여기서 x의 의미는 $x_1$이라는 시작점에서 u라는 방향으로 h라는 속력만큼 움직이겠다는 의미이다. 그렇다면 u라는 방향을 어떻게 잘 정할 수 있을까? 아래의 식을 전개해보자.

 

$f(x_1 + hu) = f(x_1) + hf'(x_1)u + h^2O(1)$

$f(x_1 + hu = f(x_1) \approx hf'(x_1)u$, 단 h의 크기가 매우 작을 때 가능

 

여기서 descent의 경우 우리는 위의 식을 최소화하는 u의 방향을 구하고 싶다. 이를 식으로 나타내보고 위의 식을 적용해보면

 

$u^* = argmin_u \left \{ f(x_1 + hu) - f(x_1) \right \} = argmin_u hf'(x_1)u = -\frac{f'(x_1}{|f'{x_1}|$

 

와 같이 된다. 

 

 

위와 같이 나타낼 수 있는 이유는

 

$f(x_1 + hu) \leq f(x_1) , \vec{a} \cdot \vec{b} = |\vec{a}||\vec{b}| cos\alpha$

 

가 되기 때문이다.

 

 

u의 방향이 정해졌으므로 다음 값의 파라미터를 업데이트하는 것은 다음과 같아진다.

 

$x_{t+1} \leftarrow x_t + h u^* = x_t - h\frac{f'(x_1)}{|f'(x_1)|}$

 

 

 

 

 

ascent의 경우 descent의 반대가 되므로 결론적으로 다음과 같다.

 

• descent의 경우 최소화하는 u의 방향은 $f'(x_1)$을 $f'(x_1)$의 크기만큼 나눠주고 부호를 음으로 바꿔준 것이 되고
• ascent의 경우 최대화하는 u의 방향은 $f'(x_1)$을 $f'(x_1)$의 크기만큼 나눠주고 부호를 양으로 바꿔준 것이 된다.

 

 

 

-히비스서커스-