EdX-Columbia機器學習課第3講筆記：最小二乘II、嶺回歸

05-13

最小二乘法的概率解釋

對於多元高斯分布，假設協方差矩陣 $Sigma = sigma^2 I$ ，概率密度為

$p(y|mu, sigma^2) = frac{1}{(2pi sigma^2)^{frac{n}{2}}}expleft(-frac{1}{2sigma^2}(y-mu)^T(y-mu) ight)$

假設 $mu = Xw$ ，求解 $w$ 的最大似然，會得到什麼？實際上還是求解

$hat{w}_{ m ML} = mathop{ m arg}max_w - frac{1}{2sigma^2} |!|y-Xw|!|^2$

即最小二乘和最大似然的解是一樣的

最大似然隱含的意思在於，誤差 $epsilon_i = y_i - x_i^Tw$ 是獨立的高斯雜訊，等價於以下三種說法：

$y_i = x_i^Tw + epsilon_i, epsilon_i mathop{sim}^{iid}N(0,sigma^2), i = 1,ldots,n$

$y_i mathop{sim}^{ind} N(x_i^Tw, sigma^2), i = 1, ldots, n$

$y sim N(Xw, sigma^2I)$

如果我們假設了有 $y sim N(Xw, sigma^2I)$ ，根據此分布，我們可以計算最大似然解的期望，有

$egin{aligned}mathbb{E}[w_{ m ML}] &= mathbb{E}[(X^TX)^{-1}X^Ty] ({ m analytical solution of least squares}) \&= int [(X^TX)^{-1}X^Ty]p(y|X,w)dy { m( expectation of continuous random variable is }E[g(X)] = int_{-infty}^{infty} g(x)f_X(x)dx)\&= (X^TX)^{-1}X^Tint yp(y|X,w)dy \&= (X^TX)^{-1}X^Tmathbb{E}[y] \&= (X^TX)^{-1}X^TXw (y sim N(Xw, sigma^2I)) \&= wend{aligned}$

即最大似然估計 $w_{ m ML}$ 是 $w$ 的一個無偏估計。但是要考慮到還有方差的存在，如果方差很大的話，即便期望是無偏的，也很可能會看到比較奇怪的值，因此需要對方差做一個判斷。

如果有 $y sim N(mu, Sigma)$ ，則

${ m var}[y] = mathbb{E}[(y-mathbb{E}[y])(y-mathbb{E}[y])^T] = Sigma$

代入 $mathbb{E}[y] = mu$ ，有

$egin{aligned}{ m var}[y] &= mathbb{E}[(y-mu)(y-mu)^T] \&= mathbb{E}[yy^T - ymu^T - mu y^T + mumu^T] \&= mathbb{E}[yy^T] - mathbb{E}[y]mu^T - mu mathbb{E}[y^T] + mumu^T \&= mathbb{E}[yy^T] - mumu^T - mu mu^T + mumu^T \&= mathbb{E}[yy^T] - mumu^Tend{aligned}$

即 $mathbb{E}[yy^T] = Sigma + mumu^T$

因此可以計算 $w$ 的方差，即

$egin{aligned}{ m var}[w_{ m ML}] &= mathbb{E}[(w_{ m ML}-mathbb{E}[w_{ m ML}])(w_{ m ML}-mathbb{E}[w_{ m ML}])^T] \&= mathbb{E}[w_{ m ML}w_{ m ML}^T] - mathbb{E}[w_{ m ML}]mathbb{E}[w_{ m ML}]^Tend{aligned}$

由於 $w = (X^TX)^{-1}X^Ty$ 且 $mathbb{E}[w_{ m ML}] = w$ ，而且 $(X^TX)$ 是對稱矩陣，其逆也是對稱矩陣，因此 $((X^TX)^{-1})^T = (X^TX)^{-1}$ 。帶入到上面可知

$egin{aligned}{ m var}[w_{ m ML}] &= mathbb{E}[(X^TX)^{-1}X^Tyy^TX(X^TX)^{-1}]-ww^T \&= (X^TX)^{-1}X^Tmathbb{E}[yy^T]X(X^TX)^{-1} - ww^Tend{aligned}$

