第六章支持向量机

2022-01-27 本文已影响0人乘瓠散人

间隔与支持向量

给定训练样本集，分类学习最基本的想法就是基于训练集在样本空间中找到一个划分超平面，将不同类别的样本分开。

但是能将不同类别样本分开的划分超平面可能有很多，直观上，我们应该去找“正中间”的划分超平面，也就是对训练样本局部扰动容忍性最好的超平面。

在样本空间中，划分超平面的方程为 $w^Tx+b=0$ ，其中 $w$ 是法向量，决定了超平面的方向； $b$ 是位移，决定了超平面与原点之间的距离。

样本空间中任意点 $x$ 到超平面的距离可写为：
$r=\frac{|w^Tx + b|}{||w||}$
假设超平面能将训练样本正确分类，即对于样本 $(x_i, y_i)\in D$ ，有：
$w^Tx_i + b \geq +1, y_i=+1$
$w^Tx_i + b \leq -1, y_i=-1$
使得不等式等号成立的几个训练样本点被称为支持向量，两个异类支持向量到超平面的距离之和为：
$\gamma = \frac{|+1|}{||w||} + \frac{|-1|}{||w||} = \frac{2}{||w||}$
也被称为间隔(margin)。

支持向量机的目的就是找到具有最大间隔的划分超平面，即公式(1)：
$\max_{w,b} \frac{2}{||w||} \iff \min_{w,b} \frac{1}{2}||w||^2$
$s.t. \ y_i(w^Tx_i + b) \geq 1, i=1,2,...,m$
转化为凸二次规划问题。

进而得到对应的分类模型 $f(x) = w^Tx + b$

支持向量机的重要性质：训练完成后，大部分训练样本都不需要保留，最终模型只与支持向量有关。

对偶问题

对公式(1)运用拉格朗日乘子法可得到其对偶问题:
$\max_{\alpha} \sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{i=1}^m \sum_{j=1}^m\alpha_i \alpha_j y_i y_j x_i^T x_j$
$s.t. \sum_{i=1}^m\alpha_i y_i = 0,$
$\quad \quad \alpha_i\geq 0, i=1,2,...,m$
其中 $\alpha_i$ 为拉格朗日乘子，解出 $\alpha$ 后，求出 $w$ 与 $b$ 即可得到模型：
$f(x) = w^T x + b = \sum_{i=1}^m \alpha_i y_i x_i^T x + b$
注意上述过程需要满足KKT条件。

核函数

前面假设训练样本是线性可分的，即存在一个划分超平面能将训练样本正确分类。然而现实任务中，原始样本空间也许不存在一个能正确分类两类样本的超平面，比如异或问题。

因此，我们考虑将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。
令 $\phi(x)$ 表示将 $x$ 映射后的特征向量，于是，在特征空间中对应的模型表示为：
$f(x) = w^T \phi(x) + b$
其中 $w$ 和 $b$ 是模型参数。
则其对偶问题中需要计算 $\phi(x_i)^T \phi(x_j)$ ，为样本 $x_i$ 和 $x_j$ 映射到特征空间中的内积，由于特征空间维数可能很高，甚至为无穷维，因此直接计算该内积通常很困难。为了避开这个障碍，考虑如下函数：
$\kappa(x_i, x_j) = \phi(x_i)^T \phi(x_j)$
即 $x_i$ 与 $x_j$ 在特征空间中内积等于它们在原始空间中函数 $\kappa(.,.)$ 的计算结果。

最终可得模型为：
$f(x) = w^T\phi(x) + b = \sum_{i=1}^m\alpha_i y_i \kappa(x, x_i) + b$
这里的函数 $\kappa(.,.)$ 就是核函数(kernel function)。

定理(核函数): 令 $X$ 为输入空间， $\kappa(.,.)$ 是定义在 $X\times X$ 上的对称函数，则 $\kappa$ 是核函数当且仅当对于任意数据 $D=\left\{ x_1, x_2, ..., x_m \right\}$ ，核矩阵(kernel matrix)K总是半正定的。

