本文純理論，來源于 Andrew Ng 公開課和李航的《統(tǒng)計學習方法》。Support Vector Machine 簡稱SVM，是一種二元(binary)線性分類，核心就是求出一個線性超平面完美的將測試數(shù)據(jù)分成兩類，正例和負例，如圖中直線就是一個超平面，X 代表正例，O 代表負例。如果測試數(shù)據(jù)落在A點，那么就有很大程度確信 A 屬于正例，對于落 在C點的數(shù)據(jù)就沒那么確信，B點介于A, C 之間。SVM的核心：以充分大的確信度對訓練數(shù)據(jù)進行劃分
有兩個概念比較煩:
- 支持向量: 支持或支撐平面上，把測試數(shù)據(jù)劃分兩類的點。也就是離超平面最近的正負例點，又因為這些點是 N 維的向量，所以這幾個有限點叫支持向量
- 超平面: 如果二維的，那么將測試數(shù)據(jù)分類的就是一條直線，如果是三維的就是一個平面，更高維的雖然無法直觀對應物理模型，但道理一樣的。統(tǒng)一稱為超平面(hyperplane)
回顧 Logistic Regression
Logistic 回歸無論二分，還是多元分類，都是使用 Sigmoid 函數(shù)將h(θ) 從負無窮到正無窮壓縮到(0,1)
hθ(x) =g(θTx)
其中g(z) 就是我們熟知的 Sigmoid 函數(shù) g(z)=1/(1+e^(-z))
可以看到 g(z) 將 θTx 從 (-∞, +∞) 映到到 (0,1), 從而將回歸問題轉換到概率問題，對于標記 y=1的概率
p{y=1|x,θ} = hθ(x)
對于標記 y=0的概率
p{y=0|x,θ} = 1-hθ(x)
當驗證數(shù)據(jù)大于0.5時，就劃分為y=1的類，否則標記為 y=0. 實際上拋開 Sigmoid 函數(shù)，θTx >0 那么 y=1, θTx < 0 判定 y=0
新的約定
SVM 會有些改變，將結果y標記由(0, 1) 替換為 {1, -1}, 同時將 θ 替換為 w 和b ,其中 θ, w 是向量，b是截距常數(shù)。
θTx= θ0 + θ1x1 + θ2x2 + ....
替換為
θTx= b + w1x1 + w2x2 + ....
將 intercept 從 θ 中剝離出來變成 b, 新的函數(shù)變成
hw,b(x) = g(w·x + b)
很好理解，實質是一樣的，但是為什么要做新的約定呢？后面會看到 y 值替換為 {1,-1} 可以創(chuàng)建一個拉格朗日約束，而 w, b 又是構造超平面的兩要素，w 是超平面的法向量，用于確定平面方向，而b是截距，用來確定滿足這個方向的唯一平面。
線性分類形象化表示
筆記開篇就是一個線性分類，下圖的也是，一個二維平面(超平面，二維空間中就是一條直線)，坐標內有兩類點，紅顏色和藍顏色，完全被紅顏色直線分隔。
我們定義這個紅顏色直線(超平面)為 w·x + b = 0, 也就是說分隔函數(shù)為 f(x) = w·x + b, 對于超平面上方的點有 f(x) >0,并且 y ＝1(人為標記成1)，對于下方的點 f(x) < 0, 并且 y = -1, 對于超平面上的點的 有 f(x) = 0.
函數(shù)間隔與幾何間隔
如何確定這樣的超平面呢？答案是讓支持向量到超平面的距離盡可能最大，這樣有更好的泛化能力。
函數(shù)間隔 functional margins
對于給定訓練數(shù)據(jù) (xi, yi), 我們定如下公式為函數(shù)間隔，其中 xi 是特征向量，yi 是我們標記的數(shù)據(jù) {1, -1}, 如果 xi 在超平面上方，那么 w·x + b > 0, yi =1 所以函數(shù)間隔大于0，同樣如果樣本 xi 位于下方，那么 w·x + b <0 , yi = -1, 函數(shù)間隔仍然大于0. 后面會用到這個約束。
對于給定訓練集，到超平面 w·x + b ＝0 的函數(shù)距離為所有點到超平面最小的距離
我們的目標就是尋找，使這個最小距離盡可能取最大值時的 w 和 b. 稍微有些繞 ... 但是函數(shù)間隔有個最大問題，會隨著 w, b 等比縮放。比如對于超平面 2w·x + 2b ＝0, 同樣滿足需求，但此時函數(shù)間隔也會放大 2 倍。所以我們要使用幾何間隔
幾何間隔 geometric margins
回想一下高中知識，求點 (x0,y0)到直線 ax + by + c = 0的距離公式，就是幾何間隔在二維的特殊形式
推廣到 N 維空間，點(x,y) 到超平面w·x + b ＝0的距離公式
由此可以看到幾何間隔就是函數(shù)間隔除以||w||, 即 w 向量的L2范數(shù)，也就是向量 w 每個元素的平方和的開方。那么此時我們的幾何間隔不會隨著 w和b 而等比縮放，始終固定。其實也很好理解，函數(shù)間隔就是 |f(x)| ，是我們人為定義的，而幾何間隔才是真正廣義空間的距離。
此時 SVM 的目標，就是尋找使測試樣本中幾何間隔最小的值，盡可能最大的 w 和 b
如上圖所示，用我們高中的知識就知道，兩類測試數(shù)據(jù) 1，2，3最接近，使樣本中幾何間隔最小的距離盡可能最大的，就是中間的紅色直線(好繞口... ) 此時幾何間隔就是
由于 w, b 的等比收縮對幾何間隔沒有影響，那么我們將w, b收縮成一個值，使 w·x + b ＝ 1，也就是說三個支持向量點 1，2，3距離超平面(中間紅線)的距離相等且為1。那么此時幾何間隔就變成了 1/||w||, 即最終尋找 w, b 使?jié)M足
max min 1/||w||
約束為
w·x + b ＝ 1
由于求 1/||W|| 最大值，但該式數(shù)學處理上不方便，那么轉換成求 ||w||^2/2 的最小值，且滿足對于所有點有 yi(w·xi + b ) - 1 >= 0, 原理很簡單，表達方式有些繞口
由此求出了 SVM 的目標函數(shù)。
舉個小例子
內容來自李航的書。如圖所示三個訓練數(shù)據(jù)，正例 x1=(3,3), x2=(4,3), 負例 x3=(1,1), 試求最大間隔分離超平面
根據(jù)所學的理論，x1, x3 是所謂的支持向量，x2 對解w, b 沒有貢獻，得到目標函數(shù)如下
min (w1^2 + w2^2)/2
約束如下
w1 + w2 + b = -1
3w1 + 3w2 + b = 1
由以上約束得到 b = -2, w1 + w2 =1
代入目標函數(shù)有
min 2w1^2 - 2w1 + 1
上面就是普通的一元二次函數(shù)，求導后得到當 w1 = 1/2 時值最小，那么 w2 = 1/2 ，得到超平面為 (1/2,1/2)·x -2 =0
注：由于書寫格式問題 w1, w2 是矢量，w 是向量，x 是特征向量。
