统计学习方法(一):感知机
感知机
模型
感知机是一种二类分类的线性分类模型,属于判别模型。感知机的数据集要求线性可分。
学习策略
对于误分类的数据
忽略
感知机学习算法
原始形式
由上文知感知机的学习目标为
该学习方法的直观解释为:当一个实例点被误分类,则调整
感知机算法由于采用不同的初值或选取不同的误分类点,解可能会不同
算法的收敛性
为便于叙述,令
- 存在满足条件
的超平面 将训练数据集完全正确分开,且存在 ,对所有
- 令
,则该算法在训练数据集上误分类的次数 满足不等式
证明如下:
- 由于训练数据集数线性可分的,则存在超平面可将训练数据集完全正确分开,任取符合条件的超平面
,通过缩放调整 。此时对于训练数据集,有 所以存在 使 - 首先参数
对误分类点有如下更新方法 ,其中 为第 个误分类实例 (这里应理解为第 次更新误分类而不是第 个误分类点) 更新前的权重向量。对更新方法的两侧同乘 ,有 取 ,递推得 对更新方法的范数两边平方有 由于 ,上式右边第三项的 被省略,且对于误分类点有 (这里为小于等于,不影响最后的结果),则上式满足 结合公式 (1) 和 (2),有 即 于是我们可以得到误分类的次数 是有上界的,算法可以经过有限次搜索将训练数据完全线性分开,即算法是收敛的。