支持向量机（Support Vector Machine）基础知识2

前文回顾

四、SVM优化求解：SMO

1、序列最小优化算法 Sequential Minimal Optimization, SMO

  支持向量机（SVM）的原始问题可以通过传统的凸二次规划方法获得全局最优解。然而，这种方法在训练数据集很大时，算法会变得很慢。

  SMO算法由John Platt在1998年提出，是一种高效求解SVM对偶问题的方法。

  对偶问题可以表示为：
$$\begin{array}{r}\max \left(\sum _{i=1}^N{\alpha }_i-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j\right)\\ \text{s.t. }\sum _{i=1}^N{\alpha }_i{y}_i=0\\ 0\le {\alpha }_i\le C,i=1,2,\dots ,N\end{array}$$

2、SMO 动机：坐标上升

  无约束最优化问题可以表示为：
$$W({\alpha }_1,{\alpha }_2,\dots ,{\alpha }_N)=\sum _{i=1}^N{\alpha }_i-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$$

  坐标上升优化算法（Coordinate Ascent Optimization Algorithm）：
$$\begin{array}{r}\text{Loop until convergence}\\ \text{for }i=1,2,\dots ,N\\ {\alpha }_i=\arg \underset{{\tilde{\alpha }}_i}{\max }W({\alpha }_1,{\alpha }_2,{\alpha }_3,\dots ,{\alpha }_{i-1},{\tilde{\alpha }}_i,{\alpha }_{i+1},\dots ,{\alpha }_N)\end{array}$$

  每次只关于一个参数 ${\alpha }_i$ 优化目标函数。坐标梯度上升法：每一步沿着坐标轴方向移动。

3、SVM 坐标上升求解

  对偶问题：
$$\begin{array}{r}\max \left(\sum _{i=1}^N{\alpha }_i-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j\right)\\ \text{s.t. }\sum _{i=1}^N{\alpha }_i{y}_i=0\\ 0\le {\alpha }_i\le C,i=1,2,\dots ,N\end{array}$$

  每次固定 $N-1$ 个变量 ${\alpha }_2,\dots ,{\alpha }_N$，关于变量 ${\alpha }_1$ 优化目标函数。

  每次更新两个变量：
$$\sum _{i=1}^N{\alpha }_i{y}_i=0$$

4、SMO：更新一对变量

  为了保证满足约束条件，每次更新两个变量。这就是SMO算法的核心思想。

  重复直到收敛：
$$\begin{array}{r}\text{Repeat until convergence :}\\ (1)\text{选择要更新的一对变量 }{\alpha }_i\text{ 和 }{\alpha }_j\\ (\text{启发式选择：选择使目标函数值改变最大的变量})\\ (2)\text{关于变量 }{\alpha }_i\text{ 和 }{\alpha }_j\text{ 优化目标函数 }W(\alpha )\end{array}$$

5、SMO: 关于两个变量的优化方法

  假设 ${\alpha }_1$ 和 ${\alpha }_2$ 满足约束条件，固定 ${\alpha }_3,\dots ,{\alpha }_N$，关于变量 ${\alpha }_1$ 和 ${\alpha }_2$ 优化目标函数 $W({\alpha }_1,{\alpha }_2)$。

  目标函数 $W({\alpha }_1,{\alpha }_2)$ 可以表示为：
$$W({\alpha }_1,{\alpha }_2)=\frac{1}{2}{\alpha }_1^2{y}_1^2{x}_1^T{x}_1+\frac{1}{2}{\alpha }_2^2{y}_2^2{x}_2^T{x}_2+{\alpha }_1{\alpha }_2{y}_1{y}_2{x}_1^T{x}_2+{\alpha }_1{y}_1\sum _{i=3}^N{\alpha }_i{y}_i{x}_1^T{x}_i+{\alpha }_2{y}_2\sum _{i=3}^N{\alpha }_i{y}_i{x}_2^T{x}_i$$

  令 $K_{ij}=K(x_i,x_j)=x_i^T{x}_j$，则有：
