[強(qiáng)基計劃] 統(tǒng)計學(xué)習(xí)方法之感知機(jī)Perceptron

感知機(jī)

2.1 感知機(jī)模型

? 感知機(jī)模型屬于一種判別模型胸囱，感知機(jī)的定義如下：

? （定義2.1）感知機(jī)：假設(shè)輸入空間（特征空間）為 $X\subseteq R^n$ 凛虽，輸出空間為y={+1,-1}蚁趁，那么函數(shù):
$f(x)=sign(w\cdot x+b) \tag {2.1}$
? 被稱為感知機(jī)据途，可見感知機(jī)的本質(zhì)就是一個符號化函數(shù)，其中：
$sign(x)=\left\{ \begin{array} +1, x\ge 0,\\ -1, x<0. \end{array} \right. \tag {2.2}$
? 顯然扛邑，感知機(jī)是一種線性分類器怜浅。

2.2 數(shù)據(jù)集的線性可分特性，感知器學(xué)習(xí)方法

? （定義2.2）數(shù)據(jù)集的線性可分性：對一個數(shù)據(jù)集 $T=\{(x_1,y_1),(x_2,y_2),(x_N,y_N)\}$ 蔬崩，其中， $x_i \in X \subseteq R^n$ 搀暑， $y_i \in \{+1,-1\}$ , 如果存在某一個超平面S沥阳，使 $w\cdot x+b=0$ 能夠把數(shù)據(jù)的正實例與負(fù)實例完全正確劃分，那么我們就說這個數(shù)據(jù)集是線性可分的自点。

? 在數(shù)據(jù)集可以被線性區(qū)分的前提下桐罕，我們開始設(shè)計感知機(jī)的損失函數(shù)。一個非常直觀的想法是用區(qū)分錯誤的點來作為感知機(jī)損失函數(shù)的依據(jù)桂敛。如果使用區(qū)分錯誤的點的總數(shù)作為損失函數(shù)的話功炮，的確可以優(yōu)化感知機(jī)，但是無法微分术唬，很難快速進(jìn)行優(yōu)化薪伏。目前的感知機(jī)采用誤分類的點到超平面S的距離作為損失函數(shù)，它的表達(dá)式很容易推導(dǎo)粗仓，首先嫁怀，對輸入的樣本中任意一點 $x_0 \in R^n$ 设捐，根據(jù)距離公式得：
$distance = \frac{1}{||w||}|w\cdot x_0+b| \tag{2.3}$
? 也就是它到超平面的距離等于它代入平面方程計算出的絕對值，除以超平面法向量的內(nèi)積（ $L_2$ 范數(shù) norms）塘淑。對于誤分類的數(shù)據(jù) $(x_i,y_i)$ 來說萝招，如果它是+，錯誤的分到了-存捺，那么有
$-y_i(w\cdot x_i+b)→-\times+\times->0 \tag{2.4}$
? 同理槐沼，上式對-分為+也有效，之所以求這個是為了說明絕對值的微分情況捌治，于是對點 $x_i$ 母赵，(2.3)式脫絕對值有：
$distance = -\frac{1}{||w||}(w\cdot x_i+b)$
? 誤分類的點（集合M）的總距離就為
$distance_{all}=-\frac{1}{||w||}\sum_{x_i\in M}y_i(w\cdot x_i+b) \tag{2.5}$
? 由于 $-\frac{1}{||w||}$ 為常數(shù)，所以在偏導(dǎo)數(shù)運(yùn)算中可以忽略。故有最終的Loss 函數(shù)：
$L(w,b)=-\sum_{x_i \in M}y_i(w\cdot x_i+b) \tag {2.6}$
? 其實損失函數(shù)也可以為負(fù)數(shù)背捌，不過優(yōu)化方向就有點詭異（不斷增大）昼接，這樣還不如設(shè)定為正方便。

2.3 感知機(jī)的學(xué)習(xí)算法

? 感知機(jī)的學(xué)習(xí)算法其實就是要達(dá)成一個目標(biāo)周蹭，使
$\min\limits_{w,b} L(w,b)=-\sum_{x_i \in M} y_i(w\cdot x+b) \tag{2.7}$
? 通用的感知器學(xué)習(xí)算法是誤分類驅(qū)動的（誤分類調(diào)整損失函數(shù)），并使用隨機(jī)梯度下降方法（stochastic gradient descent）疲恢。算法初始條件是超平面 $w_0,b_0$ 凶朗。對于固定的誤分類點集合M，損失函數(shù)的梯度為（對上面的w显拳，b進(jìn)行微分）：
$\triangledown_w L(w,b)= -\sum_{x_i\in M} y_ix_i \tag{2.8}$

$\triangledown_b L(w,b)=-\sum_{x_i \in M} y_i \tag {2.9}$

? 之所以叫隨機(jī)梯度下降算法棚愤，是因為它每次隨機(jī)選取一個誤分類點 $(x_i,y_i)$ ，對w,b進(jìn)行更新杂数，如下：
$w \leftarrow w+\eta y_i x_i \tag{2.10}$

$b\leftarrow b +\eta y_i \tag {2.11}$

? 你可能會疑惑 $\eta$ 是什么宛畦，它是學(xué)習(xí)率（learning rate），調(diào)整內(nèi)部參數(shù)更新的速度揍移，屬于超參數(shù)次和。

? 感知機(jī)算法將會運(yùn)行直到誤分類集合M清空。（也可能提前被煉丹師終止）那伐。感知機(jī)所得到的解不一定相同（求一個試試踏施，比如 $x_1 = (2,2)^T +, x_2 = (1.0)^T -$ .

? 感知機(jī)算法是收斂的（經(jīng)過有限次迭代在線性可分數(shù)據(jù)集可以得到解），記 $\hat w = (w^T,b)^T$ , $\hat x=(x^T, 1)^T$ 罕邀，則 $\hat w \hat x = w\cdot x +b$ （線性代數(shù)的一種方法）畅形。在此基礎(chǔ)上，有定理2.1 （Novikoff)诉探。它說明日熬，存在 $w_{opt}，\gamma$ 阵具，可以正確區(qū)分T中所有數(shù)據(jù)碍遍，（滿足 $\hat w_{opt} \hat x=0$ )使得對所有的i=1,2,...,N定铜，點 $x_i$ ，有
$y_i(\hat w_{opt}\cdot \hat x_i)=y_i (w_{opt}\cdot x_i + b_{opt})\ge \gamma \tag{2.12}$
? 令 $R=\max\limits_{1\le i\le N}||x_i||$ 怕敬，則感知機(jī)的誤分類次數(shù)應(yīng)該滿足 $k\le (\frac{R}{\gamma})^2$ 揣炕。證明如下：

