＜机器学习＞＜白板推导系列＞＜三＞

• Note
• 最小二乘法
• • 概率角度
• 正则化
• • • L1 Lasso
    • L2 Ridge
    • • 频率角度
      • 贝叶斯角度

样本集
D = ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x i , y i ) , . . . , ( x N , y N ) x i ∈ R p , y i ∈ R X = ( x 1 , x 2 , . . . , x N ) T ∈ R N × p Y = ( y 1 , y 2 , . . . , y N ) T ∈ R N D=(x_1, y_1), (x_2, y_2), ..., (x_i, y_i), ..., (x_N, y_N)\ x_i in mathbb{R^p} , y_i in mathbb{R}\ X = (x_1, x_2, ..., x_N)^T in mathbb{R^{N times p}} \ Y = (y_1, y_2, ..., y_N)^T in mathbb{R^{N}} D=(x1​,y1​),(x2​,y2​),...,(xi​,yi​),...,(xN​,yN​)xi​∈Rp,yi​∈RX=(x1​,x2​,...,xN​)T∈RN×pY=(y1​,y2​,...,yN​)T∈RN

线性模型
y ^ = w T x i + b w ∈ R p , b ∈ R hat{y} = w^Tx_i + b\w in mathbb{R^p},b in mathbb{R} y^​=wTxi​+bw∈Rp,b∈R
损失函数 Loss function
L ( w ) = ∑ i = 1 N ∣ ∣ w T x i − y i ∣ ∣ 2 = ∑ i = 1 N ( w T x i − y i ) 2 = ( w T x 1 − y 1 , w T x 2 − y 2 , . . . , w T x N − y N ) ( w T x 1 − y 1 , w T x 2 − y 2 , . . . , w T x N − y N ) T L(w) = sum_{i=1}^{N}||w^Tx_i-y_i||^2= sum_{i=1}^{N}(w^Tx_i-y_i)^2 \=(w^Tx_1-y_1, w^Tx_2-y_2, ... , w^Tx_N-y_N)(w^Tx_1-y_1, w^Tx_2-y_2, ... , w^Tx_N-y_N)^T L(w)=i=1∑N​∣∣wTxi​−yi​∣∣2=i=1∑N​(wTxi​−yi​)2=(wTx1​−y1​,wTx2​−y2​,...,wTxN​−yN​)(wTx1​−y1​,wTx2​−y2​,...,wTxN​−yN​)T
存在：
( w T x 1 − y 1 , w T x 2 − y 2 , . . . , w T x N − y N ) = w T ( x 1 , x 2 , . . . , x N ) − ( y 1 , y 2 , . . . , y N ) = w T X T − Y T (w^Tx_1-y_1, w^Tx_2-y_2, ... , w^Tx_N-y_N)=w^T(x_1,x_2,...,x_N) - (y_1,y_2,...,y_N) = w^TX^T-Y^T (wTx1​−y1​,wTx2​−y2​,...,wTxN​−yN​)=wT(x1​,x2​,...,xN​)−(y1​,y2​,...,yN​)=wTXT−YT
所以：
L ( w ) = ( w T X T − Y T ) ( w T X T − Y T ) T = ( w T X T − Y T ) ( X W − Y ) = w T X T X w − w T X T Y − Y T X w + Y T Y L(w) = (w^TX^T-Y^T)(w^TX^T-Y^T)^T\=(w^TX^T-Y^T)(XW-Y)\=w^TX^TXw-w^TX^TY-Y^TXw+Y^TY L(w)=(wTXT−YT)(wTXT−YT)T=(wTXT−YT)(XW−Y)=wTXTXw−wTXTY−YTXw+YTY
因为：
w ∈ R p , X ∈ R N × p , Y ∈ R N w in mathbb{R^p},X in mathbb{R^{N times p}},Yin mathbb{R^{N}} w∈Rp,X∈RN×p,Y∈RN
则：
w T X T Y ∈ R , Y T X w ∈ R w^TX^TYin mathbb{R}, Y^TXwin mathbb{R} wTXTY∈R,YTXw∈R
那么：
L ( w ) = w T X T X w − w T X T Y − Y T X w + Y T Y = w T X T X w − 2 w T X T Y + Y T Y L(w) =w^TX^TXw-w^TX^TY-Y^TXw+Y^TY\=w^TX^TXw-2w^TX^TY+Y^TY L(w)=wTXTXw−wTXTY−YTXw+YTY=wTXTXw−2wTXTY+YTY
最小二乘估计LSE：
w ^ = a r g m i n L ( w ) ∂ L ( w ) ∂ w = 2 X T X w − 2 X T Y = 0 w ^ = ( X T X ) − 1 X T Y hat{w}=argmin L(w)\ frac{partial{L(w)}}{partial{w}}=2X^TXw-2X^TY=0\hat{w}=(X^TX)^{-1}X^TY w^=argminL(w)∂w∂L(w)​=2XTXw−2XTY=0w^=(XTX)−1XTY
其中
X + = ( X T X ) − 1 X T X^{+}=(X^TX)^{-1}X^T X+=(XTX)−1XT称作伪逆

