本文是在對李航老師《統計學習方法》第二章感覺機，學習後的讀書筆記與個人的一些了解，内容如果有錯，歡迎大家指正，我們一起進步：）
感覺機模型
輸入空間 X \mathcal{X} X，輸出空間 Y = { − 1 , + 1 } \mathcal{Y}=\{-1,+1\} Y={−1,+1}， x ∈ X , y ∈ Y x\in\mathcal{X},y\in\mathcal{Y} x∈X,y∈Y，w為權值，b是偏量，sign(·)是符号函數
感覺機模型為：
f ( x ) = s i g n ( w ⋅ x + b ) f(x)=sign(w·x+b) f(x)=sign(w⋅x+b)
其實，更好了解地看這個模型其實就是在對我們的輸入資料計算後與某個标準進行比較進而對其分類。 w w w是一個向量分别對應着輸入的每個屬性，它作為權值，可以簡單地了解為一個打分的标準，我們将 w ⋅ x w·x w⋅x視為某個輸入資料的得分，某個屬性我們認為比較重要就為其賦予更大的權值，那麼這個屬性的變動就會引起得分的更大變動，是以屬具有更大權值那麼就具有對結果更大的影響力。
而将 − b -b −b視為一個分類的标準 w ⋅ x > − b w·x>-b w⋅x>−b與 w ⋅ x < − b w·x<-b w⋅x<−b呈現的是這個輸入是否達到了我們設定的某個标準，據此達到了是一類，未達到是另一類。移動不等式，添加符号函數 s i g n ( ⋅ ) sign(·) sign(⋅)，前面的達到标準與未達标準就對應着+1和-1的輸出。
式 ( 1 ) (1) (1)中最重要的部分就是 w ⋅ x + b w·x+b w⋅x+b，當 w ⋅ x + b = 0 w·x+b=0 w⋅x+b=0這表示着一個界限，區分開 w ⋅ x > − b w·x>-b w⋅x>−b和 w ⋅ x < − b w·x<-b w⋅x<−b的輸入。這個界限就是一個超平面，它是由所有滿足 w ⋅ x + b = 0 w·x+b=0 w⋅x+b=0的點組成，那麼就不難知道超平面上的任意向量 x 1 x 2 ⃗ \vec{x_1x_2} x1x2
（ x 1 , x 2 x_1,x_2 x1,x2是超平面上的任意兩點）滿足：
x 1 x 2 ⃗ ⋅ w = 0 \vec{x_1x_2}·w=0\\ x1x2
⋅w=0
有：
( x 2 − x 1 ) ⋅ w = x 2 ⋅ w + b − b − x 1 ⋅ w = ( x 2 ⋅ w + b ) − ( x 1 ⋅ w + b ) = 0 \begin{aligned} &(x_2 - x_1)·w\\ =&x_2·w+b-b-x_1·w\\ =&(x_2·w+b)-(x_1·w+b)\\ =&0 \end {aligned} ===(x2−x1)⋅wx2⋅w+b−b−x1⋅w(x2⋅w+b)−(x1⋅w+b)0
由此知道 w w w是超平面的法向量。
當然 w w w與 b b b并非我們自己可以直接按照喜好而定，它來源于資料，我們是通過已知資料，來得出最好的 w , b w,b w,b參數，使得由參數确定出的超平面能夠很好地劃分這些輸入，找到 w , b w,b w,b就是感覺機學習要做的。
感覺機學習政策
資料集T={( x 1 , y 1 x_1,y_1 x1,y1),( x 2 , y 2 x_2,y_2 x2,y2),···,( x N , y N x_N,y_N xN,yN)}，并且假定這個資料集是線性可分的
上面的前提中提到了線性可分，用下面的圖稍作解釋：
( x i , y i ) (x_i,y_i) (xi,yi)就是上面的一個點 y i y_i yi代表着這個資料的真實标記， y i = + 1 → y_i=+1\rightarrow yi=+1→o & y i = − 1 → \&\ y_i=-1\rightarrow & yi=−1→x，可見圖1中用一條直線可以完全分開所有資料，那麼圖1中的資料集就是線性可分的，而圖2中無論是紅線還是藍線都無法完全分開兩種類别，那麼圖2的資料就是線性不可分的，用線性可分的資料集就表明完美的超平面即 w ⋅ x + b = 0 w·x+b=0 w⋅x+b=0是存在的，我們有可能可以找到它。
我們感覺機學習的目标就是要找出一個能将訓練集正負執行個體點完全分開的超平面，而前面的假設前提(線性可分)已經為此奠定了基礎。找到這樣一個超平面其實就是找到理想的 w , b w,b w,b參數，為此需要确定一個學習政策，即定義損失函數并将損失函數最小化。
我們選擇誤分類點到超平面的總距離作為損失函數，也就是下圖綠色線條代表距離的總和：
那麼如何表示呢？我們首先就是要明确一個點到超平面的距離，有了這個距離總和就是很簡單能求到的了。
那麼首先假定空間裡任意一點為 x 0 x_0 x0，該點在超平面上的投影是 x 1 x_1 x1(投影就是過 x 1 x_1 x1做一條垂直于超平面的線，該線與超平面的交點就是這個 x 0 x_0 x0)，是以 x 1 x 0 ⃗ = x 0 − x 1 \vec{x_1x_0}=x_0-x_1 x1x0
=x0−x1與 w w w是平行的向量，可以有以下推導：
∣ ∣ w ⋅ x 1 x 0 ⃗ ∣ ∣ = ∣ w ⋅ ( x 0 − x 1 ) ∣ = ∣ w x 0 + b − w x 1 − b ∣ = ∣ w x 0 + b ∣ = ∣ ∣ w ∣ ∣ ⋅ ∣ ∣ x 1 x 0 ⃗ ∣ ∣ 兩 線 平 行 , ∣ ∣ x 1 x 0 ⃗ ∣ ∣ 為 向 量 長 度 d ， 就 是 點 到 超 平 面 距 離 = ∣ ∣ w ∣ ∣ ⋅ d ∣ ∣ w ∣ ∣ ⋅ d = ∣ ∣ w x 0 + b ∣ ∣ ⇒ d = 1 ∣ ∣ w ∣ ∣ ∣ w x 0 + b ∣ \begin {aligned} &||w·\vec{x_1x_0}||=|w·(x_0-x_1)|=|wx_0+b-wx_1-b|=|wx_0+b|\\ =&||w||·||\vec{x_1x_0}|| \ \ \ \ 兩線平行,||\vec{x_1x_0}||為向量長度d，就是點到超平面距離\\ =&||w||·d \end {aligned}\\ \begin{aligned} &||w||·d=||wx_0+b||\\ \Rightarrow\ &d = \frac{1}{||w||}|wx_0+b| \end{aligned} ==∣∣w⋅x1x0
∣∣=∣w⋅(x0−x1)∣=∣wx0+b−wx1−b∣=∣wx0+b∣∣∣w∣∣⋅∣∣x1x0
∣∣ 兩線平行,∣∣x1x0
∣∣為向量長度d，就是點到超平面距離∣∣w∣∣⋅d⇒ ∣∣w∣∣⋅d=∣∣wx0+b∣∣d=∣∣w∣∣1∣wx0+b∣
帶着絕對值的式子在很多時候都不好用，我們知道對于誤分類點他的标簽 y y y與我們判定的公式 w x + b wx+b wx+b是異号的，是以 − y i ( w x i + b ) > 0 -y_i(wx_i+b)>0 −yi(wxi+b)>0于是我們用這個式子取代絕對值：
d = − 1 ∣ ∣ w ∣ ∣ y i ( w x i + b ) d = -\frac{1}{||w||}y_i(wx_i+b) d=−∣∣w∣∣1yi(wxi+b)
誤分類點的集合為 M M M，那麼總的誤分類點距離為：
− 1 ∣ ∣ w ∣ ∣ ∑ x i ∈ M y i ( w ⋅ x i + b ) （ 3 ） -\frac{1}{||w||}\sum_{x_i\in M}y_i(w·x_i+b) （3） −∣∣w∣∣1xi∈M∑yi(w⋅xi+b)（3）
損失函數我們希望再簡化，因而去掉 1 ∣ ∣ w ∣ ∣ \frac{1}{||w||} ∣∣w∣∣1，最終損失函數為：
L ( w , b ) = − ∑ x i ∈ M y i ( w ⋅ x i + b ) （ 4 ） L(w,b)=-\sum_{x_i\in M}y_i(w·x_i+b)（4） L(w,b)=−xi∈M∑yi(w⋅xi+b)（4）
至于為什麼去掉 1 ∣ ∣ w ∣ ∣ \frac{1}{||w||} ∣∣w∣∣1綜合一下網上的意見然後給出點我自己的看法：
-
式(3)與式(4)的損失函數都具有相同的最小值：
根據政策，我們所要做的就是将損失函數極小化，而兩個式子很容易知道他們的最小值都是0，也就是說在去掉 1 ∣ ∣ w ∣ ∣ \frac{1}{||w||} ∣∣w∣∣1得到式(4)後依然能達到政策對于未去掉 1 ∣ ∣ w ∣ ∣ \frac{1}{||w||} ∣∣w∣∣1的要求；
-
式(3)與式(4)具有相同的極小化政策：
損失函數極小化的過程是随機梯度下降法，它使用每次選擇一個點來對w,b進行優化，盡管這種局部極小化可能會出現在優化一個點的時候另一個點的損失函數會增大，但是經過後面要提到的算法收斂檢驗發現經過這樣的有限次疊代後會找到一個完美超平面，也就是說有限次疊代後終将會優化到所有誤分類點的損失函數都為0，即不存在誤分類點，那麼這也就表明局部最小化也能帶來所有誤分類點的損失函數為0的結果，而這樣的結果不會因為一個 1 ∣ ∣ w ∣ ∣ \frac{1}{||w||} ∣∣w∣∣1而被影響
綜上可見，去掉 1 ∣ ∣ w ∣ ∣ \frac{1}{||w||} ∣∣w∣∣1後其實得到的結果是沒變的，是以簡化運算，最終損失函數定為：
L ( w , b ) = − ∑ x i ∈ M y i ( w ⋅ x i + b ) L(w,b)=-\sum_{x_i\in M}y_i(w·x_i+b) L(w,b)=−xi∈M∑yi(w⋅xi+b)
感覺機學習算法
開始說算法前，我覺得有必要了解一下随機梯度下降法，如果已經了解可以直接跳到感覺機學習算法的原始形式。
形象一點說這個方法就類似于處于山頂上的人如何走向最低處，理想的想法就是四處探看找到下降最快的方向邁出一步，不斷探看不斷邁出，最終會到達山底。而這個下降最快的方向就是梯度的反方向。那麼類比到損失函數中，損失函數最初的值就相當于處在山頂的位置，而通過計算梯度就能找到下降最快的方向，更新參數 w , b w,b w,b就像是在邁出步子走向山底，不斷重複，我們就找到最小值。
但是我們的損失函數計算的樣本點是來自于誤分類的點，我們沒辦法從全局進行梯度下降，是以選擇随機梯度下降法，也就是每次計算單個誤分類樣本點的梯度然後對參數 w , b w,b w,b進行優化，通過後面的收斂證明發現對于感覺機，随機梯度下降法是能找到完美超平面的。
但是這裡還有一個問題，那就是為什麼梯度的反方向是函數下降最快的方向呢：
下圖表示一個輸入空間，可見這個輸入的變量是個二維的向量，有屬性 x , y x,y x,y(屬性雖然用 x ( 1 ) , x ( 2 ) x^{(1)},x^{(2)} x(1),x(2)表示更好，但是現在這裡講的大多相關于高數的知識，用xy更熟悉一些，但這個y要與标簽區分開喲)
首先假設我們有一個函數 z = f ( x , y ) z=f(x,y) z=f(x,y)并且存在一條藍色的線它與 x x x軸的夾角為 α \alpha α，它在這個二維的空間裡就表示着一個方向。我們現在要做的就是求函數 z = f ( x , y ) z=f(x,y) z=f(x,y)在藍線方向上的方向導數。
方向導數，其實描述的也就是在某個方向上函數的變化率，如圖我們得到一個初始點為 ( x 0 , y 0 ) (x_0,y_0) (x0,y0)，在藍線上變化 ρ \rho ρ的長度，達到點 ( y 0 + △ y , x 0 + △ x ) (y_0+\bigtriangleup y,\ x_0+\bigtriangleup x) (y0+△y, x0+△x)，可見在 x x x軸與 y y y軸上的變化分别是 △ x \bigtriangleup x △x與 △ y \bigtriangleup y △y，根據導數的定義我們可以寫出 z z z在 x x x方向上的偏導：
lim △ x → 0 f ( x 0 + △ x , y 0 ) − f ( x 0 , y 0 ) △ x = ∂ z ∂ x \lim_{\bigtriangleup x\rightarrow0}\frac{f(x_0+\bigtriangleup x,y_0)-f(x_0,y_0)}{\bigtriangleup x}=\frac{\partial z}{\partial x} △x→0lim△xf(x0+△x,y0)−f(x0,y0)=∂x∂z
将左邊的分母乘到右邊得到：
lim △ x → 0 f ( x 0 + △ x , y 0 ) − f ( x 0 , y 0 ) = ∂ z ∂ x △ x （ 7 ） \lim_{\bigtriangleup x\rightarrow0}f(x_0+\bigtriangleup x,y_0)-f(x_0,y_0)=\frac{\partial z}{\partial x}\bigtriangleup x（7） △x→0limf(x0+△x,y0)−f(x0,y0)=∂x∂z△x（7）
若此時以 ( x 0 + △ x , y 0 ) (x_0+\bigtriangleup x,y_0) (x0+△x,y0)為起點，同上根據 z z z在 y y y方向上的偏導可以寫出：
lim △ y → 0 f ( x 0 + △ x , y 0 + △ y ) − f ( x 0 + △ x , y 0 ) = ∂ z ∂ y △ y （ 8 ） \lim_{\bigtriangleup y\rightarrow0}f(x_0+\bigtriangleup x,y_0+\bigtriangleup y)-f(x_0+\bigtriangleup x,y_0)=\frac{\partial z}{\partial y}\bigtriangleup y（8） △y→0limf(x0+△x,y0+△y)−f(x0+△x,y0)=∂y∂z△y（8）
把式(7)與式(8)相加能得到：
lim △ x → 0 lim △ y → 0 f ( x 0 + △ x , y 0 + △ y ) − f ( x 0 , y 0 ) = ∂ z ∂ x △ x + ∂ z ∂ y △ y \lim_{\bigtriangleup x\rightarrow0}\lim_{\bigtriangleup y\rightarrow0} f(x_0+\bigtriangleup x,y_0+\bigtriangleup y)-f(x_0,y_0) =\frac{\partial z}{\partial x}\bigtriangleup x +\frac{\partial z}{\partial y}\bigtriangleup y △x→0lim△y→0limf(x0+△x,y0+△y)−f(x0,y0)=∂x∂z△x+∂y∂z△y
△ x → 0 \bigtriangleup x\rightarrow0 △x→0與 △ y → 0 \bigtriangleup y\rightarrow0 △y→0等價于 ρ → 0 \rho\rightarrow0 ρ→0，然後将上式兩邊同時除以 ρ \rho ρ得到：
lim ρ → 0 f ( x 0 + △ x , y 0 + △ y ) − f ( x 0 , y 0 ) ρ = ∂ z ∂ x △ x ρ + ∂ z ∂ y △ y ρ \lim_{\rho\rightarrow0}\frac{ f(x_0+\bigtriangleup x,y_0+\bigtriangleup y)-f(x_0,y_0) }{\rho}=\frac{\partial z}{\partial x}\frac{\bigtriangleup x}{\rho} +\frac{\partial z}{\partial y}\frac{\bigtriangleup y}{\rho} ρ→0limρf(x0+△x,y0+△y)−f(x0,y0)=∂x∂zρ△x+∂y∂zρ△y
再化簡可得：
lim ρ → 0 f ( x 0 + △ x , y 0 + △ y ) − f ( x 0 , y 0 ) ρ = ∂ z ∂ x c o s α + ∂ z ∂ y s i n α \lim_{\rho\rightarrow0}\frac{ f(x_0+\bigtriangleup x,y_0+\bigtriangleup y)-f(x_0,y_0) }{\rho}=\frac{\partial z}{\partial x}cos\alpha +\frac{\partial z}{\partial y}sin\alpha ρ→0limρf(x0+△x,y0+△y)−f(x0,y0)=∂x∂zcosα+∂y∂zsinα
上式的左邊就是在藍線上的方向導數，根據式子的右邊設 G = ( ∂ z ∂ x , ∂ z ∂ y ) , I = ( c o s α , s i n α ) G = (\frac{\partial z}{\partial x},\frac{\partial z}{\partial y}),\ I=(cos\alpha,sin\alpha) G=(∂x∂z,∂y∂z), I=(cosα,sinα)， G G G就是梯度， I I I是方向導數的方向，是個機關向量，這個方向在圖裡就是那條藍線，我們現在就是要找到一個 I I I的方向使得在這個點 ( x 0 , y 0 ) (x_0,y_0) (x0,y0)處沿此方向有最大的變化，那麼再寫一下：
方 向 導 數 = G ⋅ I = ∣ G ∣ ⋅ ∣ I ∣ c o s θ 方向導數 = G · I=|G|·|I|cos\theta 方向導數=G⋅I=∣G∣⋅∣I∣cosθ
θ \theta θ就是 G G G與 I I I的之間的夾角，那麼可見當 G G G與 I I I同向時，即 θ \theta θ為0方向導數最大為正，可知 G G G的方向就是在該點函數增大最快的方向，那麼 θ \theta θ為 π \pi π，即與 G G G的方向相反，此時在該點沿該方向函數下降最快。
感覺機學習算法的原始形式
有了上面的了解，我們其實就已經知道了這個學習算法最重要的一步，那就是對于參數的更新。按照前面所說， w , b w,b w,b應該向着梯度的反方向更新。
在個誤分點對參數更新，首先寫出損失函數：
L ( w , b ) = − y i ( w ⋅ x i + b ) L(w,b)=-y_i(w·x_i+b) L(w,b)=−yi(w⋅xi+b)
對參數求導得到梯度：
▽ w L ( w , b ) = − y i x i ▽ b L ( w , b ) = − y i \begin{aligned} \triangledown_wL(w,b) &= -y_ix_i\\ \\ \triangledown_bL(w,b) &= -y_i \end{aligned} ▽wL(w,b)▽bL(w,b)=−yixi=−yi
要知道 w w w不是一個數而是一個向量，每一個 w w w的分量對 L L L求導，其偏導數組成了梯度向量 y i x i y_ix_i yixi，其實對這個損失函數而言其梯度應該将上面這兩個式子的結果寫到一起，但是為了友善更新參數，結果我們分開看。
我們以 η \eta η作為步長對參數 w , b w,b w,b更新，然後沿梯度相反方向移動 η \eta η，在式子中就表示為 參 數 − 梯 度 參數-梯度 參數−梯度:
w ← w + η y i x i b ← b + η y i \begin{aligned} &w\leftarrow w+ \eta \ y_ix_i\\ \\ &b\leftarrow b\ +\eta\ y_i \end{aligned} w←w+η yixib←b +η yi
那麼總的算法流程就如下：
(1) 選取初值 w 0 , b 0 w_0,b_0 w0,b0
(2) 在訓練集中周遊選取資料 ( x i , y i ) (x_i,y_i) (xi,yi)，這裡的 ( x i , y i ) (x_i,y_i) (xi,yi)不一定代表誤分類的點
(3) 如果 y i ( w ⋅ x i + b ) ≤ 0 y_i(w·x_i+b)\le 0 yi(w⋅xi+b)≤0：
w ← w + η y i x i b ← b + η y i \begin{aligned} &w\leftarrow w+ \eta \ y_ix_i\\ &b\leftarrow b\ +\eta\ y_i \end{aligned} w←w+η yixib←b +η yi
這一步就是判斷(2)得到的點是否是誤分類點，然後如果是那麼就對其更新
(4) 否則轉至(2)直到訓練集中沒有誤分類點
算法收斂性
雖然我們知道單個點損失函數存在最小值為0，但是由單個點對 w , b w,b w,b進行更新，損失函數最小化是局部下降的，也就是說在對某個點梯度下降時，可能會新增其他誤分類點，或者其他點的損失函數增大。那麼存在這個點更新後損失函數減小但同時另一個點損失函數又增大的情況，是以現在證明即使存在這種情況我們的算法還是收斂的，我們還是能得到最終完美的超平面。
- 為了友善推導把 b b b并入 w , x w,x w,x中， b = b ⋅ 1 b=b·1 b=b⋅1， b b b并在 w w w的最後一個， 1 1 1并在 x x x的最後一個，寫成 w ^ = ( w T , b ) , x ^ = ( x T , 1 ) \hat{w}=(w^T,b),\ \hat{x}=(x^T,1) w^=(wT,b), x^=(xT,1)
- 假設存在滿足條件 ∣ ∣ w ^ o p t ∣ ∣ = 1 ||\hat{w}_{opt}||=1 ∣∣w^opt∣∣=1的超平面将所有的資料全部完全分開
- 設 R = max 1 ≤ i ≤ N ∣ ∣ x ^ i ∣ ∣ R=\max_{1\le i\le N}||\hat{x}_i|| R=max1≤i≤N∣∣x^i∣∣
證明：
我們知道完美超平面是能将所有資料正确分開，即沒有誤分類點，标簽 y i y_i yi與輸出 f ( x i ) f(x_i) f(xi)是同号的，那麼也就是說 w o p t , b o p t w_{opt},b_{opt} wopt,bopt對于所有的訓練集資料滿足下面的式子
y i ( w ^ o p t ⋅ x ^ i ) = y i ( w o p t ⋅ x i + b o p t ) > 0 \begin{aligned} y_i(\hat{w}_{opt}·\hat{x}_i)=y_i(w_{opt}·x_i+b_{opt})>0 \end{aligned} yi(w^opt⋅x^i)=yi(wopt⋅xi+bopt)>0
是以存在：
γ = min i { y i ( w o p t ⋅ x i + b o p t ) } γ > 0 \gamma = \min_i\{y_i(w_{opt}·x_i+b_{opt})\} \\ \gamma>0 γ=imin{yi(wopt⋅xi+bopt)}γ>0
使得：
y i ( w ^ o p t ⋅ x ^ i ) = y i ( w o p t ⋅ x i + b o p t ) ≥ γ （ 15 ） y_i(\hat{w}_{opt}·\hat{x}_i)=y_i(w_{opt}·x_i+b_{opt})\ge\gamma（15） yi(w^opt⋅x^i)=yi(wopt⋅xi+bopt)≥γ（15）
最初始的超平面是 w 0 = 0 , b 0 = 0 w_0=0,b_0=0 w0=0,b0=0那麼更新參數 k k k次後得到的超平面就是 w k , b k w_k,b_k wk,bk，我們知道：
w k ← w k − 1 + η y i x i b k ← b k − 1 + η y i \begin{aligned} &w_k\leftarrow w_{k-1}+ \eta \ y_ix_i\\ &b_k\leftarrow b_{k-1}\ +\eta\ y_i \end{aligned} wk←wk−1+η yixibk←bk−1 +η yi
則會有：
w ^ k = w ^ k − 1 + η y i x ^ i \hat{w}_{k} = \hat{w}_{k-1}+\eta \ y_i\hat{x}_i w^k=w^k−1+η yix^i
(别忘了 w ^ , x ^ \hat{w},\hat{x} w^,x^的含義)
于是可以得到式子：
w ^ k ⋅ w ^ o p t = ( w ^ k − 1 + η y i x ^ i ) w ^ o p t = w ^ k − 1 ⋅ w ^ o p t + η y i x ^ i w ^ o p t \begin{aligned} \hat{w}_k·\hat{w}_{opt} &=(\hat{w}_{k-1}+\eta\ y_i\hat{x}_i)\hat{w}_{opt}\\ &=\hat{w}_{k-1}·\hat{w}_{opt}+\eta\ y_i\hat{x}_i\hat{w}_{opt} \end{aligned} w^k⋅w^opt=(w^k−1+η yix^i)w^opt=w^k−1⋅w^opt+η yix^iw^opt
将式(15)代入上面的式子中：
w ^ k ⋅ w ^ o p t = ( w ^ k − 1 + η y i x ^ i ) w ^ o p t = w ^ k − 1 ⋅ w ^ o p t + η y i x ^ i w ^ o p t ≥ w ^ k − 1 ⋅ w ^ o p t + η γ \begin{aligned} \hat{w}_k·\hat{w}_{opt} &=(\hat{w}_{k-1}+\eta\ y_i\hat{x}_i)\hat{w}_{opt}\\ &=\hat{w}_{k-1}·\hat{w}_{opt}+\eta\ y_i\hat{x}_i\hat{w}_{opt}\\ &\ge \hat{w}_{k-1}·\hat{w}_{opt}+\eta\ \gamma \end{aligned} w^k⋅w^opt=(w^k−1+η yix^i)w^opt=w^k−1⋅w^opt+η yix^iw^opt≥w^k−1⋅w^opt+η γ
對于上面的式子我們依然可以求得帶有 w ^ k − 2 ⋅ w ^ o p t \hat{w}_{k-2}·\hat{w}_{opt} w^k−2⋅w^opt的不等式：
w ^ k ⋅ w ^ o p t ≥ w ^ k − 1 ⋅ w ^ o p t + η γ ≥ w ^ k − 2 ⋅ w ^ o p t + 2 η γ \begin{aligned} \hat{w}_k·\hat{w}_{opt} &\ge \hat{w}_{k-1}·\hat{w}_{opt}+\eta\ \gamma\\ &\ge \hat{w}_{k-2}·\hat{w}_{opt}+2\eta\ \gamma \end{aligned} w^k⋅w^opt≥w^k−1⋅w^opt+η γ≥w^k−2⋅w^opt+2η γ
不斷向下類推:
w ^ k ⋅ w ^ o p t ≥ w ^ k − 1 ⋅ w ^ o p t + η γ ≥ w ^ k − 2 ⋅ w ^ o p t + 2 η γ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ≥ w ^ 2 ⋅ w ^ o p t + ( k − 2 ) η γ ≥ w ^ 1 ⋅ w ^ o p t + ( k − 1 ) η γ ≥ w ^ 0 ⋅ w ^ o p t + ( k − 0 ) η γ \begin{aligned} \hat{w}_k·\hat{w}_{opt} &\ge \hat{w}_{k-1}·\hat{w}_{opt}+\eta\ \gamma\\ &\ge \hat{w}_{k-2}·\hat{w}_{opt}+2\eta\ \gamma\\ &······\\ &\ge \hat{w}_{2}·\hat{w}_{opt}+(k-2)\eta\ \gamma\\ &\ge \hat{w}_{1}·\hat{w}_{opt}+(k-1)\eta\ \gamma\\ &\ge \hat{w}_{0}·\hat{w}_{opt}+(k-0)\eta\ \gamma\\ \end{aligned} w^k⋅w^opt≥w^k−1⋅w^opt+η γ≥w^k−2⋅w^opt+2η γ⋅⋅⋅⋅⋅⋅≥w^2⋅w^opt+(k−2)η γ≥w^1⋅w^opt+(k−1)η γ≥w^0⋅w^opt+(k−0)η γ
初始超平面前面說過，定為 w ^ 0 = 0 \hat{w}_0=0 w^0=0，是以a上式表示為：
w ^ k ⋅ w ^ o p t ≥ k η γ （ 17 ） \hat{w}_k·\hat{w}_{opt}\ge k\eta\ \gamma（17） w^k⋅w^opt≥kη γ（17）
對于 w ^ k \hat{w}_k w^k有：
∣ ∣ w ^ k ∣ ∣ 2 = ∣ ∣ w ^ k − 1 + η y i x ^ i ∣ ∣ 2 = ∣ ∣ w ^ k − 1 ∣ ∣ 2 + ∣ ∣ η y i x ^ i ∣ ∣ 2 + 2 η y i w ^ k − 1 x ^ i \begin{aligned} ||\hat{w}_k||^2&=||\hat{w}_{k-1}+\eta\ y_i\hat{x}_i||^2\\ &=||\hat{w}_{k-1}||^2+||\eta\ y_i\hat{x}_i||^2+2\eta\ y_i\hat{w}_{k-1}\hat{x}_i \end{aligned} ∣∣w^k∣∣2=∣∣w^k−1+η yix^i∣∣2=∣∣w^k−1∣∣2+∣∣η yix^i∣∣2+2η yiw^k−1x^i
第二個等号後的式子尾項，因為上式中的 y i , x ^ i y_i,\hat{x}_i yi,x^i是誤分類點，是以 y i , w ^ k x ^ i y_i,\hat{w}_k\hat{x}_i yi,w^kx^i是異号的，是以是一個負數，中間的 ∣ ∣ η y i x ^ i ∣ ∣ 2 ||\eta\ y_i\hat{x}_i||^2 ∣∣η yix^i∣∣2由于 y i y_i yi在平方下沒有實際的影響，是以不用管他，而 R = max 1 ≤ i ≤ N ∣ ∣ x ^ i ∣ ∣ R=\max_{1\le i\le N}||\hat{x}_i|| R=max1≤i≤N∣∣x^i∣∣，是以有：
∣ ∣ w ^ k ∣ ∣ 2 ≤ ∣ ∣ w ^ k − 1 ∣ ∣ 2 + η 2 ∣ ∣ x ^ i ∣ ∣ 2 ≤ ∣ ∣ w ^ k − 1 ∣ ∣ 2 + η 2 R 2 ≤ ∣ ∣ w ^ k − 2 ∣ ∣ 2 + 2 η 2 R 2 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ≤ ∣ ∣ w ^ 2 ∣ ∣ 2 + ( k − 2 ) η 2 R 2 ≤ ∣ ∣ w ^ 1 ∣ ∣ 2 + ( k − 1 ) η 2 R 2 ≤ ∣ ∣ w ^ 0 ∣ ∣ 2 + k η 2 R 2 ≤ k η R 2 \begin{aligned} ||\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\\ &\le ||\hat{w}_{k-2}||^2+2\eta^2\ R^2\\ &······\\ &\le ||\hat{w}_{2}||^2+(k-2)\eta^2\ R^2\\ &\le ||\hat{w}_{1}||^2+(k-1)\eta^2\ R^2\\ &\le ||\hat{w}_{0}||^2+k\eta^2\ R^2\\ &\le k\eta\ R^2\\ \end{aligned} ∣∣w^k∣∣2≤∣∣w^k−1∣∣2+η2 ∣∣x^i∣∣2≤∣∣w^k−1∣∣2+η2 R2≤∣∣w^k−2∣∣2+2η2 R2⋅⋅⋅⋅⋅⋅≤∣∣w^2∣∣2+(k−2)η2 R2≤∣∣w^1∣∣2+(k−1)η2 R2≤∣∣w^0∣∣2+kη2 R2≤kη R2
得到：
∣ ∣ w ^ k ∣ ∣ 2 ≤ k η R 2 ||\hat{w}_k||^2\le k\eta\ R^2 ∣∣w^k∣∣2≤kη R2
式(17)可寫成：
k η γ ≤ w ^ k ⋅ w ^ o p t k\eta\ \gamma \le \hat{w}_k·\hat{w}_{opt} kη γ≤w^k⋅w^opt
由于向量積小于等于向量模的積( a ⋅ b = ∣ ∣ a ∣ ∣ ⋅ ∣ ∣ b ∣ ∣ c o s α a·b=||a||·||b||cos\alpha a⋅b=∣∣a∣∣⋅∣∣b∣∣cosα)，是以：
k η γ ≤ w ^ k ⋅ w ^ o p t ≤ ∣ ∣ w ^ k ∣ ∣ ⋅ ∣ ∣ w ^ o p t ∣ ∣ k\eta\ \gamma \le \hat{w}_k·\hat{w}_{opt}\le||\hat{w}_k||·||\hat{w}_{opt}|| kη γ≤w^k⋅w^opt≤∣∣w^k∣∣⋅∣∣w^opt∣∣
由于 ∣ ∣ w ^ o p t ∣ ∣ = 1 ||\hat{w}_{opt}||=1 ∣∣w^opt∣∣=1而 ∣ ∣ w ^ k ∣ ∣ ≤ k η R ||\hat{w}_{k}||\le \sqrt{k}\eta\ R ∣∣w^k∣∣≤k
η R，是以：
k η γ ≤ w ^ k ⋅ w ^ o p t ≤ ∣ ∣ w ^ k ∣ ∣ ⋅ ∣ ∣ w ^ o p t ∣ ∣ ≤ k η R ⇓ k ≤ R 2 γ 2 k\eta\ \gamma \le \hat{w}_k·\hat{w}_{opt}\le||\hat{w}_k||·||\hat{w}_{opt}||\le \sqrt{k}\eta\ R\\ \Downarrow\\ k\le \frac{R^2}{\gamma^2} kη γ≤w^k⋅w^opt≤∣∣w^k∣∣⋅∣∣w^opt∣∣≤k
η R⇓k≤γ2R2
R R R與 γ \gamma γ都是一個有限的值，因而 k k k是存在上界的，這就說明隻要存在完美的超平面那麼參數更新的次數 k k k必然是有限的，也就是在有限次更新後必然能找到這個完美的超平面。
感覺機學習算法的對偶形式
由前面的内容，可以知道，目前的參數 w , b w,b w,b來自于誤分類點的更新，即：
w ← w + η y i x i b ← b + η y i \begin{aligned} &w\leftarrow w+ \eta \ y_ix_i\\ &b\leftarrow b\ +\eta\ y_i \end{aligned} w←w+η yixib←b +η yi
那麼如果某個誤分類點 ( x i , y i ) (x_i,y_i) (xi,yi)多次被選中，那麼它對目前參數就進行了 n n n次更新，它更新帶來的影響是使 w , b w,b w,b改變如下：
△ w = n η y i x i △ b = n η y i \begin{aligned} &\triangle_w = n\eta\ y_ix_i\\ &\triangle_b = n\eta\ y_i \end{aligned} △w=nη yixi△b=nη yi
更新過程中被選中的每一個誤分類點都可以如上被表示，将他們全部加起來，就可以表示由初始的 w 0 , b 0 w_0,b_0 w0,b0到目前的 w , b w,b w,b之間的總變化程度。而為了不失一般性，初始值 w 0 , b 0 w_0,b_0 w0,b0均設為0，那麼有：
w = w 0 + n 1 η y 1 x 1 + n 2 η y 2 x 2 + ⋅ ⋅ ⋅ + n i η y i x i w=w_0 + n_1\eta\ y_1x_1+n_2\eta\ y_2x_2+···+n_i\eta\ y_ix_i w=w0+n1η y1x1+n2η y2x2+⋅⋅⋅+niη yixi
上面的式子包含了訓練集所有的點，如果某個點從來沒有被選中去更新參數，那麼它前面的 n n n自然等于0。我們把上式中的 n i η n_i\eta niη改寫為 α i \alpha_i αi，而 w 0 = 0 w_0=0 w0=0，那麼上面的式子可以寫為：
w = ∑ i = 1 N α i y i x i w=\sum_{i=1}^N\alpha_iy_ix_i w=i=1∑Nαiyixi
同理得b為：
b = ∑ i = 1 N α i y i b = \sum_{i=1}^N\alpha_iy_i b=i=1∑Nαiyi
于是可以将感覺機模型改寫為 f ( x ) = s i g n ( ∑ j = 1 N α j y j x j ⋅ x + b ) f(x)=sign(\sum_{j=1}^N\alpha_jy_jx_j·x+b) f(x)=sign(∑j=1Nαjyjxj⋅x+b)
那麼對偶形式的算法其實和原始形式很像：
(1) 選取初值 α = 0 , b = 0 \alpha=0,b=0 α=0,b=0
(2) 在訓練集中周遊選取資料 ( x i , y i ) (x_i,y_i) (xi,yi)，這裡的 ( x i , y i ) (x_i,y_i) (xi,yi)不一定代表誤分類的點
(3) 如果 y i ( ∑ j = 1 N α j y j x j ⋅ x + b ) ≤ 0 y_i(\sum_{j=1}^N\alpha_jy_jx_j·x+b)\le 0 yi(∑j=1Nαjyjxj⋅x+b)≤0：
α i ← α i + η b ← b + η y i \begin{aligned} &\alpha_i\leftarrow \alpha_i+ \eta\\ &b\leftarrow b\ +\eta\ y_i \end{aligned} αi←αi+ηb←b +η yi
這一步就是判斷(2)得到的點是否是誤分類點，然後如果是那麼就對其更新
(4) 否則轉至(2)直到訓練集中沒有誤分類點