知错能改的感知机(Perceptron)

本文作者： UqRai

2017-05-25 10:34

导语：一篇关于感知机的深度科普。

感知机（perceptron）是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和-1二值。感知机对应于输入空间中将实例划分为正负两类的分离超平面，属于判别模型。感知机学习旨在求出将训练数据进行线性划分的分离超平面，为此导入了基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，求得感知机模型。感知机学习算法具有简单而易于实现的优点，分为原始形式和对偶形式。感知机是神经网络与支持向量机的基础。

划重点：简单说就是个二分类的线性分类模型,感知机学习，就是通过训练数据集，求得感知机模型，即求的模型参数。

感知机模型

由输入空间到输出空间的如下函数称为感知机：

知错能改的感知机(Perceptron)

w叫做权值（weight）或权值向量，b叫做偏置(bias)。

感知机模型的原理：给每一个属性一个权重w,对属性值和权重的乘积求和，将这个值和一个阀值(0/1)进行比较，可以判定比如是否录用这个应聘者。
感知机的几何解释：线性方程.
线性分类器的几何表示：直线、平面、超平面。

知错能改的感知机(Perceptron)

对应于特征空间Rn中的一个超平面S，其中w是超平面的法向量[注]，b是超平面的截距。这个超平面将特征空间划分为两个部分，位于两部分的点分别被分为正、负两类。因此，超平面S称为分离超平面（separating hyperplanes）。

雷锋网注：比如在二维平面里，分界是一条直线的情形下，y=wTx，那么分界线对应的y取值都是0，此时对于这条线来说，w就是分界线的法向量。

感知机是咋学习的，为啥说它是知错能改？

1. 假设数据集线性可分，感知机的学习目标是求得一个能够将训练集正实例点和负实例点完全正确分开的超平面。为了找到这个超平面，即确定感知机模型参数w，b，需要确定一个学习策略，即定义（经验）损失函数并将损失函数极小化。

损失函数的一个自然选择是误分类点的总数，但是损失函数不是w，b的连续可导函数，不易优化。损失函数的另一个选择是计算误分类点到超平面的总距离。输入空间中任一点x0x0到超平面S的距离为：

知错能改的感知机(Perceptron)

任一点到超平面距离

感知机sign(w.x+b)学习的损失函数定义为(重点)：

知错能改的感知机(Perceptron)

损失函数

一个特定样本的损失函数，在误分类的时候该函数是w和b的线性函数，而正确分类的时候是0，因此损失函数时w和b的连续可导函数。

划重点：感知机学习策略就是在假设空间中选取使感知机的损失函数最小的模型参数w和b，即感知机模型。

2. 感知机学习算法转化为求解感知机损失函数的最优化问题，最优化的方法是随机梯度下降法。

学习算法：
输入：训练数据集T、学习率α
输出：w,b；感知机模型f(x)=sign(w.x + b)
(1) 选取初值w0,b0
(2) 在训练集中选取数据(xi,yi)
(3) 如果yi(w.xi + b) <= 0，使用随机梯度下降法更新w和b
(4) 转至(2)，直至训练集中没有误分类点（重复的将误分类的点一直更新）

任意选取一个超平面w0,b0w0,b0，然后用梯度下降法不断地极小化目标函数

知错能改的感知机(Perceptron)

梯度

随机选取一个误分类点 (xi,yi)(xi,yi)，对 w,b 进行更新：

知错能改的感知机(Perceptron)

其中 η 是步长，又称为学习速率。这样通过迭代可以期待损失函数 L(w,b) 不断减小，直到 0.

这种学习算法直观上解释：当一个实例类被误分类，即位于分离超平面的错误一侧时，则调整w,b的值，使分离超平面向该分类点的一侧移动，以减少该误分类点与超平面的距离，直至超平面越过该误分类点使其被正确分类。

刚开始，随便一点，开始两个相同类型连线即法向量，作垂线得到初始的分类平面(线)

知错能改的感知机(Perceptron)

初始(来源：台湾国立大学林老师课程)

当检测到错误后，通过旋转开始修正，得到优化的分类

知错能改的感知机(Perceptron)

不断检测，直到没有错误

知错能改的感知机(Perceptron)

最后

但是这个PLA算法真的会停吗？

分两种情况讨论：数据线性可分；数据线性不可分

知错能改的感知机(Perceptron)

注意PLA 停止的条件是，对任何数据分类都正确，显然数据线性不可分时PLA 无法停止，那么我们可以用Pocket算法，运用贪心思想找到一个比较好的。

数据线性可分:

一定存在完美的w(记为wf)，使得所有的(xi, yi), yi = sign(wf*xi).可知：

知错能改的感知机(Perceptron)

下面证明在数据线性可分时，简单的感知机算法会收敛。（这个是根据林老师的定义给的，我感觉比较清晰，详细的可以看《统计学习方法》第二章）

知错能改的感知机(Perceptron)

而且量向量夹角余弦值不会大于1，可知T 的值有限。T=1，即向量内积为1，两向量重合，由此，我们证明了简单的PLA 算法可以收敛。

数据线性不可分：

Pocket Algorithm当数据线性不可分时（存在噪音），简单的PLA 算法显然无法收敛。我们要讨论的是如何得到近似的结果。我们希望尽可能将所有结果做对，即：

知错能改的感知机(Perceptron)

寻找 wg 是一个NP-hard 问题！只能找到近似解。算法如下：

知错能改的感知机(Perceptron)

Pocket Algorithm

与简单PLA 的区别：迭代有限次数（提前设定）；随机地寻找分错的数据（而不是循环遍历）；只有当新得到的w 比之前得到的最好的wg 还要好时，才更新wg（这里的好指的是分出来的错误更少）。由于计算w 后要和之前的wg 比较错误率来决定是否更新wg，所以pocket algorithm 比简单的PLA 方法要低效。