NO.38.tip： 支持向量机

背景

支持向量机（Support Vector Machine，SVM）的基本模型是定义在特征空间上间隔最大的线性分类器。它是一种二类分类模型，当采用了核技巧之后，支持向量机可以用于非线性分类。不同类型的支持向量机解决不同的问题。

• 线性可分支持向量机（也称为硬间隔支持向量机）：当训练数据线性可分时，通过硬间隔最大化，学得一个线性可分支持向量机。
• 线性支持向量机（也称为软间隔支持向量机）：当训练数据近似线性可分时，通过软间隔最大化，学得一个线性支持向量机。
• 非线性支持向量机：当训练数据不可分时，通过使用核技巧以及软间隔最大化，学得一个非线性支持向量机。

在本章中，假设输入空间和特征空间是不同的。通常假设输入空间为欧氏空间，特征空间为希尔伯特空间。此时给定某个输入 $\vec{x}$，通过某种映射（可能为线性映射，也可能为非线性映射）到特征空间的表示为 $\vec{z}$。此时在特征空间中学习线性支持向量机（而不是在输入空间中学习线性支持向量机）。欧氏空间与希尔伯特空间的不同如下：

• 欧氏空间是有限维度的，希尔伯特空间是无穷维度的；
• 欧氏空间 $\subseteq$ 希尔伯特空间 $\subseteq$ 内积空间 $\subseteq$ 赋范空间。

越抽象的空间具有的性质越少，在这样的空间中能得到的结论就越少。不过反过来，如果发现了赋范空间中的某些性质，那么前面那些空间也都具有这个性质。我们生活在三维空间，把它拓展到 $n$ 维空间就是欧氏空间，这是我们比较熟悉的空间，具有一切美好的性质。当我们不局限于有限维度，就来到了希尔伯特空间。从有限到无限是一个质变，很多美好的性质便消失了，一些非常有悖常识的现象会出现。如果再进一步去掉完备性，就来到了内积空间。如果再进一步去掉“角度”的概念，就来到了赋范空间。在这里，起码我们还有“长度”和“距离”的概念。

源与流

线性可分支持向量机

原始问题

给定一个特征空间上的训练数据集 $T=\{({\vec{x}}_1,y_1),({\vec{x}}_2,y_2),\cdots ,({\vec{x}}_N,y_N)\}$，其中 ${\vec{x}}_i=(x_i^{(1)},x_i^{(2)},\cdots ,x_i^{(n)}{)}^T\in \mathcal{X}={\mathbb{R}}^n$，$y_i\in \mathcal{Y}=\{+1,-1\}$，$i=1,2,\cdots ,N$。${\vec{x}}_i$ 为第 $i$ 个实例；$y_i$ 为 ${\vec{x}}_i$ 的类标记：

• 若 $y_i=+1$ 时，则称 ${\vec{x}}_i$ 为正例；
• 若 $y_i=-1$ 时，则称 ${\vec{x}}_i$ 为负例。

假设训练数据集线性可分，希望在特征空间中找到一个分离超平面，它能将所有的正例划分到超平面的一侧、所有的负例划分到超平面的另一侧。由于超平面可以用方程 $\vec{w}\cdot \vec{x}+b=0$ 表示，它由法向量 $\vec{w}$ 和截距 $b$ 决定，可以用 $(\vec{w},b)$ 来表示，于是需要求得分离超平面的参数 $(\vec{w},b)$。

当训练数据集线性可分时，理论上存在无穷多个分离超平面可以将两类数据正确分开。线性可分支持向量机提出了间隔最大化这样的约束，最终求得的分离超平面只有唯一的一个。

给定线性可分训练数据集 $T$，假设通过间隔最大化学习得到的分离超平面为：${\vec{w}}^{\ast }\cdot \vec{x}+b^{\ast }=0$。定义分类决策函数：$f(\vec{x})=\text{sign}({\vec{w}}^{\ast }\cdot \vec{x}+b^{\ast })$。该分类决策函数也称为线性可分支持向量机。

对于线性可分支持向量机，通常可以将一个样本距离分离超平面的远近来表示分类预测的可靠程度：一个样本距离分离超平面越远，则该样本的分类越可靠；一个样本距离分离超平面越近，则该样本的分类就不那么确信。

（给定超平面 $\vec{w}\cdot \vec{x}+b=0$，样本 ${\vec{x}}_i$ 距超平面的距离为：$|\vec{w}\cdot {\vec{x}}_i+b|$。$\vec{w}\cdot {\vec{x}}_i+b$ 的符号与样本标记 $y_i$ 的符号是否一致表示分类是否正确。）

• $\vec{w}\cdot {\vec{x}}_i+b>0$ 时，即 ${\vec{x}}_i$ 位于超平面上方，将 ${\vec{x}}_i$ 划分为正类。若 $y_i=+1$，则分类正确。
• $\vec{w}\cdot {\vec{x}}_i+b<0$ 时，即 ${\vec{x}}_i$ 位于超平面下方，将 ${\vec{x}}_i$ 划分为负类。若 $y_i=-1$，则分类正确。

