为什么三层感知器能够解决任意区域组合的分类问题(不同隐层数的感知器的分类能力)

主要内容有：

1. 单层感知器的迭代学习算法(包含代码)
2. 两层感知器解决异或问题
3. 解释两层感知器分类能力有限的问题
4. 解释为什么三层感知器能够解决任意区域组合的分类问题

访问我的博客符说八道(三层感知器能够解决任意区域组合的分类问题) 有更好的展示效果。
最近在准备模式识别考试,关于三层感知器能够解决任意区域组合的分类问题解释甚是有趣,这两天考完试了在此对这些内容做个总结。

单层感知器的迭代算法

感知器算法属于线性分类器,单层感知器在给定数据线性可分的情况下,可以经过有限次迭代使得算法收敛
我曾经写过关于感知器迭代计算学习的代码,是找到一个平面,将三维空间的两类线性可分的点分隔开来。

感知器算法的更新过程(2类问题)如下:
N个属于\(w_1 ,\ w_2\)类的模式样本构成训练样本集\(\{X_{1},X_{2},....X_{N}\}\)

1. 将原始数据写成增广向量形式,并规范化
   构成增广向量形式是指添加一个维度为1的向量,如三维的样本的话，我们将会这样设置:
   \(X = [x_{1},x_{2},x_{3},1]^{T}\)
   写成增广向量形式是为了让我们的运算能够执行矩阵乘法,便于编程实现。
   规范化是指将\(w_2\)类样本\(\times \ -1\)
   接下来任取权向量初始值\(W(1)\),开始迭代

2.用全部训练样本进行一轮迭代，计算\(W^T (k)X_i\)的值，并修正权向量。
分两种情况，更新权向量的值：

• 若 \(W^T (k) X_i \leq 0\)
  表明分类器对第i个模式做了错误分类，我们将进行校正，权向量校正为：
  \(W(k+1)=W(k)+cX_i \ , \quad c>0\)

• 若 \(W^T (k) X_i > 0\)
  表明分类正确，权向量不变。
  \(W(k+1)=W(k)\)

因此我们可以将权向量的更新规则统一写为:

