机器学习 [白板推导]（二）[线性回归]

3. 线性回归

3.1. 问题定义

  假设两个变量 $\vec{x}$ 和 $y$ 之间存在线性关系（例如 $y={\vec{w}}^T\vec{x}+b$），如何利用数据 $Data:\{({\vec{x}}_i,y_i){\}}_{i=1}^N$ 拟合出这个线性关系，使得可以对新的样本 ${\vec{x}}_{N+1}$ 回归得到其对应的 $y_{N+1}$ .
  为了便于推导，将样本表示为增广自变量矩阵 ${\hat{X}}_{N\times (p+1)}=(\begin{array}{cccc}{\hat{\vec{x}}}_1& {\hat{\vec{x}}}_2& \cdots & {\hat{\vec{x}}}_n\end{array}{)}^T=(\begin{array}{cccc}\left[\begin{array}{c}1\\ {\vec{x}}_1\end{array}\right]& \left[\begin{array}{c}1\\ {\vec{x}}_2\end{array}\right]& \cdots & \left[\begin{array}{c}1\\ {\vec{x}}_n\end{array}\right]\end{array}{)}^T$ 和 对应的因变量矩阵 $Y_{N\times 1}=(\begin{array}{cccc}{y}_1& y_2& \cdots & y_n\end{array})$，则根据线性假设，存在参数矩阵 $W_{(p+1)\times 1}$ 使得 $Y=\hat{X}W$（也可以表示为 $y_i={\hat{\vec{x}}}_i^{T}W$）. 因此该问题可以定义为求解最优参数矩阵 $\hat{W}$.

3.2. 问题求解

3.2.1. 最小二乘法求解

  根据最小二乘法，将损失函数定义为均方误差：
$${\mathcal{L}}_{MSE}(W)=\Vert \hat{X}W-Y\Vert =\sum _{i=1}^N({\hat{\vec{x}}}_i^{T}W-y_i{)}^2,\text{\hspace{1em}(3.1)}$$

则优化问题表示为
$$\hat{W}=\underset{W}{\mathrm{argmin}}{\mathcal{L}}_{MSE}(W).\text{\hspace{1em}(3.2)}$$

  要求出解析解，需要先将问题定义表示为矩阵计算，即：
$$\begin{array}{rl}{\mathcal{L}}_{MSE}(W)& =(W^T{\hat{X}}^T-Y^T)(\hat{X}W-Y)\\ & =W^T{\hat{X}}^T\hat{X}W-2W^T{\hat{X}}^{T}Y+Y^{T}Y,\end{array}\text{\hspace{1em}(3.3)}$$

将其对参数求导得：
$$\frac{\partial {\mathcal{L}}_{MSE}}{\partial W}=2{\hat{X}}^T\hat{X}W-2{\hat{X}}^{T}Y,\text{\hspace{1em}(3.4)}$$

令其为0，可得
$$\hat{W}=({\hat{X}}^T\hat{X}{)}^{-1}{X}^{T}Y=X^{†}Y\text{\hspace{1em}(3.5)}$$

其中 $X^{†}=({\hat{X}}^T\hat{X}{)}^{-1}{X}^T$ 被称为 $\hat{X}$ 的伪逆。

3.2.2. 概率角度求解

  从概率角度认为，数据中存在随机误差，表示为 $y={\hat{\vec{x}}}^{T}W+ϵ$. 其中 $ϵ$ 为误差项，遵从某种概率分布。假设误差项遵从的是高斯分布，则可以定义变量的概率分布为：
$$\begin{array}{rl}ϵ& \sim N(0,{\sigma }^2),\\ y|{\hat{\vec{x}}}^{T}W& \sim N({\hat{\vec{x}}}^{T}W,{\sigma }^2).\end{array}\text{\hspace{1em}(3.6)}$$

  使用最大似然估计法求解参数，似然函数为：