设存在高斯分布噪声：
ϵ ∼ N ( 0 , σ 2 ) y ^ = w T x + ϵ epsilon sim mathcal{N}(0, sigma^2)\hat{y}=w^Tx+epsilon ϵ∼N(0,σ2)y^​=wTx+ϵ
则：
y ^ ∼ N ( w T x , σ 2 ) hat{y} sim mathcal{N}(w^Tx, sigma^2) y^​∼N(wTx,σ2)
似然likelihood：
L ( w ) = l o g P ( Y ∣ X ; w ) = log ⁡ ∏ i = 1 N P ( y i ∣ x i ; w ) = ∑ i = 1 N l o g P ( y i ∣ x i ; w ) L(w)=logP(Y|X;w)\=logprod_{i=1}^NP(y_i|x_i;w)\=sum_{i=1}^NlogP(y_i|x_i;w) L(w)=logP(Y∣X;w)=logi=1∏N​P(yi​∣xi​;w)=i=1∑N​logP(yi​∣xi​;w)
又：
p ( y ∣ x ; w ) = 1 σ 2 π ⋅ e x p ( − ( y − w T x ) 2 2 σ 2 ) p(y|x;w) = frac{1}{sigmasqrt{2pi}}cdot exp(-frac{(y-w^Tx)^2}{2sigma^2}) p(y∣x;w)=σ2π ​1​⋅exp(−2σ2(y−wTx)2​)
因此：
L ( w ) = ∑ i = 1 N l o g P ( y i ∣ x i ; w ) = ∑ i = 1 N l o g 1 σ 2 π ⋅ e x p ( − ( y i − w T x i ) 2 2 σ 2 ) = ∑ i = 1 N [ l o g ( 1 σ 2 π ) − ( y i − w T x i ) 2 2 σ 2 ] L(w)=sum_{i=1}^NlogP(y_i|x_i;w)\ =sum_{i=1}^N logfrac{1}{sigmasqrt{2pi}}cdot exp(-frac{(y_i-w^Tx_i)^2}{2sigma^2}) \ = sum_{i=1}^N left[log(frac{1}{sigmasqrt{2pi}}) - frac{(y_i-w^Tx_i)^2}{2sigma^2} right] L(w)=i=1∑N​logP(yi​∣xi​;w)=i=1∑N​logσ2π ​1​⋅exp(−2σ2(yi​−wTxi​)2​)=i=1∑N​[log(σ2π ​1​)−2σ2(yi​−wTxi​)2​]
那么，极大似然估计：
w ^ = arg max ⁡ w L ( w ) = arg max ⁡ w ∑ i = 1 N [ l o g ( 1 σ 2 π ) − ( y i − w T x i ) 2 2 σ 2 ] = arg min ⁡ w ∑ i = 1 N ( y i − w T x i ) 2 hat{w}=mathop{argmax_w}L(w)\=mathop{argmax_w}sum_{i=1}^N left[log(frac{1}{sigmasqrt{2pi}}) - frac{(y_i-w^Tx_i)^2}{2sigma^2} right] \=mathop{argmin_w} sum_{i=1}^N (y_i-w^Tx_i)^2 w^=wargmax​L(w)=wargmax​i=1∑N​[log(σ2π ​1​)−2σ2(yi​−wTxi​)2​]=wargmin​i=1∑N​(yi​−wTxi​)2
也就是说，最小二乘估计LSE <=> 极大似然估计 MSE (noise is Gaussian Distribution)