由於 $mathbb{E}[yy^T] = Sigma + mumu^T$ 且 $y sim N(Xw, sigma^2I)$ ，即 $mu = Xw, Sigma = sigma^2 I$ ，因此

$egin{aligned}{ m var}[w_{ m ML}] &= (X^TX)^{-1}X^Tmathbb{E}[yy^T]X(X^TX)^{-1} - ww^T \&= (X^TX)^{-1}X^T (Sigma + mumu^T) X(X^TX)^{-1} - ww^T \&= (X^TX)^{-1}X^T (sigma^2I + Xww^TX^T) X(X^TX)^{-1} - ww^T \&= (X^TX)^{-1}X^Tsigma^2IX(X^TX)^{-1} + (X^TX)^{-1}X^TXww^TX^TX(X^TX)^{-1}- ww^Tend{aligned}$

由於 $sigma^2$ 是標量可以提出來，因此上式可以化簡為

${ m var}[w_{ m ML}] = sigma^2(X^TX)^{-1}$

因此在如果我們假設 $y$ 滿足高斯分布，即 $y sim N(Xw, sigma^2I)$ ，就有

$mathbb{E}[w_{ m ML}] = w, { m var}[w_{ m ML}] = sigma^2(X^TX)^{-1}$

如果 $sigma^2(X^TX)^{-1}$ 太大，那麼 $w_{ m ML}$ 就會敏感於 $y$ 的值，不利於用其做預測

嶺回歸

由於方差的存在， $w$ 可能會變得很大，而這是我們所不希望看到的。因此可以在目標函數上加一個正則項來控制 $w$ 的大小，即類似下式這樣的形式：

$w_{ m OPT} = { m arg}min_w |!|y-Xw|!|^2 + lambda g(w)$

其中 $lambda > 0$ 是正則化參數， $g(w) > 0$ 是懲罰函數，將 $w$ 引向所希望的性質。具體地，對於嶺回歸，有

$w_{ m RR} = { m arg}min_w |!|y-Xw|!|^2 + lambda |!|w|!|^2$

其中 $g(w) = |!|w|!|^2$ 對大的 $w$ 進行了懲罰。注意到目標函數的第二項和第一項之間存在著平衡關係，由 $lambda$ 控制。如果 $lambda ightarrow 0$ ，則 $w_{ m RR} ightarrow w_{ m LS}$ ；如果 $lambda ightarrow infty$ ，則 $w_{ m RR} ightarrow 0$

求解析解可得

$egin{aligned}mathcal{L} &= |!|y-Xw|!|^2 + lambda |!|w|!|^2 \&= (y - Xw)^T(y-Xw) + lambda w^Tw \ abla_w mathcal{L} &= -2X^Ty + 2X^TXw + 2lambda w = 0 \Rightarrow w_{ m RR} &= (lambda I + X^TX)^{-1}X^Tyend{aligned}$

使用嶺回歸之前需要對數據先做預處理：

$egin{aligned}y &leftarrow y - frac{1}{n}sum_{i=1}^n y_i \x_{ij} &leftarrow frac{x_{ij} - ar{x}_{.j}}{hat{sigma}_j} \hat{sigma}_j & = sqrt{frac{1}{n} sum_{i=1}^n (x_{ij} - ar{x}_{.j})^2}end{aligned}$

對嶺回歸的進一步分析

可以通過奇異值分解SVD來進一步探索最小二乘法和嶺回歸之間的關係。SVD的核心理論是對於任何 $n imes d$ 矩陣 $X$ （假設 $n>d$ ），都可以將其分解為 $X=USV^T$ ，其中

$U: n imes d$ 正交矩陣，即 $U^TU=I$
$S: d imes d$ 非負對角矩陣，即 $S_{ii}ge 0$ 且對 $i ot= j$ 有 $S_{ij} = 0$
$V: d imes d$ 正交矩陣，即 $V^TV = VV^T = I$

因此可以得出以下等式

$egin{aligned}&X^TX = (USV^T)^T(USV^T) = VS^2V^T, XX^T = US^2U^T \&(X^TX)^{-1} = (VS^2V^T)^{-1} = VS^{-2}V^Tend{aligned}$

因此 $w$ 的方差可以重寫為

