線性回歸|機器學習推導系列（三）

一、概述

假設有以下數據：

D=\left \{(x_{1},y_{1}),(x_{2},y_{2}),\cdots ,(x_{N},y_{N})\right \}\\ x_{i}\in \mathbb{R}^{p},y_{i}\in \mathbb{R},i=1,2,\cdots ,N\\ X=(x_{1},x_{1},\cdots ,x_{N})^{T}=\begin{pmatrix} x_{1}^{T}\\ x_{2}^{T}\\ \vdots \\ x_{N}^{T} \end{pmatrix}=\begin{pmatrix} x_{11} & x_{12} & \cdots &x_{1p} \\ x_{21} & x_{22}& \cdots &x_{2p} \\ \vdots & \vdots & \ddots &\vdots \\ x_{N1}& x_{N2} & \cdots & x_{Np} \end{pmatrix}_{N \times p}\\ Y=\begin{pmatrix} y_{1}\\ y_{2}\\ \vdots \\ y_{N} \end{pmatrix}_{N \times 1}

這些數據符合下圖關係（以一維數據為例），這裡的函數f(w)忽略了偏置b：

image.png

二、最小二乘估計

L(w)=\sum_{i=1}^{N}\left \| w^{T}x_{i}-y_{i}\right \|_{2}^{2}\\ =\sum_{i=1}^{N}(w^{T}x_{i}-y_{i})^{2}\\ =\underset{\underset{\underset{w^{T}X^{T}-Y^{T}}{\underbrace{w^{T}\begin{pmatrix} x_{1} & x_{2} & \cdots & x_{N} \end{pmatrix}-\begin{pmatrix} y_{1} & y_{2} & \cdots & y_{N} \end{pmatrix}}}}{\underbrace{\begin{pmatrix} w^{T}x_{1} & w^{T}x_{2} & \cdots & w^{T}x_{N} \end{pmatrix}-\begin{pmatrix} y_{1} & y_{2} & \cdots & y_{N} \end{pmatrix}}}}{\underbrace{\begin{pmatrix} w^{T}x_{1}-y_{1} & w^{T}x_{2}-y_{2} & \cdots & w^{T}x_{N}-y_{N} \end{pmatrix}}}\begin{pmatrix} w^{T}x_{1}-y_{1}\\ w^{T}x_{2}-y_{2}\\ \vdots \\ w^{T}x_{N}-y_{N} \end{pmatrix}\\ =(w^{T}X^{T}-Y^{T})(Xw-Y)\\ =w^{T}X^{T}Xw-w^{T}X^{T}Y-Y^{T}Xw+Y^{T}Y\\ =w^{T}X^{T}Xw-2w^{T}X^{T}Y+Y^{T}Y

接下來通過對w求導就可以解得參數w：

\hat{w}=argminL(w)\\ \frac{\partial L(w)}{\partial w}=2X^{T}Xw-2X^{T}Y=0\\ 得出w=\underset{X^{+}，偽逆}{\underbrace{(X^{T}X)^{-1}X^{T}}}Y

以上未考慮偏執b，如果考慮的話則可以為w添加一個維度，同時也為x添加一個維度並使得添加的維度的值為1，然後使用同樣的求解方法即可。.

三、線性回歸的幾何解釋

1. 每個樣本點的誤差的總和

使用最小二乘法可以看做損失函數是每個樣本的誤差的總和，每個樣本的誤差即是y_{i}與w^{T}x_{i}的差，如下圖所示：

image.png

2. Y在X的列空間上的投影

一組向量的生成子空間（span）是原始向量線性組合後所能抵達的點的集合。確定方程Ax=b是否有解，相當於確定向量b是否在A列向量的生成子空間中。這個特殊的生成子空間被稱為A的列空間（column space）或者A的值域（range）。

我們的目的是為了求解w使得Xw=Y，顯然這個方程一般是無解的，即Y一般不在X的列空間中，因為樣本點一般是散落在某條直線周圍，所有的樣本點準確地落在同一條直線上的情況少之又少。

對於Xw=f(w)，為了使f(w)與Y最接近，則f(w)就應該是Y在X的列空間中的投影，如下圖所示，以p=2為例：

