支持向量机part1

支持向量机(support vector machines,SVM)是一种二类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器(间隔最大使它有别于感知机)。

核技巧使得SVM称为一个非线性分类器。

学习策略是间隔最大化。通过形式化为一个求解凸二次规划的问题。等价于正则化的合页损失函数的最小化问题。

总而言之，支持向量机的学习算法是求解凸二次规划的最优化算法。

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

1. 线性可分支持向量机(硬间隔)

   当训练数据线性可分时，通过硬间隔最大化，学习一个线性的分类器，即线性可分支持向量机，又称为硬间隔支持向量机。

2. 线性支持向量机(软间隔)

   当训练数据近似线性可分时，通过软间隔最大化，学习一个线性的分类器，即线性支持向量机，又称为软间隔支持向量机。

3. 非线性支持向量机(核技巧SVM)

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

   当输入空间为欧式空间或离散集合，特征空间为希尔伯特空间时，核函数表示将输入从输入空间映射到特征空间得到的特征向量之间的内积。

   通过使用核函数来学习非线性支持向量机，等价于隐式地在高维的特征空间中学习线性支持向量机。

核技巧是比支持向量机更为一般的机器学习方法。

支持向量机的学习是在特征空间进行的。

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

8.1.1 线性可分支持向量机

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

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

其中，$x_i \in \mathcal{X}=\mathbb{R}^n$，$y_i \in \mathcal{Y}=\{+1,-1\},i=1,2,...,N$，$x_i$为第i个特征向量，也称为实例，$y_i$为$x_i$的类标记，当$y_i=+1$时，称$x_i$为正例；当$y_i=-1$时，称$x_i$为负例。$(x_i,y_i)$为样本点。

假设训练数据集是线性可分的。

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

一般地，当训练数据集线性可分时，存在无穷个分离超平面可将两类数据正确分类。

对于感知机利用误分类最小的策略，求解的分离超平面，有无数个解。

对于线性可分支持向量机利用间隔最大化策略，求解最优的分离超平面，解是唯一的。

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

$$w^{*}.x+b^{*} = 0 \ (8.1)$$

以及相应的分类决策函数:

$$f(x) = \mathrm{sign}(w^{*}.x+b^{*}) \ (8.2)$$

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

8.1.2 函数间隔和几何间隔

定义8.2(函数间隔) 对于给定的训练数据集T和超平面(w,b)，定义超平面(w,b)关于样本点$(x_i,y_i)$的函数间隔为

$$\hat{\gamma}_i = y_i(w.x_i+b) \ (8.3)$$

定义超平面(w,b)关于训练数据集T的函数间隔为超平面(w,b)关于T中所有样本点$(x_i,y_i)$的函数间隔之最小值，即

$$\hat{\gamma} = \min_{i=1,...,N} \hat{\gamma_i} \ (8.4)$$

函数间隔可以表示为分类预测的正确性及确信度。

但是，如果成比例地改变w，b(如w->2w,b->2b)，超平面并没有改变，但是函数间隔却变成了原来的两倍。为了解决这个问题，我们可以对分离超平面的法向量w加某些约束，如规范化，$\|w\|=1$。使得间隔是确定的。这时函数间隔成为几何间隔。

定义8.3(几何间隔)对于给定的训练数据集T和超平面(w,b)，定义超平面(w,b)关于样本点$(x_i,y_i)$的几何间隔为:

$$\gamma_i = y_i \left(\frac{w}{\|w\|}.x_i+\frac{b}{\|w\|}\right) \ (8.5)$$

定义超平面(w,b)关于训练数据集T的几何间隔为超平面(w,b)关于T中所有样本点$(x_i,y_i)$的几何间隔之最小值，即:

$$\gamma = \min_{i=1,...,N} \gamma_i \ (8.6)$$

根据函数间隔和几何间隔的定义可知，如果$\|w\|=1$，函数间隔与几何间隔相等。

8.1.3硬间隔最大化

