DanielLaah

《统计学习方法》笔记 (三) - 感知机


本篇博客为《统计学习方法》笔记系列第3篇, 对应《统计学习方法》中第2章的内容. 主要介绍感知机模型.
说明: 目前来讲, 本系列博客内容基本完全摘抄自李航博士的《统计学习方法》, 所以阅读本系列博客极有可能造成您的不适, 如发生, 请尽快关闭浏览器. 写此系列博客目的一是学习的时候加深印象二是为了方便自己随时复习. 后面如果在其他书籍或课程中学习了相关的知识, 可能会对文章内容进行适量增删. 谢谢你!
PPT下载


感知机(perceptron)是二类分类的线性分类模型, 将输入空间中的实例划分为正负两类的分离超平面, 属于判别模型. 感知机1957年由Rosenblatt提出, 是神经网络和支持向量机的基础.

2.1 感知机模型

假设输入空间(特征空间)是$\mathcal{X}\subseteq R^n$, 输出空间是$\mathcal{Y}=\{+1, -1\}$. 输入$x\in \mathcal{X}$表示实例的输入向量,对应于输入空间(特征空间)的点;输出$t\in \mathcal{Y}$表示实例的类别,由输入空间到输出空间的如下函数:
$$f(x)=sign(w\cdot x + b)$$
称为感知机. 线性方程$w\cdot x + b$对应于特征空间$R^n$中的一个超平面$S$, 其中$w$是超平面的法向量, $b$是超平面的截距. 这个超平面将特征空间划分成两个部分. 位于两部分的点分别被分为正, 负两类. $S$称为分离超平面(separating hyperplane)

2.2 感知机学习策略

假设训练数据集是线性可分的, 感知机学习的目标是求得一个能够将训练集正实例点和负实例点完全正确分开的分离超平面. 为了找出这样的超平面, 需要一个学习策略, 即定义(经验)损失函数并将损失函数极小化.
损失函数的一个自然选择是误分类点的总数. 但是, 这样的损失函数不是参数$w,b$的连续可导函数, 不易优化. 损失函数的另一个选择是误分类点到超平面$S$的总距离, 这是感知机所采用的.
输入空间中任意一点$x_0$到超平面$S$的距离:
$$\frac{1}{\Vert w\Vert}|w\cdot x_0 +b|$$
对于一个误分类的数据$(x_i, y_i)$来说, 有如下不等式成立:
$$-y_i(w\cdot x_i+b)\gt 0$$
所以, 误分类点$x_i$到超平面的距离是:
$$-\frac{1}{\Vert w\Vert}y_i(w\cdot x_0 +b)$$
假设误分类点的集合为$M$, 那么所有的误分类点到超平面$S$的总距离为:
$$-\frac{1}{\Vert w\Vert}\sum_{x_i\in M}y_i(w\cdot x_0 +b)$$
不考虑$-\frac{1}{\Vert w\Vert}$, 就得到感知机学习的损失函数:
$$L(w,b)=-\sum_{x_i\in M}y_i(w\cdot x_0 +b)$$
感知机学习的策略实在假设空间中选取使这个损失函数最小的模型参数$w,b$, 即感知机模型.

2.3 感知机学习算法

2.3.1 感知机学习算法的原始形式

感知机学习算法是误分类驱动的, 具体采用随机梯度下降算法(stochastic gradient descent). 首先, 任意选取一个超平面$w_0, b_0$, 然后用梯度下降算法不断极小化目标函数. 极小化过程中不是一次使$M$中所有误分类点的梯度下降, 而是一次随机选取一个误分类点使其梯度下降.
假设误分类点集合$M$是固定的, 那么损失函数$L(w,b)$的梯度为:
$$\nabla_wL(w,b)=-\sum_{x_i\in M}y_ix_i$$
$$\nabla_bL(w,b)=-\sum_{x_i\in M}y_i$$
随机选取一个误分类点$(x_i, y_i)$, 对$w,b$进行更新:
$$w\leftarrow w+\eta y_ix_i$$
$$b\leftarrow b+\eta y_i$$
其中$\eta$为步长, 也叫作学习率(learning rate). 这样, 通过迭代可以期待损失函数不管减小, 直到为0.
总结(感知机学习算法的原始形式):
输入: 训练集; 学习率
输出: $w,b$
1.选取初值$w_0, b_0$
2.在训练集中选取数据$(x_i, y_i)$
3.如果$y_i(w\cdot x_i+b)\le 0$
$$w\leftarrow w+\eta y_ix_i$$
$$b\leftarrow b+\eta y_i$$
4.转至2, 直至训练集中没有误分类点

2.3.2 算法的收敛性

下面证明对于线性可分数据集感知机学习算法原始形式收敛, 即经过有限次迭代可以得到一个将训练数据集完全正确划分的分离超平面及感知机模型.
为了方便, 记$\hat{w}=(w^T,b)^T, \hat{x}=(x^T,1)^T$, 显然$\hat{w}\cdot \hat{x}=w\cdot x+b$
假设我们最终优化后的参数为$\hat{w}_f$(即最终感知机的参数), 那么,对于所有的样本点都有:
$$y_i\hat{w}_f\cdot\hat{x}_i\gt0$$

$$\gamma=\min_i\{y_i\hat{w}_f\cdot\hat{x}_i\}$$