$$\begin{array}{rl}{\mathcal{L}}_{MLE}(W)& =\sum _{i=1}^N\log [p(y_i|\hat{\vec{x}};W)]\\ & =N\log (\frac{1}{\sqrt{2\pi }\sigma })-\frac{1}{2{\sigma }^2}\sum _{i=1}^N(y_i-{\hat{\vec{x}}}_i^{T}W{)}^2,\end{array}\text{\hspace{1em}(3.7)}$$

因此优化目标变成了$\hat{W}=\underset{W}{\mathrm{argmin}}{\mathcal{L}}_{MLE}(W)=\underset{W}{\mathrm{argmin}}{\sum }_{i=1}^N(y_i-{\hat{\vec{x}}}_i^{T}W{)}^2$，与最小二乘法相同，可以使用式（3.5）求解。

3.3. 正则化

3.3.1. 为什么要正则化

  从前面的推论可以知道参数矩阵的解析解，一般来说，但当样本量较小时，可能导致 ${\hat{X}}^T\hat{X}$ 不可逆，无法求出解析解。从拟合情况看，如果不能满足 $N\gg p$，则相较于维数来说样本不足，容易导致过拟合问题，对于过拟合情况可以用三种方法：

• 采集更多数据；
• 特征选择/特征提取（PCA，见本文第5.3节）
• 正则化（本节介绍）

3.3.2. 范数介绍

  一般地，一个向量 $L_p$ 的范数可以定义为 ${\Vert \vec{x}\Vert }_p=\sqrt[p]{{\sum }_{i=1}^m{\left|x_i\right|}^p}$。

• L1范数：Lasso，即为向量各元素的绝对值之和；
• L2范数：Ridge，${\Vert \vec{x}\Vert }_2=\sqrt[2]{{\sum }_{i=1}^m{\left|x_i\right|}^2}={\vec{x}}^T\vec{x}$；

3.3.3. L2正则化

  正则化的框架：
$$\mathcal{J}(W)=\mathcal{L}(W)+\lambda P(W),\text{\hspace{1em}(3.8)}$$

即在原有损失函数上加上一个正则化惩罚；
  对于L2正则化，则对应的惩罚项为 $W^{T}W$，而优化函数即为：
$$\mathcal{J}(W)=\mathcal{L}(W)+\lambda W^{T}W,\text{\hspace{1em}(3.9)}$$

这个优化函数也被称为岭回归；
  对式（3.9）进行化简和求导（同第3.2.1.节）可以得到新的解析解：
$$\hat{W}=({\hat{X}}^T\hat{X}+\lambda I{)}^{-1}{X}^{T}Y,\text{\hspace{1em}(3.9)}$$

解决了前面提到的不可逆的问题。

3.3.4. 从贝叶斯角度理解线性回归和L2正则化

  从贝叶斯派的角度求解线性回归问题，则是已知 $X$ 的分布 $p(\vec{x})$ 和 $Y$ 的分布 $p(y)$，对于参数矩阵假设一个先验分布 $p(W)$，采用最大后验估计法求解：
$$\hat{W}=\underset{W}{\mathrm{argmax}}p(W|y).\text{\hspace{1em}(3.10)}$$

  假设参数矩阵服从正态分布，即 $W\sim \mathcal{N}(\vec{0},{\Sigma }_0)$，则根据贝叶斯公式计算后验概率：$p(W|y)=\frac{p(y|W)\cdot p(W)}{p(y)}$，因为 $p(y)$ 不随参数变化，所以
W ^ = arg max ⁡ W p ( W ∣ y ) = arg max ⁡ W { p ( y ∣ W ) ⋅ p ( W ) p ( y ) } = arg max ⁡ W { p ( y ∣ W ) ⋅ p ( W ) } . (3.11) \begin{aligned}\hat{W}&=\argmax_Wp(W|y)\\ &=\argmax_W\left \{\frac{p(y|W)\cdot p(W)}{p(y)} \right \}\\ &=\argmax_W\left \{p(y|W)\cdot p(W)\right \}.\end{aligned}\tag{3.11} W^​=Wargmax​p(W∣y)=Wargmax​{p(y)p(y∣W)⋅p(W)​}=Wargmax​{p(y∣W)⋅p(W)}.​(3.11)

