感知機（perceptron）是二類分類的線性分類模型，它的思想很簡單，就是在一個二維空間中尋找一條直線將紅點和藍點分開（圖1），類比到高維空間中，感知機模型嘗試尋找一個超平面，將所有二元類別分開（圖2）。

圖1：二維空間

圖2：三維空間

如果我們找不到這么一條直線的話怎么辦？找不到的話那就意味著類別線性不可分（圖3），也就意味著感知機模型不適合你的數(shù)據(jù)的分類。使用感知機一個最大的前提，就是數(shù)據(jù)是線性可分的。

圖3：不可分數(shù)據(jù)

1.感知機模型

如果我們有n個樣本，每個樣本有m維特征和一個二元輸出類別：

$((x_{1}^0，x_{2}^0...x_{m-1}^0,x_{m}^0,y_{0} ),(x_{1}^1，x_{2}^1...x_{m-1}^1,x_{m}^1,y_{1} ),....(x_{1}^n，x_{2}^n...x_{m-1}^n,x_{m}^n,y_{n} ))$

感知機的目標是找到一個超平面：

$\omega _{1} x_{1} +\omega _{2} x_{2} +...+\omega _{m} x_{m} + b = 0$

讓其中一個類別的樣本滿足 $\omega _{1} x_{1} +\omega _{2} x_{2} +...+\omega _{m} x_{m} + b > 0$ ,而另一類樣本滿足

$\omega _{1} x_{1} +\omega _{2} x_{2} +...+\omega _{m} x_{m} + b < 0$ ，從而樣本線性可分。但這樣的超平面并不是唯一的，感知機模型采取不同的初始值（ $\vec{\omega }_{0} ，b_{0}$ ）解可能會不同。

我們用相量方式對上式進行表達： $\vec{\omega} \bullet \vec{x} + b = 0$ ，由此感知機的模型可以定義為：

$y = sign( \vec{\omega} \bullet \vec{x} +b)$ ,其中：

例如：將一個新的樣本 $\vec{x1}$ 帶入訓練好的模型 $\vec{\omega} \bullet \vec{x} + b$ ，當?? $\vec{\omega} \bullet \vec{x1} + b \geq 0$ ， $\vec{x1}$ ?被分為 $+1$ 類。當? $\vec{\omega} \bullet \vec{x1} + b < 0$ ，? $\vec{x1}$ 被分為 $-1$ 類。

2.感知機模型的損失函數(shù)（Loss Function）

我們將滿足 $\vec{\omega} \bullet \vec{x} + b \geq 0$ 的樣本類別輸出值取 $+1$ ，滿足 $\vec{\omega} \bullet \vec{x} + b < 0$ 的樣本類別輸出值取 $-1$ 。從而正確分類的樣本滿足 $y（ \vec{\omega} \bullet \vec{x} + b）> 0$ ，而錯誤分類的樣本滿足 $y（ \vec{\omega} \bullet \vec{x} + b）< 0$ 。損失函數(shù)的優(yōu)化目標是使所有被錯誤分類的樣本到超平面的距離之和最小。

一個被錯誤分類的樣本 $i$ ， $y_{i} （ \vec{\omega} \bullet \vec{x_{i} } + b）< 0$ ，到超平面的距離是 $-y_{i} （ \vec{\omega} \bullet \vec{x_{i} } + b）/\vert \vert \vec{\omega } \vert \vert _{2}$ ，

其中 $\vert \vert \vec{\omega } \vert \vert _{2} = \sqrt{\sum_{i=1}^m\omega _{i}^2 }$ ? ?。 $\vec{\omega }$ 為超平面的法向量， $\vec{\omega }$ 的大小變化并不會影響樣本點到超平面的距離。我們令 $\vert \vert \vec{\omega } \vert \vert _{2} = 1$ ，并且假設所有錯誤分類的點的集合為M，則所有錯誤分類的樣本到超平面的距離之和為：

$- \sum_{\vec{x_{i} } \in M}y_{i} （ \vec{\omega} \bullet \vec{x_{i} } + b）$

最終構(gòu)建的損失函數(shù)為：

$L(\vec{\omega } ，b) = - \sum_{\vec{x_{i}} \in M}y_{i} （ \vec{\omega} \bullet \vec{x_{i} } + b）$

3.感知機模型的優(yōu)化方法

感知機模型選擇的是采用隨機梯度下降，這意味著我們每次僅僅需要使用一個誤分類的點來更新梯度。損失函數(shù) $L(\vec{\omega } ，b)$ 的梯度如下：

