Rosenblatt感知器

一、引言

1958年，一位心理学家Rosenblatt发明了该感知器，所以被后人取名为Rosenblatt感知器。该感知器是第一个从算法上完整描述的神经网络。Rosenblatt感知器只能用于线性可分模式，并且Rosenblatt证明了当训练集(模式向量)取自两个线性可分的类时，感知器算法是收敛的，算法的收敛性证明称为感知器收敛定理。为方便描述，以下Rosenblatt感知器都简写为感知器。

二、感知器模型

感知器的符号流图

输入x：训练集/模式向量。

权值w：与感知器的分类效果密切相关。

偏置b：这只是一个常数，将决策边界从原点移开。

诱导局部域： $v = \sum_{i=1}^mw_ix_i+b$

硬限幅器/激活函数： $\varphi (v) = tanhv/sigmoid(v)/Relu(v)/阈值函数$ ，当然不同的激活函数有着不同的性能，在不同的环境下使用不同的激活函数。

输出y：若y=+1，则将所有输入分配给类1；若y=-1，则将所有输入分配给类2。

由此，我们可以定义超平面： $\sum_{i=1}^mw_ix_i+b =0$ ，可以令m=2进行验证。

感知器的自适应性可以使用通称为感知器收敛算法的误差修正规则，下面我们讨论本章的第二个重点，感知器收敛定理。

三、感知器收敛定理

为了方便导出感知器的误差修正学习算法，我们对上图的感知器符号流图稍作修改：

等价的感知器符号流图

在这个模型中我们将偏置b(n)当做一个等于+1的固定输入量所驱动的权值，这里的n代表算法的迭代步数。两者其实是等价的，因此我们可以定义一个(m+1)X1的输入向量：

$x(n)=[+1, x_1(n),x_2(n),...,x_m(n)]^T$

相应的，我们也需要定义(m+1)x1的权值向量：

$w(n)=[b,w_1(n),w_2(n),...,w_m(n)]^T$

因此，我们可以重写诱导局部域：

$v(n)=\sum_{i=0}^mw_i(n)x_i(n)=w^T(x)x(n)$

我们发现，这里的i是从0开始的，对应的值为b。对应于固定的n，由超平面的定义可知： $w^Tx=0$ 。

我们假设感知器的输入变量来源于两个线性可分的类。设H1为训练集中属于类1的子集，H2为训练集中属于类2的子集。H1∪H2=训练集。在感知器训练过程中，通过对权值的调整可以使得两个类别线性可分。即存在一个权值向量w具有以下性质：

$w^Tx>0 对属于类1 的每个输入向量x$ ；

$w^Tx≤0对属于类2 的每个输入向量x$ 。

在迭代过程中，权值向量能够满足上述性质，那么我们可以不对权值向量进行修改，公式表述为：

$w(n+1)=w(n)假如w^Tx(n)>0且x(n)输入类1$

$w(n+1)=w(n)假如w^Tx(n)≤0且x(n)输入类2$

否则，我们要对权值作如下修改：

$w(n+1)=w(n)-\eta (n)x(n)假如w^Tx(n)>0且x(n)输入类2$

$w(n+1)=w(n)+\eta (n)x(n)假如w^Tx(n)≤0且x(n)输入类1$

换句话说，本来属于类2你给判断错了，判断成属于类1了，我们需要调小权值向量；反之，等同。

这里的 $\eta (n)$ 表示学习率参数，控制着第n次迭代中作用于权值向量的调节，且是一个正数。

OK，到了这里，是讲完了怎么做的问题，下一步是要探究为什么的原因，即感知器收敛定理的证明：

1、首先证明当 $\eta$ =1时固定增量自适应规则的收敛性：

在算法迭代之前我们需要对权值向量做个初始化，不妨我们设w(0)=0。并且我们可以假设对n=1,2,...， $w^T(n)x(n)<0$ ，且输入向量x(n)属于H1。那么这种情况就是分类错误的情况，需要对权值向量进行修改，按照修改规则，并且学习率=1的情况下：

$w(n+1)=w(n)+x(n)$ ，对x(n)属于类1

由于w(0)=0，迭代求解上式得到如下方程：

$w(n+1)=x(1)+x(2)+...+x(n)$

由于训练集是线性可分的，如果不等式方程 $w^Tx(n)>0存在一个解w_0$ ，那么我们可以定义一个正数α,满足下列等式：

$\alpha =minw_0^Tx(n)，其中x(n)属于类1$

在迭代求解出来的方程中，我们两边同时乘以 $w_0^T$ ，我们有：

$w_0^Tw(n+1)=w_0^T(x(1)+x(2)+...+x(n))$

根据α的定义，我们可以推到出如下不等式：

$w_0^Tw(n+1)≥na$

利用柯西-施瓦茨不等式，我们可以导出如下不等式：

$||w_0||^2||w(n+1)||^2≥[w_0^Tw(n+1)]^2$

这样我们就有：

$||w_0||^2||w(n+1)||^2≥n^2α^2\Rightarrow ||w(n+1)||^2≥\frac{n^2\alpha ^2}{||w_0||^2}$

