이계도함수법: 뉴턴 메서드
정의1 2
목적함수 $J : \mathbb{R}^{n} \to \mathbb{R}$를 최적화하는 문제에서, 다음과 같은 반복 알고리즘을 뉴턴 메서드Newton’s method라 한다.
$$ \begin{equation} \mathbf{x}_{n+1} = \mathbf{x}_{n} - H^{-1}(\mathbf{x}_{n}) \nabla J(\mathbf{x}_{n}) \end{equation} $$
$\nabla J$는 그래디언트, $H$는 $J$의 헤시안이다.
유도
$J$를 2계도함수항까지 테일러 전개로 근사하면 다음과 같다.
$$ J(\mathbf{x}) \approx J(\mathbf{x}_{0}) + (\mathbf{x} - \mathbf{x}_{0})^{T} \nabla J (\mathbf{x}_{0}) + \dfrac{1}{2!}(\mathbf{x} - \mathbf{x}_{0})^{T} (H(\mathbf{x}_{0})) (\mathbf{x} - \mathbf{x}_{0}) $$
$J$를 최소로 만드는 $\mathbf{x}$를 찾기 위해 $\mathbf{x}$로 미분하면 (그래디언트와 헤시안의 변수는 생략하자)
$$ \dfrac{\partial J(\mathbf{x})}{\partial \mathbf{x}} = \nabla J + (\mathbf{x} - \mathbf{x}_{0}) H = \mathbf{0} $$ $$ \begin{equation} \implies \mathbf{x}^{\ast} = \mathbf{x}_{0} -H^{-1}\nabla J \end{equation} $$
설명
표준적인 경사하강법이 목적함수의 최적화를 위헤 1계도함수를 사용한다면, 뉴턴 메서드는 2계도함수까지 사용한다. 수식을 비교해보면 학습률 $\alpha$가 헤시안의 역행렬로 대체된 꼴이라 적응적 학습률이라고 볼 수 있다.
$$ \begin{align*} \text{Gradient Descent: } \mathbf{x}_{n+1} &= \mathbf{x}_{n} - \alpha \nabla J \\ \text{Newton’s Method: } \mathbf{x}_{n+1} &= \mathbf{x}_{n} - H^{-1} \nabla J \end{align*} $$
유도할 때 테일러 전개의 2차항까지 사용된 것에 주목하자. 만약 $J$가 (국소적으로) 2차함수라면 $(2)$는 (국소적으로) 최적해 $\mathbf{x}^{\ast}$를 한 번에 찾는 수식이다. 물론 일반적으로 그렇게 좋은 상황은 마주치기 힘드므로, $(1)$을 반복하여 $\mathbf{x}^{\ast}$를 찾아야한다.
역행렬의 계산이 포함된 만큼 실전에서 사용하기 유용한 알고리즘은 아니라는 짐작을 할 수 있을 것이다. 헤시안을 저장하는 자체만으로도 메모리를 많이 소요하고, $n \times n$ 행렬의 역행렬을 구하는 비용은 $\mathcal{O}(n^{3})$이라 $n$이 큰 경우엔 역행렬을 계산하는 시간에 그냥 경사하강법을 몇 번 더하는게 효율적일 수 있다. 특히 딥러닝에서 인공신경망이 강한 퍼포먼스를 내기 위해서는 수많은 파라매터가 필요한데, ChatGPT-3.5가 1,750억개의 파라매터를 가진 것을 생각해보면 뉴턴 메서드로 학습시키는 것을 기대하기는 힘들다. 헤시안의 높은 계산 비용을 극복하기 위한 여러 개선 알고리즘들이 고안되어왔다.
아래의 일변수일 때의 수식을 보면 root finding에서의 뉴턴 메서드와 같은꼴임이 눈에 잘 들어올 것이다.
$$ x_{n+1} = x_{n} - \dfrac{f^{\prime}(x_{n})}{f^{\prime \prime}(x_{n})} $$