Newton's Method

Newton’s Method

뉴턴법 (Newton’s Method) 이란?

•  Newton–Raphson Method (뉴턴-랩슨 방법) 이라고도 불리며, 함수의 1차 미분(Gradient)과 2차 미분(Hessian) 정보를 이용해 함수의 최솟값을 반복적으로 찾아가는 최적화 방법이다.

$$\underset{\mathbf{x}}{\min }f(\mathbf{x})$$

• Newton’s Method는 현재 위치 ${\mathbf{x}}_k$에서 함수를 2차 Taylor 근사(Quadratic Approximation) 한 뒤, 이 근사 함수의 최솟값으로 이동하며 목표 지점에 점진적으로 수렴해 나간다.

최적화 문제의 기본 조건

• 미분 가능한 함수 $f:{\mathbb{R}}^n\to \mathbb{R}$ 에서, $f(\mathbf{x})$가 최소가 되는 ${\mathbf{x}}^{\ast }$을 다음과 같이 표현한다.

$$x^{\ast }=\arg \underset{\mathbf{x}}{\min }f(\mathbf{x})$$

• 여기서 $f({\mathbf{x}}^{\ast })$는 최적해이고, 이때의 Gradient는 0이 된다.

$$\nabla f({\mathbf{x}}^{\ast })=0$$

• 따라서 Newton’s Method는 결국 다음을 만족하는 지점을 찾는 방법으로 볼 수 있다.

$$\nabla f(\mathbf{x})=0$$

---

Newton’s Method 알고리즘

• Gradient Descent는 현재 위치에서 1차 미분 정보인 Gradient (기울기)만 사용하지만, 뉴턴법에서는 2차 미분 정보인 Hessian(곡률)을 함께 사용한다.
• 따라서 기울기를 이용한 탐색 방향 + 곡률을 이용한 적절한 스텝 사이즈를 함께 고려하여 최적해에 가까워질수록 매우 빠르게 수렴하다.
• 뉴턴법은 현재 위치 ${\mathbf{x}}_k$에서 함수를 2차 테일러 근사(Quadratic Approximation) 한 뒤, 이 근사 함수의 최솟값으로 이동하여 목표 지점에 점진적으로 수렴해 나간다.

Taylor Series를 이용한 함수 근사

• 테일러 급수 (Taylor series)를 이용하여 목적 함수 $f(\mathbf{x})$를 2차 테일러 급수로 근사한다.
• 다변수 함수 $f(\mathbf{x})$를 ${\mathbf{x}}_k$ 근방에서 2차 테일러 급수로 전개하면 다음과 같다.

$$f(\mathbf{x})\approx f({\mathbf{x}}_k)+\nabla f({\mathbf{x}}_k{)}^T(\mathbf{x}-{\mathbf{x}}_k)+\frac{1}{2}(\mathbf{x}-{\mathbf{x}}_k{)}^T{\nabla }^{2}f({\mathbf{x}}_k)(\mathbf{x}-{\mathbf{x}}_k)$$

• $\nabla f({\mathbf{x}}_k)$ : ${\mathbf{x}}_k$ 위치에서의 기울기(Gradient) 벡터
• ${\nabla }^{2}f({\mathbf{x}}_k)$ : ${\mathbf{x}}_k$ 위치에서의 헤시안(Hessian) 행렬 ($=\mathbf{H}f({\mathbf{x}}_k)$)

2차 근사 함수의 최소값 찾기

• 2차 테일러 근사를 통해 얻은 2차 함수의 최소값을 찾기 위해, 근사 함수를 $\mathbf{x}$에 대해 미분하고 그 값은 $0$으로 둔다.

$${\nabla }_{\mathbf{x}}f(\mathbf{x})=0+\nabla f({\mathbf{x}}_k)+\mathbf{H}f({\mathbf{x}}_k)(\mathbf{x}-{\mathbf{x}}_k)$$ $$\nabla f({\mathbf{x}}_k)+\mathbf{H}f({\mathbf{x}}_k)(\mathbf{x}-{\mathbf{x}}_k)=0$$

다음 탐색 위치 계산

