大概3年前第一次学习Perceptron(感知机)的时候，就已经写过相关的博文。 但是，当时仅仅只是在搬运知识而已，其实当时很多内容自己都是一知半解的。 但是现在随着学习的深入，逐渐领悟到了更多的东西，逐渐理清了整个体系。 因此，觉得有必要再好好整理输出一下，加深理解。
Perceptron(感知机)
Perceptron(感知机)算是机器学习中最简单的模型之一了，其基本框架如下所示:
Input: A sequence of training examples (x1,y1),(x2,y2),⋯, 其中xi∈Rn,yi∈{−1,1}
- 初始化: w0=0∈Rn+1
- 对于每一个训练样本(xi,yi):
- 使用权重wt进行预测:{% math %}y^{'}=sgn(x_t^T x_i){% endmath %}
- 如果yi≠y′: 更新wt+1=wt+r(yixi)
- 返回最终的权重
Perceptron的Mistake Bound
Perceptron是针对线性可分数据的一种分类器，它属于Online Learning的算法。 我在之前的一篇博文中提到了Online Learning模型的Mistake Bound衡量标准。 现在我们就来分析一下Perceptron的Mistake Bound是多少。
在分析其Mistake Bound之前，我们首先需要定义几个概念。
- 我们使用R表示训练数据集中距离原点最远的点的距离。 也就是说，对于数据集(x1,y1),(x2,y2),⋯,(xm,ym)来说，其中任意一个实例(xi,yi)都满足‖xi‖≤R.
- Perceptron最终学习到的其实是一个分割正负例数据的超平面，我们定义数据集中距离超平面距离最近的点的距离为γ
在定义了上述两个概念之后，我们就能给出结论:Perceptron的Mistake Bound是: (Rγ)2.
也就是说，Perceptron在训练集上最多会犯(Rγ)2次错误. 这被称为Novikoff定理.
Novikoff定理的证明
在开始我们的证明过程之前，我们首先需要明确一些基本设定:
- 数据是线性可分的
- 权重初始值为0向量，且更新步长为1.
- 训练集中最远点的距离为R
- u是一个单位向量，且能够完美分割数据的最优超平面(因为已经假设数据是线性可分的，因此u必然是存在的)
- γ是数据集中距离超平面u最近点的距离
另外，我们需要知道Perceptron的更新条件和更新法则:
- Perceptron更新条件是: yi(wtxi)<0
- Perceptron的更新法则是: wt+1=wt+r(yixi)
要证明Novikoff定理，我们只需要证明如下两个不等式.
1. uTwt≥tγ
假设Perceptron在学习过程中已经犯了t次错误,则:
- 其中第一个等号是根据Perceptron的更新法则得到的
- 不等号是因为: 实际上uTyixi表示的是点xi到超平面u的距离，因此这个距离必然大于等于γ.
又因为w的初始值为0向量，利用归纳法，我们能得到uTwt≥tγ.
2. ‖wt‖2≤tR2
假设Perceptron载学习过程中已经犯了t次错误，则:
- 其中第一个等号是根据Perceptron的更新法则得到的
- 第一个不等号是根据R的定义得到的
- 第二个不等号是因为根据Perceptron的更新条件:wtxiyi<0.
又因为w的初始值为0向量，利用归纳法，我们能得到‖wt‖2≤tR2.
综合
根据前面两个不等式，我们有:
- ‖wt‖≤√tR
- uTwt≥tγ
- uTwt≤‖wt‖
第三个不等式是因为:
因此根据这三个不等式，我们能得到:
证明完成!
Novikoff定理
Novikoff定理说明了Perceptron的可学习性，也就是说针对任意的线性可分的数据，Perceptron最多犯(Rγ)2次错误就能学到最优的超平面。 同时，也说明了Perceptron算法的收敛性: 只要数据是线性可分的，该算法就一定会收敛。
参考资料
- Vivek Srikumar教授的课件
更新日志
- 2016年10月10日完成初稿并发布。
- 2016年10月11日修正了一些书写错误。