? 對于線性可分的數(shù)據(jù)集，顯然是存在 $\hat w_{opt}$ 的东跪，但怎么理解 $\hat w_{opt} \hat x=0$ 時候卻有(2.12)成立呢畸陡？其實我們由之前的定義知道， $\hat x =(x^T,1)^T$ 虽填，這樣只要調(diào)整b丁恭，使 $||\hat w_{opt}||$ =1，那么對于有限的i=1斋日，2牲览，...，N恶守，顯然
$y_i(\hat w_{opt} \cdot \hat x_i) >0$
? 因為數(shù)據(jù)都被正確分類第献，所以自然標(biāo)簽和分類結(jié)果的符號一致，所以必定>0,這樣兔港，只要取 $\gamma = \min\limits_i \{y_i(\hat w_{opt}\cdot \hat x_i)\}$ 庸毫，那么就可以確保(2.12)式子成立。

? （2）對于第k-1次誤分類衫樊，由(2.4)有
$y_i(\hat w_{k-1}\cdot \hat x_i)=y_i(w_{k-1}\cdot x_i + b_{k-1}) \le 0 \tag {2.13}$
? 這樣飒赃，w,b的權(quán)值更新為：
$w_k \leftarrow w_{k-1}+\eta y_i x_i$

$b_k \leftarrow b_{k-1} + \eta y_i$

? 綜合上面兩個式子為向量，也就是
$\hat w_k \leftarrow \hat w_{k-1} + \eta y_i \hat x_i \tag {2.14}$
? 假設(shè) $\hat w_{opt}$ 存在科侈，那么由(2.14),(2.12)有
$\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$
? 由载佳，數(shù)學(xué)歸納法有
$\hat w_k \cdot \hat w_{opt} \ge \hat w_{k-1} \cdot \hat w_{opt} +\eta\gamma \ge \hat w_{k-2} \cdot \hat w_{opt} +2\eta\gamma \ge ... \ge k\eta\gamma \tag {2.15}$
? 由(2.13)和(2.14)，可以得到另一個不等式
$||\hat w_k||^2 = ||\hat w_{k-1}||^2+2\eta y_i \hat x_i \hat w_{k-1}+\eta^2 ||\hat x_i||^2 (因為y_i 的平方為1)\le \\ ||\hat w_{k-1}||^2 +\eta^2 ||x_i||^2 \le ||\hat w_{k-1}||^2 + \eta^2R^2\le(重復(fù)以上操作)||\hat w_{k-2}||^2+2\eta^2R^2\le...\le k\eta^2R^2 \tag {2.16}$
? 結(jié)合(2.15)和(2.16)兑徘，我們可以發(fā)現(xiàn)刚盈，
$k\eta\gamma\le\hat w_k \hat w_{opt}\le||\hat w_k||||\hat w_{opt}||\le \sqrt{k}\eta R$

2.4 感知機(jī)學(xué)習(xí)的對偶形式

? 所謂對偶形式，其實是這樣的：由之前的隨機(jī)梯度下降方法挂脑，我們發(fā)現(xiàn)感知機(jī)根據(jù)誤分類點修正超平面的方法是根據(jù)它的標(biāo)簽 $(x_i,y_i)$ 來達(dá)成的，假設(shè)修改n次欲侮，那么w,b關(guān)于 $(x_i,y_i)$ 的增量分別為 $\alpha_iy_ix_I$ 和 $\alpha_iy_i$ 崭闲，這里 $\alpha_i=n_i\eta$ ，這樣威蕉，從學(xué)習(xí)過程可以發(fā)現(xiàn)刁俭，經(jīng)過n次學(xué)習(xí)以后，w,b可以表示為：
$w=\sum^N_{i=1}\alpha_iy_ix_I \tag {2.17}$