機器學習入門之旅（二）線性模型之感知器

05-02

1. 線性可分（Linear separability）

以最為直觀的二維空間為例，平面上分布著藍色和紅色兩種顏色的點，如果存在一條直線，使得藍色點全部分布在直線一側，紅色點全部分布在另外一側，那麼這兩類點集是線性可分的。在三維空間，線性可分指兩類點都分布在一個平面的兩側。類似地推廣到更高維的歐幾里得空間，n維空間中的點集線性可分意味著存在n-1維的超平面將其完全分隔。

數學定義：對於n維歐幾里得空間中的兩類點集 $X_{0}$ 和 $X_{1}$ ，存在n+1個實數，使得每個 $X_{0}$ 中的點 $X in X_0$ 滿足 $sum_{i=1}^{n} omega_i x_i> k$ ，使得每個 $X_{0}$ 中的點 $X in X_1$ 滿足 $sum_{i=1}^{n} omega_i x_i< k$ ，則點集 $X_{0}$ 和 $X_{1}$ 線性可分。

2. 感知器

所謂感知器，是一種用於二分類的線性分類模型，其輸入為樣本的特徵向量，計算這些輸入的線性組合，如果輸出結果大於某個閥值就輸出1，否則輸出-1。

因為是我們將要接觸到的第一個模型，這裡我會講的詳細一點。

對於輸入，以向量的形式來表示， $X=(x_1,x_2,cdot cdot cdot ?,x_n)^T$ ，含有n個特徵。每個特徵對最終輸出的影響有大有小，於是我們給每個分配一個權重 $omega _{i}$ 。對於所有的特徵，計算加權「總分」 $sum_{i=1}^{n}{omega _ix_i}$ ，同時以一個臨界值（閥值threshold）來區分輸出+1和-1：

用上一章提到的機器學習的符號來表示，並做一點小小的等效變換。用來表示我們的線性假設：

訓練一個感知器，意味著選擇 $W= (omega _0,omega _2,cdot cdot cdot ?,omega _n)$ 的值。所以感知器學習要考慮的假設集（假設空間）H就是所以可能的實數權重向量的集合：

假設我們有含有m個樣本數據的訓練集，表示為：

對於第i個樣本( $x^{(i)}, y^{(i)}$ )，特徵向量表示為 $x^{(i)}=(x_0^{(i)},x_2^{(i)},cdot cdot cdot ?,x_n^{(i))})$ 。即， $x_j^{(i)}$ 表示第i個輸入樣本的第j個特徵，其中 $x_0^{(i)}=0$ 。

下面的任務就是基於訓練數據，應用感知器演算法，從假設空間中訓練出最合適的權重，得到最終的，具體步驟如下：

1. 初始化 $W$ , 比如初始化為0或者一個很小的隨機值；

2. 對於 $D$ 中的每一個樣本( $x^{(i)}, y^{(i)}$ )，執行以下計算：

（a）. 計算 $y^{(i)}=sign (sum_{i=0}^{n} omega _i x_m^{(i)} )= sign (W^T X^{(i)} )$

（b）. 對於 $y^{(i)} e y^{(i)}$ 的點，即（a）計算出來是錯誤的分類的點，更新權重向量： $W:=W+ y^{(i)} X^{(i)}$

重複步驟2，直到所有錯誤分類的點的數量 $sum_{i=1}^{m} frac{1}{2} | y^{(i)} - y^{(i)} |$ 小於預先設定的值，或者迭代次數達到預先設定的值。

上面的步驟，可能2（b）理解起來稍有點困難，在此給一些直觀的解釋以幫助理解。分類錯誤無非就是兩種情況:

$(W^TX^{(i) }>0, y^{(i)} =+1, y^{(i) }=-1)$ 或者 $(W^TX^{(i) }<0, y^{(i)} =-1, y^{(i) }=+1)$

前一種情況， $W^TX^{(i) }>0$ 代表向量W和 $X^{(i) }$ 的夾角小於90度，更新後的權重向量 $W+ y^{(i)} X^{(i)}=W- X^{(i)}$ $X^{(i) }$ 的夾角必定大於90度，其向量積小於0。此時的W能夠保證此點正確分類。後一種情況依此類推。也可參考下圖。

如果訓練數據 $D$ 線性可分，則感知器可以確保收斂（即能找到一個W，保證所有樣本正確分類），並且迭代的次數有上界（證明略，以後有時間可以補上）。但是，問題是W有無數條，W選擇不同的初始化值，可能得到不同的結果。

如果訓練數據 $D$ 非線性可分，因為感知器是一種線性分類器，無法最終收斂。但是，除了低維度的情況，我們無法預先知道訓練數據是否線性可分。這時，我們調整我們的目標為找到一個誤分類數量最少的W：

但是，感知器演算法，在迭代過程中，並不總是向著收斂的方向逼近。比如，我們基於某個誤分類樣本樣本( $x^{(i)}, y^{(i)}$ )調整權重向量W之後，可以會造成其他本來正確分類的樣本在調整之後的權重下變成錯誤分類。

因此，我們對演算法做一個小的改進：對於已有的 $W_t$ 和迭代之後得到 $W_{t+1}$ ，分別統計誤分類的樣本數量；如果誤分類的數量少 $W_{t+1}$ ，那麼就讓 $W_{t+1}$ 替代 $W_{t}$ ，否則 $W_{t}$ 不變。這種方法，稱為口袋演算法。形象地講，就是我們先把已經遇到的最好的W放在「口袋」里。後面遇到更好的W，我們就進行替換，遇不到更好的保留原有的。

最後，給出一個用R語言實現感知器的實例：

#數據來源於R自帶的iris數據集，只截取Sepal.Length和Sepal.Width兩個特徵traindata <- head(iris, 100)labeled_traindata <- data.frame(x1 = traindata[1:100,1],x2 = traindata[1:100, 2], y = c(rep(1, 50), rep(-1, 50)))plot(4:8, 1:5, type = "n", xlab = "Sepal.Length", ylab = "Sepal.Width")points(labeled_traindata[0:50,1], labeled_traindata[0:50,2], col = "red")points(labeled_traindata[51:100,1], labeled_traindata[51:100,2], col = "green")PLA <- function(x, y, initial, t){ x <- as.matrix(cbind(x0 = rep(1, 100), x));#注意別忘了添加x0 w <- initial; t1 <- 0; while(t1<t) { t1 <- t1 + 1; err <- 0; for (i in 1:100) { if(sign(w%*%x[i,])!=y[i]) { err = err + 1; w = w + y[i]*x[i,] } } if(!err) break } return(list(w = w, t = t1, err = err))}result <- PLA(as.matrix(labeled_traindata[,1:2]), labeled_traindata[,3], initial = c(0,0,0), t = 1000)resultabline(a = -result$w[1]/result$w[3], b = -result$w[2]/result$w[3])

結果顯示，經過721次迭代，W = （126， -79.8， 101.4），所以樣本均被正確分類。

參考：

Perceptron - Wikipedia

Tom. M Mitchell 《機器學習》