【PRML】支持向量机

【1】【数之道】支持向量机SVM是什么，八分钟直觉理解其本质
【2】

文章目录

1-基本概念1.1-问题建模1.2-数学建模
2-数学求解2.1-问题建模2.2- 问题求解
3-核技巧4-软间隔的数学本质

1-基本概念

1.1-问题建模

如何设计

M

−

1

M-1

M−1维度的超平面把两类维度是

M

M

M的样本点分开
两个概念

间隔 margin：越大的间隔，则两类数据差异越大，越容易区分（the smallest distance between the decision boundary and any of the samples）决策边界 decision boundary : 求解最佳决策边界的问题可以转化为求解两类数据的最大间隔问题，而间隔的中间就是决策边界 （In support vector machines the decision boundary is chosen to be the one for which the margin is maximized.）支持向量 support vectors ：离决策边界最近的两类样本的数据 The location of this boundary is determined by a subset of the data points, known as support vectors,

1.2-数学建模

三个线性方程

决策边界
决策边界上下移动

c

c

c得到间隔上下边界

三个方程等式两边同时除以

c

c

c，并变量代换，得到新的三个方程

正负超平面与决策超平面，如何对

w

w

w与

b

b

b求解

软间隔与硬间隔 （soft margin）

是否需要为了一个异常值，牺牲间隔距离？当有更多的异常值？引入损失因子的概念（成本），间隔是收入，最大化利润，这个最优解下形成的间隔称之为软间隔soft margin 允许一定容错率，本质是在间隔距离大小和错误大小之间找一个平衡

维度转换使得原本不能区分的数据能区分

先对低维数据升维然后在高纬度下利用SVM，利用高纬度下的决策超平面分类利用维度转换函数提升维度？这需要更多的数据存储与计算需求，有没有一种方法能避免将数据送入高维度进行计算

核技巧（kernel trick）：提供高纬度向量相似度的测量（其实SVM本来也就是用来衡量两类数据之间的差异）

选取合适的核公式，即使没有具体的维度转换函数，也可以直接获取数据的高维度差异度

2-数学求解

2.1-问题建模

求解决策超平面

找超平面目标是最大化间隔，先把间隔数学表达

L

L

L先分别在正负超平面上选取一个支持向量点，这两个点满足各自的超平面方程 1 和 2转化为两个向量的点积

在决策超平面随机取两个点

类似地转化为点积发现向量

w

w

w 与决策超平面垂直

再回到正负超平面上选取一个支持向量点

基于向量

w

w

w 与决策超平面垂直的发现，我们可以给出间隔数学表达

L

L

L最大化

L

L

L ， 等价于在约束下最小化

w

w

w

约束是：所有在正超平面上方的点，等式约束变为不等式约束

≥

1

geq 1

≥1，所有在负超平面下方的点，等式约束变为不等式约束

≤

−

1

leq -1

≤−1，进一步结合类别标签，两个约束可以统一成一个约束

2.2- 问题求解

约束条件是等式可以直接用拉格朗日乘子法求解，这里是不等式，所以引入松弛变量

如果大于0,则对应的样本点不在超平面上，此时

λ

=

0

lambda=0

λ=0

λ

=

0

lambda=0

λ=0视为违背约束的惩罚系数

当不满足约束条件，即小于0，如果

λ

lambda

λ再小于0，则拉格朗日方程后半部分也小于0，这会让方程值整体变小，相当变相鼓励违反约束去获得更小值解，所以

λ

≥

0

lambdageq 0

λ≥0

下面复习KKT

根据约束与目标函数的切点。在此切点下，目标函数求梯度，梯度的指向是让函数值增加的方向（红色箭头），同样得到约束的梯度方向（绿色箭头），显然两个箭头方向一致，二箭头长短可以通过

λ

lambda

λ调整为相同当第二个约束也加上，则两个约束焦点是

f

(

w

)

f(w)

f(w)最优解的梯度向量方向，两个约束边界梯度向量包夹区域通过

λ

lambda

λ调整当第三个约束也加上，这个约束不起作用，因为根据前两个约束得到的最优解向量，不在这个约束边界线上，

λ

=

0

lambda=0

λ=0

得出最终的KKT条件
在SVM中为了求解效率和方便运用kernel trick，一般将原问题转为对偶问题

求解SVM中的对偶问题

只有正负超平面上支持向量的

λ

≥

