SVM大致思想

線性分類問題

在一群點中用線性函數分類：

但也有線性不可分問題：

線性不可分問題：

最大間隔法

兩個平行超平面間隔距離最大

軟間隔

部分難以區分的點忽略

升維

通過升維將非線性變為線性

計算統計理論基礎

學習過程的一致性

期望風險泛函：定義最優函數在真實數據分布中的期望風險
經驗風險泛函：在有限的數據集上最優函數的期望風險。
由于真實分布未知，機器學習傳統都是用最小化經驗風險來替代最小化期望風險的目標
學習理論的關鍵定理的解讀：如果一個模型方法在最壞情況下仍能表現良好， 則對它的推廣能力才有信心。
函數集的容量

函數容量與VC維

容量（ capacity） ： 函數集在一組樣本集上可能實現的分類方案數目。
例如：二分類問題中有n個樣本，則有2**n種分類方案
生長函數：容量對數在所有可能樣本集上的上界。
要達成學習過程一致性，函數集的一致性的能力不會跟隨樣本數無限增長
VC維：用函數集中的函數所能夠打散的最大樣本集的樣本數目。
期望風險上限


推廣能力： 不取決于經驗風險最小能有多小， 而在于期望風險與經驗風險有多大差距， 差距越小則推廣能力越好。
特定的問題樣本數是固定的： VC 維越高→函數集復雜性越高→置信范圍就越大→推廣能力就可能越差。
結構風險最小化原則SRM：


在小樣本中應該遵循結構風險最小化原則SRM

理論中svm的優勢

為什么要選擇最大間隔

為什么要使用核函數升維

不適定問題與正則化方法

SVM中用到的最優化技巧

以二維為例子：

通過化簡得到下面式子，確定最優化的目標函數

由最終式子可知，我們的最終目標是求盡量小的w。
接下來求約束條件：
在兩線段兩端的點被分類為1和-1
由此得到下面的約束條件

為了方便求解，目標函數做了一定處理。
接下來對不等式約束條件做一定處理變為等式：


這里得出${\lambda }_i$ $\ge$ 0。
因為：可以將${\lambda }_i$看成一個懲罰系數

當${\lambda }_i$為正數時，沒有滿足約束條件會加大原式，作為懲罰，而為負數時則變成了鼓勵參數
從幾何角度考慮這個問題：

從圖中得出有用的約束條件${\lambda }_i$必定為正數，作用是保持約束梯度矢量和與目標梯度方向大小一致。
在這里進一步說明拉格朗日對偶問題：

從求導式子中可以看出，拉格朗日常數法的最終目的是得出一系列常數使目標函數梯度與約束條件梯度相等。

直觀的從上圖中來理解，最優點一定滿足這樣一個性質，最優點對于所有過這一點的約束條件上的梯度的可以用${\lambda }_i$作為參數矢量相加等于目標函數的梯度，而其他點（非最優點）沒有這個性質。因此可以使用這種方法來尋找最優點，這也是拉格朗日常數法的原理。
而${\lambda }_i$=0則是說明對應的約束條件對于該最優化問題是無效的，即松弛的約束條件。

拉格朗日對偶問題

為方便理解，我們首先要將原問題變一下形。

我們將這個等價問題中的min與max交換一下即可得到等價命題：

將對偶函數的最小值部分變為約束條件得到下圖：

這時我們將對偶問題展開：

g($\lambda$, v)是一個仿射集也會是一個凹凸函數，對他求最大值則是對一個凹函數求最大值，約束條件為半空間$\lambda$，v $\ge$ 0，則這總是一個凸優化問題。

強對偶與弱對偶

雖然對偶問題是一個凸優化問題，但原問題只有在與對偶問題強對偶的情況下才能轉換為對偶問題


注意A(x)和I($\lambda$, v)都是L(x,$\lambda$, v)的衍生函數，均由L(x,$\lambda$, v)唯一確定。
由上述推斷出原問題與對偶問題不總是等價的。

下面通過圖形的方式直觀說明，為了方便可視化進行如下變換

接下來進行可視化

解析：原問題求$G_1$在t軸的最低點，對偶問題的值為一跳直線的截距，且斜率為負數。先取最小值決定了直線只能緊貼取值域的下端，而這些下端中相對取值最大的則真好如圖所示，當對偶問題求最大$\lambda$時必定過$G_1$最低點。
當可行域的范圍是一個凸集時，則會成為一個強對偶問題。
在下列兩種情況中都是強對偶問題


強對偶的充分條件
凸優化問題并要滿足Slash條件

圖示如下：

強對偶的必要條件

同時在凸問題中KKT可以推出最優解

回到SVM問題中

在原拉格朗日常數法中已經獲得了原問題可行解和梯度為0條件

1，2為原問題可行解，3為梯度為0條件
通過上述描述，用3，4推出互補松弛條件和最后一個對偶可行性。
補松弛條件：

對偶可行性：

由此所有KKT條件集齊：

由于SVM為凸問題，我們已經得到求取最優點的方法。

SVM中使用拉格朗日對偶

原因：為了方便使用核技巧和提升求解效率。
首先根據上述直接給出SVM的對偶問題：

接下來證明?Slater條件成立
以硬間隔問題為例：因為數據線性可分，總有($\omega$， b)使得一條直線將所有點分為兩類，即滿足所有不等式約束，Slater條件自動滿足。
軟間隔只是允許一定的誤差，原理相同。
由此證明SVM是強對偶問題。
接下來將KKT條件代入對偶問題

然后簡化求解

通過對偶問題后約束僅有$\lambda$，并且可以使用核技巧。

核技巧

當處理非線性可分問題時，需要升維。
我們很容易想到方法一：

但方法一可以更容易的寫成方法二：
上述核函數可以通過修改參數確定維度
那么有沒有什么核函數可以轉換成無窮維呢？
高斯核函數可以通過無窮級數變為無窮維