最小平方法 2

給定一個矩陣 $A$ 以及一個向量 $b$, 我們想要找到一個向量 $x$ 使得 $\|Ax - b\|^2+\|x\|^2$ 最小.

$$ A\in M_{m\times n}, \quad b \in M_{m\times 1}, \quad x\in M_{n\times 1}. $$

1. Motivation

1.1 Non-uniqueness

最小平方法 $\|Ax-b\|^2$ 問題有時候解並不唯一, 常見的例子例如深度學習裡的神經網路, 他的參數數量通常都遠比資料點數量多非常多. 若我們把 $x$ 看成所有要找的參數的集合, 因此 $n$ 就是參數個數. 然後 $b$ 就是 target 資料集, 所以 $m$ 就是資料個數. 所以常常會有 $m \ll n$ 的情形. 這樣的話 $A$ 的 null space 不為零, 最小平方法的解空間變成了一個 affine subspace, 有無窮多組解.

1.1.1 Sensitivity in prediction

由於有無窮多組解, 因此選的解變異就非常大. 而最怕的情形就是某個參數非常的大. 這樣訓練出來的模型會很敏感, 一點點小擾動預測就差非常多.

舉個極端的例子, 比如說我們要找一個模型 $f(x,y) = ax+by$, 其中 $a, b$ 是參數. 假設我們只有一筆資料 $f(1,1) = 0$. 這樣的話我們就只有一個方程式, 也就是, 模型裡的參數必須滿足

$$ a + b = 0, $$

有無窮多解!

如果我們選 $(a, b) = (10000, -10000)$. 那這樣我們的模型就是

$$ f_1(x,y) = 10000x-10000y. $$

然後算一下 $f_1(0, 0)=0$ 以及 $f_1(1,0)=10000$, 初始值差 $1$ 不過預測值差 $10000$.

如果我們選 $(a, b) = (1, -1)$. 那這樣我們的模型就是

$$ f_2(x,y) = x-y. $$

因此 $f_2(0, 0)=0$ 以及 $f_2(1,0)=1$, 初始值差 $1$ 預測值也差 $1$.

所以模型參數的大小會直接影響到模型預測的敏感度. 通常我們希望模型不要太敏感, 因此輸入的資料難免有誤差, 不要因為一點點的誤差就在預測差了十萬八千里. 而一個簡單的做法就是我們不僅要求 $\|Ax-b\|^2$ 要小, 我們也要求 $\|x\|^2$ 要小. 這樣子參數就不會太大了.

1.2 Ill-conditioning

在最小平方法的計算裡需要解 $A^TAx = A^Tb$ 這個系統. 不過 $A^TA$ 這矩陣我們只能保證半正定, 所以不一定可以解. 另外, 解這個矩陣也有可能會有很大的誤差 (在數值分析裡我們稱之為 ill-conditioned matrix). 簡單的說如果一個矩陣的 eigenvalue 離 $0$ 很靠近的話, 這個矩陣就會很像 singular matrix, 解起來就會有很大的誤差. 因此我們希望矩陣的 eigenvalue 遠離 $0$.

一個簡單的觀察是, $A^TA + I$ 這個矩陣是個正定矩陣, 並且他的 eigenvalues 全都大於等於 $1$. 所以 $(A^TA+I)x = A^Tb$ 這個系統就會 well-condition, 解起來誤差不會太大.

2. Ridge regression and its dual problem

首先我們定義 $\hat{x}$ 為找到的那個解, 也就是說, 我們要解以下這個問題

$$ \newcommand{\argmin}{\arg\min} \tag{1} \hat{x} = \argmin_{x\in\mathbb{R}^n}\left(\|Ax - b\|^2+\|x\|^2\right). $$

首先觀察可以發現

$$ \tag{2} \|Ax - b\|^2+\|x\|^2 = \left\|\begin{bmatrix}A\\ I \end{bmatrix}x - \begin{bmatrix}b\\ 0 \end{bmatrix}\right\|^2. $$

因此, (1) 其實就是個最小平方問題, 只是這個問題的系統變成加大的一個系統而已. 因此我們知道這個問題的解會滿足

$$ \tag{3} \begin{bmatrix}A^T & I \end{bmatrix} \begin{bmatrix}A\\ I \end{bmatrix}\hat{x} = \begin{bmatrix}A^T & I \end{bmatrix} \begin{bmatrix}b\\ 0 \end{bmatrix}, $$

也就是

$$ \tag{4} (A^TA + I)\hat{x} = A^Tb. $$

接著我們將 (4) 改寫成

$$ \tag{5} \hat{x} = A^T(b-A\hat{x}), $$

並且我們定義一個新變數 $\alpha$ 為

$$ \tag{6} \alpha = b-A\hat{x}, $$

因此我們有

$$ \tag{7} \hat{x} = A^T\alpha. $$

接著從 (6) 跟 (7) 我們可以得到

$$ \tag{8} \alpha = b-A\hat{x} = b-AA^T\alpha, $$

整理一下得到 $\alpha$ 要滿足的方程式為

$$ \tag{9} (AA^T+ I)\alpha = b. $$

最後, 由於 $\hat{x}=A^T\alpha$ 我們可以得到

$$ \tag{10} \hat{x} = A^T(AA^T + I)^{-1}b. $$

2.1 QR decomposition

我們對 $A$ 做 (reduced) QR 分解得到

$$ \tag{11} A = QR, $$ where $Q^TQ= I_{r\times r}$, $Q\in M_{m\times r}$ and $R\in M_{r\times n}$.

那 least square 問題的解 (4) 可以改寫成

$$ \tag{12} (R^TR+I)\hat{x} = R^TQ^Tb. $$

而 (10) 則是寫成

$$ \tag{13} \hat{x} = R^T(RR^T+I)^{-1}Q^Tb, $$

3. Conclusion

我們考慮以下最小平方法問題

$$ \min_{x\in\mathbb{R}^n}\left(\|Ax - b\|^2+\|x\|^2\right), $$

並且我們令最佳解為 $\hat{x}$.

• 如果 $m>n$, 我們以下列式子來計算 $$ \hat{x} = (A^TA+I)^{-1}A^Tb. $$
  • 如果對 $A$ 做 (reduced) QR, $A=QR$, 並且 $Q^TQ=I_{n\times n}$, $$ \hat{x} = (R^TR+I)^{-1}R^TQ^Tb. $$
• 如果 $m<n$, 我們以下列式子來計算 $$ \hat{x} = A^T(AA^T+I)^{-1}b. $$
  • 如果對 $A$ 做 (reduced) QR, $A=QR$, 並且 $Q^TQ=I_{n\times n}$, $$ \hat{x} = R^T(RR^T+I)^{-1}Q^Tb. $$