主要内容有：
- 单层感知器的迭代学习算法(包含代码)
- 两层感知器解决异或问题
- 解释两层感知器分类能力有限的问题
- 解释为什么三层感知器能够解决任意区域组合的分类问题
最近在准备模式识别考试,关于三层感知器能够解决任意区域组合的分类问题解释甚是有趣,这两天考完试了在此对这些内容做个总结。
单层感知器的迭代算法
感知器算法属于线性分类器,单层感知器在给定数据线性可分的情况下,可以经过有限次迭代使得算法收敛
我曾经写过关于感知器迭代计算学习的代码,是找到一个平面,将三维空间的两类线性可分的点分隔开来。
感知器算法的更新过程(2类问题)如下:
N个属于$w_1 ,\ w_2$类的模式样本构成训练样本集$\{X_{1},X_{2},….X_{N}\}$
- 将原始数据写成增广向量形式,并规范化
构成增广向量形式是指添加一个维度为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.$
下面是老师上课布置的编程练习:
编写感知器算法程序，求下列模式分类的解向量：
$ω_1: \{(0,0,0)^T ,(1,0,0)^T,(1,0,1)^T,(1,1,0)^T\}$
$ω2: \{(0,0,1)^T,(0,1,1)^T,(0,1,0)^T,(1,1,1)^T\}$
$w(1)=(-1,-2,-2,0)^T$
使用上面的流程并用$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),我们将四个点输入,可以得到下面的数据:
| x | g1 | g2 | y |
|---|---|---|---|
| 0 0 | 0 | 0 | 0 |
| 0 1 | 1 | 0 | 1 |
| 1 0 | 1 | 0 | 1 |
| 1 1 | 1 | 1 | 0 |
当我们得到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即可
| x | y1 | y2 | y3 | z |
|---|---|---|---|---|
| x1,x2 | 0 | 0 | 0 | 0 |
| x1,x2 | 0 | 0 | 1 | 0 |
| x1,x2 | 0 | 1 | 0 | 1 |
| x1,x2 | 0 | 1 | 1 | 0 |
| x1,x2 | 1 | 0 | 0 | 1 |
| x1,x2 | 1 | 1 | 0 | 1 |
| x1,x2 | 1 | 1 | 1 | 1 |
网络结构如下图所示:
如果我们想将(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
| x | y1 | y2 | y3 | z1 | z2 | z3 | z |
|---|---|---|---|---|---|---|---|
| x1,x2 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| x1,x2 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| x1,x2 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| x1,x2 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| x1,x2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| x1,x2 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| x1,x2 | 1 | 1 | 1 | 0 | 0 | 1 | 1 |
实际上,中间的z1,z2,z3的寻找,如果要某个为1,其他都为0,只需要用t1 + t2 + t3 - bias = 0来求得,具体得,如果要010输出为1,我们只需要让t2为1,t1和t3为-1,再调整bias即可
那么我们就会得到这样的网络结构:
这样,就可以将(000,111,110)中区域的点与其他区域分开
这可能就是下面这张图的直观理解了:
感知器迭代计算代码
具体执行迭代计算的代码量很小,大部分的代码都是在画出三维的平面图1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72import 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()