统计学习方法第七章支持向量机（1）——线性可分支持向量机

支持向量机（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）及软间隔最大化，学习一个非线性分类器

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

7.1.1 线性可分支持向量机

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

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

$$w^\star\cdot x+b^\star=0$$

以及相应的分类决策函数
$$f(x)=\text{sign}(w^\star\cdot x+b^\star)$$
称为线性可分支持向量机。

7.1.2 函数间隔和几何间隔

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

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

定义超平面 $(w,b)$ 关于训练数据集 $T$ 的函数间隔为
$$\hat{\gamma}=\min_{i=1,2,\cdots,N}\hat{\gamma}_i$$

函数间隔（functional margin）可以表示分类预测的正确性和确信度，但是具有不确定因子，我们需要对分离超平面的法向量 $w$ 加以约束，使得间隔是确定的。这时函数间隔就成了几何间隔（geometric margin）。

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

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

定义超平面 $(w,b)$ 关于训练数据集 $T$ 的几何间隔为
$$\gamma=\min_{i=1,2,\cdots,N}\gamma_i$$

易知：

$$\gamma_i=\frac{\hat{\gamma}_i}{\|w\|} \\ \gamma=\frac{\hat{\gamma}}{\|w\|}$$

如果超平面参数 $w$ 和 $b$ 成比例变化（超平面没有改变），函数间隔也按此比例变化，几何间隔不变。

7.1.3 间隔最大化

间隔最大化的直观解释：对训练数据集找到几何间隔最大的超平面意味着以充分大的确定度对训练数据进行分类。这样的超平面对未知的新实例有很好的分类预测能力。

最大间隔分离超平面

求解几何间隔最大的分离超平面问题即求解下面的约束最优化问题：

$$\max_{w,b}\ \gamma \\ \text{s.t.}\ \ \ \ y_i\left(\frac{w}{\|w\|}\cdot x_i+\frac{b}{\|w\|}\right)\geq\gamma,\ i=1,2,\cdots,N$$

可改写为：

$$\max_{w,b}\ \frac{\hat{\gamma}}{\|w\|} \\ \text{s.t.}\ \ \ \ y_i\left(w\cdot x_i+b\right)\geq\hat{\gamma},\ i=1,2,\cdots,N$$

对于上式来说，假设将分离超平面 $(w,b)$ 按比例改变为 $(\lambda w,\lambda b)$，这时函数间隔变为 $\lambda \hat{\gamma}$，所以对目标函数和约束条件都没有影响。那么，如果我们做如下变换：

$$(w,b)\to(\frac{1}{\hat{\gamma}}w,\frac{1}{\hat{\gamma}}b)$$

则函数间隔变为 1，故上述问题可改写为：

$$\max_{w,b}\ \frac{1}{\|w\|} \\ \text{s.t.}\ \ \ \ y_i\left(w\cdot x_i+b\right)\geq 1,\ i=1,2,\cdots,N$$

注意到最大化 $\frac{1}{\|w\|}$ 和最小化 $\frac{1}{2}\|w\|^2$ 是等价的，于是问题变为：

$$\min_{w,b}\ \frac{1}{2}\|w\|^2 \\ \text{s.t.}\ \ \ \ y_i\left(w\cdot x_i+b\right)-1\geq0,\ i=1,2,\cdots,N$$

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

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

$$\min_w\ f(w) \\ \text{s.t.}\ \ \ \ \begin{eqnarray} g_i(x) &\leq0&,\ i=1,2\cdots,k \\ h_i(w) &=& 0,\ i=1,2,\cdots,l \end{eqnarray} $$

其中，目标函数 $f(w)$ 和约束函数 $g_i(w)$ 都是 $\mathbb{R}^n$ 上的连续可微凸函数，约束函数 $h_i(w)$ 是 $\mathbb{R}^n$ 上的仿射函数（即满足 $h_i(w)=a\cdot w+b$ 的形式）。

