跳转至

支持向量机

信息

边际最大超平面

超平面, Hyperplane是数学和机器学习中的一个概念. 它是一个nn维空间中将空间划分为两个部分的几何对象. 具体来说, 在nn维空间中, 超平面是一个n−1n-1维子空间. 例如, 在二维空间中, 超平面是一条一维的直线, 直线将平面分成两个部分; 在三维空间中, 超平面是一个二维的平面, 平面将空间分为两个部分, 依此类推...

在左图中, 找到一个线性的决策边界(直线, 超平面)使得数据能够分开, 这道题的答案有很多, 如右图.

支持向量, support vector是离决策边界最近的样本(数据点). 边际, margin是指正负超平面(什么是正负超平面下面有讲到)之间的距离, 如左图. 当然, 也可能同时出现多个支持向量, 因为它们都是最靠近决策边界的样本点, 如右图.

支持向量之所以被称为向量是因为给的样本就是一个向量, 试想, 样本有很多的特征, 这些特征构成了向量... 支持向量是所有样本点(向量)的子集.

下面来看, 哪一个超平面(决策边界)更优呢? B1还是B2? 哪个超平面能够更准确地分类新数据?

答案是B1, 因为它的边际更大. 拥有最大边际的超平面我们称之为边际最大超平面. 按照这个超平面(决策边界)分类的数据准度会更高. 如果边际过小, 意味着决策边界和支持向量非常接近, 在这种情况下, 即使是很小的变化都可能导致分类结果发生显著变化, 这意味着模型对数据扰动很敏感, 容易出现过拟合现象; 如果边际较大, 意味着模型对于数据的微小变化更具有鲁棒性, 有较好的泛化性能. 这种选择大边际的策略在统计理论中也得到了支持, 称为"结构风险最小化原理".

线性支持向量机

现在我们有一个二分类问题, 一共有NN个训练样本(输入向量). 我们定义x\boldsymbol{x}为输入向量, yy为分类值, 即xi=(xi1,xi2,...,xim)T,yi={−1,1}\boldsymbol{x_i}=(x_{i1}, x_{i2}, ..., x_{im})^T, y_i=\{-1, 1\}. 参考线性分类. 我们有一个符号函数signsign, 如果w⋅x+b\boldsymbol{w}\cdot \boldsymbol{x}+b的结果>0>0, 说明样本点在决策边界的上方; 如果w⋅x+b\boldsymbol{w}\cdot \boldsymbol{x}+b的结果<0<0, 说明样本点在决策边界的下方. y=w⋅x+by=\boldsymbol{w}\cdot \boldsymbol{x} + b就是决策边界.

超平面方程式

假设输入向量x\boldsymbol{x}是二维的. 我们可以将决策边界HH的超平面方程式定义为w1x1+w2x2+b=0w_1x_1+w_2x_2+b=0(标量形式). 将超平面方程式上下移动cc个单位, 分别是w1x1+w2x2+b=cw_1x_1+w_2x_2+b=c和w1x1+w2x2+b=−cw_1x_1+w_2x_2+b=-c, 来到对应的间隔上下边界H1,H2H_1, H_2, 由于上下边界一定会经过一些样本数据点, 而这些点距离决策边界最近, 他们决定了间隔距离, 我们称之为支持向量. 我们可以把等式两边分别除以cc, 得到w1cx1+w2cx2+bc=1\frac{w_1}{c}x_1+\frac{w_2}{c}x_2+\frac{b}{c}=1, w1cx1+w2cx2+bc=−1\frac{w_1}{c}x_1+\frac{w_2}{c}x_2+\frac{b}{c}=-1和w1cx1+w2cx2+bc=0\frac{w_1}{c}x_1+\frac{w_2}{c}x_2+\frac{b}{c}=0, 使用w1′=w1c,w2′=w2cw'_1=\frac{w_1}{c}, w'_2=\frac{w_2}{c}和b′=bcb'=\frac{b}{c}替换, 可以得到w1′x1+w2′x2+b′=1w'_1x_1+w'_2x_2+b'=1, w1′x1+w2′x2+b′=−1w'_1x_1+w'_2x_2+b'=-1和w1′x1+w2′x2+b′=0w'_1x_1+w'_2x_2+b'=0, 由于w1′,w2′w'_1, w'_2和b′b'只是我们需要求解的代号, 所以将其换为w1,w2w_1, w_2和bb也不影响计算, 所以最终只需要求解w1,w2w_1, w_2和bb就可以了, 得到下面三个超平面方程: w1x1+w2x2+b=1w_1x_1+w_2x_2+b=1, w1x1+w2x2+b=−1w_1x_1+w_2x_2+b=-1和w1x1+w2x2+b=0w_1x_1+w_2x_2+b=0, 这三个方程式分别称为正超平面方程式(对应正超平面H1H_1), 负超平面方程式(对应负超平面H2H_2)和决策超平面方程式(对应决策超平面HH).1

