支持向量机（support vector machines，SVM）是一种二类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；支持向量机还包括核技巧，这使它成为实质上的非线性分类器。
支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划（convex quadratic programming）的问题，也等价于正则化的合页损失函数的最小化问题。
支持向量机的学习算法是求解凸二次规划的最优化算法。

支持向量机学习方法包含构建由简至繁的模型：

线性可分支持向量机（linear support vector machine in linearly separable case）

当训练数据线性可分时，通过硬间隔最大化（hard margin maximization），学习一个线性分类器，即线性可分支持向量机，又称为硬间隔支持向量机。
线性支持向量机（linear support vector machine）

当训练数据近似线性可分时，通过软间隔最大化（soft margin maximization），也学习一个线性的分类器，即线性支持向量机，又称为软间隔支持向量机。
非线性支持向量机（non-linear support vector machine）

当训练数据线性不可分时，通过使用核技巧（kernel trick）及软间隔最大化，学习非线性支持向量机。

当输入空间为欧式空间或离散集合、特征空间为希尔伯特空间时，核函数（kernel function）表示将输入从输入空间映射到特征空间得到的特征向量之间的内积。通过使用核函数可以学习非线性支持向量机，等价于隐式地在高维的特征空间中学习线性支持向量机。

7.1 线性可分支持向量机与硬间隔最大化

7.1.1 线性可分支持向量机

假设输入空间与特征空间为两个不同的空间。输入空间为欧式空间或离散集合，特征空间为欧式空间或希尔伯特空间。线性可分支持向量机、线性支持向量机假设这两个空间的元素一一对应，并将输入空间中的输入映射为特征空间中的特征向量。非线性支持向量机利用一个从输入到特征空间的非线性映射将输入映射为特征向量。所以，输入都由输入空间转换到特征空间，支持向量机的学习是在特征空间进行的。

假设给定一个特征空间上的训练数据集

$T = \{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$

其中，$x_i \in \chi = R^n, y \in \mathcal{Y} = \{+1, -1\}, i=1,2,…,N$；在假设训练数据集是线性可分的。

学习的目标是：在特征空间中找到一个分离超平面，能将实例分到不同的类。分离超平面对应于方程$\omega · x + b = 0$，它由法向量$\omega$和截距$b$决定，可用$(\omega,b)$来表示。分离超平面将特征空间划分为两部分，一部分是正类，一部分是负类。法向量指向一侧为正类，另一侧为负类。

一般地，当训练数据集线性可分时，存在无穷个分离超平面可将两类数据正确分开。感知机利用误分类最小的策略，求得分离超平面，不过这时的解有无穷多个。线性可分支持向量机利用间隔最大化求最优分离超平面，这时，解是唯一的。

定义 7.1（线性可分支持向量机） 给定线性可分训练数据集，通过间隔最大化或等价地求解相应的凸二次规划问题学习得到的分离超平面为

$\omega^* · x + b^* = 0 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.1)$

以及相应的分类决策函数

$f(x) = sign(\omega^* · x + b^*)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.2)$

称为线性可分支持向量机。

7.1.2 函数间隔和几何间隔

一般来说，一个点距离分离超平面的远近可以表示分类预测的确信程度。在超平面$\omega · x + b = 0$确定的情况下，$|\omega · x + b|$能够相对地表示点$x$距离超平面的远近。而$\omega · x + b$的符号与类标记$y$的符号是否一致能够表示分类是否正确。所以可用量$y(\omega · x + b)$来表示分类的正确性及确信度，这就是函数间隔（functional margin）的概念。

定义 7.2（函数间隔） 对于给定的训练数据集$T$和超平面$(\omega,b)$，定义超平面$(\omega,b)$关于样本点$(x_i,y_i)$的函数间隔为
$\hat \gamma_i = y_i(\omega·x_i+b)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.3)$
定义超平面$(\omega,b)$关于训练数据集$T$的函数间隔为超平面$(\omega,b)$关于$T$中所有样本点$(x_i,y_i)$的函数间隔之最小值，即
$\hat \gamma= \min\limits_{i=1,2,...,N}\hat\gamma_i\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.4)$
函数间隔可以表示分类预测的正确性及确信度。
但是选择分离超平面时，只有函数间隔还不够。因为只要成比例地改变$\omega$和$b$，超平面并没有改变，但函数间隔却成为原来的2倍。可以对分离超平面的法向量$\omega$加某些约束，如规范化，$||\omega|| = 1$，这使得间隔是确定的。这时函数间隔成为几何间隔（geometric margin）。

