normal equation
對于線性規劃問題來說，除了使用梯度下降，我們還是可以使用normal equation（正規方程），非常簡單的函數完成一步求解，不需要反複疊代：
θ = ( X T X ) − 1 X T y \theta=(X^TX)^{-1}X^Ty θ=(XTX)−1XTy
接下來舉個例子就一目了然了。
既然有如此簡潔的方法，相比之下梯度下降算法一下就落于下風。
當然對于這兩種方法，各有各的優勢和适用場景。
| Gradient Descent | Normal Equation |
|---|---|
| 需要手動設定 α \alpha α | 不需要設定 α \alpha α |
| 需要反複疊代 | 不需要疊代 |
| O ( k n 2 ) O(kn^2) O(kn2) | O ( n 3 ) O(n^3) O(n3) 需要計算 ( X T X ) − 1 (X^TX)^{-1} (XTX)−1 |
| 當 x x x很大的時候，速度優于normal equation | 當 x x x很大的時候，速度就會變得緩慢 |
Andrew Ng教授指出，一般當n大于10000才需要考慮摒棄正規方程，在此之前正規方程的用時是少于梯度下降的。
但是對于classification，比如邏輯回歸或者更複雜的學習算法，正規方程并不适用，我們還是不得不選擇使用梯度下降。
Noninvertibility
對于矩陣 X T X X^TX XTX 來說，如果它是奇異矩陣或者退化矩陣，那麼它是不可逆的，這将導緻無法求得 ( X T X ) − 1 (X^TX)^{-1} (XTX)−1。在這裡對應了兩種情況：
第一種就是對應了下圖中的第一點，選取了備援的特征然後導緻矩陣存線上性相關的列，導緻矩陣不滿秩。
第二種對應下圖中的第二點，對于矩陣 A A A 來說，它的row小于column，這樣就說明我們選取了太多的特征，導緻我們沒有足夠多的sample去fit這些特征，這就好比我們在求解線性方程時，我們的方程數比我們所要求的未知數還有少，導緻我們有無窮多解，同理，sample數小于特征數，我們很難很好的fit這些特征。
對于以上的情況，我們可以先檢查是否存在備援的特征量，如果存在就删除備援特征，然後再檢查我們是否存在過多的特征，如果存在就删除一些或者使用正則化手段。