对于线性可分的训练数据集而言，硬间隔最大化的直观解释是:对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。

1. 最大间隔分离超平面

   求最大间隔分离超平面问题可以表示为下面的约束最优化问题:

   $$\max_{w,b} \gamma \tag{8.9}$$ $$\mathrm{s.t.} y_i\left(\frac{w}{\|w\|}.x_i+\frac{b}{\|w\|}\right) \ge \gamma , i=1,2,...,N \tag{8.10}$$

根据几何间隔与函数间隔的关系，上面的约束最优化问题可以改写成一下形式:

$$\max_{w,b} \frac{\hat{\gamma}}{\|w\|} \tag{8.11}$$ $$\mathrm{s.t.} y_i(w.x_i+b)\ge \hat{\gamma} ,i=1,2,...,N \tag{8.12}$$

事实上，假设将w和b按比例改变为$\lambda w$和$\lambda b$，这时函数间隔成为$\lambda \hat{\gamma}$，由此可以看出函数间隔的这一改变对上面最优化问题的不等式约束没有影响，对目标函数的优化也没有影响。也就是说，$\hat{\gamma}$=1，也对不等式约束没有影响。同时，最大化$\frac{1}{\|w\|}$和最小化$\frac{1}{2}\|w\|^2$是等价的。

综上所述，可将上面的最优化问题进一步的调整成如下形式:

$$\min_{w,b} \frac{1}{2}\|w\|^2 \tag{8.13}$$ $$\mathrm{s.t.} y_i(w.x_i+b)-1\ge 0 , i=1,2,...,N \tag{8.14}$$

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

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

$$\min_w f(w) \tag{8.15}$$ $$\mathrm{s.t.} g_i(w) \le 0 i=1,2,...,K \tag{8.16}$$ $$h_i(w)=0 i=1,2,...,l\tag{8.17}$$

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

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

算法8.1(线性可分支持向量机学习算法——最大间隔法)

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

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

(1)构造并求解约束最优化问题:

$$\min_{w,b} \frac{1}{2}\|w\|^2$$ $$\mathrm{s.t.} y_i(w.x_i+b)-1\ge 0 , i=1,2,...,N$$

求得最优解$w^*,b^*$。

(2)由此得到分离超平面:

$$w^*.x+b^*=0$$

分类决策函数:

$$f(x) = \mathrm{sign}(w^*.x+b^*)$$

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

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

   证明:

   (1)存在性

   • 训练数据集线性可分=>存在可行解
   • 目标函数有下界=>必有解

   (2)唯一性

   假设问题(8.13)(8.14)存在两个最优解$(w_1^*,b_1^*)$和$(w_2^*,b_2^*)$。显然$\|w_1^*\|=\|w_2^*\|=c$，其中c是一个常数。

   令$w = \frac{w_1^*+w_2^*}{2}$，$b=\frac{b_1^*+b_2^*}{2}$，易知(w,b)是问题(8.13)(8.14)的可行解(满足约束条件)。从而有:

   $$c \le \|w\| \le \frac{1}{2}\|w_1^*\|+\frac{1}{2}\|w_2^*\|=c$$

   分解：

   对于$c\le \|w\|$ 是因为目标函数求得得解为$\min \|w\|$，所以对于其他非最优解，其二范数必然大于c。

   根据w的定义，可以得到$\|w\| \le \frac{1}{2}\|w_1^*\|+\frac{1}{2}\|w_2^*\|$

上式表明，式中的不等号可变为等号，即$\|w\| = \frac{1}{2}\|w_1^*\|+\frac{1}{2}\|w_2^*\| \ (0)$，由式(0)以及w取值表达式，可以得到$w_1^*.w_2^*=\|w_1^*\|\|w_2^*\|$，从而有$w_1^* = \lambda w_2^*$(两个向量共线,模相等，因此$\lambda=\pm 1$)，则有以下两种情况:

• $\lambda=-1$，则w=0，而(0,b)不是问题(8.13)(8.14)的可行解。

