一，感覺機模型
1，超平面的定義
令w1，w2，...wn，v都是實數(R) ，其中至少有一個wi不為零，由所有滿足線性方程w1*x1+w2*x2+...+wn*xn=v
的點X=[x1,x2,...xn]組成的集合，稱為空間R的超平面。
從定義可以看出：超平面就是點的集合。集合中的某一點X，與向量w=[w1，w2，...wn]的内積，等于v
特殊地，如果令v等于0，對于訓練集中某個點X：
w*X=w1*x1+w2*x2+...+wn*xn>0，将X标記為一類
w*X=w1*x1+w2*x2+...+wn*xn<0，将X标記為另一類
2，資料集的線性可分
對于資料集T={(X1, y1),(X2, y2)...(XN, yN)}，Xi belongs to Rn，yi belongs to {-1, 1}，i=1,2,...N
若存在某個超平面S：w*X=0
将資料集中的所有樣本點正确地分類，則稱資料集T線性可分。
所謂正确地分類，就是：如果w*Xi>0，那麼樣本點(Xi, yi)中的 yi 等于1
如果w*Xi<0，那麼樣本點(Xi, yi)中的 yi 等于-1
是以，給定超平面 w*X=0，對于資料集 T中任何一個點(Xi, yi)，都有yi(w*Xi)>0，這樣T中所有的樣本點都被正确地分類了。
如果有某個點(Xi, yi)，使得yi(w*Xi)<0，則稱超平面w*X對該點分類失敗，這個點就是一個誤分類的點。
3，感覺機模型
感覺機模型，對應着一個超平面w*X+b=0，這個超平面的參數是(w,b)，w是超平面的法向量，b是超平面的截距。
我們的目标是，找到一個(w,b)，能夠将線性可分的資料集T中的所有的樣本點正确地分成兩類。
如何找到(w,b)？---感覺機學習算法做的事
二，感覺機學習算法
既然我們的目标是将T中所有的樣本點正确地分類，那麼對于某個(w,b)，先看一下它在哪些點上分類失敗了。由前面所述：
如果有某個點(Xi, yi)，使得yi(w*Xi)<0，則稱超平面w*X對該點分類失敗。采用所有誤分類的點到超平面的距離來衡量分類失敗的程度。
n維空間Rn中一點Xi到超平面w*X+b=0的距離公式：
對于誤分類的點，有yi(w*Xi)<0。而距離總是大于0的，是以，某個誤分類的點到超平面的距離表示為：
||w||是一個常數，對最小化L(w,b)沒有影響，故忽略之。
假設所有的誤分類點都在集合M中，得到的損失函數如下：
最終，将尋找(w,b)問題轉化為最小化損失函數，即轉化為一個最優化問題。（損失函數越小，說明誤分類的樣本點“越少”---或者說分類失敗的程度越低）
而這個優化問題可以用梯度下降法來尋找最優的(w,b)
minL(w,b)沒有 analytical solution，我的了解是：不能通過數學公式各種推導，最終求得一個關于最優的w 和 b 的解。比如，Stanford CS229課程中cs229-notes1.pdf 中求解 linear regression 的代價函數J(θ)的參數θ，可以使用Normal Equation 方法：直接根據公式得到θ
上面說的second way of doing so. second way就是Normal Equation方法
梯度下降，則是一種疊代算法，使用不斷疊代(w,b)的方式，使得L(w,b)變得越來越小。
另外一個原因是（不知道對不對）：在《機器學習基石》視訊中講到NP-Hard問題。
x
梯度方向是函數L(w,b)增加最快的方向，而現在要最小化L(w,b)，在目前的(w,b)點，從梯度的負方向搜尋下一個(w,b)點，那麼找到的(w,b)就是使L(w,b)減少的最快的方向上的那個點(還與搜尋的步長有關)了。
現在證明為什麼梯度方向是函數f(x)增加最快的方向，這裡涉及到幾個概念：
①梯度
梯度是個向量，由于x=[x1,x2,...xn]是n維的，梯度就是對x的各個分量xi求偏導數：
②增加的方向---方向導數
給定一個函數f(x)，通俗地講方向導數就是決定 自變量x 可以往哪個方向移動。比如在f(x)邊界上，x往某個方向移動時，就不在定義域的範圍内了，那x是不能往該方向變化的。假設 d 是f(x)的一個可行方向，||d||=1，那麼函數f 的值在 x 處 沿着方向d 的增長率increase_rate，可以用内積表示：
那麼現在，到底往哪個方向增長，能夠使 increase_rate 最大呢？也即，d取哪個方向，使 increase_rate 最大？
也就是說，increase_rate的最大值為：
而當 d =
時，根據内積的定義：
increase_rate等于：
此時，increase_rate取最大值，且可行方向d 就是梯度方向！
是以，若要最小化L(w,b)，往梯度的負方向搜尋(w,b)，能使L(w,b)下降得最快。
根據前面的介紹，梯度實際上是求偏導數，是以L(w,b)分别對w 和 b 求偏導數：
而在感覺機中是一次隻選擇一個誤分類點對(w,b)進行疊代更新，選擇梯度的負方向進行更新，故更新的公式如下所示：
三，感覺機學習算法的收斂性證明
由于資料集T是線性可分的，假設存在一個理想的超平面wopt，且||wopt||=1，wopt能夠将T中的所有樣本點正确地分類。
如前所述，若正确分類，則對于資料集 T中任何一個點(Xi, yi)，都有yi(w*Xi)>0
取r=min{yi(wopt*Xi)} ，并且令R=max||xi|| ，則疊代次數k滿足下列不等式：
具體證明過程見《統計學習方法》p32-p33頁
在證明過程中，推導出了兩個不等式，一個是：wk*wopt >= knr (k是疊代次數，n是疊代步長，r是min{yi(wopt*Xi))
超平面wopt是理想的超平面，能夠完美地将所有的樣本點正确地分開。wk是采用感覺機學習算法使用梯度下降不斷疊代求解的超平面，二者之間的内積，用來衡量這兩個超平面的接近程度。因為兩個向量的内積越大，說明這兩個向量越相似(接近),也就是說:不斷疊代後的wk越來越接近理想的超平面wopt了。（向量的模為1，||wopt||=1）
第二個不等式是：
結合上面的二個不等式，有：
其中第一個不等号成立是因為：wk*wopt >= knr
第二個不等号成立是因為：柯西-施瓦茲不等式
第三個不等号成立是因為：第二個不等式 和 ||wopt||=1
四，參考文獻
《統計學習方法》
《最優化導論》
本文轉自hapjin部落格園部落格，原文連結：http://www.cnblogs.com/hapjin/p/6714526.html，如需轉載請自行聯系原作者