所以可以用 $y(\vec{w}\cdot \vec{x}+b)$ 来表示分类的正确性以及确信度（符号决定了正确性，范数决定了确信度）。

给定训练数据集 $T$，给定超平面 $(\vec{w},b)$，定义超平面 $(\vec{w},b)$ 关于样本点 $({\vec{x}}_i,y_i)$ 的函数间隔为：${\hat{\gamma }}_i=y_i(\vec{w}\cdot {\vec{x}}_i+b)$。定义超平面 $(\vec{w},b)$ 关于训练集 $T$ 的函数间隔为超平面 $(\vec{w},b)$ 关于 $T$ 中所有样本点 $({\vec{x}}_i,y_i)$ 的函数间隔之最小值：$\hat{\gamma }={\min }_{{\vec{x}}_i\in T}{\hat{\gamma }}_i$。

${\hat{\gamma }}_i$ 是关于某个样本点的间隔，$\hat{\gamma }$ 是关于训练集的间隔。

函数间隔存在一个重要的缺陷：当成比例地改变 $\vec{w}$ 和 $b$（比如将它们改变为 $100\vec{w}$ 和 $100b$，超平面 $100\vec{w}\cdot \vec{x}+100b=0$ 不变，但是函数间隔却变为原来的 100 倍。）因此我们引入几何间隔。

对于给定的训练数据集 $T$ 和超平面 $(\vec{w},b)$，定义超平面 $(\vec{w},b)$ 关于样本点 $({\vec{x}}_i,y_i)$ 的几何间隔为：${\gamma }_i=y_i\left(\frac{\vec{w}}{||\vec{w}||}\cdot {\vec{x}}_i+\frac{b}{||\vec{w}||}\right)$。定义超平面 $(\vec{w},b)$ 关于训练集 $T$ 的几何间隔为超平面 $(\vec{w},b)$ 关于 $T$ 中所有样本点 $({\vec{x}}_i,y_i)$ 的几何间隔之最小值：$\gamma ={\min }_{{\vec{x}}_i\in T}{\gamma }_i$。

${\gamma }_i$ 是关于样本点的间隔，$\gamma$ 是关于训练集的间隔。

支持向量机的目标是：求解能够正确划分训练数据集，且几何间隔最大的分离超平面。这里的几何间隔最大化又称为硬间隔最大化。

这一目标可以用数学语言描述为约束的最优化问题：

$$\begin{array}{rl}& \underset{\vec{w},b}{\max }\gamma \\ & \text{s.t. }{y}_i\left(\frac{\vec{w}}{||\vec{w}||}\cdot {\vec{x}}_i+\frac{b}{||\vec{w}||}\right)\ge \gamma ,i=1,2,\cdots ,N\end{array}$$

根据几何间隔和函数间隔的关系，问题转化为：

$$\begin{array}{rl}& \underset{\vec{w},b}{\max }\frac{\hat{\gamma }}{||\vec{w}||}\\ & \text{s.t. }{y}_i(\vec{w}\cdot {\vec{x}}_i+b)\ge \hat{\gamma },i=1,2,\cdots ,N\end{array}$$

函数间隔 $\hat{\gamma }$ 并不影响最优化问题的解（假设将 $\vec{w},b$ 按比例地改变为 $k\vec{w},kb$，此时函数间隔变成 $k\hat{\gamma }$。这一变化对求解最优化问题的不等式约束和最优化目标函数都没有影响），因此令 $\hat{\gamma }=1$。同时注意到 $\max \frac{1}{||\vec{w}||}$ 等价于 $\min \frac{1}{2}||\vec{w}|{|}_2^2$。于是最优化问题改写为：

$$\begin{array}{rl}& \underset{\vec{w},b}{\min }\frac{1}{2}||\vec{w}|{|}_2^2\\ & \text{s.t. }{y}_i(\vec{w}\cdot {\vec{x}}_i+b)-1\ge 0,i=1,2,\cdots ,N\end{array}$$

这是一个凸二次规划问题。

下面给出线性可分支持向量机学习算法——最大间隔法的算法。

• 输入：线性可分训练数据集 $T=\{({\vec{x}}_1,y_1),({\vec{x}}_2,y_2),\cdots ,({\vec{x}}_N,y_N)\}$。
• 输出：最大几何间隔的分离超平面和分类决策函数。
• 算法步骤如下。
  1. 构造并且求解约束最优化问题： $$\begin{array}{rl}& \underset{\vec{w},b}{\min }\frac{1}{2}||\vec{w}|{|}_2^2\\ & \text{s.t. }{y}_i(\vec{w}\cdot {\vec{x}}_i+b)-1\ge 0,i=1,2,\cdots ,N\end{array}$$ 求得最优解 ${\vec{w}}^{\ast },b^{\ast }$。
  2. 由此得到分离超平面：${\vec{w}}^{\ast }\cdot \vec{x}+b^{\ast }=0$，以及分类决策函数 $f(\vec{x})=\text{sign}({\vec{w}}^{\ast }\cdot \vec{x}+b^{\ast })$。