• $$\lambda=1,w_1^*=w_2^*$$

w的唯一性得证。

接下来，证明b的唯一性:

设$x_1^{'}$和$x_2^{'}$是集合$\{x_i|y_i=+1\}$中分别对应于$(w^*,b_1^*)$和$(w^*,b_2^*)$使得问题的不等式等号成立的点。$x^{''}_1$和$x_2^{''}$是集合$\{x_i|y_i=-1\}$中分别对应于$(w^*,b_1^*)$和$(w^*,b_2^*)$使得问题的不等式等号成立的点。

由$b_1^*=-\frac{1}{2}(w^*.x_1^{'}+w^*.x_1^{''})$，$b_2^*=-\frac{1}{2}(w^*.x_2^{'}+w^*.x_2^{''})$，得

$$b_1^*-b_2^* = -\frac{1}{2}[w^*.(x_1^{'}-x_2^{'})+w^*.(x_1^{''}-x_2^{''})]$$

又因为:

$$w^*.x_2^{'}+b_1^* \ge 1=w^*.x_1^{'}+b_1^*$$ $$w^*.x_1^{'}+b_2^* \ge 1 = w^*.x_2^{'}+b_2^*$$

所以，$w^*.(x_1^{'}-x_2^{'})=0$。同理有$w^{*}.(x_1^{''}-x_2^{''})=0$。因此，

$$b_1^*-b_2^* = 0$$

由$w_1^*=w_2^*$和$b_1^*=b_2^*$可知，两个最优解$(w_1^*,b_1^*)$和$(w_2^*,b_2^*)$是相同的，解的唯一性得证。

(3)分离超平面能将训练数据集集中的两类点完全正确地分开

由解满足问题的约束条件即可得知。

1. 支持向量和间隔边界

   定义(支持向量)支持向量是使约束条件式(8.14)等号成立的点，即

   $$y_i(w.x_i+b)-1=0$$

   

如上图所示，$H_1,H_2$超平面上的样本点为支持向量。而$H_1$和$H_2$之间的距离称为间隔(margin)。间隔依赖于分离超平面的法向量w，等于$\frac{2}{\|w\|}$，$H_1$和$H_2$称为间隔边界。

在决定分离超平面时，只有支持向量起作用，而其他实例点并不起作用。如果移动支持向量将改变所求的解。

8.1.4 学习的对偶算法

线性可分支持向量机的最优化问题(8.13)(8.14)为原始最优化问题，应用拉格朗日乘子得到对偶问题，通过求解对偶问题得到原始问题的最优解，这就是线性可分支持向量机的对偶算法。

这样做的优点:

1. 对偶问题往往更容易求解
2. 自然引入核函数

首先构建拉格朗日函数，为此，对每个不等式约束(8.14)引进拉格朗日乘子$\alpha_i \ge 0$，i=1,2,…,N，定义拉格朗日函数:

$$\begin{aligned}L(w,b,\alpha) &=\frac{1}{2}\|w\|^2 - \sum_{i=1}^N \alpha_i (y_i(w.x_i+b)-1)\\&= \frac{1}{2}\|w\|^2 - \sum_{i=1}^N \alpha_i y_i(w.x_i+b)+\sum_{i=1}^N \alpha_i\end{aligned} \ (8.18)$$

原始问题定义为:

$$\min_{w,b} \max_{\alpha} L(w,b,\alpha)$$

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

$$\max_{\alpha} \min_{w,b} L(w,b,\alpha)$$

所以，对偶问题的求解步骤为，先求对w,b的极小，再求对$\alpha$的极大。

(1)求$\min_{w,b}L(w,b,\alpha)$

将拉格朗日函数$L(w,b,\alpha)$分别对w,b求偏导数并令其等于0.

$$\begin{aligned}\nabla_w L(w,b,\alpha) = &w - \sum_{i=1}^N \alpha_i y_i x_i = 0 \\ \nabla_b L(w,b,\alpha) = &-\sum_{i=1}^N \alpha_i y_i = 0\end{aligned}$$

