最小平方法 2

給定一個矩陣

$A$ 以及一個向量

$b$, 我們想要找到一個向量

$x$ 使得

$\Vert Ax-b{\Vert }^2+\Vert x{\Vert }^2$ 最小.

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

1. Motivation

1.1 Non-uniqueness

最小平方法

$\Vert Ax-b{\Vert }^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$.

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

$\Vert Ax-b{\Vert }^2$ 要小, 我們也要求

$\Vert x{\Vert }^2$ 要小. 這樣子參數就不會太大了.

1.2 Ill-conditioning

在最小平方法的計算裡需要解

$A^{T}Ax=A^{T}b$ 這個系統. 不過

$A^{T}A$ 這矩陣我們只能保證半正定, 所以不一定可以解. 另外, 解這個矩陣也有可能會有很大的誤差 (在數值分析裡我們稱之為 ill-conditioned matrix). 簡單的說如果一個矩陣的 eigenvalue 離

$0$ 很靠近的話, 這個矩陣就會很像 singular matrix, 解起來就會有很大的誤差. 因此我們希望矩陣的 eigenvalue 遠離

$0$.

一個簡單的觀察是,

$A^{T}A+I$ 這個矩陣是個正定矩陣, 並且他的 eigenvalues 全都大於等於

$1$. 所以

$(A^{T}A+I)x=A^{T}b$ 這個系統就會 well-condition, 解起來誤差不會太大.

2. Ridge regression and its dual problem

首先我們定義

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

$$\begin{array}{}\text{(1)}& \hat{x}=\arg \underset{x\in {\mathbb{R}}^n}{min}(\Vert Ax-b{\Vert }^2+\Vert x{\Vert }^2).\end{array}$$

首先觀察可以發現

$$\begin{array}{}\text{(2)}& \Vert Ax-b{\Vert }^2+\Vert x{\Vert }^2={\Vert \left[\begin{array}{c}A\\ I\end{array}\right]x-\left[\begin{array}{c}b\\ 0\end{array}\right]\Vert }^2.\end{array}$$

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

$$\begin{array}{}\text{(3)}& \left[\begin{array}{cc}{A}^T& I\end{array}\right]\left[\begin{array}{c}A\\ I\end{array}\right]\hat{x}=\left[\begin{array}{cc}{A}^T& I\end{array}\right]\left[\begin{array}{c}b\\ 0\end{array}\right],\end{array}$$

也就是

$$\begin{array}{}\text{(4)}& (A^{T}A+I)\hat{x}=A^{T}b.\end{array}$$

接著我們將 (4) 改寫成

$$\begin{array}{}\text{(5)}& \hat{x}=A^T(b-A\hat{x}),\end{array}$$

並且我們定義一個新變數

$\alpha$ 為

$$\begin{array}{}\text{(6)}& \alpha =b-A\hat{x},\end{array}$$

因此我們有

$$\begin{array}{}\text{(7)}& \hat{x}=A^T\alpha .\end{array}$$

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

$$\begin{array}{}\text{(8)}& \alpha =b-A\hat{x}=b-A{A}^T\alpha ,\end{array}$$

整理一下得到

$\alpha$ 要滿足的方程式為

$$\begin{array}{}\text{(9)}& (A{A}^T+I)\alpha =b.\end{array}$$

最後, 由於

$\hat{x}=A^T\alpha$ 我們可以得到

$$\begin{array}{}\text{(10)}& \hat{x}=A^T(A{A}^T+I{)}^{-1}b.\end{array}$$

2.1 QR decomposition

我們對

$A$ 做 (reduced) QR 分解得到

$$\begin{array}{}\text{(11)}& A=QR,\end{array}$$
where

$Q^{T}Q=I_{r\times r}$,

$Q\in M_{m\times r}$ and

$R\in M_{r\times n}$.

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

$$\begin{array}{}\text{(12)}& (R^{T}R+I)\hat{x}=R^T{Q}^{T}b.\end{array}$$

而 (10) 則是寫成

$$\begin{array}{}\text{(13)}& \hat{x}=R^T(R{R}^T+I{)}^{-1}{Q}^{T}b,\end{array}$$

3. Conclusion

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

$$\underset{x\in {\mathbb{R}}^n}{min}(\Vert Ax-b{\Vert }^2+\Vert x{\Vert }^2).$$

並且我們令最佳解為

$\hat{x}$.

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

---