0%

【图解例说机器学习】线性回归

线性回归之于机器学习,正如Hello World之于编程语言,也如MINST之于深度学习。

首先,我们先定义一些即将用到的数学符号:

Notations Meaning Notations Meaning
$M$ Number of parameters $\mathrm w$ $N$ Number of instances
$\mathrm X=\{\mathrm x_1,\mathrm x_2,\cdots,\mathrm x_N\}^{\mathrm T}$ $N\times M$ matrix for training $D$ Number of features
$\mathrm y=\{y_1,y_2,\cdots,y_N\}^\mathrm{T}$ Set of targets $y_i$ Target of instance $i$
$\mathrm{x}_i=\{x_i^{(1)},x_i^{(2)},\cdots,x_i^{(D)}\}^\mathrm{T}$ Set of features for instance $i$ $x_i^{(j)}$ Feature $j$ for instance $i$
$\mathrm w=\{\omega_1,\omega_2,\cdots,\omega_M\}^\mathrm{T}$ Weights of input $\mathrm x$ $\omega_i$ Weight of feature $i$
$\phi=\{\phi_1,\phi_2,\cdots,\phi_M\}^\mathrm{T}$ Set of functions $\phi_i(\mathrm x)$ Function of features

模型描述

在线性回归中,假设目标值与参数 $\mathrm{w}=\{\omega_n\}$之间线性相关,通过构建损失函数$E$,求解损失函数最小时的参数。也就是说,线性回归试图学习得到如下函数:

公式(1)是线性回归模型的一般形式,看起来不是那么直观。其常见的形式如下:

  • 当$D=1,\phi_j(x)=x^j$时,公式(1)可以表示为:

    此时,线性回归就变成了多项式回归。

  • 当$D=M,\phi_j(\mathrm x)=x^{(j)}$时,公式(1)可以表示为:

    此时,线性回归就变成了我们通常所说的线性回归—-多元一次方程。当只有一维特征($M=1$) 时,可以得到我们初中就学过的一元一次方程

为使本文通俗易懂,除非作特别说明,本文仿真都以这个一元一次方程为例介绍线性回归


代价函数

线性回归的目的就是使得我们预测得到的$\hat y$与真实值$y$之间的误差最小。这里的误差可以用不同的距离度量,这里我们使用平方和。此时,代价函数就可以表示为

下面我们在二维空间($M=1$)和三维空间($M=2$)画出代价函数图像。这里我们假定$\phi_i(\mathrm x)=x^{(i)}$,$\omega_0,\omega_1,\omega_2$已知,则公式(1)可以分别表示为:

根据公式(6),(7),我们可以得到图1和图2中的直线和二维平面:

图1

图2

图1和图2中的红色的点是 $\mathrm x$ 对应的真实值 $\mathrm y$ ,红色线段即为误差值。


一个例子

图1和图2展示的是给定参数$\omega_0,\omega_1,\omega_2$下的真实值$y$与预测值$\hat { y}$的误差。不同的参数可以得到不同的误差值,线性回归的目的就是寻找一组参数是的误差最小。下面我们通过图3和图4来说明:

我们假设训练集有3组数据$(x, y)$:$(1, 0.8) (2, 2) (3, 3.1)$ 。我们这里使用一元线性回归,即公式(6),此时线性回归的目的就是找到一条直线$\hat y=\omega_1x+\omega_0$使得这3组数据点离直线最近。

图3

图3画出了当$\omega_0=0,\omega_1=0.5\sim1.5$时,直线$\hat y=\omega_1x+\omega_0$的图像。图4给出了当$\omega_1$取不同值时,代价函数值的变化。从图3和图4可以看出,当$\omega_1=1$时,代价最小。

图4


正规方程与梯度下降

线性回归的本质就是解如下优化问题:

令$\bar{\mathrm w}=\{\omega_0,\mathrm w\},\bar{\phi}=\{\phi_0,\phi\},\phi_0(\mathrm x)=1$,并将问题(8)表示成向量相乘的形式:

公式(9)中,$\bar{\phi}(\mathrm X)$是一个$N\times M+1$维的矩阵:

通过求表达式(8)的Hessian矩阵,可以知道这是一个凸优化问题。那么问题就变得十分简单了,可以用现成的工具来求解:比如CVX, CPLEX, MATLAB等等。这些解法器一般都是通过梯度法(后面会讲解)来求解问题的。当然我们也可以通过凸问题的性质,得到其解析解。


正规方程法

由于误差函数(8)是一个凸函数,所以其导数为0的点就是最优点。为此,我们将$E$对$\mathrm{\bar w}$进行微分求导入下:

由公式(11)可知,给定训练数据$\mathrm X$,我们就可以求出最佳的$\mathrm{\bar w}$。需要注意的是,这里需要求矩阵的逆,计算量比较大,不适合当训练数据较大的情况。这时我们可以通过梯度下降法来求解。