可以证明若训练数据集 $T$ 线性可分，最大间隔分离超平面存在且唯一。

假设已经求得最大间隔分离超平面为 $S={\vec{w}}^{\ast }\cdot \vec{x}+b^{\ast }$。把训练数据集中与 $S$ 距离最近的样本称为支持向量。支持向量就是那些使得约束条件等号成立的样本：即 $y_i({\vec{w}}^{\ast }\cdot {\vec{x}}_i+b^{\ast })-1=0$。

• 支持向量中的正例位于超平面 $H_1:{\vec{w}}^{\ast }\cdot \vec{x}+b^{\ast }=1$。
• 支持向量中的负例位于超平面 $H_2:{\vec{w}}^{\ast }\cdot \vec{x}+b^{\ast }=-1$。

超平面 $H_1$、$H_2$ 称为间隔边界。$H_1$、$H_2$ 和最大间隔分离超平面 $S$ 平行，且没有任何实例点落在 $H_1$、$H_2$ 之间。在 $H_1$、$H_2$ 之间形成一条隔离带，隔离带的宽度为 $\frac{2}{||{\vec{w}}^{\ast }||}$。

在决定分离超平面时，只有支持向量起作用：

• 如果改变了支持向量，则最大间隔分离超平面也随之改变。
• 如果去掉了间隔边界 $H_1$、$H_2$ 之外的任何数量的样本，则最大间隔分离超平面是不变的。

所以支持向量在确定最大间隔分离超平面中起着决定性作用（如图 7.1 所示）。这也是支持向量机名称的由来。

对偶问题

我们将求解线性可分支持向量机的最优化问题作为原始最优化问题。通过应用拉格朗日对偶性转化为对偶问题，这就是线性可分支持向量机的对偶算法。在这一过程中可以方便地引入核函数，从而将支持向量机算法推广到非线性分类问题。

原始问题：

$$\begin{array}{rl}& \underset{\vec{w},b}{\min }\frac{1}{2}||\vec{w}|{|}_2^2\\ & \text{s.t. }{y}_i(\vec{w}\cdot {\vec{x}}_i+b)-1\ge 0,i=1,2,\cdots ,N\end{array}$$

定义拉格朗日函数：

$$L(\vec{w},b,\vec{\alpha })=\frac{1}{2}||\vec{w}|{|}_2^2-\sum _{i=1}^N{\alpha }_i{y}_i(\vec{w}\cdot {\vec{x}}_i+b)+\sum _{i=1}^N{\alpha }_i$$

其中 $\vec{\alpha }=({\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_N{)}^T$ 为拉格朗日乘子向量。

原始问题的对偶问题是极大极小问题：${\max }_{\vec{\alpha }}{\min }_{\vec{w},b}L(\vec{w},b,\vec{\alpha })$。

先求 ${\min }_{\vec{w},b}L(\vec{w},b,\vec{\alpha })$。通过拉格朗日函数的偏导数为零，则有：

$$\{\begin{array}{l}{\nabla }_{\vec{w}}L(\vec{w},b,\vec{\alpha })=\vec{w}-\sum _{i=1}^N{\alpha }_i{y}_i{\vec{x}}_i=\vec{0}\\ {\nabla }_{b}L(\vec{w},b,\vec{\alpha })=\sum _{i=1}^N{\alpha }_i{y}_i=0\end{array}$$

求得 $\vec{w}={\sum }_{i=1}^N{\alpha }_i{y}_i{\vec{x}}_i$，${\sum }_{i=1}^N{\alpha }_i{y}_i=0$。

再求极大值。将上面得到的 $\vec{w}={\sum }_{i=1}^N{\alpha }_i{y}_i{\vec{x}}_i$，${\sum }_{i=1}^N{\alpha }_i{y}_i=0$ 代入拉格朗日函数：

$$\begin{array}{rl}L(\vec{w},b,\vec{\alpha })& =\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\vec{x}}_i\cdot {\vec{x}}_j)-\sum _{i=1}^N{\alpha }_i{y}_i\left[\left(\sum _{j=1}^N{\alpha }_j{y}_j{\vec{x}}_j\right)\cdot {\vec{x}}_i+b\right]+\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({\vec{x}}_i\cdot {\vec{x}}_j)+\sum _{i=1}^N{\alpha }_i\end{array}$$

于是待求的问题为：

$$\begin{array}{rl}& \underset{\vec{\alpha }}{\max }-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\vec{x}}_i\cdot {\vec{x}}_j)+\sum _{i=1}^N{\alpha }_i\\ & \text{s.t. }\sum _{i=1}^N{\alpha }_i{y}_i=0\\ & {\alpha }_i\ge 0,i=1,2,\cdots ,N\end{array}$$

假定已经求得对偶最优化问题的 $\vec{\alpha }$ 的解为 ${\vec{\alpha }}^{\ast }=({\alpha }_1^{\ast },{\alpha }_2^{\ast },\cdots ,{\alpha }_N^{\ast }{)}^T$，则

$${\vec{w}}^{\ast }=\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i{\vec{x}}_i$$

