感知机

1 感知机原理

感知机是二分类的线性模型，其输入是实例的特征向量，输出的是事例的类别，分别是+1和-1，属于判别模型。假设训练数据集是线性可分的，感知机学习的目标是求得一个能够将训练数据集正实例点和负实例点完全正确分开的分离超平面。如果是非线性可分的数据，则最后无法获得超平面

1.1 点到直线的距离

公式中的直线方程为Ax+By+C=0，点P的坐标为(x0,y0)。

1.2 样本到分类超平面的距离

我们假设超平面是h=w⋅x+b，其中w=(w0, w1, ... wm)，x=(x0, x1, ... xm)，样本点x′到超平面的距离如下：

2维空间中的超平面是一条线，在3维空间中的超平面是一个平面。

2 感知机模型

感知机从出入空间到输出空间的模型如下：

2.1 感知机损失函数

2.2 为什么可以不考虑 1/ ||w||

3 感知机学习算法

感知机学习算法是对上述损失函数进行极小化，求得 w 和 b。但是用普通的基于所有样本的梯度和的均值的批量梯度下降法（BGD）是行不通的，原因在于我们的损失函数里面有限定，只有误分类的M集合里面的样本才能参与损失函数的优化。所以我们不能用最普通的批量梯度下降,只能采用随机梯度下降（SGD）。目标函数如下：

3.1 原始算法形式

输入：训练数据集T=(x1,y1)，(x2,y2)，...，(xN,yN)，yi∈{−1,+1}，学习率η(0<η<1)

输出：w,b；感知机模型f(x)=sign(w⋅x+b)

（1）赋初值w0，b0

（2）选取数据点（xi,yi）

（3）判断数据点是否为当前模型的误分类点，即判断若yi(w⋅xi+b)<=0则更新

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

3.2对偶形式算法

由于w,b的梯度更新公式：

我们的w,b经过了n次修改后的，参数可以变化为下公式，其中α=ny：

3.3 原始形式和对偶形式的选择

在向量维数（特征数）过高时，计算内积非常耗时，应选择对偶形式算法加速。

在向量个数（样本数）过多时，每次计算累计和就没有必要，应选择原始算法。

4 训练过程

线形可分的过程：

超平面最终趋于稳定

线形不可分的过程：

超平面将一直震荡

5 总结

感知机算法是一个简单易懂的算法，自己编程实现也不太难。前面提到它是很多算法的鼻祖，比如支持向量机算法，神经网络与深度学习。因此虽然它现在已经不是一个在实践中广泛运用的算法，还是值得好好的去研究一下。感知机算法对偶形式为什么在实际运用中比原始形式快，也值得好好去体会。