最大化拉格朗日函数

回到超平面方程式的向量形式, 对于任意一个样本点, 它到超平面w⋅x+b=0\boldsymbol{w}\cdot \boldsymbol{x} + b=0的垂直距离可以通过公式∣w⋅x+b∣∣∣w∣∣\frac{|\boldsymbol{w}\cdot \boldsymbol{x} + b|}{||\boldsymbol{w}||}计算. 因此, 支持向量之间的垂直距离可以计算为d=∣(w⋅x1+b)−(w⋅x2+b)∣∣∣w∣∣d=\frac{|(\boldsymbol{w}\cdot \boldsymbol{x_1}+b)-(\boldsymbol{w}\cdot \boldsymbol{x_2}+b)|}{||\boldsymbol{w}||}, 由于w⋅x1+b=1\boldsymbol{w}\cdot \boldsymbol{x_1}+b=1, w⋅x2+b=−1\boldsymbol{w}\cdot \boldsymbol{x_2}+b=-1, 我们可以将其代入上述公式, 得到d=2∣∣w∣∣d=\frac{2}{||\boldsymbol{w}||}.

我们的目标就是要最大化这个dd, 也就是最小化∣∣w∣∣||\boldsymbol{w}||, 等同于最小化函数12∣∣w∣∣2.\frac{1}{2}||\boldsymbol{w}||^2. 所以线性支持向量机将12∣∣w∣∣2\frac{1}{2}||\boldsymbol{w}||^2作为代价函数, 前提条件是所有的样本必须被正确分类(即硬边际), 即对于任意的yiy_i, 有yi(w⋅xi+b)≥1y_i(\boldsymbol{w}\cdot \boldsymbol{x_i}+b)\geq 1. 这是一个凸二次优化问题.

