為什麼三層感知器能夠解決任意區域組合的分類問題(不同隱層數的感知器的分類能力) categories: – ML

• 2020 年 12 月 20 日
• 筆記
• ML

主要內容有：

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.\)

下面是老師上課布置的編程練習:

編寫感知器演算法程式，求下列模式分類的解向量：
\(ω_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),我們將四個點輸入,可以得到下面的數據:

當我們得到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三個點與其他區域分開,我們需要兩個平面才能解決這個問題,因為我們需要添加一層隱藏層,因為我們遇到了線性不可分問題
所以,兩層感知器的分類能力是有限的
下面我將討論如何使用三層感知器來實現(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()