得

$$w = \sum_{i=1}^N \alpha_i y_i x_i \ (8.19)$$ $$\sum_{i=1}^N \alpha_i y_i = 0 \ (8.20)$$

将式(8.19)代入拉格朗日函数(8.18)，并利用式(8.20)，即得：

$$\begin{aligned}L(w,b,\alpha) &= \frac{1}{2}\sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_iy_j(x_i.x_j)-\sum_{i=1}^N \alpha_iy_i \left(\left(\sum_{j=1}^N \alpha_jy_jx_j\right).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_iy_j(x_i.x_j)+\sum_{i=1}^N \alpha_i \end{aligned}$$

即

$$\min_{w,b} L(w,b,\alpha) = -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i.x_j)+\sum_{i=1}^N \alpha_i$$

(2)求$\min_{w,b}L(w,b,\alpha)$对$\alpha$的极大，即是对偶问题:

$$\max_{\alpha} -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_iy_j(x_i.x_j)+\sum_{i=1}^N \alpha_i \tag{8.21} \\$$ $$\mathrm{s.t.} \sum_{i=1}^N \alpha_i y_i = 0$$ $$\alpha_i \ge 0，i=1,2,...,N$$

将式(8.21)的目标函数由求极大转成求极小，就得到下面与之等价的对偶最优化问题:

$$\min_{\alpha} \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j(x_i.x_j) - \sum_{i=1}^N \alpha_i \tag{8.22}$$ $$\mathrm{s.t.} \sum_{i=1}^N \alpha_i y_i = 0 \tag{8.23}$$ $$\alpha_i \ge 0 , i=1,2,...,N \tag{8.24}$$

原始问题满足KKT条件，所以存在$w^*$，$\alpha^*$，使$w^*$是原始问题的解，$\alpha^*$是对偶问题的解。这意味着求解原始问题(8.13)~(8.14)可以转换为求解对偶问题(8.22)~(8.24)。

定理8.2 设$\alpha^{*} = (\alpha_1^*,\alpha_2^{*},...,\alpha_l^{*})^{\top}$是对偶最优化问题(8.22)~(8.24)的解，则存在下标j，使得$\alpha_j^{*} > 0$，并可按下式求得原始最优化问题(8.13)~(8.14)的解$w^{*}$,$b^{*}$:

$$w^{*} = \sum_{i=1}^N \alpha_i^* y_i x_i \ (8.25)$$ $$b^{*} = y_j - \sum_{i=1}^N \alpha_i^{*}y_i(x_i.x_j) \ (8.26)$$

证明：按照KKT条件成立，即得：

$$\nabla_w L(w^*,b^*,\alpha^*) = w^* - \sum_{i=1}^N \alpha_i^* y_i x_i = 0 \ (8.27)$$ $$\nabla_b L(w^*,b^*,\alpha^*) = -\sum_{i=1}^N \alpha_i^* y_i = 0$$ $$\alpha_i^* (y_i(w^*.x_i+b^*)-1) = 0 , i=1,2,...,N$$ $$y_i(w^*.x_i+b^*)-1 \ge 0 , i=1,2,...,N$$ $$\alpha_i^* \ge 0 , i=1,2,...,N$$

由此得:

$$w^* = \sum_{i} \alpha_i^* y_i x_i$$

其中至少有一个$\alpha_j^* > 0$(用反证法，假设$\alpha^*=0$，由式(8.27)可知$w^*=0$，而$w^*=0$不是原始最优化问题(8.13)~(8.14)的解，产生矛盾)，对此j有:

$$y_j (w^*.x_j + b^*)-1 = 0 \ (8.28)$$

将式(8.25)代入式(8.28)并注意到$y_j^2 = 1$，即得：

$$b^* = y_j - \sum_{i=1}^N \alpha_i^* y_i(x_i.x_j)$$

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

$$\sum_{i=1}^N \alpha_i^* y_i (x.x_i)+b^* = 0 \ (8.29)$$