0

lambda geq 0

λ≥0，其余向量的

λ

=

0

lambda =0

λ=0，0 和任何数相乘还是0，不影响

w

w

w的求解结果，所以现在求解

w

w

w只用到支持向量计算量显著减少，进一步求解

b

b

b对偶问题形式更加简洁，并且最优解仅有支持向量的点积结果决定，也就是支持向量的空间相似度决定，既然只需要空间相似度，那么直接用kernel trick直接得到好了

3-核技巧

在对偶变量

≥

0

geq 0

≥0 的约束小，最大化对偶函数，求得最优

λ

⋆

lambda^star

λ⋆，进一步求解决策超平面参数，而

λ

⋆

lambda^star

λ⋆取决于两个参数

标签数据向量之间两两点积结果

如果是非线性SVM问题，那么目标方程在原维度下无解

通过维度变换得到新问题，如何求新维度下向量之间两两点积结果，因为这就直接决定我们求解新维度下的决策超平面

两种方法

维度转换函数：定义维度转换函数，对数据完成维度转换后，再去求新维度下向量的点积直接套用核函数：可以直接利用原维度下向量点积结果，直接得到新维度下向量点积结果

举例说明

不同参数

c

d

cd

cd能控制转换后的维度数和空间相似度，进而影响最终的决策超平面结果，思考如何选择参数呢正是因为有了参数

c

c

c，最终的点积式中才包含了从低次项到高次项的数据组合，体现维度多样性如果没有参数

c

c

c，那么最终的点积式中就只包含高次项，此时，我们可以将多个不同次的核函数组合（即此时参数

c

=

0

c=0

c=0，只调整参数

d

d

d），我们也可以得到多个不同次的多项式核函数，结果包含从低次项到高次项的数据组合，维度因此多样化，这是高斯核函数的基础

总结
参数

c

d

cd

cd确定，维度数也就确定了

如果对维度不设置限制，并要求包含从低次到高次的全部的数据交互可能性组合，在这个无限维度空间求解决策超平面

维度变换根本行不通，因为无限维度需要无限的新维度数据需要先定义再存储计算高斯核函数 radial basis function （RBF）

高斯核函数 radial basis function （RBF）

高斯核函数的值表示两个向量相似度的大小，由一个大于0的参数

γ

gamma

γ和两向量坐标点间的距离共同决定给定

γ

gamma

γ，当两点距离越小，相似度向1靠近

变动

γ

gamma

γ，

γ

gamma

γ越小图越扁平，此时即使距离较远仍有明显的相似度（数据点之间的相似度呗放大，因此更容易被简单的超平面划分），反之越尖，同样的距离相似度很小（除了部分距离相近的点，其余数据点均与其他店缺乏相似性，在计算超平面时需要考虑这些点各自的空间特征，所以容易出现过拟合）

通过设置

γ

=

1

/

2

gamma=1/2

γ=1/2，对RBF推导

化简后发现，这就是上面即此时参数

c

=

0

c=0

c=0，只调整参数

d

d

d，我们也可以得到多个不同次的多项式核函数，结果包含从低次项到高次项的数据组合，维度因此多样化，根据不同的阶乘数调整再相加此时我们已经可以在不实质性踏入无限维度的情况下，得到了无限维度下向量相似度的结果所以在用SVM处理非线性分类问题可以直接使用高斯核函数

4-软间隔的数学本质

如果要迎合异常的数据点，那么硬间隔就会缩小，得到新硬间隔，此时我们需做选择

新硬间隔，由于间隔变窄，未来用于数据预测分类的效果将大打折扣原硬间隔，因为新点的加入，原硬间隔的约束条件被破坏，产生系统损失，这个包含损失的间隔就是软间隔

进一步量化这个违反约束点的损失/误差

移动这个异常点，观察损失变换，临界点解释负超平面，这就是铰链损失函数（hinge loss function）

建模软间隔的数学优化

类比硬间隔的问题建模，就是引入损失值，两者都是越小越好，但是二者会相互制约

w长度越大，间隔L越小，原始数据越不容易出现分类错误，因此损失和越小

实际中需要参数C平衡

大C，放大损失项，容忍度低，C趋于无穷，就表示无法容忍误差，此时就是硬间隔，此时最优解中的损失趋于0，优化问题也就是硬间隔问题当C小，函数值对误差不敏感，最优解中可以仍然较大的误差