SVM 支持向量机

发布时间:2017-7-9 7:03:27编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"SVM 支持向量机 ",主要涉及到SVM 支持向量机 方面的内容,对于SVM 支持向量机 感兴趣的同学可以参考一下。

支持向量机就是使用了核函数的软间隔线性分类法.“机”在机器学习领域通常是指算法,支持向量是指能够影响决策的变量。
示意图:
SVM


SVM原理

在样本量少的情况下,比神经网络的效果好。
过程:提取特征、降维、训练。

由逻辑回归引入

二分类

逻辑回归是从特征中学习出一个二分类模型。分类y=1的概率\(p(y=1|x;\theta)\)形式化表示为\(h_θ (x) = g(θ^T x)={1\over 1+e^{-θ^T x}}\) .当\(θ^T x\) ≫ 0时,\(h_θ (x)\)=1,反之≪0时\(h_θ (x)\)=0.

中间的分割线即决策边界\(θ^T x=0\),点到决策线的距离反映了分类正确的置信度。对于图中的C点,离分割线较近,分割线稍有变动就可能被误分类。逻辑回归便是找一条中间线使得所有点整体上离这条线最远。但实际上那些离得较远的点不需要过多考虑,而应该着重考虑靠近中线的那些点。SVM相当于将视角从全局拉到了局部。分类器表达式重写为(θ用w,b替换,函数关系有所变化):
\[h_{ w,b} (x) = g(w ^T x + b) \\g(z)=\begin{cases}1 && z\ge0 \\-1 && z\lt 0\end{cases}\tag 1\]

函数间隔与几何间隔(Functional and geometric margins)

给定一个训练样本\((x ^{(i)} , y ^{(i)} )\),定义函数间隔如下:
\[\hat \gamma^{(i)} = y^{(i)} (w ^T x + b) \tag 2\]
其中\(y^{(i)}\)的值为{-1,1},\(|w ^T x + b|\)越大,分类置信度越大,函数间隔越大。
其意义在于:\(|w ^T x + b|\)能够表示点x到超平面的距离,通过观察\(|w ^T x + b|\)的符号与真实类别y的符号是否一致可判断分类是否正确。同号时结果为正数。
全部样本上的函数间隔定义为:\[\hat \gamma=\min_{i=1,\dots,m}\hat \gamma^{(i)}\]
但这样定义的函数间隔存在问题,将w与b的值同时放大一定的倍数时,函数间隔也会增大。

设点A代表一个样本,标签y=1,特征为\(x ^{(i)}\),则该点在决策面\(w ^T x + b = 0\)上的投影点B的特征为\(x ^{(i)} − γ ^{(i)} · w/||w||\)\(\gamma\)为样本x到分类间隔的距离. 向量$ w/||w||$为法向量。因为点B在决策面上,因此
\[\begin{align}w^T(x ^{(i)} −& γ ^{(i)} {w\over \|w\|})+b=0 \\&↓ \\ γ ^{(i)}&=({w\over \|w\|})^Tx ^{(i)}+{b\over \|w\|} \end{align} \tag 3\]
几何间隔可进一步表示为(令 γ 乘以对应的类别得到绝对值,当然误分类的情况就是负数了)
\[γ ^{(i)}=y^{(i)}\big(({w\over \|w\|})^Tx ^{(i)}+{b\over \|w\|}\big) \tag 4\]
可以看出几何间隔就是函数间隔除以\(\|w\|\),解决了函数间隔会随w的增大而改变的问题。当\(\|w\|=1\)时,几何间隔便是函数间隔;函数间隔归一化后就是几何间隔.同函数间隔一样全部样本上的几何间隔定义为所有训练样本中最小的几何间隔\[\gamma=\min_{i=1,\dots,m}\gamma^{(i)}\].

最优间隔分类器

