《机器学习基石》9-Linear Regression

这一节主要介绍线性回归算法。

Linear Regression Problem

对于输出空间 Y=R$\mathcal{Y}=\mathbb{R}$ 的一类问题，一个比较简单的想法就是：将 Linear Classification 的决策函数中的 sign 函数去掉，使用各种特征的加权结果来表示 y$y$

这就是线性回归算法，它的假设空间为 线性回归的目标是寻找一条直线 （R2${\mathbb{R}}^2$） 或者一个平面 （R3${\mathbb{R}}^3$）或者超平面（Rn${\mathbb{R}}^n$），使得误差最小，常用的误差函数是平方误差

Linear Regression Algorithm

将 Ein$E_{in}$ 写成矩阵形式

其中

我们的目标是找到一个 w$\mathbf{\text{w}}$，使得 Ein(w)$E_{in}(\mathbf{\text{w}})$ 尽可能小。因此，将 Ein(w)$E_{in}(\mathbf{\text{w}})$ 对 w$\mathbf{\text{w}}$ 求导，得到：
令∇Ein(w)=0$\mathrm{\nabla }{E}_{in}(\mathbf{\text{w}})=0$，得到 w$\mathbf{\text{w}}$ 的最优解 其中 称为矩阵 X$X$ 的伪逆，于是

将上面做一个小结，得到 Linear Regression 算法的流程如下：

Generalization Issue

下面我们来分析一下 Linear Regression 的 Ein$E_{in}$

其中 H=XX†$H=X{X}^{†}$ 是投影矩阵，把 y$y$ 投影到 X$X$ 的 d+1$d+1$ 个向量构成的平面上，H$H$ 有如下的性质：

• 对称性 H=HT$H=H^T$
• 幂等性 H2=H$H^2=H$
• 半正定性 λi≥0${\lambda }_i\ge 0$
• trace(I−H)=N−(d+1)$trace(I-H)=N-(d+1)$

假设 y=f(X)+noise,f(x)∈span$y=f(X)+\text{noise},f(x)\in \text{span}$，那么如上图所示，有

得到：


两者最终都向 σ2${\sigma }^2$ (noise level)收敛，差距是 2(d+1)N$\frac{2(d+1)}{N}$，因此说明算法是可行的。

Linear Regression for Binary Classification

对比一下 Linear Classification 与 Linear Regression：

• Linear Regression
  
  • 用于分类问题
  • Y={+1,−1}$\mathcal{Y}=\{+1,-1\}$
  • h(x)=sign(wTx)$h(\mathbf{\text{x}})=\text{sign}({\mathbf{\text{w}}}^T\mathbf{\text{x}})$
  • NP-hard，难于求解
• Linear Regression
  
  • 用于回归问题
  • Y=R$\mathcal{Y}=\mathbb{R}$
  • h(x)=wTx$h(\mathbf{\text{x}})={\mathbf{\text{w}}}^T\mathbf{\text{x}}$
  • 易于求解

因为

所以可以将 Linear Regression 用于分类问题上：

1. run Linear Regression on binary classification data D$\mathcal{D}$
2. return g(x)=sign(wTLINx)$g(\mathbf{\text{x}})=\text{sign}({\mathbf{\text{w}}}_{\text{LIN}}^T\mathbf{\text{x}})$

以上便是 Linear Regression 的内容。