機器學習筆記（一）感知機算法之原理篇

2019 年 11 月 7 日
筆記

這篇學習筆記強調幾何直覺，同時也注重感知機算法內部的動機。限於篇幅，這裡僅僅討論了感知機的一般情形、損失函數的引入、工作原理。關於感知機的對偶形式和核感知機，會專門寫另外一篇文章。關於感知機的實現代碼，亦不會在這裡出現，會有一篇專門的文章介紹如何編寫代碼實現感知機，那裡會有幾個使用感知機做分類的小案例。

感知機算法是經典的神經網絡模型，雖然只有一層神經網絡，但前向傳播的思想已經具備。究其本質，感知機指這樣一個映射函數：(sign(w_ix_i + b))，將數據帶進去計算可以得到輸出值，通過比較輸出值和數據原本對應的標籤值是否正負號相同從而推斷出模型訓練的結果。

1. 何為感知機?

接上面的敘述，感知機的數學模型為(sign(w_ix_i + b))，其中(w = (w_1,w_2,…,w_n))是權重向量，(x_i = （x_i^{1},x_i^{2},…,x_i^{n}))是一個樣本點，從符號很容易理解，它們都是定義在(R^n)空間的(如果難以理解，可以簡單的理解為樣本點有(n)個維度，相應的權重向量也須有(n)個維度和它相匹配).

下面是一副經典的感知機模型圖：

最左邊的表示輸入一個樣本點的特徵向量，通過各自的權重前向傳播到神經元，在神經元有一個加法器，最後通過一個激活函數來決定是否激活。最下面的(x_0)是bias項，一般文獻中記為(b)。

2. 感知機可以解決什麼問題？

這裡我們可以看一個經典的例子，利用感知機模型來解決經典的(OR問題)。

【例1】設有4個樣本點，((0,0),(0,1),(1,0),(1,1))，根據(OR)的邏輯，必須至少有一個不為(0)才能判定為真，翻譯成機器學習的表達即標籤為((-1,1,1,1))，這裡負數表示負樣本，正數表示正樣本。

我們希望的是能找到一條直線（分類器），將正負樣本點準確分開。根據(S1)中的敘述，樣本點是定義在(R^2)空間的，顯然權重向量為(w = (w_1,w_2))，考慮偏置項(b)，一般添補一個(x_i^{0})為(-1)以便把式子(sumlimits_{1}^{n} w_ix_i + b)直接寫成(sumlimits_{0}^{n}w_ix_i)。先給出權重更新公式$ w_{ij} ← w_{ij} − η(y_{j} − t_{j} ) · x_i $, 稍後會給出解釋。

設置權重初值為(w = (0,0))。並且約定當且僅當(sign(x=0)=0)，算作誤分類。依次代入樣本點：

代入((0,0))點，(sign(wx + b) = sign(0 * 0 + 0 * 0 + 0*(-1)) = 0)，無法判定是否為負類，錯誤。
- 更新權重
  
  (b = 0 – 1 * (1-0) * (-1)=1)
  
  (w_1 = 0 – 1 * (1-0) * 0=0)
  
  (w_2 = 0 – 1 * (1-0) * 0=0)
代入((0,1))點，(sign(wx + b) = sign(0 * 0 + 0 * 1 +1 *(-1)) = -1)，判定為負類，錯誤。
- 更新權重
  
  (b = 1 – 1 * (1 – (-1)) * (-1) = -1)
  
  (w_1 = 0 – 1 * (1 – (-1))*0 = 0)
  
  (w_2 = 0 – 1*(1-(-1))*1 = 2)
代入((1,0))點，(sign(wx+b)=sign(0 * 1 + 2 * 0 + (-1) * (-1))= 1)，判定為正類，正確。
代入((1,1))點，(sign(wx + b)=sign(0 * 1 + 2 * 1 + （-1）* -1)=3)，判定為正類，正確。
第二輪遍歷，代入((0,0))，(sign(0*0 + 2*0 + （-1）*-1)=1)，無法判定是否為負類，錯誤。
- 更新權重
  
  (b = -1 – 1*(1-(-1))*(-1)=1)
  
  (w_1 = 0 – 1*(1-(-1))*0=0)
  
  (w_2 = 2 – 1*(1-(-1))*0 = 2)
代入((0,1))，(sign(0 * 0 + 2 * 1 + 1 * (-1))=1)，判定為正類，正確。

後面的步驟就省略不寫了，讀者可以自行驗算。根據代碼計算的結果，如果初始權重設為[0,0,0]這樣比較極端的值，學習速率為1時，且按照順序選擇樣本點時，需要完整的走完兩輪迭代才能得到穩定的權重。最後解得分類函數為: (sign(2x^{(1)} + 2x^{(2)} – 1))，讀者可以帶數據進去驗算。

3. 感知機不能解決什麼問題？

