算法模型---支持向量机(SVM)_支持向量机预测模型

来源：JerryLead

支持向量机的特点

支持向量机的用途

SVM一般是用来分类的（一般先分为两类，再向多类推广)

支持向量机的适用范围

数据类型

自变量可以数值型和标称型数据
因变量是二分类，通过改造也可以是多分类；

支持向量机的优点

通过核函数，可解决非线性问题
优点：泛化错误率低，计算开销不大，结果易解释；

1. 解决高维特征的分类问题和回归问题很有效,在特征维度大于样本数时依然有很好的效果。
2. 仅仅使用一部分支持向量来做超平面的决策，无需依赖全部数据。
3. 有大量的核函数可以使用，从而可以很灵活的来解决各种非线性的分类回归问题。
   4)样本量不是海量数据的时候，分类准确率高，泛化能力强。

在预测时因为只需考虑支持向量，而不需要考虑全部数据点，理论上较逻辑回归等算法会快很多；

支持向量机的局限性

对于靠近超平面的噪声敏感
缺点：对参数调节和核函数的选择敏感，原始分类器不加修改仅适用于处理二类问题；

1. 如果特征维度远远大于样本数，则SVM表现一般。
2. SVM在样本量非常大，核函数映射维度非常高时，计算量过大，不太适合使用。
   3）非线性问题的核函数的选择没有通用标准，难以选择一个合适的核函数。
   4）SVM对缺失数据敏感。

简介

支持向量机基本上是最好的有监督学习算法了。很多正统的讲法都是从VC 维理论和结构风险最小原理出发，然后引出SVM什么的，还有些资料上来就讲分类超平面什么的。这里以斯坦福提供的学习材料为基础。这份材料从前几节讲的logistic回归出发，引出了SVM，既揭示了模型间的联系，也让人觉得过渡更自然。

重新审视logistic回归

Logistic回归目的是从特征学习出一个0/1分类模型，通过使用logistic函数（或称作sigmoid函数）将因变量的取值范围从线性回归的$(-\infty ,+\infty )$映射到(0,1)上，映射后的值可以认为是属于$y=1$的概率。
形式化表示就是函数
$$h_w(x)=g(w^{T}x)=\frac{1}{1+e^{-w^{T}x}}$$
其中$w$是权重向量，x是样本的n维特征，两者均为列向量，函数g是sigmoid函数。
$$\begin{gathered} P(y=1|x,w)=h_w(x) \\ P(y=0|x,w)=1-h_w(x) \end{gathered}$$
通过学习，我们可以得到对全体样本最佳拟合的系数
w = [ w 0 w 1 . . . w p ] w=\left[

$$\begin{matrix} w _0\\ w_1\\...\\ w_p\\ \end{matrix}$$ \right] w=⎣⎢⎢⎡​w0​w1​...wp​​⎦⎥⎥⎤​
当我们要判别一个新来的样本属于哪个类时，只需求$h_w(x)$，若$h_w(x)$大于0.5就是y=1的类，反之属于y=0类。
再审视一下$h_w(x)$，发现只和$w^{T}x$有关，$w^{T}x$ >0，那么$h_w(x)>0$，g(z)只不过是用来映射，真实的类别决定权还在$w^{T}x$。还有当$w^{T}x>>0$时，$h_w(x)=1$;当$w^{T}x<<0$反之$h_w(x)=0$。如果我们只从$w^{T}x$出发，希望模型达到的目标无非就是让训练数据中y=1的样本$w^{T}x>>0$，而且y=0的特征$w^{T}x<<0$。Logistic回归就是要学习得到，使得正例的$w^{T}x$远大于0，负例的$w^{T}x$远小于0，强调在全部训练实例上达到这个目标。
图形化表示如下：
中间那条线是$w^{T}x=0$，logistic回顾强调所有点尽可能地远离中间那条线。学习出的结果也就中间那条线。考虑上面3个点A、B和C。从图中我们可以确定A是×类别的，B还算能够确定，然而C我们是不太确定的。这样我们可以得出结论，我们更应该关心靠近中间分割线的点，让他们尽可能地远离中间线，而不用在所有点上达到最优。因为那样的话，要使得一部分点靠近中间线来换取另外一部分点更加远离中间线。比如在谋求全局最优的时候，为了让A点这样的数据更靠近中间线，可能会使得一部分像C这样的数据点做出牺牲，这些数据点可能被分在对方那一侧去了，这是没必要的。我想这就是支持向量机的思路和logistic回归的不同点，一个考虑局部（不关心已经确定远离的点），一个考虑全局（已经远离的点可能通过调整中间线使其能够更加远离）。这是我的个人直观理解。

形式化表示