定义 7.3（几何间隔） 对于给定的训练数据集$T$和超平面$(\omega,b)$，定义超平面$(\omega,b)$关于样本点$(x_i,y_i)$的几何间隔为
$\gamma_i = y_i(\frac{\omega}{||\omega||}·x_i + \frac{b}{||\omega||})\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.5)$
定义超平面$(\omega,b)$关于训练数据集$T$的几何间隔为超平面$(\omega,b)$关于$T$中所有样本点$(x_i,y_i)$的几何间隔之最小值，即
$\gamma= \min\limits_{i=1,2,...,N}\gamma_i\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.6)$
超平面$(\omega,b)$关于样本点$(x_i,y_i)$的几何间隔一般是实例点到超平面的带符号的距离（signed distance），当样本点被超平面正确分类时就是实例点到超平面的距离。

从函数间隔和几何间隔的定义可知，函数间隔和几何间隔有下面的关系：

$\gamma_i = \frac{\hat\gamma_i}{||\omega||}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.7)$ $\gamma = \frac{\hat\gamma}{||\omega||}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.8)$

如果$||\omega|| = 1$，那么函数间隔和几何间隔相等。如果超平面参数$\omega$和$b$成比例地改变（超平面没有改变），函数间隔也按此比例改变，而几何间隔不变。

7.1.3 间隔最大化

支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。

间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。也就是说，不仅将正负实例点分开，而且对最难分的实例点（离超平面最近的点）也有足够大的确信度将它们分开。

最大间隔分离超平面

考虑如何求得一个几何间隔最大的分离超平面，即最大间隔分离超平面。具体地，这个问题可以表示为下面的约束最优化问题：

$\max\limits_{\omega,b} \gamma\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.9)$ $s.t.\ \ \ y_i(\frac{\omega}{||\omega||}·x_i + \frac{b}{||\omega||}) \geq \gamma, \ \ \ i=1,2,...,N\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.10)$

即我们希望最大化超平面$(\omega,b)$关于训练数据集的几何间隔$\gamma$，约束条件表示的是超平面$(\omega,b)$关于每个训练样本点的几何间隔至少是$\gamma$。

考虑几何间隔和函数间隔的关系式，可将这个问题改写为

$\max\limits_{\omega,b} \frac{\hat\gamma}{||\omega||}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.11)$ $s.t.\ \ \ y_i(\omega·x_i+b) \geq \hat\gamma, \ \ \ i=1,2,...,N\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.12)$

函数间隔$\hat\gamma$的取值并不影响最优化问题的解。事实上，假设将$\omega$和$b$按比例改变为$\lambda\omega$和$\lambda b$，这时函数间隔成为$\lambda \hat\gamma$。函数间隔的这一改变对上面最优化问题的不等式约束没有影响，对目标函数的优化也没有影响，也就是说，它产生一个等价的最优化问题。这样，就可以取$\hat\gamma = 1$。将$\hat\gamma = 1$代入上面的最优化问题，注意到最大化$\frac{1}{||\omega||}$和最小化$\frac{1}{2}||\omega||^2$是等价的，于是就得到下面的线性可分支持向量机学习的最优化问题：

$\min\limits_{\omega,b}\frac{1}{2}||\omega||^2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.13)$ $s.t.\ \ \ y_i(\omega·x_i+b) - 1 \geq 0, \ \ \ i=1,2,...,N\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.14)$

这是一个凸二次规划（convex quadratic programming）问题。

凸优化问题是指约束最优化问题

$\min f(\omega)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.15)$ $s.t.\ \ \ g_i(\omega) \leq 0, \ \ \ i=1,2,...,k\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.16)$ $h_i(\omega) = 0, \ \ \ i=1,2,...,l\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.17)$

其中，目标函数$f(\omega)$和约束函数$g_i(\omega)$都是$R^n$上的连续可微的凸函数，约束函数$h_i(\omega)$是$R^n$上的仿射函数。

注：$f(x)$称为仿射函数，如果它满足$f(x) = a·x +b,a\in R^n,b \in R^n,x\in R^n$。

当目标函数$f(\omega)$是二次函数且约束函数$g_i(\omega)$是仿射函数时，上述凸最优化问题称为凸二次规划问题。

算法 7.1（线性可分支持向量机学习算法——最大间隔法）

输入：线性可分训练数据集$T = \{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\}$，其中，$x_i \in \chi = R^n, y \in \mathcal{Y} = \{+1, -1\}, i=1,2,…,N$；

输出：最大间隔分离超平面和分类决策函数。

（1）构造并求解约束最优化问题：