image.png

Y-Xw就應該與每一個\begin{pmatrix} x_{1i}\\ x_{2i}\\ \vdots \\ x_{Ni} \end{pmatrix}都垂直，即X^{T}(Y-Xw)=0_{p\times1}，則可以直接解得w=(X^{T}X)^{-1}X^{T}Y。

四、最小二乘法與極大似然估計

可以認為實際值與估計值之間的差是一個高斯噪聲，即y和f(w)滿足關係y=f(w)+\varepsilon =w^{T}x+\varepsilon，其中\varepsilon是高斯噪聲，滿足\varepsilon\sim N(0,\sigma ^{2})，因此y|x;w\sim N(w^{T}x,\sigma ^{2})，即P(y|x;w)=\frac{1}{\sqrt{2\pi }\sigma }exp\left \{-\frac{(y-w^{T}x)^{2}}{2\sigma ^{2}}\right \}可以使用極大似然估計法來進行求解：

L(w)=logP(Y|X;w)\\ =log\prod_{i=1}^{N}P(y_{i}|x_{i};w)\\ =\sum_{i=1}^{N}logP(y_{i}|x_{i};w)\\ =\sum_{i=1}^{N}(log\frac{1}{\sqrt{2\pi }}+log\, exp\left \{-\frac{(y_{i}-w^{T}x_{i})^{2}}{2\sigma ^{2}}\right \})\\ =\sum_{i=1}^{N}(log\frac{1}{\sqrt{2\pi }}-\frac{(y_{i}-w^{T}x_{i})^{2}}{2\sigma ^{2}})\\ \hat{w}=\underset{w}{argmax}L(w)\\ =\underset{w}{argmax}\sum_{i=1}^{N}(log\frac{1}{\sqrt{2\pi }}-\frac{(y_{i}-w^{T}x_{i})^{2}}{2\sigma ^{2}})\\=\underset{w}{argmax}\sum_{i=1}^{N}-\frac{(y_{i}-w^{T}x_{i})^{2}}{2\sigma ^{2}}\\ =\underset{w}{argmin}\sum_{i=1}^{N}(y_{i}-w^{T}x_{i})^{2}\\ =\underset{w}{argmin}\sum_{i=1}^{N}\left \| w^{T}x_{i}-y_{i}\right \|_{2}^{2}\\ (最小二乘法)

可以看到最小二乘法與噪聲為高斯噪聲時的極大似然估計法是等價的。

五、線性回歸的正則化

1. 高維小樣本的問題

\hat{w}=(X^{T}X)^{-1}X^{T}Y

當樣本數N遠大於維度p時X^{T}X可逆，而當出現高維小樣本的情況即維度p大於樣本數N時，X^{T}X就不可逆，這種時候就容易出現過擬合的情況。

2. 處理過擬合的方法

