1.什么是感知机
感知机是一种线性的二分类模型，输入为数据的特征向量，而输出为数据的类型（+1或者-1）。
2.感知机模型
f(x)=sign(w⋅x+b)
-
w为权重
-
b为权重
f(x)={+1,−1,x≥0x<0
感知机相当于利用平面w⋅x+b=0这个平面将特征空间一分为二，分别代表正类存在的空间和负类存在的空间，如下图所示。
3.感知机的适用条件
感知机要求训练数据是线性可分的，也就是说特征空间R中必须存在某个线性平面可以完全正确的将数据分割为正类和负类，而对于不存在这个平面的时候，感知机是不适用的，如下图所示。
如上图所示这里不存在一个平面可以完美将数据分割开，所以这种情况下感知机不适用。
4.感知机的学习策略
4.1损失函数与风险函数
所有误分类点到分割平面S的总距离，如下所示。
−1||w||∑xi∈Myi(w⋅xi+b)
这里如果不考虑
||w|| 的话就可以得到感知机的损失函数，如下：
L(w,b)=−∑xi∈Myi(w⋅xi+b)
这个函数也就是感知机的经验风险函数。
4.2学习算法
感知机采用的学习算法是随机梯度下降法，其中风险函数的梯度如下：
∇wL(w,b)=−∑xi∈Myixi
∇bL(w,b)=−∑xi∈Myi
具体的计算流程如下
1.选取初始的
w0,b0
2.选取一个误分类点更新参数
wk−1→wk−1+ηyixi
bk−1→bk−1+ηyi
3.转至2循环执行，直到没有误分类点
4.3学习算法的收敛性证明
4.3.1定理
为了后面推导方便这里参数记为wˆ=(wT,b)T,xˆ=(xT,1)T。显然上面的式子满足wˆ⋅xˆ=w⋅x+b。
由于训练集是线性可分的，所以存在||wˆopt||=1的超平面wˆopt⋅xˆ=0可以将训练集正确分开，而且存在γ>0对于所有的训练集数据都满足:
yi(wˆopt⋅xˆ)≥γ
这种情况下感知机学习算法的误分类次数满足如下条件：
k≤(Rγ)2
式中
R=max1≤i≤N||xˆ||
4.3.2具体证明
(1)由学习算法的参数更新可以得出:
wˆk←wˆk−1+ηyixˆi
wˆk⋅wˆopt=wˆk−1⋅wˆopt+ηyiwˆopt⋅xˆi
wˆk−1⋅wˆopt+ηyiwˆopt⋅xˆi≥wˆk−1⋅wˆopt+ηγ
通过对上面的式子递推可以得到：
wˆk≥wˆ0+kηγ
(2)
||wˆk||2=||wˆk−1||2+2ηyiwˆk−1⋅xˆi+η2||xˆi||2
由于
xˆi是误分类点，所以第二项小于0，所以可得：
||wˆk||2≤||wˆk−1||2+η2||xˆi||2≤||wˆk−1||2+η2R2
递推得到如下结果：
||wˆk||2≤||wˆ0||2+kη2R2
当
||wˆ0||=0时，结合(1)(2)可以得出如下不等式:
kηγ≤wˆk⋅wˆopt≤||wˆk||||wˆopt||≤k√ηR
所以
k≤(Rr)2
4.3.3关于收敛性的思考
看到上面的推论，我们会发现一个问题步长η的大小不影响迭代的次数上限，但是步长不是会影响学习速度吗？如果步长特别小的话，需要的迭代次数不是会特别多吗？
关于这个问题，我们看到上面的定理的假设就是wˆ0=0，初值为0的话，之后每一次迭代产生的平面都可以表达为∑ηyixˆi=0，进一步化简可以变为∑yixˆi=0。这个时候就可以看出平面与步长没有关系，所以在初值为0的时候迭代次数上限与步长没有关系。
5.感知机的对偶形式
根据上面的推论，初值为0的时候wˆ的结果为x,y线性组合的结果，感知机对偶形式的思想是通过求解这个线性组合的系数来求解wˆ。具体的形式如下:
f(x)=sign(∑j=1Najyjxj⋅x+b)
每次更新参数与原始形式本质一样，对于误分类点按如下方式更新:
ai←ai+η
b←b+ηyi
从形式上就可以看出感知机两种形式没有本质上的区别，对偶形式是原始形式在初值为0下的一个变形。
