支持向量機是一種二分類模型，基本模型是定義在特征空間的間隔最大的線性分類器。間隔最大化使它有別于感知機。在面試中，經常遇到手推SVM，所以公式的推導也很重要。
模型：
策略： 間隔最大化，形式化為求解凸二次規劃，等價于正則化的合頁損失函數最小化
算法：略
支持向量機包括： 線性可分支持向量機，線性支持向量機，非線性支持向量機
間隔最大化的直觀解釋：對訓練數據集找到幾何間隔最大的超平面意味著以充分大的確信度對訓練數據進行分類。使其面對最難分的實例點也有足夠大的確信度將它們分開，這樣在面對未知的新實例也有很好的分類預測能力。
支持向量：在數據線性可分的情況下，訓練數據的樣本點與分離超平面最近的樣本點
獻上我看到的最好的講解：https://blog.csdn.net/v_july_v/article/details/7624837（因為鏈接中的大神講解非常好，就不寫自己的理解了）
關于smo的公式推導：https://www.jianshu.com/p/eef51f939ace
合頁損失函數
支持向量機的另外一種解釋就是最小化合頁損失函數


SVM的損失函數就是合頁損失函數加上正則項，第一項是經驗損失，第二項是w的L2范數；它與SVM求最優解的目標函數的形式很相似


從圖中我們可以看到，

1）0-1損失

當樣本被正確分類時，損失為0；當樣本被錯誤分類時，損失為1。

2）感知機損失函數

當樣本被正確分類時，損失為0；當樣本被錯誤分類時，損失為-y(wx+b)。

3）合頁損失函數

當樣本被正確分類且函數間隔大于1時，合頁損失才是0，否則損失是1-y(wx+b)。

相比之下，合頁損失函數不僅要正確分類，而且確信度足夠高時損失才是0。也就是說，合頁損失函數對學習有更高的要求。

python代碼實現：

            
              import numpy as np
from sklearn.metrics.pairwise import rbf_kernel
from scipy.io import loadmat
from sklearn import datasets
"""
svm模型
"""

def linearKernel():
    """線性核函數
    """
    def calc(X, A):
        return X * A.T
    return calc

def rbfKernel(delta):
    """rbf核函數
    """
    gamma = 1.0 / (2 * delta**2)

    def calc(X, A):
        return np.mat(rbf_kernel(X, A, gamma=gamma))
    return calc