$?_{\omega } L(\vec{\omega } ，b) = - \sum_{\vec{x_{i}} \in M}y_{i} \vec{x_{i}}$

$?_ L(\vec{\omega } ，b) = - \sum_{\vec{x_{i}} \in M}y_{i}$

隨機選取一個錯誤分類點 $(\vec{x_{i}} ,y_{i} )$ ，對 $\vec{\omega } ，b$ 進行更新：

$\vec{\omega } \leftarrow \vec{\omega _{0} } +\eta y_{i}\vec{x_{i}}$

$b \leftarrow b_{0} +\eta y_{i}$

式中 $\vec{\omega }_{0} ，b_{0}$ 為初始值， $\eta (0<\eta \leq 1)$ 是步長（learning rate）。通過這樣迭代可以使損失函數(shù) $L(\vec{\omega } ，b)$ 不斷減小，直到為0。

感知機模型的優(yōu)化方法可以通俗的解釋為：當一個樣本被錯誤分類，即位于分類超平面的錯誤一側(cè)時，則調(diào)整 $\vec{\omega } ，b$ 的值，使分類超平面向該錯誤分類點的一側(cè)移動，以減少該錯誤分類點與超平面間的距離，直至超平面越過該錯誤分類點，最終被正確分類。

4.感知機模型的優(yōu)化方法的對偶形式

上一節(jié)的感知機模型的算法形式我們一般稱為感知機模型的算法原始形式。對偶形式是對算法執(zhí)行速度的優(yōu)化。對偶形式的基本想法是將 $\vec{\omega } ，b$ 表示為樣本 $\vec{x_{i} }$ 和標簽 $y_{i}$ 的線性組合，通過求解其系數(shù)而求得 $\vec{\omega } ，b$ 。我們?nèi)〕跏贾?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Cvec%7B%5Comega%20%7D_%7B0%7D%20%20%20%20%EF%BC%8Cb_%7B0%7D%20" alt="\vec{\omega }_{0} ，b_{0} " mathimg="1">為 $0$ ，選取錯誤分類樣本 $(\vec{x_{i}} ,y_{i} )$ 對 $\vec{\omega } ，b$ 進行更新有：

$\vec{\omega } \leftarrow\eta y_{i}\vec{x_{i}}$

$b \leftarrow \eta y_{i}$

假設為了將樣本 $\vec{x_{i} }$ 正確分類而更新 $\vec{\omega } ，b$ 的次數(shù)為 $m_{i}$ ，每一個樣本 $(\vec{x_{i}} ,y_{i} )$ 的 $m_{i}$ 的初始值為 $0$ ，每當次樣本在某一次梯度下降迭代中因誤分類而更新時， $m_{i}$ 的值 $+1$ ，則 $\vec{\omega } ，b$ 關于 $(\vec{x_{i}} ,y_{i} )$ 的增量分別為 $m_{i} \eta y_{i}\vec{x_{i}}$ 和 $m_{i} \eta y_{i}$ 。則用所有樣本對 $\vec{\omega } ，b$ 進行更新，最后得到的 $\vec{\omega } ，b$ 可以表示為

$\vec{\omega } =\sum_{i=1}^nm_{i} \eta y_{i}\vec{x_{i}}$

$b =\sum_{i=1}^nm_{i} \eta y_{i}$

$m_{i}$ 的通俗解釋：如果 $m_{i}$ 的值越大，那么意味著樣本 $x_{i}$ 經(jīng)常被誤分。很明顯離超平面很近的點，當超平面稍微移動一點點， $x_{i}$ 的類別就發(fā)生變化。

我們用 $y（ \vec{\omega} \bullet \vec{x} + b）< 0$ 的等價形式? $y(\sum_{i=1}^nm_{i} \eta y_{i}\vec{x_{i}} \bullet \vec{x} + \sum_{i=1}^nm_{i} \eta y_{i})< 0$ 來判斷錯誤分類。上式中 $\vec{x_{i}} \bullet \vec{x}$ 表示的是兩個樣本的內(nèi)積，而且這個內(nèi)積的結(jié)果在更新 $\vec{\omega }$ 的過程中會多次使用。如果我們事先用矩陣運算計算出所有的樣本之間的內(nèi)積，那么在算法運行時，僅僅一次的矩陣內(nèi)積運算比多次的循環(huán)計算省時。計算量最大的判斷誤分類這兒就省下了很多的時間，這也是對偶形式的感知機模型比原始形式優(yōu)的原因。