我们可以使用拉格朗日乘数法将约束条件结合到目标函数中, 构造如下: L(w,b,λ)=12∣∣w∣∣2−∑i=1Nλi[yi(w⋅xi+b)−1]L(\boldsymbol{w}, b, \boldsymbol{\lambda})=\frac{1}{2}||\boldsymbol{w}||^2-\sum_{i=1}^N \lambda_i[y_i(\boldsymbol{w}\cdot \boldsymbol{x_i}+b)-1], 其中λi\lambda_i为拉格朗日乘子, λ=(λ1;λ2;...;λN),λi≥0\boldsymbol{\lambda}=(\lambda_1; \lambda_2; ...; \lambda_N), \lambda_i\geq 0. 拉格朗日函数是原目标函数的对偶问题, 即求原目标函数的极小值就是求拉格朗日函数的极大值, 令L(w,b,λ)L(\boldsymbol{w}, b, \boldsymbol{\lambda})对w\boldsymbol{w}和bb求导为00可得: w=∑i=1Nλiyixi(1)\boldsymbol{w}=\sum_{i=1}^{N}\lambda_iy_i\boldsymbol{x_i}(1), 0=∑i=1Nλiyi(2)0=\sum_{i=1}^N\lambda_iy_i(2). 将(1),(2)(1), (2)式代入L(w,b,λ)L(\boldsymbol{w}, b, \boldsymbol{\lambda}), 其中前半部分有12wTw=12(∑i=1Nλiyixi)T(∑j=1Nλjyjxj)=12∑i=1N∑j=1NλiλjyiyjxiTxj\frac{1}{2}\boldsymbol{w}^T{\boldsymbol{w}}=\frac{1}{2}(\sum_{i=1}^N \lambda_iy_i\boldsymbol{x_i})^T(\sum_{j=1}^N\lambda_jy_j\boldsymbol{x_j})=\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \lambda_i\lambda_jy_iy_j\boldsymbol{x_i}^T\boldsymbol{x_j}, 后半部分有∑i=1Nλi[yi(w⋅xi+b)−1]=∑i=1Nλiyi(∑j=1Nλjyjxj⋅xi+b)−λi=b∑i=1Nλiyi+∑i=1N∑j=1NλiλjyiyjxiTxj−∑i=1Nλi\sum_{i=1}^N \lambda_i[y_i(\boldsymbol{w}\cdot \boldsymbol{x_i}+b)-1]=\sum_{i=1}^N\lambda_iy_i(\sum_{j=1}^N\lambda_jy_j\boldsymbol{x_j}\cdot \boldsymbol{x_i}+b)-\lambda_i=b\sum_{i=1}^N\lambda_iy_i+\sum_{i=1}^N\sum_{j=1}^N \lambda_i\lambda_jy_iy_j\boldsymbol{x_i}^T\boldsymbol{x_j}-\sum_{i=1}^N\lambda_i, 故有max{L(w,b,λ)}=max∑i=1Nλi−12∑i=1N∑j=1Nλiλjyiyjxi⋅xjmax \{L(\boldsymbol{w}, b, \boldsymbol{\lambda})\}=max \sum_{i=1}^N\lambda_i-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\lambda_i\lambda_jy_iy_j\boldsymbol{x_i}\cdot\boldsymbol{x_j}.2

如何求解这个式子呢? 可以看到, 关键就是要求拉格朗日乘数, 其他的都可以直接读取数据得到. 拉格朗日乘数表示的是每个约束对目标函数的影响大小, 拉格朗日乘数大的样本点(通常是支持向量)对决策边界的贡献较大, 而拉格朗日乘数为00的样本点对决策边界没有影响. 这个式子的求解可以使用二次规划(Quadratic Programming, QP)或者其他的技术, QP算法如SMO算法请见西瓜书第124页.

解出拉格朗日乘数之后, 我们就可以计算出系数向量w=∑i=1Nλiyixi\boldsymbol{w}=\sum_{i=1}^N\lambda_iy_i\boldsymbol{x_i}. 最佳决策边界由w\boldsymbol{w}决定, 而w\boldsymbol{w}就是一堆向量的线性组合(∑\sum拉格朗日乘数*标签*特征向量). 在实际中, 大多数的λi\lambda_i的值都是00, 也就是说对应的训练样本xi\boldsymbol{x_i}对决策边界的确定没有贡献, 那些对应λi\lambda_i不为00的训练样本就是支持向量.

现在, 如果出现了一个新的样本zz, 我们可以计算出f=w⋅z+b=∑i=1Nλiyixi⋅z+bf=\boldsymbol{w}\cdot \bm{z}+b=\sum_{i=1}^N\lambda_iy_i\bm{x_i}\cdot \bm{z}+b, 从而预测结果为sign(f)sign(f). 如果f>0f>0, 会被归类为11; 如果f<0f<0, 会被归类为−1-1.

好了, 举一个例子. 现在我有88个二维的训练样本, 总共分22类: 11和−1-1. 在使用QP求解拉格朗日极值下的乘数λ\bm{\lambda}之后, 我们发现只有22个乘数是非零的, 分别是样本11和样本22, 它们对应的就是支持向量. 现在, 我们可以计算出它们的系数w1=∑i=1Nλiyixi1w_1=\sum_{i=1}^N \lambda_iy_i\bm{x_{i1}}, w2=∑i=1Nλiyixi2w_2=\sum_{i=1}^N \lambda_iy_i\bm{x_{i2}}. bb可以用公式推出(未给出). 现在我们就得到了预测模型f=w1x1+w2x2+bf=w_1x_1+w_2x_2+b, 根据这个就可以给出预测.

