特别对硬间隔支持向量机，此时在正负样本中都必定存在一个支持向量，落在超平面间隔上，从而

最后一个问题即如何判别样本，这个问题相对简单，因为训练集中正样本总满足((w^*)’x_i+b^*ge 1)，负样本总满足((w^*)’x_i+b^*le -1)，(xi_i)是针对特殊情况的补偿，因此在模型使用时不需考虑，未知样本(x_0)的分类就是

可以看到，求解完毕的支持向量机中，无论是参数表示还是模型使用，均只与支持向量有关.

核技巧

线性不可分时，除了能使用软间隔SVM以外，还可以用特征映射(varphi(cdot))将样本((x_i,y_i))映射到高维((varphi(x_i),y_i))，因为高维空间中的数据更系数，线性可分的可能性也更大. 然而，(varphi(cdot))往往是形式未知、维度极高甚至是无限维的，在这种情形下，核技巧(kernel trick)提供了一种绕开(varphi(cdot))的计算，不显式地计算转化后的数据集(varphi(x_i))，也能在转化后的高维空间中使用支持向量机的方法.

先回顾支持向量机应用于非特征映射数据集时的步骤：

1. 构建对偶问题求解，在(sum_{i=1}^{n}alpha_iy_i=0)且(alpha_iin[0,C])的情况下求解(max_{alpha}left(sum_{i}alpha_i-frac{1}{2}sum_{i,j}alpha_ialpha_jy_iy_j(x_i’x_j) right)).1.
2. 得到最优解(alpha)后，找到一个(alpha_kin (0,C))，反推(b=y_k-sum_{i}alpha_iy_i(x_i’x_k)).
3. 得到分割超平面(sum_ialpha_iy_i(x_i’x)+b=0)，判别新样本(y_0=mathrm{sign}(sum_{i}alpha_iy_i(x_i’x_0)+b)).

注意到上面的过程中，有意地隐去了(w)的计算，因为不论在模型表示还是样本归类中，都不需要显式地得到(w)的具体值；并且，任何出现了样本特征(x)的地方，总是以内积(x_i’x_j)的形式出现. 这说明，即使使用了特征映射(varphi(cdot))，也不必显式地得到每个样本(x)对应的高维特征(varphi(x))，但是对任意样本对((x_i,x_j))，它们的内积(varphi(x_i)’varphi(x_j))却是必要的.

因此，核技巧不显式地求解(varphi(cdot))，而是用一个对称二元函数(kappa:(mathbb{R}^{d},mathbb{R}^{d})mapsto mathbb{R})定义了内积:(kappa(x_i,x_j)=varphi(x_i)’varphi(x_j):=langle x_i,x_jrangle)，这样，将核技巧运用于支持向量机就可以将上面的步骤直接改写为：

1. 构建对偶问题求解，在(sum_{i=1}^{n}alpha_iy_i=0)且(alpha_iin[0,C])的情况下求解(max_{alpha}left(sum_{i}alpha_i-frac{1}{2}sum_{i,j}alpha_ialpha_jy_iy_jlangle x_i,x_jrangle right)).
2. 得到最优解(alpha)后，找到一个(alpha_kin (0,C))，反推(b=y_k-sum_{i}alpha_iy_ilangle x_i,x_krangle).
3. 得到分割超平面(sum_ialpha_iy_ilangle x_i,xrangle+b=0)，判别新样本(y_0=mathrm{sign}(sum_{i}alpha_iy_ilangle x_i,x_0rangle+b)).

综上所述，核技巧就是在不使用特征映射(varphi(cdot))的显式表达的同时，利用内积完成了特征映射所需要达到的目标，使得用户不需要考虑如何变换样本的特征，只需尝试不同的核函数即可. 常用的核函数有：

• 线性核：(kappa( x_i, x_j)= x_i’ x_j).
• 多项式核：(kappa( x_i, x_j)=( x_i’ x_j)^{d}).
• 高斯核：(kappa( x_i, x_j)=exp(-frac{| x_i- x_j|^2}{2sigma^2})).
• 拉普拉斯核：(kappa( x_i, x_j)=exp(-frac{| x_i- x_j|}{sigma})).
• Sigmoid核：(kappa( x_i, x_j)=tanh(beta x_i’ x_j+theta)).

甚至核函数的形式也不是必要的，只要有办法得到每一个样本对的核函数值即可，因此在训练过程中，传入一个核矩阵(Kinmathbb{R}^{ntimes n})代表样本对的核函数值，并在使用过程中传入样本(x_0)的同时，传入一个向量(k_0inmathbb{R}^{n})代表(x_0)与所有训练样本的核函数值，就可以等效地作为核函数使用.