分类决策函数可以写成：

$$f(x) = \mathrm{sign} \left(\sum_{i=1}^N \alpha_i^* y_i (x.x_i)+b^* \right) \ (8.30)$$

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

算法8.2(线性可分支持向量机学习算法):

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

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

(1)构造并求解约束最优化问题

$$\min_{\alpha} \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i.x_j) - \sum_{i=1}^N \alpha_i$$ $$\mathrm{s.t.} \sum_{i=1}^N \alpha_i y_i =0$$ $$\alpha_i \ge 0，i=1,2,...,N$$

求得最优解$\alpha^* = (\alpha_1^*,\alpha_2^*,...,\alpha_N^*)^{\top}$。

(2)计算

$$w^* = \sum_{i=1}^N \alpha_i^* y_i x_i$$

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

$$b^* = y_j - \sum_{i=1}^N \alpha_i^* y_i (x_i.x_j)$$

(3)求得分离超平面

$$w^*.x+b^* = 0$$

分类决策函数:

$$f(x) = \mathrm{sign}(w^*.x+b^*)$$

在线性可分支持向量机中，由式(8.25)、式(8.26)可知，$w^*$和$b^*$只依赖于训练数据中对应于$\alpha_i^* > 0$的样本点$(x_i,y_i)$，而其他样本点对$w^*$和$b^*$没有影响。

我们将训练数据中对应于$\alpha_i^{*}>0$的实例点$x_i \in R^n$称为支持向量。

定义8.4(支持向量)考虑原始最优化问题(8.13)~(8.14)及对偶最优化问题(8.22)~(8.24)，将训练数据集中对应于$\alpha_i^{*} > 0$的样本点$(x_i,y_i)$的实例$x_i \in R^n$称为支持向量。

根据这一定义，支持向量一定在间隔边界上，由KKT互补条件可知，

$$\alpha_i^*(y_i(w^*.x_i+b^*)-1)=0 \ , i=1,2,...,N$$

对应于$\alpha_j^* > 0$的实例$x_i$，有：

$$y_i(w^*.x_i+b^*)-1 = 0$$

或

$$w^*.x_i + b^* = \pm 1$$

即$x_i$一定在间隔边界上。这里的支持向量的定义与前面给出的支持向量的定义是一致的。

对于线性可分问题，上述线性可分支持向量机的学习(硬间隔最大化)算法是完美的。

但是，在现实问题中，训练数据集往往是线性不可分的，即在样本中出现噪声或离群点，此时，有更一般的学习算法。

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

8.2.1 线性支持向量机

线性可分支持向量机学习算法的局限性：对线性不可分训练数据是不适用的，因为这时上述方法中的不等式约束并不能都成立。

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

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

其中，$x_i \in \mathcal{X} = R^n$，$y_i \in \mathcal{Y} = \{-1,+1\}$，i=1,2,…,N，$x_i$为第i个特征向量，$y_i$为$x_i$的类标记。

再假设训练数据集不是线性可分的。通常情况是训练数据中有一些特异点(outlier)，将这些特异点除去后剩下大部分的样本点组成的集合是线性可分的。

线性不可分意味着某些样本点$(x_i,y_i)$不能满足函数间隔大于等于1的约束条件(8.14)。

解决方案:为了解决这个问题，可以对每个样本点$(x_i,y_i)$引进一个松弛变量$\xi \ge 0$，使得函数间隔加上松弛变量大于等于1(满足不等式约束条件)。这样，约束条件变为:

$$y_i(w.x_i+b) \ge 1-\xi_i$$

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

$$\frac{1}{2} \|w\|^2 + C \sum_{i=1}^N \xi_i \ (8.31)$$

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

相应于硬间隔最大化，它称为软间隔最大化。

线性不可分的线性支持向量机的学习问题变成如下凸二次规划问题(原始问题)：