$$W({\alpha }_1^{\prime },{\alpha }_2)=\frac{1}{2}{\alpha }_1^2{y}_1^2{K}_{11}+\frac{1}{2}{\alpha }_2^2{y}_2^2{K}_{22}+{\alpha }_1{\alpha }_2{y}_1{y}_2{K}_{12}+{\alpha }_1{y}_1{v}_1+{\alpha }_2{y}_2{v}_2-{\alpha }_1-{\alpha }_2$$

  假设 ${\alpha }_1$ 和 ${\alpha }_2$ 满足约束条件，固定 ${\alpha }_3,\dots ,{\alpha }_N$，关于变量 ${\alpha }_1$ 和 ${\alpha }_2$ 优化目标函数 $W({\alpha }_1,{\alpha }_2)$。

  根据约束条件：
$$\sum _{i=1}^N{\alpha }_i{y}_i=0$$

  可以得到：
$${\alpha }_1{y}_1+{\alpha }_2{y}_2=-\sum _{i=3}^N{\alpha }_i{y}_i=\zeta \text{(常数)}$$

  因此：
$${\alpha }_1=\zeta y_1-{\alpha }_2{y}_1{y}_2\text{(两边同乘以 }{y}_1\text{，且 }{y}_1^2=1\text{)}$$

  有界条件：
$$L\le {\alpha }_2\le H$$

6、SMO: 关于一个变量优化

  将 ${\alpha }_1$ 写成关于 ${\alpha }_2$ 的等式：
$${\alpha }_1=\zeta y_1-{\alpha }_2{y}_1{y}_2$$

  目标函数 $W(\alpha )$：
$$W({\alpha }_1,{\alpha }_2,\dots ,{\alpha }_N)=W(\zeta y_1-{\alpha }_2{y}_1{y}_2,{\alpha }_2)$$

  关于变量 ${\alpha }_2$ 的二次函数：
$$W({\alpha }_2)=\frac{1}{2}(\zeta -{\alpha }_2{y}_2{)}^2{K}_{11}+\frac{1}{2}{\alpha }_2^2{K}_{22}+y_2(\zeta -{\alpha }_2{y}_2){\alpha }_2{K}_{12}+(\zeta -{\alpha }_2{y}_2)v_1+{\alpha }_2{y}_2{v}_2-\zeta y_1+{\alpha }_2{y}_1{y}_2-{\alpha }_2$$

  不考虑 ${\alpha }_2$ 的取值范围，可求全局最优解：
$${\alpha }_2^{\text{new}}={\alpha }_2^{\text{old}}+\frac{y_2(E_1-E_2)}{K_{11}+K_{22}-2K_{12}}$$

7、求解 ${\alpha }_2$

  目标函数 $W({\alpha }_1,{\alpha }_2)$：
$$W({\alpha }_1,{\alpha }_2)=\frac{1}{2}{K}_{11}{\alpha }_1^2+\frac{1}{2}{K}_{22}{\alpha }_2^2+{\alpha }_1{\alpha }_2{y}_1{y}_2{K}_{12}+{\alpha }_1{y}_1{v}_1+{\alpha }_2{y}_2{v}_2-{\alpha }_1-{\alpha }_2+\text{常数}$$

  约束条件：
$${\alpha }_1{y}_1+{\alpha }_2{y}_2=-\sum _{i=3}^N{\alpha }_i{y}_i=\zeta ,0\le {\alpha }_i\le C,i=1,2$$

  其中：
$$v_1=\sum _{i=3}^N{\alpha }_i{y}_i{K}_{1i},v_2=\sum _{i=3}^N{\alpha }_i{y}_i{K}_{2i},K_{ij}=K(x_i,x_j)$$

  由 ${\alpha }_1{y}_1+{\alpha }_2{y}_2=-{\sum }_{i=3}^N{\alpha }_i{y}_i=\zeta$ 得，${\alpha }_1=\zeta y_1-{\alpha }_2{y}_1{y}_2$

  目标函数 $W({\alpha }_2)$：
$$W({\alpha }_2)=\frac{1}{2}(\zeta -{\alpha }_2{y}_2{)}^2{K}_{11}+\frac{1}{2}{\alpha }_2^2{K}_{22}+y_2(\zeta -{\alpha }_2{y}_2){\alpha }_2{K}_{12}+(\zeta -{\alpha }_2{y}_2)v_1+{\alpha }_2{y}_2{v}_2-\zeta y_1+{\alpha }_2{y}_1{y}_2-{\alpha }_2+\text{常数}$$

  对 ${\alpha }_2$ 求导：
$$\frac{\partial W({\alpha }_2)}{\partial {\alpha }_2}=(K_{11}+K_{22}-2K_{12}){\alpha }_2-y_2(\zeta (K_{11}-K_{12})+v_1-v_2-y_1+y_2)=0$$

  求解 ${\alpha }_2$：
