大概3年前第一次学习Perceptron(感知机)的时候，就已经写过相关的博文。但是，当时仅仅只是在搬运知识而已，其实当时很多内容自己都是一知半解的。但是现在随着学习的深入，逐渐领悟到了更多的东西，逐渐理清了整个体系。因此，觉得有必要再好好整理输出一下，加深理解。

Perceptron(感知机)

Perceptron(感知机)算是机器学习中最简单的模型之一了，其基本框架如下所示:

Input: A sequence of training examples $(x_1,y_1),(x_2,y_2),\cdots$, 其中$x_i\in R^n,y_i\in \{-1,1\}$

初始化: $w_0=0\in R^{n+1}$
对于每一个训练样本$(x_i,y_i)$:
- 使用权重$w_t$进行预测:{% math %}y^{'}=sgn(x_t^T x_i){% endmath %}
- 如果$y_i\neq y^{'}$: 更新$w_{t+1}=w_t+r(y_ix_i)$
返回最终的权重

Perceptron的Mistake Bound

Perceptron是针对线性可分数据的一种分类器，它属于Online Learning的算法。我在之前的一篇博文中提到了Online Learning模型的Mistake Bound衡量标准。现在我们就来分析一下Perceptron的Mistake Bound是多少。

在分析其Mistake Bound之前，我们首先需要定义几个概念。

我们使用$R$表示训练数据集中距离原点最远的点的距离。也就是说，对于数据集$(x_1,y_1),(x_2,y_2),\cdots,(x_m,y_m)$来说，其中任意一个实例$(x_i,y_i)$都满足$\Vert x_i \Vert\le R$.
Perceptron最终学习到的其实是一个分割正负例数据的超平面，我们定义数据集中距离超平面距离最近的点的距离为$\gamma$

在定义了上述两个概念之后，我们就能给出结论:Perceptron的Mistake Bound是: $(\frac{R}{\gamma})^2$.

也就是说，Perceptron在训练集上最多会犯$(\frac{R}{\gamma})^2$次错误. 这被称为Novikoff定理.

Novikoff定理的证明

在开始我们的证明过程之前，我们首先需要明确一些基本设定:

数据是线性可分的
权重初始值为0向量，且更新步长为1.
训练集中最远点的距离为$R$
$u$是一个单位向量，且能够完美分割数据的最优超平面(因为已经假设数据是线性可分的，因此$u$必然是存在的)
$\gamma$是数据集中距离超平面$u$最近点的距离

另外，我们需要知道Perceptron的更新条件和更新法则:

Perceptron更新条件是: $y_i(w_t x_i) < 0$
Perceptron的更新法则是: $w_{t+1}=w_t+r(y_i x_i)$

要证明Novikoff定理，我们只需要证明如下两个不等式.

1. $u^Tw_t\ge t\gamma$

假设Perceptron在学习过程中已经犯了$t$次错误,则:

$$ \begin{aligned} u^Tw_{t+1} &= u^T(w_t+y_ix_i)\\ &= u^Tw_t + u^T y_i x_i\\ &\ge u^Tw_t + \gamma \end{aligned} $$

其中第一个等号是根据Perceptron的更新法则得到的
不等号是因为: 实际上$u^T y_i x_i$表示的是点$x_i$到超平面$u$的距离，因此这个距离必然大于等于$\gamma$.

又因为$w$的初始值为$0$向量，利用归纳法，我们能得到$u^Tw_t\ge t\gamma$.

2. $\Vert w_t\Vert^2 \le tR^2$

假设Perceptron载学习过程中已经犯了$t$次错误，则:

$$ \begin{aligned} \Vert w_{t+1} \Vert^2 &= \Vert w_t+x_i y_i \Vert^2 \\ &= w_t^2 + 2w_t x_i y_i + x_i^2\\ &\le w_t^2 + R^2 + 2w_t x_i y_i \\ &\le w_t^2 + R^2 \end{aligned} $$

其中第一个等号是根据Perceptron的更新法则得到的
第一个不等号是根据$R$的定义得到的
第二个不等号是因为根据Perceptron的更新条件:$w_t x_i y_i <0$.

又因为$w$的初始值为$0$向量，利用归纳法，我们能得到$\Vert w_t\Vert^2 \le tR^2$.

综合

根据前面两个不等式，我们有:

$\Vert w_t \Vert \le \sqrt{t}R$
$u^Tw_t\ge t\gamma$
$u^Tw_t \le \Vert w_t\Vert$

第三个不等式是因为:

$$ u^Tw_t = \Vert u^T \Vert \cdot \Vert w_t \Vert \cdot \cos(\theta) = \Vert w_t \Vert \cdot \cos(\theta) \le \Vert w_t\Vert $$

因此根据这三个不等式，我们能得到:

$$ t\gamma \le u^Tw_t \le \Vert w_t\Vert \le \sqrt{t} R \Rightarrow t\gamma \le \sqrt{t}R \Rightarrow t\le(\frac{R}{\gamma})^2 $$

证明完成!

Novikoff定理

Novikoff定理说明了Perceptron的可学习性，也就是说针对任意的线性可分的数据，Perceptron最多犯$(\frac{R}{\gamma})^2$次错误就能学到最优的超平面。同时，也说明了Perceptron算法的收敛性: 只要数据是线性可分的，该算法就一定会收敛。

参考资料

Vivek Srikumar教授的课件

更新日志

2016年10月10日完成初稿并发布。
2016年10月11日修正了一些书写错误。

Flyaway is the owner of this blog.

So what do you think? Did I miss something? Is any part unclear? Leave your comments below

Comments

Perceptron的Mistake Bound

Perceptron(感知机)

Perceptron的Mistake Bound

Novikoff定理的证明

1. \(u^Tw_t\ge t\gamma\)

2. \(\Vert w_t\Vert^2 \le tR^2\)

综合

Novikoff定理

参考资料

更新日志

Comments

Published

Category

Tags

Contact