A glimpse of Support Vector Machine

  • 时间:
  • 浏览:0
  • 来源:彩神大发快3_神彩大发快3官方

 

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

 

就都时需了。原来做的好处有:

 

 

其他 高斯核函数是目前最主流的核函数,全都有在这里以其举例介绍:

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

则满足 ,

    于是.我都都来到了svm的核心思想 —— 寻找有好几条 超平面,使其到数据点的间隔最大。因为主全都我原来的超平面分类结果较为稳健(robust),对于最难分的数据点(即离超平面最近的点)并能有足够大的确信度将它们分开,因而泛化到新数据点效果较好。

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

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

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

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

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

 

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

其中w为优化变量,为了解你是什么间题报告 ,引入广义拉格朗日函数:

下图显示加入了有好几条 离群点后,超平面所处了很大的变动,最后形成的间隔变得很小,原来最终的泛化效果其他 不让太好。

    比如上左图的红线和紫线真是能将两类数据完美分类,但注意到这有好几条 超平面某种非常靠近数据点。以紫线为例,圆点为测试数据,其正确分类为深蓝色,但其他 超平面到数据点的间隔太近,以至于被错分成了黄色。 而上右图中其他 间隔较大,圆点即使比所有蓝点更靠近超平面,最终并能被正确分类。

[9] Wikipedia, Lagrange multiplier

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

 

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

SMO算法的基本思路是:选者有好几条 变量α1和α2,固定其他所有α,针对这有好几条 变量构建二次规划间题报告 ,原来就比原来复杂化的优化间题报告 复杂化全都有。其他 有约束条件  ,固定了其他α后,可得 。全都有α1选者后,α2即可自动获得,该间题报告 中的有好几条 变量会一同更新,再不断选者新的变量进行优化。

原来.我都都就能以较小的计算量防止非线性分类间题报告 ,甚至都是时需知道低维空间的数据是怎么映射到高维空间的,只时需在原来的低维空间计算核函数就行了。

 

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

    然而实际上都时需找到无数个超平面将这两类分开,没人 哪有好几条 超平面是效果最好的呢?

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

 

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

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

 

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

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

这里的下标P意为原始间题报告 (primal problem),若w违反了其他原始间题报告 的约束条件(即所处某个i,使得gi(w) > 0 或 hi(w) ≠ 0),没人 都是

/

在svm中.我都都的原始间题报告 :

 

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

 

其他 当样本量非常大时,线性核的层厚要远高于其他核函数,在实际间题报告 中你是什么点其他 变得非常重要。scikit-learn的LinearSVC库计算量和样本数线性相关,时间复杂化度约为O(m× n),而SVC库的时间复杂化度约为O(m2×n)到O(m3×n),当样本量很大时训练层厚会变得太快了 ,其他 使用非线性核的svm不大适合样本量非常大的情景。下表总结了scikit-learn中的svm分类库:

机器学习的一大任务全都我分类(Classification)。如下图所示,假设有好几条 二分类间题报告 ,给定有好几条 数据集,中间所有的数据都完后 被标记为两类,能很容易找到有好几条 超平面(hyperplane)将其完美分类。

 

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

考虑有好几条 “原始间题报告 ”:

前几节展示的硬间隔和软间隔svm主全都我用于防止线性分类间题报告 ,然而现实中全都有分类间题报告 是非线性的,如下图所示,无论怎么有好几条 线性超平面都无法很好地将样本点分类:

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

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

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

 

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

  

 

求解后的分离超平面为:

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

 

其他 .我都都的目标是间隔最大化,其他 间题报告 转化为:

于是,

    全都有在上述二分类间题报告 中,其他 新数据被分类的准确率高,都时需认为是“效果好”,其他 说有较好的泛化能力。其他 这里的间题报告 就转化为:上图中哪有好几条 超平面对新数据的分类准确率最高?

 

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

由上式都时需看出:

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

 

 

 直接计算 复杂化化,其他 若能找到有好几条 核函数 ,则最后变为:

 

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

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

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

    全都有,在你是什么间题报告 上.我都都能做的,也还并能并能 提出假设,建立模型,验证假设。而在svm中,你是什么假设全都我:拥有最大间隔的超平面效果最好。

因而极小化间题报告     与“原始间题报告 ”全都我等价的,其他 还并能并能 当w满足原始优化条件时,。为了方便,定义原始间题报告 的最优值为

 

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

都时需看出转换后向量的内积等于原向量内积的平方,即 

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

 

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

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

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

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

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

 

则α2new = -k = α2old 1old。但其他 α2new时需在[0,C],若α2old 1old <0,则α2new 时需等于0,其他 α2new的下界 L=max(0, α2old 1old)。

函数被称为二次多项核函数,于是其他 想计算高维形态空间的内积 ,.我都都只需计算核函数,即原向量内积的平方  

假设做有好几条 2维到3维的映射,

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

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

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

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

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

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

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

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

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

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

核函数的主要作用是将样本从原始空间映射到有好几条 更高维的形态空间,使得样本在你是什么形态空间内线性可分。下图显示原来在二维空间不可分的两类样本点,在映射到三维空间后变为线性可分 :

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

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

该式也可写为:

 

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

定义超平面:

 

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

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

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

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

   

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

 

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

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

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

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

 

 

再由  即可求得α1new,原来α1和α2就一同得到了更新。

比如下图就无法找到有好几条 超平面将蓝点和紫点完整性分开:

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

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

于是分离超平面全都我:      

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

原始间题报告 和对偶间题报告 的关系都时需用下式表示:

 

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

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

 

[3] Andrew Ng. cs229 Lecture notes 3

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

[2] 李航.《统计学习方法 》

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

 

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

   , 求  和  的内积:

[6] Andrew W. Moore. Support Vector Machines

  可重写为:    

    然而令人郁闷的是,没人 能确切地回答哪个超平面最好,其他 没人 能把真实世界中的所有数据都拿过来测试。从广义上来说,大偏离 的理论研究都是对真实情形的模拟,譬如.我都都用人均收入来衡量有好几条 国家的人民生活水平,这里的人均收入甚至全都我有好几条 不太接近的近似,其他 不其他 把每个国家中个人的收入都学会英语来一一比较。.我都都的大脑善于把繁琐的细节组合起来并层厚抽象化,形成模型和假设,来逼近真实情形。

则:     

,  

[10] Wikipedia, Radial basis function kernel