$\min\limits_{\omega,b}\frac{1}{2}||\omega||^2$ $s.t.\ \ \ y_i(\omega·x_i+b) - 1 \geq 0, \ \ \ i=1,2,...,N$

求得最优解$\omega^,b^$。

（2）由此得到分离超平面：

$\omega ^* ·x + b^* = 0$

分类决策函数

$f(x) = sign(\omega ^* ·x + b^*)$

最大间隔分离超平面的存在唯一性

定理 7.1（最大间隔分离超平面的存在唯一性） 若训练数据集$T$线性可分，则可将训练数据集中的样本点完全正确分开的最大间隔分离超平面存在且唯一。

支持向量和间隔边界

在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量（support vector）。支持向量是使约束条件式（7.14）等号成立的点，即

$y_i(\omega·x_i+ b) -1 = 0$

对$y_i = +1$的正例点，支持向量在超平面

$H_1 ：\omega ·x +b = 1$

上，对$y_i = -1$的正例点，支持向量在超平面

$H_1 ：\omega ·x +b = -1$

上。

c，并且没有实例点落在它们中间。在$H_1$与$H_2$之间形成一条长带，分离超平面与它们平行且位于它们中央。长带的宽度，即$H_1$与$H_2$之间的距离称为间隔（margin）。间隔依赖于分离超平面的法向量$\omega$，等于$\frac{2}{||\omega||}$。$H_1$和$H_2$称为间隔边界。

在决定分离超平面时只有支持向量起作用，而其他实例点并不起作用。

支持向量的个数一般很少，所以支持向量机由很少的“重要的”训练样本确定。

7.1.4 学习的对偶算法

通过求解对偶问题（dual problem）得到原始问题（primal problem）的最优解，这就是线性可分支持向量机的对偶算法（dual algorithm）。

这样做的优点：

对偶问题往往更容易求解；
自然引入核函数，进而推广到非线性分类问题。

首先构建拉格朗日函数（Lagrange function）。为此，对每一个不等式约束$(7.14)$引进拉格朗日乘子（Lagrange multiplier）$\alpha_i \geq 0,\ \ \ i = 1,2,…,N$，定义拉格朗日函数：

$L(\omega,b,\alpha) = \frac{1}{2}||\omega||^2 - \sum\limits_{i=1}^{N}\alpha_i y_i (\omega·x_i + b) + \sum\limits_{i=1}^{N}\alpha_i\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.18)$

其中，$\alpha = (\alpha_1,\alpha_2,…,\alpha_N)^T$为拉格朗日乘子向量。

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

$\max\limits_{\alpha} \min\limits_{\omega,b}L(\omega,b,\alpha)$

所以，为了得到对偶问题的解，需要先求$L(\omega,b,\alpha)$对$\omega,b$的极小，再求对$\alpha$的极大。

对偶最优化问题：

$\min\limits_{\alpha} \ \ \ \frac{1}{2}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\alpha_i \alpha_j y_i y_j (x_i·x_j)\ - \ \sum\limits_{i=1}^{N}\alpha_i\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.22)$ $s.t. \ \ \ \sum\limits_{i=1}^{N}\alpha_i y_i = 0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.23)$ $\alpha_i \geq 0, \ \ \ i = 1,2,...,N\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.24)$

定理 7.2 设$\alpha^ = (\alpha^_1,\alpha^_2,…,\alpha^_l)^T$是对偶最优化问题$(7.22)$ ~ $(7.24)$的解，则存在下标$j$，使得$\alpha_j^ > 0$，并可按下式求得原始最优化问题$(7.13)$ ~ $(7.14)$的解$\omega^,b^*$

$\omega^* =\sum\limits_{i=1}^{N}\alpha_i y_i x_i\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.25)$ $b^* = y_j - \sum\limits_{i=1}^{N}\alpha_i y_i (x_i·x_j)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.26)$

由此定理可知，分离超平面可以写成

$\sum\limits_{i=1}^{N}\alpha_i^* y_i (x·x_i) + b^* = 0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.29)$

分类决策函数可以写成

$f(x) = sign(\sum\limits_{i=1}^{N}\alpha_i^* y_i (x·x_i) + b^*)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.30)$

这就是说，分类决策函数只依赖于输入$x$和训练样本输入的内积。式$(7.30)$称为线性可分支持向量机的对偶形式。

综上所述，对于给定的线性可分训练数据集，可以首先求对偶问题$(7.22)$ ~ $(7.24)$的解$\alpha^$；再利用式$(7.25)$ ~ $(7.26)$求得原始问题的解$\omega^,b^*$；从而得到分离超平面及分类决策函数。这种算法称为线性可分支持向量机的对偶学习算法，是线性可分支持向量机学习的基本算法。