$$\min_{w,b,\xi} \frac{1}{2} \|w\|^2 + C \sum_{i=1}^N \xi_i \tag{8.32}$$ $$\mathrm{s.t.} y_i(w.x_i+b) \ge 1-\xi_i，i=1,2,...,N \tag{8.33}$$ $$\xi_i \ge 0，i=1,2,...,N \tag{8.34}$$

原始问题(8.32)~(8.34)是一个凸二次规划问题，因而关于$(w,b,\xi)$的解是存在的。可以证明w的解是唯一的，但b的解可能不唯一，而是存在于一个区间(参考《邓乃扬，田英杰。数据挖掘中的新方法——支持向量机。北京:科学出版社，2004》)。

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

$$w^*.x + b^* = 0 \ (8.35)$$

以及相应的分类决策函数:

$$f(x) = \mathrm{sign}(w^*.x + b^*) (8.36)$$

称为线性支持向量机。

8.2.2 学习的对偶算法

此章节主要是演算如何通过原始问题推出对偶问题，从而证明原始问题与对偶问题是等价的。

在对偶问题中，原始问题中引入的辅助变量$\xi$，已经消去。

原始问题(8.32)~(8.34)的对偶问题是:

$$\min_{\alpha} \frac{1}{2}\sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j(x_i.x_j)-\sum_{i=1}^N \alpha_i \tag{8.37}$$ $$\mathrm{s.t.} \sum_{i=1}^N \alpha_i y_i = 0 \tag{8.38}$$ $$0 \le \alpha_i \le C，i=1,2,...,N \tag{8.39}$$

由此，可得对应的拉格朗日函数为:

$$L(w,b,\xi,\alpha,\mu) = \frac{1}{2} \|w\|^2 + C \sum_{i=1}^N \xi_i-\sum_{i=1}^N \alpha_i(y_i(w.x_i+b)-1+\xi_i) - \sum_{i=1}^N \mu_i \xi_i \ (8.40)$$

其中，$\alpha_i \ge 0,\mu_i \ge 0$。

对对偶问题进行求解:

(1)首先求$L(w,b,\xi,\alpha,\mu)$对w,b,$\xi$的极小，由:

$$\nabla_w L(w,b,\xi,\alpha,\mu) = w-\sum_{i=1}^N \alpha_i y_i x_i = 0$$ $$\nabla_b L(w,b,\xi,\alpha,\mu) = -\sum_{i=1}^N \alpha_i y_i = 0$$ $$\nabla_{\xi_i} L(w,b,\xi,\alpha,\mu) = C-\alpha_i-\mu_i = 0$$

得

$$w = \sum_{i=1}^N \alpha_i y_i x_i \ (8.41)$$ $$\sum_{i=1}^N \alpha_i y_i = 0 \ (8.42)$$ $$C-\alpha_i - \mu_i = 0 \ (8.43)$$

将式(8.41)~(8.43)代入式(8.40)，得:

$$\min_{w,b,\xi} L(w,b,\xi,\alpha,\mu) = -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i.x_j)+\sum_{i=1}^N \alpha_i$$

(2)再对$\min_{w,b,\xi} L(w,b,\xi,\alpha,\mu)$求$\alpha$的极大，即得对偶问题:

$$\max_{\alpha} - \frac{1}{2}\sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j(x_i.x_j)+\sum_{i=1}^N \alpha_i \tag{8.44}$$ $$\mathrm{s.t.} \sum_{i=1}^N \alpha_i y_i = 0 \tag{8.45}$$ $$C - \alpha_i -\mu_i =0 \tag{8.46}$$ $$\alpha_i \ge 0 \tag{8.47}$$ $$\mu_i \ge 0，i=1,2,...,N \tag{8.48}$$

将对偶最优化问题(8.44)~(8.48)进行变换:利用等式约束(8.46)消去$\mu_i$，从而只留下变量$\alpha_i$，并将约束(8.46)~(8.48)写成：

$$0 \le \alpha_i \le C \ (8.49)$$

将对目标函数求极大转换为求极小，于是得到对偶问题(8.37)~(8.39)。

