$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)}\\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에서 사용되는 경우, 최소값(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 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가 사용됨.)
Gauss-Newton Method
Newton-Raphson Method를 연립방정식으로 확장한 경우는 Gauss-Newton Method라 불리며 다음과 같음.
$$\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기준)
- $\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임)
참고자료
2022.05.07 - [.../Math] - [Math] Jacobian : Summary
'Computer > ETC' 카테고리의 다른 글
Round-off Error vs. Truncation Error (0) | 2022.09.22 |
---|---|
Boltzmann’s Factor (or Boltzmann’s Distribution) (0) | 2022.06.09 |
[ML] From softmax to logistic function. (0) | 2022.06.06 |
[linux] 명령어 : linux 배포판 및 버전 등을 확인하기 (0) | 2022.05.18 |
HWiNFO : PC의 HW 사양 정보 확인 SW (0) | 2022.03.10 |