例子

给出下列样本以及拉格朗日乘数, 计算决策边界表达式.

x₁ x₂ y 拉格朗日乘数
0.3858 0.4687 1 65.5261
0.4871 0.6118 -1 65.5261
0.9218 0.4103 -1 0
0.7382 0.8936 -1 0
0.1763 0.0579 1 0
0.4057 0.3529 -1 0
0.9355 0.8132 1 0
0.2146 0.0099 -1 0

可以看到, 有两个拉格朗日乘数非零, 第一个样本处在正超平面上, 第二个样本处在负超平面上, 它们都是支持向量. 根据公式, 可以得到w1=∑i=12λiyixi1=65.5261(1∗0.3858−1∗0.4871)=−6.64w_1=\sum_{i=1}^2\lambda_i y_i \bm{x_{i1}}=65.5261(1*0.3858-1*0.4871)=-6.64, w2=∑i=12λiyixi2=65.5261(1∗0.4687−1∗0.6118)=−9.32w_2=\sum_{i=1}^2\lambda_i y_i \bm{x_{i2}}=65.5261(1*0.4687-1*0.6118)=-9.32

对于位于正超平面上的支持向量, 有y1(w⋅x1+b)=1y_1(\bm{w}\cdot \bm{x_1}+b)=1, 故1⋅(−6.64⋅0.3858−9.32⋅0.4687+b)=11\cdot(-6.64\cdot 0.3858-9.32\cdot 0.4687+b)=1, 可以解出b=7.93b=7.93. 对于位于负超平面上的支持向量, 也有上述式子, 解出来的bb应该和上面的结果是相等的.

综上所述, 决策边界为y=−6.64x1−9.32x2+7.93y=-6.64x_1-9.32x_2+7.93.

软边际和硬边际

上面我们提到的约束条件是"所有的样本必须正确分类", 这属于硬边际, hard-margin分类问题. 对应的还有软边际, soft-margin分类问题, 我们可以允许一些错误的分类. 软边际分类问题通俗的理解就是允许在正超平面和负超平面之间存在一些样本点. 如下图.

我们发现, 在边际的距离上B1远胜B2, 但是B1中正负超平面之间存在着两个样本点. 这是否意味着B2就好于B1呢? 其实, 是需要衡量一下的, 相当于边际的距离是加分项, 错误分类是减分项, 要做的就是根据情况掂量掂量最后的收益如何. 一般情况下, 边际的距离更重要, 因为大的边际距离能够让模型更少受噪音干扰, 防止过拟合.

在硬边际分类问题中, 我们要最小化的是∣∣w∣∣||\boldsymbol{w}||(对于所有的样本, yi(wTxi+b)≥1y_i(\bm{w}^T\bm{x_i}+b)\geq 1), 而在软边际问题中, 我们只需要增加一个额外的参数CC: ∣∣w∣∣+C∑ξi||\bm{w}||+C\sum \xi_i(对于所有的样本, yi(wTxi+b)≥1−ξiy_i(\bm{w}^T\bm{x_i}+b)\geq 1-\xi_i, ξi≥0\xi_i\geq 0), ξi\xi_i就是每个样本的额外允许的误差, 可以看到当CC变大的时候, 后面那项在最小化的时候权重就会比较大, 会使得更加注重减小分类错误, 而不是增加边际距离.

非线性支持向量机

更为普遍的情况是, 大多数的问题都不是线性可分的, 如图.

SVM可以被进一步延伸用来处理这一类问题. 一种思路就是将数据从原始特征空间转换到一个新的特征空间(通常是高纬度的空间). 在新的特征空间中, 学习一个线性决策边界来分离不同类别的数据. 新特征空间中的线性决策边界可以通过逆变换映射回原始特征空间. 在原始特征空间中, 这个映射回来的决策边界通常表现为非线性的决策边界. 例如变换ϕ=(x1,x2)→(x12−x1,x22−x2)\phi=(x_1, x_2)\rightarrow(x_1^2-x_1, x_2^2-x_2).