核函数选择成为支持向量机的最大变数，若核函数选择不合适，则意味着将样本映射到了一个不合适的特征空间，很可能导致性能不佳。
常用的核函数有线性核、多项式核、高斯核、拉普拉斯核等。

软间隔与正则化

前面我们一直假定训练样本在原始空间或特征空间是线性可分的，然而，现实任务中往往很难确定合适的核函数使得训练样本在特征空间线性可分；此外，就算恰好找到了某个核函数使得训练集在特征空间中线性可分，也很难断定这个结果不是由于过拟合造成的。

缓解这个问题的一个办法就是允许支持向量机在一些样本上出错。
硬间隔要求所有样本都必须划分正确，而软间隔则允许某些样本不满足约束：
$y_i(w^Tx_i + b)\geq 1$
此时要求在最大化间隔的同时，不满足约束的样本应尽可能少。

优化目标改写为：
$\min_{w,b}\frac{1}{2}||w||^2 + C\sum_{i=1}^m l_{0/1}(y_i(w^Tx_i + b) - 1)$
其中 $C>0$ 是一个常数， $l_{0/1}$ 是0/1损失函数：
$l_{0/1}(z)=1 \ \text{if} \ z<0 \ \text{else} \ 0$
但是0/1损失函数非凸，非连续，数学性质不太好，使得优化目标不易直接求解。人们通常使用其他一些函数来代替，比如hinge损失：
$l_{hinge}(z) = \max(0, 1-z)$

则优化目标变为：
$\min_{w,b}\frac{1}{2}||w||^2 + C\sum_{i=1}^m \max(0, 1-y_i(w^Tx_i + b))$
可看成是正则化的合页(hinge)损失最小化问题。

引入松弛变量 $\xi_i\geq 0$ ，优化目标可进一步重写为：
$\min_{w,b}\frac{1}{2}||w||^2 + C\sum_{i=1}^m \xi_i$
这就是软间隔支持向量机。每个样本都有一个对应的松弛变量，表示该样本不满足约束的程度。与原始目标函数相似，这仍是一个二次规划问题，可通过拉格朗日乘子法求解。

$L_p$ 范数是常用的正则化项，其中 $L_2$ 范数 $||w||_2$ 倾向于 $w$ 的分量取值尽量均衡，即非零分量个数尽量稠密，而 $L_0$ 范数和 $L_1$ 范数则倾向于 $w$ 的分量尽量稀疏，即非零分量个数尽量少。

支持向量机是针对二分类任务设计的，对多分类任务要进行专门的推广[Hsu and Lin, 2002]

支持向量回归

考虑回归问题，即给定训练集 $D=\left \{ (x_1, y_1), (x_2, y_2), ..., (x_m, y_m)) \right \}, y_i\in R$ ，希望学得模型 $f(x)=w^T x + b$ ，使得 $f(x)$ 与 $y$ 尽可能接近。

传统回归模型当且仅当 $f(x)$ 与 $y$ 完全相同时，损失才为0。而支持向量回归(Support Vector Regression, SVR)假设我们能容忍 $\epsilon$ 的偏差，即仅当 $f(x)$ 与 $y$ 之间的差别绝对值大于 $\epsilon$ 时才计算损失。
这相当于以 $f(x)$ 为中心，构建了一个宽度为 $2\epsilon$ 的间隔带，若训练样本落入该间隔带，则被认为是预测正确的。

所以，SVR问题可形式化为：
$\min_{w,b}\frac{1}{2}||w||^2 + C\sum_{i=1}^m l_{\epsilon}(f(x_i) - y_i)$
其中 $C$ 为正则化常数， $l_{\epsilon}$ 是 $\epsilon$ -不敏感损失函数：
$l_{\epsilon}(z) = 0 \ \text{if}\ ||z||\leq \epsilon \ \text{else}\ |z|-\epsilon$