线性回归、Logistic 回归和感知机

线性模型

Posted by Xiaosheng on April 13, 2017

1. 线性模型(Linear model)

依据实例空间的几何性质来定义的模型称为几何模型,通常假设各实例可用 $n$ 维的实值特征表示,即 $\boldsymbol{x} = (x_1;x_2;…;x_n)$,其中 $x_i$ 是 $\boldsymbol{x}$ 在第 $i$ 个属性上的取值。那些可依据直线和平面来理解的模型,通常称之为线性模型(linear model),线性模型试图学得一个通过属性的线性组合来进行预测的函数,即

一般用向量形式写成

其中 $\boldsymbol{w} = (w_1;w_2;…;w_n)$。在 $\boldsymbol{w}$ 和 $b$ 学得之后,模型就得以确定。

在机器学习中,线性模型因其简单性而格外引起人们的关注:

  • 线性模型是参数化的(parametric),这意味着其形式固定,仅有少量数值参数需要从数据中学习。
  • 线性模型比较稳定,即训练数据中的微小波动仅会对模型的学习结果产生极为有限的影响。
  • 与其他模型相比,线性模型不易产生过拟合,因为它们所包含的参数较少,这有时会导致模型的欠拟合。

线性模型可用于任何预测任务:分类、概率估计和回归,特别是线性回归。

2. 线性回归(Linear Regression)

给定数据集 $D = {(\boldsymbol{x}^{(1)},y^{(1)}),(\boldsymbol{x}^{(2)},y^{(2)}),…,(\boldsymbol{x}^{(m)},y^{(m)})}$,其中 $\boldsymbol{x}^{(i)} = (x^{(i)}_1,x^{(i)}_2,…,x^{(i)}_d)$,$y^{(i)} \in \mathbb{R}$。线性回归试图学得一个线性模型以尽可能准确地预测实值输出标记,即

我们都知道机器学习的三要素为:模型、策略、算法。现在模型已经知道了,那么应该使用怎么样的策略来选择最优模型呢,一般会通过定义模型的损失函数(loss function),它描述了 $f(\textbf{x})$ 函数不好的程度。对于线性回归模型,损失函数 $L(\boldsymbol{w},b)$ 定义为样本 $\boldsymbol{x}^{(i)}$ 的估计值与真实值 $y^{(i)}$ 之间的误差平方和,称为均方误差(为了求导方便,前面乘 $1/2$):

均方误差有非常好的几何意义,它对应了常用的欧式距离(Euclidean distance)。很明显,我们要使 $L(\boldsymbol{w},b)$ 的值尽可能小。即

注:最小化均方误差实际上就是对参数的最大似然估计,均方误差本质上是定义在训练集上的经验分布和定义在高斯模型上的概率分布之间的交叉熵。详情可以参见 最大似然估计

模型和学习策略都已经有了,最后还需要寻找一种根据学习策略,选择最优模型的算法。

基于均方误差最小化来进行模型求解的方法称为“最小二乘法”(least square method)。对于线性回归问题,最小二乘法就是试图找到一条直线,使所有样本到直线上的欧氏距离之和最小。为了便于讨论,我们通常把 $b$ 也作为一项权重 $w_0$ 吸收入 $\boldsymbol{w}$,相应的 $\boldsymbol{x}$ 增加一项永远为 $1$ 的元素 $\boldsymbol{x}_0$,这样线性模型可以表示为

于是可以把数据集表示为矩阵 $\textbf{X} \in \mathbb{R}^{m \times (n+1)}$,每行对应于一个实例,标记也写成向量形式 $\boldsymbol{y}=(y^{(1)},y^{(2)},…,y^{(m)})$。类似于 $(2.2)$,有

令 $E_\boldsymbol{w} = (\boldsymbol{y}-\textbf{X}\boldsymbol{w})^\top(\boldsymbol{y}-\textbf{X}\boldsymbol{w})$,对 $\boldsymbol{w}$ 求导得到

令上式为零可得 $\boldsymbol{w}$ 最优解的闭式解。当 $\textbf{X}^\top\textbf{X}$ 为满秩矩阵 (full-rank matrix) 或正定矩阵 (positive definite matrix) 时,令 $(2.4)$ 为零可得

最终学得的线性回归模型为

