image.png
image.png
因此我們希望找一條胖胖的線
fatness也就是我們所說的margin，上圖中的公式就可以寫成
需要滿足兩點：
- 可以把樣本點正確分類
- margin是樣本點離直線的最近距離
目標： find largest-margin separating hyperplane
hypothesis表示為h(x) = sign(WTX+b)
點到直線的距離計算公式：
目標變?yōu)椋?br>
繼續(xù)簡化-放縮
min 公式=1的必要條件是 min 公式>=1,解等價。
把條件放松之后，目標變?yōu)椋?br>
image.png
接下來的任務
求解SVM
轉變成二次規(guī)劃的形式求解
SVM的理論保證：和之前學習過的正則化比較。
另一個方面
consider ‘large-margin algorithm’ Aρ :
either returns g with margin(g) ≥ ρ (if exists), or 0 otherwise
對偶問題2
拉格朗日函數(shù)：
原問題有條件-->無條件的
選出b,w
- （壞的，1-y大于0 ）結果會越大。無限大
- （好的1-y小于0），結果a越小越好。
- 通過L函數(shù)，可以求得原問題的下限。（最大化和最小化做了交換）
-
滿足一定條件(凸，有解，線性條件)。有強對偶關系，解等價。
對偶問題
拉格朗日函數(shù)解法
KKT條件
然后取負號：把最大化-->最小化；再把約束寫到下面。把平方展開。專心求解a，w是一個藏起來的條件。然后用二次規(guī)劃求解。
- 存在問題：Q矩陣計算量太大了。用特別為SVM設計的二次規(guī)劃形式。
- 用KKT條件，求解出w和b。求解b的時候，選一個a！=0 時候計算。 注意到滿足a>0的點，一定落在fat boundary上，這些點就是支持向量。
- 支持向量的理解：
- an >0的屬于SV（在邊界上的點）
- w,b只靠SV算出來。其他的不重要。
SVM和PLA比較
總結
- 原始問題，和在哪個空間有關，d~空間太大的時候就難解
- 對偶問題，切換到a的空間，資料量的大小有關，通過最佳化，找出SV在哪，然后重建胖胖的邊界。
第三講kernel SVM ——簡化dual SVM的計算量
彎彎曲曲的d的解決:用kernel。
kernel不同，幾何定義不同，距離計算的方式不同。得到的邊界不一樣。
kernel SVM
使用無限多維？
可以。
線性的kernel(不做任何轉換)：
優(yōu)點：
- 簡單，安全
- 不涉及別的問題，所以可以設計特別的QP二次規(guī)劃的解決辦法
- 可以很容易的看出來machine怎么做分類的。哪些點重要
壞處：
有限制，當數(shù)據(jù)不是線性可分的時候。
線性核
polynomial kernel多項式核：
計算有困難，很多參數(shù)要選擇，比較困難，心里有想好的Q的時候用
py核
高斯核-無限多維的轉換
高斯核
自己定義的核函數(shù)：對稱，求出來的K是半正定的
