大家好，又见面了，我是你们的朋友全栈君。

支持向量回归(Support Vector Regression)

支持向量机除了能够分类，还可以用于回归。

回归的目的是得到一个能够尽量拟合训练集样本的模型$f(\mathbf{x})$，通常用的方法是构建一个样本标签与模型预测值的损失函数，使损失函数最小化从而确定模型$f(\mathbf{x})$。

例如，在线性回归模型中，损失函数(L2损失，L1损失，huber损失)由模型输出$f(\mathbf{x})$与真实输出$y$之间的差别来计算，通过最小化损失函数来确定模型$f(\mathbf{x})$，当且仅当$f(\mathbf{x})$与$y$完全相等时，损失才为0。

那支持向量机是如何用于回归的呢？

支持向量机的精髓在于间隔最大化。

• 在分类任务中，使靠超平面最近的样本点之间的间隔最大；

• 而在回归任务中，同样也是间隔最大，不同的是它使靠超平面最远的样本点之间的间隔最大。

如果使靠超平面最远的样本点之间的间隔最大，那么上图样本点的回归超平面结果就应该变成下左图那样。

显然，我们希望回归能达到右图的效果，于是SVR对间隔加了限制，对所有的样本点，回归模型$f(\mathbf{x})$与$y$的偏差必须$\le \epsilon$。我们把这个偏差范围称作$\epsilon$管道。

依据以上的思路，SVR的优化问题可以用数学式表示为
$$\begin{array}{rl}& \underset{\mathbf{w},b}{\min }\frac{1}{2}||\mathbf{w}|{|}_2^2\\ s.t.|y_i-({\mathbf{w}}^T& {\mathbf{x}}_i+b)|\le \epsilon ,i=1,2,\cdots ,N\end{array}$$
SVR的目的是：保证所有样本点在$\epsilon$管道内的前提下，回归超平面$f(\mathbf{x})$尽可能地平。

在$\epsilon$不变的前提下，回归超平面$f(\mathbf{x})$尽可能平和间隔尽可能大是等效的。

带松弛变量的SVR

实际应用中，$\epsilon$设置太小无法保证所有样本点都在$\epsilon$管道内，$\epsilon$太大回归超平面会被一些异常点带偏。

和软间隔SVM模型类似，SVR允许每个样本$({\mathbf{x}}_i,y_i)$添加松弛变量${\xi }_i\ge 0$，用来描述样本点偏离$\epsilon$管道的程度。

如何添加松弛变量？