這裡有一段經典的公案，《感知機》是這本書的出現，直接讓神經網絡這一流派的研究停止了二十年。因為書中在詳盡介紹感知機原理的同時，還指出了感知機的致命缺陷：無法解決(XOR)問題。

(XOR)又稱為異或，它的邏輯如下：

變量1	變量2	邏輯運算結果
0	0	0
0	1	1
1	0	1
1	1	0

這是個比較奇怪的邏輯，變量之間當且僅當不相等時為真。

憑着幾何直覺，我們很快就能發現，不可能有這樣的超平面，能準確的分開紅色和藍色兩類樣本。

這裡小結一下：

感知機可以解決完全線性可分的問題。

這似乎是一句廢話，但是感知機背後強大的思想確衍生出了支持向量機這個傳統機器學習的巔峰。而對於線性不可分的樣本，可以使用多層神經網絡（(Multi space Layer space Network))或者使用核感知機，事實上兩層的感知機就可以解決(XOR)問題

4. 感知機是如何工作的？

在上面這個略顯啰嗦的例子，我們看到了感知機的工作方法。它的算法流程可以概括如下：

選取初始值(w_0, b_0)

在訓練集中選取一個數據點((x_i,y_i))

檢查在這個樣本點上，模型是否會錯誤分類，如果錯誤分類，則更新(w_i,b_i)

回到第2步，直到整個訓練集中沒有誤分類點

從上面的算法，我們至少能讀出這麼幾層意思：

初始值是隨機給的，賦值為0是一個簡便的做法，但通常設置為一個很小的隨機值，後面會詳細討論
每次訓練其實只用到一個樣本點，即使訓練集中有很多數據點亦是如此。這和 (w_ix_i)這個表達式的計算方式有關，詳見上面的數值例子。
算法的重點在誤分類這裡，那麼如何定義誤分類就非常要緊了。
算法是一個迭代的過程，且要滿足所有樣本點都分類正確才停機。反過來理解，就是感知機算法只能運用於完全線性可分的數據集。如果數據集是不能完全線性可分的，感知機永遠不會停機，除非訓練之前先設置好停機條件，常見的比如設置訓練次數或者誤差上界（一旦誤差小於$ varepsilon $ 即可停機)。

顯然，如何定義錯誤是感知機算法里的頭等大事。

5. 該如何定義錯誤？

通俗定義：映射函數(sign(wx + b))求解得到的值和原始標籤值異號，即表示分類錯誤。

根據這個表述，我們可以很容易地將數據集分類：正確分類和錯誤分類。顯然我們要做的事就是想辦法讓模型把分錯的樣本點分對，同時對於原本已經分對的點不能又分錯了。

如果採用幾何作圖的方法，可以不斷調整超平面（即上面提到的直線，術語上通稱為超平面）來達到目標，只要給定的數據集是完全線性可分的。但是，如果是高維空間的數據集，幾何直覺就不靈了，這時需要引入代數工具。而引入損失函數就是這樣的工具，它和我們依靠幾何直覺做的事情是相同的：把所有點分對 (iff) 將損失函數降到最小。

損失函數的定義可以憑直覺而為：計算誤分類樣本的個數。例如樣本空間共有(M)個樣本，其中錯誤分類的樣本屬於區域(E)，顯然損失函數就是 (sumlimits_{iin E}x_i) 。但問題隨之而來，我們沒有工具來優化這個函數，使之向最小值運動。於是自然地想到，計算所有誤分類點到超平面的距離，對距離之和做優化。具體的思路是這樣的：

找到描述樣本點到超平面距離的計算式
正確分類的樣本點的距離和丟棄不看
定義誤分類的距離和，對它求最小值

在(R^n)空間中，任何一個樣本點(x_0)到超平面的距離公式 (frac{1}{||w||}|wcdot x + b|)。對於誤分類來說，(y_i(w cdot x + b) < 0)，於是如果有一個誤分類點(x_0)，那麼它到超平面的距離可以寫作 (-y_ifrac{1}{||w||}|wcdot x + b|)。對於所有的誤分類來說，自然可以寫出下面的損失函數：[L(w,b) = -sumlimits_{iin E} y_i frac{1}{||w||}|wcdot x + b|]。這裡添加負號的目的是使得損失函數的值恆為正數，這樣對它求最小值可以使用凸優化工具。顯然地，誤分類樣本點越少，(L(w,b))越小；誤分類點離超平面的距離越小，(L(w,b))越小。

這裡捨棄掉(frac{1}{||W||})是因為它是一個正的係數，並且對於(L(w,b))具有伸縮性，因此不影響最小化(L(w,b))。

6. 知錯後如何改錯？

回顧微分學知識，我們知道一個全局的凸函數取得最小值是在導數為0處。但是，放在多元函數的觀點來看，一元函數的導數本質上也是梯度。當一個函數沿着負梯度的方向運動是，函數值的減少是最快的；沿着正梯度方向運動時，函數值增加啊是最快的。下面我們就來求其梯度。