由于 ${\vec{\alpha }}^{\ast }$ 不是零向量（若它为零向量，则 ${\vec{w}}^{\ast }$ 也为零向量，没有实际应用价值）。则存在某个 $j$ 使得 ${\alpha }_j^{\ast }>0$。根据 ${\alpha }_j^{\ast }(y_j({\vec{w}}^{\ast }\cdot {\vec{x}}_j+b^{\ast })-1)=0$（拉格朗日函数极小值条件），此时必有 $y_j({\vec{w}}^{\ast }\cdot {\vec{x}}_j+b^{\ast })-1=0$。同时考虑 $y_j^2=1$，得到：

$$b^{\ast }=y_j-\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i({\vec{x}}_i\cdot {\vec{x}}_j)$$

于是最大间隔分离超平面为：

$$\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(\vec{x}\cdot {\vec{x}}_i)+b^{\ast }=0$$

分类决策函数为：

$$f(\vec{x})=\text{sign}\left(\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(\vec{x}\cdot {\vec{x}}_i)+b^{\ast }\right)$$

上式称为线性可分支持向量机的对偶形式。可以看到 ${\vec{w}}^{\ast },b^{\ast }$ 只依赖于 ${\alpha }_i^{\ast }>0$ 对应的样本点 ${\vec{x}}_i,y_i$，因此我们将训练数据集里面对应于 ${\alpha }_i^{\ast }>0$ 的样本点对应的实例 ${\vec{x}}_i$ 称为支持向量。

对于 ${\alpha }_i^{\ast }>0$ 的样本点，根据 ${\alpha }_i^{\ast }(y_i({\vec{w}}^{\ast }\cdot {\vec{x}}_i+b^{\ast })-1)=0$（拉格朗日函数极小值条件），有：${\vec{w}}^{\ast }\cdot {\vec{x}}_i+b^{\ast }=\pm 1$，即 ${\vec{x}}_i$ 一定在间隔边界上。这与原始问题给出的支持向量的定义是一致的。

下面给出线性可分支持向量机学习算法的对偶算法。

• 输入：线性可分训练数据集 $T=\{({\vec{x}}_1,y_1),({\vec{x}}_2,y_2),\cdots ,({\vec{x}}_N,y_N)\}$。
• 输出：最大几何间隔的分离超平面和分类决策函数。
• 算法步骤如下。
  1. 构造并且求解约束最优化问题： $$\begin{array}{rl}& \underset{\vec{\alpha }}{\min }\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\vec{x}}_i\cdot {\vec{x}}_j)-\sum _{i=1}^N{\alpha }_i\\ & \text{s.t. }\sum _{i=1}^N{\alpha }_i{y}_i=0\\ & {\alpha }_i\ge 0,i=1,2,\cdots ,N\end{array}$$ 求得最优解 ${\vec{\alpha }}^{\ast }=({\alpha }_1^{\ast },{\alpha }_2^{\ast },\cdots ,{\alpha }_N^{\ast }{)}^T$。
  2. 计算 $${\vec{w}}^{\ast }=\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i{\vec{x}}_i$$
  3. 同时选择 ${\vec{\alpha }}^{\ast }$ 的一个正的分量 ${\alpha }_j^{\ast }>0$，计算 $$b^{\ast }=y_j-\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i({\vec{x}}_i\cdot {\vec{x}}_j)$$
  4. 由此得到最大几何间隔分离超平面：${\vec{w}}^{\ast }\cdot \vec{x}+b^{\ast }=0$，以及分类决策函数 $f(\vec{x})=\text{sign}({\vec{w}}^{\ast }\cdot \vec{x}+b^{\ast })$。

线性支持向量机

对于线性不可分训练数据，线性支持向量机不再适用。但是可以想办法将它扩展到线性不可分问题。

设训练集为 $T=\{({\vec{x}}_1,y_1),({\vec{x}}_2,y_2),\cdots ,({\vec{x}}_N,y_N)\}$，其中 ${\vec{x}}_i=(x_i^{(1)},x_i^{(2)},\cdots ,x_i^{(n)}{)}^T\in \mathcal{X}={\mathbb{R}}^n$，$y_i\in \mathcal{Y}=\{+1,-1\}$，$i=1,2,\cdots ,N$。假设训练数据集不是线性可分的。这意味着某些样本点 $({\vec{x}}_i,y_i)$ 不满足函数间隔大于等于 1 的约束条件。对每个样本点 $({\vec{x}}_i,y_i)$ 引进一个松弛变量 ${\xi }_i\ge 0$，修改最优化目标和约束如下。

• 约束条件修改为：$y_i(\vec{w}\cdot {\vec{x}}_i+b)\ge 1-{\xi }_i$。表示函数间隔加上松弛变量大于等于 1。
• 优化目标修改为：${\min }_{\vec{w},b,\xi }\frac{1}{2}||\vec{w}|{|}_2^2+C{\sum }_{i=1}^N{\xi }_i$。表示对每个松弛变量 ${\xi }_i$，支付一个代价 $C{\xi }_i$，这里 $C>0$ 称为惩罚参数。
  • $C$ 值大时，对误分类的惩罚增大，此时误分类点显得更重要。
  • $C$ 值小时，对误分类的惩罚减小，此时误分类点显得不那么重要。

