掰開揉碎推導Normal Equation

01-25

Normal Equation是一種基礎的最小二乘方法，本文將從線性代數的角度來分析Normal Equation（而不是從矩陣求導 matrix derivative 的角度）。

很多作者（特別是智商比較高的）在推導公式的時候有意無意的忽略了思考過程，只留下漂亮的步驟。這讓很多讀者（比如說我）跟不上節奏，最後一頭霧水。本文將從求解「貌似無解」的方程組入手，再講講投影（Projection）的使用，最後進入到Normal Equation的應用。我的目的是讓和我一樣蠢的孩子對 $overrightarrow heta = (A^TA)^{-1}A^Toverrightarrow{y}$ 這個重要公式有一個Big Picture——即使忘記了也可以重頭推出。

更新記錄：

更新1 增加了對 $A^TA$ 的使用解釋（偏導數證明）

一、求解不可解的方程組

先看一個最最簡單的例子——

例1.0 如圖，在 $R^2$ 空間中有兩個向量，求一個常數 $heta$ 使兩個向量滿足 $heta overrightarrow{a} =overrightarrow{b}$ 。

這個方程明顯不可解，因為 $overrightarrow{b}$ 與 $overrightarrow{a}$ 不共線，無法通過對 $overrightarrow{a}$ 數乘得到 $overrightarrow{b}$ 。

再看下一個比較簡單的例子——

例2.0 在 $R^3$ 空間中的平面 $P$ 有一組基 $overrightarrow{a_1}$ 和 $overrightarrow{a_2}$ ，如圖所示，求出常數 $heta_1$ 與 $heta_2$ 使向量 $overrightarrow{b}$ 滿足條件 $heta_1overrightarrow{a_1}+ heta_2overrightarrow{a_2} =overrightarrow{b}$ 。

這個方程也明顯不可解，因為 $overrightarrow{b}$ 不在平面 $P$ 上，而 $overrightarrow{a_1}$ 與 $overrightarrow{a_2}$ 的線性組合只能得到平面上的向量。

以上兩個問題非常的典型，因為在解決實際問題的時候，我們很難得到Perfect Solution，我們只能儘力而為的爭取Best Solution。以上兩個例子明顯沒有做到perfect(連基本的方向都錯了)，那麼如何找到best solution呢？

二、投影的應用

思路很簡單：我們只要找到一個 $heta^*$ 使 $overrightarrow{a}$ 方向上的向量 $overrightarrow{p} = heta^* overrightarrow{a}$ 距離 $overrightarrow{b}$ 最近。

回到最簡單的例子

如圖，在 $R^2$ 空間中有兩個向量，求一個常數 $heta$ 使兩個向量滿足 $heta overrightarrow{a} =overrightarrow{b}$ 。

現在應該如何尋找 $heta overrightarrow{a} =overrightarrow{b}$ 的解呢？

最好的方法就是拋棄 $overrightarrow{b}$ 向量中垂直 $overrightarrow{a}$ 的分量，只要計算 $heta$ 使 $heta overrightarrow{a}$ 等於向量 $overrightarrow{b}$ 在 $overrightarrow{a}$

方向的分量（即 $overrightarrow{b}$ 在 $overrightarrow{a}$ 上的投影(Proj) $overrightarrow{p}$ ），同時我們把向量 $overrightarrow{b}$ 垂直 $overrightarrow{a}$ 方向的分量稱為 $overrightarrow{e}$ (error)。

原來的問題 $heta overrightarrow{a} =overrightarrow{b}$ 變成了求解 $heta^* overrightarrow{a} =overrightarrow{p}$ （ $heta^*$ 是 $heta$ 的估計量）

因為 $overrightarrow{p}$ 與 $overrightarrow{e}$ 合成了 $overrightarrow{b}$ 向量（ $overrightarrow{e} +overrightarrow{p}= overrightarrow{b}$ ），而且 $overrightarrow{e}$ 垂直於 $overrightarrow{a}$ ( $overrightarrow{e}ot overrightarrow{a}$ )，所以我們得出了一個非常重要的結論（敲黑板）！！！核心啊！！！

$overrightarrow{a}^T(overrightarrow{b}- heta^*overrightarrow{a} ) = 0$

