3.5 感知器算法

3.5.1 概述

• 一旦判别函数的形式确定下来，不管它是线性的还是非线性的，剩下的问题就是如何确定它的系数

• 在模式识别中，系数确定的一个主要方法就是通过对已知样本的训练和学习来得到

• 感知器算法就是通过训练样本模式的迭代和学习，产生线性（或广义线性）可分的模式判别函数

采用感知器算法（Perception Approach）能通过对训练模式样本集的“学习”得到判别函数的系数。

这里采用的算法不需要对各类别中模式的统计性质做任何假设，因此称为确定性的方法

3.5.2 感知器的训练算法

已知两个训练模式集分别属于$\omega_1$类和$\omega_2$类，权向量的初始值为$\boldsymbol{w}(1)$，可任意取值。则在用全部训练模式集进行迭代训练时，第k次的训练步骤为：

• 若$x_k\in\omega_1$且$\boldsymbol{w}^T(k)x_k\leq0$或$x_k\in\omega_2$且$\boldsymbol{w}^T(k)x_k>0$，则说明分类器对第k个模式做出了错误分类，此时应该校正权向量，使得

$$w(k+1)=w(k)-Cx_k$$

​ 其中C为校正增量

• 否则，则说明分类正确，因此权向量不变：

$$w(k+1)=w(k)$$

若对$x\in\omega_2$的模式样本乘以-1，则有：

$$\text{若}\boldsymbol{w}^T(k)x_k\leq0,\text{则}w(k+1)=w(k)+Cx_k$$

因此，感知器算法可以统一写成：

$$w(k+1) = \begin{cases} w(k) & \boldsymbol{w}^T(k)x_k > 0 \\ w(k) + Cx_k & \boldsymbol{w}^T(k)x_k\leq0 \end{cases}$$

感知器算法本质上是一种赏罚过程

• 对正确分类的“赏”本质是“不罚”

• 对错误分类的“罚”，本质是给权向量加上一个正比于$x_k$的分量

将属于$\omega_2$的训练样本乘以-1，并写作增广向量的形式，则有：

$$\begin{align} x_1&=(0,0,1)^T \nonumber \\ x_2&=(0,1,1)^T\nonumber \\ x_3&=(-1,0,-1)^T\nonumber \\ x_4&=(-1,-1,-1)^T\nonumber \end{align}$$

接下来开始迭代

第一轮，取$C=1,w(1)=(0,0,0)^T$

$\boldsymbol{w}^T(1)x_1=(0,0,0)(0,0,1)^T=0\not\gt 0$，因此$\boldsymbol{w}(2)=\boldsymbol{w}(1) + x_1 = (0,0,1)^T$

$\boldsymbol{w}^T(2)x_2=(0,0,1)(0,1,1)^T=1\gt 0$，因此$\boldsymbol{w}(3)=\boldsymbol{w}(2)= (0,0,1)^T$

$\boldsymbol{w}^T(3)x_3=(0,0,1)(-1,0,-1)^T=-1\not\gt 0$，因此$\boldsymbol{w}(4)=\boldsymbol{w}(3) + x_3 = (-1,0,0)^T$

$\boldsymbol{w}^T(4)x_4=(-1,0,0)(-1,-1,-1)^T=1\gt 0$，因此$\boldsymbol{w}(5)=\boldsymbol{w}(4) = (-1,0,0)^T$

由于上一轮迭代中还存在不大于0的情况，因此继续第二轮迭代：

$\boldsymbol{w}^T(5)x_1=(-1,0,0)(0,0,1)^T=0\not\gt 0$，因此$\boldsymbol{w}(6)=\boldsymbol{w}(5) + x_1 = (-1,0,1)^T$

$\boldsymbol{w}^T(6)x_2=(-1,0,1)(0,1,1)^T=1\gt 0$，因此$\boldsymbol{w}(7)=\boldsymbol{w}(6) = (-1,0,1)^T$

$\boldsymbol{w}^T(7)x_3=(-1,0,1)(-1,0,-1)^T=0\not\gt 0$，因此$\boldsymbol{w}(8)=\boldsymbol{w}(7) + x_3 = (-2,0,0)^T$