过拟合：

1. 增加数据量
2. 降维：特征选择/特征提取
3. 正则化

正则化框架：
arg min ⁡ w L ( w ) + λ P ( w ) mathop{argmin_w} L(w) + lambda P(w) wargmin​L(w)+λP(w)

P ( w ) = ∣ ∣ w ∣ ∣ 1 P(w) = ||w||_1 P(w)=∣∣w∣∣1​

P ( w ) = ∣ ∣ w ∣ ∣ 2 2 = w T w P(w) = ||w||_2^2=w^Tw P(w)=∣∣w∣∣22​=wTw
权值衰减
Ridge regression:
L ( w ) = ∑ i N ∣ ∣ w T x i − y i ∣ ∣ 2 2 + λ ∣ ∣ w ∣ ∣ 2 2 = ∑ i N ( w T x i − y i ) 2 + λ w T w = ( w T X T − Y T ) ( X w − Y ) + λ w T w = w T X T X w − 2 w T X T Y + Y T Y + λ w T w = w T ( X T X + λ I ) w − 2 w T X T Y + Y T Y L(w) = sum_i^N ||w^Tx_i-y_i||_2^2 + lambda ||w||_2^2\=sum_i^N (w^Tx_i-y_i)^2 + lambda w^Tw\=(w^TX^T-Y^T)(Xw-Y)+lambda w^Tw\=w^TX^TXw - 2w^TX^TY+Y^TY+lambda w^Tw\=w^T(X^TX+lambda I)w-2w^TX^TY+Y^TY L(w)=i∑N​∣∣wTxi​−yi​∣∣22​+λ∣∣w∣∣22​=i∑N​(wTxi​−yi​)2+λwTw=(wTXT−YT)(Xw−Y)+λwTw=wTXTXw−2wTXTY+YTY+λwTw=wT(XTX+λI)w−2wTXTY+YTY
那么
w ^ = arg min ⁡ w L ( w ) ∂ L ( w ) ∂ w = 2 ( X T X + λ I ) w − 2 X T Y = 0 w ^ = ( X T X + λ I ) − 1 X T Y hat{w}=mathop{argmin_w}L(w)\ frac{partial L(w)}{partial w}=2(X^TX+lambda I)w-2X^TY=0\ hat{w}=(X^TX+lambda I)^{-1}X^TY w^=wargmin​L(w)∂w∂L(w)​=2(XTX+λI)w−2XTY=0w^=(XTX+λI)−1XTY