\(W(k+1) = \left\{\begin{matrix}W(k) \quad if \ W^{T}(k)X_i > 0\\W(k) + cX_i \quad if \ W^{T}(k)X_i \leq 0\end{matrix}\right.\)

3.分析分类结果：只要有一个错误分类,回到2,直至对所有样本正确分类。
感知器算法可以证明是收敛的(在线性可分的前提下)，经过算法的有限次迭代运算后，求出了一个使所有样本都能正确分类的\(W\) 。

关于为什么是用\(W(k+1)=W(k)+cX_i \ , \quad c>0\)这个公式更新,实际上这可以从梯度下降法推导出来:
当我们的准则函数为:
\(J(W，X)=1/2 (|W^T X|-W^T X)\)
使用梯度下降更新权值:
\(W(k+1)=W(k)-c∇J=W(k)-c[\frac{∂J(W，X)}{∂W}]_{(W=W(k))}\)
就可以解得
\(W(k+1) = \left\{\begin{matrix}W(k) \quad if \ W^{T}(k)X_i > 0\\W(k) + cX_i \quad if \ W^{T}(k)X_i \leq 0\end{matrix}\right.\)

---

下面是老师上课布置的编程练习:

使用上面的流程并用\(c=1\)求得的解向量:
\(W=(3,-2,-3,1)\)
下面是我画出的决策平面(具体代码在本文最后)

实际上,感知器就是这样的单元:

典型的f为硬限幅函数(hard limiter)
下面讨论的f都为阶跃函数
也就是 输入大于0时f为1,输入小于0时f为0

两层感知器解决异或问题

感知器算法可以解决and or这种线性可分的问题,但是对于异或问题,就无力了,而两层感知器就可以做到:
如下图所示,xor线性不可分

那么两层感知器是如何解决异或线性不可分的问题呢?
它首先通过两条直线,先用g1直线将(0,0)点与其他三个点(0,1),(1,0),(1,1)分开,再用g2直线将(1,1)与(0,0),(0,1),(1,0)分开
就像下图所示:

通过两条直线的划分(在直线下方为0,在直线上方为1),我们将四个点输入,可以得到下面的数据:

当我们得到g1,g2时,我们就将(0,0)映射到了(0,0),将(0,1)和(1,0)映射到了(1,0),(1,1)映射到了(1,1)
如下图所示,我们再用图里的直线即可分开:

所以,两层感知器的结构为:

隐层的结点第一个结果为通过g1映射得到,第二个为通过g2得到

为什么两层感知器的分类能力有限?

由上图,我们假设区域中的点,如
(000,001,011)这三个区域

我们可以先将区域中的点,通过y1,y2,y3三条直线映射到
000,001,....111(没有101),总共7个区域,前面我们是通过g1,g2映射到了平面上面的点,现在我们变成了三维,因此映射到了正方体的顶点,如果我们想将(000,001,011)这三个点与其余四个点分开的话,我们可以画出正方体,并且标出点,如下图所示:

我们很容易找到一个平面将他分开,因此只需要两层感知器就可以实现分类

从y1 y2 y3到z需要让决策面为 z: y1 + y2 - y3 -1/2即可

网络结构如下图所示:

如果我们想将(000,111,110)中区域的点与其他区域分开,我们会怎么办呢?
区域图如下:

我们也会先将点映射到正方体的三个顶点,然后我们画出000,111,110三个点,我们会发现,我们没有办法用一个平面将000,111,110三个点与其他区域分开,我们需要两个平面才能解决这个问题,解决这个问题我们只需要添加一层隐藏层,就可以实现分类了,也就是说:因为2层感知器中隐藏层我们遇到了线性不可分问题,所以我们需要再加一层

所以,两层感知器的分类能力是有限的
下面我将讨论如何使用三层感知器来实现(000,111,110)中区域的点与其他区域分开

为什么三层感知器能够解决任意区域组合的分类问题?

与xor问题一样,我们会将

• 000 与其余6个区域分开
• 111 与其余6个区域分开
• 110 与其余6个区域分开
  这样我们就会得到z1,z2,z3,再将z1,z2,z3输入感知器,我们只要将000与其他(100,010,001)分开即可 z: z1 + z2 + z3 -1/2

实际上,中间的z1,z2,z3的寻找,如果要某个为1,其他都为0,只需要用t1 + t2 + t3 - bias = 0来求得,具体得,如果要010输出为1,我们只需要让t2为1,t1和t3为-1,再调整bias即可

那么我们就会得到这样的网络结构:

这样,就可以将(000,111,110)中区域的点与其他区域分开
这可能就是下面这张图的直观理解了:

感知器迭代计算代码

具体执行迭代计算的代码量很小,大部分的代码都是在画出三维的平面图

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

def main():
    path =  'data.txt'
    data = pd.read_csv(path, header=None, names=['x', 'y','z']) #读入数据
    X = np.array(data.iloc[:,:])
    X = np.column_stack((X, np.ones((len(X),1)))) # 构成增广向量
    X[4:,:] = - X[4:,:] # 规范化
    #初始化参数
    c = 1
    w = np.array([-1,-2,-2,0])
    flag = True
    cnt = 0
    while flag:
        cnt += 1
        flag = False
        for x in X:
            if w @ x <= 0:
                w = w + c*x # 更新权向量
                flag = True
    print("after {} iterations:c = {}, w={}".format(cnt,c,w))


    fig = plt.figure(figsize=(12, 8))
    ax = fig.gca(fc='whitesmoke',
                projection='3d'
                )

    x1 = np.linspace(0, 2, 9)
    x2 = np.linspace(0, 2, 9)

    x1,x2 = np.meshgrid(x1, x2)
    x3 = (-w[3] - w[0]*x1 -w[1]*x2)/w[2]
    ax.plot_surface(X=x1,
                Y=x2,
                Z=x3,
                color='b',
                alpha=0.2
               )

    half = int(len(X)/2)
    X[4:,:] = - X[4:,:]
    x = X[:half, 0]
    y = X[:half, 1]
    z = X[:half, 2]
    ax.scatter(x, y, z,c='y',marker='o',label='class 1')

    x2 = X[half:, 0]
    y2 = X[half:, 1]
    z2 = X[half:, 2]
    ax.scatter(x2, y2, z2,c='r',marker='x',label = 'class 2')
    ax.legend()
    for i_x, i_y,i_z in zip(X[:,0],X[:,1],X[:,2]):
        ax.text(i_x, i_y,i_z, '({}, {},{})'.format(int(i_x), int(i_y),int(i_z)))
    ax.set(xlabel='X',
       ylabel='Y',
       zlabel='Z',
       xlim=(0, 2),
       ylim=(0, 2),
       zlim=(0, 2),
       xticks=np.arange(0, 2, 1),
       yticks=np.arange(0, 2, 1),
       zticks=np.arange(0, 2, 1)
      )

    plt.show()


main()