[ML] Newton-Raphson Method

1. Newton-Raphson Method :  

Newton-Raphson Method

$f(x)=0$을 만족하는 root(근)인 $\hat{x}$를 찾는 방법 중 하나 : root-finding algorithm

 

위의 그림에서 보이듯이

• 1st order derivative(1차 도함수)를 이용하여
• 현재의 $x_t$로부터 $x_{t+1}$을 구해낸다.

---

이를 수식으로 표현하면 다음과 같다.

$$\begin{aligned}f^\prime(x_t)&=\dfrac{f(x_{t+1})-f(x_t)}{x_{t+1}-x_t}\\x_{t+1}-x_t&=\dfrac{f(x_{t+1})-f(x_t)}{f^\prime(x_t)}\\\quad\\x_{t+1}&=x_t+\dfrac{f(x_{t+1})-f(x_t)}{f^\prime(x_t)}\\&=x_t+\dfrac{0-f(x_t)}{f^\prime(x_t)}\\&=x_t-\dfrac{f(x_t)}{f^\prime(x_t)}\end{aligned}$$

---

update expression은 다음과 같음.

$$x_{t+1}=x_t-\dfrac{f(x_t)}{f^\prime(x_t)}$$

---

변수가 scalar인 경우의 $f(x)=0$의 근을 찾는 경우처럼 root-finding의 경우엔 Newton-Raphson Method라고 불리고,

$f(x)$의 extreme value(극값)을 구하기 위해 $\nabla f(x)=0$에 Newton-Raphson Method를 적용한 경우에는 Newton Method라고 불린다. 

---

2. Optimization for Loss Function : 

2-1. Optimization에서 Newton-Raphson Method => Newton Method : 

이를 Optimization에서 사용하는 경우,

최소값(or 최대값)에서 $f^\prime(\hat{x})=0$이므로

위의 Newton-Raphson Method의 식에서는 $f(x)$가 $f^\prime(x)$으로 대체된다

(기존의 경우, $f(x)=0$의 root를 찾는 것에서 $f^\prime(x)=0$에서의 root를 찾는 것이 된 것임.)

---

수식으로 보면 다음과 같음.

$$x_{t+1}=x_t-\dfrac{f^\prime(x_t)}{f^{\prime\prime}(x_t)}$$

---

같은 목적으로 사용되는

Steepest Gradient Decent (SGD) Method가 learning ratio ($\eta$)를 일종의 hyper-parameter(사용자가 정해주는 인자)로 남겨둔 것과 달리,

Newton-Raphson Method는 이를 업데이트식에서 $\eta=\dfrac{1}{f^{\prime\prime}(x_t)}$로 지정한 차이점이 있음.

---

참고: Newton Method vs. Newton-Raphson Method : 

즉, Newton-Raphson Method를 Optimization에 적용한 경우,

• $f^{\prime}(x)=0$ (or $\nabla f (\mathbf{x})=\mathbf{0}$) 에 대해 root-finding을 하는 것임.
• 이는 scalar function $f(\mathbf{x})$에서의 stationary point를 찾는 것임.
• 이를 Newton Method라고도 부름.

---

2-2. Steepest Gradient Decent Method (or Gradient Decent Method, GD) : 

$$x_{t+1}=x_t-\eta \nabla f(x_t) = x_t-\eta f^\prime(x_t)$$

where

• $\eta$ :
  • learning ratio,
  • 함수 $f(x)$를 최소화하는 gradient의 역방향으로 얼마나 갈지를 나타내는 step size를 조절.

---

3. Newton Method : 

Newton-Raphson Method를 optimization 을 풀기 위해 $\nabla f(\mathbf{x})$ 에 적용한 경우를 Newton Method라고 부름.

 

수식은 다음과 같음.

 

$$\begin{aligned} x_{t+1}&=x_t- \dfrac{1}{f^{\prime\prime}(x_t)} f^{\prime}(x_t) = x_t - \left[ f^{\prime\prime}(x_t)\right]^{-1}f^{\prime}(x_t) \\ \textbf{x}_{t+1} &=\textbf{x}_t - \mathbf{H}_f(\textbf{x}_t)^{-1}\nabla f(\textbf{x}_t)\end{aligned}$$

where

• $\nabla f(\textbf{x}_t)$: gradient (1st order derivative vector)
• $\textbf{H}_f(\textbf{x}_t)$: Hessian matrix (2nd order derivative matrix)

---

3-1. Newton-Raphson Method의 특징.

• 초기값을 어떻게 잡느냐에 따라, root를 찾을 수도 있고 아닐 수도 있음. 
  • 실제로 근처에서 시작할 경우는 확실히 GD보다 빠르지만,
  • 초기값이 root에서 멀리 놓인 경우, Newton-Raphson Method는 해를 못 찾는 경우가 많음. 
• Quasi-Newton method 들은 주로 2nd-order derivative( ~ Hessian)을 다른 지표로 대체하여 사용하는 경우가 많음.
  • 이들 대부분이 원래의 Newton-Raphson Method를 개선한 것으로
  • 대표적으로 BFGS 알고리즘 이 있음. (많은 경우, Limited Memory BFGS가 사용됨.)