${ m var}[w_{ m LS}] = sigma^2(X^TX)^{-1} = sigma^2VS^{-2}V^T$

如果對某個 $i$ ， $S_{ii}$ 特別小，那麼其逆會特別大，導致方差變大（這說明 $X$ 中的一些列有很高的相關性）

同時，對新的數據進行最小平方預測，結果為

$y_{ m new} = x_{ m new}^Tw_{ m LS} = x_{ m new}^T(X^TX)^{-1}X^Ty = x_{ m new}^TVS^{-1}U^Ty$

也可以看出來如果 $S^{-1}$ 很大，則預測結果會不穩定

可以推導出最小二乘得出的權重和嶺回歸得出的權重之間的關係：

$egin{aligned}w_{ m RR} &= (lambda I + X^TX)^{-1}X^Ty \&= (lambda I + X^TX)^{-1}(X^TX)(X^TX)^{-1}X^Ty \&= (lambda I + X^TX)^{-1}(X^TX)w_{ m LS} \&= [(X^TX)(lambda(X^TX)^{-1} + I)]^{-1}(X^TX)w_{ m LS}end{aligned}$

由於對於兩個對稱矩陣有 $(AB)^{-1} = B^{-1}A^{-1}$ ，因此

$egin{aligned}w_{ m RR} &= [(X^TX)(lambda(X^TX)^{-1} + I)]^{-1}(X^TX)w_{ m LS} \&= (lambda(X^TX)^{-1} + I)^{-1}(X^TX)^{-1}(X^TX)w_{ m LS} \&= (lambda(X^TX)^{-1} + I)^{-1}w_{ m LS}end{aligned}$

代入奇異值分解的結果，且考慮 $VV^T=I$ ，有

$egin{aligned}w_{ m RR} &= (lambda(X^TX)^{-1} + I)^{-1}w_{ m LS} \&= (lambda VS^{-2}V^T + I)^{-1}w_{ m LS} \&= (V(lambda S^{-2}V^T+V^T))^{-1}w_{ m LS} \&= (V(lambda S^{-2} + I)V^T)^{-1}w_{ m LS} \&= V(lambda S^{-2} + I)^{-1}V^Tw_{ m LS} \&:= VMV^Tw_{ m LS}end{aligned}$

其中 $M_{ii} = frac{S_{ii}^2}{lambda + S_{ii}^2}$

也可以把奇異值分解的結果帶入到 $w_{ m LS}$ 的求解中

$egin{aligned}w_{ m LS} &= (X^TX)^{-1}X^Ty \&= VS^{-2}V^TVS^TU^Ty \&= VS^{-2}SU^Ty \&= VS^{-1}U^Tyend{aligned}$

代入到上式，有

$w_{ m RR} = VS_{lambda}^{-1}U^Ty, S_{lambda}^{-1} = left[!egin{array}{rrr} frac{S_{11}}{lambda+S_{11}^2}&&0\ &ddots&\ 0&&frac{S_{dd}}{lambda+S_{dd}^2} end{array}! ight]$

嶺回歸也可以看作是最小二乘的一個特例情況。如果如下定義 $hat{y} approx hat{X}w$ ，即

$left[egin{array}{c} y \ 0 \ vdots \ 0 end{array} ight] approx left[egin{array}{ccc} - & X & - \ sqrt{lambda} & & 0 \ & ddots & \ 0 & & sqrt{lambda} end{array} ight] left[egin{array}{c} w_1 \ vdots \ w_d end{array} ight]$

如果對這個回歸問題求解 $w_{ m LS}$ ，則找到了原始回歸問題的 $w_{ m RR}$

$egin{aligned}(hat{y} - hat{X}w)^T(hat{y} - hat{X}w) &= (y-Xw)^T(y-Xw) + (sqrt{lambda}w)^T(sqrt{lambda}w) \&= |!|y-Xw|!|^2 + lambda |!|w|!|^2end{aligned}$
推薦閱讀：

※為什麼要使用向量化？（從時間上看）
※機器學習演算法
※技術宅如何進化為女裝大佬
※深入機器學習系列17-BFGS & L-BFGS
※過擬合與正則化

TAG:機器學習 |