算法 7.2（线性可分支持向量机学习算法）

输入：线性可分训练数据集$T = \{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\}$，其中，$x_i \in \chi = R^n, y \in \mathcal{Y} = \{+1, -1\}, i=1,2,…,N$；

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

（1）构造并求约束最优化问题

$\min\limits_{\alpha} \ \ \ \frac{1}{2}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\alpha_i \alpha_j y_i y_j (x_i·x_j)\ + \ \sum\limits_{i=1}^{N}\alpha_i$ $s.t. \ \ \ \sum\limits_{i=1}^{N}\alpha_i y_i = 0$ $\alpha_i \geq 0, \ \ \ i = 1,2,...,N$

求得最优解$\alpha^ = (\alpha^_1,\alpha^_2,…,\alpha^_N)^T$。

（2）计算

$\omega^* =\sum\limits_{i=1}^{N}\alpha_i y_i x_i$

并选择$\alpha^$的一个正分量$\alpha_j^ > 0 $，计算

$b^* = y_j - \sum\limits_{i=1}^{N}\alpha_i y_i (x_i·x_j)$

（3）求得分离超平面

$\omega^*·x +b^* = 0$

分类决策函数：

$f(x) = sign(\omega^*·x +b^*)$

由式$(7.25)$、式$(7.26)$可知，$\omega^$和$b^$只依赖于训练数据中对应于$\alpha_i^ > 0$的样本点$(x_i,y_i)$，而其他样本点对$\omega^$和$b^$没有影响。我们将训练数据中对应于$\alpha_i^ > 0$的实例点$x_i \in R^n$称为支持向量。

定义 7.4（支持向量） 考虑原始最优化问题$(7.13)$ ~ $(7.14)$及对偶最优化问题$(7.22)$ ~ $(7.24)$，将训练数据集中对应于$\alpha_i^* > 0$的样本点$(x_i,y_i)$的实例$x_i \in R^n$称为支持向量。

7.2 线性支持向量机与软间隔最大化

7.2.1 线性支持向量机

假设给定一个特征空间上的训练数据集

$T = \{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$

其中，$x_i \in \chi = R^n, y \in Y = \{+1, -1\}, i=1,2,…,N$，$x_i$为第$i$个特征向量，$y_i$为$x_i$的类标记。再假设训练数据集不是线性可分的。通常情况是，训练数据中有一些特异点（outlier），将这些特异点出去后，剩下大部分的样本点组成的集合是线性可分的。

线性不可分意味着某些样本点$(x_i,y_i)$不能满足函数间隔大于等于1的约束条件$(7.14)$。为了解决这个问题，可以对每个样本点$(x_i,y_i)$引进一个松弛变量$\xi_i \geq 0$，使函数间隔加上松弛变量大于等于1。这样，约束条件变为

$y_i(\omega·x_i+b) \geq 1 - \xi_i$

同时，对每个松弛变量$\xi_i$，支付一个代价$\xi_i$。目标函数由原来的$\frac{1}{2}||\omega||^2$变成

$\frac{1}{2}||\omega||^2 \ + \ C\sum\limits_{i=1}^N \xi_i\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.31)$

这里，$C>0$称为惩罚参数，一般由应用问题决定，$C$值大时对误分类的惩罚增大，$C$值小时对误分类的惩罚减小。最小化目标函数$(7.31)$包含两层含义：使$\frac{1}{2}||\omega||^2 $尽量小即间隔尽量大，同时使误分类点的个数尽量小，$C$是调和二者的系数。

线性不可分的支持向量机的学习问题变成如下凸二次规划（convex quadratic programming）问题（原始问题）：

$\min\limits_{\omega,b,\xi} \ \ \ \frac{1}{2}||\omega||^2 \ + \ C\sum\limits_{i=1}^N \xi_i\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.32)$ $s.t.\ \ \ y_i(\omega·x_i+b) \geq 1 - \xi_i \ \ \ i = 1,2,...,N\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.33)$ $\xi_i \geq 0,\ \ \ i = 1,2,...,N\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.34)$

原始问题$(7.32)$ ~ $(7.34)$是一个凸二次规划问题，因而关于$(\omega,b,\xi)$的解是存在的。可以证明$\omega$的解是唯一的，但$b$的解可能不唯一，而是存在于一个区间。

定义 7.5（线性支持向量机） 对于给定的线性不可分的训练数据集，通过求解凸二次规划问题，即软间隔最大化问题$(7.32)$ ~ $(7.34)$，得到的分离超平面为