• 위 방정식을 $\mathbf{x}$에 대하여 정리하면, 근사 함수의 최솟값을 주는 $\mathbf{x}$ 값을 얻을 수 있다.

$$\mathbf{H}f({\mathbf{x}}_k)(\mathbf{x}-{\mathbf{x}}_k)=-\nabla f({\mathbf{x}}_k)$$ $$(\mathbf{x}-{\mathbf{x}}_k)=-{\mathbf{H}}^{-1}f({\mathbf{x}}_k)\nabla f({\mathbf{x}}_k)$$ $$\mathbf{x}={\mathbf{x}}_k-{\mathbf{H}}^{-1}f({\mathbf{x}}_k)\nabla f({\mathbf{x}}_k)$$

• 이 값이 다음 반복에서의 새로운 추정값 ${\mathbf{x}}_{k+1}$이 된다.
• 즉, 다음 탐색 위치로의 변화량은 $\mathbf{x}-{\mathbf{x}}_k=\Delta \mathbf{x}$이며, 다음 위치는 ${\mathbf{x}}_{k+1}={\mathbf{x}}_k+\Delta \mathbf{x}$로 표현가능하다.

$${\mathbf{x}}_{k+1}={\mathbf{x}}_k-{\mathbf{H}}^{-1}f({\mathbf{x}}_k)\nabla f({\mathbf{x}}_k)$$

• *2차 근사된 함수가 전체 목적 함수를 완벽히 대변하지 못하기 때문에 이 근사는 ${\mathbf{x}}_k$ 주변의 아주 작은 영역에서만 원래 함수 $f(\mathbf{x})$와 유사하다.
• 2차 근사 함수는 ${\mathbf{x}}_k$에 가장 잘 맞는 포물선 형태를 가지며, 이 근사 함수의 기울기가 0인 지점을 찾으면 그 지점은 원래 함수 $f(\mathbf{x})$의 실제 최소값에 더 가까워질 가능성이 있다.
• 이것이 뉴턴법의 핵심 업데이트 규칙이며, 이 과정을 반복하여 목적 함수의 최솟값에 수렴해 나간다.

수렴 여부 확인

• 뉴턴법은 반복적인 알고리즘이므로, 수렴했다고 판단할지를 결정하는 기준(Stopping Criteria) 이 필요하다.
• 뉴턴법의 수렴 여부를 판단하는 주요 방법들로 다음과 같은 조건들을 조합하여 사용한다.
• (파라미터 변화량 기준) 현재 반복에서 계산된 파라미터 값과 이전 파라미터 값 사이의 변화량이 충분히 작아졌을 때 수렴했다고 판단함.

$$||{\mathbf{x}}_{k+1}-{\mathbf{x}}_k||<{ϵ}_x$$

• (목적 함수 값 변화량 기준) 목적 함수의 값이 이전 박복과 비교하여 거의 변하지 않을 때 수렴했다고 판단함.

$$|f({\mathbf{x}}_{k+1})-f({\mathbf{x}}_k)|<{ϵ}_f$$

• (기울기 크기 기준) 기울기 벡터의 크기가 충분히 작아졌을 때 수렴했다고 판단함.

$$||\nabla f({\mathbf{x}}_k)||<{ϵ}_g$$

• (최대 반복 횟수) 위 조건들이 만족되지 않더라도 무한히 반복되는 것을 방지하기 위해 반복 횟수를 제한함.

$$k>\text{max iteration}$$

Newton’s Method 전체 알고리즘

• 따라서, Newton’s Method는 다음과 같은 순서로 동작한다.
• 초기값 ${\mathbf{x}}_0$을 설정하고, 각 interation 수를 $k$라고 할 때,
• (Step 1) Gradient 계산

$$\nabla f({\mathbf{x}}_k)$$

• (Step 2) Hessian 계산

$$\mathbf{H}f({\mathbf{x}}_k)={\nabla }^{2}f({\mathbf{x}}_k)$$

• (Step 3) Newton Equation 해결 (2차 근사함수 최솟값)

$$\nabla f({\mathbf{x}}_k)+\mathbf{H}f({\mathbf{x}}_k)(\mathbf{x}-{\mathbf{x}}_k)=0$$

• (Step 4) 변수 업데이트

