在这一讲中，我们将重点介绍美国科学家Frank Rosenblatt(1928-1971)如何对神经元的MP模型进行改造，用于解决二分类的问题。

图1 Frank Rosenblatt(1928-1971)

1. 回顾

回顾上一讲的内容，神经元的MP模型：

图2 神经元生理结构示意图

图3 神经元的数学模型示意图

它的输出

2. 感知器算法

1957年，Frank Rosenblatt从纯数学的度重新考察这一模型，指出能够从一些输入输出对(X,y)中通过机器学习算法自动获得权重W和偏置b，以此，他提出感知器算法(Perceptron Algorithm)。

2.1 感知器算法的实现步骤

这里我们仍然假设输入的样本表示为给定一些输入输出对($X_i$,$y_i$)，$i$=1~N，这是一个二分类问题，其中，$X_i$是训练数据；$y_i=\pm 1$，分别代表相应的类别。

我们的任务是要找一个向量W和一个常数b，使得对$i=1\cdot \cdot \cdot N$，有
（1）$y_i=+1$，则$W^T{X}_i+b>0$
（2）$y_i=-1$，则$W^T{X}_i+b<0$
把某个训练数据$X_i$满足上述的条件，叫作这个数据获得了平衡，否则没有获得平衡。可见，一个数据$X_i$没有获得平衡也有两种情况：
（1）$y_i=+1$，则$W^T{X}_i+b<0$
（2）$y_i=-1$，则$W^T{X}_i+b>0$
可以看到，这个任务与前面支持向量机的任务完全一致。

我们已经学习过，当且仅当在训练数据集线性可分的情况下，才能找到W和b满足使所有的$n$个训练样本都达到平衡，感知器算法给出了另一种不同于支持向量机寻找W和b的方法，其做法包含如下四个步骤：
（1）随机选择W和b。
（2）取一个训练样本(X,y)
  (i) 若$W^{T}X+b>0$且$y=-1$，则：
   $w=W-X,b=b-1$
  (ii) 若$W^{T}X+b<0$且$y=+1$，则：
  $w=W+X,b=b+1$
（3）再取另一个(X,y) ，回到（2）
（4）终止条件：直到所有输入输出对都不满足（2）中(i)和(ii)之一，退出循环

从第二步（2）可以看出，这是一个没有达到平衡状态的情况，因此，我们需要对W和b进行调整。

分析第二步（2）的第一种情形，即当$y=-1$时，调整方式如下：
$W(新)=W(旧)-X，b(新)=b(旧)-1$

将上式代入下式

$W(新{)}^{T}X+b(新)=(W(旧)-X{)}^{T}X+b(旧)-1=[W(旧{)}^{T}X+b(旧)]-(X^{T}X+1)=[W(旧{)}^{T}X+b(旧)]-(||X|{|}^2+1)\le [W(旧{)}^{T}X+b(旧)]-1$
使得$X$距离平衡状态至少近了一点；

当$y=+1$时，
$W(新)=W(旧)+X，b(新)=b(旧)+1$

将上式代入下式

$W(新{)}^{T}X+b(新)=(W(旧)+X{)}^{T}X+b(旧)+1=[W(旧{)}^{T}X+b(旧)]+(X^{T}X+1)=[W(旧{)}^{T}X+b(旧)]+(||X|{|}^2+1)\ge [W(旧{)}^{T}X+b(旧)]+1$
使得$W^{T}X+b$的值比原来至少大了1。

2.2 算法能停得下来吗？

有没有可能出现W和b在某一步的变化使某个数据从不平衡状态达到了平衡状态，但同时却使另一个数据从平衡状态变为了不平衡状态呢？如果是这样，将有可能出现循环无法终止的局面。

Rosenblatt发明感知器算法时，最具创意的一步是严格地证明了只要训练数据线性可分，那么感知器算法一定可以停下来。

在描述这个定理的时候，我们需要做一些定义，对于某个训练数据$X_i$，我们定义它的增广向量如下：
（1）若$y_i=+1$，则 ${\vec{x}}_i=\left[\begin{array}{c}{x}_i\\ 1\end{array}\right]$
（2）若$y_i=-1$，则 ${\vec{x}}_i=\left[\begin{array}{c}-x_i\\ -1\end{array}\right]$