算法 7.1（线性可分支持向量机学习算法——最大间隔法）
输入：线性可分训练数据集 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$，其中 $x_i\in{\cal X}=\mathbb{R}^n$，$y_i\in{\cal Y}=\{+1,-1\}$，$i=1,2,\cdots,N$
输出：最大间隔分离超平面和分类决策函数
(1) 构造并求解约束最优化问题

$$\min_{w,b}\ \frac{1}{2}\|w\|^2 \\ \text{s.t.}\ \ \ \ y_i\left(w\cdot x_i+b\right)-1\geq0,\ i=1,2,\cdots,N$$

求得最优解 $w^\star$，$b^\star$
(2) 由此得到分离超平面
$$w^\star\cdot x+b^\star=0$$
分类决策函数
$$f(x)=\text{sign}(w^\star\cdot x+b^\star)$$

上面的算法就是最大间隔法（maximum margin method）。

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

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

支持向量和间隔边界

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

$$y_i\left(w\cdot x_i+b\right)-1\geq0,\ i=1,2,\cdots,N$$

等号成立的点，即

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

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

$$H_1:\ w\cdot x+b=1$$

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

$$H_2:\ w\cdot x+b=-1$$

上。

支持向量和间隔边界

注意到 $H_1$ 和 $H_2$ 平行，之间的距离称为间隔（margin）。间隔依赖于分离超平面的法向量，等于 $\frac{2}{\|w\|}$，$H_1$ 和 $H_2$ 称为间隔边界。

所有的支持向量都精确的落在边缘上。不管空间的维度有多大，或者数据集合有多大，支持向量的个数一般很少，都可以像 2 个这么小。在决定分离超平面时，只有支持向量起着至关重要的作用，其他的点并不起作用。所以支持向量机是由这些很少的、很“重要的”训练数据决定的。

7.1.4 学习的对偶算法

为了求解线性可分支持向量机的最优化问题

$$\min_{w,b}\ \frac{1}{2}\|w\|^2 \\ \text{s.t.}\ \ \ \ y_i\left(w\cdot x_i+b\right)-1\geq0,\ i=1,2,\cdots,N$$

可以构造对偶问题。这样做的优点，一是对偶问题往往更容易求解；二是自然引入核函数，进而推广到非线性分类问题。

定义拉格朗日函数：

$$L(w,b,\alpha)=\frac{1}{2}\|w\|^2-\sum_{i=1}^N\alpha_iy_i(w\cdot x_i+b)+\sum_{i=1}^N\alpha_i$$

其中，$\alpha_i\geq0$，$\alpha=(\alpha_1,\alpha_2,\cdots,\alpha_N)^\text{T}$ 为拉格朗日乘子向量。

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

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

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

求偏导并令偏导为 0

$$\nabla_wL(w,b,\alpha)=w-\sum_{i=1}^N\alpha_iy_ix_i=0 \\ \nabla_bL(w,b,\alpha)=-\sum_{i=1}^N\alpha_iy_i=0$$

得

$$w=\sum_{i=1}^N\alpha_iy_ix_i \\ \sum_{i=1}^N\alpha_iy_i=0$$

利用上面两式，得

$$L(w,b,\alpha)=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i$$

即

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

$\blacksquare$ 求 $\min_{w,b}L(w,b,\alpha)$ 对 $\alpha$ 的极大

即是求对偶问题

$$\max_\alpha -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i \\ \text{s.t.}\ \ \ \ \begin{eqnarray} \sum_{i=1}^N\alpha_iy_i &=& 0 \\ \alpha_i \geq 0,\ i &=& 1,2,\cdots,N \end{eqnarray}$$

也就是下面等价的最小化问题

$$\min_\alpha \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_i \\ \text{s.t.}\ \ \ \ \begin{eqnarray} \sum_{i=1}^N\alpha_iy_i &=& 0 \\ \alpha_i \geq 0,\ i &=& 1,2,\cdots,N \end{eqnarray}$$

