《統計學習方法》學習筆記：第二章 感知機

• 2 感知機
• • 2.1 感知機模型
  • 2.2 感知機學習策略
  • • 2.2.1 數據的線性可分性
    • 2.2.2 感知機學習策略
  • 2.3 感知機學習算法
  • • 2.3.1 感知機學習算法的原始形式
    • 2.3.2 算法的收斂性
    • 2.3.3 感知機學習算法的對偶形式
  • 本章概要

2 感知機

• 感知機（perceptron）是二分類的線性分類模型，其輸入為實例的特征向量，輸出為實例的類別，取+1或-1二值。感知機對于輸入空間（特征空間）中將實例劃分為正負兩類的分離超平面，屬于判別模型。感知機學習旨在求出將訓練數據進行線性劃分的分離超平面，為此，導入基于誤分類的損失函數，利用梯度下降法對損失函數進行極小化，求得感知機模型。
• 感知機學習算法具有簡單而易于實現的優點，分為原始形式和對偶形式。感知機預測是用學習到的感知機模型，對新的輸入實例進行分類。感知機于1957年由Rosenblatt提出，是神經網絡與支持向量機的基礎。

2.1 感知機模型

• 感知機【定義】
  假設輸入空間（特征空間）是 $X\in R^n$ ，輸出空間是 $Y=\{?1,+1\}$ 。輸入 $x\in X$ 表示實例的特征向量，對于輸入空間的點；輸出 $y\in Y$表示實例的類別。由輸入空間到輸出空間的如下函數:$$f(x)=sign(w?x+b)$$稱為感知機。其中，$w$和$b$為感知機模型參數， $w\in R^n$叫做權值（weight）或權值向量（weight vector），$b\in R$ 叫做偏置（bias），$w?x$表示$w$和$x$的內積，$sign$是符號函數，即：
  $$sign(x)=\{\begin{array}{ll}+1,& x\ge 0\\ ?1,& x<0\end{array}$$
• 感知機是一種線性分類模型，屬于判別模型。感知機模型的假設空間是定義在特征空間中的所有線性分類模型或線性分類器，即函數集合$\{f|f(x)=w?x+b\}$。
• 感知機有如下幾何解釋：線性方程$$w?x+b=0$$對應于特征空間$R^n$中的一個超平面$S$，其中$w$是超平面的法向量，$b$是超平面的截距。這個超平面將特征空間劃分為兩個部分，位于兩部分的點（特征向量）分別被分為正負兩類。因此，超平面 $S$ 稱為分離超平面。
  
• 感知機學習，由訓練數據集（實例的特征向量及類別）$$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$,求得感知機模型，即求得模型參數 $w,b$ 。感知機預測，通過學習得到的感知機模型，對于新的輸入實例給出其對應的輸出類別。

2.2 感知機學習策略

2.2.1 數據的線性可分性

給定一個數據集$$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$，如果存在某個超平面 $S$，能夠將數據集的正實例點和負實例點完全正確的劃分到超平面的兩側，即對所有 $y_i=+1$ 的實例 $i$ ，有 $w?x_i+b>0$，對所有 $y_i=?1$ 的實例 $i$ ，有 $w?x_i+b<0$，則稱數據集 $T$ 為線性可分數據集；否則，稱數據集 $T$ 為線性不可分。

2.2.2 感知機學習策略

• 假設訓練數據集是線性可分的，感知機學習的目標是求得一個能夠將訓練集正實例點和負實例點完全正確分開的分離超平面。為了找出這樣的超平面，即確定感知機模型參數 $w,b$ ，需要確定一個學習策略，即定義（經驗）損失函數并將損失函數極小化。
• 損失函數的一個自然選擇是誤分類點的總數。但是，這樣的損失函數不是參數$w,b$的連續可導函數，不易優化。損失函數的另一個選擇是誤分類點到超平面$S$的總距離，這是感知機所采用的。為此，首先寫出輸入空間$R^n$中任一點$x_0$到超平面$S$的距離：$$\frac{1}{||w||}|w?x_0+b|$$這里，$||w||$是$w$的$L_2$范數。
• 其次，對于誤分類的數據$(x_i,y_i)$來說，$$?y_i(w?x_i+b)>0$$成立。因為當$w?x_i+b>0$時，$y_i=?1$；當$w?x_i+b<0$時，$y_i=+1$；因此，誤分類點$x_i$到超平面$S$的距離是$$?\frac{1}{||w||}{y}_i(w?x_i+b)$$
• 這樣，假設超平面的誤分類點集合為$M$，那么所有誤分類點到超平面的總距離為$$?\frac{1}{||w||}\sum _{x_i\in M}{y}_i(w?x_i+b)$$，不考慮 $\frac{1}{||w||}$ 就得到感知機學習的損失函數。
• 給定訓練數據集$$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$。感知機$sign(w?x+b)$學習的損失函數定義為$$L(w,b)=?\sum _{x_i\in M}{y}_i(w?x_i+b)$$，其中$M$為誤分類點的集合。這個損失函數就是感知機學習的經驗風險函數。
• 顯然，損失函數$L(w,b)$是非負的。如果沒有誤分類點，損失函數值為0.而且，誤分類點越少，誤分類點離超平面越近，損失函數值就越小。一個特點樣本點的損失函數：在誤分類時，是參數$w,b$的線性函數，在正確分類時是0.因此，給定訓練數據集$T$，損失函數$L(w,b)$是$w,b$的連續可導函數。
• 感知機學習的策略是在假設空間中選取使損失函數式最小的模型參數$w,b$,即感知機模型。

2.3 感知機學習算法

2.3.1 感知機學習算法的原始形式

• 感知機學習問題轉化為求解損失函數式的最優化問題，最優化的方法是隨機梯度下降法。
• 感知機學習算法是對以下最優化問題的算法。給定訓練數據集$$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$。
• 感知機$sign(w?x+b)$學習的損失函數定義為$$L(w,b)=?\sum _{x_i\in M}{y}_i(w?x_i+b)$$，其中$M$為誤分類點的集合。求參數$w,b$使其為以下損失函數極小化問題的解：$$mi{n}_{w,b}L(w,b)=?\sum _{x_i\in M}{y}_i(w?x_i+b)$$
• 感知機學習算法是誤分類驅動的，具體采用隨機梯度下降法。首先，任意選取一個超平面$w_0,b_0$，然后用梯度下降法不斷地極小化目標函數。極小化過程中不是一次使$M$中所有誤分類點的梯度下降，而是一次隨機選取一個誤分類點使其梯度下降。
• 感知機學習算法的原始形式
  輸入：訓練數據集$$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$；學習率 $\eta$ $(0<\eta \le 1)$.
  輸出：$w,b$；感知機模型：$f(x)=sign(w?x+b)$
  (1)選取初值$w_0,b_0$
  (2)在訓練集中選取數據$(x_i,y_i)$
  (3)如果 $y_i(w?x_i+b)\le 0$，$$w\leftarrow w+\eta y_i{x}_i$$ $$b\leftarrow b+\eta y_i$$
  (4)轉至(2)，直至訓練集中沒有誤分類點。
• 感知機學習算法的原始形式直觀上有如下解釋：當一個實例點被誤分類，即位于分離超平面的錯誤一側時，則調整$w,b$的值，使分離超平面向該誤分類點的一側移動，以減少該誤分類點與超平面間的距離，直至超平面超過該誤分類點使其被正確分類。

2.3.2 算法的收斂性

• 對于線性可分數據集，感知機學習算法原始形式收斂，即經過有限次迭代可以得到一個將訓練數據集完全正確劃分的分離超平面及感知機模型。
• 誤分類的次數是有上界的，經過有限次搜索，可以找到將訓練數據完全分開的超平面。也就是說，當訓練數據集線性可分時，感知機學習算法原始形式是收斂的。
• 感知機學習算法存在許多解，這些解既依賴于初值的選擇，也依賴于迭代過程中誤分類點的迭代次序，為了得到唯一的超平面，需要對分離超平面添加約束條件。當訓練集線性不可分時，迭代結果會發生震蕩。

2.3.3 感知機學習算法的對偶形式

• 對偶形式的基本想法是，將 $w$ 和 $b$ 表示為實例 $x_i$ 和標記 $y_i$ 的線性組合的形式，通過求解系數而求得 $w$ 和 $b$ 。在感知機學習算法的原始形式中，假設初始值$w_0,b_0$均為0.對誤分類點$(x_i,y_i)$通過$$w\leftarrow w+\eta y_i{x}_i$$ $$b\leftarrow b+\eta y_i$$，逐步修改$w,b$，設修改n次，則$w,b$關于$(x_i,y_i)$的增量分別是$a_i{y}_i{x}_i$和$a_i{y}_i$，這里$a_i=n_i\eta$.
• 在學習過程中不難看出，最后學習到的$w,b$可以分別表示為$$w=\sum _{i=1}^N{a}_i{y}_i{x}_i$$ $$b=\sum _{i=1}^N{a}_i{y}_i$$這里，$a_i\ge 0,i=1,2,?,N$，當$\eta =1$時，表示第$i$個實例點由于誤分而進行更新的次數。實例點更新次數越多，意味著它距離分離超平面越近，也就越難正確分類，這樣的實例對學習結果影響最大。
  感知機學習算法的對偶形式
  輸入：線性可分的數據集$$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$；學習率 $\eta$ $(0<\eta \le 1)$.
  輸出：$a,b$；感知機模型：$$f(x)=sign(\sum _{j=1}^N{a}_j{y}_j{x}_j+b)$$,其中$a=(a_1,a_2,?,a_N{)}^T$
  （1）$a\leftarrow 0,b\leftarrow 0$
  （2）在訓練集中選取數據$(x_i,y_i)$
  （3）如果$$y_i(\sum _{j=1}^N{a}_j{y}_j{x}_j?x_i+b)\le 0$$,
  $$a\leftarrow a_i+\eta$$,$$b\leftarrow b+\eta y_i$$
  （4）轉至（2）直至沒有誤分類數據
• 對偶形式中，訓練實例僅以內積的形式出現，為了方便，可以預先將訓練集中實例間的內積計算出來，并以矩陣的形式存儲，這個矩陣就是Gram矩陣：$$G=[x_i?x_j{]}_{N?N}$$

本章概要

感知機是根據輸入實例的特征向量$x$對其進行二分類的線性分類模型:$$f(x)=sign(w?x+b)$$感知機模型對應于輸入空間（特征空間）中的分離超平面：$$w?x+b=0$$

感知機學習的策略是極小化損失函數:$$mi{n}_{w,b}L(w,b)=?\sum _{x_i\in M}{y}_i(w?x_i+b)$$損失函數對應于誤分類點到分離超平面的總距離。

感知機學習算法是基于隨機梯度下降法的對損失函數的最優化算法，有原始形式和對偶形式，算法簡單且易于實現。原始形式中，首先任意選一個超平面，然后用梯度下降法不斷極小化目標函數。在這個過程中，一次隨機選取一個誤分類點使其梯度下降。

當訓練數據集線性可分時，感知機學習算法是收斂的。感知機算法在訓練數據集上的誤分類次數 $k$ 滿足不等式：$$k\le (\frac{R}{\gamma }{)}^2$$當訓練數據集線性時，感知機學習算法存在無窮多個解，其解由不同的初值或不同的迭代次序而可能有所不同。

總結

以上是生活随笔為你收集整理的机器学习理论《统计学习方法》学习笔记：第二章 感知机的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。