A glimpse of Support Vector Machine

  • 时间:
  • 浏览:1
  • 来源:大发5分3DAPP下载_大发5分3DAPP官方

上述优化问题报告 的解为间隔最大时的w和b,随即可求出超平面 

 

 将原始空间映射到高维形态学 空间后变为:

    而是 在上述二分类问题报告 中,肯能新数据被分类的准确率高,都可不都里能认为是“效果好”,肯能说有较好的泛化能力。而且这里的问题报告 就转化为:上图中哪有有另一个超平面对新数据的分类准确率最高?

求出上式中的α后,即可求得原始问题报告 中的w和b,进而获得分离超平面。

第二节中提到样本空间任意点x到超平面的距离为:,下面给出证明:

其中w为优化变量,为了解這個 问题报告 ,引入广义拉格朗日函数:

    然而实际不都可不都里能找到无数个超平面将这两类分开,没了哪有有另一个超平面是效果最好的呢?

[8] Chih-Jen Lin, etc. A Practical Guide to Support Vector Classification

 

都可不都里能看出转换后向量的内积等于原向量内积的平方,即 

另外肯能有不等式约束,  需满足下列Karush-Kuhn-Tucker (KKT)条件 :

   , 求  和  的内积:

若将式中 [1-y(wx+b)]+ 替换为对率损失(logistic loss): log[1+exp(-y(wx+b))],则成为了Logistic Regression的损失函数。下图显示出二者的关系:

在svm中朋友的原始问题报告 :

 

前几节展示的硬间隔和软间隔svm主也前会于外理线性分类问题报告 ,然而现实中而是 分类问题报告 是非线性的,如下图所示,无论怎么才能 才能 有有另一个线性超平面都无法很好地将样本点分类:

上述优化问题报告 同样可使用拉格朗日乘子法:

log[1+exp(-y(wx+b))] 始终不为0,但当样本点远离其决策边界时,损失就会变得非常接近0。

都可不都里能用通用的二次规划算法求解,但现实中当训练样本容量很大时,往往求解非常低效。而是 本节介绍的SMO(sequential minimal optimization)算法而是高效求解上述问题报告 的算法之一。

 

于是分离超平面而是:      