---

참고: Newton-Raphson Method for Multi-Varaible Function

Multi-Variable Multi-Valued Function 은 입력과 출력이 모두 vector인 경우 (=연립방정식)로,

이같은 multi-variable function $\mathbf{f}(\mathbf{x})=\mathbf{0}$의 root를 찾기 위한

Newton-Raphson Method 는 다음과 같음.

$$ \mathbf{x}_{t+1} = \mathbf{x}_t - J_\textbf{f}({\mathbf{x}_t})^{-1} \mathbf{f}(\mathbf{x}_t) = \mathbf{x}_t - \frac{\mathbf{f}(\mathbf{x}_t)}{J_{\mathbf{x}_t}}$$

where,

$J_\textbf{f}(\mathbf{x}_t)$는 $\mathbf{f}(\mathbf{x}_t)$의 Jacobian matrix임.

사실 matrix를 분모로 놓는 건 수학적으로 부정확한 표현이나, 개념 이해를 위해 기재함.

 

$$J_\textbf{f}(\mathbf{x} = \begin{bmatrix} \frac{\partial f_1}{\partial x_1} & \frac{\partial f_1}{\partial x_2} &\cdots &\frac{\partial f_1}{\partial x_n} \\ \frac{\partial f_2}{\partial x_1} & \frac{\partial f_2}{\partial x_2} &\cdots &\frac{\partial f_2}{\partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial f_m}{\partial x_1} & \frac{\partial f_m}{\partial x_2} &\cdots & \frac{\partial f_m}{\partial x_n} \end{bmatrix}$$

• 각 row는 output function $f_i$의 gradient의 transpose임.
• 각 column은 input variable $x_j$에 대한 partial derivative.

Newton-Raphson Method는 root-finding method임.

• 적용대상 함수가 $\mathbf{f}: \mathbb{R}^n \to \mathbb{R}^n$인 경우로 $\mathbf{f}(\mathbf{x})=\mathbf{0}$의 root-finding.
• 우연히 optimization에 쓰이는 Newton Method와 같이 multivariable function에 적용되었지만 엄밀히는 Newton-Raphson Method임.
• Newton Method는 optimization을 위해 $f(\mathbf{x})$의 extreme value에서의 $\mathbf{x}$를 구하기 위해, $\nabla f(\mathbf{x})=\mathbf{0}$에 대해 Newton-Raphson Method를 적용한 경우임.

---

4. Gauss-Newton Method

Newton-Raphson Method를 연립방정식으로 확장한 경우와 유사해보이지만 
Gauss-Newton Method 는 다음과 같은 residual을 최소화하는 비선형 최소제곱 문제를 해결하는데 주로 사용되며

$$\underset{\mathbf{\beta}}{\text{min}} \sum^m_{i=1} [r_i(\mathbf{\beta})]^2$$

 

수식은 다음과 같음 (여기서 $\mathbf{f}(\mathbf{x})=\mathbf{r}(\mathbf{\beta})$).

$$\textbf{x}_{t+1}=\textbf{x}_{t}-(J_\mathbf{f}(\textbf{x}_t)^\top J_\mathbf{f}(\textbf{x}_t)^{-1} J_\mathbf{f}(\textbf{x}_t)^\top \textbf{f}(\textbf{x}_t)$$

where

• $\textbf{x}$ : variable vector, $\textbf{x}=(x_1, \dots, x_n)^\top$ (column vector기준)
  • residual을 최소제곱으로 푸는 문제에서는 $\mathbf{\beta}$로 표기되면 구하고자 하는 parameter를 가르킴.
  • 이 경우 $x_i$는 residual $r_i$에 해당하는 측정 데이터 포인트로 많이 사용됨.
  • 이 문서에서는 parameter vector를 $\mathbf{\beta}$가 아닌 $\mathbf{x}$로 기재하여 표기함 (앞서의 경우와 일관성을 위해)
• $\textbf{f}(\textbf{x})$ : function vector, $\textbf{f} = (f_1, \dots, f_m)^\top$. 벡터의 각 요소는  $f_i(\textbf{x})=f_i(x_1, \cdots, x_n)=0$으로 연립방정식을 이루는 방정식 하나임. 
• $m$ : 연립방정식에서 식의 수.
• $n$ : 연립방정식에서 변수(or 미지수, 파라메터)의 수.
• $J_\mathbf{f}(\textbf{x}_t)$ : Jacobian matrix로 1st order derivative 또는 gradient에 해당. (vector-vector 함수인 경우 1차 미분이 matrix임) 
  • loss function이 제곱이 되어 있기 때문에 Newton Method of Optimzation 과 달리 Hessian을 구하지 않고도
  • Jacobian만으로 처리가 가능하기 때문에 Newton Method 보다 효율적임.

---

참고자료

2022.05.07 - [.../Math] - [Math] Jacobian : Summary

[Math] Jacobian : Summary

https://convex-optimization-for-all.github.io/contents/chapter18/2021/03/23/18_07_Limited_Memory_BFGS_(LBFGS)/ 

18-07 Limited Memory BFGS (LBFGS) · 모두를 위한 컨벡스 최적화

---