寻找最优间隔分类器即找出最大的几何间隔(不用函数间隔是因为缩放w使得函数间隔可无限增大),可以形式化的表示为:
\[\begin{align}\max_{ γ,w,b} &\ \ γ \\s.t. &\ \ y ^{(i)} (w ^T x^{(i)} + b) ≥ γ, i = 1, . . . , m \\&\ \ \|w\| = 1\end{align}\tag 5\]
这里用||w||=1 规约 w,使得\(w ^T x + b\)是几何间隔。然而||w|| = 1不是凸函数,普通的优化求解器无法求解.考虑几何间隔和函数间隔的关系,\(γ={\hat γ\over \|w\|}\),我们改写一下上面的式子:
\[\begin{align}\max_{ γ,w,b} &\ \ {\hat γ\over \|w\|} \\s.t. &\ \ y ^{(i)} (w ^T x^{(i)} + b) ≥\hat γ, i = 1,\dots, m\end{align}\tag 6\]
式子中仍然包含凸函数,考虑到同时将w和b扩大或缩放一定倍数,对分类结果没有影响,因此可以使得\(\hat γ=1\).因此max \({\hat γ\over \|w\|}={1\over \|w\|}\)等价于min ||w||,等价于min \({1\over 2} \|w\|^2\),后者便于求导后的式子表达.改写之后变为二次规划问题:
\[\begin{align}\min_{ γ,w,b} &\ \ {1\over 2}\|w\|^2 \\s.t. &\ \ y ^{(i)} (w ^T x^{(i)} + b) ≥ 1, i = 1,\dots, m\end{align}\tag 7\]

对偶问题

构造拉格朗日函数:
\[\mathcal L(w, b, α) ={1\over 2}\|w\|^2 −\sum^m_{i=1}α_ i[ y ^{(i) }(w^ T x^{(i) }+ b) − 1] \tag 8\]
在约束条件(\(\forall i, y ^{(i)} (w ^T x^{(i)} + b) ≥ 1\))都满足的情况下,且约束\(α_ i\ge 0(i=1,\cdots, n)\),则优化的目标\(\min_{w,b} {1\over 2}\|w\|^2\)等价于\(\min_{w,b}\max_{α_ i\ge 0} \mathcal L(w, b, α)\)
接下来求解对偶问题.

\(\nabla_w\mathcal L(w, b, α) =0\),求得
\[w=\sum^m_{i=1}α_ i y ^{(i) }x^{(i) } \tag{9}\]
对b求偏导得
\[\nabla_b\mathcal L(w, b, α) =\sum^m_{i=1}α_ i y ^{(i) }=0 \tag{10}\]
合并(8)(9)(10)可得原问题的对偶问题:
\[\begin{align}\max_{α} &\ \ W(α)=\sum^m_{i=1}α_ i-{1\over 2}\sum^m_{i,j=1}y ^{(i)} y ^{(j)}α_ iα_ j⟨x^{(i)},x^{(j)}⟩ \\s.t. &\ \ α_ i ≥0, i = 1,\dots, m \\&\ \ \sum^m_{i=1}α_ i y ^{(i) }=0 \end{align}\tag{11}\]
求解出了各个\(α_ i\)的值,可进而求出w与b,因此可以使用\(w^T x + b\)来对新样本进行分类了.实际上这里可以用一种快速学习算法即 SMO 算法来求解这个对偶问题.可以得到w为\[w=\sum^m_{i=1}α_ix^{(i)}y^{(i)}\]
此时决策函数为\(f(x)=\rm{sgn}(w^T x + b)\)
\(w^T x + b\)的形式稍作变化可以引入核函数:
\[w^T x + b =\sum^m_{i=1}α_ i y ^{(i) }⟨x^{(i)},x⟩+b\tag{12}\]
所有的非支持向量的\(α=0\),因此内积操作只需计算少量的支持向量.

核函数

用于将数据映射到高维,从而更好得拟合模型并且还可以解决线性不可分的情况.举例,y与x的关系可能是3次多项式关系,因此需要将特征x扩展到三维\((x, x ^2 , x ^3)\),然后寻找特征和结果之间的模型.

我们需要将SVM公式\(w^T x + b\) 中的内积从\(< x ^{(i)} , z >\),映射到\(< φ(x ^{(i)} ), φ(z) >\).定义映射后的内积为核函数$K(x,z)= φ(x )^T φ(z) $.

