4.3　感知器算法

Fisher 线性判别把线性分类器的设计分为两步：首先确定最优的投影方向；然后在这个投影方向上确定分类阈值。下面介绍一种可直接得到完整的线性判别函数的方法——感知器（Perceptron）[3]。

为了讨论方便，把向量增加一维，但其取值为常数，即定义为

其中，为样本的第i维分量；y为增广的样本向量。相应地，定义增广的权向量为

线性判别函数变为

如果定义一个新的变量y'，使对于第一类样本y'=y，而对于第二类样本y'=−y，即

其中，i=1,2,…,N，则样本可分性条件就变成了存在，使

这样定义的y'称为规范化增广样本向量。为了讨论方便，都采用规范化增广样本向量，并且把y'仍然记作y。

对于线性可分的一组样本，用规范化增广样本向量表示，若一个权向量满足

则称为一个解向量。在权值空间中，所有解向量组成的区域称为解空间。

显然，权向量和样本向量的维数相同，对于一个样本，定义了权空间中一个过原点的超平面。对于这个样本来说，处于超平面正侧的任何一个向量都能使，因而都是对这个样本的一个解。考虑样本集中的所有样本，解空间就是每个样本对应超平面正侧的交集，如图4-8中的阴影区域所示。

解空间中的任意一个向量都是解向量，都能把样本没有错误地分开。但是，从直观角度看，如果一个解向量靠近解空间的边缘，虽然所有样本都能满足，但某些样本的判别函数可能刚刚大于零，考虑到噪声误差等因素，靠近解空间中间的解向量应该是更加可信的。

所以要求余量b>0，即把解空间向中间聚集，只考虑靠近中心的解，如图4-9中的阴影区域所示。以公式表示就是要求解向量满足

如何找到一个解向量？对于权向量，若某个样本被错误地分类，则。可以用对所有错分样本的求和来表示对错分样本的惩罚，即

这就是Rosenblatt提出的感知器准则函数[4]。

显然，当且仅当时，是解向量。感知器准则函数式（4-35）的最小化可以用梯度下降法迭代求解。

即下一次迭代的权向量是把当前时刻的权向量向目标函数的负梯度方向进行修正，其中为修正的步长。目标函数对权向量的梯度为

因此，迭代修正的公式为

即在每一步迭代时，把错分的样本按照某个系数加到权向量上。

通常情况下，一次将所有错误样本都进行修正的做法并不是效率最高的，更常用的是每次只修正一个样本的固定增量法，其步骤如下。

（1）任意选择初始的权向量，置t=0。

（2）考查样本，若，则；否则继续。

（3）考查另一个样本，重复步骤（2），直至对所有样本都有，即=0。

若考虑余量b，则只需将上面算法中的错分判断条件变成即可。

这种单步的固定增量法采用的修正步长为=l。为了减少迭代步数，还可以使用可变的步长。如绝对修正法就对错分样本用下面的步长来调整权向量。

上述感知器算法只能解决线性可分的问题，因此在实际应用中，直接使用它的场合并不多，但它是很多更复杂算法的基础，如支持向量机和包含多层感知器的人工神经网络。

感知器算法要求样本是线性可分的，通过梯度下降法有限次的迭代后就可以收敛得到一个解。当样本非线性时，使用感知器算法不会收敛。若让算法任意地停止在某一时刻，则无法保证得到的解能够正确分类样本中的大多数。为了使感知器算法在样本集不是线性可分时仍能得到收敛的解，可以在梯度下降过程中让步长按照一定的规则逐渐缩小，这样就可以强制让算法收敛。如果只有小部分样本线性不可分，那么这种强制收敛的做法还是有效的。