感知机学习规则收敛性证明

感知机的学习规则十分简单，但他非常有效。实际上可以证明：只要权值的解存在，该规则总能收敛到实现期望分类的权值上。

由单神经元感知机的输出可得下式：

\[a = hardlim(1^{W^T} p + b)\]

网络提供了正确反映网络行为的下述实例：

{p1, t1}, {p2, t2},…,{pq, tq}

其中每个目标的输出 tq 取值 0 或 1

记号

为了方便证明过程，引入几个记号：

权值偏置组合为一个向量：

\[X = \begin{bmatrix} 1^W\\ b \end{bmatrix}\]

同样，在输入向量中也增加一个参数 1 ，以表示偏置输入：

\[Z_q = \begin{bmatrix} P_q\\ 1 \end{bmatrix}\]

现在可以将神经元的净输入值表示为：

\[n = 1^{W^T} p + b = X^T Z\]

那么感知机学习规则可写为：

\[X^{new} = X^{old} + eZ\]

误差 e 可以去 1， 0 和 -1。如果 e = 0，那么权值不变；如果 e = 1，则将输入向量和权值向量相加；如果 e = -1，则将权值向量减去输入向量。如果只考虑权值向量发生改变的那些迭代，则该学习规则变为：

\[X(k) = X(k - 1) + Z'(k - 1) （式：1）\]

其中Z’(k - 1)是如下集合的元素：

\[\{ Z_1, Z_2, \dots , Z_Q, -Z_1, -Z_2, \dots , -Z_Q \} （式：2）\]

现在假设存在对所有 Q 个输入向量进行正确分类的权值向量 $ X^* $，对该权值向量，假设：

\[如果 t_q = 1, 那么 X^{*T} Z_q > \delta > 0 （式：3）\]

以及

\[如果 t_q = 0, 那么 X^{*T} Z_q < -\delta < 0 （式：4）\]

证明

下面开始感知机收敛证明，为此必须找出算法每一阶段权值向量长度的上界和下届。

假设算法的初始权值向量为 0 ，也即是 X(0) = 0。这么并不影响参数的普遍性。那么迭代 k 次后，由（式：1）得：

\[X(k) = Z'(0) + Z'(1) + \dots + Z'(k - 1)\]

迭代 k 次后的权值向量和最终的权值向量解 $ X^* $ 之间的内积，可得

\[X^{*T} X(k) = X^{*T} Z'(0) + X^{*T} Z'(1) + \dots + X^{*T} Z'(k - 1)\]

由（式：2）到（式：4）可知：

\[X^{*T} Z'(i) > \delta\]

所以

\[X^{*T} X(k) > k\delta （式：5）\]

由柯西不等式：

\[(X^{*T} X(k))^2 \leq ||X^*||^2 ||X(k)||^2 （式：6）\]

其中

\[||X^*||^2 = X^TX\]

（式：5）和（式：6）结合，则可以得到迭代 k 次后权值向量长度平方的下界为：

\[||X^*||^2 \geq \frac{(X^{*T} X(k))^2 }{||X^*||^2} > \frac{(k\delta)^2}{||X^*||^2}\]

下面求权值向量长度的上界：

\[||X^*||^2 = X^T(k)X(k) \\ = [X(k-1) + Z'(k - 1)]^T [X(k-1) + Z'(k - 1)] \\ = X^T(k - 1) X(k - 1) + 2 X^T(k-1) Z'(k - 1) + Z'^T(k - 1) Z'(k - 1) （式：7）\]

注意：

\[X^T(k-1) Z'(k - 1) \leq 0\]

因为权值向量只有在前一输入错误分类时才会进行更新，（式：7）可化简为：

\[||X(k)||^2 \leq ||X(k - 1)||^2 + ||Z'(k - 1)||^2\]

对$

X(k - 1)

^2 $ $

Z’(k - 2)

^2 $ … 重复上述过程，可得：

\[||X(k)||^2 \leq ||Z'(0)||^2 + \dots + ||Z'(k - 1)||^2\]

令 $ \Pi = max{

Z’(i)

^2 } $，该上界可简化为：

\[||X^*||^2 \leq k\Pi\]

至此，已求出了 k 次迭代后权值向量长度平方的上界和下届，将其合并：

\[k\Pi \geq ||X^*||^2 > \frac{(k\delta)^2}{||X^*||^2} 或 k \leq \frac{\Pi||X^*||^2}{\delta^2}\]

由于 k 有上界，意味着权值的改变次数是有限的，所以感知机在有限次迭代后收敛。

迭代的最大次数与$ \delta^2 $成反比。该参数是输入模式与决策边界的解靠近程度的一种测度。这意味着，如果输入向量越靠近决策边界，就越难将他们分开，就要迭代越多次才能使算法收敛。

请注意该证明是建立在下面三条假设的基础上：

1. 问题解存在

2. 仅在输入向量被错误分类时才改变权值

3. 输入向量长度的上界存在

由于证明的一般性，所以感知机的学习规则的许多变形同样也可证明是收敛的，

局限性

基本的感知机学习规则不能解决异或问题。

线性可分性

假设有一个线性边界（超平面），则感知机可以对那些能够被先行边界分开的输入向量进行分类。这样的向量成为线性可分的。

事实上很多问题并非线性可分的。最典型的就是XOR（异或）门。我们可以使用能够求解任意分类问题的多层感知机，以及反传算法。