$\omega^* · x + b^* =0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.35)$

以及相应的分类决策函数

$f(x) = sign(\omega^* · x + b^*)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.36)$

称为线性支持向量机。

显然，线性支持向量机包含线性可分支持向量机。

7.2.2 学习的对偶算法

原始问题$(7.32)$ ~ $(7.34)$的对偶问题是

$\min\limits_{\alpha} \ \ \ \frac{1}{2}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\alpha_i \alpha_j y_i y_j (x_i·x_j)\ - \ \sum\limits_{i=1}^{N}\alpha_i\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.37)$ $s.t. \ \ \ \sum\limits_{i=1}^{N}\alpha_i y_i = 0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.38)$ $0 \leq \alpha_i \leq C, \ \ \ i = 1,2,...,N\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.39)$

定理 7.3 设$\alpha^ = (\alpha^_1,\alpha^_2,…,\alpha^_N)^T$是对偶问题$(7.37)$~$(7.39)$的一个解，若存在$\alpha^$的一个分量$\alpha_j^$，$0< \alpha_j^<C$ ，则原始问题$(7.32)$~$(7.34)$的解$\omega^,b^*$可按下式求得：

$\omega^* =\sum\limits_{i=1}^{N}\alpha_i^* y_i x_i\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.50)$ $b^* = y_j - \sum\limits_{i=1}^{N}\alpha_i^* y_i (x_i·x_j)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.51)$

由此定理可知，分离超平面可以写成

$\sum\limits_{i=1}^{N}\alpha_i^* y_i (x·x_j) + b^* = 0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.55)$

分类决策函数可以写成

$f(x)= sign(\sum\limits_{i=1}^{N}\alpha_i^* y_i (x·x_j) + b^*)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.56)$

算法 7.3（线性支持向量机学习算法）

输入：线性可分训练数据集$T = \{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\}$，其中，$x_i \in \chi = R^n, y \in \mathcal{Y} = \{+1, -1\}, i=1,2,…,N$；

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

（1）选择惩罚参数$C>0$，构造并求解凸二次规划问题

$\min\limits_{\alpha} \ \ \ \frac{1}{2}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\alpha_i \alpha_j y_i y_j (x_i·x_j)\ - \ \sum\limits_{i=1}^{N}\alpha_i$ $s.t. \ \ \ \sum\limits_{i=1}^{N}\alpha_i y_i = 0$ $0 \leq \alpha_i \leq C, \ \ \ i = 1,2,...,N$

求得最优解$\alpha^ = (\alpha^_1,\alpha^_2,…,\alpha^_N)^T$。

（2）计算$\omega^ = \sum\limits_{i=1}^{N}\alpha_i^ y_i x_i$

选择$\alpha^$的一个分量$\alpha_j^$适合条件$0<\alpha_j^* <C$，计算

$b^* = y_j - \sum\limits_{i=1}^{N}\alpha_i^* y_i (x_i·x_j)$

（3）求得分离超平面

$\omega^*·x+b^* = 0$

分类决策函数

$f(x)=sign(\omega^*·x+b^*)$

7.2.3 支持向量

在线性不可分的情况下，将对偶问题$(7.37)$~$(7.39)$的解$\alpha^ = (\alpha^_1,\alpha^_2,…,\alpha^_N)^T$中对应于$\alpha^*_i > 0$的样本点$(x_i,y_i)$的实例$x_i$称为支持向量（软间隔的支持向量）。

软间隔的支持向量$x_i$或者在间隔边界上，或者在间隔边界与分离超平面之间，或者在分离超平面误分一侧。

若$\alpha_i^* <C$，则$\xi_i = 0$，支持向量$x_i$恰好落在间隔边界上；
若$\alpha_i^* = C$，$0<\xi_i <1$，则分类正确，$x_i$在间隔边界与分离超平面之间；
若$\alpha_i^* = C$，$\xi_i = 1$，则$x_i$在分离超平面上；
若$\alpha_i^* = C$，$\xi_i > 1$，则$x_i$位于分离超平面误分类一侧。

7.2.4 合页损失函数

线性支持向量机学习还有另外一种解释，就是最小化以下目标函数：

$\sum\limits_{i=1}^{N}[1-y_i(\omega·x +b)]_{+} + \lambda||\omega||^2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.57)$