对应于硬间隔最大化，这里称为软间隔最大化。于是线性不可分的线性支持向量机的学习问题就是求解凸二次规划问题：

$$\begin{array}{rl}& \underset{\vec{w},b,\xi }{\min }\left(\frac{1}{2}||\vec{w}|{|}_2^2+C\sum _{i=1}^N{\xi }_i\right)\\ & \text{s.t. }{y}_i(\vec{w}\cdot {\vec{x}}_i+b)\ge 1-{\xi }_i,i=1,2,\cdots ,N\\ & {\xi }_i\ge 0,i=1,2,\cdots ,N\end{array}$$

这称为线性支持向量机的原始问题。可以证明 $\vec{w}$ 的解是唯一的，$b$ 的解不是唯一的，$b$ 的解存在于一个区间内。

假设求解软间隔最大化问题得到的分离超平面为：${\vec{w}}^{\ast }\cdot \vec{x}+b^{\ast }=0$，相应的分类决策函数为 $f(\vec{x})=\text{sign}({\vec{w}}^{\ast }\cdot \vec{x}+b^{\ast })$。$f(\vec{x})$ 称为线性支持向量机。

对于线性支持向量机的对偶问题，定义拉格朗日函数为：

$$L(\vec{w},b,\vec{\xi },\vec{\alpha },\vec{\mu })=\frac{1}{2}||\vec{w}|{|}_2^2+C\sum _{i=1}^N{\xi }_i-\sum _{i=1}^N{\alpha }_i[y_i(\vec{w}\cdot {\vec{x}}_i+b)-1+{\xi }_i]-\sum _{i=1}^N{\mu }_i{\xi }_i$$

$${\alpha }_i\ge 0,{\mu }_i\ge 0$$

原始问题是拉格朗日函数的极小极大问题；对偶问题是拉格朗日函数的极大极小问题。

先求 $L(\vec{w},b,\vec{\xi },\vec{\alpha },\vec{\mu })$ 对 $\vec{w},b,\vec{\xi }$ 的极小。根据偏导数为 0：

$$\{\begin{array}{l}{\nabla }_{\vec{w}}L(\vec{w},b,\vec{\xi },\vec{\alpha },\vec{\mu })=\vec{w}-\sum _{i=1}^N{\alpha }_i{y}_i{\vec{x}}_i=\vec{0}\\ {\nabla }_{b}L(\vec{w},b,\vec{\xi },\vec{\alpha },\vec{\mu })=-\sum _{i=1}^N{\alpha }_i{y}_i=0\\ {\nabla }_{{\xi }_i}L(\vec{w},b,\vec{\xi },\vec{\alpha },\vec{\mu })=C-{\alpha }_i-{\mu }_i=0\end{array}$$

得到：

$$\{\begin{array}{l}\vec{w}=\sum _{i=1}^N{\alpha }_i{y}_i{\vec{x}}_i\\ \sum _{i=1}^N{\alpha }_i{y}_i=0\\ C-{\alpha }_i-{\mu }_i=0\end{array}$$

再求极大问题。将上面三个等式代入拉格朗日函数：

$$\underset{\vec{\alpha },\vec{\mu }}{\max }\underset{\vec{w},b,\vec{\xi }}{\min }L(\vec{w},b,\vec{\xi },\vec{\alpha },\vec{\mu })=\underset{\vec{\alpha },\vec{\mu }}{\max }\left[-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\vec{x}}_i\cdot {\vec{x}}_j)+\sum _{i=1}^N{\alpha }_i\right]$$

于是得到对偶问题：

$$\begin{array}{rl}& \underset{\vec{\alpha }}{\min }\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\vec{x}}_i\cdot {\vec{x}}_j)-\sum _{i=1}^N{\alpha }_i\\ & \text{s.t. }\sum _{i=1}^N{\alpha }_i{y}_i=0\\ & 0\le {\alpha }_i\le C,i=1,2,\cdots ,N\end{array}$$

设 ${\vec{\alpha }}^{\ast }=({\alpha }_1^{\ast },{\alpha }_2^{\ast },\cdots ,{\alpha }_N^{\ast }{)}^T$ 是对偶问题的一个解。若存在 ${\vec{\alpha }}^{\ast }$ 的某个分量 ${\alpha }_j^{\ast }$，$0<{\alpha }_j^{\ast }<C$，则线性支持向量机的原始问题的解可以按照下式得到：

