機器學習筆記(一) - LSE 、牛頓法

前言

機器學習是從 模型識別(pattern recognition) 以及 計算學習原理(computational learning theory) 所衍生出來的學科，其主要目標為藉由提供的資料來達到特定的目的。目前已廣泛應用於資料探勘、電腦視覺、自然語言處理、生物特徵識別、搜尋引擎、醫學診斷、檢測信用卡欺詐、證券市場分析、DNA序列測序、語音和手寫識別、戰略遊戲和機器人等領域。依照有無資料標籤（Label）可以分為 監督式學習（Supervised Learning）以及 非監督式學習（Unsupervised Learning）。

• 監督式學習（Supervised Learning）: 在訓練的過程中告訴機器答案、也就是「有標籤」的資料，比如給機器各看了 1000 張蘋果和橘子的照片後、詢問機器新的一張照片中是蘋果還是橘子。
• 非監督式學習（Unsupervised Learning）: 訓練資料沒有標準答案、不需要事先以人力輸入標籤，故機器在學習時並不知道其分類結果是否正確。訓練時僅須對機器提供輸入範例，它會自動從這些範例中找出潛在的規則。

簡單來說，若輸入資料有標籤，即為監督式學習；資料沒標籤，讓機器自行摸索出資料規律的則為非監督式學習，如 集群（Clustering）演算法。

非監督式學習本身沒有 標籤（Label）的特點，使其難以得到如監督式一樣近乎完美的結果。就像兩個學生一起準備考試，一個人做的練習題都有答案（有標籤）、另一個人的練習題則都沒有答案，想當然爾正式考試時，第一個學生容易考的比第二個人好。另外一個問題在於不知道 特徵（Feature）的重要性，在資料量較少的情況下，可能無法歸納出對預期結果佔有較大權重的 特徵（Feature）。

監督式學習（Supervised Learning）

一般在學習機器學習時，會先從 監督式學習（Supervised Learning）開始。給定資料對 $(x, y)$，$x$為輸入資料、$y$為預期結果，我們可以假設 $y=f(x)$，亦即 $y$ 和 $x$ 是有相關性的，此假設也可以推廣：

$$\begin{array}{ll} 假設輸入\ m\ 個特徵（Feature），分別為\ x_{1}\ ,\ x_{2}\ ,\ x_{3}\ ,\ \cdots\ ,\ x_{m} &\quad\quad\quad(m \in \mathbb{Z}^{+}) \\ 輸出\ k\ 個結果，分別為\ y_{1}\ ,\ y_{2}\ ,\ y_{3}\ ,\ \cdots\ ,\ y_{k} &\quad\quad\quad(k \in \mathbb{N}) \\ 可推得：y_{i}=f_{1}(x_{1})+f_{2}(x_{2})+f_{3}(x_{3})+\cdots+f_{m}(x_{m}) &\quad\quad\quad(\forall i \in \mathbb{N} \land i \le k) \end{array}$$

想像我們要做一個與房市相關的預測，則 $x_{1}$ 可能是某建案大樓所在地區、$x_{2}$ 可能是該大樓每戶的坪數、$x_{3}$ 可能是該大樓的公設比等等；而 $y_{1}$ 可能是每戶的價格、$y_{2}$ 可能是該大樓的空屋率等等。

如果用函數圖形來表示的話，為了繪圖方便，我們暫且假設 $(x,y)$ 構成一個 $\mathbb{R}^{2}$ 空間，其中 x 軸代表 input_x 的值， y 軸代表 expected_output_y 的值：

假設圖中兩個點為輸入資料，由 拉格朗日插值多項式(Lagrange polynomial) 可得到通過兩點的直線。另外一種求法可以假設 $y=ax+b$ (因為要通過 $n$ 個點的多項式最小次方為$n-1$)，由輸入資料可得二元一次方程式： $$\begin{cases}7=4a+b \\2=a+b \end{cases}$$ 用矩陣形式表示： $$\begin{bmatrix} 4 & 1\\1 & 1\end{bmatrix}\begin{bmatrix} a\\b\end{bmatrix}=\begin{bmatrix} 7\\2\end{bmatrix}$$ $$\quad A\qquad\ \ \vec {x}\ \ \ =\ \ \vec {b}$$

