统计学习方法笔记08

李航. 统计学习方法[M]. 清华大学出版社, 2012.

第7章支持向量机

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

感知机利用误分类最小的策略，求得分离超平面，这时的解有无穷多个；线性可分支持向量机利用间隔最大化求分离超平面，解是唯一的。

函数间隔的定义

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

$\hat{\gamma_i}=y_i(\omega\cdot x_i+b)$

定义超平面关于数据集T的函数间隔为超平面关于T中所有样本点的函数间隔之最小值，即

$\hat{\gamma}=\min_{i=1,\dots,N}\hat{\gamma_i}$

几何间隔的定义

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

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

定义超平面关于数据集T的几何间隔为超平面关于T中所有样本点的几何间隔之最小值，即

$\gamma = \min_{i=1,\dots,N} \gamma_i$

线性可分支持向量机学习的最优化问题：(令函数间隔 $\hat{\gamma}=1$ )

$\begin{aligned}& \min_{\omega} \dfrac{1}{2} ||\omega||^2 \\& \text{s.t.} \quad y_i(\omega\cdot x_i+b)-1\geq 0， i=1,2,\dots,N\end{aligned}$

求解上述最优化问题的解 $(\omega^*,b^*)$ ，即可得到最大间隔分离超平面 $\omega^*\cdot x+b^*=0$ 和分类决策函数 $f(x)=sign(\omega^*\cdot x+b^*)$ 。

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

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

在线性可分的情况下，训练数据集的样本点中与分离超平面最近的样本点的实例称为支持向量(support vector)。支持向量是满足 $y_i(\omega\cdot x_i+b)-1=0$ 的点。

正例点与负例点中的支持向量所在的两个超平面之间的距离称为间隔(margin)。间隔依赖于分离超平面的法向量，等于 $\dfrac{2}{||\omega||}$ 。

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

输入：线性可分训练集 $T=\{(x_i,y_i)\}$ ，其中 $x_i\in\mathbb{R}^n$ ， $y_i\in\{-1,+1\}$ ， $i=1,\dots,N$

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

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

$\begin{aligned}\min_{\alpha} \quad & \dfrac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j(x_i\cdot x_j) - \sum_{i=1}^N \alpha_i \\\text{s.t.} \quad & \sum_{i=1}^N \alpha_i y_i = 0 \\& \alpha_i \geq 0, i=1,2,\dots,N\end{aligned}$

(2) 计算 $\omega^*=\sum_{i=1}^N \alpha_i^* y_ix_i$ ，并选择 $\alpha^*$ 的一个正分量 $\alpha_j^* > 0$ ，计算

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

(3) 求得分离超平面 $\omega^*\cdot x+b^*=0$ 和分类决策函数 $f(x)=sign(\omega^*\cdot x+b^*)$ 。

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

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

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

$\begin{aligned}\min_{\omega,b,\xi} \quad & \dfrac{1}{2}||\omega||^2 + C\sum_{i=1}^N \xi_i \\\text{s.t.} \quad & y_i(\omega\cdot x_i+b) \geq 1-\xi_i ,\quad i=1,2,\dots,N \\& \xi_i\geq 0, \quad i=1,2,\dots,N\end{aligned}$

线性支持向量机

对于给定的线性不可分的训练数据集，通过求解上述凸二次规划问题，得到的分离超平面为 $\omega^*\cdot x+b^*=0$ 以及相应的分类决策函数 $f(x)=sign(\omega^*\cdot x+b^*)$ 称为线性支持向量机。

对偶问题及其解

线性不可分凸二次规划问题的对偶问题是：

$\begin{equation}\begin{aligned}\min_{\alpha} \quad & \dfrac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j(x_i\cdot x_j) - \sum_{i=1}^N \alpha_i \\\text{s.t.} \quad & \sum_{i=1}^N \alpha_i y_i = 0 \\& 0 \leq \alpha_i \leq C, i=1,2,\dots,N\end{aligned}\end{equation}$