定理8.3设$\alpha^{*}=(\alpha_1^*,\alpha_2^*,...,\alpha_N^*)^{\top}$是对偶问题(8.37)~(8.39)的一个解，若存在$\alpha^*$的一个分量$\alpha_j^*$，$0<\alpha_j^*<C$，则原始问题(8.32)~(8.34)的解$w^{*}$，$b^*$可按下式求得:

$$w^{*} = \sum_{i=1}^N \alpha_i^* y_i x_i \ (8.50)$$ $$b^* = y_j - \sum_{i=1}^N y_i \alpha_i^*(x_i.x_j) \ (8.51)$$

证明:原始问题是凸二次规划问题，解满足KKT条件。即得：

$$\nabla_wL(w^{*},b^{*},\xi^*,\alpha^*,\mu^*) = w^*-\sum_{i=1}^N \alpha_i^* y_i x_i = 0 \ (8.52)$$ $$\nabla_b L(w^*,b^*,\xi^*,\alpha^*,\mu^*) = -\sum_{i=1}^N \alpha_i^* y_i = 0$$ $$\nabla_{\xi} L(w^*,b^*,\xi^*,\alpha^*,\mu^*) = C-\alpha^*-\mu^* = 0$$ $$\alpha_i^* (y_i(w^*.x_i + b^*)-1+\xi^*_i) = 0 \ (8.53)$$ $$\mu_i^* \xi^*_i = 0 \ (8.54)$$ $$y_i(w^*.x_i+b^*)-1+\xi^*_i \ge 0$$ $$\xi_i^* \ge 0$$ $$\alpha_i^* \ge 0$$ $$\mu_i^* \ge 0 , i=1,2,...,N$$

由式(8.52)易知式(8.50)成立。

由式(8.53)~(8.54)可知，若存在$\alpha_j^*$，$0 < \alpha_j^* < C$，则$y_i(w^*.x_i+b^*)-1=0$。由此即得式(8.51)。

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

$$\sum_{i=1}^N \alpha_i^* y_i (x.x_i)+b^* = 0 \ (8.55)$$

分类决策函数可以写成:

$$f(x) = \mathrm{sign} \left(\sum_{i=1}^N \alpha_i^* y_i(x.x_i)+b^* \right) \ (8.56)$$

式(8.56)为线性支持向量机的对偶形式。

算法8.3 (线性支持向量机学习算法)

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

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

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

$$\min_{\alpha} \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i.x_j) - \sum_{i=1}^N \alpha_i$$ $$\mathrm{s.t.} \sum_{i=1}^N \alpha_i y_i = 0$$ $$0 \le \alpha_i \le C , i=1,2,...,N$$

求得最优解$\alpha^* = (\alpha_1^*,\alpha_2^*,...,\alpha_N^*)^{\top}$。

(2)计算$w^* = \sum_{i=1}^N \alpha_i^* y_i x_i$

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

$$b^* = y_j - \sum_{i=1}^N y_i \alpha_i^*(x_i.x_j)$$

(3)求得分离超平面

$$w^*.x+b^* = 0$$

分类决策函数:

$$f(x) = \mathrm{sign}(w^*.x+b^*)$$

步骤(2)中，对任一适合条件$0<\alpha_j^* <C$的$\alpha_j^*$，按式(8.51)都可求出$b^*$，从理论上，原始问题(8.32)~(8.34)对b的解可能不唯一，然而在实际应用中，往往只会出现算法叙述的情况。

8.2.3 支持向量

在线性不可分的情况下，将对偶问题(8.37)~(8.39)的解$\alpha^* = (\alpha_1^*,\alpha_2^*,...,\alpha_N^*)^{\top}$中对应于$\alpha_i^* > 0$的样本点$(x_i,y_i)$的实例$x_i$称为支持向量(软间隔的支持向量)。

如下图所示，分离超平面由实线表示，间隔边界由虚线表示，正例点由”。”表示，负例点由”x”表示。图中还标出了实例$x_i$到间隔边界的距离$\frac{\xi_i}{\|w\|}$。

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

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