要得到矩陣的解，只需將 $A^{-1}$ 的解求出後，在乘上 $\vec {b}$ 即可，常見的方法有公式解、高斯消去法(Gaussian Elimination)、Cholesky分解(Cholesky decomposition or Cholesky factorization)、LU分解(LU decomposition)。其中後兩者的複雜度較前兩者低。

最小平方誤差(Least Squares Error)

在討論誤差前，我們先來討論另外兩個問題。

1. 誤差的來源：誤差的來源很多，不論是藉由人的感官觀察，亦或者是利用精密的儀器，總是會存在誤差，差別是在大小而已。另外，在電腦紀錄數字時，由於電腦是二進位制的，在記錄小數時，也存在四捨五入(round off) 的問題。
2. 回歸分析(Regression Analysis) 所用的函數：下方左圖是對 $y=\sin(x)$ 取樣(sampling) 所得到的點，假設存在某種誤差，使得取樣出來的點都有些微偏離 $y=\sin(x)$ 這條真正的線 (事實上 $y=\sin(x)$ 上的點大多屬於無理數，對於使用有限位元儲存數字的電腦來說，或多或少會存在些誤差)。如果我們使用多項式來尋找這些點的最小誤差，可以得到 $y=-0.1206x^6+1.4959x^5-7.2949x^4+17.667x^3-22.409x^2+14.309x-2.7468$，函數圖形如下方右圖。雖然說三角函數可以藉由泰勒級數來做近似，但如果我們需要預測離我們資料有一段距離的點，那就必須用到非常高次的多項式來做逼近，大大增加了運算的複雜度。

假設我們想用多項式來表達輸出入的關係，令 $x^{(i)}$ 為第 $i$ 筆輸入資料；$y^{(k)}$ 為第 $k$ 筆輸出資料，且總共有 $t$ 筆資料，則待求的回歸多項式可以用矩陣表示：

$$\begin{bmatrix} 1& x^{(1)^{(1)}}&\cdots& x^{(1)^{(n)}}&\\ 1& x^{(2)^{(1)}}&\cdots& x^{(2)^{(n)}}&\\ \vdots&\vdots&\ddots&\vdots\\ 1& x^{(t)^{(1)}}&\cdots& x^{(t)^{(n)}}&\\ \end{bmatrix} \begin{bmatrix} c_0\\ c_1\\ \vdots\\ c_n \end{bmatrix}= \begin{bmatrix} y^{(1)}\\ y^{(2)}\\ \vdots\\ y^{(t)} \end{bmatrix}\\ \qquad\qquad\qquad A\qquad\qquad\qquad\ \ \vec{w}\quad=\quad\vec{b}$$

不難看出 $$y^{(k)}=\sum_{i=0}^n c_i x^{(k)^{(i)}}$$ 另外對於 $\vec{w}$ 來說，此方程式是線性的，故又稱 linear method。

上面的矩陣形式也可以推廣至任意函數：

設函數 $f_0, f_1, \cdots, f_n$為單變數實函數，若利用此 $n+1$ 個函數當 基底函數(basis function) ，則可利用以下矩陣方程式來求各項係數：

$$\begin{bmatrix} f_0(x^{(1)})& f_1(x^{(1)})&\cdots& f_n(x^{(1)})&\\ f_0(x^{(2)})& f_1(x^{(2)})&\cdots& f_n(x^{(2)})&\\ \vdots&\vdots&\ddots&\vdots\\ f_0(x^{(t)})& f_1(x^{(t)})&\cdots& f_n(x^{(t)})&\\ \end{bmatrix} \begin{bmatrix} c_0\\ c_1\\ \vdots\\ c_n \end{bmatrix}= \begin{bmatrix} y^{(1)}\\ y^{(2)}\\ \vdots\\ y^{(t)} \end{bmatrix}$$

可以類推 $$y^{(k)}=\sum_{i=0}^n c_i f_i(x^{(k)})$$ 若令 $f_i(x)=x^i$ 即和上式相同

在了解輸入的資料存在著誤差後，接下來的問題便是如何評估函數與輸入資料之間的相關性，最常用到的方法是 最小平方誤差(LSE, Least Square Error)。必須先要了解清楚的是，上式 $A\vec{w}=\vec{b}$ 所求出來的 $\vec{b}$ 實際上並不是我們所預期 (設定) 的輸出 $\vec{y}=\begin{bmatrix} y^{(1)} y^{(2)} \cdots y^{(t)} \end{bmatrix}^{T}$ ，在上式的情況中是假設理想情況，也就是說回歸函數會通過所有輸入的資料點，但在實際情況中，因為誤差存在的關係，僅有少數資料會在回歸函數上，也就是說 $\vec{w}$ 的最佳解並不是 $A^{-1}\vec{b}$，況且我們也不能保證矩陣 $A$ 一定可逆 (甚至連方陣都不是)。