不过，由于核函数本身是特征映射内积的替代，所以核函数本身需要满足一定的条件. Mercer表明任何半正定函数都可以作为核函数使用，半正定函数指的是对任意数据集((x_1,cdots,x_n))，核函数(kappa)诱导的矩阵(Kinmathbb{R}^{ntimes n}:K_{ij}=kappa(x_i,x_j))都是对称半正定的. 即使传入核矩阵(K)代替核函数，那么(K)本身也要是对称半正定矩阵，并且加入训练样本后，它与其他样本构成的核向量也要在增广意义下是对称半正定的.

SMO算法

最后进入到求解对偶问题的算法，常使用SMO(序列最小优化)算法对SVM的对偶问题进行求解，其思想是在对偶问题的(n)个变量中每次只选择两个进行优化，通过约束(sum_{i=1}^{n}alpha_iy_i=0)，固定(n-2)个变量使得每次优化只有一个(alpha_i)可以自由变化，因此可以通过求梯度的方式直接优化.

对软间隔SVM，令(K_{ij}=langle x_i,x_jrangle)即(x_i,x_j)的核函数值，目标是最大化

现选择变量对((alpha_1,alpha_2))优化并将其他变量用无关值(C)代替，那么约束变为(alpha_1y_1+alpha_2y_2=zeta)，目标就变成

再将约束条件：(alpha_2=zeta y_2-alpha_1y_1y_2)代入，并令(sum_{j=3}^{n}alpha_jy_jK_{ij}=v_i(i=1,2))，就得到关于(alpha_1)的一元二次优化问题

令(frac{partial W(alpha_1)}{partial alpha_1}=0)就得到(alpha_1)应满足的条件为

在求得(zeta)、(v_1)和(v_2)的同时，已经可以计算得到(alpha_1)、(alpha_2)的值. 注意，在软间隔SVM中还需要满足(alpha_1in[0,C])与(alpha_2in[0,C])，并结合约束(alpha_1y_1+alpha_2y_2=zeta). 这里分两种情况：

1. (y_1ne y_2)时，约束变为(alpha_1-alpha_2=k)，其中(k)的正负性未知，因此(max(0,k)lealpha_1lemin(C,C+k)).
2. (y_1=y_2)时，约束变为(alpha_1+alpha_2=k)，其中(k)与(C)的大小关系未知，因此(max(0,k-C)lealpha_1le min(C,k)).
3. 对(k)的求值，注意到参数更新前后始终有(alpha_1y_1+alpha_2y_2=zeta)且((y_1,y_2))不变，因此可以直接用更新前的参数计算(k).
4. 得到的上下界同时适用于(alpha_1)和(alpha_2)，若求得的(alpha_1,alpha_2)超出此边界，则进行矩形修剪.

上述形式还可以继续化简，注意对(alpha^text{new})和(alpha^text{old})作区分. SVM对样本(x)的预测为(f(x)=sum_{i=1}^{n}alpha_i^text{old}y_ilangle x_i,xrangle +b)，因此

再将(alpha_2=zeta y_2-alpha_1y_1y_2)代入（此式子对(alpha^text{new})和(alpha^text{old})均成立），就得到

将其带回(frac{partial W(alpha_1)}{partial alpha_1})得到

令(E_i=f(x_i)-y_i)为旧模型在第(i)个样本上的预测误差，就有

上式略过了一些繁琐参数（如(C)、(zeta)）的计算，形式美观，但应服务器托管用上依赖于旧模型(f(cdot))，这意味着每次更新参数后需要得到新的模型，即需要对(b)进行更新. 注意到，至少有一个(alpha_i)不在边界([0,C])上时(x_i)是支持向量，此时有

若两个(alpha_i)经更新后均不在边界上，则通过两个(x_i)计算得到的(b^text{new})相等；若两个(alpha_i)经更新后均在边界上，则取用这两个样本计算得到的(b)的中点作为(b^text{new}).

综上，给出SMO算法更新软间隔SVM的含代数步骤：