$$\{\begin{array}{l}{\vec{w}}^{\ast }=\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i{\vec{x}}_i\\ b^{\ast }=y_j-\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i({\vec{x}}_i\cdot {\vec{x}}_j)\end{array}$$

于是分离超平面为：${\sum }_{i=1}^N{\alpha }_i^{\ast }{y}_i({\vec{x}}_i\cdot \vec{x})+b^{\ast }=0$。分类决策函数为：$f(\vec{x})=\text{sign}\left[{\sum }_{i=1}^N{\alpha }_i^{\ast }{y}_i({\vec{x}}_i\cdot \vec{x})+b^{\ast }\right]$。

下面给出线性支持向量机学习算法的对偶算法。

• 输入
  • 训练数据集 $T=\{({\vec{x}}_1,y_1),({\vec{x}}_2,y_2),\cdots ,({\vec{x}}_N,y_N)\}$。
  • 惩罚参数 $C>0$。
• 输出：软间隔最大化分离超平面和分类决策函数。
• 算法步骤如下。

  1. 求解约束最优化问题： $$\begin{array}{rl}& \underset{\vec{\alpha }}{\min }\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\vec{x}}_i\cdot {\vec{x}}_j)-\sum _{i=1}^N{\alpha }_i\\ & \text{s.t. }\sum _{i=1}^N{\alpha }_i{y}_i=0\\ & C\ge {\alpha }_i\ge 0,i=1,2,\cdots ,N\end{array}$$ 求得最优解 ${\vec{\alpha }}^{\ast }=({\alpha }_1^{\ast },{\alpha }_2^{\ast },\cdots ,{\alpha }_N^{\ast }{)}^T$。

  2. 计算 $${\vec{w}}^{\ast }=\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i{\vec{x}}_i$$

  3. 同时选择 ${\vec{\alpha }}^{\ast }$ 的某个分量 $C>{\alpha }_j^{\ast }>0$，计算 $$b^{\ast }=y_j-\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i({\vec{x}}_i\cdot {\vec{x}}_j)$$

     可能存在多个符合条件的 ${\alpha }_j^{\ast }$。这是由于原始问题中，对 $b$ 的解不唯一。实际计算时，可以取在所有符合条件的样本点上的平均值。

  4. 由此得到软间隔最大化分离超平面：${\vec{w}}^{\ast }\cdot \vec{x}+b^{\ast }=0$，以及分类决策函数 $f(\vec{x})=\text{sign}({\vec{w}}^{\ast }\cdot \vec{x}+b^{\ast })$。

对偶问题的解 ${\vec{\alpha }}^{\ast }=({\alpha }_1^{\ast },{\alpha }_2^{\ast },\cdots ,{\alpha }_N^{\ast }{)}^T$ 中对应于 ${\alpha }_i^{\ast }>0$ 的样本点 $({\vec{x}}_i,y_i)$ 的实例点 ${\vec{x}}_i$ 称为支持向量（软间隔的支持向量），可能存在下列情形。

• 若 ${\alpha }_i^{\ast }<C$，则松弛量 ${\xi }_i=0$，支持向量恰好落在了间隔边界上。
  • 因为根据 ${\nabla }_{{\xi }_i}L(\vec{w},b,\vec{\xi },\vec{\alpha },\vec{\mu })=C-{\alpha }_i-{\mu }_i=0$，得到：
  • 当 ${\alpha }_i^{\ast }<C$，则 ${\mu }_i>0$，根据拉格朗日函数极值条件，必须有 ${\xi }_i=0$；
  • 当 ${\alpha }_i^{\ast }=C$，则 ${\mu }_i=0$，于是 ${\xi }_i$ 可能为任何正数。
• 若 ${\alpha }_i^{\ast }=C$，且 $0<{\xi }_i<1$，则支持向量落在间隔边界与分离超平面之间，分类正确。
• 若 ${\alpha }_i^{\ast }=C$，且 ${\xi }_i=1$，则支持向量落在分离超平面上。
• 若 ${\alpha }_i^{\ast }=C$，且 ${\xi }_i>1$，则支持向量落在分离超平面误分类一侧。

根据 ${\xi }_i$ 的定义，它就是使得函数间隔加上 ${\xi }_i$ 大于等于 1。即线性可分时，支持向量位于间隔边界：$y_i(\vec{w}\cdot {\vec{x}}_i+b)=1$ 上；现在支持向量位于 $y_i(\vec{w}\cdot {\vec{x}}_i+b)=1-{\xi }_i$ 上。

非线性支持向量机

对于给定的训练集 $T=\{({\vec{x}}_1,y_1),({\vec{x}}_2,y_2),\cdots ,({\vec{x}}_N,y_N)\}$，其中 ${\vec{x}}_i=(x_i^{(1)},x_i^{(2)},\cdots ,x_i^{(n)}{)}^T\in \mathcal{X}={\mathbb{R}}^n$，$y_i\in \mathcal{Y}=\{+1,-1\}$，$i=1,2,\cdots ,N$，如果能用 ${\mathbb{R}}^n$ 中的一个超曲面将正负实例正确分开，则称这个问题为非线性可分问题。

设 $\mathcal{X}\subseteq {\mathbb{R}}^n$ 是输入空间，$\mathcal{H}$ 为特征空间（希尔伯特空间）。若存在一个从 $\mathcal{X}$ 到 $\mathcal{H}$ 的映射 $\varphi (\vec{x}):\mathcal{X}\to \mathcal{H}$，使得所有的 $\vec{x},\vec{z}\in \mathcal{X}$，函数 $K(\vec{x},\vec{z})=\varphi (\vec{x})\cdot \varphi (\vec{z})$，则称 $K(\vec{x},\vec{z})$ 为核函数。即核函数将输入空间中的任意两个向量 $\vec{x},\vec{z}$ 映射为特征空间中对应的向量之间的内积。

