뉴턴 방법, 준 뉴턴 방법

최대경사법(steepest Gradient Descent)는 벡터가 최저점을 가리키고 있지 않은 경우에 진동 현상이 발생한다.

이런 진동현상을 없애는 방법으로 2차 도함수(헤시안 행렬)을 이용하는 방법이나 모멘텀 방법이 있다.

 

일반적인 경우에는 2차 도함수를 사용하고, 2차 도함수(헤시안 행렬)를 계산하기 어려운 인공신경망 등에서는 모멘텀 방법을 많이 사용한다. <모멘텀 방법의 설명은 생략>

https://datascienceschool.net/view-notebook/4642b9f187784444b8f3a8309c583007/

헤시안 행렬을 이용해서 최저점을 찾는 방법에 대해서 알아보자.

 

2차 도함수를 사용한 뉴턴 방법

 

뉴턴함수는 gradient와 다르게 미분 값만을 이용하여 optimizer를 시키는 것이 아니다. 미분 값과 미분 값에 대한 정보 즉, 2차 도함수를 사용해 최적화를 시킨다.

스텝 사이즈는 hyperparameter가 아니라, 뉴턴 함수가 알아서 최적의 스텝 사이즈를 찾는데 최적의 스텝 사이즈가 바로 2차 도함수 값이다.

그렇다면, 어떻게 최적의 스텝으로 최적 값을 찾는지 유도해보겠다.

 

공식

${x}_{n+1} = {x}_n - \dfrac{f'(x_n)}{f''(x_n)}$

 

위의 식으로 최저점을 유도해보자.$f'(x) = 2ax - 2ax_0$
$f''(x)=2a$ 를 위의 공식에 적용하면
${x}_{n+1} = {x}_n - \dfrac{2ax_n - 2ax_0}{2a} = x_n - (x_n - x_0) = x_0$
가 된다.
즉, 어떤 점$(x_n)$에서 출발해도 최저점 $x_0$로 도달할 수 있다.

 

뉴턴방법은 목적함수가 2차 함수일 때 한 번의 스텝으로 바로 최적점을 찾을 수 있어 엄청난 성능을 자랑한다.

또, 2차 함수가 아니더라도 기울기뿐 아니라 기울기의 정보도 사용하기 때문에 인장점에 대해 영향을 크게 받지 않아 gradient descent보다는 훨씬 빠르게 수렴한다.

 

하지만, 뉴턴 방법은 계산이 복잡하다는 단점이 있다. 2차 도함수이므로 헤시안 행렬을 계산해야 하는데, 헤시안의 연산자 체도 매우 복잡하고 공간 역시 크게 필요하기 때문에 neural network에서는 사용하지 않는다

 

준 뉴턴 방법

 

뉴턴 방법은 목적함수가 2차 함수와 비슷한 모양을 가질 때 빠르게 수렴할 수 있지만 헤시안 행렬로 인해 연산이나 메모리가 복잡하다는 단점이 있다. 또, 함수의 모양에 따라 잘 수렴하지 않을 수 있다.

이런 단점들을 준 뉴턴 방법이 보완했는데, 헤시안 행렬 대신 $x_n$점의 주변에서 2차 도함수의 근삿값을 구해 계산한다.

준 뉴턴 방법 중에서 BFGS(Broyden–Fletcher–Goldfarb–Shanno) 방법이 많이 사용된다.

 

 

일반 적으로 SGD를 많이 사용하지만 더 빠른 수렴 속도가 필요하다면 line search, steepest method, newton's method를 고려해볼 만하다.