$\boldsymbol{w}^T(8)x_4=(-2,0,0)(-1,-1,-1)^T=2\gt 0$，因此$\boldsymbol{w}(9)=\boldsymbol{w}(8) = (-2,0,0)^T$

仍然不是全满足，继续第四轮迭代：

$\boldsymbol{w}^T(9)x_1=(-2,0,0)(0,0,1)^T=0\not\gt 0$，因此$\boldsymbol{w}(10)=\boldsymbol{w}(9) + x_1 = (-2,0,1)^T$

$\boldsymbol{w}^T(10)x_2=(-2,0,1)(0,1,1)^T=1\gt 0$，因此$\boldsymbol{w}(11)=\boldsymbol{w}(10) = (-2,0,1)^T$

$\boldsymbol{w}^T(11)x_3=(-2,0,1)(-1,0,-1)^T=1\gt 0$，因此$\boldsymbol{w}(12)=\boldsymbol{w}(11) = (-2,0,1)^T$

$\boldsymbol{w}^T(12)x_4=(-2,0,1)(-1,-1,-1)^T=1\gt 0$，因此$\boldsymbol{w}(13)=\boldsymbol{w}(12) = (-2,0,1)^T$

仍然有一个不满足，继续第四轮迭代：

$\boldsymbol{w}^T(13)x_1=(-2,0,1)(0,0,1)^T=1\gt 0$，因此$\boldsymbol{w}(14)=\boldsymbol{w}(13) = (-2,0,1)^T$

$\boldsymbol{w}^T(14)x_2=1\gt 0$，因此$\boldsymbol{w}(15)=\boldsymbol{w}(14) = (-2,0,1)^T$

$\boldsymbol{w}^T(15)x_3=1\gt 0$，因此$\boldsymbol{w}(16)=\boldsymbol{w}(15) = (-2,0,1)^T$

$\boldsymbol{w}^T(16)x_2=1\gt 0$，因此解向量为$(-2,0,1)^T$，对应的判别函数即为：

$$d(x) = -2x_1+1$$

感知器算法的收敛性

只要模式类别是线性可分的，就可以在有限的迭代步数里求出权向量

3.5.3 使用感知器算法的多模式分类

采用3.2.2章节中第三种情况，对M类模式存在M个判别函数$\{d_i, i = 1,2,\dots,M\}$，若$x\in\omega_1$，则$d_i\gt d_j,\forall j\neq i$。由此将感知器算法推广到多类模式：

设M种模式类别$\omega_1,\omega_2,\dots,\omega_M$，若在训练过程的第k次迭代时，一个属于$\omega_i$类的模式样本x送入分类器，则应先算出M个判别函数：

$$d_j(k)=\omega_j(k)x,\ \ j=1,2,\dots,M$$

若$d_i(k)\gt d_j(k),\ j=1,2,\dots,M,\ \forall j\neq i$的条件成立，则权向量不变，即：

$$w_j(k+1) = w_j(k)$$

若其中第一个权向量使得$d_j(k)\leq d_1(k)$，则相应的权向量应作调整，即：

$$\begin{cases} w_i(k+1) = w_i(k)+C_x \\ w_l(k+1) = w_l(k)-C_x \\ w_j(k+1) = w_j(k) & j=1,2,\dots,M,j\neq i,j\neq l \end{cases}$$

其中C是一个正常数，权向量的初值可视情况任意选择。

例：给出三类模式的训练样本

$$\omega_1:\{(0,0)^T\},\\ \omega_1:\{(1,1)^T\},\\ \omega_1:\{(-1,1)^T\}$$

将模式样本写成增广形式：

$$x_1 = (0,0,1)^T \\ x_2 = (1,1,1)^T \\ x_3 = (-1,1,1)^T$$

取初始值$w_1(1)=w_2(1)=w_3(1)=(0,0,0)^T$，C=1

第一轮迭代，以$x_1$为训练样本

$$d_1(1)=w_1^T(1)x_1=(0,0,0)(0,0,1)^T=0 \\ d_2(1)=w_2^T(1)x_1=(0,0,0)(0,0,1)^T=0 \\ d_3(1)=w_3^T(1)x_1=(0,0,0)(0,0,1)^T=0$$

由于$d_1(1)\not\gt d_2(1),d_1(1)\not\gt d_3(1)$，因此：