通常我们不关心这个映射的具体表达形式，而是直接给出 $K(\vec{x},\vec{z})$。

考虑到在线性支持向量机的对偶形式中，只涉及输入实例和实例之间的内积，故将内积 ${\vec{x}}_i\cdot {\vec{x}}_j$ 替换成核函数 $K({\vec{x}}_i,{\vec{x}}_j)=\varphi ({\vec{x}}_i)\cdot \varphi ({\vec{x}}_j)$。则对偶问题的目标函数成为：

$$W(\vec{\alpha })=\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_{j}K({\vec{x}}_i,{\vec{x}}_j)-\sum _{i=1}^N{\alpha }_i$$

分类决策函数变成：

$$f(\vec{x})=\text{sign}\left(\sum _{i=1}^N{\alpha }_i^{\ast }{y}_{i}K({\vec{x}}_i,\vec{x})+b^{\ast }\right)$$

在给定核函数 $K(\vec{x},\vec{z})$ 的情况下，可以利用求解线性分类问题的方法求解非线性分类问题的支持向量机。学习是隐式地在特征空间进行的，这样的技巧称为核技巧。（在实际应用中，往往依赖经验直接选择核函数，然后验证该核函数确实是有效的核函数。）给出常用的一些核函数如下。

• 多项式核函数：$K(\vec{x},\vec{z})=(\vec{x}\cdot \vec{z}+1{)}^p$

  • 对应的支持向量机是一个 $p$ 次多项式分类器。
  • 此时分类决策函数成为 $$f(\vec{x})=\text{sign}\left(\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i({\vec{x}}_i\cdot \vec{x}+1{)}^p+b^{\ast }\right)$$

• 高斯核函数： $$K(\vec{x},\vec{z})=\exp \left(-\frac{||x-z|{|}_2^2}{2{\sigma }^2}\right)$$

  • 对应的支持向量机是高斯径向基函数分类器（radial basis function）。
  • 此时的分类决策函数成为 $$f(\vec{x})=\text{sign}\left(\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i\exp \left(-\frac{||x_i-x|{|}_2^2}{2{\sigma }^2}\right)+b^{\ast }\right)$$

• sigmoid核函数：$K(\vec{x},\vec{z})=\tanh (\gamma (\vec{x}\cdot \vec{z})+r)$。

最后我们总结非线性支持向量机学习算法。

• 输入
  • 训练数据集 $T=\{({\vec{x}}_1,y_1),({\vec{x}}_2,y_2),\cdots ,({\vec{x}}_N,y_N)\}$。
  • 惩罚参数 $C>0$。
• 输出：分类决策函数。
• 算法步骤如下。
  1. 选择适当的核函数 $K(\vec{x},\vec{z})$，求解约束最优化问题： $$\begin{array}{rl}& \underset{\vec{\alpha }}{\min }\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_{j}K({\vec{x}}_i,{\vec{x}}_j)-\sum _{i=1}^N{\alpha }_i\\ & \text{s.t. }\sum _{i=1}^N{\alpha }_i{y}_i=0\\ & C\ge {\alpha }_i\ge 0,i=1,2,\cdots ,N\end{array}$$ 求得最优解 ${\vec{\alpha }}^{\ast }=({\alpha }_1^{\ast },{\alpha }_2^{\ast },\cdots ,{\alpha }_N^{\ast }{)}^T$。
  2. 计算 $${\vec{w}}^{\ast }=\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i{\vec{x}}_i$$
  3. 同时选择 ${\vec{\alpha }}^{\ast }$ 的某个合适的分量 $C>{\alpha }_j^{\ast }>0$，计算 $$b^{\ast }=y_j-\sum _{i=1}^N{\alpha }_i^{\ast }{y}_{i}K({\vec{x}}_i,{\vec{x}}_j)$$
  4. 构造分类决策函数 $f(\vec{x})=\text{sign}\left({\sum }_{i=1}^N{\alpha }_i^{\ast }{y}_{i}K({\vec{x}}_i,\vec{x})+b^{\ast }\right)$。

当 $K(\vec{x},\vec{z})$ 是正定核函数时，该问题为凸二次规划问题，解是存在的。

支持向量回归

支持向量机不仅可以用于分类问题，也可以用于回归问题。给定训练数据集 $T=\{({\vec{x}}_1,y_1),({\vec{x}}_2,y_2),\cdots ,({\vec{x}}_N,y_N)\}$，其中 ${\vec{x}}_i=(x_i^{(1)},x_i^{(2)},\cdots ,x_i^{(n)}{)}^T\in \mathcal{X}={\mathbb{R}}^n$，$y_i\in \mathcal{Y}=\mathbb{R}$，$i=1,2,\cdots ,N$。对于样本 $({\vec{x}}_i,y_i)$ 通常根据模型输出 $f({\vec{x}}_i)$ 与真实值 $y_i$ 之间的差别来计算损失，当且仅当 $f({\vec{x}}_i)=y_i$ 时损失才为零。