定義函數 $J(\vec{x})$ 為回歸函數的 成本函數(cost function)，可推導出以下結果：

$$\begin{align}J(\vec{x})&=\begin{Vmatrix}A\vec{x}-\vec{b}\end{Vmatrix}_2^2\\&=(A\vec{x}-\vec{b})^T(A\vec{x}-\vec{b})\\&=(\vec{x}^T A^T-\vec{b}^T)(A\vec{x}-\vec{b})\\&=\vec{x}^T A^T A\vec{x} - \vec{x}^T A^T \vec{b} - \vec{b}^T A\vec{x} + \vec{b}^T\vec{b}\end{align}$$

先把上面的式子放一邊，我們來推導一下需要的矩陣導數，假設 $A$ 為矩陣，$a_{ij}$ 為矩陣第 $i$ 列、第$j$ 行的元素；$\vec{x}$ 為向量，$a_{k}$ 為向量 $\vec{x}$ 第 $k$ 個元素：

$$\begin{align}(VV-2)\qquad\qquad\qquad \frac{\partial \vec{x}}{\partial \vec{x}} &=\begin{bmatrix}\frac{\partial x_1}{\partial \vec{x}}& \frac{\partial x_2}{\partial \vec{x}}&\cdots& \frac{\partial x_n}{\partial \vec{x}}\end{bmatrix}\\ &=\begin{bmatrix} \frac{\partial x_1}{\partial x_1}& \frac{\partial x_2}{\partial x_1}&\cdots& \frac{\partial x_n}{\partial x_1} \\ \frac{\partial x_1}{\partial x_2}& \frac{\partial x_2}{\partial x_2}&\cdots& \frac{\partial x_n}{\partial x_2} \\ \vdots&\vdots&\ddots&\vdots\\ \frac{\partial x_1}{\partial x_n}& \frac{\partial x_2}{\partial x_n}&\cdots& \frac{\partial x_n}{\partial x_2} \end{bmatrix} \\ &=\begin{bmatrix} 1& 0& \cdots& 0 \\ 0& 1& \cdots& 0 \\ \vdots&\vdots&\ddots&\vdots\\ 0& 0& \cdots& 1 \\ \end{bmatrix} \\ &= I \\ \end{align}$$ $$\begin{align}(VV-3)\qquad\qquad\quad\ \frac{\partial A \vec{x}}{\partial \vec{x}} &=\begin{bmatrix}\frac{\partial \sum_{i=1}^n a_{1i} x_i}{\partial \vec{x}}& \frac{\partial \sum_{i=1}^n a_{2i} x_i}{\partial \vec{x}}&\cdots& \frac{\partial \sum_{i=1}^n a_{ni} x_i}{\partial \vec{x}}\end{bmatrix}\\ &=\begin{bmatrix} \frac{\partial \sum_{i=1}^n a_{1i} x_i}{\partial x_1}& \frac{\partial \sum_{i=1}^n a_{2i} x_i}{\partial x_1}&\cdots& \frac{\partial \sum_{i=1}^n a_{ni} x_i}{\partial x_1} \\ \frac{\partial \sum_{i=1}^n a_{1i} x_i}{\partial x_2}& \frac{\partial \sum_{i=1}^n a_{2i} x_i}{\partial x_2}&\cdots& \frac{\partial \sum_{i=1}^n a_{ni} x_i}{\partial x_2} \\ \vdots&\vdots&\ddots&\vdots\\ \frac{\partial \sum_{i=1}^n a_{1i} x_i}{\partial x_n}& \frac{\partial \sum_{i=1}^n a_{2i} x_i}{\partial x_n}&\cdots& \frac{\partial \sum_{i=1}^n a_{ni} x_i}{\partial x_2} \end{bmatrix} \\ &=\begin{bmatrix} a_{11}& a_{21}& \cdots& a_{n1} \\ a_{12}& a_{22}& \cdots& a_{n2} \\ \vdots&\vdots&\ddots&\vdots\\ a_{1n}& a_{2n}& \cdots& a_{nn} \\ \end{bmatrix} \\ &= A^T \\ \end{align}$$ $$\begin{align}(VV-4)\qquad\qquad\ \ \ \frac{\partial \vec{x}^T A}{\partial \vec{x}} &=\begin{bmatrix}\frac{\partial \sum_{i=1}^n x_i a_{i1}}{\partial \vec{x}}& \frac{\partial \sum_{i=1}^n x_i a_{i2}}{\partial \vec{x}}&\cdots& \frac{\partial \sum_{i=1}^n x_i a_{in}}{\partial \vec{x}}\end{bmatrix}\\ &=\begin{bmatrix} \frac{\partial \sum_{i=1}^n x_i a_{i1}}{\partial x_1}& \frac{\partial \sum_{i=1}^n x_i a_{i2}}{\partial x_1}&\cdots& \frac{\partial \sum_{i=1}^n x_i a_{in}}{\partial x_1} \\ \frac{\partial \sum_{i=1}^n x_i a_{i1}}{\partial x_2}& \frac{\partial \sum_{i=1}^n x_i a_{i2}}{\partial x_2}&\cdots& \frac{\partial \sum_{i=1}^n x_i a_{in}}{\partial x_2} \\ \vdots&\vdots&\ddots&\vdots\\ \frac{\partial \sum_{i=1}^n x_i a_{i1}}{\partial x_n}& \frac{\partial \sum_{i=1}^n x_i a_{i2}}{\partial x_n}&\cdots& \frac{\partial \sum_{i=1}^n x_i a_{in}}{\partial x_2} \end{bmatrix} \\ &=\begin{bmatrix} a_{11}& a_{12}& \cdots& a_{1n} \\ a_{21}& a_{22}& \cdots& a_{2n} \\ \vdots&\vdots&\ddots&\vdots\\ a_{n1}& a_{n2}& \cdots& a_{nn} \\ \end{bmatrix} \\ &= A \\ \end{align}$$ $$\begin{align}(SV-10)\qquad\quad\ \ \frac{\partial \vec{x}^T A \vec{x}}{\partial \vec{x}} &=\begin{bmatrix}\frac{\partial \sum_{i=1}^n (x_i (\sum_{j=1}^n x_j a_{ji}))}{\partial \vec{x}}\end{bmatrix} \\ &=\begin{bmatrix} \frac{\partial \sum_{i=1}^n (x_i (\sum_{j=1}^n x_j a_{ji}))}{\partial x_1} \\ \frac{\partial \sum_{i=1}^n (x_i (\sum_{j=1}^n x_j a_{ji}))}{\partial x_2} \\ \vdots \\ \frac{\partial \sum_{i=1}^n (x_i (\sum_{j=1}^n x_j a_{ji}))}{\partial x_n} \end{bmatrix}\\ &=\begin{bmatrix} \frac{\partial (x_1 (\sum_{j=1}^n x_j a_{j1}) + \sum_{i=2}^n (x_i (\sum_{j=1}^n x_j a_{ji})))}{\partial x_1} \\ \frac{\partial (x_1 (\sum_{j=1}^n x_j a_{j1}) + x_2 (\sum_{j=1}^n x_j a_{j2}) + \sum_{i=3}^n (x_i (\sum_{j=1}^n x_j a_{ji})))}{\partial x_2} \\ \vdots \\ \frac{\partial (\sum_{i=1}^{n-1} (x_i (\sum_{j=1}^n x_j a_{ji})) + x_n (\sum_{j=1}^n x_j a_{jn})}{\partial x_n} \end{bmatrix}\\ &=\begin{bmatrix} (\sum_{j=1}^n x_j a_{j1}) + x_1 a_{11}+ (\sum_{i=2}^n x_i a_{1i}) \\ x_1 a_{21} + (\sum_{j=1}^n x_j a_{j2}) + x_2 a_{22} + (\sum_{i=3}^n (x_i a_{2i}) \\ \vdots \\ (\sum_{i=1}^{n-1} x_i a_{ni}) + (\sum_{j=1}^n x_j a_{jn}) + x_n a_{nn} \end{bmatrix}\\ &=\begin{bmatrix} (\sum_{j=1}^n x_j a_{j1}) + (\sum_{i=1}^n x_i a_{1i}) \\ (\sum_{j=1}^n x_j a_{j2}) + (\sum_{i=1}^n x_i a_{2i}) \\ \vdots \\ (\sum_{i=1}^n x_i a_{ni}) + (\sum_{j=1}^n x_j a_{jn}) \end{bmatrix}\\ &=\begin{bmatrix} \sum_{j=1}^n x_j a_{j1} \\ \sum_{j=1}^n x_j a_{j2} \\ \vdots \\ \sum_{i=1}^n x_i a_{ni} \end{bmatrix} + \begin{bmatrix} \sum_{i=1}^n x_i a_{1i} \\ \sum_{i=1}^n x_i a_{2i} \\ \vdots \\ \sum_{j=1}^n x_j a_{jn} \end{bmatrix} \\ &=\begin{bmatrix} a_{11}& a_{21}& \cdots& a_{n1} \\ a_{12}& a_{22}& \cdots& a_{n2} \\ \vdots&\vdots&\ddots&\vdots\\ a_{1n}& a_{2n}& \cdots& a_{nn} \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ \vdots\\ x_n \end{bmatrix} + \begin{bmatrix} a_{11}& a_{12}& \cdots& a_{1n} \\ a_{21}& a_{22}& \cdots& a_{2n} \\ \vdots&\vdots&\ddots&\vdots\\ a_{n1}& a_{n2}& \cdots& a_{nn} \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ \vdots\\ x_n \end{bmatrix}\\ &= A^T \vec{x} + A \vec{x}\\ &= (A^T + A) \vec{x} \end{align}$$

要注意的一點是，上面的式子為了推導方便，都是假設 $A$ 為 $(n*n)$ 的矩陣、$\vec{x}$ 為 $(n*1)$ 的向量 ，事實上在符合矩陣的乘法要求下，$A$ 和 $\vec{x}$ 可為任意大小，上方的結果依然成立。另外，本文為了使推導過程較直觀，造成過程有些冗長，比較推薦下方參考資料 "矩陣導數" 中的推導方式，該篇的證明非常完整，相信在閱讀過後，會對相關的概念有更進一步的認識。

回到我們的成本函數，要找到 $J(\vec{x})$ 的極小值，我們可以將其對 $\vec{x}$ 偏微分： $$\begin{align}\frac{\partial J(\vec{x})}{\partial \vec{x}} &= \frac{\partial (\vec{x}^T A^T A\vec{x} - \vec{x}^T A^T \vec{b} - \vec{b}^T A\vec{x} + \vec{b}^T\vec{b})}{\partial\vec{x}} \\ &= \frac{\partial (\vec{x}^T A^T A\vec{x})}{\partial\vec{x}} - \frac{\partial (\vec{x}^T A^T \vec{b})}{\partial\vec{x}} - \frac{\partial (\vec{b}^T A\vec{x})}{\partial\vec{x}} + \frac{\partial (\vec{b}^T\vec{b})}{\partial\vec{x}} \\ &= ((A^T A)^T + A^T A) \vec{x} - A^T \vec{b} - (\vec{b}^T A)^T \\ &= 2 A^T A \vec{x} - 2 A^T \vec{b} \end{align}$$

假設 $\vec{x}^*$ 可以讓 $J(\vec{x})$ 的值最小：

$$\Rightarrow \frac{\partial J(\vec{x}^*)}{\partial \vec{x}} = 0 \\ \Rightarrow 2 A^T A \vec{x}^* - 2 A^T \vec{b} = 0 \\ \Rightarrow 2 A^T A \vec{x}^* = 2 A^T \vec{b} \\ \Rightarrow \vec{x}^* = (A^T A)^{-1} A^T \vec{b} \qquad\qquad\qquad\qquad\qquad \text{(如果 $A^T A$ 可逆)}$$

從幾何觀點來解釋的話，$\vec{x}^*$ 是 $\vec{b}$ 在 $Range(A)$ 上的投影 ( $(A^T A)^{-1} A^T$ 即為投影矩陣)。

過適(Overfitting，或稱過度擬合)

當我們發現我們的回歸函數在 訓練集(train set) 中誤差很小，可是在 開發集(dev set) 和 測試集(test set) 中誤差很大時，很有可能發生過度擬合現象。一般來說，發生過度擬合的原因有四種：

1. 數據量小，低於PAC規定的最小數據量。
2. 數據噪音大，很多亂七八糟的點干擾了學習的過程，重點完全跑偏了。
3. 模型任務本身很複雜，這種情況下不管怎麼搞都效果不好，或多或少會過擬合。
4. 設空間 H 太大，比如說從二項式、三項式甚至到 1024 項式都有，最後我們選擇的最優模型必然是高次項的模型，這種情況下必然過擬合。

其中 1 可以通過增大數據集解決，2 可以通過數據清洗和預處理解決，3 受限於問題本質，最後 4 可以利用 rLSE 解決。

rLSE (regularized Least Square Error)

透過觀察，我們發現當過適發生時，其各項係數通常會很大，因此引入 正則化(regularization) 的概念來減輕過適的程度。定義新的成本函數：

$$\widetilde{J}(\vec{x})=\begin{Vmatrix}A\vec{x}-\vec{b}\end{Vmatrix}_2^2 + \lambda \begin{Vmatrix}\vec{x}\end{Vmatrix}_2^2 \\ \frac {\partial \widetilde{J}(\vec{x})}{\partial (\vec{x})} = 2 A^T A \vec{x} - 2 A^T \vec{b} + 2 \lambda \vec{x}$$

假設 $\vec{x}^*$ 可以讓 $\widetilde{J}(\vec{x})$ 的值最小：

$$\Rightarrow \frac{\partial J(\vec{x}^*)}{\partial \vec{x}} = 0 \\ \Rightarrow 2 A^T A \vec{x}^* - 2 A^T \vec{b} + 2 \lambda \vec{x}^* = 0 \\ \Rightarrow A^T A \vec{x}^* + \lambda \vec{x}^* = A^T \vec{b} \\ \Rightarrow \vec{x}^* = (A^T A + \lambda I)^{-1} A^T \vec{b}$$

正規化同時解決了另一個問題， $A^TA$ 的可逆性：因為 $A^TA$為正半定矩陣，故 $A^T A + \lambda I$ 行列式大於零，確保可逆性。如果從圖形上來看，要先提到 拉格朗日乘數法(Lagrange Multiplier)：

對於一個 $n$ 變數的函數 $f(x_1,\ x_2,\ \cdots,\ x_n)$ 在 $k$ 個約束條件

$\qquad g_1(x_1,\ x_2,\ \cdots,\ x_n) = 0\\\qquad g_2(x_1,\ x_2,\ \cdots,\ x_n) = 0\\\qquad \qquad\qquad\ \ \vdots\\\qquad g_k(x_1,\ x_2,\ \cdots,\ x_n) = 0$

之下求出極值，等價於求出

$\qquad \mathcal{L}(x_1,\ x_2,\ \cdots,\ x_n,\ \lambda_1,\ \lambda_2,\ \cdots,\ \lambda_k)=f(x_1,\ x_2,\ \cdots,\ x_n) + \sum_{i=1}^k \lambda_i g_i(x_1,\ x_2,\ \cdots,\ x_n)$

的極值(其解僅為可能值)，另外可將限制條件推廣至不等式，即 $h_k(x_1,\ x_2,\ \cdots,\ x_n) \le 0$，相關推導請查看Karush-Kuhn-Tucker (KKT) 條件。

左邊的圖描述當正規項為 $\lambda\begin{Vmatrix}\vec{x}\end{Vmatrix}_2^2$ 的圖形，其優點為可微分求解；而右邊的圖描述當正規項為 $\lambda\begin{Vmatrix}\vec{x}\end{Vmatrix}_1$ 的圖形，其優點為有機會使部分係數趨近於 0 (因為原成本函數 $J(\vec{x})$ 容易與限制函數交於尖角，當此情況發生時會有部分係數為 0)，此方法又稱 Lasso算法（Least Absolute Shrinkage and Selection Operator)。

如果從代數上來看，可以藉由 奇異值分解(SVD, Single Value Decomposition)及 共變異數（Covariance）的概念推出正規化是根據協方差矩陣的特徵值對不同成分進行收縮，詳細推導請參閱這裡。

牛頓─拉弗森法 (Newton-Raphson method)

另外一種求最佳解的方法為 牛頓法(Newton's method)，其利用泰勒級數展開到二次項來做根的逼近：

$$f(x) = 0 = f(x_0) + f'(x_0)(x-x_0)+O((x-x_0)^2) \\ \Rightarrow 0 \approx f(x_0) + f'(x_0)(x-x_0) \\ \Rightarrow x = x_0 - \frac {f(x_0)}{f'(x_0)}$$

我們可以根據上式的結果來不斷迭代，終止條件為 $f'(x)=0$ 或 $x$ 的誤差在容許範圍內。值得注意的是，牛頓法得到的結果與初值設定 $x_0$ 及函數本身有關係，有可能不會收斂，又或者是收斂在 $f(x)\neq 0$ 的位置上，下方參考資料有對於牛頓法不同收斂結果的函數範例。另外牛頓法亦可以套用在求極值的問題上，我們知道在極值發生的點上 $f'(x)=0$，類似上方推導過程：

$$f(x) = f(x_0) + f'(x_0)(x-x_0)+ \frac {1}{2!}f''(x_0)(x-x_0)^2+O((x-x_0)^3) \\ \Rightarrow 0 = f'(x) \approx f'(x_0) + f''(x_0)(x-x_0)\\ \Rightarrow x = x_0 - \frac {f'(x_0)}{f''(x_0)}$$

如果要解決回歸直線的問題，我們需要將牛頓法推廣到多維：

$$\begin{align}f(\vec{x}) = f(\vec{x_0}+\delta x) &=f(\vec{x_0})+\sum_i \delta x_i\frac{\partial f}{\partial x_{0_i}}+\frac{1}{2!}\sum_{i,j} \delta x_i \delta x_j\frac{\partial^2f}{\partial x_{0_i}\partial x_{0_j}}+\frac{1}{3!}\sum_{i,j,k}\delta x_i \delta x_j \delta x_k\frac{\partial^3f}{\partial x_{0_i}\partial x_{0_j}\partial x_{0_k}}+\cdots \\ &\approx f(\vec{x_0})+{\delta x}^T\nabla f(\vec{x_0})+\frac{1}{2!}{\delta x}^T H(f(\vec{x_0}))\delta x\end{align}$$ $$\Rightarrow \frac{\partial f(\vec{x})}{\partial \delta x} \approx \nabla f(\vec{x_0}) + \frac{1}{2!}(H(f(\vec{x_0})^T + H(f(\vec{x_0})))\delta x$$

可以適當假設 cost function 的一階及二階導數為連續函數，因此 Hessian 矩陣為對稱矩陣：

$$\Rightarrow 0 = \nabla f(\vec{x_0}) + H(f(\vec{x_0})) \delta x \\ \Rightarrow \delta x = -H(f(\vec{x_0}))^{-1}\nabla f(\vec{x_0})$$ $$\begin{align}\Rightarrow \vec{x}&= \vec{x_0}+ \delta x \\ &=\vec{x_0} -H(f(\vec{x_0}))^{-1}\nabla f(\vec{x_0})\end{align}$$

上式即為牛頓法在高維時的迭代，透過誤差分析可以得知其收斂速度是二次的，比梯度下降法的一階收斂還要快。然而，此迭代在實作上有兩個困難點：

• Hessian 矩陣的可逆性：因為成本函數一般僅為凸函數，其 Hessian 矩陣本身只保證為正半定矩陣，其反矩陣不一定存在。
• 計算複雜度：在目標函數為二次以上時，每次迭代都需要重新計算 Hessian 矩陣，然後再求其逆矩陣，計算量相當大。

為了解決牛頓法在計算方面的問題，就發展出了擬牛頓法。

擬牛頓法（Quasi-Newton Methods）

擬牛頓法的本質思想是改善牛頓法每次需要求解複雜的Hessian矩陣的逆矩陣的缺陷，它使用正定矩陣來近似Hessian矩陣的逆，從而簡化了運算的複雜度。擬牛頓法和最速下降法一樣只要求每一步迭代時知道目標函數的梯度。通過測量梯度的變化，構造一個目標函數的模型使之足以產生超線性收斂性。尤其對於困難的問題，這類方法大大優於最速下降法。由於推導過程超出筆者能說明解釋範圍，有興趣的讀者請參閱牛顿法与拟牛顿法学习笔记。

參考資料：

Machine learning
監督式學習？增強學習？聽不懂的話，一定要看這篇入門的機器學習名詞解釋！
矩陣導數
机器学习中使用正则化来防止过拟合是什么原理？
Why are additional constraint and penalty term equivalent in ridge regression?
如何通俗易懂地讲解牛顿迭代法求开方？
牛頓法
應用於最優化的牛頓法
怎么理解二阶偏导与凸函数的Hessian矩阵是半正定的？
[Math] 常见的几种最优化方法