我们这次使用的结果标签是y=-1,y=1，替换在logistic回归中使用的y=0和y=1。再明确下假设函数
$$h_{w,b}=g(w^{T}x+b)$$
这里将参数的常数量单独拿出来了，用b表示，与逻辑回归是一个意思。
上一节提到过我们只需考虑的正负问题，而不用关心g(z)，因此我们这里将g(z)做一个简化，将其简单映射到y=-1和y=1上。映射关系如下：
g ( z ) = { 1 , z ≥ 0 − 1 , z &lt; 0 g(z)= \left\{

$$\begin{matrix} 1,z\geq 0\\ -1,z&lt;0 \end{matrix}$$ \right. g(z)={1,z≥0−1,z<0​

函数间隔（functional margin）和几何间隔（geometric margin）

函数间隔
给定一个训练样本，x是特征，y是结果标签,i表示第i个样本。我们定义函数间隔如下：
$${\hat{\gamma }}_i=y_i(w^T{x}_i+b)$$
当$y_i=1$时，$w^T{x}_i+b\ge 0$；当$y_i=-1$时，$w^T{x}_i+b<0$；${\hat{\gamma }}_i$的值实际上就是$||w^T{x}_i+b||$，$||w^T{x}_i+b||$越大，我们更有信心确定是正例还是负例。因此函数间隔代表了我们认为样本是正例还是负例的确信度。
继续考虑w和b，如果同时加大w和b，比如在前面乘个系数比如2，那么所有点的函数间隔都会增大二倍，这个对求解问题来说没有影响，因为我们要求解的是$W^{T}x+b=0$，同时扩大w和b对结果是无影响的。在判断样本类别，作定性分析的时候，也没有影响；但想定量分析某一类别概率的时候，这种概率应该是固定，也就判断的尺度本身不应该可变。我们可以对系数进行归一化，归一化的函数间隔其实就是几何间隔。
几何间隔

当然我们也可以一开始就从几何间隔出发。
在初中的几何中，我们知道点$(x_0,y_0)$到直线$Ax+By+C=0$的距离公式为
$$r=\frac{||A{x}_0+B{y}_0+C||}{\sqrt{A^2+B^2}}$$
对应到我们的情况：
此时$w$就相当于A，而B=0，C相当于b。
因而样本点到分界面的几何间隔可如下表示和计算
$${\gamma }_i=\frac{||w^T{x}_i+b||}{\sqrt{(w^T{)}^2}}=$$
考虑到$y_i$与$w^T{x}_i+b$正负取值的一致，可以将上式改写为
$${\gamma }_i=y_i\frac{(w^T{x}_i+b)}{||w||}$$
再回过来看，当时||w||=1时，不就是函数间隔吗？是的，前面提到的函数间隔归一化结果就是几何间隔。
全局的几何间隔
定义如下：
$$\gamma =mi{n}_{i=1,2,\dots ,m}{\gamma }_i$$

最优间隔分类器定义（optimal margin classifier）

回想前面我们提到我们的目标是寻找一个超平面，使得离超平面比较近的点能有更大的间距。也就是我们不考虑所有的点都必须远离超平面，我们关心求得的超平面能够让所有点中离它最近的点具有最大间距。形象的说，我们将上面的图看作是一张纸，我们要找一条折线，按照这条折线折叠后，离折线最近的点的间距比其他折线都要大。形式化表示为：
$$\begin{gathered} ma{x}_{w,b}\gamma \\ s.t.y_i\frac{(w^T{x}_i+b)}{||w||}\ge \gamma ,i=0,1,\dots ,m \end{gathered}$$


上面的目标函数归纳起来就是求取w和b使得离分类超平面最近的点到分类超平面的几何距离最大，而其他点到分类超平面的几何距离比这个值都大。
到此，我们已经将模型定义出来了。如果求得了w和b，那么来一个样本特征x，代入到$W^{T}x+b$，我们就能够分类了，满足上述目标函数的分类器称为最优间隔分类器。接下的问题就是如何求解w和b的问题了。
离超平面最近的点即所谓的支持向量。如上图中圆圈所中的点。
注意，函数间隔的尺度缩放并不会影响几何间隔的大小，我们不防把离超平面最近点的函数间隔设为1，此时离超平台最近点的几何间隔为$\frac{1}{||w||}$。我们的目标就变成了求一组参数使得$\frac{1}{||w||}$尽可能大，且其它样本点到超平面的距离都大于等于这个距离。而$\frac{1}{||w||}$尽可能大,也就是$\frac{||w|{|}^2}{2}$尽可能小；其它样本点到超平面的距离都大于等于这个距离，这与其它样本点到超平面的函数距离都大于等于1是等价的。
因而整个目标函数就变成
$$\begin{gathered} mi{n}_{w,b}\frac{||w^2||}{2} \\ s.t{y}_i(w^T{x}_i+b)\ge 1 \end{gathered}$$

这下好了，只有线性约束了，而且是个典型的二次规划问题（目标函数是自变量的二次函数）。代入优化软件可解。

接下来介绍的是手工求解的方法了，一种更优的求解方法。

拉格朗日乘数法

参考算法模型—最优化方法–常用方法

库恩-库塔条件

参考算法模型—最优化方法–常用方法

最优间隔分类器求解

最优间隔器的目标函数为：
$$\begin{gathered} mi{n}_{w,b}\frac{||w|{|}^2}{2} \\ s.t.1-y_i(w^T{x}_i+b)\le 0 \end{gathered}$$
这是一个不等式约束条件下的极值求解问题。先构造广义拉格朗日函数
$$L(w,b,\alpha )=\frac{1}{2}||w|{|}^2+\sum _{i=1}^m{\alpha }_i(1-y_i(w^T{x}_i+b))$$
套用KKT条件的结论，上式中如下位置取到极值
$$\begin{gathered} \frac{\partial L(w,b,\alpha )}{\partial w}=0-----(1) \\ \frac{\partial L(w,b,\alpha )}{\partial b}=0-----(2) \\ {\alpha }_i(1-y_i(w^T{x}_i+b))=0-----(3) \\ {\alpha }_i\ge 0-----(4) \\ 1-y_i(w^T{x}_i+b)\le 0-----(5) \end{gathered}$$
在展开进一步计算前我们先理清一些关系，对于任意一个样本点，只有其是支持向量的时候才有$1-y_i(w^T{x}_i+b)=0$，而其它样本点$1-y_i(w^T{x}_i+b)<0$,代入（3）式中，我们可以得到结论，只有在支持向量处${\alpha }_i̸=0$而其他位置${\alpha }_i=0$。
下面就(1)(2)两式展开计算。
$$\begin{gathered} \frac{\partial L(w,b,\alpha )}{\partial w}=w+\sum _{i=1}^m{\alpha }_i(-y_i{x}_i)=0 \\ \sum _{i=1}^m{\alpha }_i{y}_i=0 \end{gathered}$$
即
$$\begin{gathered} w=\sum _{i=1}^m{\alpha }_i{y}_i{x}_i \\ \sum _{i=1}^m{\alpha }_i{y}_i=0 \end{gathered}$$
将上式带回到拉格朗日函数中得到，此时得到的是该函数的最小值（目标函数是凸函数）
$$L(w,b,\alpha )=\frac{1}{2}||w|{|}^2+\sum _{i=1}^m{\alpha }_i(1-y_i(w^T{x}_i+b))$$
目标函数进一步化简为：
L ( w , b , α ) = 1 2 ( ∑ i = 1 m α i y i x i ) T ∑ i = 1 m α i y i x i + ∑ i = 1 m α i − ∑ i = 1 m α i y i ( ∑ i = 1 m α i y i x i ) T x i − ∑ i = 1 m α i y i b = 1 2 ∑ i = 1 m α i y i ( x i ) T ∑ i = 1 m α i y i x i + ∑ i = 1 m α i − ∑ i = 1 m α i y i ( x i ) T ∑ i = 1 m α i y i x i = − 1 2 ∑ i = 1 m α i y i ( x i ) T ∑ i = 1 m α i y i x i + ∑ i = 1 m α i = − 1 2 ∑ i = 1 m α i y i ( x i ) T ∑ j = 1 m α j y j x j + ∑ i = 1 m α i = − 1 2 ∑ i = 1 m ∑ j = 1 m α i y i ( x i ) T α j y j x j + ∑ i = 1 m α i = − 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j ( x i ) T x j + ∑ i = 1 m α i

$$\begin{matrix} L(w,b,\alpha) &amp;=&amp;\frac{1}{2} (\sum_{i=1}^m\alpha_i y_ix_i)^T \sum_{i=1}^m\alpha_i y_ix_i+\sum_{i=1}^m \alpha_i -\sum_{i=1}^m \alpha_i y_i(\sum_{i=1}^m \alpha_i y_ix_i)^Tx_i-\sum_{i=1}^m \alpha_i y_ib\\ &amp;=&amp;\frac{1}{2} \sum_{i=1}^m\alpha_i y_i(x_i)^T \sum_{i=1}^m\alpha_i y_ix_i+\sum_{i=1}^m \alpha_i -\sum_{i=1}^m \alpha_i y_i(x_i)^T\sum_{i=1}^m \alpha_i y_ix_i\\ &amp;=&amp;-\frac{1}{2} \sum_{i=1}^m\alpha_i y_i(x_i)^T \sum_{i=1}^m\alpha_i y_ix_i+\sum_{i=1}^m \alpha_i\\ &amp;=&amp;-\frac{1}{2} \sum_{i=1}^m\alpha_i y_i(x_i)^T \sum_{j=1}^m\alpha_j y_jx_j+\sum_{i=1}^m \alpha_i\\ &amp;=&amp;-\frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i y_i(x_i)^T \alpha_j y_jx_j+\sum_{i=1}^m \alpha_i\\ &amp;=&amp;-\frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j (x_i)^T x_j+\sum_{i=1}^m \alpha_i\\ \end{matrix}$$ L(w,b,α)​======​21​(∑i=1m​αi​yi​xi​)T∑i=1m​αi​yi​xi​+∑i=1m​αi​−∑i=1m​αi​yi​(∑i=1m​αi​yi​xi​)Txi​−∑i=1m​αi​yi​b21​∑i=1m​αi​yi​(xi​)T∑i=1m​αi​yi​xi​+∑i=1m​αi​−∑i=1m​αi​yi​(xi​)T∑i=1m​αi​yi​xi​−21​∑i=1m​αi​yi​(xi​)T∑i=1m​αi​yi​xi​+∑i=1m​αi​−21​∑i=1m​αi​yi​(xi​)T∑j=1m​αj​yj​xj​+∑i=1m​αi​−21​∑i=1m​∑j=1m​αi​yi​(xi​)Tαj​yj​xj​+∑i=1m​αi​−21​∑i=1m​∑j=1m​αi​αj​yi​yj​(xi​)Txj​+∑i=1m​αi​​
上式中$(x_i{)}^T{x}_j$就是两个向量内向积的计算公式，可以表示成$<x_i,x_j>$
至此，目标函数及其约束可以表示成下面的形式
$$\begin{gathered} L(w,b,\alpha )=-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j<x_i,x_j>+\sum _{i=1}^m{\alpha }_i-----(6) \\ w=\sum _{i=1}^m{\alpha }_i{y}_i{x}_i-----(7) \\ \sum _{i=1}^m{\alpha }_i{y}_i=0-----(8) \\ {\alpha }_i(1-y_i(w^T{x}_i+b))=0-----(9) \\ {\alpha }_i\ge 0-----(10) \\ 1-y_i(w^T{x}_i+b)\le 0-----(11) \end{gathered}$$
如果求得极值点的${\alpha }_i^{\ast }$，那么极值点的$w^{\ast }$可由公式（7）计算得到。极值点处的$b^{\ast }$可由支持向量给出。即离超平面最近的正的函数间隔要等于离超平面最近的负的函数间隔。
$$\begin{gathered} (w^{\ast }{)}^T{x}^{(\ast i)}+b^{\ast }=1,x^{(\ast i)}为正方向的支持向量 \\ (w^{\ast }{)}^T{x}^{(\ast j)}+b^{\ast }=-1,x^{(\ast j)}为负方向的支持向量 \end{gathered}$$
从而$b^*=-\frac{(w*)^Tx{(*i)}+(w^*)Tx^{(*j)}}{2} $
但其实关于样本的类别判断，我们都不需要这么麻烦的去计算$w^{\ast }$和$b^{\ast }$。
先看看$w^T{x}_i+b$，这是我们对样本进行类别判断的标准。
$$\begin{array}{ccc}{w}^{T}x+b& =& ({\sum }_{i=1}^m{\alpha }_i{y}_i{x}_i{)}^{T}x+b\\ & =& {\sum }_{i=1}^m{\alpha }_i{y}_i(x_i{)}^{T}x+b\\ & =& {\sum }_{i=1}^m{\alpha }_i{y}_i<x_i,x>+b\end{array}$$
也就是说，以前新来的要分类的样本首先根据w和b做一次线性运算，然后看求的结果是大于0还是小于0,来判断正例还是负例。现在有了${\alpha }_i$，我们不需要求出$w$，只需将新来的样本和训练数据中的所有样本做内积和即可。那有人会说，与前面所有的样本都做运算是不是太耗时了？其实不然，我们从KKT条件中得到，只有支持向量的${\alpha }_i>0$，其他情况${\alpha }_i=0$。因此，我们只需求新来的样本和支持向量的内积，然后运算即可。

核函数（Kernels）

引入核函数的原因

考虑我们最初在“线性回归”中提出的问题，特征是房子的面积x，这里的x是实数，结果y是房子的价格。假设我们**从样本点的分布中(因而如何选核函数的时候这就是一种方法，对样本抽样，查看其分布)**看到x和y符合3次曲线，那么我们希望使用x的三次多项式来逼近这些样本点。那么首先需要将特征x扩展到三维$(x,x^2,x^3)$，然后寻找特征和结果之间的模型。我们将这种特征变换称作特征映射（feature mapping）。映射函数称作$\varphi$，在这个例子中
ϕ ( x ) = [ x x 2 x 3 ] \phi(x)= \left[

$$\begin{matrix} x\\x^2\\x^3\\ \end{matrix}$$ \right] ϕ(x)=⎣⎡​xx2x3​⎦⎤​
我们希望将得到的特征映射后的特征应用于SVM分类，而不是最初的特征。这样，我们需要将前面$w^{T}x+b$公式中的内积从$\langle x_i,x\rangle$，映射到$\langle \varphi (x_i),\varphi (x)\rangle$。
至于为什么需要映射后的特征而不是最初的特征来参与计算，上面提到的（为了更好地拟合）是其中一个原因，另外的一个重要原因是样例可能存在线性不可分的情况，而将特征映射到高维空间后，往往就可分了。（在《数据挖掘导论》Pang-Ning Tan等人著的《支持向量机》那一章有个很好的例子说明）

上图所示的数据，如果用线性分类器来分类，没有办法作区分。
但如果通过下面的映射
$$\begin{gathered} z_1=x_1^2 \\ {z}_2=x_2^2 \\ {z}_3=x_2 \end{gathered}$$
映射后的图像如下：

我们可以看到，在高维空间就可分了。
我们作映射的原因：

• 1、为了更好地拟合；
• 2、样例可能存在线性不可分的情况，而将特征映射到高维空间后，可能就可分了

将数据映射到高维空间后，我们就可以使用与之前一样的方法来迭代拟合相应的${\alpha }_i$和b，不同的是特征变量数目会比原空间多很多，但整个优化过程中是没有任何区别的。
将核函数形式化定义
如果原始特征内积是$\langle x,z\rangle$，映射后为$\langle \phi (x),\phi (z)\rangle$，那么定义
核函数（Kernel）为$K(x,z)=\varphi (x{)}^T\varphi (z)$
即把计算两个向量在隐式映射后的空间内内积的函数做作核函数。
到这里，我们可以得出结论，如果要实现该节开头的效果，只需先计算$\varphi (x)$，然后计算$\varphi (x{)}^T\varphi (z)$即可，然而这种计算方式是非常低效的。
**问题：**虽然上面的方式原理上可解，但是因为多了列，假如$\phi (x)$的列是$x$3倍，那么内积的数目将是原来的9倍。如何是用高斯函数或多项式项目的时候，就会存在维数灾难。比如最初的特征是$n$维的，我们将其映射到$n^{2$维，然后再计算，这样需要$O(n}2)$的时间。那么我们能不能想办法减少计算时间呢？
先看一个例子，假设x和z都是n维的，,其核函数表示如下：
$$K(x,z)=(x^{T}z{)}^2$$

**当我们看到核函数后就知道要怎么计算映射后的内积：将原始空间的内积经过一定变换后得到。但根据核函数的不同，可能有的是在原始空间的内积上运算，有的是直接将样本代入核函数，此时可能就看不到内积的运算。**现在我们来看看这种变换的结果是不是映射后空间的内积。
将上面的核函数展开
K ( x , z ) = ( x T z ) 2 = ( ∑ i = 1 n x i z i ) ( ∑ j = 1 n x j z j ) = ∑ i = 1 n ∑ j = 1 n x i z i x j z j = ∑ i = 1 n ∑ j = 1 n ( x i x j ) ( z i z j ) = ϕ ( x ) T ϕ ( z )

$$\begin{matrix} K(x,z) &amp;=&amp;(x^T z)^2\\ &amp;=&amp;(\sum_{i=1}^n x_i z_i)(\sum_{j=1}^n x_j z_j)\\ &amp;=&amp;\sum_{i=1}^n\sum_{j=1}^n x_i z_i x_j z_j\\ &amp;=&amp;\sum_{i=1}^n\sum_{j=1}^n (x_i x_j) (z_i z_j)\\ &amp;=&amp;\phi (x)^T \phi(z)\\ \end{matrix}$$ K(x,z)​=====​(xTz)2(∑i=1n​xi​zi​)(∑j=1n​xj​zj​)∑i=1n​∑j=1n​xi​zi​xj​zj​∑i=1n​∑j=1n​(xi​xj​)(zi​zj​)ϕ(x)Tϕ(z)​
这个时候发现我们可以只计算原始特征x和z内积的平方（时间复杂度是O(n)），就等价于计算映射后特征的内积。也就是说我们不需要花$O(n^2)$时间了(上面的转换过程还是看不懂，那是因为我们不知道原始空间如何映射的，下面由核函数反推映射函数)。
现在看一下映射函数（n=3时），根据上面的公式，得到
$$\phi (x)=\left[\begin{array}{c}{x}_1{x}_1\\ x_1{x}_2\\ x_1{x}_3\\ x_2{x}_1\\ x_2{x}_2\\ x_2{x}_3\\ x_3{x}_1\\ x_3{x}_2\\ x_3{x}_3\end{array}\right]$$
也就是说核函数$K(x,z)=(x^{T}z{)}^2$只能在选择这样的$\varphi$作为映射函数时才能够等价于映射后特征的内积。

再看一个核函数
$$K(x,z)=(x^{T}z+c{)}^2=\sum _{i=1}^n\sum _{j=1}^n[(x_i{x}_j)(z_i{z}_j)]+\sum _{i=1}^n[(\sqrt{2c}{x}_i)\sqrt{2c}{z}_i)]+c^2$$
对应的映射函数（n=3时）是
ϕ ( x ) = [ x 1 x 1 x 1 x 2 x 1 x 3 x 2 x 1 x 2 x 2 x 2 x 3 x 3 x 1 x 3 x 2 x 3 x 3 2 c x 1 2 c x 2 2 c x 3 c ] \phi(x)= \left[

$$\begin{matrix} x_1 x_1\\x_1 x_2\\x_1 x_3 \\x_2 x_1\\x_2 x_2\\x_2 x_3 \\x_3 x_1\\x_3 x_2\\x_3 x_3\\\sqrt{2c}x_1\\ \sqrt{2c}x_2\\ \sqrt{2c}x_3\\c\\ \end{matrix}$$ \right] ϕ(x)=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡​x1​x1​x1​x2​x1​x3​x2​x1​x2​x2​x2​x3​x3​x1​x3​x2​x3​x3​2c ​x1​2c ​x2​2c ​x3​c​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤​
更一般地，多项式核函数$K(x,z)=(x^{T}z+c{)}^d$对应的映射后特征维度为$\left(\begin{array}{c}n+d\\ d\end{array}\right)$。

由于计算的是内积，我们可以想到IR中的余弦相似度，如果x和z向量夹角越小，那么核函数值越大，反之，越小。因此，核函数值是$\varphi (x)$和$\varphi (z)$的相似度。
再看另外一个核函数–高斯径向核
$$K(x,z)=exp\left(-\frac{\Vert x-z{\Vert }^2}{2{\sigma }^2}\right)$$
这时，如果x和z很相近$(\Vert x-z\Vert \approx 0)$，那么核函数值为1，如果x和z相差很大$（\Vert x-z\Vert \gg 0）$，那么核函数值约等于0。由于这个函数类似于高斯分布，因此称为高斯核函数，也叫做径向基函数(Radial Basis Function 简称RBF)。它能够把原始特征映射到无穷维。
既然高斯核函数能够比较x和z的相似度，并映射到0到1，回想logistic回归，sigmoid函数可以，因此还有sigmoid核函数等等。
下面有张图说明在低维线性不可分时，映射到高维后就可分了，使用高斯核函数。

注意，使用核函数后，怎么分类新来的样本呢？
回想我们之前说过的
w T x + b = ∑ i = 1 m α i y i &lt; x i , x &gt; + b

$$\begin{matrix} w^Tx+b &amp;=&amp;\sum_{i=1}^m \alpha_iy_i&lt;x_i,x&gt; +b\\ \end{matrix}$$ wTx+b​=​∑i=1m​αi​yi​<xi​,x>+b​
现在只需将$\langle x_i,x\rangle$替换成$K(x_i,x)$，$\langle x_i,x\rangle$是在原始空间上算内积，$K(x_i,x)$，$\langle x_i,x\rangle$是将原始空间的样本代入到核函数计算。然后值的判断同上。

核函数有效性判定

请查阅原文

常见的核函数和如何选择核函数

要构造出一个具有良好性能的SVM，核函数的选择是关键也是最重要的一步．通常来讲核函数的选择包括两部分工作：一是核函数类型的选择，二是确定核函数类型后相关参数的选择。如何根据具体的数据选择恰当的核函数是SVM应用领域遇到的一个重大难题，也成为科研工作者所关注的焦点，但是目前还没有具体的理论或方法来指导核函数的选取。
核函数的定义并不困难，根据泛函的有关理论，只要一种函数$K(x_i,x_j)$满足Mercer条件，它就对应某一变换空间的内积。对于判断哪些函数是核函数到目前为止也取得了重要的突破，得到Mercer定理和以下常用的核函数类型：
线性核
线性内核是最简单的内核函数。 它由内积$<x，y>$加上可选的常数c给出。 使用线性内核的内核算法通常等于它们的非内核对应物，即具有线性内核的KPCA与标准PCA相同。
表达式 ： $k(x,y)=x^{T}y+c$
线性核，主要用于线性可分的情况，我们可以看到特征空间到输入空间的维度是一样的，其参数少速度快，对于线性可分数据，其分类效果很理想，因此我们通常首先尝试用线性核函数来做分类，看看效果如何，如果不行再换别的。
**多项式核函数 **
多项式核是非固定内核。 多项式内核非常适合于所有训练数据都归一化的问题。我记得一般都会把问题归一化吧？
表达式：$k（x，y）=（\alpha x^{T}y+c{）}^d,d>0$
可调参数是斜率$\alpha$，常数项$c$和多项式度$d$。
多项式核函数可以实现将低维的输入空间映射到高纬的特征空间，但是多项式核函数的参数多，当多项式的阶数比较高的时候，核矩阵的元素值将趋于无穷大或者无穷小，计算复杂度会大到无法计算。
**高斯核 **
高斯核是径向基函数核的一个例子。
$k(x,y)=exp(-\frac{||x-y|{|}^2}{2{\sigma }^2}),\sigma >0$
或者，它也可以使用来实现
$k(x,y)=exp(-\gamma ||x-y|{|}^2)$
可调参数$\sigma >0$在内核的性能中起着主要作用，并且应该仔细地调整到手头的问题。 如果过高估计，指数将几乎呈线性，高维投影将开始失去其非线性功率。 另一方面，如果低估，该函数将缺乏正则化，并且决策边界将对训练数据中的噪声高度敏感。
Gauss径向基函数则是局部性强的核函数，其外推能力随着参数$\sigma$的增大而减弱。多项式形式的核函数具有良好的全局性质，但局部性较差。
指数的内核
指数核与高斯核密切相关，只有正态的平方被忽略。 它也是一个径向基函数内核。
表达式：$k(x,y)=exp(-\frac{||x-y||}{2{\sigma }^2}),\sigma >0$
拉普拉斯算子核
拉普拉斯核心完全等同于指数内核，除了对$\sigma$参数的变化不那么敏感。 作为等价的，它也是一个径向基函数内核。
表达式：$k(x,y)=exp(-\frac{||x-y||}{\sigma }),\sigma >0$
重要的是注意，关于高斯内核的σ参数的观察也适用于指数和拉普拉斯内核。
Sigmoid核(sigmoid):
表达式：$k(x,y)=tanh(\beta x^{T}y+\theta ),\beta >0$
采用Sigmoid函数作为核函数时，支持向量机实现的就是一种多层感知器神经网络，应用SVM方法，隐含层节点数目(它确定神经网络的结构)、隐含层节点对输入节点的权值都是在设计(训练)的过程中自动确定的。而且支持向量机的理论基础决定了它最终求得的是全局最优值而不是局部最小值，也保证了它对于未知样本的良好泛化能力而不会出现过学习现象。
傅里叶核
表达式：$k(x,y)=\frac{1-q^2}{2(1-2qcos(x-y)-q^2)}$
样条核
表达式：$k(x,y)=B_{2n+1}(x-y)$

如何选择核函数

在选取核函数解决实际问题时，通常采用的方法有：

• 一是利用专家的先验知识预先选定核函数；
• 二是采用Cross-Validation方法，即在进行核函数选取时，分别试用不同的核函数，归纳误差最小的核函数就是最好的核函数．如针对傅立叶核、RBF核，结合信号处理问题中的函数回归问题，通过仿真实验，对比分析了在相同数据条件下，采用傅立叶核的SVM要比采用RBF核
  的SVM误差小很多．
• 三是采用由Smits等人提出的混合核函数方法，该方法较之前两者是目前选取核函数的主流方法，也是关于如何构造核函数的又一开创性的工作．将不同的核函数结合起来后会有更好的特性，这是混合核函数方法的基本思想．

经验一：
1）. Linear核：主要用于线性可分的情形。参数少，速度快，对于一般数据，分类效果已经很理想了。
2）. RBF核：主要用于线性不可分的情形。参数多，分类结果非常依赖于参数。有很多人是通过训练数据的交叉验证来寻找合适的参数，不过这个过程比较耗时。我个人的体会是：使用libsvm，默认参数，RBF核比Linear核效果稍差。通过进行大量参数的尝试，一般能找到比linear核更好的效果。
应用最广的应该就是RBF核了，无论是小样本还是大样本，高维还是低维等情况，RBF核函数均适用，它相比其他的函数有一下优点：
1）RBF核函数可以将一个样本映射到一个更高维的空间，而且线性核函数是RBF的一个特例，也就是说如果考虑使用RBF，那么就没有必要考虑线性核函数了。
2）与多项式核函数相比，RBF需要确定的参数要少，核函数参数的多少直接影响函数的复杂程度。另外，当多项式的阶数比较高时，核矩阵的元素值将趋于无穷大或无穷小，而RBF则在上，会减少数值的计算困难。
3）对于某些参数，RBF和sigmoid具有相似的性能。
经验二：

•    如果如果特征数远远大于样本数的情况下,使用线性核就可以了.
  1

•    如果特征数和样本数都很大,例如文档分类,一般使用线性核, LIBLINEAR比LIBSVM速度要快很多.
  1

•    如果特征数远小于样本数,这种情况一般使用RBF.但是如果一定要用线性核,则选择LIBLINEAR较好,而且使用-s 2选项。
  1

构造复杂的混合核函数

来源：支持向量机中核函数的选取方法的研究
如何从简单的核函数构造复杂的混合核函数,仍然满足于 Mercer定理

定理 设$K_1$和$K_2$是$X\times X$上的核,$X\subseteq R^n$.设常数$a>0$,则下面的函数均是核:

(i)$K(x,x^{\prime })=K_1(x,x^{\prime })+K_2(x,x^{\prime })$
(ii)$K(x^{\prime },x^{\prime })=a{K}_1(x,x^{\prime })$
(iii)$K(x,x^{\prime })=K_1(x,x^{\prime })K_2(x,x^{\prime })$

混合核函数能够兼顾其构成中的普通核函数的优势,得到性能更加优越的SvM的同时,仍存在着以下问题和困难:
①易出现构造的混合核函数比单一的普通核函数的性能差的情形,主要原因是混合核函数中的核参数过多,使得模型选择的困难增大及核参数的选取不当。如何根据待解决的问题筛选恰当的普通核函数来构造混合核函数,如何确定核参数的问题仍缺乏相应的理论指导
②在已选定用哪些普通核函数来构造混合核函数并确定核参数的情况下,如何根据具体的数据选择恰当的权参数$\rho$是尚待解决的难题

事实上,现有的这些核函数的选取方法,其本质上是先粗略的确定了核函数的类型,再通过已知的测试数据选取核参数,这已基本形成共识。但如何确定核函数的类型,成为核函数选取的关键。

选取规则1

首先,我们规定求解具体问题所选取的核函数为混合核函数,这是因为混合核函数较之其他普通核函数在性能上更具优越性,且有着巨大的应用潜力。同时也存在一个子问题,即选择哪些类型的普通核函数来构造混合核函数理想的结果是尽量采用较少类型的普通核函数来构造一个适应于多数问题的混合核函数在融入先验知识的基础上,我们通过分析对比上述常用核函数的特性来解决此问题。

在五种常用的核函数中,应用最广泛的是具有较好学习能力的RBF核函数,无论低维、高维、小样本、大样本等情况,RBF核函数均适应,具有较宽的收敛域,是较为理想的分类依据函数。Keerthi等人证明了线性核函数和多项式核函数是RBF核函数的特殊情况Lin等人说明了在某些参数情况下, Sigmoid核函数同RBF核函数具有相似的性能另外,与其他常用核函数相比,RBF核函数具有参数少的优点,易于掌握,其参数$\sigma$ 对SVM性能的优劣有着至关重要的影响。大量的数值实验表明,RBF核函数的学习能力随参数$\sigma$的增大而减弱。当$\sigma$过大会造成SVM的分类能力差且无较好的推广能力;当$\sigma$很小时,SVM对训练样本点的错误分类率虽为0,但对测试样本点的正确分类率低,即推广能力差;当$\sigma$过小时易出现“过拟合”现象。
下面给出选取RBF核函数的SVM(RBF-SVM)随参数$\sigma$变化时所具有的两个重要的性质:

性质1 若 RBF-SVM中的参数$\sigma \to 0$,则所有训练样本点$x_i,i=1,\dots \dots ,l$都是支持向量,且它们全部能被正确分类

性质2 若 RBF-SVM中的参数$\sigma \to \infty$,则其学习推广能力或对新样本点的正确判别能力为0,即它把所有的样本点都判为同一类。

由数学分析知识可知:任何连续函数都可以用多项式逼近;任何连续可微的周期性函数均可以展开成傅立叶级数由此可以设想用这两类核函数去逼近其它类型的核函数。多项式核函数具有较强的推广能力,并随阶数d的减小而增强当d过大时,函数集的VC维升高,学习机器的复杂性也提高,SVM的推广能力降低,易出现“过拟合”现象。而对于某些具有周期性,包含正弦(余弦)频率分量等特点的特殊问题,选取傅立叶核函数可使SVM的性能达到最优,并且只要其展开项数不多,“过拟合”现象很难产生但二者都有参数较为复杂的缺点。
综上所述,RBF核函数、多项式核函数和傅立叶核函数各自都有突出的优点且有很强的互补性,自然地可以想象用RBF核函数和比较简单的多项式核函数、傅立叶核函数的混合形式能够针对不同的实际问题构造出更为理想的核函数为了叙述方便,我们先引入如下符号
令
$$\begin{gathered} F_p^d=\left\{((x.x^{\prime })+1{)}^d|d>0\right\}， \\ {F}_R^{\sigma }=\left\{exp(-\frac{||x-x^{\prime }|{|}^2}{{\sigma }^2})|\sigma >0\right\}， \\ {F}_f^q=\left\{\frac{1-q^2}{2(1-2qcos(x-x^{\prime })+q^2)}|0<q<1\right\}， \\ {F}_{mix}^p=\left\{{\rho }_1{F}_p^d+{\rho }_2{F}_R^{\sigma }+{\rho }_3{F}_f^q|{\rho }_i\ge 0,\sum _{i=1}^3{\rho }_i=1,i=1,2,3\right\} \end{gathered}$$
其中,${\sigma }_i$称为权参数,代表着这三类核函数在混合核函数中占的比重。$d,\sigma ,q$称为核参数

**规则1:**取核函数$K(x,x^{\prime })\in F_{mix}^{\rho }$

选取规则2

在选取核参数之前,我们需要对多项式核函数的阶数$d$及傅立叶核函数的阶数$n$做出限定。二者的阶数不易过大,正如上文所述,阶数太大,二者各自的展开项越多,不仅增加了学习模型的复杂性,易出现“过拟合”现象,而且使SVM的推广性能降低因此,规定$d$(或$n$)的取值不超过3

规则2: d ≤ m i n { 3 , d i m { 训 练 集 } } , n ≤ m i n { 3 , d i m { 训 练 集 } } d≤min\{3,dim\{训练集\}\},n≤min\{3,dim\{训练集\}\} d≤min{3,dim{训练集}},n≤min{3,dim{训练集}}

选取规则3

确定了混合核函数后,核参数的选择也同样重要正如上文所分析,核参数选取的好坏直接影响着SVM的性能。正确的核参数选择可以使SVM恰当表征数据的内在结构,以达到最小化结构风险的目的。由于已选择的混合核函数:
$$K(x,x^{\prime })={\rho }_1(x\cdot x^{\prime })+1{)}^d+{\rho }_{2}exp(-\frac{||x-x^{\prime }|{|}^2}{2{\sigma }^2})+{\rho }_3\frac{1-q^2}{2(1-2qcos(x-x^{\prime })+q^2)}$$
中的参数比较复杂,所以按照每一部分又可单独作为一个核函数的特点,把参数选取分成两个步骤完成,即:首先,选取单一核的参数$(d,\sigma ,q)$;其次,选取权参数$({\rho }_1,{\rho }_2,{\rho }_3)$。下面针对$(d,\sigma ,q)$的选取给出规则3,针对$({\rho }_1,{\rho }_2,{\rho }_3)$的选取给出规则4.
令${\rho }_1=1,{\rho }_2={\rho }_3=0$,相当于仅选用单一的多项式核函数,此时用下面所给出的方法之一来选取最优的核参数$d$
方法一:已经被人们所熟悉的选取核参数的方法,主要有:①预先给定参数值;②交叉验证法;③网络搜索法;④改进的方法,如遗传算法等
方法二:本文采用董玉林提出的平衡约束规划(MPEO)模型来优化选取核参数。其思想是首先给出非线性SVM核参数优化选取的具有非光滑目标函数的平衡约束规划(MPEC)模型;其次,为了方便求解该模型,给出了它的光滑化近似模型,并且证明了原模型和光滑化模型之间的解存在一定的关系;最后给出了光滑化模型的最优性条件及求解算法,由此即可求得最优的核参数的值。
同理,令${\rho }_2=1,rh{o}_1={\rho }_3=0$,对单一的RBF核函数,采用同样的方法选取最优的核参数$\sigma$；
令${\rho }_3=1,{\rho }_1={\rho }_2=0$,对单一的傅立叶核函数,也采用相同的方法选取最优的核参数$q$
据上述分析,我们得到
规则3:$(d,\sigma ,q)$满足: d ∈ { 最 优 核 参 数 d ∣ ρ 1 = 1 , ρ 2 = ρ 3 = 0 } , σ ∈ { 最 优 核 参 数 σ ∣ ρ 2 = 0 , ρ 1 = ρ 3 = 0 } , q ∈ { 最 优 核 参 数 q ∣ ρ 3 = 1 , ρ 1 = ρ 2 = 0 } d∈\{最优核参数d|\rho_1=1,\rho_2=\rho_3=0\},\sigma∈\{最优核参数\sigma|\rho_2=0,\rho_1=\rho_3=0\},q∈\{最优核参数q|\rho_3=1,\rho_1=\rho_2=0\} d∈{最优核参数d∣ρ1​=1,ρ2​=ρ3​=0},σ∈{最优核参数σ∣ρ2​=0,ρ1​=ρ3​=0},q∈{最优核参数q∣ρ3​=1,ρ1​=ρ2​=0}

选取规则4

将规则3中已确定好的$(d,\sigma ,q)$代入混合核函数后,接下来要考虑哪一类型的核函数在混合中占主导地位,从而使得SVM具有最优的非线性处理能力,这取决于权参数${\rho }_i(i=1,2,3)$的选择。当$(d,\sigma ,q)$确定后,权参数实质上相当于混合核函数中的核参数,可采用效仿规则3中的方法进行选择(即选择方法一或方法二中的某种方法)
规则4:$({\rho }_1,{\rho }_2,{\rho }_3)$满足：

( ρ 1 , ρ 2 , ρ 3 ) ∈ { 最 优 权 参 数 ( ρ 1 , ρ 2 , ρ 3 ) ∣ ( d , σ , q 按 照 规 则 3 给 出 } (\rho_1,\rho_2,\rho_3)∈\{最优权参数(\rho_1,\rho_2,\rho_3)|(d,\sigma,q按照规则3给出\} (ρ1​,ρ2​,ρ3​)∈{最优权参数(ρ1​,ρ2​,ρ3​)∣(d,σ,q按照规则3给出}

以上4点选取规则,仅仅为解决核函数的选取问题提供一种思路。不同于传统意义上核函数的选取方法,采用本文给出的方法来确定的核函数更具有合理性,我们称该选取方法为RSM( Reasonable Selection Method)方法

核函数python编码：

def kernelTrans(X, A, kTup): #通过数据计算转换后的核函数
    #X是支持向量（因而数目不多，一行为一个样本），A是需要预测的样本，kTup用来选择核的类型，及其跟核相关的其它参数
    m,n = shape(X)
    K = mat(zeros((m,1)))
    if kTup[0]=='lin': #线性核函数
        K = X * A.T   #结果是m行一列，每一行是一个支持向量与新样本的内积
    
    elif kTup[0]=='rbf':#高斯核
        for j in range(m):
            deltaRow = X[j,:] - A
            K[j] = deltaRow*deltaRow.T
        K = exp(K/(-1*kTup[1]**2)) 
 
    elif kTup[0] == 'laplace':#拉普拉斯核
        for j in range(m):
            deltaRow = X[j,:] - A
            K[j] = deltaRow*deltaRow.T
            K[j] = sqrt(K[j])
        K = exp(-K/kTup[1])     
 
    elif kTup[0] == 'poly':#多项式核
        K = X * A.T
        for j in range(m):
            K[j] = K[j]**kTup[1]
        
    elif kTup[0] == 'sigmoid':#Sigmoid核
        K = X * A.T
        for j in range(m):
            K[j] = tanh(kTup[1]*K[j]+kTup[2])
        
    else: raise NameError('Houston We Have a Problem -- \
    That Kernel is not recognized')
    return K
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

规则化和不可分情况处理（Regularization and the non-separable case）

之前我们得到了支持向量机的目标函数及其约束
$$\begin{gathered} L(w,b,\alpha )=-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j<x_i,x_j>+\sum _{i=1}^m{\alpha }_i-----(6) \\ w=\sum _{i=1}^m{\alpha }_i{y}_i{x}_i-----(7) \\ \sum _{i=1}^m{\alpha }_i{y}_i=0-----(8) \\ {\alpha }_i(1-y_i(w^T{x}_i+b))=0-----(9) \\ {\alpha }_i\ge 0-----(10) \\ 1-y_i(w^T{x}_i+b)\le 0-----(11) \end{gathered}$$
之前讨论的情况都是建立在样例线性可分的假设上，当样例线性不可分时，我们可以尝试使用核函数来将特征映射到高维，这样很可能就可分了。然而，映射后我们也不能100%保证可分。那怎么办呢，我们需要将模型进行调整，以保证在不可分的情况下，也能够尽可能地找出分隔超平面。
看下面两张图：

可以看到一个离群点（可能是噪声）可以造成超平面的移动，间隔缩小，可见以前的模型对噪声非常敏感。再有甚者，如果离群点在另外一个类中，那么这时候就是线性不可分了。
这时候我们应该允许一些点游离并在在模型中违背限制条件（函数间隔大于1）。我们设计得到新的模型如下（也称软间隔）：
KaTeX parse error: Expected 'EOF', got '\ ' at position 52: …_{i=1}^m\xi_i\\\̲ ̲s.t ~~~ y_i(w^T…
引入非负参数${\xi }_i$后（称为松弛变量），就允许某些样本点的函数间隔小于1，即在最大间隔区间里面，或者函数间隔是负数，即样本点在对方的区域中。而放松限制条件后，我们需要重新调整目标函数，以对离群点进行处罚，目标函数后面加上的$C{\sum }_{i=1}^m{\xi }_i$就表示离群点越多，目标函数值越大，而我们要求的是尽可能小的目标函数值。这里的C是离群点的权重，C越大表明离群点对目标函数影响越大，也就是越不希望看到离群点。我们看到，目标函数控制了离群点的数目和程度，使大部分样本点仍然遵守限制条件。
模型修改后，拉格朗日公式也要修改如下：
$$L(w,b,\xi ,\alpha ,\gamma )=\frac{1}{2}||w|{|}^2+C\sum _{i=1}^m{\xi }_i+\sum _{i=1}^m{\alpha }_i(1-{\xi }_i-y_i(w^T{x}_i+b))-\sum _{i=1}^m{\gamma }_i{\xi }_i$$
这里的${\alpha }_i$和${\gamma }_i$都是拉格朗日乘子，回想我们在拉格朗日对偶中提到的求法，先写出拉格朗日公式（如上），然后将其看作是变量w和b的函数，分别对其求偏导，得到w和b的表达式。
$$\begin{gathered} \frac{\partial L}{\partial w}=w-\sum _{i=1}^m{\alpha }_i{y}_i{x}_i=0 \\ \frac{\partial L}{\partial b}=\sum _{i=1}^m{\alpha }_i{y}_i=0 \\ \frac{\partial L}{\partial {\xi }_i}=C-{\alpha }_i-{\gamma }_i=0 \end{gathered}$$
即
$$\begin{gathered} w=\sum _{i=1}^m{\alpha }_i{y}_i{x}_i \\ \sum _{i=1}^m{\alpha }_i{y}_i=0 \\ C-{\alpha }_i-{\gamma }_i=0 \end{gathered}$$
然后代入公式中，求带入后公式的极大值。整个推导过程类似以前的模型，这里只写出最后结果如下：
$$\begin{gathered} ma{x}_{\alpha }\psi (\alpha )=ma{x}_{\alpha }-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j<x_i,x_j>+\sum _{i=1}^m{\alpha }_i-----(12) \\ {\alpha }_i\ge 0-----(13) \\ \sum _{i=1}^m{\alpha }_i{y}_i=0-----(14) \\ {\gamma }_i\ge 0---(15) \\ C-{\alpha }_i-{\gamma }_i=0---(16) \end{gathered}$$
即
$$\begin{gathered} mi{n}_{\alpha }\psi (\alpha )=mi{n}_{\alpha }\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j<x_i,x_j>-\sum _{i=1}^m{\alpha }_i-----(12) \\ {\alpha }_i\ge 0-----(13) \\ \sum _{i=1}^m{\alpha }_i{y}_i=0-----(14) \\ {\gamma }_i\ge 0---(15) \\ C-{\alpha }_i-{\gamma }_i=0---(16) \end{gathered}$$
当然还有其他的一些表达式，这里只列举了与最后类别判断有关的（都是围绕着${\alpha }_i$的计算）。
此时，我们发现没有了参数${\xi }_i$，与之前模型唯一不同在于${\alpha }_i$又多了的限制条件${\alpha }_i\le C$。即由(13)和(16)式
可以得到
$$0\le {\alpha }_i\le C$$
需要提醒的是，$b$的求值公式也发生了改变，改变结果在SMO算法里面介绍。
前面根据KKT条件我们得到一个结论，只有在支持向量处${\alpha }_i$才不等于0。这里需要作一些变化。
$$\begin{gathered} {\alpha }_i=0⟺y_i(w^T{x}_i+b)\ge 1 \\ {\alpha }_i=C⟺y_i(w^T{x}_i+b)\le 1 \\ 0<{\alpha }_i<C⟺y_i(w^T{x}_i+b)=1 \end{gathered}$$
这个KKT条件说明，在两条间隔线外面的点，对应前面的系数为0，在两条间隔线里面的对应为C，在两条间隔线上的对应的系数在0和C之间。通过KKT条件可知，某些在最大间隔线上的样本点也不是支持向量，相反也可能是离群点。

坐标上升法（Coordinate ascent）

在最后讨论$w(\alpha )$的求解之前，我们先看看坐标上升法的基本原理。假设要求解下面的优化问题：
$ma{x}_{\alpha }w({\alpha }_1,{\alpha }_2,\dots ,{\alpha }_m)$
这里$w$是向量的函数。之前我们在回归中提到过两种求最优解的方法，一种是梯度下降法，另外一种是牛顿法。现在我们再讲一种方法称为坐标上升法（求解最小值问题时，称作坐标下降法，原理一样）。
方法过程：

Loop until convergence:{
     ~~~~     For i=1,…,m,{
     ~~~~           ~~~~     ${\alpha }_i:=argma{x}_{{\alpha }_i}w({\alpha }_1,\dots ,{\alpha }_{i-1},{\alpha }_i,{\alpha }_{i+1},\dots ,{\alpha }_m)$
     ~~~~     }
}
最里面语句的意思是固定除${\alpha }_i$之外的所有${\alpha }_j$，这时$W$可看作只是关于${\alpha }_i$的函数，那么直接对${\alpha }_i$求导优化即可。这里我们进行最大化求导的顺序i是从1到m，可以通过更改优化顺序来使$w$能够更快地增加并收敛。如果$w$在内循环中能够很快地达到最优，那么坐标上升法会是一个很高效的求极值方法。
下面通过一张图来展示：

椭圆代表了二次函数的各个等高线，变量数为2，起始坐标是(2,-2)。图中的直线式迭代优化的路径，可以看到每一步都会向最优值前进一步，而且前进路线是平行于坐标轴的，因为每一步只优化一个变量。

SMO优化算法（Sequential minimal optimization）

SMO算法由Microsoft Research的John C. Platt在1998年提出，并成为最快的二次规划优化算法，特别针对线性SVM和数据稀疏时性能更优。关于SMO最好的资料就是他本人写的《Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machines》了。
下面先说讲义上对此方法的总结。
首先回到我们前面一直悬而未解的问题，对偶函数最后的优化问题：
$$\begin{gathered} mi{n}_{\alpha }\psi (\alpha )=mi{n}_{\alpha }\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j<x_i,x_j>-\sum _{i=1}^m{\alpha }_i \\ {\alpha }_i\ge 0 \\ \sum _{i=1}^m{\alpha }_i{y}_i=0 \\ {\alpha }_i=0⟺y_i(w^T{x}_i+b)\ge 1 \\ {\alpha }_i=C⟺y_i(w^T{x}_i+b)\le 1 \\ 0<{\alpha }_i<C⟺y_i(w^T{x}_i+b)=1 \end{gathered}$$
推广到更一般的情况，即带核函数的情形。同时用$u_i$表示$y_i(w^T{x}_i+b)$
$$\begin{gathered} mi{n}_{\alpha }\psi (\alpha )=mi{n}_{\alpha }\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,x_j)-\sum _{i=1}^m{\alpha }_i---(15) \\ {\alpha }_i\ge 0 \\ \sum _{i=1}^m{\alpha }_i{y}_i=0 \\ {\alpha }_i=0⟺y_i{u}_i\ge 1 \\ {\alpha }_i=C⟺y_i{u}_i\le 1 \\ 0<{\alpha }_i<C⟺y_i{u}_i=1 \end{gathered}$$
同时有下面的关系式：（还需要进一步核查）
$$\begin{gathered} W^{\ast }=W=\sum _{i=1}^m{\alpha }_i{y}_i{x}_i \\ {b}^{\ast }=b=y_j-\sum _{i=1}^m{\alpha }_i{y}_i⟨x_i,x_j⟩ \\ =-\frac{ma{x}_{i:y_i=-1}{W}^{\ast T}{x}_i+mi{n}_{i:y_i=1}{W}^{\ast T}{x}_i}{2} \\ {W}^{T}x+b=(\sum _{i=1}^m{\alpha }_i{y}_i{x}_i{)}^{T}x+b=\sum _{i=1}^m{\alpha }_i{y}_i⟨x_i,x⟩+b \end{gathered}$$

上式中$W$表示对偶问题的解，$W^{\ast }$表示原问题的解。b的表达式说明离超平面最近的正的函数间隔要等于离超平面最近的负的函数间隔。
按照之前的方法，新来一个样本，要判断其类别，需要根据$W$和$b$做一次线性运算，然后看$W^{T}x+b$结果是大于0还是小于0。现在则可以根据${\alpha }_i$，并将新样本与全体样本做内积即可计算出$W^{T}x+b$的正负。表面上似乎没有减少什么计算量，但是，由于只有支持向量以内的样本对应的${\alpha }_i>0$，其他${\alpha }_i=0$，所以只需要将新来的样本与少数向量做内积即可。
SMO优化算法（Sequential minimal optimization）
现在要解决的是在参数 { α 1 , α 2 , … , α m } \{\alpha_1,\alpha_2,\dots,\alpha_m\} {α1​,α2​,…,αm​}上求最大值$\psi$的问题，至于$x_i$和$y_i$都是已知数。C由我们预先设定，也是已知数。
按照坐标上升的思路，我们首先固定${\alpha }_1$除以外的所有参数，然后在${\alpha }_1$上求极值。等一下，这个思路有问题，因为如果固定${\alpha }_1$以外的所有参数，那么${\alpha }_1$将不再是变量（可以由其他值推出），因为问题中规定了
$${\alpha }_1{y}_1=-\sum _{i=2}^m{\alpha }_i{y}_i$$
因此，我们需要一次选取两个参数做优化，比如${\alpha }_1$和${\alpha }_2$，此时${\alpha }_2$可以由${\alpha }_1$和其他参数表示出来。这样回带到$w$中，$w$就只是关于${\alpha }_1$的函数了，可解。
SMO的主要步骤如下：

Repeat until convergence:{
1.Select some pair ${\alpha }_i$ and ${\alpha }_j$ to update next (using a heuristic that tries to pick the two that will allow us to make the biggest progess towards the global maximum).
2.Reoptimize $W(\alpha )$ with respect to ${\alpha }_i$ and ${\alpha }_j$ ,while holding all the other ${\alpha }_k^{{}^{\prime }}s(k̸=i,j)$ fixed.
}
意思是：
第一步选取一对${\alpha }_i$和${\alpha }_j$，选取方法使用启发式方法（后面讲）。
第二步，固定除${\alpha }_i$和${\alpha }_j$之外的其他参数，确定$w$极值条件下的${\alpha }_i$，${\alpha }_j$由${\alpha }_i$表示。
SMO之所以高效就是因为在固定其他参数后，对一个参数优化过程很高效。

下面讨论具体方法：

拉格朗日乘子的取值范围

假设我们选取的初始值 { α 1 , α 2 , ⋯ &ThinSpace; , α m } \{\alpha_1,\alpha_2,\cdots,\alpha_m\} {α1​,α2​,⋯,αm​}满足了问题中的约束条件。接下来，我们固定 { α 3 , α 4 , ⋯ &ThinSpace; , α m } \{\alpha_3,\alpha_4,\cdots,\alpha_m\} {α3​,α4​,⋯,αm​}，固定其他变量，先求一部分变量，这是坐标上升法的思想，具体过程后面再给出，这样W就是${\alpha }_1$和${\alpha }_2$的函数。并且${\alpha }_1$和${\alpha }_2$满足条件：
$${\alpha }_1+{\alpha }_2=-\sum _{i=3}^m{\alpha }_i{y}_i$$
由于 { α 3 , α 4 , ⋯ &ThinSpace; , α m } \{\alpha_3,\alpha_4,\cdots,\alpha_m\} {α3​,α4​,⋯,αm​}都是已知固定值，因此为了方便，可将等式右边标记成实数值$\zeta$。
$${\alpha }_1+{\alpha }_2=\zeta$$
当${\alpha }_1$和${\alpha }_2$异号时，也就是一个为1，一个为-1时，他们可以表示成一条直线，斜率为1;当${\alpha }_1$和${\alpha }_2$同号时，也就是同为1，或同为-1时，他们斜率为-1。如下图：

横轴是${\alpha }_1$，纵轴是${\alpha }_2$，${\alpha }_1$和${\alpha }_2$既要在矩形方框内，也要在直线上。
如果只把${\alpha }_2$作为变量
(1)$y_1$和$y_2$同号，此时
当${\alpha }_2-{\alpha }_1<0$时，${\alpha }_2$的取值范围为$[0,C+k]$，即$[0,C+{\alpha }_2-{\alpha }_1]$；
当${\alpha }_2-{\alpha }_1\ge 0$时，${\alpha }_2$的取值范围为$[k,C]$，即$[{\alpha }_2-{\alpha }_1,C]$；
将上面两种情况合并起来就是
${\alpha }_2$的取值范围为$[max(0,{\alpha }_2-{\alpha }_1),min(C,C+{\alpha }_2-{\alpha }_1)]$；
(2)$y_1$和$y_2$异号，此时
当${\alpha }_2+{\alpha }_1<C$时，${\alpha }_2$的取值范围为$[0,k]$,即$[0,{\alpha }_2+{\alpha }_1]$；
当${\alpha }_2+{\alpha }_1\ge C$时，${\alpha }_2$的取值范围为$[k,C]$,即$[{\alpha }_2+{\alpha }_1-C,C]$；
将上面两种情况合并起来就是
${\alpha }_2$的取值范围为$[max(0,{\alpha }_2+{\alpha }_1-C),min(C,{\alpha }_2+{\alpha }_1)]$；
把(1)(2)统一表示为
$$\begin{gathered} L\le {\alpha }_2\le H \\ 当y_1和y_2同号时： \\ L=max(0,{\alpha }_2-{\alpha }_1) \\ H=min(C,C+{\alpha }_2-{\alpha }_1) \\ 当y_1和y_2异号时： \\ L=max(0,{\alpha }_2+{\alpha }_1-C) \\ H=min(C,C+{\alpha }_2+{\alpha }_1) \end{gathered}$$

目标函数的变形

将${\alpha }_1$用${\alpha }_2$来表示，
$${\alpha }_1=（\zeta -{\alpha }_2{y}_1）y_1=\zeta y_1-{\alpha }_2{y}_1{y}_1$$
将${\alpha }_1$代入目标函数
$$MA{X}_{\alpha }W(\alpha )=\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{y}_i{y}_j{\alpha }_i{\alpha }_j⟨x_i,x_j⟩$$
目标函数可转化成下面的形式（大概看一下就可以知道）
$$W(\alpha )=a{\alpha }_2^2+b{\alpha }_2+c——（2）$$
式中$a,b,c$均为固定值，由已知样本和固定的拉格朗日乘子给出，具体推导过程下面马上给出。

拉格朗日乘子的更新

（2）式对${\alpha }_2$进行求导并令导数为0，可以得到极值点处的${\alpha }_2$，但是要保证$L\le {\alpha }_2\le H$，我们可以使用${\alpha }_2^{new}$表示极值点处的${\alpha }_2$。最后${\alpha }_2$的取值要由下式来确定。
α 2 n e w = { L i f α 2 n e w ≤ L α 2 n e w i f L &lt; α 2 n e w &lt; H H i f α 2 n e w ≥ H \alpha_2^{new}=\left\{

$$\begin{matrix} L&amp;if&amp;\alpha_2^{new}\leq L\\ \alpha_2^{new}&amp;if&amp;L&lt;\alpha_2^{new}&lt; H\\ H&amp;if&amp;\alpha_2^{new}\geq H \end{matrix}$$ \right. α2new​=⎩⎨⎧​Lα2new​H​ififif​α2new​≤LL<α2new​<Hα2new​≥H​
这样得到${\alpha }_2^{new}$后，我们可以得到${\alpha }_1$的新值${\alpha }_1^{new}$。
下面进行具体计算：
我们将重新计算(2)式，同时我们将核函数引入。
$$\begin{gathered} MA{X}_{\alpha }W(\alpha )=\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{y}_i{y}_j{\alpha }_i{\alpha }_{j}K⟨x_i,x_j⟩ \\ ⟺ \\ MI{N}_{\alpha }W(\alpha )=\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{y}_i{y}_{j}K⟨x_i,x_j⟩{\alpha }_i{\alpha }_j-\sum _{i=1}^m{\alpha }_i \end{gathered}$$
$W(\alpha )$可推导如下：

W ( α ) = 1 2 ∑ i = 1 m [ y i y 1 K ⟨ x i , x 1 ⟩ α i α 1 + y i y 1 K ⟨ x i , x 1 ⟩ α i α 2 + ∑ j = 3 m y i y j K ⟨ x i , x j ⟩ α i α j ] − α 1 − α 2 − ∑ i = 3 m α i = 1 2 [ y 1 y 1 K ⟨ x 1 , x 1 ⟩ α 1 α 1 + y 1 y 1 K ⟨ x 1 , x 1 ⟩ α 2 α 1 + ∑ i = 3 m y i y 1 K ⟨ x i , x 1 ⟩ α i α 1 ] + 1 2 [ y 1 y 1 K ⟨ x 1 , x 1 ⟩ α 1 α 2 + y 1 y 1 K ⟨ x 1 , x 1 ⟩ α 2 α 2 + ∑ i = 3 m y i y 1 K ⟨ x i , x 1 ⟩ α i α 2 ] + 1 2 [ ∑ j = 3 m y 1 y j K ⟨ x 1 , x j ⟩ α 1 α j + ∑ j = 3 m y 1 y j K ⟨ x 1 , x j ⟩ α 2 α j + ∑ i = 3 m ∑ j = 3 m y i y j K ⟨ x i , x j ⟩ α i α j ] − α 1 − α 2 − ∑ i = 3 m α i = 1 2 K ⟨ x 1 , x 1 ⟩ α 1 2 + 1 2 K ⟨ x 1 , x 1 ⟩ α 2 2 + y 1 y 1 K ⟨ x 1 , x 1 ⟩ α 1 α 2 + y 1 α 1 ∑ j = 3 m y j K ⟨ x 1 , x j ⟩ α j + y 1 α 2 ∑ j = 3 m y j K ⟨ x 1 , x j ⟩ α j − α 1 − α 2 + 1 2 ∑ i = 3 m ∑ j = 3 m y i y j K ⟨ x i , x j ⟩ α i α j − ∑ i = 3 m α i

$$\begin{matrix} W(\alpha)&amp;=&amp;\frac{1}{2} \sum_{i=1}^m \left[ y_iy_1K\langle x_i,x_1\rangle\alpha_i \alpha_1 + y_iy_1K\langle x_i,x_1\rangle\alpha_i \alpha_2 + \sum_{j=3}^m y_iy_jK\langle x_i,x_j\rangle\alpha_i \alpha_j \right] -\alpha_1-\alpha_2-\sum_{i=3}^m \alpha_i \\ &amp;=&amp;\frac{1}{2} \left[ y_1y_1K\langle x_1,x_1\rangle\alpha_1 \alpha_1 +y_1y_1K\langle x_1,x_1\rangle\alpha_2 \alpha_1 + \sum_{i=3}^m y_iy_1K\langle x_i,x_1\rangle\alpha_i \alpha_1 \right ] +\frac{1}{2} \left[ y_1y_1K\langle x_1,x_1\rangle\alpha_1 \alpha_2 + y_1y_1K\langle x_1,x_1\rangle\alpha_2 \alpha_2 + \sum_{i=3}^m y_iy_1K\langle x_i,x_1\rangle\alpha_i \alpha_2 \right] +\frac{1}{2} \left[ \sum_{j=3}^m y_1y_jK\langle x_1,x_j\rangle\alpha_1 \alpha_j + \sum_{j=3}^m y_1y_jK\langle x_1,x_j\rangle\alpha_2 \alpha_j + \sum_{i=3}^m \sum_{j=3}^m y_iy_jK\langle x_i,x_j\rangle\alpha_i \alpha_j \right] -\alpha_1-\alpha_2-\sum_{i=3}^m \alpha_i \\ &amp;=&amp;\frac{1}{2} K\langle x_1,x_1\rangle\alpha_1^2 +\frac{1}{2} K\langle x_1,x_1\rangle\alpha_2^2 +y_1y_1K\langle x_1,x_1\rangle\alpha_1 \alpha_2 + y_1 \alpha_1 \sum_{j=3}^m y_jK\langle x_1,x_j\rangle \alpha_j + y_1 \alpha_2 \sum_{j=3}^m y_jK\langle x_1,x_j\rangle \alpha_j -\alpha_1-\alpha_2+\frac{1}{2} \sum_{i=3}^m \sum_{j=3}^m y_iy_jK\langle x_i,x_j\rangle\alpha_i \alpha_j -\sum_{i=3}^m \alpha_i\\ \end{matrix}$$ W(α)​===​21​∑i=1m​[yi​y1​K⟨xi​,x1​⟩αi​α1​+yi​y1​K⟨xi​,x1​⟩αi​α2​+∑j=3m​yi​yj​K⟨xi​,xj​⟩αi​αj​]−α1​−α2​−∑i=3m​αi​21​[y1​y1​K⟨x1​,x1​⟩α1​α1​+y1​y1​K⟨x1​,x1​⟩α2​α1​+∑i=3m​yi​y1​K⟨xi​,x1​⟩αi​α1​]+21​[y1​y1​K⟨x1​,x1​⟩α1​α2​+y1​y1​K⟨x1​,x1​⟩α2​α2​+∑i=3m​yi​y1​K⟨xi​,x1​⟩αi​α2​]+21​[∑j=3m​y1​yj​K⟨x1​,xj​⟩α1​αj​+∑j=3m​y1​yj​K⟨x1​,xj​⟩α2​αj​+∑i=3m​∑j=3m​yi​yj​K⟨xi​,xj​⟩αi​αj​]−α1​−α2​−∑i=3m​αi​21​K⟨x1​,x1​⟩α12​+21​K⟨x1​,x1​⟩α22​+y1​y1​K⟨x1​,x1​⟩α1​α2​+y1​α1​∑j=3m​yj​K⟨x1​,xj​⟩αj​+y1​α2​∑j=3m​yj​K⟨x1​,xj​⟩αj​−α1​−α2​+21​∑i=3m​∑j=3m​yi​yj​K⟨xi​,xj​⟩αi​αj​−∑i=3m​αi​​

为了便于书写和推导，我们作一些字符替换，不防令
$$\begin{gathered} K⟨x_i,x_j⟩=K_{ij} \\ \sum _{j=3}^m{y}_{j}K⟨x_i,x_j⟩{\alpha }_j=v_i \\ {y}_i{y}_j=S_{ij} \\ \frac{1}{2}\sum _{i=3}^m\sum _{j=3}^m{y}_i{y}_{j}K⟨x_i,x_j⟩{\alpha }_i{\alpha }_j-\sum _{i=3}^m{\alpha }_i=W_{constant} \end{gathered}$$
则$W(\alpha )$可简写如下：
$$
W(\alpha)=\frac{1}{2} K_{11} \alpha_1^2 +\frac{1}{2} K_{22} \alpha_2^2 +S_{12}K_{12}\alpha_1 \alpha_2 \

• y_1 \alpha_1 v_1 + y_1 \alpha_2 v_2 \
  -\alpha_1-\alpha_2\
  +W_{constant}\
  $$

下面我们将${\alpha }_1$用${\alpha }_2$来表示。注意下面表达式的演化，后面将反复用到这种关系。
y 1 α 1 + y 1 α 2 = − ∑ i = 3 m y i α i ⟹ α 1 + S 12 α 2 = − y 1 ∑ i = 3 m y i α i   = − y 1 ∑ i = 3 m y i α i ∗   = α 1 ∗ + S 12 α 2 ∗

$$\begin{matrix} y_1 \alpha_1 + y_1 \alpha_2&amp;=&amp;-\sum_{i=3}^m y_i \alpha_i\\ \Longrightarrow\alpha_1 + S_{12}\alpha_2&amp;=&amp;-y_1\sum_{i=3}^m y_i \alpha_i\\ ~&amp;=&amp;-y_1\sum_{i=3}^m y_i \alpha_i^*\\ ~&amp;=&amp;\alpha_1^* + S_{12}\alpha_2^*\\ \end{matrix}$$ y1​α1​+y1​α2​⟹α1​+S12​α2​  ​====​−∑i=3m​yi​αi​−y1​∑i=3m​yi​αi​−y1​∑i=3m​yi​αi∗​α1∗​+S12​α2∗​​
上式中，${\alpha }_1^{\ast }$和${\alpha }_2^{\ast }$均表示迭代前的值，为固定值。我们暂时用$A$来表示，$A=-y_1{\sum }_{i=3}^m{y}_i{\alpha }_i=-y_1{\sum }_{i=3}^m{y}_i{\alpha }_i^{\ast }$，则$ \alpha_1 $可表示成
$${\alpha }_1=A-S_{12}{\alpha }_2$$
将${\alpha }_1$代入$W(\alpha )$，则有
$$\begin{array}{ccc}W(\alpha )& =& \frac{1}{2}{K}_{11}(A-S_{12}{\alpha }_2{)}^2+\frac{1}{2}{K}_{22}{\alpha }_2^2+S_{12}{K}_{12}（A-S_{12}{\alpha }_2）{\alpha }_2\\ & & +y_1(A-S_{12}{\alpha }_2)v_1+y_1{\alpha }_2{v}_2\\ & & -(A-S_{12}{\alpha }_2)-{\alpha }_2\\ & & +W_{constant}\end{array}$$

现在对上式求导，则有
d W d α 2 = ( − S 12 ) K 11 ( A − S 12 α 2 ) + K 22 α 2 + S 12 K 12 （ − S 12 ） α 2 + S 12 K 12 （ A − S 12 α 2 ） + y 1 ( − S 12 ) v 1 + y 1 v 2 − ( − S 12 ) − 1 = − S 12 K 11 A + K 11 α 2 + K 22 α 2 − K 12 α 2 + S 12 K 12 A − K 12 α 2 − y 1 S 12 v 1 + y 1 v 2 = ( K 11 − 2 K 12 + K 22 ) α 2 − S 12 A ( K 11 − K 12 ) − y 1 ( v 1 − v 2 ) − ( − S 12 ) − 1

$$\begin{matrix} \frac{d_W}{d_{\alpha_2}}&amp;=&amp;(-S_{12}) K_{11} (A-S_{12}\alpha_2) + K_{22} \alpha_2 +S_{12}K_{12} （-S_{12}） \alpha_2 +S_{12}K_{12} （A-S_{12}\alpha_2） \\ &amp;&amp;+ y_1 (-S_{12}) v_1 + y_1 v_2 \\ &amp;&amp;-(-S_{12})-1\\ &amp;=&amp;-S_{12}K_{11} A +K_{11} \alpha_2 + K_{22} \alpha_2 - K_{12} \alpha_2 +S_{12}K_{12} A - K_{12} \alpha_2 -y_1 S_{12} v_1 + y_1 v_2 \\ &amp;=&amp;(K_{11} - 2 K_{12} +K_{22} )\alpha_2 -S_{12} A (K_{11} -K_{12} ) -y_1 (v_1- v_2 ) -(-S_{12})-1\\ \end{matrix}$$ dα2​​dW​​​===​(−S12​)K11​(A−S12​α2​)+K22​α2​+S12​K12​（−S12​）α2​+S12​K12​（A−S12​α2​）+y1​(−S12​)v1​+y1​v2​−(−S12​)−1−S12​K11​A+K11​α2​+K22​α2​−K12​α2​+S12​K12​A−K12​α2​−y1​S12​v1​+y1​v2​(K11​−2K12​+K22​)α2​−S12​A(K11​−K12​)−y1​(v1​−v2​)−(−S12​)−1​
求导过程中要注意，$v_i$的表达式中只有$i\ge 3$时的${\alpha }_i$值，因而是一个固定值。
下面将
$S_{12}=y_1{y}_1$、
$A=-y_1{\sum }_{i=3}^m{y}_i{\alpha }_i={\alpha }_1^{\ast }+S_{12}{\alpha }_2^{\ast }$
和
$$\begin{array}{ccc}{v}_i& =& {\sum }_{j=3}^m{y}_{j}K⟨x_i,x_j⟩{\alpha }_j\\ & =& {\sum }_{j=3}^m{y}_{j}K⟨x_i,x_j⟩{\alpha }_j^{\ast }\\ & =& u_i^{\ast }-y_{1}K⟨x_i,x_1⟩{\alpha }_1^{\ast }-y_{1}K⟨x_i,x_1⟩{\alpha }_2^{\ast }-b^{\ast }\end{array}$$
上式中$u_i={\sum }_{j=1}^m{y}_{j}K⟨x_i,x_j⟩{\alpha }_j+b$，$u_i$就是我们用来判断新样本类别的公式。
将上面三式代回$\frac{d_W}{d_{{\alpha }_2}}$，可得（这里将值代入的时候有一个技巧:由于后面是要求导数等于0的，因而我们要尽可能用迭代前的值即带*号的变量代入。）
$$\begin{array}{ccc}\frac{d_W}{d_{{\alpha }_2}}& =& (K_{11}-2K_{12}+K_{22}){\alpha }_2-S_{12}C(K_{11}-K_{12})-y_1(v_1-v_2)-(-S_{12})-1\\ & =& (K_{11}-2K_{12}+K_{22}){\alpha }_2-S_{12}({\alpha }_1^{\ast }+S_{12}{\alpha }_2^{\ast })(K_{11}-K_{12})-y_1[(u_1^{\ast }-y_{1}K⟨x_1,x_1⟩{\alpha }_1^{\ast }-y_{1}K⟨x_1,x_1⟩{\alpha }_2^{\ast }-b^{\ast })-(u_2^{\ast }-y_{1}K⟨x_1,x_1⟩{\alpha }_1^{\ast }-y_{1}K⟨x_1,x_1⟩{\alpha }_2^{\ast }-b^{\ast })]-(-y_1{y}_1)-y_1{y}_1\\ & =& (K_{11}-2K_{12}+K_{22}){\alpha }_2-（y_1{y}_1{\alpha }_1^{\ast }+{\alpha }_2^{\ast }）(K_{11}-K_{12})-y_1[(u_1^{\ast }-u_2^{\ast }-y_1(K_{11}-K_{12}){\alpha }_1^{\ast }-y_1(K_{12}-K_{22}){\alpha }_2^{\ast }]-(-y_1{y}_1)-y_1{y}_1\\ & =& (K_{11}-2K_{12}+K_{22}){\alpha }_2-y_1(u_1^{\ast }-u_2^{\ast })-\left[（y_1{y}_1{\alpha }_1^{\ast }+{\alpha }_2^{\ast }）(K_{11}-K_{12})-y_1{y}_1(K_{11}-K_{12}){\alpha }_1^{\ast }-(K_{12}-K_{22}){\alpha }_2^{\ast }\right]-(-y_1{y}_1)-y_1{y}_1\\ & =& (K_{11}-2K_{12}+K_{22}){\alpha }_2-y_1(u_1^{\ast }-y_1-u_2^{\ast }+y_1)-\left[y_1{y}_1{\alpha }_1^{\ast }{K}_{11}+{\alpha }_2^{\ast }{K}_{11}-y_1{y}_1{\alpha }_1^{\ast }{K}_{12}-{\alpha }_2^{\ast }{K}_{12}-y_1{y}_1{K}_{11}{\alpha }_1^{\ast }+y_1{y}_1{K}_{12}{\alpha }_1^{\ast }-K_{12}{\alpha }_2^{\ast }+K_{22}{\alpha }_2^{\ast }\right]\\ & =& (K_{11}-2K_{12}+K_{22}){\alpha }_2-y_1(u_1^{\ast }-y_1-u_2^{\ast }+y_1)-\left[{\alpha }_2^{\ast }{K}_{11}-{\alpha }_2^{\ast }{K}_{12}-K_{12}{\alpha }_2^{\ast }+K_{22}{\alpha }_2^{\ast }\right]\\ & =& (K_{11}-2K_{12}+K_{22}){\alpha }_2-y_1(E_1-E_2)-(K_{11}-2K_{12}+K_{22}){\alpha }_2^{\ast }\end{array}$$
式中$E_i=u_i^{\ast }-y_i$；
令导数为0,则有
$$(K_{11}-2K_{12}+K_{22}){\alpha }_2=(K_{11}-2K_{12}+K_{22}){\alpha }_2^{\ast }+y_1(E_1^{\ast }-E_2^{\ast })$$
用$\eta=K_{11} - 2 K_{12} +K_{22} $同除等式两边得到
$${\alpha }_2={\alpha }_2^{\ast }+\frac{y_1(E_1^{\ast }-E_2^{\ast })}{\eta }$$
为了与原论文一致，这里仍然用${\alpha }_2$表示迭代前的值，${\alpha }_2^{new}$表示迭代后的值，则上式可重新表示如下：
$${\alpha }_2^{new}={\alpha }_2+\frac{y_1(E_1-E_2)}{\eta }$$
加入边界约束后，有如下表达式：
$${\alpha }_2^{new,clipped}=\{\begin{array}{ccc}L& if& {\alpha }_2^{new}\le L\\ {\alpha }_2^{new}& if& L<{\alpha }_2^{new}<H\\ H& if& {\alpha }_2^{new}\ge H\end{array}$$
由于
$${\alpha }_1+S_{12}{\alpha }_2={\alpha }_1^{\ast }+S_{12}{\alpha }_2^{\ast }$$
即
$${\alpha }_1^{new}+S_{12}{\alpha }_2^{new,clipped}={\alpha }_1+S_{12}{\alpha }_2$$
则有
$${\alpha }_1^{new}={\alpha }_1+S_{12}({\alpha }_2-{\alpha }_2^{new,clipped})$$
至此，我们就将最关键的拉格朗日乘数的更新方式推导出来了，每次同时更新两个值，具体先更新哪两个值，随机选都可以。但实际上为了加快收敛速度，会采用启发式的方式选择优先更新的${\alpha }_i$。

参数b的更新

在$u_i$的表达式里是包含参数$b$的，而$y_i{u}_i$要满足KKT条件，即在最优解里$b$会受到约束。我们可以利用这种约束，在每一步迭代的时候都对$b$进行更新，这样可以使得整体的解更快收敛。我们令$b$为更新前的值，$b^{new}$为更新后的值，则有下面的表达式：
u i = ∑ j = 1 m y j K ⟨ x i , x j ⟩ α j + b = ∑ j = 3 m y j K ⟨ x i , x j ⟩ α j + y 1 K ⟨ x i , x 1 ⟩ α 1 + y 1 K ⟨ x i , x 1 ⟩ α 2 + b u i n e w = ∑ j = 1 m y j K ⟨ x i , x j ⟩ α j n e w + b n e w = ∑ j = 3 m y j K ⟨ x i , x j ⟩ α j + y 1 K ⟨ x i , x 1 ⟩ α 1 n e w + y 1 K ⟨ x i , x 1 ⟩ α 2 n e w + b n e w

$$\begin{matrix} u_i&amp;=&amp; \sum_{j=1}^m y_jK\langle x_i,x_j\rangle \alpha_j + b\\ &amp;=&amp; \sum_{j=3}^m y_jK\langle x_i,x_j\rangle \alpha_j + y_1K\langle x_i,x_1\rangle \alpha_1 + y_1K\langle x_i,x_1\rangle \alpha_2+ b\\ u_i^{new}&amp;=&amp; \sum_{j=1}^m y_jK\langle x_i,x_j\rangle \alpha_j^{new} + b^{new}\\ &amp;=&amp; \sum_{j=3}^m y_jK\langle x_i,x_j\rangle \alpha_j + y_1K\langle x_i,x_1\rangle \alpha_1^{new} + y_1K\langle x_i,x_1\rangle \alpha_2^{new} + b^{new}\\ \end{matrix}$$ ui​uinew​​====​∑j=1m​yj​K⟨xi​,xj​⟩αj​+b∑j=3m​yj​K⟨xi​,xj​⟩αj​+y1​K⟨xi​,x1​⟩α1​+y1​K⟨xi​,x1​⟩α2​+b∑j=1m​yj​K⟨xi​,xj​⟩αjnew​+bnew∑j=3m​yj​K⟨xi​,xj​⟩αj​+y1​K⟨xi​,x1​⟩α1new​+y1​K⟨xi​,x1​⟩α2new​+bnew​
上式中，${\alpha }_i$和$b$最开始由初始化给出,一般开始时均为0，因为最终的结果里大部分${\alpha }_i$为0。虽然${\alpha }_1^{new}$和${\alpha }_2^{new}$的计算并不依赖于$b$的取值；但我们可以反过来看，当已经计算出${\alpha }_1^{new}$和${\alpha }_2^{new}$后，我们将这两个参数代回到$u_i^{new}$的计算，${\alpha }_i$必须满足如下矩形约束

**说明：**在矩形框内即为界内和在矩形边界即为界上。
当${\alpha }_i$在界内
这是最普通的情况，此时由KKT条件有
$$y_i{u}_i=1$$
在完美拟合（或者利用数学公式推导）的情况下，最终的最优解应该满足如下表达式：
$$\begin{array}{ccc}{y}_i& =& u_i^{最优}\\ & =& {\sum }_{j=1}^m{y}_{j}K⟨x_i,x_j⟩{\alpha }_j^{最优}+b^{最优}\end{array}$$
如果在迭代更新的时候b不变，计算出的$u_i^{new}$可能与$y_i$的差距很大；我们应该通过更新b使得$u_i^{new}$等于$y_i$。因而之前的表达式可重写如下：
$$\begin{array}{ccc}{u}_i& =& {\sum }_{j=1}^m{y}_{j}K⟨x_i,x_j⟩{\alpha }_j+b\\ & =& {\sum }_{j=3}^m{y}_{j}K⟨x_i,x_j⟩{\alpha }_j+y_{1}K⟨x_i,x_1⟩{\alpha }_1+y_{1}K⟨x_i,x_1⟩{\alpha }_2+b\\ y_i& =& {\sum }_{j=1}^m{y}_{j}K⟨x_i,x_j⟩{\alpha }_j^{new}+b^{new}\\ & =& {\sum }_{j=3}^m{y}_{j}K⟨x_i,x_j⟩{\alpha }_j+y_{1}K⟨x_i,x_1⟩{\alpha }_1^{new}+y_{1}K⟨x_i,x_1⟩{\alpha }_2^{new}+b^{new}\end{array}$$
这样
$$\begin{array}{ccc}{u}_i-y_i& =& y_{1}K⟨x_i,x_1⟩{\alpha }_1+y_{1}K⟨x_i,x_1⟩{\alpha }_2+b-y_{1}K⟨x_i,x_1⟩{\alpha }_1^{new}-y_{1}K⟨x_i,x_1⟩{\alpha }_2^{new}-b^{new}\\ ⟺b^{new}& =& y_i-u_i+y_1({\alpha }_1-{\alpha }_1^{new})K⟨x_i,x_1⟩+y_1({\alpha }_2-{\alpha }_2^{new})K⟨x_i,x_1⟩\\ ⟺b^{new}& =& -E_i+y_1({\alpha }_1-{\alpha }_1^{new})K⟨x_i,x_1⟩+y_1({\alpha }_2-{\alpha }_2^{new})K⟨x_i,x_1⟩\end{array}$$
由于我们是同时更新一对${\alpha }_i$，这里是${\alpha }_1$和${\alpha }_2$，因而为了迎合$u_1^{new}=y_1$和$u_2^{new}=y_2$,我们就会得到两个$b^{new}$值，$b_1^{new}$和$b_2^{new}$,但$b^{new}$不可能同时取两个值，我们必须选择一个最佳的。
由KKT条件知当${\alpha }_i$在界内时需要满足的是等式约束，而${\alpha }_i$在界上时需要满足的是不等式约束，等式约束更难达到，b的更新应该优先满足等式约束。
下面说明b更新时不同取值的几种情况:
(1)、${\alpha }_1$在界内，
优先满足${\alpha }_1$的约束，此时应该取$b^{new}=b_1^{new}$
(2)、${\alpha }_2$在界内，
优先满足${\alpha }_2$的约束，此时应该取$b^{new}=b_2^{new}$
(3)、${\alpha }_1$和${\alpha }_2$均在界内，
此时应该取$b^{new}=b_1^{new}=b_2^{new}$，
$b_1^{new}=b_2^{new}$，这个应该是可以推导出来的，这里我们可以直觉地感到，${\alpha }_1$和${\alpha }_2$的意义，求解方法，求值范围都是完全一样，因而两者对应的约束解$b^{new}$也应该是一样的。好像在物理里还是数学里有一个这样的关于对称性的定理。
(4)、${\alpha }_1$和${\alpha }_2$均在界内
$b_1^{new}$和$b_2^{new}$之间的任何数都满足KKT条件，都可以作为b的更新值，一般取$b^{new}=\frac{b_1^{new}+b_2^{new}}{2}$；
这里可以这样理解，$b_1^{new}$可以使得${\alpha }_1$满足不等式约束，$b_2^{new}$可以使得${\alpha }_2$满足不等式约束，两者均比较容易满足，各方面的情况也是一样的，直觉是取两者的平均值更容易同时满足两个不等式约束。
其实利用这种对称性可以把(3)(4)两种情况合为一种情况。(3)里也可以认为是取了两者的均值。

这样全部参数的更新公式都已经介绍完毕。

SMO中拉格朗日乘子的启发式选择方法

前面我们拿了${\alpha }_1$和${\alpha }_2$来做演示，表示同时更新一对${\alpha }_i$，但具体先更新哪对${\alpha }_i$呢？
当然，随机的选择，最终也会逐步迭代出结果，但如果有一种方法能够选择出好的${\alpha }_i$对，使得收敛速度加快，则会更好。启发式选择方法就是用来解决这个问题的。
所谓的启发式选择方法主要思想是每次选择拉格朗日乘子的时候，优先选择样本前面系数$0<{\alpha }_i<C$的${\alpha }_i$作优化（论文中称为无界样例），因为在界上（${\alpha }_i$为0或C）的样例对应的系数一般不会更改。
这条启发式搜索方法是选择第一个拉格朗日乘子用的，比如前面的${\alpha }_2$。那么这样选择的话，是否最后会收敛。可幸的是Osuna定理告诉我们只要选择出来的两个${\alpha }_i$中有一个违背了KKT条件，那么目标函数在一步迭代后值会减小。违背KKT条件不代表$0<{\alpha }_i<C$的${\alpha }_i$，在界上也有可能会违背。是的，因此在给定初始值${\alpha }_i=0$后，先对所有样例进行循环，循环中碰到违背KKT条件的（不管界上还是界内）都进行迭代更新（迭代的过程就是使得不断满足KKT条件的过程），这里的满足KKT条件其中一种情况是$y_i{u}_i=1$并且$0<{\alpha }_i<C$，也就是$y_i{E}_i=0$并且$0<{\alpha }_i<C$，由于采用迭代的方法，在一定误差范围内就认为等于0，这里可以设置一个最小误差。等这轮过后，如果没有收敛，第二轮就只针对$0<{\alpha }_i<C$的样例进行迭代更新。
在第一个乘子选择后，第二个乘子也使用启发式方法选择，第二个乘子的迭代步长大致正比于$|E_1-E_2|$，选择第二个乘子使$|E_1-E_2|$最大。即$E_1$当为正时选择负的绝对值最大的$E_2$，反之，选择正值最大的$E_2$。
最后的收敛条件是在界内（$0<{\alpha }_i<C$）的样例都能够遵循KKT条件，且其对应的${\alpha }_i$只在极小的范围内变动。

SMO算法python实现

SMO算法基础版
程序是网上下载的，做了些注释和简单的更改，找不到原网址了，如有侵权实非故意。

#coding=utf-8

"""
这一段SVM算法实现了最基本的功能，在更新alpha的时候没有采用启发式方法，而是外层采用逐个样本扫描，内层随机抽取样本的方式更新；
没有引入核函数的概念;
计算的时候也不是采用内积的计算，而是使用矩阵对位相乘;
"""

import numpy as np
from numpy import *
import matplotlib
import matplotlib.pyplot as plt
from matplotlib.patches import Circle

def loadDataSet(fileName):
    """
    加载数据集
    :param fileName:
    :return:
    """
    dataMat = []; labelMat = []
    with open(fileName,encoding='UTF-8') as fr:
        for line in fr.readlines():
            if line.startswith("\ufeff"):#在window保存文本文件为uft-8时默认是带BOM标记的，此时用java或python读入，第一行开头将是\ufeff，占一字字符的位置
                line=line.replace("\ufeff","")
            lineArr = line.strip().split()
            dataMat.append([float(lineArr[0]), float(lineArr[1])])
            labelMat.append(float(lineArr[2]))
    return dataMat,labelMat


def selectJrand(i,m):
    """
    随机从0到m挑选一个不等于i的数
    :param i:
    :param m:
    :return:
    """
    j=i             #排除i
    while (j==i):
        j = int(random.uniform(0,m))
    return j
 
def clipAlpha(aj,H,L):
    """
    将aj剪裁到L(ow)和H(igh)之间
    :param aj:
    :param H:
    :param L:
    :return:
    """
    if aj > H:
        aj = H
    if L > aj:
        aj = L
    return aj


def calcWs(alphas,dataArr,classLabels):
    """
    根据支持向量计算分离超平面(w,b)的w参数
    :param alphas:拉格朗日乘子向量
    :param dataArr:数据集x
    :param classLabels:数据集y
    :return: w=∑alphas_i*y_i*x_i
    """
    X = mat(dataArr); labelMat = mat(classLabels).transpose()
    m,n = shape(X)
    w = zeros((n,1))
    for i in range(m):
        w += multiply(alphas[i]*labelMat[i],X[i,:].T)
    return w



def plotSVM(dataArr, labelArr, w, b, svList):
    """
    可视化函数
    """
    xcord0 = []
    ycord0 = []
    xcord1 = []
    ycord1 = []
    markers =[]
    colors =[]
    min_x=1000000
    max_x=-1000000
    min_y=1000000
    max_y=-1000000    
    for i in range(len(labelArr)):#用来提取两类样本
        xPt = dataArr[i][0]
        yPt = dataArr[i][1]
        if xPt<min_x :min_x=xPt
        if xPt>max_x :max_x=xPt        
        if yPt<min_y :min_y=yPt
        if yPt>max_y :max_y=yPt        
        label = labelArr[i]
        if (label == -1):
            xcord0.append(xPt)
            ycord0.append(yPt)
        else:
            xcord1.append(xPt)
            ycord1.append(yPt)
 
    fig = plt.figure()
    ax = fig.add_subplot(111)
    # 画数据散点图
    ax.scatter(xcord0,ycord0, marker='s', s=90)
    ax.scatter(xcord1,ycord1, marker='o', s=50, c='red')
    plt.title('Support Vectors Circled')
    # 画支持向量，用圆圈圈出
    for sv in svList:#
        circle = Circle((dataArr[sv][0], dataArr[sv][1]), 0.2, facecolor='none', edgecolor=(0,0.8,0.8), linewidth=3, alpha=0.5)
        ax.add_patch(circle)
 
    w0=w[0][0]; w1=w[1][0]; b=float(b)
    x = arange(min_x-0.5, max_x+0.5, 0.1)
    y = (-w0*x - b)/w1#画分界线，SVM与LSR是一样的方法
    ax.plot(x,y)
    ax.axis([min_x-0.5,max_x+0.5,min_y-0.5,max_y+0.5])
    plt.show()


def smoSimple(dataMatIn, classLabels, C, toler, maxIter):
    """
    简化版SMO算法
    :param dataMatIn:       X
    :param classLabels:     Y
    :param C:               惩罚参数,也就是alpha_i允许的最大值
    :param toler:           容错率（小于这个值就认为等于0）
    :param maxIter:         最大循环次数
    :return:
    """
    dataMatrix = mat(dataMatIn); labelMat = mat(classLabels).transpose()
    b = 0#初始化b为0
    m,n = shape(dataMatrix)  # m:=训练实例的个数；n:=每个样本的特征数目
    alphas = mat(zeros((m,1)))#初始化所有样本的拉格朗日乘子为0
    iter = 0
    while (iter < maxIter):#进行maxIter轮的迭代优化,每一轮里面，虽然是逐个样本更新alpha，但并不是尝试完所有样本就算一轮，而是尝试到alpha不再优化算一轮。
        alphaPairsChanged = 0   #alpha是否已经进行了优化
        for i in range(m):
            #   w = alpha * y * x;  f(x_i) = w^T * x_i + b
            fXi = float(multiply(alphas,labelMat).T*dataMatrix*dataMatrix[i,:].T) + b     # 预测的类别
            Ei = fXi - float(labelMat[i])   #得到误差，如果误差太大，检查是否可能被优化
            if ((labelMat[i]*Ei < -toler) and (alphas[i] < C)) or ((labelMat[i]*Ei > toler) and (alphas[i] > 0)): #必须满足约束
                j = selectJrand(i,m)#随机挑选了另一个样本与前一个样本配对
                fXj = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[j,:].T)) + b
                Ej = fXj - float(labelMat[j])
                alphaIold = alphas[i].copy(); alphaJold = alphas[j].copy()                # 教材中的α_1^old和α_2^old
                if (labelMat[i] != labelMat[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: print("L==H"); continue#则该对拉格朗日乘子不需要优化
                # Eta = -(2 * K12 - K11 - K22)，且Eta非负，此处eta = -Eta则非正
                eta = 2.0 * dataMatrix[i,:]*dataMatrix[j,:].T - dataMatrix[i,:]*dataMatrix[i,:].T - dataMatrix[j,:]*dataMatrix[j,:].T
                if eta >= 0: print("eta>=0"); continue#eta出现特殊值，这里直接跳过这种情况，实际上是需要考虑特殊情况的。
                alphas[j] -= labelMat[j]*(Ei - Ej)/eta
                #print(alphas[j])
                alphas[j] = clipAlpha(alphas[j],H,L)#将alpha值限定在矩形框内
                #print(alphas[j])
                #如果内层循环通过以上方法选择的α_2不能使目标函数有足够的下降，那么放弃α_1
                if (abs(alphas[j] - alphaJold) < 0.00001): print("j not moving enough"); continue
                alphas[i] += labelMat[j]*labelMat[i]*(alphaJold - alphas[j])
                b1 = b - Ei- labelMat[i]*(alphas[i]-alphaIold)*dataMatrix[i,:]*dataMatrix[i,:].T - labelMat[j]*(alphas[j]-alphaJold)*dataMatrix[i,:]*dataMatrix[j,:].T
                b2 = b - Ej- labelMat[i]*(alphas[i]-alphaIold)*dataMatrix[i,:]*dataMatrix[j,:].T - labelMat[j]*(alphas[j]-alphaJold)*dataMatrix[j,:]*dataMatrix[j,:].T
                if (0 < alphas[i]) and (C > alphas[i]): b = b1
                elif (0 < alphas[j]) and (C > alphas[j]): b = b2
                else: b = (b1 + b2)/2.0
                alphaPairsChanged += 1
                print("iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged))
        if (alphaPairsChanged == 0): 
            iter += 1
            #print(alphas,b)
        else: iter = 0
        print("iteration number: %d" % iter)
    return b,alphas

# 该数据集中共有100行，3列，即88个样本，前两列为特征，最后一列为类别标签，共两类用-1,1来表示
dataArr, labelArr = loadDataSet('testSet.txt')
b,alphas = smoSimple(dataArr, labelArr, 0.6, 0.001, 40)
print(b)
print(alphas)
print(alphas[alphas > 0])

for i in range(len(alphas)):#将支持向量打印出来
    if alphas[i] > 0.0 : print(dataArr[i], labelArr[i])

w = calcWs(alphas, dataArr, labelArr)
print(w)
svList = []
for i in range(len(alphas)):#获取支持向量
    if abs(alphas[i]) > 0.0000001 :
        print(dataArr[i], labelArr[i])
        svList.append(i)
 
plotSVM(dataArr, labelArr, w, b, svList)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199

程序运行结果如下：

总结

这份SVM的讲义重点概括了SVM的基本概念和基本推导，中规中矩却又让人醍醐灌顶。起初让我最头疼的是拉格朗日对偶和SMO，后来逐渐明白拉格朗日对偶的重要作用是将w的计算提前并消除w，使得优化函数变为拉格朗日乘子的单一参数优化问题。而SMO里面迭代公式的推导也着实让我花费了不少时间。
对比这么复杂的推导过程，SVM的思想确实那么简单。它不再像logistic回归一样企图去拟合样本点（中间加了一层sigmoid函数变换），而是就在样本中去找分隔线，为了评判哪条分界线更好，引入了几何间隔最大化的目标。
之后所有的推导都是去解决目标函数的最优化上了。在解决最优化的过程中，发现了$w$可以由特征向量内积来表示，进而发现了核函数，仅需要调整核函数就可以将特征进行低维到高维的变换，在低维上进行计算，实质结果表现在高维上。由于并不是所有的样本都可分，为了保证SVM的通用性，进行了软间隔的处理，导致的结果就是将优化问题变得更加复杂，然而惊奇的是松弛变量没有出现在最后的目标函数中。最后的优化求解问题，也被拉格朗日对偶和SMO算法化解，使SVM趋向于完美。
另外，其他很多议题如SVM背后的学习理论、参数选择问题、二值分类到多值分类等等还没有涉及到，以后有时间再学吧。其实朴素贝叶斯在分类二值分类问题时，如果使用对数比，那么也算作线性分类器。

支持向量机多分类

来源：
SVM本身是一个二值分类器，SVM算法最初是为二值分类问题设计的，当处理多类问题时，就需要构造合适的多类分类器。 目前，构造SVM多类分类器的方法主要有两类，直接法、间接法。

一 直接法

直接在目标函数上进行修改，将多个分类面的参数求解合并到一个最优化问题中，通过求解该最优化问题“一次性”实现多类分类。这种方法看似简单，但其计算复杂度比较高，实现起来比较困难，只适合用于小型问题中；

二 间接法

主要是通过组合多个二分类器来实现多分类器的构造，常见的方法有one-against-one和one-against-all两种。

(1）一对多法（one-versus-rest,简称OVR SVMs）

训练时依次把某个类别的样本归为一类,其他剩余的样本归为另一类，这样k个类别的样本就构造出了k个SVM。分类时将未知样本分类为具有最大分类函数值的那类。

假如我有四类要划分（也就是4个Label），他们是A、B、C、D。

于是我在抽取训练集的时候，分别抽取

• （1）A所对应的向量作为正集，B，C，D所对应的向量作为负集；
• （2）B所对应的向量作为正集，A，C，D所对应的向量作为负集；
• （3）C所对应的向量作为正集，A，B，D所对应的向量作为负集；
• （4）D所对应的向量作为正集，A，B，C所对应的向量作为负集；

使用这四个训练集分别进行训练，然后的得到四个训练结果文件。
在测试的时候，把对应的测试向量分别利用这四个训练结果文件进行测试。
最后每个测试都有一个结果f1(x),f2(x),f3(x),f4(x)。
于是最终的结果便是这四个值中最大的一个作为分类结果。

评价

**优点：**训练k个分类器，个数较少，其分类速度相对较快。

缺点：

①每个分类器的训练都是将全部的样本作为训练样本，这样在求解二次规划问题时，训练速度会随着训练样本的数量的增加而急剧减慢；
②同时由于负类样本的数据要远远大于正类样本的数据，从而出现了样本不对称的情况，且这种情况随着训练数据的增加而趋向严重。解决不对称的问题可以引入不同的惩罚因子，对样本点来说较少的正类采用较大的惩罚因子C；
③还有就是当有新的类别加进来时，需要对所有的模型进行重新训练。

**从“一对多”的方法又衍生出基于决策树的分类： **
首先将所有类别分为两个类别，再将子类进一步划分为两个次级子类，如此循环下去，直到所有的节点都只包含一个单独的类别为止，此节点也是二叉树树种的叶子。该分类将原有的分类问题同样分解成了一系列的两类分类问题，其中两个子类间的分类函数采用SVM。下图引用出自于王正海《基于决策树多分类支持向量机岩性波谱分类》

（2）一对一法（one-versus-one,简称OVO SVMs或者pairwise）

其做法是在任意两类样本之间设计一个SVM，因此k个类别的样本就需要设计k(k-1)/2个SVM。
当对一个未知样本进行分类时，最后得票最多的类别即为该未知样本的类别。
Libsvm中的多类分类就是根据这个方法实现的。
假设有四类A,B,C,D四类。在训练的时候我选择A,B; A,C; A,D; B,C; B,D;C,D所对应的向量作为训练集，然后得到六个训练结果，在测试的时候，把对应的向量分别对六个结果进行测试，然后采取投票形式，最后得到一组结果。

投票是这样的：

• A=B=C=D=0;
• (A,B)-classifier 如果是A win,则A=A+1;otherwise,B=B+1;
• (A,C)-classifier 如果是A win,则A=A+1;otherwise, C=C+1;
  　　…
• (C,D)-classifier 如果是A win,则C=C+1;otherwise,D=D+1;
• The decision is the Max(A,B,C,D)

评价：这种方法虽然好,但是当类别很多的时候,model的个数是n*(n-1)/2,代价还是相当大的。

评价：

**优点：**不需要重新训练所有的SVM，只需要重新训练和增加语音样本相关的分类器。在训练单个模型时，相对速度较快。

**缺点：**所需构造和测试的二值分类器的数量关于k成二次函数增长，总训练时间和测试时间相对较慢。

从“一对一”的方式出发，出现了有向无环图（DirectedAcyclic Graph）的分类方法。

图1 有向无环图 直接方法尽管看起来简洁，但是在最优化问题求解过程中的变量远远多于第一类方法，训练速度不及间接方法，而且在分类精度上也不占优。当训练样本数非常大时，这一问题更加突出。正因如此，间接方法更为常用。

支持向量机模型的检验(及自变量的选择)

支持向量机模型的评估方法

支持向量机的正则化

并行支持向量机

淘宝双11数据分析与预测课程案例—步骤四:利用Spark预测回头客行为

线性支持回归

来源：
思路：还是在y(w,x)=w^tx+b
然后利用支持向量机的思路来求w和b。与支持向量机用于分类不同。回归模型，没有类别。其实类别是隐含了一个超平面（粗略的理解就是两个类别中间），然后支持向量到超平面的几何距离要尽可能大，其他样本点要在支持向量之外。在回归中假如已经拟合了一条回归曲线，那么我们也要让回归曲线穿过这些样本点，并让样本点分布曲线两侧，相当于就是一个超平面。当然我们还要人为归定样本点到拟合曲线的距离不能太大（这个与分类中的很不一样）。依此我们可以构建与分类问题中相似的目标函数和约束条件。
$$\begin{gathered} min\frac{1}{2}||w|{|}_2^2 \\ s.t|y_i-w\bullet \varphi (x_i)-b|\le ϵ(i=1,2,...m) \end{gathered}$$
然后就可以利用可以利用广义拉格朗日乘法和KKT条件进行推导，得到目标函数只关于拉格朗日乘数的函数，并利用SMO算法求解$\alpha$,进而得到$b$和$w$。
代入到y(w,x)=w^tx+b的表达式即可得到测试样本的回归值，应该还是用内积的算法。

SVM应用

分类算法之支持向量机:SVM（应用篇）

SVM使用心得

关于调试SVM的一点心得
各位大侠来说说用SVM的经验？
关于统计学习的一篇好的心得感受！
SVM一样，没有L2-norm regularization，实践中的性能就会变得很差
对SVM的个人理解—浅显易懂
SVM调参经验
使用SVM模型进行分类预测时的参数调整技巧
使用svm的一个常见错误
支持向量机之使用核SVM解决非线性分类问题
支持向量机(SVM)是否适合大规模数据？

其他资料
手把手教你实现SVM算法（一）
手把手教你实现SVM算法（二）
支持向量机通俗导论（理解SVM的三层境界）
SVM理论
支持向量机:里面有代码
机器学习之支持向量机SVM:里面有代码和案例
机器学习中的算法(2)-支持向量机(SVM)基础
Sequential Minimal Optimization - A Fast Algorithm for Training Support Vector Machines
SVM notation
理解SVM（二）——线性不可分的情况
采用线性SVM对线性不可分的数据进行分类（含matlab实现）