感知机
感知机是根据输入实例的特征向量 x 对其进行二类分类的线性模型：
f(x)=sign(w⋅x+b)

感知机模型对应于输入空间（特征空间）中的分离超平面 w⋅x+b=0w⋅x+b=0.其中w是超平面的法向量，b是超平面的截距。
可见感知机是一种线性分类模型，属于判别模型。

感知机学习的假设
感知机学习的重要前提假设是训练数据集是线性可分的。

感知机学习策略
感知机学的策略是极小化损失函数。

损失函数的一个自然选择是误分类点的总数。但是，这样的损失函数不是参数 w, b的连续可导的函数，不易于优化。所以通常是选择误分类点到超平面 S 的总距离：

学习的策略就是求得使 L(w,b) 为最小值的 w 和 b。其中 M 是误分类点的集合。

感知机学习的算法
感知机学习算法是基于随机梯度下降法的对损失函数的最优化算法，有原始形式和对偶形式，算法简单易于实现。

原始形式

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

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

b←b+ηyi

其中 η(0<η≤1)η(0<η≤1)是学习率。

对偶形式
对偶形式的基本想法是，将 w 和 b 表示为是咧 xixi 和标记 yiyi的线性组合的形式，通过求解其系数而得到 w 和 b。
w←w+ηyixi

b←b+ηyi

逐步修改 w,b，设修改 n 次，则 w,b 关于 (xi,yi)(xi,yi) 的增量分别是 αiyixi和 αiyiαiyi, 这里 αi=niη。最后学习到的 w,b 可以分别表示为：

 

 

 

这里， αi≥0,i=1,2,...,Nαi≥0,i=1,2,...,N,当 η=1η=1时，表示第i个是实例点由于误分类而进行更新的次数，实例点更新次数越多，说明它距离分离超平面越近，也就越难区分，该点对学习结果的影响最大。
感知机模型对偶形式：
f(x)=sign(∑j=1Nαjyjxj⋅x+b)
其中
α=(α1,α2,...,αN)T

学习时初始化 α←0,b←0α←0,b←0, 在训练集中找分类错误的点，即：
yi(∑j=1Nαjyjxj⋅xi+b)≤0

然后更新：
αi←αi+η

b←b+ηyi

知道训练集中所有点正确分类
对偶形式中训练实例仅以内积的形式出现，为了方便，可以预先将训练集中实例间的内积计算出来以矩阵的形式存储，即 Gram 矩阵。