$${\alpha }_2^{\text{new}}={\alpha }_2^{\text{old}}+\frac{y_2(E_1-E_2)}{K_{11}+K_{22}-2K_{12}}$$
  SMO高效：更新 ${\alpha }_i$ 和 ${\alpha }_j$ 的方法计算高效！

8、SMO: 关于一个变量优化

  考虑约束条件：

$${\alpha }_2^{\text{new}}=\{\begin{array}{ll}H& {\alpha }_2^{\text{new, unclipped}}>H\\ {\alpha }_2^{\text{new, unclipped}}& L\le {\alpha }_2^{\text{new, unclipped}}\le H\\ L& {\alpha }_2^{\text{new, unclipped}}<L\end{array}$$

$$L=\max (0,{\alpha }_2^{\text{old}}-{\alpha }_1^{\text{old}})$$

$$H=\min (C,C+{\alpha }_2^{\text{old}}-{\alpha }_1^{\text{old}})$$

  图中展示了不同的${\alpha }_1$和${\alpha }_2$的取值范围，以及对应的约束条件。${\alpha }_1$和${\alpha }_2$的取值受到$C$（惩罚参数）和$\zeta$（阈值）的限制。

9、SMO: 两个变量的最优解

  得到${\alpha }_2^{\text{new}}$后，根据${\alpha }_1=\zeta y_1-{\alpha }_2{y}_1{y}_2$可得：

$${\alpha }_1^{\text{old}}{y}_1+{\alpha }_2^{\text{old}}{y}_2={\alpha }_1^{\text{new}}{y}_1+{\alpha }_2^{\text{new}}{y}_2$$

$${\alpha }_1^{\text{new}}={\alpha }_1^{\text{old}}+y_1{y}_2({\alpha }_2^{\text{old}}-{\alpha }_2^{\text{new}})$$

  这里展示了如何通过已知的${\alpha }_2^{\text{new}}$来计算${\alpha }_1^{\text{new}}$。

10、SMO: 第一个变量的选择

  主要思想：从训练样本中选择违背KKT条件的样本，进而确定${\alpha }_i$。

  KKT条件：

$$\{\begin{array}{ll}{\alpha }_i=0& \Rightarrow y_i(w^T{x}_i+b)\ge 1\\ 0<{\alpha }_i<C& \Rightarrow y_i(w^T{x}_i+b)=1\\ {\alpha }_i=C& \Rightarrow y_i(w^T{x}_i+b)\le 1\end{array}$$

  首先选择违反$0<{\alpha }_i<C\Rightarrow y_i(w^T{x}_i+b)=1$的点（决策边界上的支持向量）。

  如果上述支持向量都满足KKT条件，检查其他所有训练样本。

11、SMO: 第二个变量的选择

  选${\alpha }_2$的标准？

$${\alpha }_2^{\text{new, unclipped}}={\alpha }_2^{\text{old}}+\frac{y_2(E_1-E_2)}{\eta }$$

  其中$\eta =K_{11}+K_{22}-2K_{12}$。

  选择使$|E_1-E_2|$最大的${\alpha }_2$。

  ${\alpha }_1$固定，$E_1$固定。

• $E_1>0\Rightarrow$ 选最小的$E_i$作为$E_2$
• $E_1<0\Rightarrow$ 选最大的$E_i$作为$E_2$

  $E_i$很关键，怎么样使得算法高效？保存所有的$E_i$。

12、SMO: $b$及对偶值 $E_i$

  更新完变量后，更新$b$：

• 如果 ${\alpha }_1^{\text{new}}>0$，根据KKT条件：$y_{1}f(x_1)=y_1\left({\sum }_{i=1}^N{\alpha }_i{y}_{i}K(x_i,x_1)+b\right)=1$

$$b_1^{\text{new}}=y_1-\sum _{i=3}^N{\alpha }_i{y}_i{K}_{i1}-{\alpha }_1^{\text{new}}{y}_1{K}_{11}-{\alpha }_2^{\text{new}}{y}_2{K}_{21}$$

  引入：$E_1=f(x_1)-y_1={\sum }_{i=3}^N{\alpha }_i{y}_i{K}_{i1}+{\alpha }_1^{\text{old}}{y}_1{K}_{11}+{\alpha }_2^{\text{old}}{y}_2{K}_{21}+b^{\text{old}}$

  得到：

$$\{\begin{array}{l}{b}_1^{\text{new}}=-E_1-y_1{K}_{11}({\alpha }_1^{\text{new}}-{\alpha }_1^{\text{old}})-y_2{K}_{21}({\alpha }_2^{\text{new}}-{\alpha }_2^{\text{old}})+b^{\text{old}}\\ b_2^{\text{new}}=-E_2-y_1{K}_{12}({\alpha }_1^{\text{new}}-{\alpha }_1^{\text{old}})-y_2{K}_{22}({\alpha }_2^{\text{new}}-{\alpha }_2^{\text{old}})+b^{\text{old}}\end{array}$$

  如果$0<{\alpha }_1^{\text{new}}<C$，$0<{\alpha }_2^{\text{new}}<C$，则$b^{\text{new}}=b_1^{\text{new}}=b_2^{\text{new}}$

  如果${\alpha }_1^{\text{new}}$、${\alpha }_2^{\text{new}}$同时是0或$C$， ∀ b ∈ [ min ⁡ { b 1 new , b 2 new } , max ⁡ { b 1 new , b 2 new } ] \forall b \in [\min\{b_1^{\text{new}}, b_2^{\text{new}}\}, \max\{b_1^{\text{new}}, b_2^{\text{new}}\}] ∀b∈[min{b1new​,b2new​},max{b1new​,b2new​}]都满足KKT条件，取

$$b^{\text{new}}=\frac{b_1^{\text{new}}+b_2^{\text{new}}}{2}$$

  更新 $E_i={\sum }_j{y}_j{\alpha }_{j}K(x_i,x_j)+b^{\text{new}}-y_i$

13、SMO 算法

  1. 初始化：${\alpha }^{(0)}=0$，并计算偏移量$b^{(0)}$

  2. 初始化误差项$E_i$

  3. 选择待优化的变量：${\alpha }_1$和${\alpha }_2$求解优化问题的解

$${\alpha }_2^{\text{new, unclipped}}={\alpha }_2^{\text{old}}+\frac{y_2(E_1-E_2)}{\eta }$$

$${\alpha }_2^{\text{new}}=\{\begin{array}{ll}H& {\alpha }_2^{\text{new, unclipped}}>H\\ {\alpha }_2^{\text{new, unclipped}}& L\le {\alpha }_2^{\text{new, unclipped}}\le H\\ L& {\alpha }_2^{\text{new, unclipped}}<L\end{array}$$

$$\eta =K_{11}+K_{22}-2K_{12}$$

$${\alpha }_1^{(t+1)}={\alpha }_1^{(t)}+y_1{y}_2({\alpha }_2^{(t)}-{\alpha }_2^{(t+1)})$$

  4. 更新$\alpha$为${\alpha }^{(t+1)}$，更新$E_i$，计算$b^{(t+1)}$

  5. 如果达到终止条件，则停止算法；否则$t=t+1$, 转到第 ③ 步

  终止条件：满足KKT条件或误差项均小于$\epsilon$

14、SMO 小结

  - 启发式、迭代式算法。
  - 解满足KKT条件时，得到最优解；否则选择两个变量来优化。
  - 最优化问题转换为关于两个选定变量的QP问题，该问题通常有闭式解，计算高效，收敛快。
  - 变量的选择方法：

• 第一个变量：违背KKT条件程度最大的变量
• 第二个变量：使目标函数值减小最快的变量
    - 把一个最优化问题不换转化为若干个子问题，通过对子问题的求解得到原问题的解。

五、SVM回归（SVR）

1、ε不敏感损失函数

  在之前的线性回归模型中，只有当真实值$y$与预测值$\hat{y}$完全相等时，我们才认为损失为0（L2损失、L1损失、Huber损失）。

  在支持向量回归中，我们能容忍当真实值$y$与预测值$\hat{y}$有$ϵ$的偏差，即当$y$与$\hat{y}$之间的差异大于$ϵ$时才计算损失，称为$ϵ$不敏感损失（$ϵ$ insensitive loss）。

$$L_{ϵ}(y,\hat{y})=\{\begin{array}{ll}0& \text{if }|y-\hat{y}|\le ϵ\\ |y-\hat{y}|-ϵ& \text{otherwise}\end{array}$$

• 不惩罚小的损失
• 误差大于$ϵ$时，对损失的影响是线性的，对噪声鲁棒
  

2、支持向量回归（Support Vector Regression，SVR）

  假设回归函数为线性模型：$f(x)=w^{T}x+b$

  同SVM分类类似，SVR的目标函数为

$$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }_2^2$$

$$\text{s.t. }|y_i-(w^T{x}_i+b)|\le ϵ,i=1,2,...,N$$

3、松弛变量

  类似SVM分类模型，加入松弛变量${\xi }_i\ge 0$，用于表示每个点在$ϵ$管道外的程度。

  由于用的是绝对值，实际上是两个不等式，也就是说两边都需要松弛变量：${\xi }_i^{+},{\xi }_i^{-}$。

  则SVR模型的目标函数变为

$$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }_2^2$$

$$\text{s.t. }-ϵ-{\xi }_i^{-}\le y_i-(w^T{x}_i+b)\le ϵ+{\xi }_i^{+},i=1,2,...,N$$

$${\xi }_i^{+}\ge 0,{\xi }_i^{-}\ge 0,i=1,2,...,N$$

4、拉格朗日函数

与支持向量机（SVM）类似，支持向量回归（SVR）的拉格朗日函数定义如下：

  $$L(w,b,{\alpha }^v,{\alpha }^c,{\xi }^v,{\xi }^c,{\mu }^v,{\mu }^c)=\frac{1}{2}\Vert w{\Vert }_2^2+C\sum _{i=1}^N({\xi }_i^v+{\xi }_i^c)$$

  目标是最小化以下表达式：
$$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }_2^2$$

  同时满足以下约束条件：
$$\begin{array}{rl}s.t.-ϵ-{\xi }_i^v& \le y_i-(w^T{x}_i+b)\le ϵ+{\xi }_i^c\\ {\xi }_i^c& \ge 0,{\xi }_i^v\ge 0\end{array}$$

  拉格朗日乘子${\alpha }_i^v$和${\alpha }_i^c$以及${\mu }_i^v$和${\mu }_i^c$的引入，使得问题可以转化为对偶问题求解。对偶问题的目标函数为：
$$\begin{array}{rl}& +\sum _{i=1}^N{\alpha }_i^v\left(-ϵ-{\xi }_i^v-y_i+{\mathbf{w}}^{\top }{\mathbf{x}}_i+b\right)\\ & +\sum _{i=1}^N{\alpha }_i^c\left(y_i-{\mathbf{w}}^{\top }{\mathbf{x}}_i-b-ϵ-{\xi }_i^c\right)\\ & -\sum _{i=1}^N{\mu }_i^v{\xi }_i^v-\sum _{i=1}^m{\mu }_i^c{\xi }_i^c\end{array}$$

5、SVR的对偶问题

  拉格朗日函数$L(w,b,{\alpha }^v,{\alpha }^c,{\xi }^v,{\xi }^c,{\mu }^v,{\mu }^c)$对$w,b,{\xi }_i^{\wedge },{\xi }_i^{\vee }$的一阶导数如下：

  $$\frac{\partial L(w,b,{\alpha }^v,{\alpha }^c,{\xi }^v,{\xi }^c,{\mu }^v,{\mu }^c)}{\partial \mathbf{w}}=0\Rightarrow \mathbf{w}=\sum _{i=1}^N({\alpha }_i^{\wedge }-{\alpha }_i^{\vee }){\mathbf{x}}_i$$

  $$\frac{\partial L(w,b,{\alpha }^v,{\alpha }^c,{\xi }^v,{\xi }^c,{\mu }^v,{\mu }^c)}{\partial b}=0\Rightarrow \sum _{i=1}^N({\alpha }_i^{\wedge }-{\alpha }_i^{\vee })=0$$

  $$\frac{\partial L(w,b,{\alpha }^v,{\alpha }^c,{\xi }^v,{\xi }^c,{\mu }^v,{\mu }^c)}{\partial {\xi }_i^{\wedge }}=0\Rightarrow C-{\alpha }_i^{\wedge }+{\mu }_i^{\wedge }$$

  $$\frac{\partial L(w,b,{\alpha }^v,{\alpha }^c,{\xi }^v,{\xi }^c,{\mu }^v,{\mu }^c)}{\partial {\xi }_i^{\vee }}=0\Rightarrow C-{\alpha }_i^{\vee }+{\mu }_i^{\vee }$$

6、对偶问题的构建

  将上述结论代入拉格朗日函数$L(w,b,{\alpha }^v,{\alpha }^c,{\xi }^v,{\xi }^c,{\mu }^v,{\mu }^c)$，得到对偶问题：

  $$\underset{{\alpha }^v,{\alpha }^c}{\max }\left(-\sum _{i=1}^N((ϵ-y_i){\alpha }_i^{\wedge }+(ϵ+y_i){\alpha }_i^{\vee })-\sum _{i=1}^N\frac{1}{2}({\alpha }_i^{\wedge }-{\alpha }_i^{\vee })({\alpha }_j^{\wedge }-{\alpha }_j^{\vee }){\mathbf{x}}_i^{\top }{\mathbf{x}}_j\right)$$

  约束条件为：
$$\begin{array}{rl}\sum _{i=1}^N({\alpha }_i^{\wedge }-{\alpha }_i^{\vee })& =0\\ 0\le {\alpha }_i^{\wedge }& \le C,i=1,2,...,N\\ 0\le {\alpha }_i^{\vee }& \le C,i=1,2,...,N\end{array}$$

  去掉负号，将上述目标函数中的$\max$换成$\min$，得到等价问题：

  $$\underset{{\alpha }^v,{\alpha }^c}{\min }\left(\sum _{i=1}^N((ϵ-y_i){\alpha }_i^{\wedge }+(ϵ+y_i){\alpha }_i^{\vee })+\sum _{i=1}^N\frac{1}{2}({\alpha }_i^{\wedge }-{\alpha }_i^{\vee })({\alpha }_j^{\wedge }-{\alpha }_j^{\vee }){\mathbf{x}}_i^{\top }{\mathbf{x}}_j\right)$$

7、SVR模型

  求得$\alpha$的最优值后，可计算$\mathbf{w},b$，从而得到SVR模型：

  $$f(\mathbf{x})={\mathbf{w}}^{\top }\mathbf{x}+b=\sum _{i=1}^N({\alpha }_i^{\wedge }-{\alpha }_i^{\vee }){\mathbf{x}}_i^{\top }\mathbf{x}+b$$

  $$=\sum _{i=1}^N({\alpha }_i^{\wedge }-{\alpha }_i^{\vee })⟨{\mathbf{x}}_i,\mathbf{x}⟩+b$$

  $\mathbf{x}$与训练数据的点积$⟨{\mathbf{x}}_i,\mathbf{x}⟩$换成核函数$k({\mathbf{x}}_i,\mathbf{x})$，得到核化SVR模型：

  $$f(\mathbf{x})=\sum _{i=1}^N({\alpha }_i^{\wedge }-{\alpha }_i^{\vee })k({\mathbf{x}}_i,\mathbf{x})+b$$

8、SVR的支持向量

  KKT条件之二为：

  $${\alpha }_i^{\vee }\left(ϵ+{\xi }_i^{\vee }+y_i-({\mathbf{w}}^{\top }{\mathbf{x}}_i+b)\right)=0$$

  $${\alpha }_i^{\wedge }\left(ϵ+{\xi }_i^{\wedge }-y_i+({\mathbf{w}}^{\top }{\mathbf{x}}_i+b)\right)=0$$

  支持向量：仅当样本$({\mathbf{x}}_i,y_i)$落在$ϵ$间隔中，${\alpha }_i^{\vee }$、${\alpha }_i^{\wedge }$才取非0值。

六、Sklearn中的SVM的API

1、Scikit-Learn中的SVM实现

  sklearn.svm模块提供支持向量机算法，可用于分类、回归和异常值检测。

  分类实现有三种方式：

• LinearSVC：基于liblinear实现线性SVM，比基于libsvm实现的线性SVC / NuSVC更快，同时可采用更多正则选择（L1/L2）和损失函数选择。
  • L1正则可以得到特征系数稀疏的效果。
  • 适用于样本数更多的情况。
• SVC和NuSVC：类似，都是基于libsvm实现的C-SVM，二者在参数方面有细微不同（NuSVC有参数$\nu$控制训练误差的上限和支持向量的下限）。
• SGDClassifier（不在sklearn.svm模块，在sklearn.linear_model）实现了基于随机梯度下的线性SVM分类。

  回归实现方式同分类类似。

  SVM还支持非监督的异常值检测：OneClassSVM

2、LinearSVC

class sklearn.svm.LinearSVC(penalty='l2', loss='squared_hinge', dual=True, tol=0.0001, C=1.0,
                          multi_class='ovr', fit_intercept=True, intercept_scaling=1, class_weight=None, verbose=0,
                          random_state=None, max_iter=1000)

  支持两种正则：L2正则和L1正则，正则参数为：penalty、C。
  支持两种损失函数：标准的合页损失hinge和合页损失的平方squared_hinge。
  支持不同类别的样本权重设置：class_weight。

3、参数说明

4、LinearSVC的属性

5、LinearSVC的方法

注意：LinearSVC不能像Logistic回归那样得到每个类别的概率。

6、SVC

class sklearn.svm.SVC(C=1.0, kernel='rbf', degree=3, gamma='auto', coef0=0.0,
                     shrinking=True, probability=False, tol=0.001, cache_size=200, 
                     class_weight=None, verbose=False, max_iter=-1, 
                     decision_function_shape='ovr', random_state=None)

• 支持L2正则化。
• 支持多种核函数：‘linear’, ‘poly’, ‘rbf’, ‘sigmoid’, 'precomputed’和自定义核函数。
• 支持多类分类实现：一对一（‘ovo’）。
• 支持不同类别的样本权重设置：class_weight。

7、SVC的属性

注意：LinearSVC没有支持向量等属性。

8、SVC的常用方法

注意：如果参数probability被设为True，则可以得到属于每个类别的概率估计（predict_proba和predict_log_proba方法可用）。

9、核函数参数

  核函数的参数有$degree(M)$、$gamma(\gamma )$、$coef0(\theta )$，核函数可以有以下几种选择：

  - 线性核：$k(x,x^{\prime })=x^T{x}^{\prime }$
  - 多项式核，缺省为3阶多项式：$k(x,x^{\prime })=(\gamma x^T{x}^{\prime }+r{)}^M$
  - 径向基函数（RBF）：$k(x,x^{\prime })=\exp (-\gamma \Vert x-x^{\prime }{\Vert }_2^2)$
  - sigmoid函数：$k(x,x^{\prime })=\tanh (-\gamma x^T{x}^{\prime }+\theta )$

10、多类别分类

  - SVM最初是处理二分类问题的。多类别分类通过一对一（One vs. One，‘ovo’）方案实现（SVC、NuSVC）。
  - 一对一法：假设进行$C$个类别的分类任务，一对一法在任意两类样本之间设计一个SVM，构造$C\times (C-1)/2$个分类器。当对一个未知样本进行分类时，最后得票最多的类别即为该样本的类别。
  - 为了提供一个和其它分类器一致的接口，参数decision_function_shape允许调用者将所有“一对一”分类器的结果聚合进一个$(n\_samples,n\_classes)$的决策函数。
  - LinearSVC实现“一对多”分类法（‘ovr’），训练$C$个模型。

11、得分与概率

  - SVC中的decision_function方法对每个样本都会给出在各个类别上的分数（在两类分类问题中，对每个样本只给出一个分数）。
  - 如果构造函数的参数probability被设为True，则可以得到属于每个类别的概率估计（通过predict_proba和predict_log_proba方法）。概率使用Platt缩放进行调整，通过在训练集上做额外的交叉检验来拟合一个在SVM分数上的Logistic回归。

• Platt缩放中的交叉检验在大数据集上是一个代价很高的操作
• 概率估计与实际得分可能会不一致，即使得分取得了最大值，概率并不一定也能取到最大值
• Platt的方法在理论上也有一些问题
    - 如果需要拿到置信分数，而这些分数又不一定非得是概率，则建议把probability置为False，并且使用decision_function，而不是predict_proba。

12、计算复杂度

  - 支持向量机很强大，一度是处理机器学习任务的首选算法。
  - 但随着训练样本数目的增加，它们对计算和存储资源的需求也快速增长。

• SVM的核心是二次规划问题（QP）。令特征维数为$D$，训练样本数目为$N$，取决于libsvm缓存在实践中使用的效率（依赖于数据集），基于libsvm的实现所用的QP求解器时间复杂度在$D{N}^2$到$D{N}^3$不等。如果数据非常稀疏，$D$为一个样本中的平均非零特征数目。因此通常在$N<100000$时可用。
    - 对线性的情况，基于liblinear实现的LinearSVC的算法比基于libsvm实现的SVC效率要高很多，liblinear在处理以百万计的样本和/或特征时仅以线性增长。