定义增广向量的目的是简化我们的表达，原任务是寻找$（W，b）$使得$i=1\cdot \cdot \cdot N$，有：
（1）$y_i=+1$，则$W^T{X}_i+b>0$
（2）$y_i=-1$，则$W^T{X}_i+b<0$

有了增广向量这个定义后，简化表达为寻找 $W=\left[\begin{array}{c}W\\ b\end{array}\right]$使得对$i=1\cdot \cdot \cdot N$，有：
$W^T{\vec{x}}_i>0$

2.3 基于增广向量的感知器算法

最初是随机的寻找一个W，接下来如果对于$i=1\cdot \cdot \cdot N$的某一个$i$，若$W^T{\vec{x}}_i\le 0$，那么$w=w+{\vec{x}}_i$，以此循环直到对于所有的$i=1\cdot \cdot \cdot N$，$W^T{\vec{x}}_i>0$为止。

可以证明基于增广向量的感知器算法和原来的感知器算法也是完全等价的。
下面利用增广向量的感知器算法来证明感知器算法收敛定理。

2.4 感知器算法收敛定理

对于$N$个增广向量${\vec{x}}_1,{\vec{x}}_2,\cdot \cdot \cdot ,{\vec{x}}_N$，如果存在一个权重向量$w_{opt}$，使得对于每一个$i=1\cdot \cdot \cdot N$，有
$$w_{opt}^t{\vec{x}}_i>0$$
运用上述感知器算法，在有限步内找到一个$w$，使得对所有的$i=1\cdot \cdot \cdot N$，有$w^T{\vec{x}}_i>0$。

需要注意的是这个定理的一个条件，即存在一个权重向量$w_{opt}$使得对于每一个${\vec{x}}_i$的增广向量有$w_{opt}^t{\vec{x}}_i>0$，这个条件与训练数据集线性可分是完全等价的。另外需要注意，当训练数据集线性可分的情况下，在有限步内找到的$w$不一定是$w_{opt}$，回顾线性可分的定义，如果存在一个超平面分开两类，则一定存在无数个平面分开两类，而$w$与$w_{opt}$是这无数多个超平面中的两个。

感知器收敛定理证明如下：

首先我们假设$||w_{opt}||=1$（向量$\vec{W}$和$a\vec{W}$代表的是同一个平面，因此我们可以用一个$a$去加权$w_{opt}$，使$||w_{opt}||=1$）

定义$w(k)$为第$k$次改变后的权重向量值，那么会有以下两种情况：

情况1：

情况2：

将这个式子两边同时减去$a{w}_{opt}$

取模并展开
$$||w(k+1)-a{w}_{opt}|{|}^2=||w(k)-a{w}_{opt}+{\vec{x}}_i|{|}^2=||w(k)-a{w}_{opt}|{|}^2+||{\vec{x}}_i|{|}^2+2w(k{)}^T{\vec{x}}_i-2a{w}_{opt}^T{\vec{x}}_i$$

又由于：

我们有：

$w$的值每更新一次，它离$a{w}_{opt}$的距离至少减少1个单位。

假设：$w$的初值为$w(0)$，经过$||w(0)-a{w}_{opt}|{|}^2$ 次迭代，$w$一定会收敛到$a{w}_{opt}$。当然，也有可能没有经过这么多次迭代，感知器算法已经收敛并退出循环了。

以上完成了感知器算法的证明。

3. 感知器算法收敛的MATLAB程序演示

下面这幅图是二维特征空间线性可分的例子

设置最初的$w$值，如下图直线所示

接下来，调用感知器算法不断的更新这条直线的方程。

可以看到这条直线以一种无规律的方式不断运动，似乎看不到它收敛的时候，但是感知器算法收敛定理保证了只要训练数据集线性可分，就一定能收敛。

最后，经过多轮的迭代后，它收敛到了这里，完全分开了两个类别。

作为本讲的结束，有两道思考题：
（1）如果训练数据集线性不可分，那么感知器算法是否还收敛呢？请证明你的结论。
（2）如果此时感知器算法不收敛，你能否改造一下这个算法，使它在线性不可分的情况下，能自动终止循环呢？

参考资料

浙江大学《机器学习》课程—胡浩基老师主讲