原始最优化问题和对偶最优化问题满足拉格朗日对偶性定理 2 的条件，所以存在 $w^\star$，$b^\star$ 和 $\alpha^\star$ 使 $w^\star$，$b^\star$是原始问题的解，$\alpha^\star$是对偶问题的解。

对线性可分训练数据集，假设对偶最优化问题的解是

$$\alpha^\star=\left(\alpha_1^\star,\alpha_2^\star,\cdots,\alpha_N^\star\right)^\text{T}$$

可以由下面的定理求得 $w^\star$ 和 $b^\star$。

定理 7.2 设 $\alpha^\star=\left(\alpha_1^\star,\alpha_2^\star,\cdots,\alpha_N^\star\right)^\text{T}$ 是对偶最优问题的解，则存在下标 $j$，使得 $\alpha_j^\star>0$，并且可按下式求得原始最优化问题的解

$$w^\star=\sum_{i=1}^N\alpha_i^\star y_ix_i \\ b^\star=y_j-\sum_{i=1}^N\alpha_i^\star y_i(x_i\cdot x_j)$$

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

$$\sum_{i=1}^N\alpha_i^\star y_i(x\cdot x_i)+b^\star=0$$

分类决策函数可以写成

$$f(x)=\text{sign}\left(\sum_{i=1}^N\alpha_i^\star y_i(x\cdot x_i)+b^\star\right)$$

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

算法 7.2（线性可分支持向量机学习算法）
输入：线性可分训练数据集 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$，其中 $x_i\in{\cal X}=\mathbb{R}^n$，$y_i\in{\cal Y}=\{+1,-1\}$，$i=1,2,\cdots,N$
输出：分离超平面和分类决策函数
(1) 构造并求解约束最优化问题

求得最优解 $\alpha^\star=\left(\alpha_1^\star,\alpha_2^\star,\cdots,\alpha_N^\star\right)^\text{T}$
(2) 计算
$$w^\star=\sum_{i=1}^N\alpha_i^\star y_ix_i$$
并选择 $\alpha^\star$ 的一个正分量 $\alpha_j^\star>0$，计算
$$b^\star=y_j-\sum_{i=1}^N\alpha_i^\star y_i(x_i\cdot x_j)$$
(3) 求得分离超平面
$$\sum_{i=1}^N\alpha_i^\star y_i(x\cdot x_i)+b^\star=0$$
分类决策函数
$$f(x)=\text{sign}\left(\sum_{i=1}^N\alpha_i^\star y_i(x\cdot x_i)+b^\star\right)$$

由公式知 $w^\star$，$b^\star$ 只依赖于训练数据中对于与 $\alpha_i^\star>0$ 的样本点 $(x_i,y_i)$，我们将这些实例点称为支持向量。

其中 $b^\ast$ 的计算是根据如下事实：

在最优解 $\alpha^\star=\left(\alpha_1^\star,\alpha_2^\star,\cdots,\alpha_N^\star\right)^\text{T}$ 中，$\alpha_j^\star>0$ 的样本点才是支持向量，而对于支持向量 $(x_j,y_j)$ 来说，其一定位于方程 $y_j(w^\ast\cdot x_j + b)=1$ 上，又因为 $|y_j|=1$，故 $y_j=w^\ast\cdot x_j + b$，得出

$$b^\ast=y_j-w^\ast\cdot x_j=y_j-\sum_{i=1}^N\alpha_i^\star y_i(x_i\cdot x_j)$$

统计学习方法第七章支持向量机（1）——线性可分支持向量机

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

7.1.1 线性可分支持向量机

7.1.2 函数间隔和几何间隔

7.1.3 间隔最大化

最大间隔分离超平面

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

支持向量和间隔边界

7.1.4 学习的对偶算法

发布日期

最后更新

分类

标签

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

7.1.1 线性可分支持向量机

7.1.2 函数间隔和几何间隔

7.1.3 间隔最大化

最大间隔分离超平面

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

支持向量和间隔边界

7.1.4 学习的对偶算法

发布日期

最后更新

分类

标签

7.1.2 函数间隔和几何间隔

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