[frac{partial L}{partial w} = – sumlimits_{x_i in E} y_i x_i]

[frac{partial L}{partial b} = – sumlimits_{x_i in E} y_i]

我們來看關於(w)的梯度表達式，本質上就是找到所有的誤分類點，然後把標籤值(y_i)作為一個權重((+1/-1))。如果(x_1)是一個被錯誤分類的點，假設這個點對應的原始標籤是正類，現在被分成負類，所以在前面加一個符號，表示往反方向彌補。所以(sumlimits_{x_i in E}y_ix_i)

可以理解為通過所有錯誤分類的樣本點擬合出一個運動方向，往那個方向運動可以彌補模型中(w)參數的錯誤。

而例1中，我們每次只選取一個樣本點，假設這個樣本點是((x_i,y_i))，那麼更新公式就是 (w = w + eta y_i x_i)，其中的(eta)是每次更新的步長，術語為學習率。同理，偏置項的更新公式為 (b = b + eta y_i)。

7. (Novikoff) 定理

先敘述一下這個定理。定理來自李航老師的《統計學習方法》第二版Page42。

設訓練數據集(T = {(x_1,y_1),(X_2,y_2),…,(x_N,y_N)})是線性可分的，其中(x_i in X = R^n, y_i in Y = {-1,+1}, i = 1,2,…,N)，則

(1) 存在滿足條件(||hat{w}_{opt}|| = 1)的超平面(hat{w}_{opt} cdot hat{x} = w_{opt} cdot x + b_{opt})將訓練數據集完全正確分開；且存在(gamma > 0)，對所有的(i = 1,2,…,N)有[y_i (hat{w}_{opt} cdot hat{x}_i) = y_i (w_{opt} cdot x_i + b_{opt}) ge gamma]

(2)令(R = maxlimits_{1 le i le N} ||hat{x}_i||)，則感知機算法在訓練數據集上的誤分類次數(k)滿足不等式 [k le (frac{R}{gamma})^2]

先從直覺上理解下這個定理表述的意思。大意是對於可以找出線性超平面做分類的數據集，存在一個下界$ gamma $，所有樣本點到超平面的距離都至少大於這個 $ gamma $，同時錯誤分類的次數有一個上界，第 (k+1) 次之後，分類都是正確的，算法最終是收斂的。

證明

(1) 由於數據是線性可分的，因此一定存在一個分割超平面(S)，不妨就取(S)的參數為(hat{w}_{opt})，顯然對於超平面上的所有點(x)，都有(hat{w}_{opt} cdot x = w_{opt} cdot x + b_{opt} = 0)，並滿足(||hat{w}_{opt}||=1)。而對於訓練數據集中的樣本點，由於現在都被正確分類了，所以有(hat{w}_{opt} cdot x_i > 0)，於是取 (gamma = minlimits_{i} {y_i(w_{opt} cdot x_i + b_{opt} })，這就得到了下界。

(2) 由 (k le (frac{R}{gamma})^2)推出(k gamma le sqrt{k} R) 。

假設((x_i,y_i))是一個在第(k)次被誤分類的點，那麼這件事的觸發條件是 (y_i (hat{w}_{k-1} cdot x_i) le 0).

由更新公式，(hat{w}_k = hat{w}_{k-1} + eta y_i hat{x}_{i}) .

(hat{w}_{k} cdot hat{w}_{opt} = hat{w}_{k-1} cdot hat{w}_{opt} + eta y_i hat{w}_{opt} cdot hat{x}_i ge hat{w}_{k-1} cdot hat{w}_{opt} + eta gamma) .

迭代(k-1)次立即得到 (hat{w}_{k} cdot hat{w}_{opt} ge ketagamma).
對(hat{w}_k)兩邊平方，

(||hat{w}_k||^2 = ||hat{w}_{k-1}||^2 + 2eta y_i hat{w}_{k-1} cdot hat{x}_{i} + eta^2 ||hat{x}_{i}||^2). 注意到中間這項是負數(因為這是誤分類點)

立即得到 (||hat{w}_k||^2 le ||hat{w}_{k-1}||^2 + eta^2 ||hat{x}_{i}||^2 le ||hat{w}_{k-1}||^2 + eta^2 R^2).

迭代(k-1)次後立即得到 (||hat{w}_k||^2 le k eta^2 R^2) .

即可建立不等式

(ketagamma le hat{w}_{k} cdot hat{w}_{opt} le ||hat{w}_{k}|| cdot ||hat{w}_{opt}|| le sqrt{k}eta R). 再稍加變形就得到欲證的式子。

這裡(R)其實只是一個記號而已，它代表的意思是從所有誤分類中找到模長最大的，而這個記號其實是從證明過程中產生的。

作為介紹感知機原理的文章，已經寫得非常長啦，可以就此打住~

如果有任何紕漏差錯，歡迎評論互動。