[ML] Newton-Raphson Method

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)}$$

---

Optimization for Loss Function

Optimization에서 Newton-Raphson 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)}$로 지정한 차이점이 있음.

---

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를 조절.

---

Newton-Raphson Method (or Newton Method)

$$x_{t+1}=x_t- \dfrac{1}{f^{\prime\prime}(x_t)} \nabla f(x_t)=x_t - \left[ f^{\prime\prime}(x_t) \right]^{-1} f^\prime(x_t)$$

---

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 Method (or Newton-Raphson Method)는 다음과 같음.

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

 

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

$$J_{\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}$$

---

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_{\textbf{x}_t}^TJ_{\textbf{x}_t})^{-1}J_{\textbf{x}_t}^T\textbf{f}(\textbf{x}_t)$$

where

• $\textbf{x}$ : variable vector, $\textbf{x}=(x_1, \dots, x_n)^T$ (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)^T$. 벡터의 각 요소는  $f_i(\textbf{x})=f_i(x_1, \cdots, x_n)=0$으로 연립방정식을 이루는 방정식 하나임. 
• $m$ : 연립방정식에서 식의 수.
• $n$ : 연립방정식에서 변수(or 미지수, 파라메터)의 수.
• $J_{\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) · 모두를 위한 컨벡스 최적화

---