def getSmo(X, y, C, tol, maxIter, kernel=linearKernel()):
    """SMO， X 訓練樣本，y標簽集 C正規化參數 tol容忍值 maxIter最大迭代次數，K所用的核
    Args:
        X 訓練樣本
        y 標簽集
        C 正規化參數
        tol 容忍值
        maxIter 最大迭代次數
        K 所用核函數
    Returns:
        trainSimple 簡化版訓練算法
        train 完整版訓練算法
        predict 預測函數
    """
    m, n = X.shape
    # 存放核函數的轉化結果
    K = kernel(X, X)
    # Cache存放預測誤差，用以加快計算速度
    ECache = np.zeros((m,2))

    def predict(X, alphas, b, supportVectorsIndex, supportVectors):
        """計算權值向量
        Args:
            X 預測矩陣
            alphas alphas
            b b
            supportVectorsIndex 支持向量坐標集
            supportVectors 支持向量
        Returns:
            predicts 預測結果
	這里因為對預測起作用的是支持向量，
        非支持向量的前面的alphas為0,支持向量的0
              
                
                   1:
            for k in validCaches:
                if k==i: continue
                Ek = E(k, alphas, b)
                dist = np.abs(abs(Ei-Ek))
                if maxDist < dist:
                    Ej = Ek
                    maxJ = k
                    maxDist = dist
            return maxJ, Ej
        else:
            ### 隨機選擇
            j = selectJRand(i)
            Ej = E(j, alphas, b)
            return j, Ej

    def select(i, alphas, b):
        """alpha對選擇，對alphas的選擇，優化alphas的值
        """
        Ei = E(i, alphas, b)
        # 選擇違背KKT條件的，作為alpha2
       ####yi*f(xi)<-.001 alphas
                  
                    0.01 alphas>0,也就是alpha在0-C下，樣本點不滿足KKT的條件
        Ri = y[i] * Ei
        if (Ri < -tol and alphas[i] < C) or \
                (Ri > tol and alphas[i] > 0):
            # 選擇第二個參數
            j = selectJRand(i)
            Ej = E(j, alphas, b)
            # j, Ej = selectJ(i, Ei, alphas, b)
            # get bounds
            # ##alphas的邊界,0
                    
                      
                        = 0:
                return 0, alphas, b
            iOld = alphas[i].copy()
            jOld = alphas[j].copy()
            alphas[j] = jOld - y[j] * (Ei - Ej) / eta
            if alphas[j] > H:
                alphas[j] = H
            elif alphas[j] < L:
                alphas[j] = L
            if abs(alphas[j] - jOld) < tol:
                alphas[j] = jOld
                return 0, alphas, b
            alphas[i] = iOld + y[i] * y[j] * (jOld - alphas[j])
            # update ECache，update Ecache,存放更新alpha后對應的樣本的誤差
            updateE(i, alphas, b)
            updateE(j, alphas, b)
            # update b
            bINew = b - Ei - y[i] * (alphas[i] - iOld) * Kii - y[j] * \
                (alphas[j] - jOld) * Kij
            bJNew = b - Ej - y[i] * (alphas[i] - iOld) * Kij - y[j] * \
                (alphas[j] - jOld) * Kjj
            if alphas[i] > 0 and alphas[i] < C:
                bNew = bINew
            elif alphas[j] > 0 and alphas[j] < C:
                bNew = bJNew
            else:
                bNew = (bINew + bJNew) / 2
            return 1, alphas, b
        else:
            return 0, alphas, b

    def train():
        """完整版訓練算法
        Returns:
            alphas alphas
            w w
            b b
            supportVectorsIndex 支持向量的坐標集
            supportVectors 支持向量
            iterCount 迭代次數
        """
        numChanged = 0
        examineAll = True
        iterCount = 0
        alphas = np.mat(np.zeros((m, 1)))
        b = 0
        # 如果所有alpha都遵從 KKT 條件，則在整個訓練集上迭代
        # 否則在處于邊界內 (0, C) 的 alpha 中迭代
        while (numChanged > 0 or examineAll) and (iterCount < maxIter):
            numChanged = 0
            if examineAll:
                for i in range(m):
                    changed, alphas, b = select(i, alphas, b)
                    numChanged += changed
            else:
                nonBoundIds = np.nonzero((alphas.A > 0) * (alphas.A < C))[0]
                for i in nonBoundIds:
                    changed, alphas, b = select(i, alphas, b)
                    numChanged += changed
            iterCount += 1

            if examineAll:
                examineAll = False
            elif numChanged == 0:
                examineAll = True
        supportVectorsIndex = np.nonzero(alphas.A > 0)[0]
        supportVectors = np.mat(X[supportVectorsIndex])
        return alphas, w(alphas, b, supportVectorsIndex, supportVectors), b, \
            supportVectorsIndex, supportVectors, iterCount

    def trainSimple():
        """簡化版訓練算法
        Returns:
            alphas alphas
            w w
            b b
            supportVectorsIndex 支持向量的坐標集
            supportVectors 支持向量
            iterCount 迭代次數
        """
        numChanged = 0
        iterCount = 0
        alphas = np.mat(np.zeros((m, 1)))
        b = 0
        L = 0
        H = 0
        while iterCount < maxIter:
            numChanged = 0
            for i in range(m):
                Ei = E(i, alphas, b)
                Ri = y[i] * Ei
                # 選擇違背KKT條件的，作為alpha2
                if (Ri < -tol and alphas[i] < C) or \
                        (Ri > tol and alphas[i] > 0):
                    # 選擇第二個參數
                    j = selectJRand(i)
                    Ej = E(j, alphas, b)
                    # get bounds
                    if y[i] != y[j]:
                        L = max(0, alphas[j] - alphas[i])
                        H = min(C, C + alphas[j] - alphas[i])
                    else:
                        L = max(0, alphas[j] + alphas[i] - C)
                        H = min(C, alphas[j] + alphas[i])
                    if L == H:
                        continue
                    Kii = K[i, i]
                    Kjj = K[j, j]
                    Kij = K[i, j]
                    eta = 2.0 * Kij - Kii - Kjj
                    if eta >= 0:
                        continue
                    iOld = alphas[i].copy();
                    jOld = alphas[j].copy()
                    alphas[j] = jOld - y[j] * (Ei - Ej) / eta
                    if alphas[j] > H:
                        alphas[j] = H
                    elif alphas[j] < L:
                        alphas[j] = L
                    if abs(alphas[j] - jOld) < tol:
                        alphas[j] = jOld
                        continue
                    alphas[i] = iOld + y[i] * y[j] * (jOld - alphas[j])
                    # update b
                    bINew = b - Ei - y[i] * (alphas[i] - iOld) * Kii - y[j] * \
                        (alphas[j] - jOld) * Kij
                    bJNew = b - Ej - y[i] * (alphas[i] - iOld) * Kij - y[j] * \
                        (alphas[j] - jOld) * Kjj
                    if alphas[i] > 0 and alphas[i] < C:
                        b = bINew
                    elif alphas[j] > 0 and alphas[j] < C:
                        b = bJNew
                    else:
                        b = (bINew + bJNew) / 2.0
                    numChanged += 1
            if numChanged == 0:
                iterCount += 1
            else:
                iterCount = 0
        supportVectorsIndex = np.nonzero(alphas.A > 0)[0]
        supportVectors = np.mat(X[supportVectorsIndex])
        return alphas, w(alphas, b, supportVectorsIndex, supportVectors), b, \
            supportVectorsIndex, supportVectors, iterCount
    return trainSimple, train, predict
if __name__ == '__main__':
    data = loadmat('data/ex6data1.mat')

    X = np.mat(data['X'])
    y = np.mat(data['y'], dtype=np.float)
    y[y == 0] = -1

    m, n = X.shape
    tol = 1e-3
    maxIter = 20
    # C = 1.0
    C = 100.0

    trainSimple, train, predict = getSmo(X, y, C, tol, maxIter)
    alphas, w, b, supportVectorsIndex, supportVectors, iterCount = train()
    print(w)
    print(b)
    print(len(supportVectorsIndex))
    print('iterCount:%d' % iterCount)

    predictions = predict(X, alphas, b, supportVectorsIndex, supportVectors)
    errorCount = (np.multiply(predictions, y).A < 0).sum()
    print('error rate: %.2f' % (float(errorCount) / m))


                      
                    
                  
                
              
            
          

代碼的流程：
初始化，所有的alpha都為0，b為0
第一輪遍歷：
1、遍歷整個數據集，計算每個樣本在初始條件下是否滿足KKT條件（y_i*f(x_i)>=1)
滿足：則跳過
不滿足：則作為第一個alpha_1,再遍歷數據集找到|E2-E1|最大的對應的alpha作為alpha_2
2、根據alpha的公式更新alpha_2
3、判斷更新后的alpha_2是否在約束條件內，不在則取邊緣條件的取值；判斷更新的alpha_2與alpha_2_old差值
超過容忍度：計算alpha_1的值，更新b的取值
如果小于容忍度：alpha_2仍然取舊的值
4、當更新后的alpha_1和alpha_2都滿足KKT的約束條件，b取更新后的值；否，則取alpha_1和alpha_2各自對應更新的值的均值
第二輪遍歷：
對alphas中滿足0 繼續重復第二輪，直到：迭代次數超過最大迭代次數
5、根據alphas中大于0的作為支持向量
6、依據更新完畢的alphas和支持向量做predict
補充：通過分類決策函數可以發現，與感知機是一樣的

整個公式推導的流程：

間隔最大化（函數間隔，幾何間隔）——優化目標函數——使用對偶問題求解（要滿足KKT條件對偶問題的最優解才是原問題的最優解）——使用SMO序列最小最優算法求解
（整個公式的推導過程應該時刻注意約束條件）

公式推導手撕版（沒有考慮核函數）：

核函數的介紹以及選擇：

主要是針對線性核，多項式核，和高斯核進行討論：

一般推薦在做訓練之前對數據進行歸一化，當然測試集中的數據也需要歸一化。。

2）在特征數非常多的情況下，或者樣本數遠小于特征數的時候，使用線性核，效果已經很好，并且只需要選擇懲罰系數C即可。

3）在選擇核函數時，如果線性擬合不好，一般推薦使用默認的高斯核’rbf’。這時我們主要需要對懲罰系數C和核函數參數γ進行艱苦的調參，通過多輪的交叉驗證選擇合適的懲罰系數C和核函數參數γ。

4）理論上高斯核不會比線性核差，但是這個理論卻建立在要花費更多的時間來調參上。所以實際上能用線性核解決問題我們盡量使用線性核。

針對高斯核的兩個參數C和 $\gamma$ :
C是控制軟間隔的松弛系數的大小，可以看作是正則項，當C比較大時，我們的損失函數也會越大，這意味著我們不愿意放棄比較遠的離群點。這樣我們會有更加多的支持向量，也就是說支持向量和超平面的模型也會變得越復雜，也容易過擬合。反之，當C比較小時，意味我們不想理那些離群點，會選擇較少的樣本來做支持向量，最終的支持向量和超平面的模型也會簡單。scikit-learn中默認值是1。
$\gamma$ 主要定義了單個樣本對整個分類超平面的影響，當γ比較小時，單個樣本對整個分類超平面的影響比較小，不容易被選擇為支持向量，反之，當 $\gamma$ 比較大時，單個樣本對整個分類超平面的影響比較大，更容易被選擇為支持向量，或者說整個模型的支持向量也會多。scikit-learn中默認值是 $1/樣本特征數$
對C和 $\gamma$ 的調參：
使用網格搜索，使用交叉驗證，尋找出最佳的參數。