模型

定义：假设输入空间（特征空间）是 X∈R^n ，输出空间是 Y={+1，-1} 。输入 x∈X 表示实例的特征向量，对应于输入空间（特征空间）的点；输出 y∈Y 表示实例的类别。由输入空间到输出空间的如下函数：

称为感知机。其中， w 和 b 为感知机参数， w 叫做权值向量（weight vector）， b 叫做偏置（bias）， wx 叫做w和x的内积。sign是符号函数，即：

感知机 = 是 / 非题 = 二类分类（binary classification）。感知机是一种线性分类模型，属于判别模型。
感知机有如下几何解释：

线性方程：

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

假设特征空间为R^2，则上述方程可以表示为：

该方程可以表示为如图所示，x(1)为横轴，x(2)为纵轴，直线为对应方程。该直线将样本点分为两类，叫做分离超平面。

图 感知机模型

感知机学习的最后目的就是通过训练数据集
T = {(x1,y1),(x2,y2),...,(xn,yn)}
来求得感知机模型，即求得模型参数w和b。

学习策略

线性可分性

给定一个数据集
T={(X1,y1),(x2,y2),...,(xn,yn)}
如果存在某个超平面S：

能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧。我们就称数据集 T 是线性可分数据集。否则，称数据集 T 线性不可分。

学习策略

假设训练数据集是线性可分的，感知机学习的目标是求得一个能够将训练集正实例点和负实例点完全正确分开的分离超平面。为了找到这样的超平面，即确定感知机模型的参数w，b，需要确定一个学习策略，即定义损失函数，并且将损失函数（loss function）极小化 。
损失函数的一个自然选择是误分类点的总数，但这样的函数不是参数w和b的连续可导函数，不易优化。损失函数另一个选择是误分类点到超平面S的总距离，这是感知机所采用的。

推导过程

首先，写出输入空间R^n中任意一点x0到超平面S的距离：

而对于误分类的数据（xi，yi）来说：

因此，误分类点xi到超平面S的距离是：

这样，假设超平面的误分类点集合为M，那么所有的误分类点到超平面S的总距离为：

不考虑 ||w|| ，就得到感知机学习的损失函数。

感知机的损失函数
给定训练数据集：
T={(X1,y1),(x2,y2),...,(xn,yn)}
感知机学习的损失函数为：

学习算法（PLA）

感知机学习的问题此时候就转化成了损失函数的最优化问题。最优化的方法是 随机梯度下降法 。感知机学习的具体算法包括原始形式和对偶形式。以下我会一一介绍。

PLA原始形式

给定一个训练数据集
T={(X1,y1),(x2,y2),...,(xn,yn)}
求参数w，b，使其为以下损失函数极小化问题的解：

其中，M为误分类点的集合。

感知机学习是误分类驱动的，具体采用随机梯度下降。
首先，任意选取一个超平面w0,b0，然后使用梯度下降法不断极小化目标函数。
极小化过程中不是一次使M中所有的误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。

假设误分类点的集合M是固定的。那么损失函数L（w,b）的梯度由以下式子给出（对L(w,b)分别求偏导）：

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

式子中 η 是步长，在统计学习中又称为学习率。这样通过迭代可以是期望损失函数不断减小，直到为0。综上，得到如下算法：

原始形式
输入：训练数据集 T 、学习率 η
输出：w，b；感知机模型f（x）
（1）选取初值w0,b0；
（2）在训练集中选取数据（xi,yi）
（3）如果yi(wxi+b)<=0 ：

（4）转至（2），直到训练集中没有误分类点。

例题

假设有训练数据集：
正实例点是 x1=(3,3) ， X2=(4,3)
负实例点是 x3=(1,1)，使用感知机学习算法的原始形式求感知机模型：

（1）取初值：

（2）迭代第一次：

（3）迭代第二次：

（4）迭代第三次：

如此往复下去，直到对于所有的数据都满足：

此时候，没有误分类点，损失函数达到极小。

分离超平面为：

感知机模型为：

PLA对偶形式

如果描述两种物理现象的方程具有相同数学形式，则他们解的数学形式也是相同的，这就是对偶原理（dual principle）。所以，PLA对偶形式只不过是原始形式的另外一种表达方法。
对偶形式的出现得益于上述原始形式的迭代过程，我们将前三步中w和b的更新过程写出来：

假设修改了n次，那么：

则：

》》对偶形式
输入：训练数据集 T 、学习率 η
输出：α，b；感知机模型：

（1）选取初值α = 0，b = 0；
（2）在训练集中选取数据（xi,yi）
（3）如果

更新：

（4）转至（2），直到训练集中没有误分类点。

如下图，为什么要这样更新呢？

解释：

对偶形式中训练实例是以内积的形式出现，故先将内积求出，并以矩阵的方式存放，该矩阵叫做Gram矩阵。

例题

我们还是看上面的例题
（1）取初始值：

（2）第一步迭代：

（3）第二步迭代：

以此类推，最后得到的结果为：

注意：

两种形式的算法，在每步迭代的时候，其实是做了同样的操作。原始形式在每步迭代后，没有进行记录只是从上步推导下步的w，而对偶形式对迭代过程的每一步进行了记录（哪一个点被选取），并参与以后运算。

参考资料

• 知乎地址：
  https://zhuanlan.zhihu.com/p/27152953
  https://www.zhihu.com/question/26526858
• 《统计学习方法》 - 李航
• 《机器学习基石》- 林轩田