支持向量机

狼啸风云

发布于 2022-09-28 19:52:37

5940

发布于 2022-09-28 19:52:37

文章被收录于专栏：计算机视觉理论及其实现计算机视觉理论及其实现

1、间隔与支持向量

给定训练样本集

\large D=\{ (x_1,y_1), (x_1,y_1),...,(x_m,y_m) \}

，

，分类学习最基本的想法就是基于训练集D在样本空间中找到一个划分超平面可能有很多。直观上看，应该去找位于两类训练样本“正中间”的划分超平面，因为该划分超平面对训练样本局部扰动的“容忍性”最好。例如由于训练集的局限性或噪声的因素，训练集外的样本可能比训练样本更接近两个类的分隔界，这将使许多划分朝平面出现错误，而红色的超平面受影响最小。换言之，这个划分超平面所产生的分类结果是最鲁棒的，对未见示例的泛化能力最强。

在样本空间中，划分超平面可能通过如下线性方程来描述：

(1)

其中

为法向量，决定了超平面的方向；b为位移项，决定了超平面与原点之间的距离。显然，划分超平面可被法向量w和位移b确定，下面我们将其记为(w,b)。样本空间中任意点x到超平面(w,b)的距离可写为：

(2)

假设超平面(w, b)能将训练样本正确分类，即对于

，若

，则有

；若

，则有

，令