這個方程的核心就是寫成向量內積形式的 $overrightarrow{e}$ 與 $overrightarrow{a}$ 的垂直關係，只不過 $overrightarrow{e}$ 被拆開書寫。其實這個方程也可以寫作 $overrightarrow{a} imes (overrightarrow{b}- heta^*overrightarrow{a} ) = 0$ ，但是寫作轉置向量 $overrightarrow{a}^T$ 的形式可以讓這個方程更自然的拓展到高維。好了，我們繼續改寫方程……

$heta^*overrightarrow{a}^T overrightarrow{a} = overrightarrow{a}^Toverrightarrow{b}$

$heta^* = frac{overrightarrow{a}^Toverrightarrow{b}}{overrightarrow{a}^Toverrightarrow{a}}$

在這一步我們就得到了best的 $heta$ ，但考慮到這並不perfect，所以我們稱之為 $heta^*$ 。

P.S.如果想用投影矩陣P來簡化從 $overrightarrow{a}$ 轉換到 $overrightarrow{p}$ 的過程，可以把 $heta^*$ 的結果帶入到 $overrightarrow{p} = heta^* overrightarrow{a}$ 中。我們發現投影矩陣 $P$ 在形式上就等於乘數 $heta^* = frac{overrightarrow{a}^Toverrightarrow{b}}{overrightarrow{a}^Toverrightarrow{a}}$ ，即 $overrightarrow{p}$ 滿足 $overrightarrow{p} =Poverrightarrow{a}$ 。

現在我們再看看怎麼在 $R^3$ 中解決不可解方程。

例2.0 在 $R^3$ 空間中的平面 $P$ 有一組基 $overrightarrow{a_1}$ 和 $overrightarrow{a_2}$ ，如圖所示，求出常數 $heta_1$ 與 $heta_2$ 使向量 $overrightarrow{b}$ 滿足條件 $heta_1overrightarrow{a_1}+ heta_2overrightarrow{a_2} =overrightarrow{b}$ 。

平面 $P$ 有基向量 $overrightarrow{a_1}$ 和 $overrightarrow{a_2}$ ，故 $P$ 可以表示成基的線性組合 $heta_1overrightarrow{a_1}+ heta_2overrightarrow{a_2}$ ，即 $egin{bmatrix}a_1 a_2end{bmatrix}egin{pmatrix} heta_1 \ heta_2end{pmatrix}$

令基向量組成的矩陣 $A=egin{bmatrix}| |\a_1 a_2\| |\end{bmatrix}$ ，參數組成的向量 $overrightarrow{ heta} = heta_{1 dots n} (n = 2)$ ，與平面垂直的誤差向量 $overrightarrow{e} = overrightarrow{b}-A overrightarrow{ heta^*}$ 。（這裡插一句話，最小二乘法的核心就是找出一個 $heta^*$ 就是讓 $left|| A heta-b ight||^2$ 最小化）

我們發現在 $R^2$ 中的問題 $heta overrightarrow{a} =overrightarrow{b}$ 在這裡拓展成為了 $Aoverrightarrow{ heta }=overrightarrow{b}$ 。

相應的， $heta^* overrightarrow{a} =overrightarrow{p}$ 問題在這裡拓展成了 $Aoverrightarrow{ heta^*}=overrightarrow{p}$ ，其中 $overrightarrow{p}=overrightarrow{ heta_1}overrightarrow{a_1}+overrightarrow{ heta_2}overrightarrow{a_1}$ 。

還是一樣的套路，我們還是從垂直關係入手——因為 $P ot overrightarrow{e}$ ，而且 $P in overrightarrow{ heta_1} overrightarrow{a_1} +overrightarrow{ heta_1} overrightarrow{a_2}$ ，所以有以下方程組——

$egin{cases}overrightarrow{a_1}^T(overrightarrow{b}-Aoverrightarrow{ heta^*})=0\overrightarrow{a_2}^T(overrightarrow{b}-Aoverrightarrow{ heta^*})=0end{cases}$

整理成矩陣的形式——

$egin{bmatrix}-overrightarrow{a_1}^T-\-overrightarrow{a_2}^T-\end{bmatrix}(overrightarrow{b}-Aoverrightarrow{ heta^*})=0$

（敲黑板！！！敲黑板！！！）

$A^T(overrightarrow{b}-Aoverrightarrow{ heta^*})=0$

寫到這裡回頭看看 $R^2$ 情景下的核心公式 $overrightarrow{a}^T(overrightarrow{b}- heta^*overrightarrow{a} ) = 0$ ，可以這傢伙換一套馬甲又出現了！！！看來方程 $A^T(overrightarrow{b}-Aoverrightarrow{ heta^*})=0$ 是一種高維的拓展。我們可以把 $R^2$ 中的 $overrightarrow{a}$ 看成一個只有一列的矩陣。