面對上述過擬合的現象有一些解決方案，主要有\left\{\begin{matrix} 增加數據量\\ 特徵選擇/特徵提取\\ 正則化 \end{matrix}\right.

特徵選擇指的是根據某種規則去掉一些特徵來實現降維；特徵提取的方法例如主成分分析（PCA），也是實現降維；正則化的方法指給損失函數添加懲罰項來避免過擬合。

3. 正則化的方法

通過最小化J(w)=\underset{loss}{\underline{L(w)}}+\lambda \underset{penalty}{\underline{P(w)}}來實現正則化，主要有L1正則化和L2正則化（也叫嶺回歸、權重衰減）。

\left\{\begin{matrix} L1正則化(Lasso)：P(w)=\left \| w\right \|_{1}\\ L2正則化(Ridge)：P(w)=\left \| w\right \|_{2}^{2} \end{matrix}\right.

下面為L2正則化的求解過程：

J(w)=L(w)+\lambda P(w)\\ =(w^{T}X^{T}-Y^{T})(Xw-Y)+\lambda w^{T}w\\ =w^{T}X^{T}Xw-2w^{T}X^{T}Y+Y^{T}Y+\lambda w^{T}w\\ =w^{T}(X^{T}X+\lambda I)w-2w^{T}X^{T}Y+Y^{T}Y\\ \hat{w}=\underset{w}{argmin}J(w)\\ \frac{\partial J(w)}{\partial w}=2(X^{T}X+\lambda I)w-2X^{T}Y=0\\ \hat{w}=(X^{T}X+\lambda I)^{-1}X^{T}Y

半正定矩陣X^{T}X加上對角矩陣\lambda I一定是可逆的，可以解決X^{T}X可能不可逆帶來的問題。

六、最小二乘法與最大後驗估計

1. 已知

仍然認為實際值與估計值之間的差是一個高斯噪聲，即y和f(w)滿足關係:

y=f(w)+\varepsilon =w^{T}x+\varepsilon \\ 其中\varepsilon是高斯噪聲，滿足\varepsilon\sim N(0,\sigma ^{2})\\ 因此y|x;w\sim N(w^{T}x,\sigma ^{2})，即P(y|x;w)=\frac{1}{\sqrt{2\pi }\sigma }exp\left \{-\frac{(y-w^{T}x)^{2}}{2\sigma ^{2}}\right \}

另外假設參數w的服從先驗分佈：

w\sim N(0,\sigma _{0}^{2})，即P(w)=\frac{1}{\sqrt{2\pi }\sigma_{0}}exp\left \{-\frac{\left \| w\right \|_{2}^{2}}{2\sigma _{0}^{2}}\right \}\\ 後驗概率為P(w|Y)=\frac{P(Y|w)P(w)}{P(Y)}(這裡的Y指Y|X，為書寫簡單而省略。)

2. 最大後驗估計法求解參數w

\hat{w}=\underset{w}{argmax}P(w|Y)\\ =\underset{w}{argmax}\frac{P(Y|w)P(w)}{P(Y)}\\ =\underset{w}{argmax}P(Y|w)P(w)\\ =\underset{w}{argmax}\, logP(Y|w)P(w)\\ =\underset{w}{argmax}\, log\prod_{i=1}^{N}P(y_{i}|w)P(w)\\ =\underset{w}{argmax}\sum_{i=1}^{N}logP(y_{i}|w)P(w)\\ =\underset{w}{argmax}\sum_{i=1}^{N}log(\frac{1}{\sqrt{2\pi }\sigma}\frac{1}{\sqrt{2\pi }\sigma_{0}}exp\left \{-\frac{(y-w^{T}x)^{2}}{2\sigma ^{2}}-\frac{\left \| w\right \|_{2}^{2}}{2\sigma _{0}^{2}}\right \})\\ =\underset{w}{argmax}\sum_{i=1}^{N}(log\frac{1}{\sqrt{2\pi }\sigma}\frac{1}{\sqrt{2\pi }\sigma_{0}}+log\, exp\left \{-\frac{(y-w^{T}x)^{2}}{2\sigma ^{2}}-\frac{\left \| w\right \|_{2}^{2}}{2\sigma _{0}^{2}}\right \})\\ =\underset{w}{argmax}\sum_{i=1}^{N}(-\frac{(y-w^{T}x)^{2}}{2\sigma ^{2}}-\frac{\left \| w\right \|_{2}^{2}}{2\sigma _{0}^{2}})\\ =\underset{w}{argmin}\sum_{i=1}^{N}(\frac{(y-w^{T}x)^{2}}{2\sigma ^{2}}+\frac{\left \| w\right \|_{2}^{2}}{2\sigma _{0}^{2}})\\ =\underset{w}{argmin}\sum_{i=1}^{N}(\underset{LSE}{\underbrace{(y-w^{T}x)^{2}}}+\underset{\lambda }{\underbrace{\frac{\sigma ^{2}}{\sigma _{0}^{2}}}}\left \| w\right \|_{2}^{2})

可以看到正則化的最小二乘法與噪聲為高斯噪聲且先驗也是高斯分佈時的最大後驗估計法是等價的。

 3. 總結

LSE\Leftrightarrow MLE(noise為Gaussian Distribution)\\ Regularized \: LSE\Leftrightarrow MAP(noise、prior為Gaussian Distribution)

Tags:

VirMach 便宜 VPS

QNews

QNews