《统计学习方法》（第二版）第2章
2 感知机
二类分类、线性分类模型、判别模型
输入：实例的特征向量
输出：实例的类别（+1，-1）
2.1 感知机模型
几何解释
(w·x+b=0)对应一个超平面(S)，(w)是超平面的法向量，(b)是超平面的截距。
法向量证明：从超平面上任取(overrightarrow{x_1})，(overrightarrow{x_2})，有(w·overrightarrow{x_1}+b=0)，(w·overrightarrow{x_2}+b=0)，两式相减可知(w·overrightarrow{x_2x_1}=0)，(w)与超平面上任一向量垂直，即为法向量。
2.2 感知机学习策略
数据集的线性可分性
存在某个超平面(S)能够将数据集(T)的正实例点和负实例点完全正确地划分到超平面的两侧。
感知机学习策略
自然选择：误分类点的总数（不是参数(w,b)的连续可导函数，不易优化）
另一个选择：误分类点到超平面(S)的总距离
对于任一点(x_0)到超平面(S)的距离：(frac{1}{||w||}|w·x_0+b|)（参见点到直线距离公式(d=frac{|Ax_0+By_0+C|}{sqrt{A^2+B^2}})）
则误分类点到超平面(S)的总距离：(-frac{1}{||w||}sum limits_{x_i in M} y_i(w·x_i+b))
所以损失函数(L(w,b)=-sum limits_{x_i in M}y_i(w·x_i+b))，其中(M)为误分类点的集合
2.3 感知机学习算法
原始形式
采用随机梯度下降法stochastic gradient descent，极小化目标函数
( abla_w L(w,b)=-sum limits_{x_i in M}y_ix_i)
( abla_b L(w,b)=-sum limits_{x_i in M}y_i)
步骤：
-
选取初值(w_0,b_0)
-
在训练集中选取数据((x_i,y_i))
-
如果$ y_i(w·x_i+b) le 0$，
[w ← w + eta y_ix_i \ b ← b + eta y_i ] -
转至2.，直至训练集中没有误分类点，即(L(w,b)=0)。
算法收敛性
误分类的次数是有上界的，经过有限次搜索可以找到将训练数据完全分开的分离超平面。
其中(R=max limits_{1 le i le N}|hat x_i|)，(y_i(hat w_{opt}·hat x_i)=y_i(w_{opt}·x_i+b_{opt}) ge gamma)
对偶形式
即(w=sum limits_{j=1}^N alpha_jy_jx_i,b=sum limits_{j=1}^N alpha_jy_j)
(alpha=n_ieta)，当(N=1)时，表示第(i)个实例点由于误分而进行更新的次数。
(Gram)矩阵：(G=[x_i·x_j]_{N×N})
步骤：
-
(alpha←0，b←0)
-
在训练集中选取数据((x_i,y_i))
-
如果$ y_i(sum limits_{j=1}^N alpha_jy_jx_i+b) le 0$，
[alpha_i ← alpha_i + eta \ b ← b + eta y_i ] -
转至2.，直至训练集中没有误分类点。
扩展学习方法
口袋算法、表决感知机、带边缘感知机