目标函数的第1项是经验损失或经验风险，函数
$L(y(\omega·x + b)) = [1-y(\omega·x+b)]_{+}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.58)$
称为合页损失函数（hinge loss function）。下标“+”表示以下去正值的函数。
$[z]_{+} = \lbrace_{0,\ \ \ z \leq 0}^{z, \ \ \ z >0}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.59)$
这就是说，当样本点$(x_i,y_i)$被正确分类且函数间隔（确信度）$y_i(\omega·x_i+b)$大于1时，损失是0，否则损失是$1-y_i(\omega·x_i+b)$。
目标函数的第2项是系数为$\lambda$的$\omega$的$L_2$范数，是正则化项。

定理 7.4 线性支持向量机原始最优化问题：

$\min\limits_{\omega,b,\xi} \ \ \ \frac{1}{2}||\omega||^2 \ + \ C\sum\limits_{i=1}^N \xi_i$ $s.t.\ \ \ y_i(\omega·x_i+b) \geq 1 - \xi_i \ \ \ i = 1,2,...,N$ $\xi_i \geq 0,\ \ \ i = 1,2,...,N$

等价于最优化问题

$\min\limits_{\omega,b}\ \ \ \sum\limits_{i=1}^{N}[1-y_i(\omega·x +b)]_{+} + \lambda||\omega||^2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.63)$

合页损失函数横轴是函数间隔$y(\omega·x +b)$，纵轴是损失。由于函数形状像一个合页，故名合页损失函数。

0-1损失函数，可以认为它是二分类问题的真正的损失函数，而合页损失函数是0-1损失函数的上界。由于0-1损失函数不是连续可导的，直接优化由其构成的目标函数比较困难，可以认为线性支持向量机是优化由0-1损失函数的上界（合页损失函数）构成的目标函数。这时的上界损失函数又称为代理损失函数（surrogate loss function）。

合页损失函数不仅要分类正确，而且确信度足够高时损失才是0。也就是说，合页损失函数对学习有更高的要求。

7.3 非线性支持向量机与核函数

非线性支持向量机主要特点是利用核技巧（kernel trick）。

7.3.1 核技巧

非线性分类问题

一般来说，对给定的一个训练数据集$T = \{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\}$，其中，$x_i \in \chi = R^n, y \in Y = \{+1, -1\}, i=1,2,…,N$。如果能用$R^n$中的一个超曲面将正负例正确分开，则称这个问题为非线性可分问题。

非线性问题往往不好求解，所以希望能用解线性分类问题的方法解决这个问题。所采取的方法是进行一个非线性变换，将非线性问题变换为线性问题，通过解变换后的线性问题的方法求解原来的非线性问题。

用线性分类方法求解非线性分类问题分为两步：

使用一个变换将原空间的数据映射到新空间；
在新空间里用线性分类学习方法从训练数据中学习分类模型。

核函数的定义

定义 7.6 （核函数） 设$\chi$是输入空间（欧式空间$R^n$的子集或离散集合），又设$\mathcal{H}$为特征空间（希尔伯特空间），如果存在一个从$\mathcal{X}$到$\mathcal{H}$的映射

$\phi(x) : \mathcal{X} \longrightarrow \mathcal{H}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.65)$

使得对所有$x,z \in \mathcal{X}$，函数$K(x,z)$满足条件

$K(x,z) = \phi(x)·\phi(z)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.66)$

则称$K(x,z)$为核函数，$\phi(x)$为映射函数，式中$\phi(x)·\phi(z)$为$\phi(x)$和$\phi(z)$的内积。

核技巧想法是，在学习与预测中只定义核函数$K(x,z)$，而不显示地定义映射函数$\phi$。通常，直接计算$K(x,z)$比较容易，而通过$\phi(x)$和$\phi(z)$计算$K(x,z)$并不容易。

对于给定的核$K(x,z)$，特征空间$\mathcal{H}$和映射函数$\phi$的取法并不唯一，可以取不同的特征空间，即便是在同一特征空间里也可以取不同的映射。

核技巧在支持向量机中的应用

在线性支持向量机的对偶问题中，无论是目标函数还是决策函数（分离超平面）都只涉及输入实例与实例之间的内积。在对偶问题的目标函数$(7.37)$中内积$x_i·x_j$可以用核函数$K(x_i,x_j) = \phi(x_i)·\phi(x_j)$来代替。此时对偶问题的目标函数成为

$W(\alpha) = \frac{1}{2}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\alpha_i \alpha_j y_i y_j K(x_i,x_j)\ - \ \sum\limits_{i=1}^{N}\alpha_i\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.67)$

同样，分类决策函数中的内积也可以用核函数代替，而分类决策函数式成为

