第六章 支持向量机
6.1 间隔与支持向量
- 给定训练样本$D={(x_1,y_1),(x_2,y_2),…,(x_m,y_m)},y_i\in{-1,1}$，分类学习最基本的想法就是基于训练集$D$在样本空间中找到一个划分超平面，将不同类别的样本分开。
- 划分超平面所产生的分类结果应该是最鲁棒的，对未见示例的泛化能力最强。
- 在样本空间中，划分超平面可以通过线性方程描述：$w^Tx+b=0$。
- $w=(w_1;w_2;…,w_d)$为法向量，决定了超平面的方向
- $b$为位移项，决定了超平面与原点之间的距离。
- 样本空间任意点$x$到超平面$(w,b)$的距离可写为：$r=\frac{\mid w^T+b\mid }{\mid \mid w\mid \mid }$
- 假设超平面$(w,b)$能将训练样本正确分类，即对于$(w_i,y_i)\in D$，若$y_i=+1$，则有$w^Tx_i+b>0$；若$y_i=-1$，则有$w^Tx_i+b<0$，令：\(\begin{cases} w^Tx_i+b\geq +1,&{y_i=+1;} \\ w^Tx_i+b\leq-1,&{y_i=-1.} \end{cases}\)
- 距离超平面最近的几个训练样本使上面公式的等号成立，被称为“支持向量”（support vector），两个异类支持向量到超平面的距离之和为：$r=\frac{2}{\mid \mid w\mid \mid }$，被称为间隔（margin）。
- 欲找到具有最大间隔（maximum margin）的划分超平面，也就是找到能满足条件公式中约束的参数$w$和$b$，使得$r$最大，即：\(\mathop{\max}\limits_{w,b}\frac{2}{\mid \mid w\mid \mid }\)。
- 可以等价为：\(\mathop{\min}\limits_{w,b}\frac12{\mid \mid w\mid \mid ^2}\)，$s.t. y_i(w^Tx_i+b)\geq1,i=1,2,…,m$，这就是支持向量机（Support Vector Machine，简称SVM）的基本型。
6.2 对偶问题
- 我们希望求解$\mathop{\min}\limits_{w,b}\frac12{\mid \mid w\mid \mid ^2}$，$s.t. y_i(w^Tx_i+b)\geq1,i=1,2,…,m$来得到最大间隔划分超平面所对应的模型：\(f(x)=w^Tx+b\)，其中$w$和$b$是模型参数。
- 对凸二次规划（convex quadratic programming）问题，能直接用现成的优化计算包求解，还有更高效的办法。
- 对$\mathop{\min}\limits_{w,b}\frac12{\mid \mid w\mid \mid ^2}$，$s.t. y_i(w^Tx_i+b)\geq1,i=1,2,…,m$使用拉格朗日乘子法，可以得到其对偶问题（dual problem）。对上式的每条约束添加拉格朗日乘子$\alpha_i\geq0$，则该问题的拉格朗日函数可写为：
- \(L(w,b,\alpha)=\frac12\mid \mid w\mid \mid ^2+\sum_i^m\alpha_i(1-y_i(w^Tx_i+b))\)，其中$\alpha=(\alpha_1;\alpha_2;…;\alpha_m)$
- 令$L(w,b,\alpha)$对$w$和$b$的偏导为零，可得到：
- $w=\sum_i^m\alpha_iy_ix_i$
- $0=\sum_i^m\alpha_iy_i$
- 将$w$代入$L(w,b,\alpha)$，可以消去$w$和$b$，得到对偶问题：\(\mathop{max}\limits_{\alpha}\sum_i^m\alpha_i-\frac12\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_jx_i^Tx_j\)，
- $s.t. \sum_{i=1}^ma_iy_i=0$,
- $\alpha_i\geq0,i=1,2,…,m.$
- 求解出$\alpha$后，求出$w$和$b$得到模型$f(x)=w^Tx+b=\sum_{i=1}^ma_iy_ix_i^Tx+b$
- 从对偶问题解出的$\alpha_i$是拉格朗日乘子，它对应着训练样本$(x_i,y_i)$，上述过程满足KKT（Karush-Kuhn-Tucker）条件，即：
- \[\begin{cases}\alpha_i\geq0;\\y_if(x_i)-1\geq0;\\\alpha_i(y_if(x_i)-1)=0.\end{cases}\]
- 对任意训练样本$(x_i,y_i)$，总有$\alpha_i=0$或$y_if(x_i)=1$。
- 若$\alpha_i=0$，则该样本将不会在模型公式求和项中出现，不会对$f(x)$有任何影响；
- 若$\alpha_i>0$，则必有$y_if(x_i)=1$，所对应的样本点位于最大间隔边界上，是一个支持向量。
- 求解支持向量机的目标函数是二次规划问题，可以通过二次规划算法求解；然而该问题的规模正比于训练样本，会在实际中造成很大开销。可以采用SMO（Sequential Minimal Optimization）方法。
6.3 核函数
- 现实任务中，原始样本空间内也许并不存在一个能正确划分两类样本的超平面（异或问题就不是线性可分的）。
- 对这样的问题，可以将样本从原始空间映射到更高维的特征空间，使得样本在这个特征空间内线性可分。
- 如果原始空间是有限维，即属性有限，那么一定存在一个高维特征空间使样本可分。
- 令$\phi(x)$表示将$x$映射后的特征向量，欲使特征空间中划分超平面所对应的模型可表示为：$f(x)=w^T\phi(x)+b$，其中$w$和$b$是模型参数，目标函数、对偶问题均与6.2类似，只是将$x$替换为$\phi(x)$。
- 求解对偶问题时，涉及到计算$\phi(x_i)^T\phi(x_j)$，这是样本$x_i$与$x_j$映射到特征空间之后的内积。由于特征空间维数可能很高，甚至可能是无穷维，因此直接计算$\phi(x_i)^T\phi(x_j)$非常困难。
- 为避开这个障碍，可以设想一个函数：$\kappa(x_i,x_j)=\langle\phi(x_i),\phi(x_j)\rangle=\phi(x_i)^T\phi(x_j)$，即$x_i$与$x_j$在特征空间的内积等于它们在原始样本空间中通过函数$\kappa(·,·)$计算的结果。
- 利用这个函数，可以得到：$\begin{cases}\mathop{max}\limits_{\alpha}\sum_i^m\alpha_i-\frac12\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\kappa(x_i,x_j);\{s.t. } \sum_{i=1}^m\alpha_iy_i=0;\{\alpha_i} \geq 0 ,i=1,2,…,m.\end{cases}$
- 求解后得到：$f(x)=w^T\phi(x)+b=\sum_{i=1}^m\alpha_iy_i\phi(x_i)^T\phi(x)+b=\sum_{i=1}^m\alpha_iy_i\kappa(x,x_i)+b$
- $\kappa(·,·)$是核函数（Kernel Function），上式表示模型最优解可以通过训练样本的核函数展开，也称为“支持向量展式”（support vector expansion）
- 若已知合适映射$\phi(·)$的具体形式，则可写出核函数$\kappa(·)$。但是现实任务中，我们通常不知道$\phi(·)$是什么形式。
- 定理6.1（核函数） 令$\chi$为输入空间，$\kappa(·)$是定义在$\chi\times\chi$上的对称函数，则$\kappa$是核函数当且仅当对于任意数据$D={x_1,x_2,…,x_m}$，“核矩阵”（kernel matrix）$K$总是半正定的：$K=\begin{bmatrix}\kappa(x_1,x_1)&\cdots&\kappa(x_1,x_j)&\cdots&\kappa(x_1,x_m)\\vdots&\ddots&\vdots&\ddots&\vdots\\kappa(x_i,x_1)&\cdots&\kappa(x_i,x_j)&\cdots&\kappa(x_i,x_m)\\vdots&\ddots&\vdots&\ddots&\vdots\\kappa(x_m,x_i)&\cdots&\kappa(x_m,x_j)&\cdots&\kappa(x_m,x_m)\end{bmatrix}$
- 定理6.1表明，只要一个对称函数所对应的核矩阵半正定，它就能作为核函数使用。对于一个半正定核矩阵，总能找到一个与之对应的映射$\phi$。
- 任何一个核函数都隐式地定义了一个称为“再生核希尔伯特空间”（Reproducing Kernel Hilbert Space，简称RKHS）的特征空间。
- 核函数选择为支持向量机的最大变数。
- 常用的几种核函数：
- 核函数还可以通过函数组合得到：
- 两个核函数的线性组合也是核函数；
- 核函数的直积也是核函数
- 若$\kappa_1(x,z)$是核函数，则$g(x)\kappa_1(x,z)g(z)$也是核函数。
6.4 软间隔与正则化
- 之前假定训练样本在样本空间或特征空间中线性可分，即存在一个超平面能将不同类的样本完全划分开。
- 现实任务中很难确定合适的核函数使得训练样本在特征空间中线性可分。
- 缓解该问题的办法是允许持之向量机在一些样本上出错。引入“软间隔”（soft margin）
- 软间隔允许某些样不满足约束$y_i(w^Tx_i+b)\geq 1$
- 在最大化间隔的同时，不满足约束的样本应尽可能少。优化目标可以写为：\(\mathop{min}\limits_{w,b}\frac12\mid \mid w\mid \mid ^2+C\sum_{i=1}^ml_{0/1}(y_i(w^Tx_i+b)-1)\)，其中$C>0$是一个常数，$l_{0/1}$是“0/1损失函数”
- $l_{0/1}(z)=\begin{cases}1,&\text{if z<0}; \ {0},&otherwise.\end{cases}$，非凸非连续，数学性质不太好。
- C为无穷大时，所有样本都满足约束$y_i(w^Tx_i+b)\geq 1$；当C取有限值时，允许一些样本不满足约束。
6.5 支持向量回归
-
给定训练样本$D={(x_1,y_1),(x_2,y_2),…,(x_m,y_m)}，y_i\in R$，希望能够学习得到一个回归模型，使得$f(x)$与$y$尽可能接近。
- 对样本$(x,y)$，传统回归模型通常指接基于模型输出$f(x)$与真实输出$y$之间的差别来计算损失。
- 支持向量回归（support vector regression，SVR）假设我们能容忍$f(x)$与$y$之间最多有$\epsilon$的偏差，即仅当$f(x)$与$y$之间的差别的绝对值大于$\epsilon$时才计算损失。这相当于以$f(x)$为中心，构建了一个宽度为$2\epsilon$的间隔带，若训练样本落入此间隔带，则认为是被预测正确的。
-
SVR问题可以形式化为：$\mathop{min}\limits_{w,b}\frac12\mid \mid w\mid \mid ^2+C\sum_{i=1}^ml_\epsilon(f(x_i)-y_i)$，其中$C$为正则化常数，$l_\epsilon$是$\epsilon$-不敏感损失函数($\epsilon$-insensitive loss)：$l_\epsilon(z)=\begin{cases}0,&\text{if }\mid z\mid \leq \epsilon\ {\mid} z{\mid} -\epsilon,&otherwise\end{cases}$
- 引入松弛变量$\xi_i$和$\hat \xi_i$，可以把上式重写为：$\mathop{min}\limits_{w,b,\xi_i,\hat\xi_i}\frac12\mid \mid w\mid \mid ^2+C\sum_{i=1}^m(\xi_i+\hat\xi_i)$
- $s.t.\text{ }f(x_i)-y_i\leq\epsilon+\xi_i\ y_i-f(x_i)\leq\epsilon+\hat\xi_i\ \xi_i\geq0,\hat\xi_i\geq0,i=1,2,…,m$
- 引入拉格朗日乘子，得到拉格朗日函数。
- 最后得到SVR的解形如：$f(x)=\sum_{i=1}^m(\hat\alpha_i-\alpha_i)x_i^Tx+b$
- 能使上式中$(\hat\alpha_i-\alpha_i)\neq0$的样本即为SVR的支持向量，必落在$\epsilon-$间隔带之外。
- SVR的支持向量仅是训练样本的一部分，其解仍具有稀疏性。
6.6 核方法
- 给定训练样本${(x_1,y_1),(x_2,y_2),…,(x_m,y_m)}$，若谷考虑偏移项$b$，无论SVM还是SVR，学得的模型总能表示成核函数$\kappa(x,x_i)$的线性组合。
定理6.2（表示定理）令$H$为核函数$\kappa$对应的再生核希尔伯特空间，$\mid \mid h\mid \mid _H$表示$H$空间中关于$h$的范数，对于任意单调递增函数$\Omega$：$[0,\infty]→ R$和任意非负损失函数$l$：$R^m→[0,\infty]$，优化问题\(\mathop{min}\limits_{h\in H}F(h)=\Omega(\mid \mid h\mid \mid _H)+l(h(x_1),h(x_2),...,h(x_m))\)的解总可写为：\(h^*(x)=\sum_{i=1}^m\alpha_i\kappa(x,x_i)\)
- 表示定理对损失函数没有限制，对正则化项$\Omega$仅要求单调递增。意味着对于一般的损失函数和正则化项，优化问题的最优解都可表示为核函数的线性组合。
- 一系列基于核函数的学习方法，统称为“核方法”（kernel methods）。
- 通过“核化”将线性学习器拓展为非线性学习器
- 通过核化将线性判别进行非线性拓展（Kernelized Linear Discriminant Analysis，KLDA）：