1. 随机选择一对样本对应的变量作为更新变量((alpha_i,alpha_j)).
2. 令(E_k=f(x_k)-y_k)为旧SVM的预测误差，计算无修剪的更新值(alpha_i^text{new}=alpha_i^text{old}-frac{y_i(E_i-E_服务器托管j)}{K_{ii}+K_{jj}-2K_{ij}}).
3. 求(alpha_i^text{new})的修剪上下限：若(y_ine y_j)则约束为(alpha_i-alpha_j=k)，因此(L=max(0,alpha_i^text{old}-alpha_j^text{old}))，(H=min(C,C+alpha_i^text{old}-alpha_j^text{old}))；若(y_i=y_j)则约束为(alpha_i+alpha_j=k)，因此(L=max(0,alpha_i^text{old}+alpha_j^text{old}-C))，(H=min(C,alpha_i^text{old}+alpha_j^text{old})).
4. 修剪解：将(alpha_i^text{new})修剪至([L,H])之间，并根据(alpha_i^text{old}y_i+alpha_j^text{old}y_j=alpha_i^text{new}y_i+alpha_j^text{new}y_j)得到(alpha_j^text{new}).
5. 更新(b)：若(alpha_i^text{new})和(alpha_j^text{new})中至少有一个是支持向量（设为(i)），则更新(b^text{new}=1-y_isum_{j}alpha_j^text{new}y_jK_{ji})；若二者均不是支持向量，则依然用此法计算两个(b)，取它们的平均作为(b^text{new}).
6. 循环上述步骤，取不同的更新变量对进行更新.

SVM分类的建议代码实现

下面给出了使用SMO算法训练SVM分类器的具体实现，这里使用了随机抽选的方式选择每次更新的变量对((alpha_i,alpha_j))，并且使用内积核函数，指定(C=+infty)代表一个硬间隔分类器. 模型对一个人造数据集合真实数据集breast_cancer都有较为不错的分辨能力，需注意要对模型标签进行({-1,1})化，同时这里还对特征进行归一化以防止数值溢出.

import numpy as np
from sklearn.datasets import load_breast_cancer

class SVM:
    def __init__(self, X, y, kernel=None):
        self.X = np.array(X)
        self.y = np.array(y)  # {-1, 1}
        if not kernel:
            kernel = np.dot
        self.kernel = kernel
        self.n_samples, self.dim = self.X.shape
        self.alpha = np.zeros(self.n_samples)
        self.b = 0
    
    def fit(self, max_iter=10000, C=float('inf')):
        for k in range(max_iter):
            i, j = np.random.choice(self.n_samples, 2, replace=False)
            Ei = self.predict(self.X[i]) - self.y[i]
            Ej = self.predict(self.X[j]) - self.y[j]
            eta = self.kernel(self.X[i], self.X[i]) + self.kernel(self.X[j], self.X[j]) - 2 * self.kernel(self.X[i], self.X[j])
            alpha_i_unclipped = self.alpha[i] - self.y[i] * (Ei-Ej) / eta
            alpha_i_clipped, alpha_j_clipped = 0, 0
            if self.y[i] == self.y[j]:
                K_constant = self.alpha[i] + self.alpha[j]
                lower_bound = max(0, K_constant - C)
                upper_bound = min(C, K_constant)
                alpha_i_clipped = self.__clip(alpha_i_unclipped, lower_bound, upper_bound)
                alpha_j_clipped = K_constant - alpha_i_clipped
            else:
                K_constant = self.alpha[i] - self.alpha[j]
                lower_bound = max(0, K_constant)
                upper_bound = min(C, C + K_constant)
                alpha_i_clipped = self.__clip(alpha_i_unclipped, lower_bound, upper_bound)
                alpha_j_clipped = alpha_i_clipped - K_constant
            self.alpha[i], self.alpha[j] = alpha_i_clipped, alpha_j_clipped
            if self.alpha[i] > 0 and self.alpha[i]  0 and self.alpha[j]  H:
            return H
        else:
            return alpha
    
    def __calculate_b(self, ind):
        return 1 - self.y[ind] * np.dot(self.y * self.alpha, self.kernel(self.X, self.X[ind]))
    
    def predict(self, x):
        x = np.array(x)
        if len(x.shape) == 1:
            return self.b + np.sum(self.alpha * self.y * self.kernel(self.X, x))
        elif len(x.shape) == 2:
            return self.b + np.dot(self.alpha * self.y, self.kernel(self.X, x.T))
    
    def predict_label(self, x):
        y_pred = self.predict(x)
        return np.sign(y_pred)
    
def acc(pred, label):
    return (pred == label).mean()

np.random.seed(0)
d = 5; n = 200
X_syn = [np.random.multivariate_normal(mean=np.random.normal(size=d), cov=np.identity(d) / 5, size=(100,)) for i in range(2)]
X_syn = np.vstack(X_syn)
y_syn = np.repeat([-1, 1], 100)
clf = SVM(X_syn, y_syn)
clf.fit()
print(f'acc = {acc(clf.predict_label(X_syn), y_syn)}')

df = load_breast_cancer()
X_real, y_real = df['data'], df['target']
X_real = (X_real - X_real.mean(0)) / X_real.std(0)
y_real = y_real * 2 - 1
clf_real = SVM(X_real, y_real, kernel=np.dot)
clf_real.fit()
print(f'acc of breast cancer = {acc(clf_real.predict_label(X_real), y_real)}')