根据式（3.6），因为 $p(\vec{x})$ 已知，所以也可以写作：
$$y|W\sim N(\hat{\vec{x}}W,{\sigma }^{2}I),\text{\hspace{1em}(3.12)}$$

因此联立参数矩阵 $W$ 的概率密度函数，可得：
$$p(y|W)\cdot p(W)=\frac{1}{\sqrt{2\pi }{\sigma }^2}\frac{1}{\sqrt{2\pi }{\sigma }_0^2}\cdot \exp \left\{-\frac{(y-{\hat{\vec{x}}}^{T}W{)}^T(y-{\hat{\vec{x}}}^{T}W)}{2{\sigma }^2}-\frac{W^T{\Sigma }_0^{-1}W}{2}\right\}\text{\hspace{1em}(3.13)}$$

  当 ${\Sigma }_0={\sigma }_0^{2}I$（即方差各向同性）时，有 $\frac{W^T{\Sigma }_0^{-1}W}{2}=\frac{W^{T}W}{2{\sigma }_0^2}=\frac{{\Vert W\Vert }^2}{2{\sigma }_0^2}$，因此：
W ^ = arg max ⁡ W { p ( W ∣ y ) } = arg max ⁡ W { p ( y ∣ W ) ⋅ p ( W ) } = arg max ⁡ W { log ⁡ ( p ( y ∣ W ) ⋅ p ( W ) ) } = arg max ⁡ W { ( y − x ⃗ ^ T W ) T ( y − x ⃗ ^ T W ) 2 σ 2 + W T W 2 σ 0 2 } = arg max ⁡ W { ( y − x ⃗ ^ T W ) T ( y − x ⃗ ^ T W ) + σ 2 σ 0 2 W T W } , (3.14) \begin{aligned}\hat{W}&=\argmax_W\left \{p(W|y) \right \}\\ &=\argmax_W\left \{ p(y|W)\cdot p(W)\right \} \\ &=\argmax_W\left \{\log( p(y|W)\cdot p(W))\right \} \\ &=\argmax_W\left \{\frac{(y-\hat{\vec{x}}^TW)^T(y-\hat{\vec{x}}^TW)}{2\sigma^2}+\frac{W^TW}{2\sigma_0^2} \right \} \\ &=\argmax_W\left \{(y-\hat{\vec{x}}^TW)^T(y-\hat{\vec{x}}^TW)+\frac{\sigma^2}{\sigma_0^2}W^TW\right \},\end{aligned}\tag{3.14} W^​=Wargmax​{p(W∣y)}=Wargmax​{p(y∣W)⋅p(W)}=Wargmax​{log(p(y∣W)⋅p(W))}=Wargmax​{2σ2(y−x ^TW)T(y−x ^TW)​+2σ02​WTW​}=Wargmax​{(y−x ^TW)T(y−x ^TW)+σ02​σ2​WTW},​(3.14)

此时的优化函数和L2正则化是相同的，只是将 $\lambda$ 替换为了 $\frac{{\sigma }^2}{{\sigma }_0^2}$.

  若取消方差各向同性假设，使用全量数据求解参数矩阵：