然而如果直接计算高维数据的内积,显然计算量级比原始数据的内积高.如果核函数仍然是计算低维数据,则可以不增加计算量.
核技巧举例:设\(\mathbf x_1=(x_1,y_1),\mathbf x_2=(x_2,y_2)\)为二维空间中的两个点,利用映射\((x,y)\mapsto (x^2,y^2,\sqrt 2xy)\)将其映射到一个三维特征空间中的点\(\mathbf x_1',\mathbf x_2'\).内积\(\langle \mathbf x_1',\mathbf x_2'\rangle=x_1^2x_2^2+y_1^2y_2^2+2x_1y_1x_2y_2=(x_1x_2+y_1y_2)^2=(\langle\mathbf x_1,\mathbf x_2\rangle)^2\)
可见,只要将这两点的原始空间中的内积取平方,无需构造新的特征向量(高维特征)便可得到新空间中对应的内积.直接根据原始空间中的向量来计算新特征空间中内积的函数称为核函数.在这个例子中核函数为\(\kappa(\mathbf x_1,\mathbf x_2)=(\langle\mathbf x_1,\mathbf x_2\rangle)^2\).
对核函数的选择,现在还缺乏指导原则,实验观察结果表明,某些问题用某些核函数效果很好,用另一些就很差,但是一般来讲,径向基核函数是不会出太大偏差的一种,首选.
采用核方法,能够很方便地产生非线性分类边界。
- linear,线性核,会产生线性分类边界。一般来说它的计算效率最高,而且需要数据最少。
- poly ,多项式核,\(K(x, z) = (x^T z+c)^ d\),会产生多项式分类边界,映射后特征维度为\({n+d\choose d}\)
- rbf,是根据与每一个支持向量的距离来决定分类边界的。\(K(x, z) = \exp\big(-{\|x-z\|^2\over 2\sigma^2}\big)\),类似于高斯分布,因此称为高斯核
函数,也叫做径向基函数(Radial Basis Function 简称 RBF),它能够把原始特征映射到无穷维。它是最灵活的方法,但是也需要最多的数据。比较相似的还有sigmoid 核函数等等。

高斯核更灵活,而且对于训练数据效果是最好的。但是要担心过拟合。
核函数可以看做是对x与z的相似度的衡量.

对新样本进行分类时将式(12)中的内积用核函数计算即可.

核函数有效性判定: K 是有效的核函数 <=> 核函数矩阵 K 是对称半正定的。

核函数不仅仅用在 SVM 上,但凡在一个模型后算法中出现了< x, z >,我们都可以常使用K(x, z)去替换,这可能能够很好地改善我们的算法。

正则化与非线性可分情况处理

在将数据映射到高维后可能仍然不是线性可分的,即时是线性可分的,超平面也易受离群点的影响,难以确定这个超平面是否是我们想要的.

这时候我们应该允许一些点游离并且在模型中违背限制条件(原先的函数间隔大于 1)。对式(7)进行改变,在限制条件中加入软间隔,目标函数中加入软间隔L1正则项作为惩罚项,得到新的模型如下:
\[\begin{align}\min_{ γ,w,b} &\quad {1\over 2}\|w\|^2+C\sum_{i=1}^m\xi_i \\s.t. &\quad y ^{(i)} (w ^T x^{(i)} + b) ≥ 1-\xi_i, \\&\quad \xi_i\ge 0,\quad i = 1,\dots, m\end{align}\tag {13}\]
目标函数控制了离群点的数目和程度,使大部分样本点仍然遵守限制条件。

多分类

可以选用一对一的方式,在任意两类样本之间设计一个SVM,因此k个类别的样本就需要设计k(k-1)//2个SVM.当对一个未知样本进行分类时,最后得票最多的类别即为该未知样本的类别.

SVM vs Softmax

SVM 和 softmax 均能完成多类别的分类任务,但其分类输出的打分值意义不同。其中 SVM 输出的数值大小仅仅表示所属类别的概率排序结果,该数字的绝对值大小没有物理意义。而 softmax 分类器的打分值表明该类别的概率。
SVM 的处理样本时是只考虑支持向量去学习分类器,而 softmax 通过非线性映射的方式减小了远离分类平面的样本点的权重,相对提升了近分类样本点的权重,二者本质思路上是一致的。SVM 和 softmax 并没有孰优孰劣的区分,但 SVM 过程中将原问题转化为对偶问题后,计算只需要支持向量的样本点,对于复杂的问题,利用核函数后能够极大的简化模型和计算工作量。

与神经网络的结合

在训练阶段训练 VGG、AlexNet 等模型时在最后层采用 softmax 分类器。
测试时将网络模型的最后的特征作为样本单独训练一个 SVM 分类器。
对未知样本进行分类预测时先经过网络提取特征再将特征经过SVM分类。
目前主流的模型中也没有没有明确的指出 SVM 和 softmax 分类器的绝对优势。因此在不追求绝对精度的情况下,二者均可以作为模型的分类器使用。


上一篇:A记录和CNAME记录的区别
下一篇:最优Django环境配置

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款