支持向量回归（Support Vector Regression，SVR）的基本思路是：允许 $f({\vec{x}}_i)$ 与 $y_i$ 之间最多有 $\epsilon$ 的偏差。仅当 $|f({\vec{x}}_i)-y_i|>\epsilon$ 时，才计算损失。当 $|f({\vec{x}}_i)-y_i|\le \epsilon$ 时，我们认为预测正确。

用数学语言描述 SVR 问题：

$$\underset{\vec{w},b}{\min }\frac{1}{2}||\vec{w}|{|}_2^2+C\sum _{i=1}^N{L}_{\epsilon }(f({\vec{x}}_i)-y_i)$$

其中 $C\ge 0$ 为罚项常数，$L_{\epsilon }$ 为损失函数 $L_{\epsilon }$，如图 7.2 所示。$L_{\epsilon }$ 定义为：

$$L_{\epsilon }(z)=\{\begin{array}{ll}0& ,\text{if }|z|\le \epsilon \\ |z|-\epsilon & ,\text{else}\end{array}$$

线性回归中，损失函数为 $L(z)=z^2$。

更进一步，引入松弛变量 ${\xi }_i,{\hat{\xi }}_i$，则新的最优化问题为：

$$\begin{array}{rl}& \underset{\vec{w},b,{\xi }_i,{\hat{\xi }}_i}{\min }\frac{1}{2}||\vec{w}|{|}_2^2+C\sum _{i=1}^N({\xi }_i+{\hat{\xi }}_i)\\ & \text{s.t. }f({\vec{x}}_i)-y_i\le \epsilon +{\xi }_i,\\ & y_i-f({\vec{x}}_i)\le \epsilon +{\hat{\xi }}_i,\\ & {\xi }_i\ge 0,{\hat{\xi }}_i\ge 0,i=1,2,\cdots ,N\end{array}$$

这就是 SVR 原始问题。类似地，引入拉格朗日乘子，${\mu }_i\ge 0,{\hat{\mu }}_i\ge 0,{\alpha }_i\ge 0,{\hat{\alpha }}_i\ge 0$，定义拉格朗日函数：

$$\begin{array}{rl}L(\vec{w},b,\vec{\alpha },\hat{\vec{\alpha }},\vec{\xi },\hat{\vec{\xi }},\vec{\mu },\hat{\vec{\mu }})& =\frac{1}{2}||\vec{w}|{|}_2^2+C\sum _{i=1}^N({\xi }_i+{\hat{\xi }}_i)-\sum _{i=1}^N{\mu }_i{\xi }_i-\sum _{i=1}^N{\hat{\mu }}_i{\hat{\xi }}_i\\ & +\sum _{i=1}^N{\alpha }_i(f({\vec{x}}_i)-y_i-\epsilon -{\xi }_i)+\sum _{i=1}^N{\hat{\alpha }}_i(y_i-f({\vec{x}}_i)-\epsilon -{\hat{\xi }}_i)\end{array}$$

根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题

$$\left(\underset{\vec{\alpha },\hat{\vec{\alpha }}}{\max }\underset{\vec{w},b,\vec{\xi },\hat{\vec{\xi }}}{\min }L(\vec{w},b,\vec{\alpha },\hat{\vec{\alpha }},\vec{\xi },\hat{\vec{\xi }},\vec{\mu },\hat{\vec{\mu }})\right)$$

先求极小问题：根据 $L(\vec{w},b,\vec{\alpha },\hat{\vec{\alpha }},\vec{\xi },\hat{\vec{\xi }},\vec{\mu },\hat{\vec{\mu }})$ 对 $\vec{w},b,\vec{\xi },\hat{\vec{\xi }}$ 偏导数为零可得：

$$\{\begin{array}{l}\vec{w}=\sum _{i=1}^N({\hat{\alpha }}_i-{\alpha }_i){\vec{x}}_i\\ 0=\sum _{i=1}^N({\hat{\alpha }}_i-{\alpha }_i)\\ C={\alpha }_i+{\mu }_i\\ C={\hat{\alpha }}_i+{\hat{\mu }}_i\end{array}$$

再求极大问题（取负号变极小问题）：

$$\begin{array}{rl}& \underset{\vec{\alpha },\hat{\vec{\alpha }}}{\min }\sum _{i=1}^N\left[y_i({\hat{\alpha }}_i-{\alpha }_i)-\epsilon ({\hat{\alpha }}_i+{\alpha }_i)\right]-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N({\hat{\alpha }}_i-{\alpha }_i)({\hat{\alpha }}_j-{\alpha }_j){\vec{x}}_i^T{\vec{x}}_j\\ & \text{s.t. }\sum _{i=1}^N({\hat{\alpha }}_i-{\alpha }_i)=0\\ & 0\le {\alpha }_i,{\hat{\alpha }}_i\le C\end{array}$$