[1-y(wx+b)]+ 也可写为 max(0, 1-y((wx+b)),该损失函数被称为Hinge Loss。

 

 

上图中距离超平面最近的有有另一个点(即支持向量)满足 |wTx+b| = 1,又由样本空间任意点x到超平面的距离:, 而且所有数据点的最小间隔为

[6] Andrew W. Moore. Support Vector Machines

[7] Pang-Ning Tan, etc. Introduction to Data Mining

上图中超平面为: ,假设x1和x2都有超平面上,则有 wTx1+b = wTx2+b, wT(x1-x2)=0,即法向量w与超平面上任意向量正交。

 

    然而令人懊恼的是,没了能确切地回答哪个超平面最好,肯能没了能把真实世界中的所有数据都拿过来测试。从广义上来说,大累积的理论研究都有对真实状况的模拟,譬如朋友用人均收入来衡量有有另一个国家的人民生活水平,这里的人均收入甚至而是有有另一个不太接近的近似,肯能不肯能把每个国家中每每每人个的收入都读懂来一一比较。朋友的大脑善于把繁琐的细节组合起来并层厚抽象化,形成模型和假设,来逼近真实状况。

 

比如下图就无法找到有有另一个超平面将蓝点和紫点全部分开:

    要回答這個 问题报告 ,首先就要定义哪几个叫做“效果好”?在面临机器学习问题报告 的事先普遍都有很关心训练数据的分类正确否有,而是关心有有另一个新数据出显的事先其都可不都里能被模型正确分类。举个上学的例子(这里主要指理科),训练数据就像是平时的作业和小测验+答案,新数据则像是期末大考或中高考。作业和小测验有答案的帮助下做得很好,朋友自然很高兴,但扪心自问,做作业和小测验的目的是为了在这之中取得好成绩吗?觉得 本质上都有的,作业和小测验的目的是为了训练朋友的“大脑模型”,以备在期末大考和联 高考中取得好成绩,继而走上人生巅峰。而是 在做作业和小测验的事先,重要的是训练有一种解题的思路,使之充分熟练进而能举一反三,在真正的大考中灵活地运用哪几个思路获得好成绩。此类状况用机器学习的说法而是這個 “大脑模型”有较好的泛化能力,而相应的“过拟合”则指的是平时做题总要,一到关键大考就掉链子的行为。造成此类“过拟合”的由于 之而是 有而是 种,但其中之一恐怕而是平时不训练清楚思路、一直死记硬背、以至把答案中的“噪音”也学进去了。

该式称为原始问题报告 的对偶问题报告 ,定义其最优值为 

上一节求解出来的间隔被称为“硬间隔(hard margin)“,其都可不都里能将所有样本点划分正确且都有间隔边界之外,即所有样本点都满足

求解后的分离超平面为:

在上一节中,最后的对偶问题报告 为:  

则α2new = -k = α2old 1old。但肯能α2new都要在[0,C],若α2old 1old <0,则α2new 都要等于0,而且α2new的下界 L=max(0, α2old 1old)。

[4] Hastie, etc. An Introduction to Statistical Learning

 

    而是 ,在這個 问题报告 上朋友能做的,也都可不都里能提出假设,建立模型,验证假设。而在svm中,這個 假设而是:拥有最大间隔的超平面效果最好。

 

原始问题报告 和对偶问题报告 的关系都可不都里能用下式表示:

因而极小化问题报告     与“原始问题报告 ”而是等价的,肯都可不都里能当w满足原始优化条件时,。为了方便,定义原始问题报告 的最优值为

LibSVM的作者,国立台湾大学的林智仁教授在其一篇小文(A Practical Guide to Support Vector Classification)中提出了svm库的一般使用流程 :

肯能高斯核函数是目前最主流的核函数,而是 在这里以其举例介绍:

/

则满足 ,

若要满足强对偶性(strong duality),即 ,则需满足Slater条件: f(w)和g(w)都有凸函数,h(w)是仿射函数,而且居于w使得所有的不等式约束g(w)<0成立。

于是,

 

也即是说,对于svm的hinge loss而言,肯能样本点被正确分类且在间隔边界之外,即wx + b >1,则[1-y(wx+b)] +=0,损失为0。若样本点即使被正确分类,但居于超平面和间隔边界之间,由于 分类正确的确信度过低高,因而损失不为0。而对于logistic regression来说,所有的样本点总要有损失,肯能其损失函数

就都可不都里能了。曾经做的好处有:

 

核函数是怎么才能 才能 将原始空间映射到高维的形态学 空间的? 下面先举个例子:

以上左图为例,假设要求α2的最小值,令α1等于0,由α12 =k,

将上两式代入拉格朗日函数,即可得对偶问题报告 的新形式:

 

 

SMO采用启发式的变量选则最好的办法:第有有另一个变量α1,一般选则训练样本中违反KKT条件最严重的样本点所对应的α。而第有有另一个变量α2则选则与α1的样本点之间间隔最大的样本点对应的α,曾经二者的更新往往会给目标函数带来更大的变化。

B点为A点到超平面的投影, 为垂直于超平面的单位向量,γ为A到超平面的算术距离,A点为 x(i),则B点为  ,代入 得:

 

肯能一点变量αi (i=3,4…N)都有固定的,而是 有 ,其中为常数。又有约束 ,且y1,y2都可不都里能取值+1或-1,而是 α1,α2的直线平行于[0,C]×[0,C]形成的对角线。

机器学习的一大任务而是分类(Classification)。如下图所示,假设有有另一个二分类问题报告 ,给定有有另一个数据集,上方所有的数据都事先被标记为两类,能很容易找到有有另一个超平面(hyperplane)将其完美分类。

 

这时原始问题报告 和对偶问题报告 的最优解相同,可用解对偶问题报告 替代解原始问题报告 。

 直接计算 比较比较复杂,而且若能找到有有另一个核函数 ,则最后变为:

高斯核函数可理解为有有另一个样本点的例如程度,两点(x, x’)的距离  越大,越小,则有有另一个点的例如程度很小,这由于 高斯核具有“局部(local)”形态学 ,都可不都里能相对邻近的样本点会对测试点的分类产生较大作用。 ,即为scikit-learn中的svm超参数 γγ 越大,由于 有有另一个点都可不都里能相当接近时才会被判为例如,曾经决策边界会变得较为扭曲,容易过拟合,肯能只取决于较少的几个样本点。相反,γ 越小,小量的点被判为近似,因而由于 模型变得简单,容易欠拟合。

再由  即可求得α1new,曾经α1和α2就一并得到了更新。

这里的下标D意为对偶(dual),接着考虑其极大化问题报告 :

肯能朋友的目标是间隔最大化,而且问题报告 转化为:

假设做有有另一个2维到3维的映射,

这里的下标P意为原始问题报告 (primal problem),若w违反了一点原始问题报告 的约束条件(即居于某个i,使得gi(w) > 0 或 hi(w) ≠ 0),没了都有

 

    间隔(margin)指的是所有数据点中到這個 超平面的最小距离。如下图所示,实线为超平面,虚线为间隔边界,黑色箭头为间隔,即虚线上的点到超平面的距离。都可不都里能看出,虚线上的有有另一个点(2蓝1红)到超平面的距离都有一样的,实际上都可不都里能这有有另一个点一并决定了超平面的位置,因而它们被称为“支持向量(support vectors)”,而“支持向量机”也由此而得名。

为了缓解哪几个问题报告 ,引入了“软间隔(soft margin)”,即允许一点样本点跨越间隔边界甚至是超平面。如下图中一点离群点就跨过了间隔边界。

 

在w和b的求解公式中,注意到w和b由对应于α> 0的样本点(xi,yi)决定,又由KKT条件中:αi (yi(w•xi+b)-1)=0  ,  yi(w•xi+b)= ±1,而且哪几个样本点(xi,yi)一定在间隔边界上,它们而是“支持向量”,哪几个点一并决定了分离超平面。

    支持向量机(support vector machine, 以下简称svm)是机器学习里的重要最好的办法,怪怪的适用于中小型样本、非线性、高维的分类和回归问题报告 。本篇希望在正篇提供有有另一个svm的简明阐述,附录则提供一点一点内容。(以下各节内容分别来源于不同的资料,在数学符号表述上肯能有差异,望见谅。)

这里采用迭代法,假设上一轮迭代得到的解是α1old和α2old,沿着约束方向未经剪辑时α2的最优解为α2new, unclipped。本轮迭代完成后的解为α1new 和 α2new

同理,上界H = min(C, C+α2old 1old)。

[10] Wikipedia, Radial basis function kernel

拉格朗日乘子法的主要思想是将饱含n个变量和k个约束条件的约束优化问题报告 转化为饱含(n+k)个变量的无约束优化问题报告 。下面阐述其原理 :

   

1. 离群点的松弛变量值越大,点就离得越远。

无论是线性还是非线性svm,最后都有归结为求拉格朗日乘子α的问题报告 。

该式也可写为:

SMO算法的基本思路是:选则有有另一个变量α1和α2,固定一点所有α,针对这有有另一个变量构建二次规划问题报告 ,曾经就比曾经比较复杂的优化问题报告 比较复杂而是 。肯能有约束条件  ,固定了一点α后,可得 。而是 α1选则后,α2即可自动获得,该问题报告 中的有有另一个变量会一并更新,再不断选则新的变量进行优化。

2. 所有没离群的点松弛变量都等于0,即哪几个点都满足

而是 在此引入核函数(kernel function),构造非线性svm,如下图所示,左图使用的是多项式核函数,右图使用的是高斯核函数,二者均能将样本点很好地分类:

考虑有有另一个“原始问题报告 ”:

其中第二步scaling对于svm的整体效果有重大影响。主要原肯能在没了进行scaling的状况下,数值范围大的形态学 会产生较大的影响,进而影响模型效果。

假设二分类问题报告 中正类的标签为+1,负类的标签为 -1,若要找到有有另一个超平面能正确分类所有样本点点,且所有样本点都居于间隔边界上或间隔边界外侧(如上图所示),

但硬间隔有有有另一个缺点:1. 不适用于线性不可分数据集。 2. 对离群点(outlier)敏感。

下图都可不都里能看出在原始空间和高维空间下计算量的巨大差异:

原始问题报告 的对偶问题报告 为:。最好的办法KKT条件,先固定ɑ,令L(w, b, α)对w和b的偏导为0可得,

函数被称为二次多项核函数,于是肯能想计算高维形态学 空间的内积 ,朋友只需计算核函数,即原向量内积的平方  

接下来考虑“对偶问题报告 ”,定义:

则:     

 

 

下图显示加入了有有另一个离群点后,超平面居于了很大的变动,最后形成的间隔变得很小,曾经最终的泛化效果肯能前会太好。

为上方解优化问题报告 方便,上式可重写为:

高斯核(Gaussian Kernel) 属于径向基函数(Radial Basis Function , RBF)的有一种。其表达式  

    于是朋友来到了svm的核心思想 —— 寻找有有另一个超平面,使其到数据点的间隔最大。由于 主而是曾经的超平面分类结果较为稳健(robust),对于最难分的数据点(即离超平面最近的点)都可不都里能有足够大的确信度将它们分开,因而泛化到新数据点效果较好。

于是为每个样本点引入松弛变量 ,优化问题报告 变为:

这是有有另一个凸二次规划(convex quadratic programming)问题报告 ,都可不都里能用现成的软件包计算。然而现实中一般采用对偶算法(dual algorithm),通过求解原始问题报告 (primal problem)的对偶问题报告 (dual problem),来获得原始问题报告 (primal problem)的最优解。曾经做的优点,一是对偶问题报告 往往更容易求解,二是能自然地引入核函数,进而高效的外理高维非线性分类问题报告 。

[1] 周志华.《机器学习》

由上式都可不都里能看出:

运用和上一节同样的最好的办法,分别对w,b, 求偏导,得到对偶问题报告 :

 

 

定义超平面:

第三步中认为应优先试验RBF核,通常效果比较好。但他一并也提到,RBF核前会是万能的,在一点状况下线性核更加适用。当形态学 数非常多,肯能样本数远小于形态学 数时,使用线性核已然足够,映射到高维空间作用不大,而且而是对C进行调参即可。觉得 理论上高斯核的效果前会差于线性核,但高斯核都要更多轮的调参。

 

[2] 李航.《统计学习最好的办法》

求出上式中的α后,即可求得原始问题报告 中的w和b。

但回到曾经的二维空间中,决策边界就变成非线性的了:

 

  

 

 

3. C > 0 被称为惩罚参数,即为scikit-learn中的svm超参数C。当C设的越大,由于 对离群点的惩罚就越大,最终就会有较少的点跨过间隔边界,模型也会变得比较复杂。而C设的越小,则较多的点会跨过间隔边界,最终形成的模型较为平滑。

如正片中所述,scikit-learn中svm库的有有另一个主要超参数为C和γ,C和γ越大,则模型趋于比较复杂,容易过拟合;反之,C和γ越大,模型变得简单,如下图所示:

也可写为 ,范围为(0,1],其中

下面来看怎么才能 才能 解α1和α2

,  

而且当样本量非常大时,线性核的传输强度要远高于一点核函数,在实际问题报告 中這個 点肯能变得非常重要。scikit-learn的LinearSVC库计算量和样本数线性相关,时间比较复杂度约为O(m× n),而SVC库的时间比较复杂度约为O(m2×n)到O(m3×n),当样本量很大时训练传输强度会变得更慢,而且使用非线性核的svm不大适合样本量非常大的情景。下表总结了scikit-learn中的svm分类库:

 

[9] Wikipedia, Lagrange multiplier

核函数的主要作用是将样本从原始空间映射到有有另一个更高维的形态学 空间,使得样本在這個 形态学 空间内线性可分。下图显示曾经在二维空间不可分的两类样本点,在映射到三维空间后变为线性可分 :

[5] Aurélien Géron. Hands-On Machine Learning with Scikit-Learn&TensorFlow

ɑi和βi为拉格朗日乘子,ɑi ≥0,考虑下式:

[3] Andrew Ng. cs229 Lecture notes 3

 

曾经朋友就能以较小的计算量外理非线性分类问题报告 ,甚至都有都要知道低维空间的数据是怎么才能 才能 映射到高维空间的,只都要在曾经的低维空间计算核函数就行了。

 

 

  可重写为:    

由拉格朗日乘子法,为每条约束引进拉格朗日乘子αi ≥ 0,该问题报告 的拉格朗日函数变为:

线性svm还有另有一种解释最好的办法,能揭示出其与一点分类最好的办法(如Logistic Regression)的渊源。线性svm的原始最优化问题报告 :

    比如上左图的红线和紫线觉得 能将两类数据完美分类,但注意到这有有另一个超平面有一种非常靠近数据点。以紫线为例,圆点为测试数据,其正确分类为浅绿色,但肯能超平面到数据点的间隔太近,以至于被错分成了黄色。 而上右图中肯能间隔较大,圆点即使比所有蓝点更靠近超平面,最终都可不都里能被正确分类。