$$\begin{array}{rl}P(W|X,Y)& \propto \exp \left\{-\frac{1}{2{\sigma }^2}(Y-XW{)}^T(Y-XW)-\frac{1}{2}{W}^T{\Sigma }_0^{-1}W\right\}\\ & =\exp \left\{-\frac{1}{2{\sigma }^2}(Y^{T}Y-2Y^{T}XW+W^T{X}^{T}XW)-\frac{1}{2}{W}^T{\Sigma }_0^{-1}W\right\}\\ & \propto \exp \left\{\underset{\text{Quadratic term}}{\underbrace{-\frac{1}{2}\left[W^T({\sigma }^{-2}{X}^{T}X+{\Sigma }_0^{-1})W\right]}}+\underset{\text{Linear term}}{\underbrace{[{\sigma }^{-2}{Y}^{T}XW]}}\right\},\end{array}\text{\hspace{1em}(3.15)}$$

其中Quadratic term表示变量的二次项，Linear term表示变量的一次项。
  另一方面，将式（2.3）（高斯分布PDF标准形式，见另一篇帖子：机器学习[白班推导]（一））：
$$\begin{array}{rl}P(\vec{x})& =\frac{1}{(2\pi {)}^{\frac{p}{2}}|\Sigma {|}^{\frac{1}{2}}}\exp \left\{-\frac{1}{2}\left[(\vec{x}-\vec{\mu }{)}^T{\Sigma }^{-1}(\vec{x}-\vec{\mu })\right]\right\}\\ & =\frac{1}{(2\pi {)}^{\frac{p}{2}}|\Sigma {|}^{\frac{1}{2}}}\exp \left\{-\frac{1}{2}\left[{\vec{x}}^T{\Sigma }^{-1}\vec{x}-2{\vec{\mu }}^T{\Sigma }^{-1}\vec{x}+{\vec{\mu }}^T{\Sigma }^{-1}\vec{\mu }\right]\right\}\\ & \propto \exp \left\{\underset{\text{Quadratic term}}{\underbrace{-\frac{1}{2}\left[{\vec{x}}^T{\Sigma }^{-1}\vec{x}\right]}}+\underset{\text{Linear term}}{\underbrace{{\vec{\mu }}^T{\Sigma }^{-1}\vec{x}}}\right\},\end{array}\text{\hspace{1em}(3.16)}$$

根据二次项对应系数矩阵可以求得方差矩阵，进而根据一次项对应系数矩阵可以求得均值向量，具体计算为：
$$\begin{array}{rl}& \{\begin{array}{c}{\Sigma }_W^{-1}={\sigma }^{-2}{X}^{T}X+{\Sigma }_0^{-1}\\ {\vec{\mu }}_W^T{\Sigma }_W^{-1}={\sigma }^{-2}{Y}^{T}X\end{array}\\ ⟹& \{\begin{array}{c}{\Sigma }_W=({\sigma }^{-2}{X}^{T}X+{\Sigma }_0^{-1}{)}^{-1}\\ {\vec{\mu }}_W=(X^{T}X+{\sigma }^2{\Sigma }_0^{-1}{)}^{-1}{X}^{T}Y\end{array},\end{array}\text{\hspace{1em}(3.17)}$$

当满足方差各向同性 ${\Sigma }_0={\sigma }_0^{2}I$ 时，均值 ${\vec{\mu }}_W$ 的计算结果与式（3.9）的解析解形式相同，只是将 $\lambda$ 替换为了 $\frac{{\sigma }^2}{{\sigma }_0^2}$.

3.4. 线性回归的特性

  线性回归算法作为重要的基础算法，具有3个特性，也成为了以线性回归为基础的改进模型的3个发展方向：

• 线性：为了能解决非线性问题，从3个角度拓展了线性回归的算法：
  • 属性非线性：特征建模（例如多项式回归）
  • 全局非线性：线性分类（使用非线性激活函数）
  • 系数非线性：多层感知机/神经网络
• 全局性（通常认为变量之间的线性关系是恒定一致的）：为了能解决非全局的线性拟合问题，可以使用线性样条回归（类似于将变量之间的关系看做分段线性的函数，将数据划分为子集，分别对不同子集拟合，得到分段线性关系）、决策树等算法改进。
• 数据未加工：可以使用PCA、流形学习（高维数据的低维映射）等算法解决。

​