梯度下降法

使用梯度下降法,可以对凸问题求得最优解,对非凸问题,可以找到局部最优解。梯度下降法的算法思想如下图5和图6所示:

  • 在左图(图5)中,梯度为$\frac{d\hat y}{d x}=x-2$。当$x<2$时,梯度小于零,此时$x$应当向右移动来减小函数值(负梯度方向);当$x>2$时,梯度大于零,此时$x$应当向左移动来减小函数值(负梯度方向)。
    图5
  • 在右图(图6)中,函数不是凸函数的情况下,使用梯度下降法会得到局部最优解(假定初始值为$x=0$)。当初始值$x=7$时,我们可以得到最优解。因此,初始值对梯度下降法影响较大,我们可以通过随机选择初始值来克服陷入局部最优解的情况。
    图6

根据(10)得到的梯度表达式,梯度下降的每一次迭代过程如下:

将公式(13)的矩阵相乘展开可以得到

公式(13)或(14)就是标准的梯度下降法,其中$\eta$是每次迭代的步长大小。

  • $\eta$较小时,迭代较慢,当时可以保证收敛到最优解(凸函数的情况下);$\eta$较大时,函数值下降较快,但容易发生震荡。
  • 每次迭代时,需要使用所有的样本点$\mathrm x_i,i=1,2,\cdots,N$。当数据样本点非常大时,开销十分大。

为此,有人提出了随机梯度下降,其迭代公式如下:

随机梯度下降又称连续梯度下降,比较适合于实时系统,即整个数据集$\mathrm x_i$不是可以一次性获得的,但是我们需要作出预测的场景。相较于梯度下降法(14),随机梯度只根据当前样本更新迭代,随机性较大。因此有可能跳出标准梯度下降法的局部最优解。


算法实现

这里我们使用sklearn中波士顿房价的数据集,该数据集有13维特征,506个样例。为简便起见,我们只取前2维特征作为输入($M=D=2,\hat y=\omega_0+\omega_1x^{(1)}+\omega_2x^{(2)}$),前500个作为输入样例,后6个作为预测样例。在算法实现中,我们分别考虑了正规方程法梯度下降法。并且,考虑到$x^{(1)}$和$x^{(2)}$的取值范围差距较大,我们还考虑了特征值缩放。为此,我们实现了上述四种算法的组合[特征不缩放(特征缩放)+正规方程法(梯度下降法)]。


算法结果

图7给出了上述4种算法的结果:

图7

图7中,E_train为训练误差,即前500个样例的真实值与预测值的误差,E_test为预测误差,即最后6个样例的真实值与预测值的误差。由于误差函数对于参数w是凸函数,我们总能得到最优解,即最小的训练误差,所以上述四种方法的训练误差相同。


特征缩放与梯度下降法

图7能得到最小误差函数值,是因为目标函数$E$是参数$\omega_1$和$\omega_2$的凸函数。为方便起见,对于具体实例,我们给出$E$的表达式:

公式(16)中,$\omega_0$与具体样例无关,$\omega_0$的值不改变$E$的图像形状,改变$\omega_0$相当于进行位移,我们这里假定$\omega_0=0$。为此,当给定波士顿房价数据集,即$x^{(1)},x^{(2)},y_i$ 给定时,我们可以画出公式(16)对应的等高线图,图8。

  • 从图8可以看出,当改变$\omega_2$时,$E$变的较快(等高线在$\omega_2$方向较为稀疏)。这是因为$\omega_2$的系数为$x^{(2)}$,而$x^{(2)}$相对于$x^{(1)}$有较大的取值。在这种情况下,对梯度下降法就十分不友好—很容易跳过最优解。也就是说,步长设置要十分小,这就会导致收敛速度慢。在我们这个实例中,步长最大只能设置为$\eta=5e^{-6}$,此时需要差不多30000次迭代才能收敛到最优,如图10所示。
    图8

    图9

  • 特征缩放是一种解决上述情况下,梯度下降法收敛慢的方法。特征缩放的表达式都十分简单,这里不再赘述,我们这里是直接使用的sklearn库中的preprocessing.StandardScaler()函数对样例进行特征缩放。对$x^{(1)},x^{(2)}$缩放后,我们可以用相同的方式画出对应的等高线图,图9,以及收敛图,图11。经过特征缩放后,图9中等高线在$\omega_1,\omega_2$方向上的稀疏程度差不多。图11中,步长可以设置得较大($\eta=1e^{-3}$),收敛速度变得极快,只需要迭代8次左右就达到最优。
    图10

图11


附录

下面给出图1—图11的Python源代码如下:

坚持原创技术分享,您的支持将鼓励我继续创作!