8.2.4 合页损失函数

对应线性支持向量机学习来说，(1)模型为分离超平面$w^*.x+b^*=0$及决策函数$f(x) = \mathrm{sign}(w^*.x+b^*)$，(2)学习策略为软间隔最大化，学习算法为凸二次规划。

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

$$\sum_{i=1}^N [1-y_i(w.x_i+b)]_{+}+\lambda \|w\|^2 \ (8.57)$$

目标函数的第一项是经验损失或经验风险，函数

$$L(y(w.x+b)) = [1-y(w.x+b)]_{+} \ (8.58)$$

称为合页损失函数。下标”+”表示以下取正值的函数。

$$[z]_+ = \left\{\begin{aligned}z, &z>0 \\ 0, &z\le 0\end{aligned} \right . \ (8.59)$$

也就是说，当样本点$(x_i,y_i)$被正确分类且函数间隔(确信度)$y_i(w.x_i+b)$大于1时，损失是0；否则损失是$1-y_i(w.x_i+b)$。

目标函数的第二项是系数为$\lambda$的w的$L_2$范数，是正则化项。

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

$$\min_{w,b,\xi} \frac{1}{2}\|w\|^2 + C \sum_{i=1}^N \xi_i \tag{8.60}$$ $$\mathrm{s.t.} y_i(w.x_i+b) \ge 1-\xi_i ，i=1,2,...,N \tag{8.61}$$ $$\xi_i \ge 0，i=1,2,...,N \tag{8.62}$$

等价于最优化问题:

$$\min_{w,b} \sum_{i=1}^N [1-y_i(w.x_i+b)]_+ + \lambda \|w\|^2 \tag{8.63}$$

证明：可将最优化问题(8.63)写成问题(8.60)~(8.62)。令

$$[1-y_i(w.x_i+b)]_+ = \xi_i \ (8.64)$$

则$\xi_i \ge 0$，式(8.62)成立。

由式(8.64)可得：

1. 当$1-y_i(w.x_i+b) > 0$时，有$y_i(w.x_i+b)=1-\xi_i$
2. 当$1-y_i(w.x_i+b) \le 0$时，$\xi_i = 0$，有$y_i(w.x_i+b) \ge 1-\xi_i$。

综上所述，式(8.61)成立。

于是，w,b,$\xi_i$满足约束条件(8.61)~(8.62)。所以最优化问题(8.63)可写成:

$$\min_{w,b} \sum_{i=1}^N \xi_i + \lambda \|w\|^2$$

若取$\lambda = \frac{1}{2C}$，则：

$$\min_{w,b} \frac{1}{C} \left(\frac{1}{2}\|w\|^2+C\sum_{i=1}^N \xi_i \right)$$

与式(8.60)等价。

反之，也可将最优化问题(8.60)~(8.62)表示成问题(8.63)。

合页损失函数的图形如图8.6所示，

图中一共有三种损失函数，

• 0-1损失函数，对于正确分类的样例(即y(w.x+b)>0)，损失为0,而错误分类的样例(即y(w.x+b)<0)，损失为1。
• 感知机损失函数$[-y_i(w.x_i+b)]_+$，当样本点被正确分类时(y(w.x+b)>=0)，损失为0，而错误分类的样例[y(w.x+b)<0]，损失为$-y_i(w.x_i+b)$。
• 合页损失函数，比感知机损失函数更加严格，当样本点被正确分类且函数间隔必须大于1的时候(即y(w.x+b)>1)，损失为0，而错误分类的样例(y(w.x+b)<=1)，损失为1-y(w.x+b)。

总结

线性可分支持向量机与线性支持向量机的目标函数的区别在于：线性支持向量机多了一个约束条件$\alpha_i \le C$。

$C$为线性支持向量机中的惩罚系数：

• C值大时，对误分类的惩罚增大(对应着限制变大)
• C值小时，对误分类的惩罚减小