到了这一步，我们总算导出了 $||w(n+1)||^2$ 的下界，下面我们将导出它的上界。这里我们遵循另一种发展路线，我们可以写出如下的式子：

$w(k+1)=w(k)+x(k)$ ，k是从1到n，并且x(k)属于类1

这里注意了，我们采取的是对等式两边取欧几里得范数的平方，迭代求解了，区别就在这，即：

$||w(k+1)||^2=||w(k)||^2+||x(k)||^2+2w^T(k)x(k)$

由于感知器判断错误，即 $w^T(k)x(k)≤0$ ，那么我们可以得到如下不等式：

$||w(k+1)||^2≤||w(k)||^2+||x(k)||^2$

到这里，我们采取与求下界相同的方式迭代求取上界，即：

$||w(n+1)||^2≤\sum_{k=1}^n||x(k)||^2$

同理，我们设一个正数 $\beta$ ，定义为：

$\beta =max||x(k)||^2$ ，x(k)属于类1，那么我们可以将不等式写成下式：

$||w(n+1)||^2≤n\beta$

OK，到了这里，我们终于导出了 $||w(n+1)||^2$ 的上下界，即：

$n\alpha ≤||w(n+1)||^2≤n\beta$

由此，我们还可以解出n的范围，将α与β代入得：

$n_{max}=\frac{\beta ||w_0||^2}{\alpha ^2}$

这样我们证明了如果解向量 $w_0$ 存在，那么感知器权值的适应过程最多在 $n_{max}$ 迭代后终止。

简单的说明下为什么到这里感知器的固定增量收敛定理证明完毕：第一点权值向量是有界的，第二点在模式向量属于类1的情况下，权值是单调递增的，反之亦然。

下面我们考虑当 $\eta (n)$ 变化时单层感知器自适应的绝对误差修正过程，我们不妨设 $\eta (n)$ 是满足下式的最小整数：

$\eta (n)x^T(n)x(n)>|w^T(n)x(n)|$

这个不等式可以通过第二个权值向量修改规则推导出来，不清楚的可以私信我。

利用这个不等式我们可以发现第n次迭代时的內积 $w^T(n)x(n)$ 存在符号错误，那么第n+1次迭代时，符号就会是正确的，为啥子？书上讲解的不是很清楚，我们通过以下式子来看：

假设模式向量本属于类1，当感知器分类错误时，根据自适应性修正规则，我们有：

$w(n+1)=w(n)+\eta (n)x(n)$

对等式两边同乘以一个 $x^T(n)$ ，得到如下等式：

$x(n)^Tw(n+1)=x(n)^Tw(n)+\eta (n)x(n)^Tx(n)$

等价于：

$\eta (n)x^Tx(n)=w^T(n+1)x(n)-w^T(n)x(n)$

那么我们可以推出：

$w^T(n+1)x(n)>w^T(n)x(n)+|w^T(n)x(n)|$

OK，到了这一步大家再看，当第n次迭代时，符号发生错误，即 $sgn(w^T(n)x(n))=-1$ ，那么当第n+1次迭代时，符号一定正确。最后的实际响应我们采用符号函数sgn( `)，即：

$y(n)=sgn(w^T(n)x^T(n))$

到此为止，对于感知器的收敛性我们已经全部证明完毕。下面我们给出感知器的伪代码：

"""感知器收敛算法概述"""

变量和参数：

x(n)=m+1维输入向量： $[+1, x_1(n),x_2(n),...,x_m(n)]^T$

w(n)=m+1维权值向量： $[b,w_1(n),w_2(n),...,w_m(n)]^T$

b：偏置

y(n)：量化的实际响应

d(n)：期望响应

$\eta$ ：学习率参数， $0<\eta ≤1$

1、初始化：

w(0)=0，对时间步n=1,2,...执行下列计算

2、激活

在时间步n，通过提供连续值输入向量x(n)和期望响应d(n)来激活感知器

3、计算实际响应： $y(n)=sgn(w^T(n)x^T(n))$

4、权值向量的自适应性。更新感知器的权值向量： $w(n+1)=w(n)+\eta (d(n)-y(n))x(n)$

这里d(n)是与y(n)一样的符号函数。

5、继续。时间步增加1，返回第2步。

四、小结

最后想要补充说明的是，对于w(0)的权值选择，都能保证感知器是收敛的，但是会导致迭代次数增加或者减少。对于学习率参数的选择会导致收敛速度增加或者减少，对于一个稳定的权值估计需要一个较小的学习率，也可能为了快速自适应，需要一个较大的学习率，需要把握好之间的平衡。下节我们将讲述高斯环境下感知器与贝叶斯分类器的关系，并且给出相关的计算机实验。

本文参考《神经网络与机器学习》一书，但是由于此书晦涩难懂，特将自己的感想分享给大家，创作不易，点个赞呗。

注：文章若有不当之处，烦请多多指教。

Rosenblatt感知器

一、引言

二、感知器模型

三、感知器收敛定理

四、小结

推荐阅读更多精彩内容