$f(x)= sign(\sum\limits_{i=1}^{N}\alpha_i^* y_i \phi(x)·\phi(x_j) + b^*)$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =sign(\sum\limits_{i=1}^{N}\alpha_i^* y_i K(x_i,x) + b^*)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.68)$

这等价于经过映射函数$\phi$将原来的输入空间变换到一个新的特征空间，将输入空间中的内积$x_i·x_j$变换为特征空间中的内积$\phi(x_i)·\phi(x_j)$，在新的特征空间里从训练样本中学习线性支持向量机。当映射函数是非线性函数时，学习到的含有核函数的支持向量机是非线性分类模型。

在核函数$K(x,z)$给定的条件下，可以利用解线性分类问题的方法来求解非线性分类问题的支持向量机。学习是隐式地在特征空间进行的，不需要显式地定义特征空间和映射函数。这样的技巧称为核技巧，它是巧妙地利用线性分类学习方法与核函数解决非线性问题的技术。

7.3.2 正定核

通常所说的核函数就是正定核函数（positive definite kernel function）。

假设$K(x,z)$是定义在$\mathcal{X} \times \mathcal{X}$上的对称函数，并且对任意的$x_i,x_2,…,x_m \in \mathcal{X}$，$K(x,z)$关于$x_i,x_2,…,x_m$的$Gram$矩阵是半正定的。可以依据函数$K(x,z)$，构成一个希尔伯特空间(Hilbert space)，其步骤是：首先定义映射$\phi$并构成向量空间$\mathcal{S}$；然后在$\mathcal{S}$上定义内积构成内积空间；最后将$\mathcal{S}$完备化构成希尔伯特空间。

定义映射，构成向量空间$\mathcal{S}$

先定义映射

$\phi : x \longrightarrow K(·,x)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.69)$

根据这一映射，对任意$x_i \in \mathcal{X},\alpha_i \in R,i=1,2,…,m$，定义线性组合

$f(·)=\sum\limits_{i=1}^{m}\alpha_i K(·,x_i)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.70)$

考虑由线性组合为元素的集合$\mathcal{S}$。由于集合$\mathcal{S}$对加法和数乘运算是封闭的，所以$\mathcal{S}$构成一个向量空间。

在$\mathcal{S}$上定义内积，使其成为内积空间

在$\mathcal{S}$上定义一个运算$*$：对任意$f,g \in \mathcal{S}$,

$f(·)=\sum\limits_{i=1}^{m}\alpha_i K(·,x_i)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.71)$ $g(·)=\sum\limits_{j=1}^{l}\beta_j K(·,z_j)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.72)$

定义运算$*$

$f * g = \sum\limits_{i=1}^{m}\sum\limits_{j=1}^{l}\alpha_i\beta_j K(x_i,z_j)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.73)$

赋予内积的向量空间为内积空间。因此$\mathcal{S}$是一个内积空间。既然$*$为$\mathcal{S}$的内积运算，那么仍然用$·$表示，即

$f · g = \sum\limits_{i=1}^{m}\sum\limits_{j=1}^{l}\alpha_i\beta_j K(x_i,z_j)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.74)$

将内积空间$\mathcal{S}$完备化为希尔伯特空间

现将内积空间$\mathcal{S}$完备化。由式$(7.81)$定义的内积可以得到范数

$||f|| = \sqrt{f·f}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.82)$

因此，$\mathcal{S}$是一个赋范向量空间。根据泛函分析理论，对于不完备的赋范向量空间$\mathcal{S}$，一定可以使之完备化，得到完备的赋范向量空间$\mathcal{H}$。一个内积空间，当作为一个赋范向量空间是完备的时候，就是希尔伯特空间。这样，就得到了希尔伯特空间$\mathcal{H}$。

这一希尔伯特空间$\mathcal{H}$称为再生核希尔伯特空间（reproducing kernel Hilbert space，RKHS）。这是由于核$K$具有再生性，即满足

$K(·,x)·f = f(x)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.83)$

及

$K(·,x) · K(·,z) = K(x,z)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.84)$

称为再生核。

正定核的充要条件

定理 7.5（正定核的充要条件） 设$K:\mathcal{X} \times \mathcal{X} \longrightarrow R$是对称函数，则$K(x,z)$为正定核函数的充要条件是对任意$x_i \in \mathcal{X},i=1,2,…,m$，$K(x,z)$对应的$Gram$矩阵：

$K = [K(x_i,x_j)]_{m \times m}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.85)$

是半正定矩阵。

