標籤：

機器學習線性回歸

EdX-Columbia機器學習課第6講筆記：稀疏線性回歸

05-09

引子：欠定線性等式 (underdetermined linear equations)

這裡考慮的是 $y = Xw, X in mathbb{R}^{n imes d} (d >!!> n)$ 的問題。即數據集的維數大於樣本數。此時 $w$ 有無窮多個解滿足 $y = Xw$ 。在這些解中， $w_{ m ln} = X^T(XX^T)^{-1}y$ 佔據著一個重要的地位。如果把這個解加上一個 $X$ 的零空間 $mathcal{N}$ 中的向量 $delta in mathbb{R}^d$ ，得到的新的權重仍然是原始問題的解。

$delta in mathcal{N}(X) Rightarrow Xdelta = 0 land delta ot= 0 \ herefore X(w_{ m ln} + delta) = Xw_{ m ln} + Xdelta = y + 0$

而因為 $d > n$ ，因此 $delta$ 可以有無限多個。

下面用兩種方法證明 $w_{ m ln}$ 是這些解里 $ell_2$ 範數最小的解，即

$w_{ m ln} = { m arg}min_w |!|w|!|^2 { m subject to} Xw = y$

分析法

令 $w$ 是 $Xw=y$ 的另一個解，因此 $X(w-w_{ m ln}) = 0$ ，且有

$egin{aligned}(w - w_{ m ln})^Tw_{ m ln} &= (w - w_{ m ln})^TX^T(XX^T)^{-1}y \&= (X(w - w_{ m ln}))^T(XX^T)^{-1}y = 0end{aligned}$

即 $w-w_{ m ln}$ 正交於 $w_{ m ln}$ ，這意味著

$egin{aligned}|!|w|!|^2 &= |!|w - w_{ m ln} + w_{ m ln}|!|^2 \&= |!|w - w_{ m ln}|!|^2 + |!|w_{ m ln}|!|^2 + 2(w - w_{ m ln})^Tw_{ m ln} \&= |!|w - w_{ m ln}|!|^2 + |!|w_{ m ln}|!|^2 \&> |!|w_{ m ln}|!|^2end{aligned}$

$lacksquare$

Lagrange乘子法

為了求解

${ m arg}min_w |!|w|!|^2 { m subject to} Xw = y$

可以引入Lagrange乘子，即

$mathcal{L}(w, eta) = w^Tw + eta^T(Xw - y)$

分別對 $w$ 和 $eta$ 求導，得到兩個條件

$abla_w mathcal{L} = 2w + X^Teta = 0, abla_{eta}mathcal{L} = Xw - y = 0$

由第一個式子可知

$w = -X^Teta / 2$

代入到第二個式子解得

$eta = -2(XX^T)^{-1}y$

將 $eta$ 代回第一個式子

$w_{ m ln} = X^T(XX^T)^{-1}y$

$lacksquare$

稀疏回歸

普通最小二乘和嶺回歸通常只用於理想情況。現實問題中，通常有很多特徵，而其中只有一部分與 $y$ 相關，非常重要，而普通最小二乘和嶺回歸對所有特徵都是同等對待，重要的特徵會被不重要的特徵拉低

通常來講，優化問題都可以抽象為公式

${ m total cost} = { m goodness of fit term} + { m penalty term}$

前者說明模型 $f$ 對數據的近似有多好，後者使得最後的解不會那麼「重」。嶺回歸的懲罰項是 $|!|w|!|^2$ ，而這個懲罰項的特點是，如果 $w$ 很大，那麼縮小它能夠很快地縮小懲罰項；然而如果 $w$ 小，那麼縮小它的效果就不顯著。因此使用這個懲罰項的結果是所有特徵的權重都小了

稀疏學習的目的是選出 $d$ 維特徵的一個子集作為模型，而篩掉其它維度的特徵，也就是把不重要的特徵權重設為0。常用線性懲罰項——引出了LASSO

LASSO: Least Absolute Shrinkage and Selection Operator，使用 $ell_1$ 正則項

$w_{ m lasso} = { m arg}min_w |!|y - Xw|!|^2_2 + lambda |!|w|!|_1 \|!|w|!|_1 = sum_{j=1}^d |w_j|$

正則化可以推廣到 $ell_p$ 正則化回歸，即

$w_{ell_p} = { m arg}min_w |!|y - Xw|!|^2_2 + lambda |!|w|!|_p^p \|!|w|!|_p^p = left(sum_{j=1}^d |w_j|^p ight)^{frac{1}{p}}$

其中 $ell_1$ 正則化是LASSO， $ell_2$ 正則化是嶺回歸

當 $p = infty$ 時，懲罰項只懲罰最大的那一項， $|!|w|!|_infty = max_j |w_j|$

當 $1 < p < 2$ 時，可以找到最優解，但是只能通過迭代方式解出（沒有解析解）

當 $0 < p < 1$ 時，只能找到近似解，不過可以保證稀疏性

當 $p ightarrow 0$ 時，只記錄某一項是否為0，即 $|!|w|!|_0 = sum_j mathbb{I}{w_j ot= 0}$

推薦閱讀：

※機器學習入門之旅（三）線性模型之線性回歸與最小二乘法
※【線上直播】線性回歸——求解介紹及回歸拓展
※簡單線性回歸、邏輯回歸和泰坦尼克號的生存預測
※簡單線性回歸和邏輯回歸（五）
※機器學習入門（1）：線性回歸

TAG:機器學習 | 線性回歸 |