我們繼續整理這個公式——

$A^Toverrightarrow{b} = A^TAoverrightarrow{ heta}$

$overrightarrow{ heta} = (A^TA)^{-1}A^Toverrightarrow{b}$

寫到這裡我們就沒什麼可以乾的了。

有人可能想說——明明還可以繼續化簡啊！！！

$egin{equation}egin{split}overrightarrow{ heta} &= (A^TA)^{-1}A^Toverrightarrow{b}\& = A^{-1}(A^T)^{-1}A^Toverrightarrow{b}\& = A^{-1}overrightarrow{b}end{split}end{equation}$

但實際的情況中，我們不能保證矩陣 $A$ 總是方陣（square），但是 $A^TA$ 總是可以保證是方陣。因為只有方陣才有逆矩陣，所以我們只能保證有 $(A^TA)^{-1}$ ，而不能保證有 $A^{-1}$ 。

所以我們只能回到 $overrightarrow{ heta} = (A^TA)^{-1}A^Toverrightarrow{b}$ 這裡。如果你有讀過Andrew Ng著名的公開課CS229的Lecture Notes，你一定記得他用矩陣求導得出的Normal Equation——

你會發現除了 $overrightarrow{y}$ 和 $overrightarrow{b}$ 不一樣以外，我們已經把Normal Equation（ $overrightarrow{ heta} = (A^TA)^{-1}A^Toverrightarrow{b}$ ）推出來了……我居然在下一部分還沒有開始講就把內容說完了，場面一度非常尷尬啊。可見從投影推出Normal Equation是一件多麼自然的事情啊~~~我都不知道哪裡切開。

說到這裡先總結一下投影的幾個意義（敲黑板）！！！

$Aoverrightarrow{ heta}$ 的所有可能結果都在一個固定的區域中，在線性代數中我們稱這個區域為列空間(column space),列空間顧名思義就是矩陣各列的所有線性組合 $overrightarrow{ heta_1}overrightarrow{a_1}+overrightarrow{ heta_2}overrightarrow{a_2}+dots+overrightarrow{ heta_n}overrightarrow{a_n}$ 。在1-D的情況下列空間就是一條線，在2-D的情況下列空間就是一個平面。但是我們的數據哪裡會這麼恰好的落在矩陣的列空間里呢？天底下哪有這樣的好事啊！！！

特別是在數據量特別大的情況下，矩陣 $A$ 會成為一個 $ngg m$ 的超級高大的 $n imes m$ 矩陣（如下圖）。在這種等式數量遠大於未知數數量的情況中，我們很難滿足每一個等式的約束。 $A = egin{bmatrix}1 & 1\1 & 2\. & .\. & .\ . & .\1 & 3\end{bmatrix}$

但是目標不再在空間里並不代表不能求出解，只能說沒有perfect solution（語出Gilbert Strang），但是我們努力一下還是可以做到最好的(best solution)。我們用投影向量 $overrightarrow{p}$ 來尋找最合適的 $overrightarrow{ heta^*}$ 。 $overrightarrow{ heta^*}$ 就是並不存在的完美解 $overrightarrow{ heta}$ 的估計值。

三、Normal Equation應用

既然Normal Equation在上文都推導完了，這裡我們就隨便帶幾個數據來玩玩咯。

練手案例 找一條直線來擬合點 (1,1)、(2,2)、(3,2)

我們如果用一條直線來擬合的話，設 $h( heta) = heta_0 + heta_1x_1$ ，我們先得到以下值——
$overrightarrow{ heta} = heta_{0 dots n} (n = 1)$
$A = egin{bmatrix}1 & 1\1 & 2\1 & 3\end{bmatrix}$ $A^T = egin{bmatrix}1 & 1 & 1 \1 & 2 & 3 \end{bmatrix}$ $A^TA = egin{bmatrix}3 & 6 \6 & 14\end{bmatrix}$
$overrightarrow{h( heta)}= (1,2,2)^T$
我們發現 $Aoverrightarrow{ heta} =overrightarrow{h( heta)}$ 很遺憾的沒有解，於是我們左右各乘上 $A^T$ ，祭出了投影大招—— $A^TAoverrightarrow{ heta^*}=A^Toverrightarrow{h( heta^*)}$ 。
再把這個方程變換成Normal Equation: $overrightarrow{ heta^*} = (A^TA)^{-1}A^Toverrightarrow{h( heta^*)}$
帶入數值在Matlab中小跑一下就得到了結果 $overrightarrow{ heta^*} = egin{pmatrix}frac 23\\frac 12 \ end{pmatrix}$
即直線 $h(x) = frac 23 + frac 12 x$ 是上述三個點的擬合結果。