$${\mathbf{x}}_{k+1}\leftarrow {\mathbf{x}}_k-{\mathbf{H}}^{-1}f({\mathbf{x}}_k)\nabla f({\mathbf{x}}_k)$$

• (Step 5) 수렴 여부 확인

---

Newton’s Method 예시

• 다음 함수 $f(x)$에 대해 뉴턴법을 이용한 최소값을 찾는 예시.

최적화 문제 정의

• 함수 $f(x)$는 다음과 같고, Global Minimum을 가진다.

$$f(x)=x^4-4x^2+x$$ $$\underset{x\in \mathbb{R}}{\min }f(x)$$

Gradient 계산

• 함수 $f(x)$는 일변수 함수이므로 Gradient가 1차 미분이다.

$$f^{\prime }(x)=4x^3-8x+1$$

• 즉 최적점에서는 $f^{\prime }(x)=0$ 이어야 하므로, 이것을 만족하는 $x$를 찾아야 한다.

Hessian 계산

• 일변수 함수에서 Hessian은 2차 미분이다.

$$f^{\prime \prime }(x)=12x^2-8$$

Newton Method 유도

• 다변수 함수에서 뉴턴법의 업데이트 공식은 앞서 정리한 것과 같이 다음과 같다.

$${\mathbf{x}}_{k+1}={\mathbf{x}}_k-{\mathbf{H}}^{-1}f({\mathbf{x}}_k)\nabla f({\mathbf{x}}_k)$$

• 여기서, 일변수 함수의 뉴턴법 업데이트 공식은 다음과 같이 정리된다.

$$x_{k+1}=x_k-\frac{f^{\prime }(x_k)}{f^{\prime \prime }(x_k)}$$

• 이 식을 이용해 현재 함수의 Gradient와 Hessian을 대입하면 다음과 같다.

$$x_{k+1}=x_k-\frac{4x^3-8x+1}{12x^2-8}$$

• 따라서 함수 $f(x)$의 Newton Update Rule을 나타낸다.

초기값 설정 및 업데이트

• 초기값 $x_0$를 $-2$로 설정하여 값을 업데이트하며, Local Minimum에 수렴해 나간다.
• Newton’s Method는 기본적으로 함수의 최솟값$(f^{\prime }(x)=0)$을 찾는 방법이며, Non-Convex Optimization에서 Global Minimum을 보장하지 않는다.

Iteration 1

$$x_0=-2,f^{\prime }(-2)=-15,f^{\prime \prime }(-2)=40$$ $$x_1=-1.625$$

Iteration 2

$$x_1=-1.625,f^{\prime }(-1.625)\approx -3.658,f^{\prime \prime }(-1.625)\approx 23.688$$ $$x_2\approx -1.47$$

Iteration 3 ~~

$$\begin{array}{rl}{x}_0=& -2.000\\ x_1=& -1.625\\ x_2\approx & -1.470\\ x_3\approx & -1.474\\ x_4\approx & -1.473\\ & ⋮\\ x^{\ast }\approx & -1.473\end{array}$$

---

Newton’s Method 정리

• 함수의 Hessian(곡률) 정보를 활용하여 최적해 방향으로 직접 이동하기 때문에 학습률(Learning rate) 튜닝이 필요없고, 목적 함수가 충분히 매끄럽고 초기 추정값이 최적해에 가깝다면 경사 하강법(Gradient Descent) 등의 방법보다 훨씬 빠르게 수렴한다.
• 뉴턴법은 이론적으로 매우 강력하고 빠른 수렴 속도를 제공하지만, Hessian Hessian 행렬 계산 및 역행렬 연산의 비용이 크기 때문에 고차원 문제(특히 딥러닝)에는 직접적으로 적용하기 어렵다.
• 이러한 단점들을 보완하기 위해 준-뉴턴법(Quasi-Newton Methods) 이나 확률적 준-뉴턴법(Stochastic Quasi-Newton Methods) 과 같이 헤시안 행렬을 근사하여 사용하는 방법들이 개발되었다.
• 뉴턴법은 가장 가까운 Local Minimum으로 수렴하기 때문에 이것이 Global Minimum이라는 보장은 없다.