---
title: 最小平方法 2
tags: Linear algebra
GA: G-77TT93X4N1
---

最小平方法 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.
$$

---