再如:

所以, 我们应该用什么样的映射函数ϕ\phi? 就算我们知道了映射函数, 我们怎么在新的特征空间里面高效的计算? 因为在新的特征空间里面做点积是非常消耗计算机资源的. 要计算的是∑i=1Nλi−12∑i=1N∑j=1Nλiλjyiyjϕ(xi)⋅ϕ(xj)\sum_{i=1}^N\lambda_i-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\lambda_i\lambda_jy_iy_j\boldsymbol{\phi(x_i)}\cdot\boldsymbol{\phi(x_j)}的最大值, 而ϕ(xi)\boldsymbol{\phi(x_i)}和ϕ(xj)\boldsymbol{\phi(x_j)}都是更高维的向量, 点积非常耗时间.

核方法

解决上述问题的方法是使用核方法, kernel trick. 核方法是一种计算ϕ(xi)⋅ϕ(xj)\boldsymbol{\phi(x_i)}\cdot\boldsymbol{\phi(x_j)}的方法. 它与之前的方法不同, 它不会先映射xi\bm{x_i}和xj\bm{x_j}然后点积ϕ(xi)\boldsymbol{\phi(x_i)}和ϕ(xj)\boldsymbol{\phi(x_j)}. 它采取的是另一种方式: 我们先计算原始特征向量的点积, 然后使用核函数得出映射后的特征向量的点积. 这个核函数表示了原始特征向量的点积和映射后的特征向量的点积的关系.

例如, 现在我们有两个二维的特征向量u=(u1,u2)\bm{u}=(u_1, u_2), v=(v1,v2)\bm{v}=(v_1, v_2). 和一个映射函数ϕ=(x1,x2)→(x12,2x1x2,x22)\phi=(x_1, x_2)\rightarrow(x_1^2, \sqrt{2}x_1x_2, x_2^2), 按照原来的方法, 应该先计算ϕ(u)\phi(\bm{u})和ϕ(v)\phi(\bm{v}), 然后点积ϕ(xi)⋅ϕ(xj)\boldsymbol{\phi(x_i)}\cdot\boldsymbol{\phi(x_j)}. ϕ(xi)⋅ϕ(xj)=(u12,2u1u2,u22)⋅(v12,2v1v2,v22)=(u1v1+u2v2)2=(u⋅v)2\boldsymbol{\phi(x_i)}\cdot\boldsymbol{\phi(x_j)}=(u_1^2, \sqrt{2}u_1u_2, u_2^2)\cdot(v_1^2, \sqrt{2}v_1v_2, v_2^2)=(u_1v_1+u_2v_2)^2=(\bm{u}\cdot\bm{v})^2. 这样子费时费力, 消耗大量资源. 但是, 有一个惊喜, 在计算过程中, 我们发现映射后的特征向量的点积居然可以用原始特征向量的点积表示, 即ϕ(u)⋅ϕ(v)=(u⋅v)2\phi(\bm{u})\cdot \phi(\bm{v})=(\bm{u}\cdot \bm{v})^2. 这个关系可以用核函数表示, K(u,v)=(u⋅v)2K(\bm{u}, \bm{v})=(\bm{u}\cdot\bm{v})^2. 所以, 我们可以先在低维空间算出u⋅v\bm{u}\cdot\bm{v}, 然后利用核函数直接算出高维空间的点积.

默瑟定理

在上面我们计算的时候我们已经知道了映射函数ϕ\phi, 但是大多数情况下, 我们是不知道这个映射函数的. 有时候这个映射函数可能非常复杂, 高维空间的维度可能非常高, 显式地定义和计算ϕ\phi不切实际. 这意味着我们不能先知道ϕ\phi, 然后从这个ϕ\phi反推出核函数.