$$w_1(2) = w_1(1) + x_1=(0,0,1)^T \\ w_2(2) = w_2(1) - x_1=(0,0,-1)^T \\ w_3(2) = w_3(1) - x_1=(0,0,-1)^T$$

第二轮迭代，以$x_2$为训练样本

$$d_1(2)=w_1^T(2)x_2=(0,0,1)(1,1,1)^T=1 \\ d_2(2)=w_2^T(2)x_2=(0,0,-1)(1,1,1)^T=-1 \\ d_3(2)=w_3^T(2)x_2=(0,0,-1)(1,1,1)^T=-1$$

由于$d_2(2)\not\gt d_1(2),d_2(2)\not\gt d_3(2)$，因此：

$$w_1(3) = w_1(2) - x_2=(-1,-1,0)^T \\ w_2(3) = w_2(2) + x_2=(1,1,0)^T \\ w_3(3) = w_3(2) - x_2=(-1,-1,-2)^T$$

第三轮迭代，以$x_3$为训练样本

$$d_1(3)=w_1^T(3)x_3=(-1,-1,0)(-1,1,1)^T=0 \\ d_2(3)=w_2^T(3)x_3=(1,1,0)(-1,1,1)^T=0 \\ d_3(3)=w_3^T(3)x_3=(-1,-1,-2)(-1,1,1)^T=-2$$

由于$d_3(3)\not\gt d_1(3),d_3(3)\not\gt d_2(3)$，因此：

$$w_1(4) = w_1(3) - x_3=(0,-2,-1)^T \\ w_2(4) = w_2(3) - x_3=(2,0,-1)^T \\ w_3(4) = w_3(3) + x_3=(-2,0,-1)^T$$

第四轮迭代，以$x_1$为训练样本

$$d_1(4)=w_1^T(4)x_1=-1 \\ d_2(4)=w_2^T(4)x_1=-1 \\ d_3(4)=w_3^T(4)x_1=-1$$

由于$d_1(4)\not\gt d_2(4),d_1(4)\not\gt d_3(4)$，因此：

$$w_1(5) = w_1(4) + x_1=(0,-2,0)^T \\ w_2(5) = w_2(4) - x_1=(2,0,-2)^T \\ w_3(5) = w_3(4) - x_1=(-2,0,-2)^T$$

第五轮迭代，以$x_2$为训练样本

$$d_1(5)=w_1^T(5)x_2=-2 \\ d_2(5)=w_2^T(5)x_2=0 \\ d_3(5)=w_3^T(5)x_2=-4$$

由于$d_2(5)\gt d_1(5),d_2(5)\gt d_3(5)$，因此：

$$w_1(6) = w_1(5) \\ w_2(6) = w_2(5) \\ w_3(6) = w_3(5)$$

第六轮迭代，以$x_3$为训练样本

$$d_1(6)=w_1^T(6)x_3=-2 \\ d_2(6)=w_2^T(6)x_3=-4 \\ d_3(6)=w_3^T(6)x_3=0$$

由于$d_3(6)\gt d_1(6),d_3(6)\gt d_2(6)$，因此：

$$w_1(7) = w_1(6) \\ w_2(7) = w_2(6) \\ w_3(7) = w_3(6)$$

第七轮迭代，以$x_1$为训练样本

$$d_1(7)=w_1^T(7)x_1=0 \\ d_2(7)=w_2^T(7)x_1=-2 \\ d_3(7)=w_3^T(7)x_1=-2$$

由于$d_1(7)\gt d_2(7),d_1(7)\gt d_3(7)$，因此权向量不变

综上，可得最后的权向量：

$$w_1=(0,-2,0)^T \\ w_2=(2,0,-2)^T \\ w_3=(-2,0,-2)^T$$

因此判别函数为：

$$d_1(x) = -2x_2 \\ d_2(x) = 2x_1-2 \\ d_3(x) = -2x_1-2$$

这里的分类算法都是通过模式样本来确定判别函数的系数，但一个分类器的判断性能最终要受并未用于训练的那些未知样本来检验。

要使一个分类器设计完善，必须采用有代表性的训练数据，它能够合理反映模式数据的整体。

一般来说，合适的样本数目可如下估计：

若k是模式的维数，令C=2(k+1)，则通常选用的训练样本数目约为C的10~20倍。