但是该方法要求 $\textbf{X}^\top\textbf{X}$ 是满秩矩阵,而且求矩阵的逆比较慢,特别是对于高维特征空间,其计算复杂度可能会非常巨大。因而在实际操作中,我们通常是通过梯度下降算法来寻找一个较好的参数向量 $\boldsymbol{w}$,它使得损失函数 $L(\boldsymbol{w})$ 取极小值。

2.1 梯度下降算法(gradient descent algorithm)

我们可以把最小化损失函数的过程看成是在下山,很明显最快地下山方式,应该是每一步都往坡度最陡的方向往下走,而坡度最陡的方向就是损失函数相应的偏导数。

梯度下降法是按下面的流程进行的:

  1. 首先对 $\boldsymbol{w}$ 赋值,这个值可以是随机的,也可以让 $\boldsymbol{w}$ 是一个全零的向量。
  2. 改变 $\boldsymbol{w}$ 的值,使得损失函数 $L(\boldsymbol{w})$ 按梯度下降的方向进行减少。

对于损失函数 $L(\boldsymbol{w})$ 来说,坡度最陡的方向(梯度)就是损失函数相应的偏导数,因为这里是要下降,因而前进方向是梯度的反方向。对于一个样本 ($m = 1$),算法迭代的规则就是:

其中 $\alpha$ 是算法的学习率,控制下降的步长,$\alpha$ 越大每一步下降的幅度越大速度也会越快,但过大有可能导致算法不准确。梯度下降算法求得的可能是局部最优解,这与起始点有关,即 $\boldsymbol{w}$ 初始化时的值。不过对于线性规划问题,通常损失函数 $L(\boldsymbol{w})$ 是碗状的,所以往往只会有一个全局最优解,所以不用过多担心算法收敛到局部最优解。

1

当训练集的样本量大于 1 时,有两种算法:

批量梯度下降(batch gradient descent)

重复下面过程直到收敛:

随机梯度下降(stochastic gradient descent)

遍历所有样本,每遍历一个样本 $x^{(i)}$ 更新一下参数向量 $\boldsymbol{\theta}$:

当训练样本量很大时,批量梯度下降的每一步都要遍历整个训练集,开销极大;而随机梯度下降每次下降时只选取其中的一个样本,因此后者的速度要快于前者。另外,虽然随机梯度下降可能不会收敛,但是实践当中大多数情况下得到的结果都是真实最小值的一个足够好的近似。

3. Logistic 回归(Logistic Regression)

之前我们讨论了如何使用线性模型进行回归学习,但如果要做的是分类任务该怎么办?事实上我们只需要找一个单调可微函数将分类任务的真实标记 $y$ 与线性回归模型的预测值联系起来就可以了,Logistic 回归就是一个典型的例子。

记住虽然名字叫“回归”,但实际上 Logistic 回归模型用于分类。

考虑二分类任务,其输出标记 $y \in {0,1}$,而线性回归模型产生的预测值 $z = \boldsymbol{w}^\top\boldsymbol{x}$ 是实值,于是我们需要将实值 $z$ 转换为 $0/1$ 值。最理想的是“单位阶跃函数” (unit-step function):

即若预测值 $z$ 大于零就判为正例,小于零则判为反例,预测值为临界值零则可任意判别。但是单位阶跃函数不连续,因而我们希望找到一个近似的单调可微函数来代替它,logistic 函数就是一个常用的替代函数:

Logistic 函数是一种 sigmoid 函数 (sigmoid 函数即形似 S 的函数),logistic 函数是 sigmoid 函数最重要的代表,它在神经网络中有着重要的作用。logistic 函数是一条 $y$ 值从 0 到 1 的连续曲线。当 $z\rightarrow\infty$,$y\rightarrow1$;当 $z\rightarrow−\infty$,$y\rightarrow0$。

2

于是 Logistic 回归模型可以描述为

其条件概率分布为

即我们将 $y$ 作为正例的可能性,将 $1-y$ 作为反例的可能性,两者的比例

称为几率 (odds),反映了 $\boldsymbol{x}$ 作为正例的相对可能性。对几率取对数则得到对数几率 (log odds,亦称 logit)

