線性迴歸與脊迴歸

線性迴歸是許多人都聽過的一套理論。簡單來說，當手中有一系列的點 \((x_1,y_1), \ldots, (x_N, y_N)\) 時，如何找到一條最能代表這些點的趨勢的 最適直線（best fitting line）。以下我們用不同觀點來看這個問題、提出解法、並推廣到脊迴歸。

更精確一點來說，線性迴歸考慮的是所有直線

\[ \mathcal{H} = \{f(x) = c_0 + c_1x: c_0, c_1\in\mathbb{R}\} = \vspan\{1, x\}, \]

並求解以下最佳化問題

\[ \min_{f\in\mathcal{H}} \sum_{i=1}^N (y_i - f(x_i))^2. \]

同樣的問題可以改寫為矩陣的形式，我們首先把所有 \(x\) 座標值和所有 \(y\) 座標值分別記成向量 \(\bx = (x_1, \ldots, x_N)\trans\) 和 \(\by = (y_1, \ldots, y_N)\trans\)，並考慮矩陣

\[ X = \begin{bmatrix} | & | \\ \bone & \bx \\ | & | \\ \end{bmatrix}. \]

如此一來，原最佳化問題等價於

\[ \min_{\bc\in\mathbb{R}^2} \|X\bc - \by\|^2, \]

而兩問題中的 \(\bc = (c_0, c_1)\) 及 \(f(x) = c_0 + c_1x\) 是相互對應的，也就是每個 \(\mathcal{H}\) 中的函數都可以表示成一個二維向量。

線性迴歸有許多標準的解法，如：

  1. 將 \(\by\) 對 \(\Col(X)\) 投影、或
  2. 將 \(\|X\bc - \by\|\) 對 \(\bc\) 微分以求極值等等。

而各種解法都得到唯一解 \(\bc = (X\trans X)^{-1} X\trans\by\)。

這次我們以二次規劃的觀點來求最小值。首先我們觀察

\[ \|X\bc - \by\|^2 = (X\bc - \by)\trans (X\bc - \by) = \bc\trans X\trans X\bc - 2\by\trans X\bc + \by\trans\by, \]

根據 正定矩陣的二次規劃 的結論，我們可以看出上式的最小值唯一發生在

\[ \bc = -\frac{1}{2}(X\trans X)^{-1} (-2X\trans\by) = (X\trans X)^{-1}X\trans\by, \]

因此得到一致的結論。

除了標準版的線性迴歸外， 脊迴歸（ridge regression） 推廣了暨有的設定，並加上一項 \(f\) 的 懲罰項（penalty term），以避免 \(f\) 過度被給定的資料點牽引，它考慮的最佳化問題是

\[ \min_{f\in\mathcal{H}} \sum_{i=1}^N (y_i - f(x_i))^2 + \lambda \|f\|^2, \]

這裡 \(\lambda \geq 0\) 為給定值，而我們考慮 \(\mathcal{H} = \vspan\{1, x\}\) 為搭配

\[ \inp{a_0 + a_1x}{b_0 + b_1x} = a_0b_0 + a_1b_1 \]

的內積空間，因此 \(\|f\|^2 = \|c_0 + c_1x\|^2 = c_0^2 + c_1^2\)。

考慮同樣的 \(X\)，則這個問題等價於

\[ \min_{\bc\in\mathbb{R}^2} \|X\bc - \by\|^2 + \lambda \|\bc\|^2. \]

這樣非標準型的線性迴歸問題，我們還是可以用二次規劃來處理。同樣地將目標式展開

\[ \begin{aligned} \|X\bc + \by\|^2 + \lambda \|\bc\|^2 &= \bc\trans X\trans X\bc - 2\by\trans X\bc + \by\trans\by + \lambda\bc\trans\bc \\ &= \bc\trans (X\trans X + \lambda I)\bc - 2\by\trans X\bc + \by\trans\by. \end{aligned} \]

由於 \(\lambda \geq 0\)，我們知道 \(X\trans X + \lambda I\) 正定，並且上式在

\[ \bc = (X\trans X + \lambda I)^{-1}X\trans\by \]

時可以得到唯一的最小值。

最後，我們強調我們可以調整

\[ \mathcal{H} = \{f(x) = c_0 + c_1x + \cdots + c_dx^d: c_0, c_1,\ldots,c_d\in\mathbb{R}\} = \vspan\{1, x, \ldots, x^d\}, \]

以及

\[ X = \begin{bmatrix} | & | & ~ & | \\ \bone & \bx & \cdots & \bx^{(d)}\\ | & | & ~ & | \\ \end{bmatrix}, \]

其中 \(\bx^{r} = (x_1^r, \ldots, x_N^r)\trans\)。如此一來就可以將原問題拓展到多項式規劃、以及多項式的脊規劃，而實際上 \(X\) 之中的每一列也可以換成其它由 \(x\) 決定的特徵函數，讓「線性」規劃擁有更多的可能性。

想想以下問題：

  1. 考慮資料點 \((1,3)\), \((2,3)\), \((3,4)\), \((4,4)\)。
    1. 計算其線性迴歸的解，並用畫圖表示這些點及解出來的函數。
    2. 計算其二次多項式迴歸的解，並用畫圖表示這些點及解出來的函數。
  2. 考慮 \(\mathcal{H} = \vspan\{1, x, x^2\}\) 並使用上述內積。
    1. 對任意 \(p\in\mathbb{R}\)，定義 \(K_p(x) = 1 + px + p^2x^2\in\mathcal{H}\)。說明對任何 \(f(x)\in\mathcal{H}\) 都有 \(\inp{f(x)}{K_p(x)} = f(p)\)。
    2. 對任意 \(p,q\in\mathbb{R}\)，定義 \(K(p,q) = \inp{K_p(x)}{K_q(x)}\)。說明 \(K(p,q)\) 為正定函數，也就是對任何有限的 \(p_1, \ldots, p_N\in\mathbb{R}\) 來說，\(\begin{bmatrix} K(p_i,p_j) \end{bmatrix}\) 為一 \(N\times N\) 的正定矩陣。