定义 7.7（正定核的等价定义） 设$\mathcal{X} \subset R^n$，$K(x,z)$是定义在$\mathcal{X} \times \mathcal{X}$上的对称函数，如果对任意$x_i \in \mathcal{X},i=1,2,…,m$，$K(x,z)$对应的$Gram$矩阵

$K = [K(x_i,x_j)]_{m \times m}$

是半正定矩阵，则称$K(x,z)$是正定核。

7.3.3 常用核函数

多项式核函数（polynomial kernel function）

$K(x,z) = (x·z + 1 )^p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.88)$

对应的支持向量机是一个$p$次多项式分类器。在此情形下，分类决策函数成为

$f(x) = sign(\sum\limits_{i=1}^{N_\mathcal{S}}a_i^* y_i(x_i·x + 1)^p + b^*)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.89)$

高斯核函数（Gaussian kernel function）

$K(x,z) = exp(-\frac{||x-z||^2}{2\sigma^2})\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.90)$

对应的支持向量机是高斯径向基函数（radial basis function）分类器。在此情形下，分类决策函数成为

$f(x) = sign(\sum\limits_{i=1}^{N_\mathcal{S}}a_i^* y_iexp(-\frac{||x-x_i||^2}{2\sigma^2}) + b^*)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.91)$

字符串核函数（string kernel function）

核函数不仅可以定义在欧式空间上，还可以定义在离散数据的集合上。

两个字符串$s$和$t$上的字符串核函数是基于映射$\phi$的特征空间中的内积：

$k_n(s,t) = \sum\limits_{u\in \sum^n}[\phi_n(s)]_u [\phi_n(t)]_u$ $= \sum\limits_{u\in \sum^n}\sum\limits_{(i,j):s(i)=t(j)=u}\lambda^{l(i)}\lambda^{l(j)}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.93)$

字符串核函数$k_n(s,t)$给出了字符串$s$和$t$中长度等于$n$的所有子串组成的特征向量的余弦相似度（cosine similarity）。直观上，两个字符串相同的子串越多，他们就越相似，字符串核函数的值就越大。

7.3.4 非线性支持向量分类机

将线性支持向量机扩展到非线性支持向量机，只需将线性支持向量机对偶形式中的内积换成核函数。

定义 7.8（非线性支持向量机） 从非线性分类训练集，通过核函数与软间隔最大化，或凸二次规划$(7.95)$~$(7.97)$，学习得到的分类决策函数

$f(x) = sign(\sum\limits_{i=1}^{N}\alpha_i^* y_i K(x,x_i) + b^*)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.94)$

称为非线性支持向量机，$K(x,z)$是正定核函数。

算法 7.4 （非线性支持向量机学习算法）

输入：训练数据集$T = \{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\}$，其中，$x_i \in \chi = R^n, y \in \mathcal{Y} = \{+1, -1\}, i=1,2,…,N$；

输出：分类决策函数。

（1）选取适当的核函数$K(x,z)$和适当的参数$C$，构造并求解最优化问题

$\min\limits_{\alpha}\ \ \ \frac{1}{2}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\alpha_i \alpha_j y_i y_j K(x_i,x_j)\ - \ \sum\limits_{i=1}^{N}\alpha_i\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.95)$ $s.t. \ \ \ \ \sum\limits_{i=1}^{N}\alpha_iy_i = 0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.96)$ $0 \leq \alpha_i \leq C,\ \ \ i = 1,2,...,N\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (7.97)$

求得最优解$\alpha^ = (\alpha^_1,\alpha^_2,…,\alpha^_N)^T$。

（2）选择$\alpha^$的一个正分量$0<\alpha_j^ < C$，计算

$b^* = y_j - \sum\limits_{i=1}^{N}\alpha_i^* y_i K(x_i·x_j)$

（3）构造决策函数：

$f(x) = sign(\sum\limits_{i=1}^{N}\alpha_i^* y_i K(x,x_i) + b^*)$

当$K(x,z)$是正定核函数时，问题$(7.95)$~$(7.97)$是凸二次规划问题，解是存在的。

Blog

第七章支持向量机

7.1 线性可分支持向量机与硬间隔最大化

7.1.1 线性可分支持向量机

7.1.2 函数间隔和几何间隔

7.1.3 间隔最大化

7.1.4 学习的对偶算法

7.2 线性支持向量机与软间隔最大化

7.2.1 线性支持向量机

7.2.2 学习的对偶算法

7.2.3 支持向量

7.2.4 合页损失函数

7.3 非线性支持向量机与核函数

7.3.1 核技巧

7.3.2 正定核

7.3.3 常用核函数

7.3.4 非线性支持向量分类机

7.4 序列最小最优化算法