---
disqus: ierosodin
---

# Newton method

> Organization contact [name= [ierosodin]([e-mail])]
###### tags: `machine learning` `學習筆記`

==[Back to Catalog](https://hackmd.io/@ierosodin/Machine_Learning)==

一種求根的方法，利用方程是在某一點一次微分的值極為其切線斜率，推得：
${x_{i+1}\ =\ x_i\ -\ \frac{f(x_i)}{f'(x_i)}}$


## Newton method in optimization

在推導前，必須要先認識泰勒展開式，以及為何使用泰勒展開式來做估計會是合理的。

### Talor

對一個函式 ${f(x)}$ 在 ${x_0}$ 做展開，我們這裡先定義成：
${\begin{split}
f(x)\ &=\ f(x_0)\ + f'(x_0)(x-x_0)\ +\ \frac{1}{2!}f''(x_0)(x-x_0)^2\ +\ ... \\
&=\ \sum_n \frac{f^{(n)}(x_0)}{n!}(x-x_0)^n
\end{split}}$

### 常用的級數

${e^x\ =\ 1\ +\ x\ +\ \frac{1}{2}x^2\ + \frac{1}{3!}x^3\ +\ ...\ =\ \sum_n \frac{x^n}{n!}\ (at\ x_0\ =\ 0)}$

${sinx\ =\ x\ -\ \frac{1}{3!}x^3\ +\ \frac{1}{5!}x^5\ -\ ...}$

${cosx\ =\ 1\ -\ \frac{1}{2}x^2\ +\ \frac{1}{4!}x^4\ -\ ...}$

${\begin{split}
e^{ix}\ &=\ 1\ +\ ix\ +\ \frac{1}{2}(-1)x^2\ +\ \frac{1}{3!}(-i)x^3\ +\ ... \\
&=\ (1\ -\ \frac{1}{2}x^2\ +\ \frac{1}{4!}x^4\ -\ ...)\ +\ i(x\ -\ \frac{1}{3!}x^3\ +\ \frac{1}{5!}x^5)\ -\ ... \\
&=\ cosx\ +\ isinx
\end{split}}$

### 行為分析

泰勒展開式有許多的證明與應用，這裡提一個簡單的想法，來說明稍後為何我們要用 Talor 來做簡化與估計，從展開式中我們可以發現，對 ${x_0}$ 展開後，對其做 $i$ 次微分：
${f^{(i)}(x_0)\ =\ 0\ +\ ...\ +\ 0\ +\ f^{(i)}(x_0)\ +\ 0\ +\ ...\ +\ 0}$

也就是原函式與展開式在微分的行為是一樣的。

### Newton method in optimization

從剛剛行為的分析我們可以知道，原函式與展開式在微分的行為是一樣的，因此若我們想找一個高次函式的最低點，可以先透過找到通過 ${x_0}$ 的二次泰勒展開式的最低值，一步一步做逼近。

從數學式子來看：
${\begin{split}
f(x_0)\ &=\ f(x_0\ +\ dx)\ =\ f(x_0)\ +\ f'(x_0\ +\ dx)(x_0\ +\ dx\ -\ x_0)\ +\ \frac{1}{2}f''(x_0)(x_0\ +\ dx\ -x_0)^2\ +\ ... \\
&=\ f(x_0)\ +\ f'(x)dx\ +\ \frac{1}{2}f''(x_0)(dx)^2
\end{split}}$

其中，${dx}$ 是從 ${x_0}$ 抵達最低點的一小段位移量。
微分可得，${f'(x_0)\ +\ f''(x_0)dx\ =\ 0 \\
\Rightarrow\ dx\ =\ \frac{-f'(x_0)}{f''(x_0)}}$

推廣到高維空間：
${x_{i+1}\ =\ x_i\ -\ Hf(x_0)^{-1}\nabla f(x_0)}$

其中，${Hession\ function\ of\ f(x)}$
${Hf(x)\ =\ {\left[
\begin{array}{ccc}
\frac{\partial^2f}{\partial x_0^2} & \frac{\partial^2f}{\partial x_0x_1} & ... \\
\frac{\partial^2f}{\partial x_1x_0} & \frac{\partial^2f}{\partial x_1^2} & ... \\
... & ... & ... \\
\end{array}
\right]}}$

從幾何的角度極為，將經過 ${x_0}$ 的高次項多項式簡化為二次多項式，求得此方程式的極值，再迭代將經過此極值之高次項多項式簡化為二次多項式，以此類推，慢慢逼近最小值。


### LSE

我們可以利用牛頓法來驗證 LSE：
${LSE\ =\ ||A\vec{x}\ -\ \vec{b}||^2\ =\ x^TA^TA\vec{x}\ -\ 2x^TA^T\vec{b}\ +\ \vec{b}^T\vec{b}}$
${\nabla\ =\ 2A^TA\vec{x}\ -\ 2A^T\vec{b}}$
${H\ =\ 2A^TA}$

${\begin{split}
\vec{x_1}\ &=\ \vec{x_0}\ -\ (2A^TA)^{-1}(2A^TA\vec{x_0}\ -\ 2A^T\vec{b}) \\
&=\ (A^TA)^{-1}A^T\vec{b}
\end{split}}$

可以發現，經過一次迭代，即得到 LSE 的最小值，這是因為 LSE 本身即為二次多項式，因此迭代一次的最小值就是整體的最小值。

### 缺點

1. 當維度越來越高時，hession function 計算所耗費的時間是 ${O(n^3)}$
2. 可能會掉進 locel optimization，且並不能保證找到 globel 的最小值