支持向量机(Support Vecor Machine,以下简称SVM)虽然诞生只有短短的二十多年，但是自一诞生便由于它良好的分类性能席卷了机器学习领域，并牢牢压制了神经网络领域好多年。如果不考虑集成学习的算法，不考虑特定的训练数据集，在分类算法中的表现SVM说是排第一估计是没有什么异议的。
SVM是一个二元分类算法，线性分类和非线性分类都支持。经过演进，现在也可以支持多元分类，同时经过扩展，也能应用于回归问题。本系列文章就对SVM的原理做一个总结。
1. 回顾感知机模型
感知机的模型就是尝试找到一条直线，能够把二元数据隔离开。放到三维空间或者更高维的空间，感知机的模型就是尝试找到一个超平面，能够把所有的二元类别隔离开。对于这个分离的超平面，我们定义为$w^Tx + b = 0$，如下图。在超平面$w^Tx + b = 0$上方的我们定义为$y=1$,在超平面$w^Tx + b = 0$下方的我们定义为$y=−1$。可以看出满足这个条件的超平面并不止一个。那么我们可能会尝试思考，这么多的可以分类的超平面，哪个是最好的呢？或者说哪个是泛化能力最强的呢?
接着我们看感知机模型的损失函数优化，它的思想是让所有误分类的点(定义为M)到超平面的距离和最小，即最小化下式：$$\sum\limits_{x_i \in M}- y^{(i)}(w^Tx^{(i)} +b)\big / ||w||_2$$
当w和bw和b成比例的增加，比如,当分子的$w和b$扩大N倍时，分母的L2范数也会扩大N倍。也就是说，分子和分母有固定的倍数关系。那么我们可以固定分子或者分母为1，然后求另一个即分子自己或者分母的倒数的最小化作为损失函数，这样可以简化我们的损失函数。在感知机模型中，我们采用的是保留分子，固定分母$||w||_2=1$,即最终感知机模型的损失函数为：$$\sum\limits_{x_i \in M}- y^{(i)}(w^Tx^{(i)} +b)$$
如果我们不是固定分母，改为固定分子，作为分类模型有没有改进呢？
这些问题在我们引入SVM后会详细解释。
2. 函数间隔与几何间隔
在正式介绍SVM的模型和损失函数之前，我们还需要先了解下函数间隔和几何间隔的知识。
在分离超平面固定为$w^Tx+b=0$的时候，$|w^Tx+b|$表示点x到超平面的距离。通过观察$w^Tx+b$和y是否同号，我们判断分类是否正确，这些知识我们在感知机模型里都有讲到。这里我们引入函数间隔的概念，定义函数间隔$γ′$为：$$\gamma^{'} = y(w^Tx + b)$$
可以看到，它就是感知机模型里面的误分类点到超平面距离的分子。对于训练集中m个样本点对应的m个函数间隔的最小值，就是整个训练集的函数间隔。
函数间隔并不能正常反应点到超平面的距离，在感知机模型里我们也提到，当分子成比例的增长时，分母也是成倍增长。为了统一度量，我们需要对法向量$w$加上约束条件，这样我们就得到了几何间隔$γ$,定义为：$$\gamma = \frac{y(w^Tx + b)}{||w||_2} = \frac{\gamma^{'}}{||w||_2}$$
几何间隔才是点到超平面的真正距离，感知机模型里用到的距离就是几何距离。
3. 支持向量
在感知机模型中，我们可以找到多个可以分类的超平面将数据分开，并且优化时希望所有的点都离超平面远。但是实际上离超平面很远的点已经被正确分类，我们让它离超平面更远并没有意义。反而我们最关心是那些离超平面很近的点，这些点很容易被误分类。如果我们可以让离超平面比较近的点尽可能的远离超平面，那么我们的分类效果会好有一些。SVM的思想起源正起于此。
如下图所示，分离超平面为$w^Tx+b=0$，如果所有的样本不光可以被超平面分开，还和超平面保持一定的函数距离（下图函数距离为1），那么这样的分类超平面是比感知机的分类超平面优的。可以证明，这样的超平面只有一个。和超平面平行的保持一定的函数距离的这两个超平面对应的向量，我们定义为支持向量，如下图虚线所示。
支持向量到超平面的距离为$1/||w||_2$,两个支持向量之间的距离为$1/||w||_2$。
4. SVM模型目标函数与优化
SVM的模型是让所有点到超平面的距离大于一定的距离，也就是所有的分类点要在各自类别的支持向量两边。用数学式子表示为：$$max \;\; \gamma = \frac{y(w^Tx + b)}{||w||_2} \;\; s.t \;\; y_i(w^Tx_i + b) = \gamma^{'(i)} \geq \gamma^{'} (i =1,2,...m)$$
一般我们都取函数间隔$γ′$为1，这样我们的优化函数定义为：$$max \;\; \frac{1}{||w||_2} \;\; s.t \;\; y_i(w^Tx_i + b) \geq 1 (i =1,2,...m)$$
也就是说，我们要在约束条件$y_i(w^Tx_i + b) \geq 1 (i =1,2,...m)$下，最大化$1/||w||_2$。可以看出，这个感知机的优化方式不同，感知机是固定分母优化分子，而SVM是固定分子优化分母，同时加上了支持向量的限制。
由于$\frac{1}{||w||_2}$的最大化等同于$\frac{1}{2}||w||_2^2$的最小化。这样SVM的优化函数等价于：$$min \;\; \frac{1}{2}||w||_2^2 \;\; s.t \;\; y_i(w^Tx_i + b) \geq 1 (i =1,2,...m)$$
由于目标函数$\frac{1}{2}||w||_2^2$是凸函数，同时约束条件不等式是仿射的，根据凸优化理论，我们可以通过拉格朗日函数将我们的优化目标转化为无约束的优化函数，具体的，优化函数转化为：$$L(w,b,alpha) = frac{1}{2}||w||_2^2 - sumlimits_{i=1}^{m}alpha_i[y_i(w^Tx_i + b) - 1] ; 满足alpha_i geq 0$$
由于引入了朗格朗日乘子，我们的优化目标变成：$$\underbrace{min}_{w,b}\; \underbrace{max}_{\alpha_i \geq 0} L(w,b,\alpha)$$
我们的这个优化函数满足KKT条件，也就是说，我们可以通过拉格朗日对偶将我们的优化问题转化为等价的对偶问题来求解。如果对凸优化和拉格朗日对偶不熟悉，建议阅读鲍德的《凸优化》。
也就是说，现在我们要求的是：$$\underbrace{max}_{\alpha_i \geq 0} \;\underbrace{min}_{w,b}\; L(w,b,\alpha)$$
从上式中，我们可以先求优化函数对于$w和b$的极小值。接着再求拉格朗日乘子$α$的极大值。
首先我们来求$w和b$的极小值，即$\underbrace{min}_{w,b}\; L(w,b,\alpha)$。这个极值我们可以通过对$w和b$分别求偏导数得到：$$\frac{\partial L}{\partial w} = 0 \;\Rightarrow w = \sum\limits_{i=1}^{m}\alpha_iy_ix_i$$
$$\frac{\partial L}{\partial b} = 0 \;\Rightarrow \sum\limits_{i=1}^{m}\alpha_iy_i = 0$$
从上两式子可以看出，我们已经求得了$w和α$的关系，只要我们后面接着能够求出优化函数极大化对应的$α$，就可以求出我们的$w$了，至于b，由于上两式已经没有b，所以最后的b可以有多个。
好了，既然我们已经求出$w和α$的关系，就可以带入优化函数$L(w,b,α)$消去$w$了。我们定义:$$\psi(\alpha) = \underbrace{min}_{w,b}\; L(w,b,\alpha)$$
现在我们来看将$w$替换为$α$的表达式以后的优化函数$ψ(α)$的表达式：$$\begin{align} \psi(\alpha) & = \frac{1}{2}||w||_2^2 - \sum\limits_{i=1}^{m}\alpha_i[y_i(w^Tx_i + b) - 1] \\& = \frac{1}{2}w^Tw-\sum\limits_{i=1}^{m}\alpha_iy_iw^Tx_i - \sum\limits_{i=1}^{m}\alpha_iy_ib + \sum\limits_{i=1}^{m}\alpha_i \\& = \frac{1}{2}w^T\sum\limits_{i=1}^{m}\alpha_iy_ix_i -\sum\limits_{i=1}^{m}\alpha_iy_iw^Tx_i - \sum\limits_{i=1}^{m}\alpha_iy_ib + \sum\limits_{i=1}^{m}\alpha_i \\& = \frac{1}{2}w^T\sum\limits_{i=1}^{m}\alpha_iy_ix_i - w^T\sum\limits_{i=1}^{m}\alpha_iy_ix_i - \sum\limits_{i=1}^{m}\alpha_iy_ib + \sum\limits_{i=1}^{m}\alpha_i \\& = - \frac{1}{2}w^T\sum\limits_{i=1}^{m}\alpha_iy_ix_i - \sum\limits_{i=1}^{m}\alpha_iy_ib + \sum\limits_{i=1}^{m}\alpha_i \\& = - \frac{1}{2}w^T\sum\limits_{i=1}^{m}\alpha_iy_ix_i - b\sum\limits_{i=1}^{m}\alpha_iy_i + \sum\limits_{i=1}^{m}\alpha_i \\& = -\frac{1}{2}(\sum\limits_{i=1}^{m}\alpha_iy_ix_i)^T(\sum\limits_{i=1}^{m}\alpha_iy_ix_i) - b\sum\limits_{i=1}^{m}\alpha_iy_i + \sum\limits_{i=1}^{m}\alpha_i \\& = -\frac{1}{2}\sum\limits_{i=1}^{m}\alpha_iy_ix_i^T\sum\limits_{i=1}^{m}\alpha_iy_ix_i - b\sum\limits_{i=1}^{m}\alpha_iy_i + \sum\limits_{i=1}^{m}\alpha_i \\& = -\frac{1}{2}\sum\limits_{i=1}^{m}\alpha_iy_ix_i^T\sum\limits_{i=1}^{m}\alpha_iy_ix_i + \sum\limits_{i=1}^{m}\alpha_i \\& = -\frac{1}{2}\sum\limits_{i=1,j=1}^{m}\alpha_iy_ix_i^T\alpha_jy_jx_j + \sum\limits_{i=1}^{m}\alpha_i \\& = \sum\limits_{i=1}^{m}\alpha_i - \frac{1}{2}\sum\limits_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j \end{align}$$
其中，(1)式到(2)式用到了范数的定义$||w||_2^2 =w^Tw$, (2)式到(3)式用到了上面的$w = \sum\limits_{i=1}^{m}\alpha_iy_ix_i$， (3)式到(4)式把和样本无关的$w^T$提前，(4)式到(5)式合并了同类项，(5)式到(6)式把和样本无关的$b$提前，(6)式到(7)式继续用到$w = \sum\limits_{i=1}^{m}\alpha_iy_ix_i$，（7）式到(8)式用到了向量的转置。由于常量的转置是其本身，所有只有向量$x_i$被转置，（8）式到(9)式用到了上面的$\sum\limits_{i=1}^{m}\alpha_iy_i = 0$，（9）式到(10)式使用了$(a+b+c+…)(a+b+c+…)=aa+ab+ac+ba+bb+bc+…(a+b+c+…)(a+b+c+…)=aa+ab+ac+ba+bb+bc+…$的乘法运算法则，（10）式到(11)式仅仅是位置的调整。
从上面可以看出，通过对$w,b$极小化以后，我们的优化函数$ψ(α)$仅仅只有$α$向量做参数。只要我们能够极大化$ψ(α)$，就可以求出此时对应的$α$，进而求出$w,b$.
对$ψ(α)$求极大化的数学表达式如下:$$\underbrace{max}_{\alpha} -\frac{1}{2}\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{m}\alpha_i\alpha_jy_iy_j(x_i \bullet x_j) + \sum\limits_{i=1}^{m} \alpha_i$$
$$s.t. \; \sum\limits_{i=1}^{m}\alpha_iy_i = 0$$
$$\alpha_i \geq 0 \; i=1,2,...m$$
可以去掉负号，即为等价的极小化问题如下：
$$\underbrace{max}_{\alpha} \frac{1}{2}\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{m}\alpha_i\alpha_jy_iy_j(x_i \bullet x_j) - \sum\limits_{i=1}^{m} \alpha_i$$
$$s.t. \; \sum\limits_{i=1}^{m}\alpha_iy_i = 0$$
$$\alpha_i \geq 0 \; i=1,2,...m$$
只要我们可以求出上式极小化时对应的$α$向量就可以求出$w和b$了。具体怎么极小化上式得到对应的$α$，一般需要用到SMO算法，这个算法比较复杂，我们后面会专门来讲。在这里，我们假设通过SMO算法，我们得到了对应的$α$的值$α^∗$。
那么我们根据$w = \sum\limits_{i=1}^{m}\alpha_iy_ix_i$，可以求出对应的$w$的值$$w^{*} = \sum\limits_{i=1}^{m}\alpha_i^{*}y_ix_i$$
求b则稍微麻烦一点。注意到，对于任意支持向量$(x_x, y_s)$，都有$$y_s(w^Tx_s+b) = y_s(\sum\limits_{i=1}^{m}\alpha_iy_ix_i^Tx_s+b) = 1$$
假设我们有S个支持向量，则对应我们求出S个$b^∗$,理论上这些$b^∗$都可以作为最终的结果， 但是我们一般采用一种更健壮的办法，即求出所有支持向量所对应的$b^∗_s$，然后将其平均值作为最后的结果。注意到对于严格线性可分的SVM，$b$的值是有唯一解的，也就是这里求出的所有$b^∗$都是一样的，这里我们仍然这么写是为了和后面加入软间隔后的SVM的算法描述一致。
怎么得到支持向量呢？根据KKT条件中的对偶互补条件$\alpha_{i}^{*}(y_i(w^Tx_i + b) - 1) = 0$，如果$α_i>0$则有$y_i(w^Tx_i + b) =1$ 即点在支持向量上，否则如果$α_i>0$则有$y_i(w^Tx_i + b) \geq 1$，即样本在支持向量上或者已经被正确分类。
5. 线性可分SVM的算法过程
这里我们对线性可分SVM的算法过程做一个总结。
输入是线性可分的m个样本${(x_1,y_1), (x_2,y_2), ..., (x_m,y_m),}$,其中x为n维特征向量。y为二元输出，值为1，或者-1.
输出是分离超平面的参数$w^∗和b^∗$和分类决策函数。
算法过程如下：
1）构造约束优化问题$$\underbrace{max}_{\alpha} \frac{1}{2}\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{m}\alpha_i\alpha_jy_iy_j(x_i \bullet x_j) - \sum\limits_{i=1}^{m} \alpha_i$$
$$s.t. \; \sum\limits_{i=1}^{m}\alpha_iy_i = 0$$
$$\alpha_i \geq 0 \; i=1,2,...m$$
2）用SMO算法求出上式最小时对应的$α$向量的值$α^∗$向量.
3) 计算$w^{*} = \sum\limits_{i=1}^{m}\alpha_i^{*}y_ix_i$
4) 找出所有的S个支持向量,即满足$alpha_s > 0对应的样本(x_s,y_s)$，通过 $y_s(\sum\limits_{i=1}^{m}\alpha_iy_ix_i^Tx_s+b) = 1$，计算出每个支持向量$(x_x, y_s)$对应的$b^∗_s$,计算出这些$b_s^{*} = y_s - \sum\limits_{i=1}^{m}\alpha_iy_ix_i^Tx_s$. 所有的$b^∗_s$对应的平均值即为最终的$b^{*} = \frac{1}{S}\sum\limits_{i=1}^{S}b_s^{*}$
这样最终的分类超平面为：$w^{*} \bullet x + b^{*} = 0$,最终的分类决策函数为：$f(x) = sign(w^{*} \bullet x + b^{*})$
6. 线性分类SVM面临的问题
有时候本来数据的确是可分的，也就是说可以用 线性分类SVM的学习方法来求解，但是却因为混入了异常点，导致不能线性可分，比如下图，本来数据是可以按下面的实线来做超平面分离的，可以由于一个橙色和一个蓝色的异常点导致我们没法按照线性支持向量机中的方法来分类。
另外一种情况没有这么糟糕到不可分，但是会严重影响我们模型的泛化预测效果，比如下图，本来如果我们不考虑异常点，SVM的超平面应该是下图中的红色线所示，但是由于有一个蓝色的异常点，导致我们学习到的超平面是下图中的粗虚线所示，这样会严重影响我们的分类模型预测效果。
如何解决这些问题呢？SVM引入了软间隔最大化的方法来解决。
7. 线性分类SVM的软间隔最大化
所谓的软间隔，是相对于硬间隔说的，我们可以认为上一篇线性分类SVM的学习方法属于硬间隔最大化。
回顾下硬间隔最大化的条件：$$min\;\; \frac{1}{2}||w||_2^2 \;\; s.t \;\; y_i(w^Tx_i + b) \geq 1 (i =1,2,...m)$$
接着我们再看如何可以软间隔最大化呢？
SVM对训练集里面的每个样本$(x_i,y_i)$引入了一个松弛变量$\xi_i \geq 0$,使函数间隔加上松弛变量大于等于1，也就是说：
$$y_i(w\bullet x_i +b) \geq 1- \xi_i$$
对比硬间隔最大化，可以看到我们对样本到超平面的函数距离的要求放松了，之前是一定要大于等于1，现在只需要加上一个大于等于0的松弛变量能大于等于1就可以了。当然，松弛变量不能白加，这是有成本的，每一个松弛变量$\xi_i$, 对应了一个代价$\xi_i$，这个就得到了我们的软间隔最大化的SVM学习条件如下：
$$min\;\; \frac{1}{2}||w||_2^2 +C\sum\limits_{i=1}^{m}\xi_i$$
$$s.t. \;\; y_i(w^Tx_i + b) \geq 1 - \xi_i \;\;(i =1,2,...m)$$
$$\xi_i \geq 0 \;\;(i =1,2,...m)$$
这里,$C>0$为惩罚参数，可以理解为我们一般回归和分类问题正则化时候的参数。$C$越大，对误分类的惩罚越大，$C$越小，对误分类的惩罚越小。
也就是说，我们希望$\frac{1}{2}||w||_2^2$尽量小，误分类的点尽可能的少。C是协调两者关系的正则化惩罚系数。在实际应用中，需要调参来选择。
这个目标函数的优化和上一篇的线性可分SVM的优化方式类似，我们下面就来看看怎么对线性分类SVM的软间隔最大化来进行学习优化。
8. 线性分类SVM的软间隔最大化目标函数的优化
和线性可分SVM的优化方式类似，我们首先将软间隔最大化的约束问题用拉格朗日函数转化为无约束问题如下：$$L(w,b,\xi,\alpha,\mu) = \frac{1}{2}||w||_2^2 +C\sum\limits_{i=1}^{m}\xi_i - \sum\limits_{i=1}^{m}\alpha_i[y_i(w^Tx_i + b) - 1 + \xi_i] - \sum\limits_{i=1}^{m}\mu_i\xi_i$$
其中$\mu_i \geq 0, \alpha_i \geq 0$,均为拉格朗日系数。
也就是说，我们现在要优化的目标函数是：$$\underbrace{min}_{w,b,\xi}\; \underbrace{max}_{\alpha_i \geq 0, \mu_i \geq 0,} L(w,b,\alpha, \xi,\mu)$$
这个优化目标也满足KKT条件，也就是说，我们可以通过拉格朗日对偶将我们的优化问题转化为等价的对偶问题来求解如下：$$\underbrace{max}_{\alpha_i \geq 0, \mu_i \geq 0,} \; \underbrace{min}_{w,b,\xi}\; L(w,b,\alpha, \xi,\mu)$$
我们可以先求优化函数对于$w, b, \xi$的极小值, 接着再求拉格朗日乘子$α$和 $μ$的极大值。
首先我们来求优化函数对于$w, b, \xi$的极小值，这个可以通过求偏导数求得：
$$\frac{\partial L}{\partial w} = 0 \;\Rightarrow w = \sum\limits_{i=1}^{m}\alpha_iy_ix_i$$
$$\frac{\partial L}{\partial b} = 0 \;\Rightarrow \sum\limits_{i=1}^{m}\alpha_iy_i = 0$$
$$\frac{\partial L}{\partial \xi} = 0 \;\Rightarrow C- \alpha_i - \mu_i = 0$$
好了，我们可以利用上面的三个式子去消除$w$和$b$了。
$$begin{align} L(w,b,xi,alpha,mu) & = frac{1}{2}||w||_2^2 +Csumlimits_{i=1}^{m}xi_i - sumlimits_{i=1}^{m}alpha_i[y_i(w^Tx_i + b) - 1 + xi_i] - sumlimits_{i=1}^{m}mu_ixi_i \&= frac{1}{2}||w||_2^2 - sumlimits_{i=1}^{m}alpha_i[y_i(w^Tx_i + b) - 1 + xi_i] + sumlimits_{i=1}^{m}alpha_ixi_i \& = frac{1}{2}||w||_2^2 - sumlimits_{i=1}^{m}alpha_i[y_i(w^Tx_i + b) - 1] \& = frac{1}{2}w^Tw-sumlimits_{i=1}^{m}alpha_iy_iw^Tx_i - sumlimits_{i=1}^{m}alpha_iy_ib + sumlimits_{i=1}^{m}alpha_i \& = frac{1}{2}w^Tsumlimits_{i=1}^{m}alpha_iy_ix_i -sumlimits_{i=1}^{m}alpha_iy_iw^Tx_i - sumlimits_{i=1}^{m}alpha_iy_ib + sumlimits_{i=1}^{m}alpha_i \& = frac{1}{2}w^Tsumlimits_{i=1}^{m}alpha_iy_ix_i - w^Tsumlimits_{i=1}^{m}alpha_iy_ix_i - sumlimits_{i=1}^{m}alpha_iy_ib + sumlimits_{i=1}^{m}alpha_i \& = - frac{1}{2}w^Tsumlimits_{i=1}^{m}alpha_iy_ix_i - sumlimits_{i=1}^{m}alpha_iy_ib + sumlimits_{i=1}^{m}alpha_i \& = - frac{1}{2}w^Tsumlimits_{i=1}^{m}alpha_iy_ix_i - bsumlimits_{i=1}^{m}alpha_iy_i + sumlimits_{i=1}^{m}alpha_i \& = -frac{1}{2}(sumlimits_{i=1}^{m}alpha_iy_ix_i)^T(sumlimits_{i=1}^{m}alpha_iy_ix_i) - bsumlimits_{i=1}^{m}alpha_iy_i + sumlimits_{i=1}^{m}alpha_i \& = -frac{1}{2}sumlimits_{i=1}^{m}alpha_iy_ix_i^Tsumlimits_{i=1}^{m}alpha_iy_ix_i - bsumlimits_{i=1}^{m}alpha_iy_i + sumlimits_{i=1}^{m}alpha_i \& = -frac{1}{2}sumlimits_{i=1}^{m}alpha_iy_ix_i^Tsumlimits_{i=1}^{m}alpha_iy_ix_i + sumlimits_{i=1}^{m}alpha_i \& = -frac{1}{2}sumlimits_{i=1,j=1}^{m}alpha_iy_ix_i^Talpha_jy_jx_j + sumlimits_{i=1}^{m}alpha_i \& = sumlimits_{i=1}^{m}alpha_i - frac{1}{2}sumlimits_{i=1,j=1}^{m}alpha_ialpha_jy_iy_jx_i^Tx_j end{align}$$
其中，(1)式到(2)式用到了$C- \alpha_i - \mu_i = 0$, (2)式到(3)式合并了同类项，(3)式到(4)式用到了范数的定义$||w||_2^2 =w^Tw$, (4)式到(5)式用到了上面的$w = \sum\limits_{i=1}^{m}\alpha_iy_ix_i$， (5)式到(6)式把和样本无关的$w^T$提前，(6)式到(7)式合并了同类项，(7)式到(8)式把和样本无关的bb提前，(8)式到(9)式继续用到$w = \sum\limits_{i=1}^{m}\alpha_iy_ix_i$，（9）式到(10)式用到了向量的转置。由于常量的转置是其本身，所有只有向量$x_i$被转置，（10）式到(11)式用到了上面的$\sum\limits_{i=1}^{m}\alpha_iy_i = 0$，（11）式到(12)式使用了$(a+b+c+…)(a+b+c+…)=aa+ab+ac+ba+bb+bc+…$的乘法运算法则，（12）式到(13)式仅仅是位置的调整。
仔细观察可以发现，这个式子和我们上面线性可分SVM的一样。唯一不一样的是约束条件。现在我们看看我们的优化目标的数学形式：
$$\underbrace{ max }_{\alpha} \sum\limits_{i=1}^{m}\alpha_i - \frac{1}{2}\sum\limits_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j$$
$$s.t. \; \sum\limits_{i=1}^{m}\alpha_iy_i = 0$$
$$C- \alpha_i - \mu_i = 0$$
$$\alpha_i \geq 0 \;(i =1,2,...,m)$$
$$\mu_i \geq 0 \;(i =1,2,...,m)$$
对于$C- alpha_i - mu_i = 0 ， alpha_i geq 0 ，mu_i geq 0$i≥0这3个式子，我们可以消去$μ_i$，只留下$α_i$，也就是说$0≤α_i≤C$。 同时将优化目标函数变号，求极小值，如下：
$$\underbrace{ min }_{\alpha} \frac{1}{2}\sum\limits_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j - \sum\limits_{i=1}^{m}\alpha_i$$
$$s.t. \; \sum\limits_{i=1}^{m}\alpha_iy_i = 0$$
$$0 \leq \alpha_i \leq C$$
这就是软间隔最大化时的线性可分SVM的优化目标形式，和上一篇的硬间隔最大化的线性可分SVM相比，我们仅仅是多了一个约束条件$0≤α_i≤C$。我们依然可以通过SMO算法来求上式极小化时对应的αα向量就可以求出$w和b$了。
9. 软间隔最大化时的支持向量
在硬间隔最大化时，支持向量比较简单，就是满足$y_i(w^Tx_i + b) -1 =0$就可以了。根据KKT条件中的对偶互补条件$\alpha_{i}^{*}(y_i(w^Tx_i + b) - 1) = 0$，如果$α_i∗>0$则有$y_i(w^Tx_i + b) =1$ 即点在支持向量上，否则如果$α^∗_i=0$则有$y_i(w^Tx_i + b) \geq 1$，即样本在支持向量上或者已经被正确分类。
在软间隔最大化时，则稍微复杂一些，因为我们对每个样本$(x_i,y_i)$引入了松弛变量$\xi_i$。我们从下图来研究软间隔最大化时支持向量的情况，第i个点到对应类别支持向量的距离为$\frac{\xi_i}{||w||_2}$。根据软间隔最大化时KKT条件中的对偶互补条件$\alpha_{i}^{*}(y_i(w^Tx_i + b) - 1 + \xi_i^{*}) = 0$我们有：
a) 如果$α=0$那么$y_i(w^Tx_i + b) - 1 \geq 0$,即样本在支持向量上或者已经被正确分类。如图中所有远离支持向量的点。
b) 如果$0 < \alpha < C$,那么$\xi_i = 0 ,\;\; y_i(w^Tx_i + b) - 1 = 0$,即点在支持向量上。如图中在虚线支持向量上的点。
c) 如果$\alpha = C$，说明这是一个可能比较异常的点，需要检查此时$\xi_i$
i)如果$0 \leq \xi_i \leq 1$,那么点被正确分类，但是却在超平面和自己类别的支持向量之间。如图中的样本2和4.
ii)如果$\xi_i =1$,那么点在分离超平面上，无法被正确分类。
iii)如果$\xi_i =1$,那么点在超平面的另一侧，也就是说，这个点不能被正常分类。如图中的样本1和3.
10. 软间隔最大化的线性可分SVM的算法过程
这里我们对软间隔最大化时的线性可分SVM的算法过程做一个总结。
输入是线性可分的m个样本${(x_1,y_1), (x_2,y_2), ..., (x_m,y_m),}$,其中x为n维特征向量。y为二元输出，值为1，或者-1.
输出是分离超平面的参数$w^∗和b^∗$和分类决策函数。
算法过程如下：
1）选择一个惩罚系数$C>0$, 构造约束优化问题
$$\underbrace{ min }_{\alpha} \frac{1}{2}\sum\limits_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j - \sum\limits_{i=1}^{m}\alpha_i$$
$$s.t. \; \sum\limits_{i=1}^{m}\alpha_iy_i = 0$$
$$0 \leq \alpha_i \leq C$$
2）用SMO算法求出上式最小时对应的$α$向量的值$α^∗$向量.
3) 计算$w^{*} = \sum\limits_{i=1}^{m}\alpha_i^{*}y_ix_i$
4) 找出所有的S个支持向量,即满足$0 < \alpha_s < C$对应的样本$(x_s,y_s)$，通过 $y_s(\sum\limits_{i=1}^{S}\alpha_iy_ix_i^Tx_s+b) = 1$，计算出每个支持向量$(x_x, y_s)$对应的$b^∗_s$,计算出这些$b_s^{*} = y_s - \sum\limits_{i=1}^{S}\alpha_iy_ix_i^Tx_s$. 所有的$b^∗_s$对应的平均值即为最终的$b^{*} = \frac{1}{S}\sum\limits_{i=1}^{S}b_s^{*}$
这样最终的分类超平面为：$w^{*} \bullet x + b^{*} = 0$,最终的分类决策函数为：$f(x) = sign(w^{*} \bullet x + b^{*})$
前面我们讲到了SVM的线性分类和非线性分类，以及在分类时用到的算法。这些都关注与SVM的分类问题。实际上SVM也可以用于回归模型，接下来就对如何将SVM用于回归模型做一个总结。重点关注SVM分类和SVM回归的相同点与不同点。
11. SVM回归模型的损失函数度量
回顾下我们前面SVM分类模型中，我们的目标函数是让$\frac{1}{2}||w||_2^2$最小，同时让各个训练集中的点尽量远离自己类别一边的的支持向量，即$y_i(w \bullet \phi(x_i )+ b) \geq 1$。如果是加入一个松弛变量$\xi_i \geq 0$,则目标函数是$\frac{1}{2}||w||_2^2 +C\sum\limits_{i=1}^{m}\xi_i$,对应的约束条件变成：$y_i(w \bullet \phi(x_i ) + b ) \geq 1 - \xi_i$ 。
但是我们现在是回归模型，优化目标函数可以继续和SVM分类模型保持一致为$\frac{1}{2}||w||_2^2$，但是约束条件呢？不可能是让各个训练集中的点尽量远离自己类别一边的的支持向量，因为我们是回归模型，没有类别。对于回归模型，我们的目标是让训练集中的每个点$(x_i,y_i)$,尽量拟合到一个线性模型$y_i ~= w \bullet \phi(x_i ) +b$。对于一般的回归模型，我们是用均方差作为损失函数,但是SVM不是这样定义损失函数的。
SVM需要我们定义一个常量$\epsilon > 0$,对于某一个点$(x_i,y_i)$，如果$|y_i - w \bullet \phi(x_i ) -b| \leq \epsilon$，则完全没有损失，如果$|y_i - w \bullet \phi(x_i ) -b| > \epsilon$,则对应的损失为$|y_i - w \bullet \phi(x_i ) -b| - \epsilon$，这个均方差损失函数不同，如果是均方差，那么只要$y_i - w \bullet \phi(x_i ) -b \neq 0$，那么就会有损失。
如下图所示，在蓝色条带里面的点都是没有损失的，但是外面的点的是有损失的，损失大小为红色线的长度。
总结下，我们的SVM回归模型的损失函数度量为：
$$err(x_i,y_i) = \begin{cases} 0 & {|y_i - w \bullet \phi(x_i ) -b| \leq \epsilon}\\ |y_i - w \bullet \phi(x_i ) +b| - \epsilon & {|y_i - w \bullet \phi(x_i ) -b| > \epsilon} \end{cases}$$
12. SVM回归模型的目标函数的原始形式
上一节我们已经得到了我们的损失函数的度量，现在可以可以定义我们的目标函数如下：$$min\;\; \frac{1}{2}||w||_2^2 \;\; s.t \;\; |y_i - w \bullet \phi(x_i ) -b| \leq \epsilon (i =1,2,...m)$$
和SVM分类模型相似，回归模型也可以对每个样本$(x_i,y_i)$加入松弛变量$\xi_i \geq 0$, 但是由于我们这里用的是绝对值，实际上是两个不等式，也就是说两边都需要松弛变量，我们定义为$\xi_i^{\lor}, \xi_i^{\land}$, 则我们SVM回归模型的损失函数度量在加入松弛变量之后变为：
$$min\;\; \frac{1}{2}||w||_2^2 + C\sum\limits_{i=1}^{m}(\xi_i^{\lor}+ \xi_i^{\land})$$
$$s.t. \;\;\; -\epsilon - \xi_i^{\lor} \leq y_i - w \bullet \phi(x_i ) -b \leq \epsilon + \xi_i^{\land}$$
$$\xi_i^{\lor} \geq 0, \;\; \xi_i^{\land} \geq 0 \;(i = 1,2,..., m)$$
依然和SVM分类模型相似，我们可以用拉格朗日函数将目标优化函数变成无约束的形式，也就是拉格朗日函数的原始形式如下：
$$L(w,b,\alpha^{\lor}, \alpha^{\land}, \xi_i^{\lor}, \xi_i^{\land}, \mu^{\lor}, \mu^{\land}) = \frac{1}{2}||w||_2^2 + C\sum\limits_{i=1}^{m}(\xi_i^{\lor}+ \xi_i^{\land}) + \sum\limits_{i=1}^{m}\alpha^{\lor}(-\epsilon - \xi_i^{\lor} -y_i + w \bullet \phi(x_i) + b) +$$
$ \sum\limits_{i=1}^{m}\alpha^{\land}(y_i - w \bullet \phi(x_i ) - b -\epsilon - \xi_i^{\land}) - \sum\limits_{i=1}^{m}\mu^{\lor}\xi_i^{\lor} - \sum\limits_{i=1}^{m}\mu^{\land}\xi_i^{\land}$$
其中$$\mu^{\lor} \geq 0, \mu^{\land} \geq 0, \alpha_i^{\lor} \geq 0, \alpha_i^{\land} \geq 0$$,均为拉格朗日系数。
13. SVM回归模型的目标函数的对偶形式
上一节我们讲到了SVM回归模型的目标函数的原始形式,我们的目标是$$\underbrace{min}_{w,b,\xi_i^{\lor}, \xi_i^{\land}}\; \;\;\;\;\;\;\;\;\underbrace{max}_{\mu^{\lor} \geq 0, \mu^{\land} \geq 0, \alpha_i^{\lor} \geq 0, \alpha_i^{\land} \geq 0}\;L(w,b,\alpha^{\lor}, \alpha^{\land}, \xi_i^{\lor}, \xi_i^{\land}, \mu^{\lor}, \mu^{\land})$$
和SVM分类模型一样，这个优化目标也满足KKT条件，也就是说，我们可以通过拉格朗日对偶将我们的优化问题转化为等价的对偶问题来求解如下：$$\underbrace{max}_{\mu^{\lor} \geq 0, \mu^{\land} \geq 0, \alpha_i^{\lor} \geq 0, \alpha_i^{\land} \geq 0}\; \;\;\;\;\;\;\;\;\underbrace{min}_{w,b,\xi_i^{\lor}, \xi_i^{\land}}\;L(w,b,\alpha^{\lor}, \alpha^{\land}, \xi_i^{\lor}, \xi_i^{\land}, \mu^{\lor}, \mu^{\land})$$
我们可以先求优化函数对于$w,b,\xi_i^{\lor}, \xi_i^{\land}$的极小值, 接着再求拉格朗日乘子$\alpha^{\lor}, \alpha^{\land}, \mu^{\lor}, \mu^{\land}$的极大值。
首先我们来求优化函数对于$w,b,\xi_i^{\lor}, \xi_i^{\land}$的极小值，这个可以通过求偏导数求得：
$$\frac{\partial L}{\partial w} = 0 \;\Rightarrow w = \sum\limits_{i=1}^{m}(\alpha_i^{\land} - \alpha_i^{\lor})\phi(x_i)$$
$$\frac{\partial L}{\partial b} = 0 \;\Rightarrow \sum\limits_{i=1}^{m}(\alpha_i^{\land} - \alpha_i^{\lor}) = 0$$
$$\frac{\partial L}{\partial \xi_i^{\lor}} = 0 \;\Rightarrow C-\alpha^{\lor}-\mu^{\lor} = 0$$
$$\frac{\partial L}{\partial \xi_i^{\land}} = 0 \;\Rightarrow C-\alpha^{\land}-\mu^{\land} = 0$$
好了，我们可以把上面4个式子带入$L(w,b,\alpha^{\lor}, \alpha^{\land}, \xi_i^{\lor}, \xi_i^{\land}, \mu^{\lor}, \mu^{\land})$去消去$w,b,\xi_i^{\lor}, \xi_i^{\land}$了。
看似很复杂，其实消除过程和系列第一篇第二篇文章类似，由于式子实在是冗长，这里我就不写出推导过程了，最终得到的对偶形式为：
$$\underbrace{ max }_{\alpha^{\lor}, \alpha^{\land}}\; -\sum\limits_{i=1}^{m}(\epsilon-y_i)\alpha_i^{\land}+ (\epsilon+y_i)\alpha_i^{\lor}) - \frac{1}{2}\sum\limits_{i=1,j=1}^{m}(\alpha_i^{\land} - \alpha_i^{\lor})(\alpha_j^{\land} - \alpha_j^{\lor})K_{ij}$$
$$s.t. \; \sum\limits_{i=1}^{m}(\alpha_i^{\land} - \alpha_i^{\lor}) = 0$$
$$0 < \alpha_i^{\lor} < C \; (i =1,2,...m)$$
$$0 < \alpha_i^{\land} < C \; (i =1,2,...m)$$
对目标函数取负号，求最小值可以得到和SVM分类模型类似的求极小值的目标函数如下：
$$\underbrace{ max }_{\alpha^{\lor}, \alpha^{\land}}\; \sum\limits_{i=1}^{m}(\epsilon-y_i)\alpha_i^{\land}+ (\epsilon+y_i)\alpha_i^{\lor}) + \frac{1}{2}\sum\limits_{i=1,j=1}^{m}(\alpha_i^{\land} - \alpha_i^{\lor})(\alpha_j^{\land} - \alpha_j^{\lor})K_{ij}$$
$$s.t. \; \sum\limits_{i=1}^{m}(\alpha_i^{\land} - \alpha_i^{\lor}) = 0$$
$$0 < \alpha_i^{\lor} < C \; (i =1,2,...m)$$
$$0 < \alpha_i^{\land} < C \; (i =1,2,...m)$$
对于这个目标函数，我们依然可以用第四篇讲到的SMO算法来求出对应的$\alpha^{\lor}, \alpha^{\land}$，进而求出我们的回归模型系数$w, b$。
14. SVM回归模型系数的稀疏性
在SVM分类模型中，我们的KKT条件的对偶互补条件为： $\alpha_{i}^{*}(y_i(w \bullet \phi(x_i) + b) - 1+\xi_i^{*}) = 0$，而在回归模型中，我们的对偶互补条件类似如下：$$\alpha_i^{\lor}(\epsilon + \xi_i^{\lor} + y_i - w \bullet \phi(x_i ) - b ) = 0$$
$$\alpha_i^{\land}(\epsilon + \xi_i^{\land} - y_i + w \bullet \phi(x_i ) + b ) = 0$$
根据松弛变量定义条件，如果$|y_i - w \bullet \phi(x_i ) -b| < \epsilon$，我们有$\xi_i^{\lor} = 0, \xi_i^{\land}= 0$，此时$\epsilon + \xi_i^{\lor} + y_i - w \bullet \phi(x_i ) - b \neq 0, \epsilon + \xi_i^{\land} - y_i + w \bullet \phi(x_i ) + b \neq 0$这样要满足对偶互补条件，只有$\alpha_i^{\lor} = 0, \alpha_i^{\land} = 0$。
我们定义样本系数系数$$\beta_i =\alpha_i^{\land}-\alpha_i^{\lor}$$
根据上面$w$的计算式$w = \sum\limits_{i=1}^{m}(\alpha_i^{\land} - \alpha_i^{\lor})\phi(x_i)$，我们发现此时$β_i=0$,也就是说ww不受这些在误差范围内的点的影响。对于在边界上或者在边界外的点，$\alpha_i^{\lor} \neq 0, \alpha_i^{\land} \neq 0$，此时$β_i≠0$。
针对SVM算法中涉及的KTT和SMO两大点，原博客中没有讲得特别清楚，我将在后面总结出来。