\large \left\{\begin{matrix} w^Tx_i + b \geqslant +1 &,y_i=+1 \\ w^Tx_i + b \leqslant -1 &,y_i=-1 & \end{matrix}\right.

(3)

距离超平面最近的这几个训练样本点使式(3)的等号成立，它们被称为“支持向量”(support vector)，两个异类支持向量到超平面的距离之和为

(4)

它被称为“间隔”(margin)。

欲找到具有“最大间隔”(maximum margin)的划分超平面，也就要找到满足式(3)的约束参数w和b，使得

最大，即

\large max_{w,b}\frac{2}{||w||}\\ s.t.\ y_i (w^Tx_i + b)\geqslant 1, i=1,2,...,m.

(5)

显然，为了最大化间隔，仅需最大化

。于是，式(5)可重写为

\large min_{w,b}||w||^2\\ s.t.\ y_i(w^T x_i+b)\geqslant 1,i=1,2,...,m.

(6)

这就是支持向量机(Support Vector Machine)，简称SVM的基本型。

2、对偶问题

我们希望求解来得到最大间隔划分超平面所对应的模型

(7)

其中w和b是模型参数。注意式(6)本身是一个凸二次规划(convex quadratic programming)问题，能直接用现代的优化算法计算包求解，但我们可以有更高效的办法。对式(6)使用拉格朗日乘子法可得到其“对偶问题”(dual proplem)。具体来说，式(6)的每条约束添加拉格朗日乘子

，则该问题的拉格朗日函数可写为

\large L(w,b,\alpha)=\frac{1}{2}||w||^2+\sum^m_{i=1}\alpha_i(1-y_i(w^Tx_i+b))

(8)

其中

\large \alpha = (\alpha_1;\alpha_2;...\alpha_m)

.令

对w和b的偏导为零可得

(9)

(10)

将式(9)代入(8)，即可将

中的w和b消去，再考虑式(10)的约束，就得到式(6)的对偶问题

\large 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^Tx_j \\ s.t. \ \sum_{i=1}^m \alpha_i y_i =0\\ \alpha\geqslant 0, i=1,2,...,m.

(11)

解出

后，求出w与b即可得到模型

\large f(x)=w^Tw +b \\ =\sum_{i=1}^m\alpha_i y_i x_i^Tx + b

(12)

从对偶问题(11)解出的

是式(8)中的拉格朗日乘子，它恰对应着训练样本

。注意到式(6)中有不等式约束，因此上述过程需要满足KKT(Karush-Kuhn-Tucker)条件，即要求

\large \left\{\begin{matrix} \alpha_i\geqslant 0;\\ y_if(x_i)-1\geqslant 0;\\ \alpha_i(y_if(x_i)-1)=0 \end{matrix}\right.

(13)

于是，对任意训练样本

，总有

或

。若

，则这样本将不会在式(12)的求和中出现，也就不会对f(x)有任何影响；若

，则必有

，所对应的样本点位于最大间隔边界上，是一个支持向量。这显示出支持向量机的一个重要性质：训练完成后，大部分的训练样本都不需保留，最终模型仅与支持向量有关。

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

SMO的基本思路是先固定

之外的所有参数，然后求

上的极值。由于存在约束

，若固定

之外的其他变量，则

可由其他变量导出。于是，SMO每次选择两个变量

和

，并固定其他参数。这样，在参数初始化后，SMO不断执行如下两个步骤知道收敛：

选取一对需要更新的变量

和

；

固定

和

以外的参数，求解式(11)获得更新后的

和

；

注意到只需选取的

和

中有一个不满足KKT条件(13)，目标函数就会在迭代后增大。直观来看，KKT条件违背的程度越大，则变量更新后可能导致的目标函数值增幅越大。于是，SMO先选取违背KKT条件程度最大的变量。第二个变量应该选择一个使目标函数值增长最快的变量，但由于比较各变量所对应的目标函数数值的增幅的复杂度过高，因此SMO采用了一个启发式：使选取的两变量所对对应样本之间的间隔最大。一种直观的解释是，这样的两个变量有很大的差别，与对两个相似的变量进行更新相比，对它们进行更新会带给目标数值更大的变化。

SMO算法之所以高效，恰由于在固定其他参数后，仅优化两个参数的过程能做到非常高效。具体来说，仅考虑

和

时，式(11)中的约束可重写为

\large \alpha_i y_i + \alpha_j y_j=c, \alpha_i\geqslant 0, \alpha_j\geqslant 0

(14)

其中

\large c = -\sum_{k\neq i,j}\alpha_k y_k

(15)

是使

成立的常数。用

(16)

消去式(11)中的变量

，则得到一个关于

的单变量二次规划问题，仅有的约束是

.不难发现，这样的二次规划问题具有闭式解，于是不必调用数值优化算法即可高效地计算出更新后的

和

。

如何确定偏移项b呢？注意到对任意支持向量

为所有支持向量的下标集。理论上，可选取任意支持向量并通过求解式(17)

即

\large y_s(\sum_{i\in S}\alpha_iy _i x_i^T x_s + b)=1

其中

为所有支持向量的下标集。理论上，可选取任意支持向量并通过求解式(17)获得b，但现实任务中常采用一种更鲁棒的做法：使用所有支持向量求解的平均值

\large b=\frac{1}{|S|}\sum_{s\in S}(1/y_s \sum_{i\in S} \alpha_i y_i x_i^T x_s)

(18)

3、核函数

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

表示将x映射后的特征向量，于是，在特征空间划分超平面所对应的模型可表示为

(19)

其中w和b是模型参数，类似式(6)，有

\large min_{w,b}\frac{1}{2}||w||^2 \\ s. t. y_i(w^T \phi (x_i)+b)\geqslant 1,i=1,2,...,m

其对偶问题是

\large max_{\alpha}\sum^m_{i=1}\alpha_i-\frac{1}{2}\sum^m_{i=1}\sum^m_{j=1}\alpha_i\alpha_jy_i y_j \phi(x_i)^T\phi(x_j)

(21)

\large s. t. \sum^m_{i=1}\alpha_i y_i =0,\\ \alpha_i \geqslant 0, i= 1,2,...,m.

求解式(21)涉及到计算

，这是样本

和

映射到特征空间之后的内积。由于特征空间维数可能很高，甚至可能是无穷维，因此直接计算

通常是困难的。为了避开这个障碍，可以设想这样一个函数：

\large \kappa (x_i,y_i)=(\phi(x_i),\phi(y_i))=\phi(x_i)^T\phi(x_j)

(22)

即

和

是在特征空间的内积等于它们在原始样本空间中通过函数

计算的结果。有了这样的函数，我们就不必直接去计算高维甚至无穷维特征空间中的内积，于是式(21)可重写为

\large max_{\alpha}\sum^m_{i=1}\alpha_i - \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\kappa (x_i,y_i) s.t. \sum^m_{i=1}\alpha_i y_i=0\\ \alpha_i \geqslant 0, i=12,...,m.

(23)

求解后即可得到

\large f(x)=w^T\phi(x)+b\\=\sum^m_{i=1}\alpha_i y_i \phi(x_i)^T\phi(x)+b\\=\sum^m_{i=1}\alpha_iy_i\kappa (x,x_i)+b

(24)

这里函数

就是“核函数”(kernel function)，式(24)显示出模型最优解可通过训练样本的核函数展开，这一展开亦称“支持向量展式”(support vector expansion)。

显然，若已知适合映射

的具体形式，则可写出核函数

。但在现实任务中我们通常不知道

是什么形式，那么，适合的核函数是否一定存在呢？什么样的函数能做核函数？我们有下面的定理：

定理：令

为输入空间，

是定义在

上的对称函数，则

是核函数当且仅当对于任意数据

，“核函数”(kernel matrix)K总是半正定的：

\large K=\begin{bmatrix} \kappa (x_1,x_1)& ... & \kappa (x_1,x_j) &... & \kappa (x_1,x_m)\\ \kappa (x_i,x_1)& ... & \kappa (x_i,x_j) &... & \kappa (x_i,x_m)\\ \kappa (x_m,x_1)& ... & \kappa (x_m,x_j) &... & \kappa (x_m,x_m)\\ \end{bmatrix}

上面定理表明，只要一个对称核函数所对应的核矩阵半正定，它就能作为核函数使用。事实上，对于一个半正定核矩阵，总额能找到一个与之对应的映射

。换言之，任何一个核函数都隐式地定义了一个称为“再生核希尔伯特空间”(Reproducing Kernel Space，简称PKHS)的特征空间。

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

下表列出了几种常见的核函数。

名称	表达式	参数
线性核
多项式核		为多项式的次数
高斯核		为高斯核的带宽(width)
拉普拉斯核
SIgmoid核		tanh为双曲正切函数，，

此外，还可以通过函数组合得到，例如：

和

为核函数，则对于任意正数

、

，其线性组合

\large \gamma_1\kappa _1 + \gamma _2 \kappa _2

也是核函数。

和

为核函数，则核函数的直积

\large \kappa _1 \otimes \kappa _2(x,z)=\kappa _1 \otimes \kappa _2(x,z)

(26)

也是核函数。

为核函数，则对于任意函数

，

\large \kappa (x,z)=g(x)\kappa _1(x,z)g(z)

(27)

也是核函数。

4、软间隔与正则化

在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分，退一步讲，即便恰好找到了某个核函数是训练集在特征空间中线性可分，也很难断定这个貌似线性可分的结果不是由于过拟合所造成的。缓解该问题的一个办法是允许向量机在一些样本上出错。为此，要引入“软间隔”(soft margin)的概念。

具体来说，前面介绍的支持向量机形式是要求所有样本均满足约束(3)。即所有样本都必须划分正确，这称为“硬间隔”(hard margin)，而软间隔则是允许某些样本不满足约束

(28)

当然，在最大化间隔的同时，不满足约束的样本尽可能少。于是，优化目标可写为

\large min_{w,b}\frac{1}{2}+C\sum^m_{i=1}\iota _{0/1}(y_i(w^Tx_i+b)-1)

(29)

其中

是一个常数，

是“0/1损失函数”

\large \iota _{0/1}=\left\{\begin{matrix} 1,\ \ if \ z< 0 ;\\ 0, otherwise \end{matrix}\right.

(30)

显然，当C为无穷大时，式(29)迫使所有样本均满足约束(28)，于是式(29)等价于式(6)；当C取有限值时，式(29)不宜直接求解。于是，人们通常其他一些函数来代替

，称为“替代损失”(surrogate loss)。替代损失函数一般具有较好的数学性质，如它们通常是凸的连续

Hinge损失：

(31)

指数函数(exponential loss)：

(32)

对率损失(logistic loss)：

(33)

若采用hinge损失，则式(29)变成：

\large min_{w,b}\frac{1}{2}||w||^2+C\sum_{i=1}^m(0,1-y_i(w^Tx_i+b))

(34)

引入“松弛变量”(slack variables)

，可将(34)重写为

\large min_{w,b,\xi _i}\frac{1}{2}||w||^2+C\sum^m_{i=1}\xi_i

(35)

这就是常用的“软间隔支持向量机”。

显然，式(35)中每个样本都有一个对应的松弛变量，用以表征该样本不满足约束(28)的程度。但是，与式(6)相似，这仍是一个二次规划问题。于是，类似式(6)，通过拉个朗日乘子法可得式(35)的拉格朗日函数

\large L(w,b,\alpha,\xi ,\mu )=\frac{1}{2}||w||^2+C\sum^m_{i=1}\xi_i+\sum^m_{i=1}\alpha_i(1-\xi_i-y_i(w^Tx_i+b))-\sum^m_{i=1}\mu_i\xi_i

(36)

其中

，

是拉个朗日乘子。

令

对w,b,

的偏导数为零可得

(37)

(38)

(39)

将式(37)-(39)代入式(36)即可得到式(35)的对偶问题

\large max_\alpha \sum_{i=1}^m \alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_jx_i^Tx_j\\ s.t. \sum_{i=1}^m\alpha_iy_i=0,0\leqslant \alpha_i\leqslant C,i=1,2,...,m.

(40)

将式(40)与硬间隔下的对偶问题(11)对比可以看出，两者唯一的差别就在对偶变量的约束不同：前者是

，后者是

。于是，可采用二中同样的算法求解式(40)；在引入核函数后能得到与式(24)同样的支持向量展开。

类似式(12)，对软间隔支持向量机，KKT条件要求

\large \left\{\begin{matrix} \alpha_i \geqslant 0, \mu_i \geqslant 0,\\ y_if(x_i)-1+\xi_i\geqslant 0,\\ \alpha_i(y_if(x_i)-1+\xi_i)=0,\\ \xi_i\geqslant 0,\mu_i\xi_i=0. \end{matrix}\right.

(41)

于是，对于任意训练样本

，总有

或

。若

，则该样子不会对f(x)有任何影响；若

，则必有

，即该样本是支持向量：由式(39)可知，若

，则

，进而有

，即该样本恰在最大间隔边界上；若

，则有

，此时若

则该样本落在最大间隔内部，若

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

那么，能否对式(29)使用其他的替代损失函数呢？可以发现，如果使用对率损失函数

来替代式(29)中的0/1损失函数，则几乎就得到了对率回归模型(27)。实际上，支持向量机与对率回归的优化目标想进，通常情形下他们的性能也相当。对率回归的优势主要在于其输出具有自然的概率意义，即在给出预测标记的同时也给出了概率，而支持向量机的输出不具有概率意义，欲得到概率输出需进行特殊处理；此外，对率回归能直接用于多分类任务，支持向量机为此需进行推广。另一方面，从图6.5可看出，hinge损失有一块“平坦”的零区域，这使得支持向量机的解具有稀疏性，而对率损失是光滑的单调递减函数，不能导出类似支持向量的概念，因此对率回归的解依赖于更多的训练样本，其预测开销更大。

我们还可以把式(29)中的0/1损失函数换成别的替代损失函数可以得到其他学习模型，这些模型的性质与所用的替代函数直接相关，但它们具有一个共性：优化目标中第一项用来描述划分超平面的“间隔”大小，另一项

用来表述训练集上的误差，可写为更一般的形式

\large min_f \Omega (f)+ C\sum_{i=1}^m \iota (f(x_i),y_i)

(42)

其中

称为“结构风险”(structured risk)，用于描述模型f的某些性质；第二项

称为“经验风险”(empirical risk)，用于描述模型与训练数据的契合程度；C用于对二者进行折中，从经验风险最小化的角度看，

表述了我们希望获得具有何种性质的模型(例如希望获得复杂度较小的模型)，这位引入领域知识和用户意图提供了途径；另一方面，该信息有助于削减假设空间，从而降低了最小化训练误差的过拟合风险，从这个角度来说，式(42)称为“正则化”(regularization)问题，

称为正则化项，C称为正则化常数，

范数(norm)是常用的正则化项，其中

范数

倾向于w的分解取值尽量均衡，即非零分量个数进行稠密，而

范数

和

范数

则倾向于w的分量尽量稀疏，即非零分量个数尽量少。

5、支持向量机

现在我们来考虑回归问题，给懂训练样本

\large D=\{ (x_1,y_1),(x_2,y_2),,...,(x_m,y_m)\},y_i\in R

，希望学得一个形式如(7)的回归模型，使得f(x)与y尽可能接近，w和b是待确定的模型参数。对样本(x,y)，传统回归模型通常直接基于模型输出f(x)与真实输出y之间的查表来计算损失，当且仅当f(x)与y完全相同时，损失才为零，与此不同，支持向量机回归(Support Vector Regression，简称SVR)假设我们能容忍f(x)与y之间最多有

的偏差，即仅当f(x)与y之间的差别绝对值大于

时才计算损失。这相当于以f(x)为中心，构建了一个宽度为2

的间隔带，若训练样本落入此间隔带，则认为是被预测正确的。

于是SVR问题可形式化为

\large min_{w,h}\frac{1}{2}||w||^2+C\sum^m_{i=1}\iota _\varepsilon (f(x_i)-y_i)

(43)

其中C为正则化常数，

是

-不敏感损失(

-insensitive loss)函数

\large \iota _\varepsilon (z)=\left\{\begin{matrix} 0,\ if|z|\leqslant \varepsilon ;\\ |z|-\varepsilon ,\ otherwise \end{matrix}\right.

(44)

引入松弛变量

和

，可将式(43)重写为

\large min_{w,b,\xi_i,\hat{\xi_i}}\frac{1}{2}||w||^2 + C\sum_{i=1}^m(\xi_i+\hat{\xi_i})\\ s.t. f(x_i)-y_i\leqslant \epsilon + \xi_i\\ y_i-f(x_i)\leqslant \epsilon +\hat{\xi_i}\\ \xi_i\geqslant 0,\hat{\xi_i}\geqslant 0,i=1,2,...,m.

(45)

类似式(36)，通过引入拉个朗日乘子

，

，

，由拉格朗日乘子法可得到式(45)的拉格朗日函数

\large L(w,b,\alpha,\hat{\alpha},\xi,\hat{\xi},\xi,\hat{\xi})=\frac{1}{2}||w||^2+C\sum_{i=1}^m(\xi_i+\hat{\xi_i})-\sum^m_{i=1}\mu_i\xi_i-\sum_{i=1}^m\alpha_i(f(x_i)-y_i-\epsilon -\xi_i)+\sum^m_{i=1}\hat{\alpha_i}(y_i-f(x_i)-\epsilon -\hat{\xi_i})

(46)

将式(7)代入，再令

\large L(w,b,\alpha,\hat{\alpha},\xi,\hat{\xi},\xi,\hat{\xi})

对

的偏导数为零可得

\large w=\sum^m_{i=1}(\hat{\alpha_i}- \alpha_i)x_i

(47)

\large 0=\sum^m_{i=1}(\hat{\alpha_i}-\alpha_i)x_i

(48)

(49)

(50)

将式(47)-(50)代入式(46)，即可得到SVR的对偶问题

\large max_{\alpha,\hat{\alpha}} \sum_{i=1}^my_i({\hat{\alpha_i}}-\alpha)-\epsilon {\hat{\alpha_i}+\alpha_i}-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m({\hat{\alpha_i}}-\alpha_i)({\hat{\alpha_j}}-\alpha_j)x_i^Tx_j s.t.\sum_{i=1}^m({\hat{\alpha_i}}-\alpha)=0,0\leqslant \alpha_i,{\hat{\alpha_i}}\leqslant C

(51)

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

\large \left\{\begin{matrix} \alpha_i(f(x_i)-y_i-\epsilon -\xi_i)=0,\\ \hat{\alpha_i}(y_i-\epsilon -\hat{\xi_i})=0,\\ \alpha_i\hat{\alpha_i}=0,\xi_i\hat{\xi_i}=0,\\ (C-\alpha_i)\xi_i=0,(C-\hat{\alpha_i})\hat{\xi_i}=0 \end{matrix}\right.

(52)

可以看出，当且仅当

时

能取非零值，当且仅当

\large f(x_i)-y_i-\epsilon -\hat{\xi_i}=0

时

能取非零值。换言之，仅当样本

不落入

-间隔带中，相应的

和

才能去非零值。此外，约束

和

不能同时成立，因此

和

中至少有一个为零。

将式(47)代入式(7)，则SVR的解形如

\large f(x)=\sum_{i=1}^m(\hat{\alpha_i-\alpha_i})x_i^Tx+b

(53)

能使式(53)中的

的样本即为SVR的支持向量，它们必落在

-间隔带之外。显然，SVR的支持向量仅是训练样本的一部分，即其解仍具有稀疏性。由KKT条件(52)可看出，对每个样本

都有

且

。于是，在得到

后，若

，则必有

，进而有

\large b=y_i+\epsilon -\sum^m_{i=1}{\hat{\alpha_j}-\alpha_j}x_j^Tx_i

(54)

若考虑特征映射形式(19)，相应的，式(47)将形如

\large w=\sum_{i=1}^m(\hat{\alpha_i}-\alpha_i)\phi (x_i)

(55)

将式(55)代入(19)，则SVR可表示为

\large f(x)=\sum_{i=1}^m(\hat{\alpha_i}-\alpha_i)\kappa (x,x_i)+b

(56)

其中

\large \kappa (x_i,x_j)=\phi (x_i)^T\phi(x_j)

为核函数。

6、核方法

回顾式(24)和(56)可发现，给定训练样本

\large \{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\}

，若不考虑偏移项b，无论如何SVM还是SVR，学得的模型总能表示成核函数

的线性组合。不仅如此，事实上我们有下面这个称为“表示定理” (representer theorem)的更一般的结论。

定理：令H为核函数

对应的再生希尔伯特空间，

表示H空间中关于h的范数，对于任意单调递增函数

和任意非负损失函数

，优化问题

\large min_{h\in R }F(h)=\Omega(||h||_H)+\iota (h(x_1),h(x_2),...,h(x_m))

(57)

的解总可写为

\large h^*(x)=\sum^m_{i=1}\alpha_i \kappa (x,x_i)

(58)

表示定理对损失函数没有限制，对正则化项

仅要求单调递增，甚至不要求

是凸函数，意味着对于一般的损失函数和正则项，优化问题(57)的最优解

都可表示为核函数

的线性组合；这显示出核函数的巨大威力。人们发展处一些列基于核函数的学习方法，统称为“核方法”(kernel methods)。最常见的，是通过“核化”(即引入核函数)来将线性学习器拓展为非线性学习器。下面我们以线性判别分析为例来演示如何通过核化来对其进行非线性拓展，从而得到“核线性判别分析”(Kernelized Linear Discriminant Analysis，简称KLDA)。

我们先假设可通过某种映射