如果直接在约束条件中加上松弛变量，变成$|y_i-({\mathbf{w}}^T{\mathbf{x}}_i+b)|\le \epsilon +{\xi }_i$，即
$$\{\begin{array}{rl}{y}_i-({\mathbf{w}}^T{\mathbf{x}}_i+b)& \le \epsilon +{\xi }_i上界约束\\ ({\mathbf{w}}^T{\mathbf{x}}_i+b)-y_i& \le \epsilon +{\xi }_i下界约束\end{array}$$

显然，超出间隔上界的样本点影响到了下界面的约束。

那么是否可以对超出不同界面的样本点分开添加松弛变量？

比如：样本点超出间隔上界，我们令
$$\{\begin{array}{rl}{y}_i-({\mathbf{w}}^T{\mathbf{x}}_i+b)& \le \epsilon +{\xi }_i上界约束\\ ({\mathbf{w}}^T{\mathbf{x}}_i+b)-y_i& \le \epsilon 下界约束\end{array}$$
超出间隔下界，令
$$\{\begin{array}{rl}{y}_i-({\mathbf{w}}^T{\mathbf{x}}_i+b)& \le \epsilon 上界约束\\ ({\mathbf{w}}^T{\mathbf{x}}_i+b)-y_i& \le \epsilon +{\xi }_i下界约束\end{array}$$
但是事先不知道样本点超出的是上界还是下界，因此也不可行，而且超出上界和超出下界的约束条件形式还不相同。

其实，上下界的松弛变量可以用不同符号来表示：${\xi }_i^{\bigwedge }\ge 0,{\xi }_i^{\bigvee }\ge 0$，约束条件变成
$$\{\begin{array}{rl}{y}_i-({\mathbf{w}}^T{\mathbf{x}}_i+b)& \le \epsilon +{\xi }_i^{\bigwedge }上界约束\\ ({\mathbf{w}}^T{\mathbf{x}}_i+b)-y_i& \le \epsilon +{\xi }_i^{\bigvee }下界约束\end{array}$$
当${\xi }_i^{\bigwedge }\ne 0,{\xi }_i^{\bigvee }=0$时，样本点超出上界；

当${\xi }_i^{\bigwedge }=0,{\xi }_i^{\bigvee }\ne 0$时，样本点超出下界；

当${\xi }_i^{\bigwedge }=0,{\xi }_i^{\bigvee }=0$时，样本点在$\epsilon$通道内。

${\xi }_i^{\bigwedge }\ne 0,{\xi }_i^{\bigvee }\ne 0$这种情况不可能出现，因为这表示样本点既超出上界又超出下界，明显不可能发生。

引入松弛变量，SVR的优化问题形式为
$$\begin{array}{rl}& \underset{\mathbf{w},b}{\min }\frac{1}{2}||\mathbf{w}|{|}_2^2+C\sum _{i=1}^N({\xi }_i^{\bigvee }+{\xi }_i^{\bigwedge })\\ s.t.-\epsilon -{\xi }_i^{\bigvee }& \le y_i-({\mathbf{w}}^T{\mathbf{x}}_i+b)\le \epsilon +{\xi }_i^{\bigwedge },i=1,2,\cdots ,N\\ & {\xi }_i^{\bigvee }\ge 0,{\xi }_i^{\bigwedge }\ge 0,i=1,2,\cdots ,N\end{array}$$

带松弛变量的SVR目标函数的优化

依然与SVM分类模型类似，先用拉格朗日乘子法，将目标函数变成：
$$\begin{array}{rl}& L(\mathbf{w},b,{\mathbf{\alpha }}^{\bigvee },{\mathbf{\alpha }}^{\bigwedge },{\mathbf{\xi }}^{\bigvee },{\mathbf{\xi }}^{\bigwedge },{\mathbf{\mu }}^{\bigvee },{\mathbf{\mu }}^{\bigwedge })\\ =& \frac{1}{2}||\mathbf{w}|{|}_2^2+C\sum _{i=1}^N({\xi }_i^{\bigvee }+{\xi }_i^{\bigwedge })+\sum _{i=1}^N{\alpha }_i^{\bigvee }[-\epsilon -{\xi }_i^{\bigvee }-y_i+({\mathbf{w}}^T{\mathbf{x}}_i+b)]\\ & +\sum _{i=1}^N{\alpha }_i^{\bigwedge }[y_i-({\mathbf{w}}^T{\mathbf{x}}_i+b)-\epsilon -{\xi }_i^{\bigwedge }]-\sum _{i=1}^N{\mu }_i^{\bigvee }{\xi }_i^{\bigvee }-\sum _{i=1}^N{\mu }_i^{\bigwedge }{\xi }_i^{\bigwedge }\end{array}$$

其中，${\alpha }_i^{\bigvee }\ge 0,{\alpha }_i^{\bigwedge }\ge 0,{\mu }_i^{\bigvee }\ge 0,{\mu }_i^{\bigwedge }\ge 0$都是拉格朗日系数。

那么优化问题变为
$$\begin{array}{rl}\underset{\mathbf{w},b,{\mathbf{\xi }}^{\bigvee },{\mathbf{\xi }}^{\bigwedge }}{\min }\underset{{\mathbf{\alpha }}^{\bigvee },{\mathbf{\alpha }}^{\bigwedge },{\mathbf{\mu }}^{\bigvee },{\mathbf{\mu }}^{\bigwedge }}{\max }L(& \mathbf{w},b,{\mathbf{\alpha }}^{\bigvee },{\mathbf{\alpha }}^{\bigwedge },{\mathbf{\xi }}^{\bigvee },{\mathbf{\xi }}^{\bigwedge },{\mathbf{\mu }}^{\bigvee },{\mathbf{\mu }}^{\bigwedge })\\ s.t.{\xi }_i^{\bigvee }\ge 0,& i=1,2,\cdots ,N\\ {\xi }_i^{\bigwedge }\ge 0,& i=1,2,\cdots ,N\\ {\alpha }_i^{\bigvee }\ge 0,& i=1,2,\cdots ,N\\ {\alpha }_i^{\bigwedge }\ge 0,& i=1,2,\cdots ,N\\ {\mu }_i^{\bigvee }\ge 0,& i=1,2,\cdots ,N\\ {\mu }_i^{\bigwedge }\ge 0,& i=1,2,\cdots ,N\end{array}$$
优化问题满足KKT条件，可以等价为对偶问题
$$\begin{array}{rl}\underset{{\mathbf{\alpha }}^{\bigvee },{\mathbf{\alpha }}^{\bigwedge },{\mathbf{\mu }}^{\bigvee },{\mathbf{\mu }}^{\bigwedge }}{\max }\underset{\mathbf{w},b,{\mathbf{\xi }}^{\bigvee },{\mathbf{\xi }}^{\bigwedge }}{\min }L(& \mathbf{w},b,{\mathbf{\alpha }}^{\bigvee },{\mathbf{\alpha }}^{\bigwedge },{\mathbf{\xi }}^{\bigvee },{\mathbf{\xi }}^{\bigwedge },{\mathbf{\mu }}^{\bigvee },{\mathbf{\mu }}^{\bigwedge })\\ s.t.{\xi }_i^{\bigvee }\ge 0,& i=1,2,\cdots ,N\\ {\xi }_i^{\bigwedge }\ge 0,& i=1,2,\cdots ,N\\ {\alpha }_i^{\bigvee }\ge 0,& i=1,2,\cdots ,N\\ {\alpha }_i^{\bigwedge }\ge 0,& i=1,2,\cdots ,N\\ {\mu }_i^{\bigvee }\ge 0,& i=1,2,\cdots ,N\\ {\mu }_i^{\bigwedge }\ge 0,& i=1,2,\cdots ,N\end{array}$$
先求目标函数的最小化问题
$$\underset{\mathbf{w},b,{\mathbf{\xi }}^{\bigvee },{\mathbf{\xi }}^{\bigwedge }}{\min }L(\mathbf{w},b,{\mathbf{\alpha }}^{\bigvee },{\mathbf{\alpha }}^{\bigwedge },{\mathbf{\xi }}^{\bigvee },{\mathbf{\xi }}^{\bigwedge },{\mathbf{\mu }}^{\bigvee },{\mathbf{\mu }}^{\bigwedge })$$
对参数求偏导得：
$$\{\begin{array}{rl}& \frac{\partial L}{\partial \mathbf{w}}=0\Rightarrow \mathbf{w}=\sum _{i=1}^N({\alpha }_i^{\bigwedge }-{\alpha }_i^{\bigvee }){\mathbf{x}}_i\\ & \frac{\partial L}{\partial b}=0\Rightarrow \sum _{i=1}^N({\alpha }_i^{\bigwedge }-{\alpha }_i^{\bigvee })=0\\ & \frac{\partial L}{\partial {\xi }_i^{\bigvee }}=0\Rightarrow C-{\alpha }_i^{\bigvee }-{\mu }_i^{\bigvee }=0\\ & \frac{\partial L}{\partial {\xi }_i^{\bigwedge }}=0\Rightarrow C-{\alpha }_i^{\bigwedge }-{\mu }_i^{\bigwedge }=0\end{array}$$
令
$$\psi ({\mathbf{\alpha }}^{\bigvee },{\mathbf{\alpha }}^{\bigwedge },{\mathbf{\mu }}^{\bigvee },{\mathbf{\mu }}^{\bigwedge })=\underset{\mathbf{w},b,{\mathbf{\xi }}^{\bigvee },{\mathbf{\xi }}^{\bigwedge }}{\min }L(\mathbf{w},b,{\mathbf{\alpha }}^{\bigvee },{\mathbf{\alpha }}^{\bigwedge },{\mathbf{\xi }}^{\bigvee },{\mathbf{\xi }}^{\bigwedge },{\mathbf{\mu }}^{\bigvee },{\mathbf{\mu }}^{\bigwedge })$$
把以上偏导结果代入目标函数得到
$$\begin{array}{rl}& \psi ({\mathbf{\alpha }}^{\bigvee },{\mathbf{\alpha }}^{\bigwedge },{\mathbf{\mu }}^{\bigvee },{\mathbf{\mu }}^{\bigwedge })\\ =& \frac{1}{2}||\mathbf{w}|{|}_2^2+C\sum _{i=1}^N({\xi }_i^{\bigvee }+{\xi }_i^{\bigwedge })+\sum _{i=1}^N{\alpha }_i^{\bigvee }[-\epsilon -{\xi }_i^{\bigvee }-y_i+({\mathbf{w}}^T{\mathbf{x}}_i+b)]\\ & +\sum _{i=1}^N{\alpha }_i^{\bigwedge }[y_i-({\mathbf{w}}^T{\mathbf{x}}_i+b)-\epsilon -{\xi }_i^{\bigwedge }]-\sum _{i=1}^N{\mu }_i^{\bigvee }{\xi }_i^{\bigvee }-\sum _{i=1}^N{\mu }_i^{\bigwedge }{\xi }_i^{\bigwedge }\\ =& \frac{1}{2}||\mathbf{w}|{|}_2^2+\sum _{i=1}^N[(C-{\alpha }_i^{\bigvee }-{\mu }_i^{\bigvee }){\xi }_i^{\bigvee }+(C-{\alpha }_i^{\bigwedge }-{\mu }_i^{\bigwedge }){\xi }_i^{\bigwedge }]\\ & +\sum _{i=1}^N{\alpha }_i^{\bigvee }[-\epsilon -y_i+({\mathbf{w}}^T{\mathbf{x}}_i+b)]+\sum _{i=1}^N{\alpha }_i^{\bigwedge }[y_i-({\mathbf{w}}^T{\mathbf{x}}_i+b)-\epsilon ]\\ =& \frac{1}{2}||\mathbf{w}|{|}_2^2+\sum _{i=1}^N{\alpha }_i^{\bigvee }[-\epsilon -y_i+({\mathbf{w}}^T{\mathbf{x}}_i+b)]+\sum _{i=1}^N{\alpha }_i^{\bigwedge }[y_i-({\mathbf{w}}^T{\mathbf{x}}_i+b)-\epsilon ]\\ =& \frac{1}{2}{\mathbf{w}}^T\mathbf{w}-{\mathbf{w}}^T\sum _{i=1}^N({\alpha }_i^{\bigwedge }-{\alpha }_i^{\bigvee }){\mathbf{x}}_i+b\sum _{i=1}^N({\alpha }_i^{\bigvee }-{\alpha }_i^{\bigwedge })-\sum _{i=1}^N[(\epsilon -y_i){\alpha }_i^{\bigwedge }+(\epsilon +y_i){\alpha }_i^{\bigvee }]\\ =& \frac{1}{2}{\mathbf{w}}^T\sum _{i=1}^N({\alpha }_i^{\bigwedge }-{\alpha }_i^{\bigvee }){\mathbf{x}}_i-{\mathbf{w}}^T\sum _{i=1}^N({\alpha }_i^{\bigwedge }-{\alpha }_i^{\bigvee }){\mathbf{x}}_i-\sum _{i=1}^N[(\epsilon -y_i){\alpha }_i^{\bigwedge }+(\epsilon +y_i){\alpha }_i^{\bigvee }]\\ =& -\frac{1}{2}{\mathbf{w}}^T\sum _{i=1}^N({\alpha }_i^{\bigwedge }-{\alpha }_i^{\bigvee }){\mathbf{x}}_i-\sum _{i=1}^N[(\epsilon -y_i){\alpha }_i^{\bigwedge }+(\epsilon +y_i){\alpha }_i^{\bigvee }]\\ =& -\frac{1}{2}[\sum _{j=1}^N({\alpha }_j^{\bigwedge }-{\alpha }_j^{\bigvee }){\mathbf{x}}_j{]}^T\sum _{i=1}^N({\alpha }_i^{\bigwedge }-{\alpha }_i^{\bigvee }){\mathbf{x}}_i-\sum _{i=1}^N[(\epsilon -y_i){\alpha }_i^{\bigwedge }+(\epsilon +y_i){\alpha }_i^{\bigvee }]\\ =& -\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N({\alpha }_i^{\bigwedge }-{\alpha }_i^{\bigvee })({\alpha }_j^{\bigwedge }-{\alpha }_j^{\bigvee }){\mathbf{x}}_j^T{\mathbf{x}}_i-\sum _{i=1}^N[(\epsilon -y_i){\alpha }_i^{\bigwedge }+(\epsilon +y_i){\alpha }_i^{\bigvee }]\\ =& -\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N({\alpha }_i^{\bigwedge }-{\alpha }_i^{\bigvee })({\alpha }_j^{\bigwedge }-{\alpha }_j^{\bigvee }){\mathbf{x}}_i^T{\mathbf{x}}_j-\sum _{i=1}^N[(\epsilon -y_i){\alpha }_i^{\bigwedge }+(\epsilon +y_i){\alpha }_i^{\bigvee }]\end{array}$$
因为目标函数已经消去了参数${\mathbf{\xi }}^{\bigvee }$和${\mathbf{\xi }}^{\bigwedge }$，所以相应的约束条件也可以去掉。

剩下约束条件
$$\begin{array}{rl}{\alpha }_i^{\bigvee }\ge 0,& i=1,2,\cdots ,N\\ {\alpha }_i^{\bigwedge }\ge 0,& i=1,2,\cdots ,N\\ {\mu }_i^{\bigvee }\ge 0,& i=1,2,\cdots ,N\\ {\mu }_i^{\bigwedge }\ge 0,& i=1,2,\cdots ,N\end{array}$$
联合等式
$$\begin{array}{rl}C-{\alpha }_i^{\bigvee }-{\mu }_i^{\bigvee }=0,& i=1,2,\cdots ,N\\ C-{\alpha }_i^{\bigwedge }-{\mu }_i^{\bigwedge }=0,& i=1,2,\cdots ,N\end{array}$$
可以去掉${\mu }_i^{\bigvee },{\mu }_i^{\bigwedge }$，等效为
$$\begin{array}{rl}0\le {\alpha }_i^{\bigvee }\le C,& i=1,2,\cdots ,N\\ 0\le {\alpha }_i^{\bigwedge }\le C,& i=1,2,\cdots ,N\end{array}$$

去掉包含参数${\mu }_i^{\bigvee },{\mu }_i^{\bigwedge }$的约束条件的原因和软间隔SVM分类模型的类似，是为了让整个优化问题涉及的参数尽量少，方便优化问题的求解。

综上，优化问题的数学形式表示为：
$$\begin{array}{rl}\underset{{\mathbf{\alpha }}^{\bigvee },{\mathbf{\alpha }}^{\bigwedge }}{\max }-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N({\alpha }_i^{\bigwedge }-& {\alpha }_i^{\bigvee })({\alpha }_j^{\bigwedge }-{\alpha }_j^{\bigvee }){\mathbf{x}}_i^T{\mathbf{x}}_j-\sum _{i=1}^N[(\epsilon -y_i){\alpha }_i^{\bigwedge }+(\epsilon +y_i){\alpha }_i^{\bigvee }]\\ s.t.& \sum _{i=1}^N({\alpha }_i^{\bigwedge }-{\alpha }_i^{\bigvee })=0\\ & 0\le {\alpha }_i^{\bigvee }\le C,i=1,2,\cdots ,N\\ & 0\le {\alpha }_i^{\bigwedge }\le C,i=1,2,\cdots ,N\end{array}$$
目标函数去掉负号，将上述的最大化问题变成最小化问题，得到等价问题：
$$\begin{array}{rl}\underset{{\mathbf{\alpha }}^{\bigvee },{\mathbf{\alpha }}^{\bigwedge }}{\min }\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N({\alpha }_i^{\bigwedge }-& {\alpha }_i^{\bigvee })({\alpha }_j^{\bigwedge }-{\alpha }_j^{\bigvee }){\mathbf{x}}_i^T{\mathbf{x}}_j+\sum _{i=1}^N[(\epsilon -y_i){\alpha }_i^{\bigwedge }+(\epsilon +y_i){\alpha }_i^{\bigvee }]\\ s.t.& \sum _{i=1}^N({\alpha }_i^{\bigwedge }-{\alpha }_i^{\bigvee })=0\\ & 0\le {\alpha }_i^{\bigvee }\le C,i=1,2,\cdots ,N\\ & 0\le {\alpha }_i^{\bigwedge }\le C,i=1,2,\cdots ,N\end{array}$$
通过SMO算法可以求得最优参数${{\mathbf{\alpha }}^{\bigvee }}^{\ast }$和${{\mathbf{\alpha }}^{\bigwedge }}^{\ast }$，然后计算
$${\mathbf{w}}^{\ast }=\sum _{i=1}^N({{\alpha }_i^{\bigwedge }}^{\ast }-{{\alpha }_i^{\bigvee }}^{\ast }){\mathbf{x}}_i$$

与软间隔SVM分类模型类似，SVR的支持向量并不都在最大间隔边界上，而且SVR上下界的数学表达式还不相同，为方便处理，我们只选用下界的支持向量(当然，你也可以选用上界的支持向量)。

对任一下界的支持向量$({\mathbf{x}}_k,y_k)$，有
$$b^{\ast }=y_k+ϵ-{{\mathbf{w}}^{\ast }}^T{\mathbf{x}}_k$$

实践中常采用一种求$b^{\ast }$的更鲁棒(robust)的方法：选取多个(或所有)下界(或上界)的支持向量求解b后再取平均。

SVM回归模型的支持向量

已知KKT条件(部分，不是全部)：
$$\begin{array}{rl}C-{\alpha }_i^{\bigvee }-{\mu }_i^{\bigvee }=0,& i=1,2,\cdots ,N\\ C-{\alpha }_i^{\bigwedge }-{\mu }_i^{\bigwedge }=0,& i=1,2,\cdots ,N\\ {\alpha }_i^{\bigvee }[\epsilon +{\xi }_i^{\bigvee }+y_i-({\mathbf{w}}^T{\mathbf{x}}_i+b)]=0,& i=1,2,\cdots ,N\\ {\alpha }_i^{\bigwedge }[\epsilon +{\xi }_i^{\bigwedge }-y_i+({\mathbf{w}}^T{\mathbf{x}}_i+b)]=0,& i=1,2,\cdots ,N\\ {\mu }_i^{\bigvee }{\xi }_i^{\bigvee }=0,& i=1,2,\cdots ,N\\ {\mu }_i^{\bigwedge }{\xi }_i^{\bigwedge }=0,& i=1,2,\cdots ,N\\ y_i\ge ({\mathbf{w}}^T{\mathbf{x}}_i+b)-\epsilon -{\xi }_i^{\bigvee },& i=1,2,\cdots ,N\\ y_i\le ({\mathbf{w}}^T{\mathbf{x}}_i+b)+\epsilon +{\xi }_i^{\bigwedge },& i=1,2,\cdots ,N\\ {\xi }_i^{\bigvee }\ge 0,& i=1,2,\cdots ,N\\ {\xi }_i^{\bigwedge }\ge 0,& i=1,2,\cdots ,N\\ {\alpha }_i^{\bigvee }\ge 0,& i=1,2,\cdots ,N\\ {\alpha }_i^{\bigwedge }\ge 0,& i=1,2,\cdots ,N\\ {\mu }_i^{\bigvee }\ge 0,& i=1,2,\cdots ,N\\ {\mu }_i^{\bigwedge }\ge 0,& i=1,2,\cdots ,N\end{array}$$

我们有以下推论：

• 如果${\alpha }_i^{\bigvee }\ne 0$且${\alpha }_i^{\bigwedge }\ne 0$，那么根据
  $$\{\begin{array}{rl}{\alpha }_i^{\bigvee }[\epsilon +{\xi }_i^{\bigvee }+y_i-({\mathbf{w}}^T{\mathbf{x}}_i+b)]& =0\\ {\alpha }_i^{\bigwedge }[\epsilon +{\xi }_i^{\bigwedge }-y_i+({\mathbf{w}}^T{\mathbf{x}}_i+b)]& =0\end{array}$$
  样本点$({\mathbf{x}}_i,y_i)$就必须满足
  $$\{\begin{array}{rl}\epsilon +{\xi }_i^{\bigvee }+y_i-({\mathbf{w}}^T{\mathbf{x}}_i+b)& =0\\ \epsilon +{\xi }_i^{\bigwedge }-y_i+({\mathbf{w}}^T{\mathbf{x}}_i+b)& =0\end{array}$$
  即
  $$\{\begin{array}{r}{y}_i=({\mathbf{w}}^T{\mathbf{x}}_i+b)-\epsilon -{\xi }_i^{\bigvee }\\ y_i=({\mathbf{w}}^T{\mathbf{x}}_i+b)+\epsilon +{\xi }_i^{\bigwedge }\end{array}$$
  因为
  $$\{\begin{array}{r}{\xi }_i^{\bigvee }\ge 0\\ {\xi }_i^{\bigwedge }\ge 0\end{array}$$

  所以样本点$({\mathbf{x}}_i,y_i)$同时在上界外和下界外，显然是不可能的。

• 如果${\alpha }_i^{\bigvee }=0$且${\alpha }_i^{\bigwedge }=0$，根据
  $$\{\begin{array}{rl}C-{\alpha }_i^{\bigvee }-{\mu }_i^{\bigvee }& =0\\ C-{\alpha }_i^{\bigwedge }-{\mu }_i^{\bigwedge }& =0\end{array}$$
  有
  $$\{\begin{array}{rl}{\mu }_i^{\bigvee }& =C\\ {\mu }_i^{\bigwedge }& =C\end{array}$$
  再根据
  $$\{\begin{array}{rl}{\mu }_i^{\bigvee }{\xi }_i^{\bigvee }& =0\\ {\mu }_i^{\bigwedge }{\xi }_i^{\bigwedge }& =0\end{array}$$
  有
  $$\{\begin{array}{rl}{\xi }_i^{\bigvee }& =0\\ {\xi }_i^{\bigwedge }& =0\end{array}$$
  所以
  $$\{\begin{array}{rl}{y}_i& \ge ({\mathbf{w}}^T{\mathbf{x}}_i+b)-\epsilon \\ y_i& \le ({\mathbf{w}}^T{\mathbf{x}}_i+b)+\epsilon \end{array}$$
  样本点$({\mathbf{x}}_i,y_i)$在$\epsilon$通道内，不是支持向量；

上面两种情况的讨论可以总结出
$$\begin{array}{rl}{\alpha }_i^{\bigvee }\ne 0& \Rightarrow y_i=({\mathbf{w}}^T{\mathbf{x}}_i+b)-\epsilon -{\xi }_i^{\bigvee }\\ {\alpha }_i^{\bigwedge }\ne 0& \Rightarrow y_i=({\mathbf{w}}^T{\mathbf{x}}_i+b)+\epsilon +{\xi }_i^{\bigwedge }\\ {\alpha }_i^{\bigvee }=0& \Rightarrow y_i\ge ({\mathbf{w}}^T{\mathbf{x}}_i+b)-\epsilon \\ {\alpha }_i^{\bigwedge }=0& \Rightarrow y_i\le ({\mathbf{w}}^T{\mathbf{x}}_i+b)+\epsilon \end{array}$$

• 如果${\alpha }_i^{\bigvee }\ne 0$且${\alpha }_i^{\bigwedge }=0$，有
  $$\{\begin{array}{rl}{y}_i& =({\mathbf{w}}^T{\mathbf{x}}_i+b)-\epsilon -{\xi }_i^{\bigvee }\\ y_i& \le ({\mathbf{w}}^T{\mathbf{x}}_i+b)+\epsilon \end{array}\Rightarrow y_i=({\mathbf{w}}^T{\mathbf{x}}_i+b)-\epsilon -{\xi }_i^{\bigvee }$$
  说明样本点$({\mathbf{x}}_i,y_i)$在最大间隔的下界外，是支持向量。

可以更进一步讨论：

• 如果$0<{\alpha }_i^{\bigvee }<C$，根据
  $$C-{\alpha }_i^{\bigvee }-{\mu }_i^{\bigvee }=0$$
  可知
  $${\mu }_i^{\bigvee }>0$$
  由
  $${\mu }_i^{\bigvee }{\xi }_i^{\bigvee }=0$$
  得出
  $${\xi }_i^{\bigvee }=0$$
  因此
  $$y_i=({\mathbf{w}}^T{\mathbf{x}}_i+b)-\epsilon$$
  说明样本点$({\mathbf{x}}_i,y_i)$恰好落在最大间隔的下界；

• 如果${\alpha }_i^{\bigvee }=C$，根据
  $$C-{\alpha }_i^{\bigvee }-{\mu }_i^{\bigvee }=0$$
  可知
  $${\mu }_i^{\bigvee }=0$$
  由
  $${\mu }_i^{\bigvee }{\xi }_i^{\bigvee }=0$$
  得出
  $${\xi }_i^{\bigvee }\ge 0$$
  由于样本点$({\mathbf{x}}_i,y_i)$满足
  $$y_i=({\mathbf{w}}^T{\mathbf{x}}_i+b)-\epsilon -{\xi }_i^{\bigvee }$$
  说明样本点$({\mathbf{x}}_i,y_i)$不高于最大间隔的下界；

• 同理，如果${\alpha }_i^{\bigvee }=0$且${\alpha }_i^{\bigwedge }\ne 0$，那么有
  $$\{\begin{array}{rl}{y}_i& =({\mathbf{w}}^T{\mathbf{x}}_i+b)+\epsilon +{\xi }_i^{\bigwedge }\\ y_i& \ge ({\mathbf{w}}^T{\mathbf{x}}_i+b)-\epsilon \end{array}\Rightarrow y_i=({\mathbf{w}}^T{\mathbf{x}}_i+b)+\epsilon +{\xi }_i^{\bigwedge }$$
  说明样本点$({\mathbf{x}}_i,y_i)$在最大间隔的上界外，是支持向量。

• 如果$0<{\alpha }_i^{\bigwedge }<C$，根据
  $$C-{\alpha }_i^{\bigwedge }-{\mu }_i^{\bigwedge }=0$$
  可知
  $${\mu }_i^{\bigwedge }>0$$
  由
  $${\mu }_i^{\bigwedge }{\xi }_i^{\bigwedge }=0$$
  得出
  $${\xi }_i^{\bigwedge }=0$$
  因此
  $$y_i=({\mathbf{w}}^T{\mathbf{x}}_i+b)+\epsilon$$
  样本点$({\mathbf{x}}_i,y_i)$恰好落在最大间隔的上界；

• 如果${\alpha }_i^{\bigwedge }=C$，根据
  $$C-{\alpha }_i^{\bigwedge }-{\mu }_i^{\bigwedge }=0$$
  可知
  $${\mu }_i^{\bigwedge }=0$$
  由
  $${\mu }_i^{\bigwedge }{\xi }_i^{\bigwedge }=0$$
  得出
  $${\xi }_i^{\bigwedge }\ge 0$$
  由于样本点$({\mathbf{x}}_i,y_i)$满足
  $$y_i=({\mathbf{w}}^T{\mathbf{x}}_i+b)+\epsilon +{\xi }_i^{\bigwedge }$$
  说明样本点$({\mathbf{x}}_i,y_i)$不低于最大间隔的上界；

所以，当$0<{\alpha }_i^{\bigvee }<C$时，样本点是落在最大间隔下界的支持向量。

如果你要找落在最大间隔上界的支持向量，应该要找$0<{\alpha }_i^{\bigwedge }<C$的样本点。

SVR的算法过程

输入：训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) } T=\{(\mathbf{x}_1,y_1), (\mathbf{x}_2,y_2), \cdots, (\mathbf{x}_N,y_N)\} T={
(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}。

输出：分离超平面和分类决策函数。

算法步骤：

1. 选择一个惩罚系数$C>0$，构造约束优化问题
   $$\begin{array}{rl}\underset{{\mathbf{\alpha }}^{\bigvee },{\mathbf{\alpha }}^{\bigwedge }}{\min }\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N({\alpha }_i^{\bigwedge }-& {\alpha }_i^{\bigvee })({\alpha }_j^{\bigwedge }-{\alpha }_j^{\bigvee }){\mathbf{x}}_i^T{\mathbf{x}}_j+\sum _{i=1}^N[(\epsilon -y_i){\alpha }_i^{\bigwedge }+(\epsilon +y_i){\alpha }_i^{\bigvee }]\\ s.t.& \sum _{i=1}^N({\alpha }_i^{\bigwedge }-{\alpha }_i^{\bigvee })=0\\ & 0\le {\alpha }_i^{\bigvee }\le C,i=1,2,\cdots ,N\\ & 0\le {\alpha }_i^{\bigwedge }\le C,i=1,2,\cdots ,N\end{array}$$

2. 用SMO算法求出最优参数${{\mathbf{\alpha }}^{\bigvee }}^{\ast }$和${{\mathbf{\alpha }}^{\bigwedge }}^{\ast }$。

3. 计算${\mathbf{w}}^{\ast }={\sum }_{i=1}^N({{\alpha }_i^{\bigwedge }}^{\ast }-{{\alpha }_i^{\bigvee }}^{\ast }){\mathbf{x}}_i$。

4. 寻找一个满足$0<{{\alpha }_i^{\bigvee }}^{\ast }<C$的样本点$({\mathbf{x}}_k,y_k)$，计算$b^{\ast }=y_k+ϵ-{{\mathbf{w}}^{\ast }}^T{\mathbf{x}}_k$。

5. 构建最终的回归超平面${{\mathbf{w}}^{\ast }}^T\mathbf{x}+b^{\ast }=0$和预测函数$f(x)=\text{sgn}({{\mathbf{w}}^{\ast }}^T\mathbf{x}+b^{\ast })$。

与SVM类似，非线性情况下SVR也可以使用核方法，算法流程只要将内积${\mathbf{x}}_i^T{\mathbf{x}}_j$都替换成核函数$\kappa ({\mathbf{x}}_i,{\mathbf{x}}_j)$即可。

带松弛变量的SVR的一种解释：$\epsilon$不敏感损失+L2正则

$\epsilon$不敏感损失($\epsilon$-insensitive loss)

$\epsilon$不敏感损失表达式
$$L_{\epsilon }(x)=\{\begin{array}{r}0,|x|\le \epsilon \\ |x|-\epsilon ,|x|>\epsilon \end{array}$$

带松弛变量的SVR的一种解释

带松弛变量的SVR的优化函数：$L(\mathbf{w},b)=\frac{1}{2}||\mathbf{w}|{|}_2^2+C{\sum }_{i=1}^N({\xi }_i^{\bigvee }+{\xi }_i^{\bigwedge })$

根据之前对支持向量的讨论，有下列结论：

• 对于在$\epsilon$管道内的样本点$({\mathbf{x}}_i,y_i)$，即$|y_i-({\mathbf{w}}^T{\mathbf{x}}_i+b)|\le \epsilon$

  ${\xi }_i^{\bigvee }=0$，${\xi }_i^{\bigwedge }=0$，所以${\xi }_i^{\bigvee }+{\xi }_i^{\bigwedge }=0$。

• 对于在$\epsilon$管道外的样本点$({\mathbf{x}}_i,y_i)$，即$|y_i-({\mathbf{w}}^T{\mathbf{x}}_i+b)|\ge \epsilon$

  • 如果不低于间隔上界

    有${\xi }_i^{\bigvee }=0$，$y_i-({\mathbf{w}}^T{\mathbf{x}}_i+b)=\epsilon +{\xi }_i^{\bigwedge }$，即${\xi }_i^{\bigwedge }=y_i-({\mathbf{w}}^T{\mathbf{x}}_i+b)-\epsilon$。

    所以${\xi }_i^{\bigvee }+{\xi }_i^{\bigwedge }=|y_i-({\mathbf{w}}^T{\mathbf{x}}_i+b)|-\epsilon$。

  • 如果不高于间隔下界

    有${\xi }_i^{\bigwedge }=0$，$({\mathbf{w}}^T{\mathbf{x}}_i+b)-y_i=\epsilon +{\xi }_i^{\bigvee }$，即${\xi }_i^{\bigvee }=({\mathbf{w}}^T{\mathbf{x}}_i+b)-y_i-\epsilon$。

    所以${\xi }_i^{\bigvee }+{\xi }_i^{\bigwedge }=|y_i-({\mathbf{w}}^T{\mathbf{x}}_i+b)|-\epsilon$。

因此，所有样本的${\xi }_i^{\bigvee }+{\xi }_i^{\bigwedge }$都可以用$ \varepsilon$不敏感损失表示
$$\begin{array}{rl}{\xi }_i^{\bigvee }+{\xi }_i^{\bigwedge }=& L_{\epsilon }(y_i-({\mathbf{w}}^T{\mathbf{x}}_i+b))\\ =& \{\begin{array}{r}0,|y_i-({\mathbf{w}}^T{\mathbf{x}}_i+b)|\le \epsilon \\ |y_i-({\mathbf{w}}^T{\mathbf{x}}_i+b)|-\epsilon ,|y_i-({\mathbf{w}}^T{\mathbf{x}}_i+b)|>\epsilon \end{array}\end{array}$$

这里$\epsilon$不敏感损失要传达的意思是：如果样本点在$\epsilon$管道内，损失为0；否则损失是样本点在$y$方向上到$\epsilon$管道的距离。

也就是，样本点在$\epsilon$管道内认为无损失，在$\epsilon$管道外才计算损失。

带松弛变量的SVR的目标函数可以写成
$$L(\mathbf{w},b)=C\sum _{i=1}^N{L}_{\epsilon }(y_i-({\mathbf{w}}^T{\mathbf{x}}_i+b))+\frac{1}{2}||\mathbf{w}|{|}_2^2$$
这个数学形式表明带松弛变量的SVR可以解释为$\mathbf{\epsilon }$不敏感损失+L2正则的机器学习模型。

总结

SVM是非常经典的机器学习算法，在集成学习和神经网络的算法流行之前，SVM在分类领域占据着统治地位。在大数据时代，SVM由于在大样本数据集上的计算量太大，所以热度有所下降，但不失为一个常用的机器学习算法。

SVM算法的优点：

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

SVM算法的缺点：

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