支持向量机

支持向量机（support vector machine, SVM）是一种用于分类、回归和异常检测的有监督学习方法。按照数据集的特点，可分为3类：

  1. 当数据集线性可分时，通过硬间隔最大化（不容许错误分类），学习线性可分支持向量机，又叫硬间隔支持向量机（hard-margin SVM）
  2. 当数据集近似线性可分时，通过软间隔最大化（容许一定误差），学习线性支持向量机（linear SVM），又叫软间隔支持向量机（soft-margin SVM）
  3. 当数据集线性不可分时，通过核技巧（kernel method）及软间隔最大化，学习非线性支持向量机（non-linear SVM）

给定的数据集

D={(x1,y1),(x2,y2),⋯ ,(xN,yN}D=\{(\mathbf x_1,y_1),(\mathbf x_2,y_2),\cdots,(\mathbf x_N,y_N\}

包含 NN 个样本，pp 个特征。其中，第 ii 个样本的特征向量为 xi=(xi1,xi2,⋯ ,xip)T\mathbf x_i=(x_{i1},x_{i2},\cdots,x_{ip})^T 。目标变量 yi∈{−1,+1}y_i\in\{-1,+1\} 。

间隔最大化

本节讨论线性可分的数据集，即存在无数超平面，可以将正样本和负样本正确分类。从几何角度，具有最大间隔的超平面有更好的泛化性能，因为该超平面对训练样本局部扰动的容忍性最好。SVM 采用最大间隔超平面（maximal margin hyperplane）作为决策边界，此时的超平面是存在且唯一的。

分离的超平面可以写为如下形式

wTx+b=0\mathbf{w}^T\mathbf{x}+b=0

其中 w=(w1,w2,⋯ ,wp)T\mathbf w=(w_1,w_2,\cdots,w_p)^T 为法向量，决定了超平面的方向；bb 为位移项，决定了超平面与原点之间的距离。显然，超平面可被法向量 w\mathbf w 和位移 bb 确定，下面我们将其记为 (w,b)(\mathbf w,b) 。

Model：

fw,b(x)=sign(wTx+b)f_{\mathbf{w},b}(\mathbf{x})=\text{sign}(\mathbf{w}^T\mathbf{x}+b)

符号函数

sign(z)={+1if z⩾0−1if z<0\text{sign}(z)=\begin{cases}+1 & \text{if }z\geqslant 0\\ -1 & \text{if }z<0\end{cases}

最大间隔：

距离超平面 (w,b)(\mathbf w,b) 最近的样本，被称为支持向量 （support vector）。如上图，设超平面两侧平行边界的方程分别为

B1:wTx+b=γB2:wTx+b=−γ\begin{aligned} B_1: & \mathbf{w}^T\mathbf{x}+b=\gamma \\ B_2: & \mathbf{w}^T\mathbf{x}+b=-\gamma \end{aligned}

超平面 B1,B2B_1,B_2 间的距离称为间隔（margin）

margin=2γ∥w∥\text{margin}=\frac{2\gamma}{\|\mathbf w\|}

假设样本能被超平面正确分类，则

{wTxi+b⩾γif yi=+1wTxi+b⩽−γif yi=−1\begin{cases} \mathbf{w}^T\mathbf{x}_i+b\geqslant \gamma & \text{if }y_i=+1\\ \mathbf{w}^T\mathbf{x}_i+b\leqslant- \gamma & \text{if }y_i=-1 \end{cases}

可简写为

yi(wTxi+b)⩾γi=1,2,⋯ ,Ny_i(\mathbf{w}^T\mathbf{x}_i+b)\geqslant \gamma \quad i=1,2,\cdots,N

参数估计：由于超平面的系数经过同比例缩放不会改变这个平面，我们不妨给出约束 γ=1\gamma=1，从而得到唯一系数。那么最大化间隔可表示为：

max⁡w,b2∥w∥s.t.yi(wTxi+b)⩾1,i=1,2,⋯ ,N\begin{aligned} \max\limits_{\mathbf w,b}&\frac{2}{\|\mathbf w\|} \\ \text{s.t.}&\quad y_i(\mathbf{w}^T\mathbf{x}_i+b)\geqslant 1, \quad i=1,2,\cdots,N \end{aligned}

s.t. 是 subject to (such that) 的缩写，表示约束条件。约束为分类任务的要求。

显然，为了最大化间隔，仅需最大化 ∥w∥−1\|\mathbf w\|^{-1}，这等价于最小化 ∥w∥2\|\mathbf w\|^2 。于是上式可重写为

min⁡w,b12∥w∥2s.t.yi(wTxi+b)⩾1,i=1,2,⋯ ,N\begin{aligned} \min\limits_{\mathbf w,b}&\frac{1}{2}\|\mathbf w\|^2 \\ \text{s.t.}&\quad y_i(\mathbf{w}^T\mathbf{x}_i+b)\geqslant 1, \quad i=1,2,\cdots,N \end{aligned}

这就是 SVM 的基本形式，是一个包含 NN 个约束的凸优化问题。

对偶问题

支持向量机通常将原始问题（primal problem）转化成拉格朗日对偶问题（dual problem）来求解。首先引入 Lagrange 函数

L(w,b,α)=12wTw+∑i=1Nαi(1−yi(wTxi+b))L(\mathbf w,b,\mathbf\alpha)=\frac{1}{2}\mathbf w^T\mathbf w+\sum_{i=1}^N\alpha_i(1-y_i(\mathbf{w}^T\mathbf{x}_i+b))

参数 αi⩾0\alpha_i\geqslant 0 称为拉格朗日乘子（Lagrange multiplier）。根据拉格朗日对偶性，原始问题的对偶问题为

max⁡αmin⁡w,bL(w,b,α)\max_{\mathbf\alpha}\min_{\mathbf w,b}L(\mathbf w,b,\mathbf\alpha)

令 L(w,b,α)L(\mathbf w,b,\mathbf\alpha) 对 w\mathbf w 和 bb 的偏导数为 0 可以得到

∑i=1Nαiyi=0w=∑i=1Nαiyixi\sum_{i=1}^N\alpha_iy_i=0\\ \mathbf w=\sum_{i=1}^N\alpha_iy_i\mathbf x_i

将上式带入拉格朗日函数，我们就可以消去 w\mathbf w 和 bb ，得到对偶最优化问题

max⁡α∑i=1Nαi−12∑i=1N∑j=1NαiαjyiyjxiTxjs.t.∑i=1Nαiyi=0αi⩾0,i=1,2,⋯ ,N\begin{aligned} \max\limits_{\mathbf\alpha}&\sum_{i=1}^N\alpha_i-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j\mathbf x_i^T\mathbf x_j \\ \text{s.t.}&\quad \sum_{i=1}^N\alpha_iy_i=0 \\ &\quad\alpha_i\geqslant 0, \quad i=1,2,\cdots,N \end{aligned}

原问题和对偶问题等价的充要条件为其满足 KKT（Karush-Kuhn-Tucker）条件

{αi⩾01−yi(wTxi+b)⩽0αi(1−yi(wTxi+b))=0\begin{cases} \alpha_i\geqslant 0 \\ 1-y_i(\mathbf{w}^T\mathbf{x}_i+b) \leqslant 0 \\ \alpha_i(1-y_i(\mathbf{w}^T\mathbf{x}_i+b))=0 \end{cases}

解出 α\mathbf\alpha 后，求出 w\mathbf w 和 bb 即可得到模型

fw,b(x)=sign(wTx+b)=sign(∑i=1NαiyixiTx+b)\begin{aligned} f_{\mathbf{w},b}(\mathbf{x})&=\text{sign}(\mathbf{w}^T\mathbf{x}+b) \\ &=\text{sign}(\sum_{i=1}^N\alpha_iy_i\mathbf x_i^T\mathbf x+b) \end{aligned}

由 KKT 互补条件可知，对任意训练样本 (xi,yi)(\mathbf x_i,y_i)， 总有 αi=0\alpha_i=0 或 yi(wTxi+b)=1y_i(\mathbf{w}^T\mathbf{x}_i+b)=1。

  • 若 αi=0\alpha_i=0 ，则该样本将不会在式 fw,b(x)f_{\mathbf{w},b}(\mathbf{x}) 的求和中出现，也就不会对模型有任何影响
  • 若 αi>0\alpha_i>0，则必有 yi(wTxi+b)=1y_i(\mathbf{w}^T\mathbf{x}_i+b)=1 ，所对应的样本点位于最大间隔边界上，被称为支持向量。这显示出 SVM 的一个重要性质：训练完成后，大部分的训练样本都不需保留，最终模型仅与支持向量有关。

不难发现，求解 α\mathbf\alpha 是一个二次规划问题，可使用通用的二次规划算法来求解。然而，该问题的规模正比于训练样本数，这会在实际任务中造成很大的开销。为了避开这个障碍，人们通过利用问题本身的特性，提出了很多高效算法， SMO (Sequential Minimal Optimization) 是其中典型代表。

软间隔与正则化

在前面的讨论中，假定训练样本是线性可分的，即所有样本都必须严格满足约束

yi(wTxi+b)⩾1y_i(\mathbf{w}^T\mathbf{x}_i+b)\geqslant 1

这称为硬间隔（hard margin）。然而，现实任务中的数据很难线性可分，这时，我们为每个样本引入松弛变量（slack variable） ξi>0\xi_i>0 ，允许某些样本不满足约束，约束条件修改为

yi(wTxi+b)⩾1−ξiy_i(\mathbf{w}^T\mathbf{x}_i+b)\geqslant 1-\xi_i

使用软间隔（soft margin）最大化求解。

当然，在最大化间隔的同时，不满足约束的样本应尽可能少。于是，引入损失

ξi=max⁡{0,1−yi(wTxi+b)}\xi_i=\max\{0,1-y_i(\mathbf{w}^T\mathbf{x}_i+b)\}

每个样本都有一个对应的松弛变量， 用以表征该样本不满足严格约束的程度。上式称为hinge损失函数

hinge_loss(z)=max⁡{0,1−z}\text{hinge\_loss}(z)=\max\{0,1-z\}

因此，软间隔SVM的优化目标可写为

min⁡w,b,ξ12∥w∥2+C∑i=1Nξis.t.yi(wTxi+b)⩾1−ξiξi⩾0,i=1,2,⋯ ,N\begin{aligned} \min\limits_{\mathbf w,b,\mathbf\xi}&\frac{1}{2}\|\mathbf w\|^2+C\sum_{i=1}^N\xi_i \\ \text{s.t.}&\quad y_i(\mathbf{w}^T\mathbf{x}_i+b)\geqslant 1-\xi_i \\ &\quad \xi_i\geqslant 0, \qquad i=1,2,\cdots,N \end{aligned}

其中，CC 为惩罚参数，用于控制惩罚强度。这便是线性 SVM 的基本式。

原始问题的拉格朗日函数为

L(w,b,ξ,α,η)=12wTw+C∑i=1Nξi+∑i=1Nαi(1−ξi−yi(wTxi+b))−∑i=1NηiξiL(\mathbf w,b,\mathbf\xi,\mathbf\alpha,\mathbf\eta)=\frac{1}{2}\mathbf w^T\mathbf w+C\sum_{i=1}^N\xi_i+\sum_{i=1}^N\alpha_i(1-\xi_i-y_i(\mathbf{w}^T\mathbf{x}_i+b))-\sum_{i=1}^N\eta_i\xi_i

参数 αi⩾0,ηi\alpha_i\geqslant 0,\eta_i 称为拉格朗日乘子。令 L(w,b,ξ,α,η)L(\mathbf w,b,\mathbf\xi,\mathbf\alpha,\mathbf\eta) 对 w,b\mathbf w,b 和 ξ\mathbf \xi 的偏导数为 0 可以得到

∑i=1Nαiyi=0w=∑i=1Nαiyixiαi+ηi=C\sum_{i=1}^N\alpha_iy_i=0\\ \mathbf w=\sum_{i=1}^N\alpha_iy_i\mathbf x_i \\ \alpha_i+\eta_i=C

将上式带入拉格朗日函数，得到拉格朗日对偶问题

max⁡α∑i=1Nαi−12∑i=1N∑j=1NαiαjyiyjxiTxjs.t.∑i=1Nαiyi=00⩽αi⩽C,i=1,2,⋯ ,N\begin{aligned} \max\limits_{\mathbf\alpha}&\sum_{i=1}^N\alpha_i-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j\mathbf x_i^T\mathbf x_j \\ \text{s.t.}&\quad \sum_{i=1}^N\alpha_iy_i=0 \\ &\quad 0\leqslant\alpha_i\leqslant C, \quad i=1,2,\cdots,N \end{aligned}

上式与线性可分对偶问题唯一不同的是对 αi\alpha_i 的约束。对软间隔支持向量机， KKT 条件要求

{αi⩾0,ηi⩾01−ξi−yi(wTxi+b)⩽0αi(1−ξi−yi(wTxi+b))=0ξi⩾0,ηiξi=0\begin{cases} \alpha_i\geqslant 0 ,\quad \eta_i \geqslant 0 \\ 1-\xi_i-y_i(\mathbf{w}^T\mathbf{x}_i+b)\leqslant 0 \\ \alpha_i(1-\xi_i-y_i(\mathbf{w}^T\mathbf{x}_i+b))=0 \\ \xi_i\geqslant 0 ,\quad \eta_i\xi_i=0 \end{cases}

解出 α,η\mathbf\alpha,\mathbf\eta 后，求出 w\mathbf w 和 bb 即可得到模型

fw,b(x)=sign(wTx+b)=sign(∑i=1NαiyixiTx+b)\begin{aligned} f_{\mathbf{w},b}(\mathbf{x})&=\text{sign}(\mathbf{w}^T\mathbf{x}+b) \\ &=\text{sign}(\sum_{i=1}^N\alpha_iy_i\mathbf x_i^T\mathbf x+b) \end{aligned}

由 KKT 条件可知，对任意训练样本 (xi,yi)(\mathbf x_i,y_i)， 总有 αi=0\alpha_i=0 或 yi(wTxi+b)=1−ξiy_i(\mathbf{w}^T\mathbf{x}_i+b)=1-\xi_i。

  • 若 αi=0\alpha_i=0 ，则该样本将不会在式 fw,b(x)f_{\mathbf{w},b}(\mathbf{x}) 的求和中出现，也就不会对模型有任何影响
  • 若 αi>0\alpha_i>0，则必有 yi(wTxi+b)=1−ξiy_i(\mathbf{w}^T\mathbf{x}_i+b)=1-\xi_i ，该样本为支持向量
  • 若 αi<C\alpha_i<C，则 ηi>0\eta_i>0，进而有 ξi=0\xi_i=0 ，即该样本恰在最大间隔边界上
  • 若 αi=C\alpha_i=C，则有 ηi=0\eta_i=0，此时若 ξi⩽1\xi_i\leqslant 1 则该样本落在最大间隔内部，若 ξi>1\xi_i>1 则该样本被错误分类

由此可看出，软间隔支持向量机的最终模型仅与支持向量有关，即通过采用hinge 损失函数仍保持了稀疏性。

核方法

现实任务中，原始样本空间内也许并不存在一个能正确划分两类样本的超平面。对这样的问题，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。如下图，异或问题就不能线性可分

可证明，如果原始空间是有限维， 即属性数有限，那么一定存在一个高维特征空间使样本可分。

令 ϕ(x)\mathbf{\phi(x)} 表示将 x\mathbf x 映射后的特征向量，于是，在特征空间中划分超平面所对应的模型可表示为

fw,b(x)=sign(wTϕ(x)+b)f_{\mathbf{w},b}(\mathbf{x})=\text{sign}(\mathbf{w}^T\mathbf{\phi(x)}+b)

那么最大化间隔可表示为

min⁡w,b12∥w∥2+C∑i=1Nξis.t.yi(wTϕ(xi)+b)⩾1−ξiξi⩾0,i=1,2,⋯ ,N\begin{aligned} \min\limits_{\mathbf w,b}&\frac{1}{2}\|\mathbf w\|^2+C\sum_{i=1}^N\xi_i \\ \text{s.t.}&\quad y_i(\mathbf{w}^T\mathbf\phi(\mathbf x_i)+b)\geqslant 1-\xi_i \\ &\quad \xi_i\geqslant 0, \qquad i=1,2,\cdots,N \end{aligned}

其对偶问题是

max⁡α∑i=1Nαi−12∑i=1N∑j=1Nαiαjyiyjϕ(xi)Tϕ(xj)s.t.∑i=1Nαiyi=00⩽αi⩽C,i=1,2,⋯ ,N\begin{aligned} \max\limits_{\mathbf\alpha}&\sum_{i=1}^N\alpha_i-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j\mathbf\phi(\mathbf x_i)^T\mathbf\phi(\mathbf x_j) \\ \text{s.t.}&\quad \sum_{i=1}^N\alpha_iy_i=0 \\ &\quad 0\leqslant\alpha_i\leqslant C, \quad i=1,2,\cdots,N \end{aligned}

求解上述问题涉及到计算 ϕ(xi)Tϕ(xj)\mathbf\phi(\mathbf x_i)^T\mathbf\phi(\mathbf x_j)， 这是样本 xi\mathbf x_i 与 xj\mathbf x_j 映射到特征空间之后的内积。由于特征空间维数可能很高，甚至可能是无穷维，因此直接计算 ϕ(xi)Tϕ(xj)\mathbf\phi(\mathbf x_i)^T\mathbf\phi(\mathbf x_j) 通常是困难的。为了避开这个障碍，引入核函数（kernel function）

K(x1,x2)=ϕ(x1)Tϕ(x2)K(\mathbf x_1,\mathbf x_2)=\mathbf\phi(\mathbf x_1)^T\mathbf\phi(\mathbf x_2)

即 xi\mathbf x_i 与 xj\mathbf x_j 在特征空间的内积等于它们在原始样本空间中通过核函数计算的结果，这称为核技巧（kernel trick）。核函数 KK 的实现方法通常有比直接构建 ϕ(x)\mathbf\phi(\mathbf x) 再算点积高效很多。

于是，对偶问题可重写为

max⁡α∑i=1Nαi−12∑i=1N∑j=1NαiαjyiyjK(xi,xj)s.t.∑i=1Nαiyi=00⩽αi⩽C,i=1,2,⋯ ,N\begin{aligned} \max\limits_{\mathbf\alpha}&\sum_{i=1}^N\alpha_i-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j K(\mathbf x_i,\mathbf x_j) \\ \text{s.t.}&\quad \sum_{i=1}^N\alpha_iy_i=0 \\ &\quad 0\leqslant\alpha_i\leqslant C, \quad i=1,2,\cdots,N \end{aligned}

可写为矩阵形式

min⁡α12αTQα−eTαs.t.yTα=00⩽αi⩽C,i=1,2,⋯ ,N\begin{aligned} \min\limits_{\mathbf\alpha}&\frac{1}{2}\mathbf\alpha^T\mathbf Q\mathbf\alpha-\mathbf e^T\mathbf\alpha \\ \text{s.t.}&\quad \mathbf y^T\mathbf\alpha=0 \\ &\quad 0\leqslant\alpha_i\leqslant C, \quad i=1,2,\cdots,N \end{aligned}

其中，e\mathbf e 是一个全1的 NN 维向量，Q\mathbf Q 是一个 N×NN\times N 的半正定矩阵，Qij=yiyjK(xi,xj)Q_{ij}=y_iy_j K(\mathbf x_i,\mathbf x_j)。

求解后即可得到

fw,b(x)=sign(wTϕ(x)+b)=sign(∑i=1NαiyiK(xi,x)+b)\begin{aligned} f_{\mathbf{w},b}(\mathbf{x})&=\text{sign}(\mathbf{w}^T\mathbf{\phi(x)}+b) \\ &=\text{sign}(\sum_{i=1}^N\alpha_iy_iK(\mathbf x_i,\mathbf x)+b) \end{aligned}

通过前面的讨论可知，我们希望样本在特征空间内线性可分，因此特征空间的好坏对支持向量机的性能至关重要。需注意的是，在不知道特征映射的形式时，我们并不知道什么样的核函数是合适的，而核函数也仅是隐式地定义了
这个特征空间。于是，"核函数选择"成为支持向量机的最大变数，若核函数选择不合适，则意味着将样本映射到了一个不合适的特征空间，很可能导致性能不佳。

下面介绍几种常用的核函数

(1) 线性核函数（linear kernel function）

K(x1,x2)=x1Tx2K(\mathbf x_1,\mathbf x_2)=\mathbf x_1^T\mathbf x_2

(2) 多项式核函数（polynomial kernel function）

K(x1,x2)=(x1Tx2+1)pK(\mathbf x_1,\mathbf x_2)=(\mathbf x_1^T\mathbf x_2+1)^p

(3) 高斯核函数（Gaussian kernel function）：也被称为径向基函数（radial basis function, RBF），是最常用的核函数。σ>0\sigma>0 为高斯核的带宽（width）。

K(x1,x2)=exp⁡(∥x1−x2∥22σ2)K(\mathbf x_1,\mathbf x_2)=\exp(\frac{\|\mathbf x_1-\mathbf x_2\|^2}{2\sigma^2})

(4) 拉普拉斯核函数（Laplace kernel function）

K(x1,x2)=exp⁡(∥x1−x2∥2σ2)K(\mathbf x_1,\mathbf x_2)=\exp(\frac{\|\mathbf x_1-\mathbf x_2\|}{2\sigma^2})

(5) Sigmoid 核函数（Sigmoid kernel function）

K(x1,x2)=tanh⁡(βx1Tx2+θ)K(\mathbf x_1,\mathbf x_2)=\tanh(\beta\mathbf x_1^T\mathbf x_2+\theta)

支持向量回归

支持向量分类方法可以推广到解决回归问题，这种方法称为支持向量回归（Support Vector Regression，SVR）。

给定的数据集

D={(x1,y1),(x2,y2),⋯ ,(xN,yN}D=\{(\mathbf x_1,y_1),(\mathbf x_2,y_2),\cdots,(\mathbf x_N,y_N\}

包含 NN 个样本，pp 个特征。其中，第 ii 个样本的特征向量为 xi=(xi1,xi2,⋯ ,xip)T\mathbf x_i=(x_{i1},x_{i2},\cdots,x_{ip})^T 。目标变量 yi∈Ry_i\in\R 。

Model：相比于线性回归用一条线来拟合训练样本， SVR采用一个以 f(x)f(\mathbf x) 为中心，宽度为 2ϵ2\epsilon 的间隔带，来拟合训练样本。预测函数仍为

fw,b(x)=wTϕ(x)+bf_{\mathbf{w},b}(\mathbf{x})=\mathbf{w}^T\mathbf\phi(\mathbf x)+b

落在带子内的样本不计算损失，不在带子内的样本则以偏离的程度作为损失，然后以最小化损失的方式迫使间隔带从样本最密集的地方（中心地带）穿过，进而达到拟合训练样本的目的。

为适应每个样本，引入松弛变量

ξi=max⁡{0,∣wTϕ(xi)+b−yi∣−ϵ}\xi_i=\max\{0,|\mathbf{w}^T\mathbf\phi(\mathbf x_i)+b-y_i|-\epsilon\}

并将 ξi⩾0\xi_i\geqslant 0 作为惩罚项加入优化，惩罚那些偏离 ϵ\epsilon 带的样本，ξi\xi_i 表示样本远离带的程度。

因此SVR的优化问题可以写为

min⁡w,b12∥w∥2+C∑i=1Nξis.t.−ϵ−ξi⩽wTϕ(xi)+b⩽ϵ+ξiξi⩾0,i=1,2,⋯ ,N\begin{aligned} \min\limits_{\mathbf w,b}&\frac{1}{2}\|\mathbf w\|^2+C\sum_{i=1}^N\xi_i \\ \text{s.t.}&\quad -\epsilon-\xi_i \leqslant \mathbf{w}^T\mathbf\phi(\mathbf x_i)+b\leqslant \epsilon+\xi_i \\ &\quad \xi_i\geqslant 0, \qquad i=1,2,\cdots,N \end{aligned}

注释：

  • 当样本在带内时，一定满足约束条件，因此代价函数中惩罚项取最小值 ξi=0\xi_i=0
  • 当样本在带外时，为满足样本位置和惩罚项最小值，约束条件则变为 ∣wTϕ(xi)+b∣=ϵ+ξi|\mathbf{w}^T\mathbf\phi(\mathbf x_i)+b|=\epsilon+\xi_i

这里我们使用了ϵ-不敏感损失函数（epsilon-insensitive）, 即小于ϵ的误差被忽略了。

lossϵ(z)−=max⁡{0,∣z∣−ϵ}\text{loss}_\epsilon(z)-=\max\{0,|z|-\epsilon\}

在这里不用均方误差的目的是为了和软间隔支持向量机的优化目标保持形式上的一致，这样就可以导出对偶问题引入核函数

如果考虑两边采用不同的松弛程度，可重写为

min⁡w,b12∥w∥2+C∑i=1N(ξi+ξi′)s.t.−ϵ−ξi′⩽wTϕ(xi)+b⩽ϵ+ξiξi⩾0,ξi′⩾0,i=1,2,⋯ ,N\begin{aligned} \min\limits_{\mathbf w,b}&\frac{1}{2}\|\mathbf w\|^2+C\sum_{i=1}^N(\xi_i+\xi_i') \\ \text{s.t.}&\quad -\epsilon-\xi_i' \leqslant \mathbf{w}^T\mathbf\phi(\mathbf x_i)+b\leqslant \epsilon+\xi_i \\ &\quad \xi_i\geqslant 0,\xi_i'\geqslant 0, \qquad i=1,2,\cdots,N \end{aligned}

对偶问题为

max⁡α,α′∑i=1Nyi(αi′−αi)−ϵ(αi′+αi)−12∑i=1N∑j=1N(αi′−αi)(αj′−αj)K(xi,xj)s.t.∑i=1N(αi′−αi)=00⩽αi,αi′⩽C,i=1,2,⋯ ,N\begin{aligned} \max\limits_{\mathbf\alpha,\mathbf\alpha'}&\sum_{i=1}^Ny_i(\alpha_i'-\alpha_i)-\epsilon(\alpha_i'+\alpha_i) \\ &-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N(\alpha_i'-\alpha_i)(\alpha_j'-\alpha_j)K(\mathbf x_i,\mathbf x_j) \\ \text{s.t.}&\quad \sum_{i=1}^N(\alpha_i'-\alpha_i)=0 \\ &\quad 0\leqslant\alpha_i,\alpha_i'\leqslant C, \quad i=1,2,\cdots,N \end{aligned}

可写为矩阵形式

min⁡α,α′12(α−α′)TQ(α−α′)+ϵeT(α+α′)−yT(α−α′)s.t.eT(α−α′)=00⩽αi,αi′⩽C,i=1,2,⋯ ,N\begin{aligned} \min\limits_{\mathbf\alpha,\mathbf\alpha'}&\frac{1}{2}(\mathbf\alpha-\mathbf\alpha')^T\mathbf Q(\mathbf\alpha-\mathbf\alpha')+\epsilon\mathbf e^T(\mathbf\alpha+\mathbf\alpha')-\mathbf y^T(\mathbf\alpha-\mathbf\alpha') \\ \text{s.t.}&\quad \mathbf e^T(\mathbf\alpha-\mathbf\alpha')=0 \\ &\quad 0\leqslant\alpha_i,\alpha_i'\leqslant C, \quad i=1,2,\cdots,N \end{aligned}

其中，e\mathbf e 是一个全1的 NN 维向量，Q\mathbf Q 是一个 N×NN\times N 的半正定矩阵，Qij=K(xi,xj)Q_{ij}=K(\mathbf x_i,\mathbf x_j)。

上述过程中需满足KKT 条件，即要求

{αi(wTϕ(xi)+b−yi−ϵ−ξi)=0αi′(yi−wTϕ(xi)−b−ϵ−ξi′)=0αiαi′=0,ξiξi′=0(C−αi)ξi=0,(C−αi′)ξi′=0\begin{cases} \alpha_i(\mathbf{w}^T\mathbf\phi(\mathbf x_i)+b-y_i-\epsilon-\xi_i)=0 \\ \alpha_i'(y_i-\mathbf{w}^T\mathbf\phi(\mathbf x_i)-b-\epsilon-\xi_i')=0 \\ \alpha_i\alpha_i'=0 ,\quad \xi_i\xi_i'=0 \\ (C-\alpha_i)\xi_i=0 ,\quad (C-\alpha_i')\xi_i'=0 \end{cases}

可以看出

  • 当且仅当 wTϕ(xi)+b−yi−ϵ−ξi=0\mathbf{w}^T\mathbf\phi(\mathbf x_i)+b-y_i-\epsilon-\xi_i=0 时，αi\alpha_i 能取非零值
  • 当且仅当 yi−wTϕ(xi)−b−ϵ−ξi′=0y_i-\mathbf{w}^T\mathbf\phi(\mathbf x_i)-b-\epsilon-\xi_i'=0 时，αi′\alpha_i' 能取非零值

换言之，仅当样本不落入间隔带中，相应的 αi\alpha_i 和 αi′\alpha_i' 才能取非零值。

  • 此外，约束 wTϕ(xi)+b−yi−ϵ−ξi=0\mathbf{w}^T\mathbf\phi(\mathbf x_i)+b-y_i-\epsilon-\xi_i=0 和 yi−wTϕ(xi)−b−ϵ−ξi′=0y_i-\mathbf{w}^T\mathbf\phi(\mathbf x_i)-b-\epsilon-\xi_i'=0 不能同时成立，因此 αi\alpha_i 和 αi′\alpha_i' 中至少有一个为零。

预测函数为

fw,b(x)=∑i=1N(αi−αi′)K(xi,x)+bf_{\mathbf{w},b}(\mathbf{x})=\sum_{i=1}^N(\alpha_i-\alpha_i')K(\mathbf x_i,\mathbf x)+b

能使上式中的 αi−αi′≠0\alpha_i-\alpha_i'\neq 0 的样本即为 SVR 的支持向量，它们必落在 ϵ\epsilon 间隔带之外。显然，SVR 的支持向量仅是训练样本的一部分，即其解仍具有稀疏性。

附录

超平面几何

超平面方程为

wTx+b=0\mathbf{w}^T\mathbf{x}+b=0

其中 x=(x1,x2,⋯ ,xp)T\mathbf x=(x_1,x_2,\cdots,x_p)^T ，w=(w1,w2,⋯ ,wp)T\mathbf w=(w_1,w_2,\cdots,w_p)^T 。

超平面的方程不唯一，同比例缩放 w,b\mathbf w,b ，仍是同一个超平面。若缩放倍数为负数，会改变法向量方向。

法向量：取超平面上任意两点 x1,x2\mathbf x_1,\mathbf x_2 ，则

wTx1+b=0wTx2+b=0\mathbf{w}^T\mathbf{x}_1+b=0 \\ \mathbf{w}^T\mathbf{x}_2+b=0

上面两式相减可得

wT(x1−x2)=w⋅(x1−x2)=0\mathbf{w}^T(\mathbf{x}_1-\mathbf{x}_2)=\mathbf{w}\cdot(\mathbf{x}_1-\mathbf{x}_2)=0

即向量 w\mathbf w 与超平面垂直，所以超平面 wTx+b=0\mathbf{w}^T\mathbf{x}+b=0 的法向量为 w\mathbf w 。

任意点到超平面的距离：取超平面外任意一点 x\mathbf x ，在超平面上的投影为 x1\mathbf x_1 ，距离为 d>0d>0 ，则

w⋅x1+b=0w⋅(x−x1)=∥w∥⋅d\mathbf{w}\cdot\mathbf{x}_1+b=0 \\ \mathbf{w}\cdot(\mathbf{x}-\mathbf{x}_1)=\|\mathbf w\|\cdot d

因此 x\mathbf x 到超平面距离

d=∣wTx+b∣∥w∥d=\frac{|\mathbf{w}^T\mathbf{x}+b|}{\|\mathbf w\|}