뉴턴 방법

뉴턴 방법

뉴턴 방법(Newton's Method)은 함수를 이차 근사하여 최적점을 반복적으로 구하는 최적화 알고리즘이다. 경사 하강법보다 훨씬 빠르게 수렴하지만 헤시안 행렬의 역행렬 계산이 필요하다.

핵심

• 이차 수렴(quadratic convergence) 특성으로 경사 하강법보다 적은 반복으로 수렴한다
• 매 스텝에서 헤시안(Hessian) 행렬 \(H\)를 계산하고 역행렬을 구해야 한다
• 업데이트 규칙: \(\theta \leftarrow \theta - H^{-1}\nabla_\theta \ell(\theta)\)
• 매개변수 수가 많으면 헤시안 역행렬 계산이 \(O(n^3)\)으로 매우 비싸다
• 로지스틱 회귀처럼 매개변수가 적은 모델에서 효과적이다

수식

\[\theta^{(t+1)} = \theta^{(t)} - H^{-1}\nabla_\theta \ell(\theta^{(t)})\]

\[H_{jk} = \frac{\partial^2 \ell}{\partial \theta_j \partial \theta_k}\]