由此可以看出,Logistic 回归模型实际上是在用线性回归模型的预测结果去逼近真实标记的对数几率,因此,模型称为“对数几率回归” (logistic regression)。注意,虽然名字是“回归”,但实际上却是一种分类方法。

一个事件的几率 (odds) 是指该事件发生的概率与该事件不发生的概率的比值。

Logistic 回归模型有许多优点:

  • 直接对分类可能性建模,无需事先假设数据分布,这样就避免了假设分布不准确带来的问题。
  • 不是仅预测出“类别”,而是可得到近似概率预测,这对许多需利用概率辅助决策的任务很有用。
  • 对数几率函数是任意阶可导的凸函数,有很好的数学性质,现有的许多数值优化算法都可以直接用于求取最优解。

模型已经有了,接下来就需要寻找学习策略了。Logistic 回归使用的策略是通过“极大似然法” (maximum likelihood method) 来估计 $\boldsymbol{w}$。给定数据集 ${(\boldsymbol{x}^{(i)},y^{(i)})}_{i=1}^m$,Logistic 回归模型最大化对数似然函数 (log-likelihood):

因为我们将 $y$ 作为正例的可能性,因此 $P(\mathbb{y}=1\mid \boldsymbol{x}) = f(\boldsymbol{x})$,$P(\mathbb{y} = 0\mid\boldsymbol{x}) = 1-f(\boldsymbol{x})$,则 $(3.25)$ 中的似然项可以重写为

于是 $(3.5)$ 对数似然函数可以进一步化为

很明显,我们需要使对数似然函数 $\mathcal{L}(\boldsymbol{w})$ 尽可能地大,即令每个样本属于其真实标记的概率越大越好。我们可以用梯度下降找到极小值的点,反过来也可以用梯度上升找到极大值的点。Logistic 回归通常就使用梯度上升算法来寻找使得对数似然函数 $\mathcal{L}(\boldsymbol{w})$ 取极大值的参数向量 $\boldsymbol{w}$。

本质上,梯度上升法与梯度下降法是相同的,因为求 $f(\boldsymbol{x})$ 的极大就是求 $-f(\boldsymbol{x})$ 的极小。

3.1 梯度上升算法(gradient ascent)

首先补充一下计算中要用到的 Logistic 函数的导数:

在此基础上我们对对数似然函数求导获得梯度,对于一个样本 ($m = 1$):

这个导数和线性回归中的导数非常相似,但是要注意两者的模型 $f(\boldsymbol{x})$ 是不一样的,逻辑回归在 $\boldsymbol{w}^\top\boldsymbol{x}$ 的基础上还加了一层 $g(z)$ 函数映射。现在我们要沿着梯度方向上升,因而前进方向就是梯度方向。最终采用随机梯度上升的迭代规则如下:

遍历所有样本,每遍历一个样本 $\boldsymbol{x}^{(i)}$ 更新一下参数向量 $\boldsymbol{w}$:

4. 感知机(The perceptron learning algorithm)

感知机的模型为:

从模型上来看感知机与 Logistic 回归十分相似,都是在 $\boldsymbol{w}^\top\boldsymbol{x}$ 的基础上,又做了一层函数映射。只不过逻辑回归的函数是 Logistic 函数(又称 sigmoid 函数),而感知机的函数是阶跃函数,只输出 0 和 1。

虽然和 Logistic 回归形式上相近,但是很难为感知机的预测加上概率解释,也很难说感知机算法是源于最大化似然函数,训练感知机模型也是通过梯度上升算法来进行(和 Logistic 回归一样):

遍历所有样本,每遍历一个样本 $\boldsymbol{x}^{(i)}$ 更新一下参数向量 $\boldsymbol{w}$:

从 $(4.2)$ 可以看出,若感知机对训练样例 $(\boldsymbol{x},y)$ 预测正确,即 $f(\boldsymbol{x}) = y$,则感知机不发生变化,否则将根据错误的程度进行权重调整。

注:这个更新算法也被称为感知器训练法则。

参考

Peter Flach《机器学习》
周志华《机器学习》
Logos《斯坦福CS229机器学习课程笔记一:线性回归与梯度下降算法》
Logos《斯坦福CS229机器学习课程笔记二:GLM广义线性模型与Logistic回归》
JerryLead《对回归方法的认识》
MIT《深度学习》