四、其他想說的話

1.關於 $A^TAoverrightarrow{ heta^*}=A^Toverrightarrow{h( heta^*)}$ 的暴力使用

在前一步可以不用判斷是否可解，可以直接使用 $A^TAoverrightarrow{ heta^*}=A^Toverrightarrow{h( heta^*)}$ 。事實上，在最小二乘時遇到長方形矩陣 $A^T$ ，我們就可以用上 $A^TA$ 替代 $A^T$ 計算。這是是一種路子很野的但是很簡單實用的經驗規則，可以簡單實驗如下——

用直線 $h( heta) = heta_0 + heta_1x_1$ 擬合三個點 (1,1)、(2,2)、(3,2)時，自然希望真實值和估計值的誤差 $left | h( heta^*)-h(x) ight |^2$ 越小越好。
$egin{equation}egin{split}error=left | h( heta^*)-h(x) ight |^2 &= ( heta_0 + heta_1 -1 )^2+( heta_0 +2 heta_1-2 )^2+( heta_0 +3 heta_1 -2 )^2\end{split}end{equation}$
分別對 $heta_0$ 和 $heta_1$ 求偏導數等於的零的值——
$egin{equation}egin{split}partial error/partial heta_0&= 2( heta_0 + heta_1 -1 )+2( heta_0 +2 heta_1-2 )+2( heta_0 +3 heta_1 -2 )\& = 6 heta_0+12 heta_1-10\& = 0\end{split}end{equation}$
$egin{equation}egin{split}partial error/partial heta_0&= 2( heta_0 + heta_1 -1 )+2( heta_0 +2 heta_1-2 ) imes 2+2( heta_0 +3 heta_1 -2 ) imes 3\& = 12 heta_0+28 heta_1-22\& = 0\end{split}end{equation}$
整理以上公式我們得到了方程組——
$egin{cases}3 heta_0+6 heta_1 = 5\6 heta_0+14 heta_1 = -11\end{cases}$
再整理一下，把這個方程寫成矩陣乘法的形式——
$egin{bmatrix}3&6\6&14end{bmatrix}egin{pmatrix} heta_0\ heta_1end{pmatrix}= egin{pmatrix}5\-11end{pmatrix}$
在最後一步整理以後我們發現剛才千辛萬苦算出來的 $egin{bmatrix}3 & 6 \6 & 14\end{bmatrix}$ 就是上文的 $A^TA$ 啊！！！

說明這個經驗方法是可以信得過的！！！

2.關於化簡的問題

因為投影的性質非常美妙，如果矩陣 $A$ 是各行線性無關的方陣(square)，說明存在 $A^{-1}$ ，則Normal Equation會變成如下形式——

$egin{equation}egin{split}overrightarrow{ heta} &= (A^TA)^{-1}A^Toverrightarrow{b}\&=A^{-1}{A^T}^{-1}A^Toverrightarrow{b}\&=A^{-1} overrightarrow{b}\end{split}end{equation}$

說明如果存在一個perfect solution，該解不會受到影響。

3.多次投影有影響嗎？

已經在空間中的向量乘上投影矩陣 $P$ 仍然等於本身，二次投影不會有任何副作用！也就是說 $P^2 = P$ 。證明如下——

$egin{equation}egin{split}P^2 &= (A(A^TA)^{-1}A^T)(A(A^TA)^{-1}A^T)\&=A(A^TA)^{-1}(A^TA)(A^TA)^{-1}A^T\&=A(A^TA)^{-1}A^T\&=Pend{split}end{equation}$

五、參考資料

1.Gilbert Strang Introduction to Linear Algebra 4.2 Projection 4.3 Least Squares Approximations
2.Andrew Ng CS229 Lecture Note 1 Supervised learning/The normal equations

六、最後的話

列空間沒展開講不知道有沒有必要。

筆力不夠好，想像中應該寫的更簡單易懂的，但是沒有達到效果，會再更新。

歡迎拍磚！！！