设存在高斯分布噪声：
ϵ ∼ N ( 0 , σ 2 ) y ^ = w T x + ϵ epsilon sim mathcal{N}(0, sigma^2)\hat{y}=w^Tx+epsilon ϵ∼N(0,σ2)y^​=wTx+ϵ
则似然 P ( y ∣ x ; w ) P(y|x;w) P(y∣x;w)：
y ^ ∼ N ( w T x , σ 2 ) p ( y ∣ w ) = 1 σ 2 π exp ⁡ ( − ( y − w T x ) 2 2 σ 2 ) hat{y} sim mathcal{N}(w^Tx, sigma^2)\p(y|w)=frac{1}{sigma sqrt{2pi}}exp(-frac{(y-w^Tx)^2}{2sigma ^2}) y^​∼N(wTx,σ2)p(y∣w)=σ2π ​1​exp(−2σ2(y−wTx)2​)
设参数 w w w的先验分布满足：
w ∼ N ( 0 , σ w 2 ) p ( w ) = 1 σ w 2 π exp ⁡ ( − ∣ ∣ w ∣ ∣ 2 2 σ w 2 ) w sim mathcal{N}(0, sigma_{w}^2)\p(w)=frac{1}{sigma_{w}sqrt{2pi}}exp(-frac{||w||^2}{2sigma_{w}^2}) w∼N(0,σw2​)p(w)=σw​2π ​1​exp(−2σw2​∣∣w∣∣2​)
那么，后验分布为：
p ( w ∣ y ) = p ( y ∣ w ) p ( w ) p ( y ) p(w|y) = frac{p(y|w)p(w)}{p(y)} p(w∣y)=p(y)p(y∣w)p(w)​
最大似然估计MAP:
w ^ = arg max ⁡ w log ⁡ p ( w ∣ y ) = arg max ⁡ w log ⁡ ( p ( y ∣ w ) p ( w ) ) hat{w}=mathop{argmax_w} log p(w|y)\=mathop{argmax_w} log (p(y|w)p(w)) w^=wargmax​logp(w∣y)=wargmax​log(p(y∣w)p(w))
有：
p ( y ∣ w ) p ( w ) = 1 2 π σ σ w exp ⁡ ( − ( y − w T x ) 2 2 σ 2 − ∣ ∣ w ∣ ∣ 2 2 σ w 2 ) p(y|w)p(w)=frac{1}{2pisigma sigma_{w}} expleft(-frac{(y-w^Tx)^2}{2sigma^2}-frac{||w||^2}{2sigma_{w}^2}right) p(y∣w)p(w)=2πσσw​1​exp(−2σ2(y−wTx)2​−2σw2​∣∣w∣∣2​)
因此：
w ^ = arg max ⁡ w log ⁡ ∏ i = 1 N p ( y i ∣ w ) p ( w ) = arg max ⁡ w ∑ i = 1 N [ log ⁡ 1 2 π σ σ w − ( y i − w T x i ) 2 2 σ 2 − ∣ ∣ w ∣ ∣ 2 2 σ w 2 ] = arg min ⁡ w ∑ i = 1 N [ ( y i − w T x i ) 2 2 σ 2 + ∣ ∣ w ∣ ∣ 2 2 σ w 2 ] = arg min ⁡ w ∑ i = 1 N [ ( y i − w T x i ) 2 + σ 2 σ w 2 ∣ ∣ w ∣ ∣ 2 ] = arg min ⁡ w ∑ i = 1 N ( y i − w T x i ) 2 + ∑ i = 1 N σ 2 σ w 2 ∣ ∣ w ∣ ∣ 2 hat{w}=mathop{argmax_w} log prod_{i=1}^Np(y_i|w)p(w) =mathop{argmax_w} sum_{i=1}^Nleft[log frac{1}{2pisigma sigma_{w}} -frac{(y_i-w^Tx_i)^2}{2sigma^2}-frac{||w||^2}{2sigma_{w}^2}right]\=mathop{argmin_w}sum_{i=1}^Nleft[ frac{(y_i-w^Tx_i)^2}{2sigma^2}+frac{||w||^2}{2sigma_{w}^2}right]\=mathop{argmin_w}sum_{i=1}^Nleft[ (y_i-w^Tx_i)^2+frac{sigma^2}{sigma_{w}^2}||w||^2right]\=mathop{argmin_w}sum_{i=1}^N(y_i-w^Tx_i)^2+sum_{i=1}^Nfrac{sigma^2}{sigma_{w}^2}||w||^2 w^=wargmax​logi=1∏N​p(yi​∣w)p(w)=wargmax​i=1∑N​[log2πσσw​1​−2σ2(yi​−wTxi​)2​−2σw2​∣∣w∣∣2​]=wargmin​i=1∑N​[2σ2(yi​−wTxi​)2​+2σw2​∣∣w∣∣2​]=wargmin​i=1∑N​[(yi​−wTxi​)2+σw2​σ2​∣∣w∣∣2]=wargmin​i=1∑N​(yi​−wTxi​)2+i=1∑N​σw2​σ2​∣∣w∣∣2
Regularized LSE <=> MAP (noise is Gaussian distribution；prior is Gaussian distribution)