$$y_i\hat{w}_f\cdot\hat{x}_i\ge\gamma \tag 1$$
假设在第$k-1$次更新参数的时候, 我们选择了某个误分类实例$(x_i, y_i)$, 由于该实例在此时是误分类的, 所以有
$$y_i\hat{w}_{k-1}\cdot\hat{x}_i\lt0$$
并且根据更新规则:
$$\hat{w}_{k}=\hat{w}_{k-1}+\eta y_i\hat{x}_i \tag 2$$
由(1)(2)两式
$$\begin{align}
\hat{w}_k\cdot \hat{w}_f & = (\hat{w}_{k-1}+\eta y_i\hat{x}_i)\cdot \hat{w}_f \\
\\
& = \hat{w}_{k-1}\cdot \hat{w}_f + \eta y_i\hat{w}_f\cdot\hat{x}_i \\
\\
& \ge \hat{w}_{k-1}\cdot \hat{w}_f + \eta \gamma \ge \hat{w}_{k-2}\cdot \hat{w}_f + 2\eta \gamma \ge … \ge k\eta \gamma
\end{align} \tag 3$$
再由(2)式
$$\begin{align}
{\Vert\hat{w}_{k}\Vert}^2 & = {\Vert\hat{w}_{k-1}+\eta y_i\hat{x}_i\Vert}^2 \\
\\
& = {\Vert\hat{w}_{k-1}\Vert}^2 + 2\eta y_i\hat{w}_{k-1}\cdot \hat{x}_i + \eta{\Vert\hat{x}_{i}\Vert}^2 \\
\\
& \lt {\Vert\hat{w}_{k-1}\Vert}^2 + \eta^2{\Vert\hat{x}_{i}\Vert}^2 \\
\\
& \lt {\Vert\hat{w}_{k-1}\Vert}^2 + \eta^2\max_{i}{\Vert\hat{x}_{i}\Vert}^2 \lt {\Vert\hat{w}_{k-2}\Vert}^2 + 2\eta^2\max_{i}{\Vert\hat{x}_{i}\Vert}^2 \lt … \lt k\eta^2\max_{i}{\Vert\hat{x}_{i}\Vert}^2
\end{align} \tag 4$$
令$\Vert\hat{w}_f\Vert=1$结合(3)(4)式
$$k\eta\gamma\le\hat{w}_k\cdot \hat{w}_f\le\Vert\hat{w}_k\Vert \Vert\hat{w}_f\Vert\le\sqrt{k}\eta\max_{i}{\Vert\hat{x}_{i}\Vert}$$
$$k^2\gamma^2\le k\max_{i}{\Vert\hat{x}_{i}\Vert}^2$$
于是
$$k\le\left(\frac{\max_{i}{\Vert\hat{x}_{i}\Vert}}{\gamma}\right)^2$$
这表明误分类的次数$k$是有上界的, 经过有限次搜索可以找到将训练数据完全正确分开的分离超平面. 也就是说, 当训练数据集线性可分时, 感知机学习算法原始形式迭代是收敛的. 当训练集线性不可分时, 感知机学习算法不收敛, 迭代结果产生震荡.

2.3.3 感知机学习算法的对偶形式

感知机学习算法的原始形式和对偶形式与第7章中支持向量机学习算法的原始形式和对偶形式相对应.
对偶形式的基本想法是, 将$w$和$b$表示为实例$x_i$和标记$y_i$的线性组合的形式, 通过求解其系数而求得$w$和$b$. 假设初始值$w_0,b_0$均为0. 对误分类点$(x_i, y_i)$通过
$$w\leftarrow w+\eta y_ix_i$$
$$b\leftarrow b+\eta y_i$$
逐步修改$w,b$, 设修改n次, 则$w,b$关于$(x_i, y_i)$的增量分别是$\alpha_iy_ix_i$和$\alpha_iy_i$, 这里$\alpha_i=n_i\eta$.这样, 最后学习到的$w, b$可以分别表示为
$$w=\sum_{i=1}^N\alpha_iy_ix_i$$
$$b=\sum_{i=1}^N\alpha_iy_i$$
这里, $\alpha_i\ge0, i=1,2,…,N$, 当$\eta=1$时, 表示第$i$个实例点由于误分类而进行更新的次数. 实例点更新的次数越多, 意味着它距离分离超平面越近, 也就越难正确分类. 换句话说, 这样的实例对学习结果的影响最大.
总结(感知机学习算法的对偶形式):
输入: 训练集; 学习率
输出: $\alpha,b$; 感知机模型$f(x)=\text{sign}\left(\sum_{j=1}^N\alpha_iy_ix_i\cdot x+b\right)$, 其中$\alpha=(\alpha_1,\alpha_2,…,\alpha_N)$
1.$a\leftarrow 0, b\leftarrow 0$
2.在训练集中选取数据$(x_i, y_i)$
3.如果$y_i\left(\sum_{j=1}^N\alpha_iy_ix_i\cdot x+b\right)\le 0$
$$\alpha_i\leftarrow \alpha_i+\eta$$
$$b\leftarrow b+\eta y_i$$
4.转至2, 直至训练集中没有误分类点
对偶形式中训练实例仅以内积的形式出现. 为了方便, 可以预先将训练集中实例间的内积计算出来并以矩阵的形式存储, 这个矩阵就是Gram矩阵(Gram matrix)
$$G=\left[x_i\cdot x_j\right]_{N\times N}$$