在实际中, 我们会直接选择一个能够使样本线性可分的核函数(知道了核函数相当于知道了映射后的内积, 知道了映射后的内积相当于可以求拉格朗日方程的极大值对应的参数, 得到决策边界), 而不需要关心映射函数ϕ\phi(因为映射关系对于求解问题可有可无).

默瑟定理, Mercer定理表明, 一个核函数K(u,v)K(\bm{u}, \bm{v})如果满足特定条件, 那么这个核函数一定对应这某一个映射函数ϕ\phi. 所以, 我们一般会直接选择或者设计一个符合要求的核函数, 它已经隐含了某种高维空间的映射函数, 这种映射函数我们是不用关心的.

几种常见的符合默瑟定理的核函数为:

  • 多项式核: K(x,y)=(x⋅y+1)pK(\bm{x}, \bm{y})=(\bm{x}\cdot \bm{y}+1)^p
  • RBF核: K(x,y)=exp(−∣∣x−y∣∣22σ2)K(\bm{x}, \bm{y})=exp(-\frac{||\bm{x}-\bm{y}||^2}{2\sigma^2})
  • 双曲正切核: K(x,y)=tanh(kx⋅y−θ)K(x, y)=tanh(k\bm{x}\cdot y-\theta) (默瑟定理只对一些kk和θ\theta成立)

我们要做的就是选出最优的核函数, 使得进行隐式映射后, 得到的样本在高维空间中能够线性可分而且得到的结果不错. 极大化拉格朗日函数可以写为max∑i=1Nλi−12∑i=1N∑j=1NλiλjyiyjK(xi,xj)max \sum_{i=1}^N\lambda_i-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\lambda_i\lambda_jy_iy_jK(\bm{x_i, x_j}). 预测zz: f=w⋅z+b=∑i=1NλiyiK(xi,z)+bf=\bm{w}\cdot \bm{z}+b=\sum_{i=1}^N \lambda_iy_iK(\bm{x_i}, \bm{z})+b.

RBF核函数

我们来看一种比较常用的核函数: RBF核函数, 这种表达式的函数为K(x,y)=exp(−∣∣x−y∣∣22σ2)K(\bm{x}, \bm{y})=exp(-\frac{||\bm{x}-\bm{y}||^2}{2\sigma^2}). 这个函数有一个超参数, Hyper Parameter, 即σ\sigma, 结合我们在软边际和硬边际中讲到的另一个超参数CC. 我们在训练中常常会调节这两个参数, 尝试将它们组合, 然后评估结果, 如:

  • 超参数σ\sigma控制核函数的曲线形状, 决定了每个点的"影响范围". 当σ\sigma很小的时候, RBF曲线的半径较大, 意味着每个点的影响范围更广, 导致决策边界更加平滑, 接近线性, 这种情况下, 模型可能会欠拟合, 因为它没有捕捉数据中的细节. 当σ\sigma很大的时候, RBF曲线的半径较小, 每个点的影响范围较窄, 模型会试图过多地你和训练数据中的细节, 导致决策边界在个别实例周围出现波动和不规则形, 可能会导致过拟合
  • 超参数CC控制模型对误分类点的惩罚强度, 参考软边际和硬边际. 当CC很小的时候, 允许更多的点被误分类, 因此决策边界更加平滑, 接近线性, 适用于防止过拟合, 我们可以看左上角的图, 边界基本上是线性的了; 当CC很大的时候, 模型更加关注误分类的点, 导致决策边界弯曲, 以捕捉到更多的细节, 如果数据复杂, 模型可能会过拟合, 我们可以看到右下角的图, 相比于左下角的图, 两个蓝色的点被正确分类了

控制超参数是非常重要的, 我们可以使用交叉验证结合参数网格的方法来训练模型.

  1. FunInCode. (n.d.). 【数之道】支持向量机SVM是什么，八分钟直觉理解其本质_哔哩哔哩_bilibili. From https://www.bilibili.com/video/BV16T4y1y7qj/ ↩

  2. 周志华. (n.d.). 机器学习. ↩

评论