4.4. Gradient Method

Files: https://strutive07.github.io/assets/images/4_4_Gradient_Method/IE661-Week_4-Part_2-icmoon-ver-1.pdf last update datetime: Jan 16, 2020 11:50 PM

Gradient Descent / Ascent

특정 fuction f(x), x1 이라는 위치가 있다고 가정해보자. 이 함수를 gradient desccent를 사용하여 optimize하려면 어떻게 해야할까?

간단히 생각하면, f(x) 값을 낮게 바꾸면 될것이다. 그럼 이걸 어떻게?

미분해서 목표하는 방향을 찾고, 해당 방향으로 이동하면된다.

자 이걸 진행해보자.

$$f(x) = f(a) + \cfrac{f'(a)}{1!}(x-a) + O((x-a)^2)$$

함수를 테일러 급수 형태로 변환해서 나타내었다.

a = x1 이라고 하고, x = x1 + hu 라고 한다면, u 가 가장 중요하다. 여기서 h 는 속력, u는 unit direction vector이다.

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

h를 매우 작은 숫자로 가정한다면, h^2 를 무시할 수 있는 수준으로 가정할 수 있을것이다. 따라서 아래 식 처럼 변환할 수 있다.

다시 말하면, 속력을 매우 작게 가정하고, 많은 step으로 u라는 방향으로 나아가면서 optimize 하겠다라는것이다.

$$f(x_1 + hu) - f(x_1) \approx hf'(x_1)u$$

Gradient descent에서는 속력과 방향을 따라 이동하였을때, 기존 위치와 차이가 가장 작게 움직여야한다.

$$u' = argmin_u(f(x_1+hu) - f(x_1))$$

이 식을 위에서 유도했던식으로 변환해보자.

$$u' = argmin_u(hf'(x)u) = -\cfrac{f'(x_1)}{|f'(x_1)|}$$

u 는 유닛벡터이기 때문에, 절댓값을 사용하여 유닛벡터로 만들어준다.

그리고 방향이 f’(x) 와 반대방향인 이유는, f’(x) 내적 u 를 하게 되면, 극대값으로 가게 된다. why? 내적의 공식에서 cosine 값이 가장 작아지는 값 두 각이 반대방향일 때 이기 때문이다.

gradient descent를 하기 위해서는 결국 f’(x_1) 의 반대방향으로 이동하면 된다.

gradient ascent 를 원한다면 같은 방향으로 이동하면된다.

$$u' = argmin_u(f(x_1+hu) - f(x_1)) = argmin_u(hf'(x)u) = -\cfrac{f'(x_1)}{|f'(x_1)|}$$

x_1 이후의 x_2 는 아래와같이 정리될 수 있다.

$$x_{t+1} = x_t + hu' = x_t - h \cfrac{f'(x)}{|f'(x)|}$$