[최적화] Gradient를 계산하는 방법

 

 

최적화 방법을 보면 gradient 정보를 사용하는 경우가 많다. 실제 최적화 알고리즘을 구현하고자 할 때 의문인 것이 바로 이 gradient를 어떻게 구하냐는 질문이다.

 

대표적

최적화 방법을 보면 gradient 정보를 사용하는 경우가 많다. 실제 최적화 알고리즘을 구현하고자 할 때 의문인 것이 바로 이 gradient를 어떻게 구하냐는 질문이다.

 

 

그 방법으로는

0. By hand
1. Finite-difference method
2. Auto-differentiation
3. Complex step method

 

다음과 같이 설명할 수 있다.

 

0. By hand

만약 목적함수가 파라미터에 대해 간단하게 표현되어있다면 사전에 gradient를 계산해서 결과 값만 대입하면 쉽게 구할 수 있다.

 

1. Finite-difference method

대부분의 최적화 알고리즘에서 사용하는 방식이다. 함수값에 작은 $h$값의 perturbation을 통해 근사적으로 미분값을 구한다.

 

$$\frac{d f}{d x}=\frac{f(x+h)-f(x)}{h}+\mathcal{O}(h)$$

다음과 같이 forward different method를 적용할 수도 있고 더 효율적인 정확도를 위해 central difference method를 쓸 수도 있다.

$$\frac{d f}{d x}=\frac{f(x+h)-f(x-h)}{2h}+\mathcal{O}(h^2)$$

 

 

이렇게 근사하는 경우에는 두 가지 에러가 존재하게 된다.

 

- Truncation error : 위에서 보인 것과 같이 $\mathcal{O}(h)$ 텀으로 인한 에러.

- Subtractive cancellation error : floating point 계산으로 인해 발생하는 에러. $f(x+h)$와 $f(x)$의 값이 거의 비슷하기 때문에 발생하는 에러다.

 

 

2. Automatic differentiation

많은 인공지능 방법에서 gradient를 계산할 때 사용하는 방법이다. 거쳐온 모든 연산에 대해 gradient를 계산한 다음 (symbolic rule 사용) chain rule를 적용하여 구하는 방식이다.

 

참고 내용:

https://www.mathworks.com/help/optim/ug/autodiff-background.html

Automatic Differentiation Background

 

 

3. Complax-step method

finite difference와 유사하지만 subtractive cancellation이 존재하지 않는 방법이다. 따라서 $h$를 매우 작게 잡아도 문제가 되지 않는다.

 

$f(x + i h)$의 taylor expansion을 생각해보자. ($i = \sqrt{-1}$)

$h$이 작은 경우,

\[ f(x + i h) = f(x) + i h \frac{df}{dx} - h^2 \frac{d^2 f}{dx^2} + \mathcal{O}(h^3). \]

 

\[ \frac{df}{dx} \approx \frac{\operatorname{Im} \{f(x + i h)\}}{h} + \mathcal{O}(h^2). \]

 

그러나 이 방법도 단점은 존재한다. source code에서 complex variable을 쓸 수 있어야하고 computational cost가 디자인 변수의 수에 따라 증가한다. 또한 complax number을 사용하면 일반적인 경우보다 더 느려진다.