SVM可以说是一个很经典的二分类问题,属于有监督学习算法的一种。看过那么多的博客知乎解释SVM我一定要自己总结一篇,加深一下自己的理解。
带着问题去读文章会发现,柳暗花明又一村,瞬间李敏浩出现在眼前的感觉
(1)分界线(决策面)------线性分类
(2)支持向量-------如何找?
(3)分类间隔-------为什么需要最大化间隔,以及如何最大化分类间隔(软间隔、硬间隔等)
(4)拉格朗日乘子法和KKT条件----什么是拉格朗日乘子法和KKT条件,用处是干嘛?(PS:解决凸问题,凸优化的)
(5)对偶问题的求解
(6)序列最小最优化(sequential minimal optimization)SMO算法
SMO(Sequential Minimal Optimization)是针对求解SVM问题的Lagrange对偶问题,一个二次规划式,开发的高效算法。传统的二次规划算法的计算开销正比于训练集的规模,而SMO基于问题本身的特性(KKT条件约束)对这个特殊的二次规划问题的求解过程进行优化。对偶问题中我们最后求解的变量只有Lagrange乘子向量,这个算法的基本思想就是每次都只选取一对,固定向量其他维度的元素的值,然后进行优化,直至收敛。
(7)核函数------什么是核函数,为什么要用到核函数?
(8)SVM与LR(Logistic Regression)的区别
--------------机器学习中提到的向量没做特殊说明都是指列向量----------
SVM要解决的问题可以用一个经典的二分类问题加以描述,如下图所示红色和蓝色的二维数据点显然是可以被一条直线分开的,在模式识别领域称为线性可分问题。然而将两类数据点分开的直线显然不止一条。图1(b)和(c)分别给出了A、B两种不同的分类方案,其中黑色实线为分界线,术语称为“决策面”。(---解答了(1)问题---)每个决策面对应了一个线性分类器。虽然在目前的数据上看,这两个分类器的分类结果是一样的,但如果考虑潜在的其他数据,则两者的分类性能是有差别的。
SVM算法认为图1中的分类器A在性能上优于分类器B,其依据是A的分类间隔比B要大。这里涉及到第一个SVM独有的概念“分类间隔”。在保证决策面方向不变且不会出现错分样本的情况下移动决策面,会在原来的决策面两侧找到两个极限位置(越过该位置就会产生错分现象),如虚线所示。虚线的位置由决策面的方向和距离原决策面最近的几个样本的位置决定。而这两条平行虚线正中间的分界线就是在保持当前决策面方向不变的前提下的最优决策面。两条虚线之间的垂直距离就是这个最优决策面对应的分类间隔。显然每一个可能把数据集正确分开的方向都有一个最优决策面(有些方向无论如何移动决策面的位置也不可能将两类样本完全分开),而不同方向的最优决策面的分类间隔通常是不同的,那个具有“最大间隔”的决策面就是SVM要寻找的最优解。而这个真正的最优解对应的两侧虚线所穿过的样本点,就是SVM中的支持样本点,称为“支持向量”。对于图1中的数据,A决策面就是SVM寻找的最优解,而相应的三个位于虚线上的样本点在坐标系中对应的向量就叫做支持向量(---解答了(2)问题)。
从表面上看,我们优化的对象似乎是这个决策面的方向和位置。但实际上最优决策面的方向和位置完全取决于选择哪些样本作为支持向量。而在经过漫长的公式推导后,你最终会发现,其实与线性决策面的方向和位置直接相关的参数都会被约减掉,最终结果只取决于样本点的选择结果。
到这里,我们明确了SVM算法要解决的是一个最优分类器的设计问题。既然叫作最优分类器,其本质必然是个最优化问题。所以,接下来我们要讨论的就是如何把SVM变成用数学语言描述的最优化问题模型,这就是我们在第二部分要讲的“线性SVM算法的数学建模”。
*关于“决策面”,为什么叫决策面,而不是决策线?好吧,在图1里,样本是二维空间中的点,也就是数据的维度是2,因此1维的直线可以分开它们。但是在更加一般的情况下,样本点的维度是n,则将它们分开的决策面的维度就是n-1维的超平面(可以想象一下3维空间中的点集被平面分开),所以叫“决策面”更加具有普适性,或者你可以认为直线是决策面的一个特例。
---------------------线性SVM的算法建模---------------------
一个最优化问题通常有两个最基本的因素:1)目标函数,也就是你希望什么东西的什么指标达到最好;2)优化对象,你期望通过改变哪些因素来使你的目标函数达到最优。在线性SVM算法中,目标函数显然就是那个“分类间隔”,而优化对象则是决策面。所以要对SVM问题进行数学建模,首先要对上述两个对象(“分类间隔”和“决策面”)进行数学描述。按照一般的思维习惯,我们先描述决策面。
------决策面方程
请你暂时不要纠结于n维空间中的n-1维超平面这种超出正常人想象力的情景。我们就老老实实地看看二维空间中的一根直线,我们从初中就开始学习的直线方程形式很简单。
-------分类“间隔”的计算模型
间隔的大小实际上就是支持向量对应的样本点到决策面的距离的二倍,如上图所示:
所以分类间隔计算似乎相当简单,无非就是点到直线的距离公式(点到线的距离公式推导如左下图)
----------->
故根据上述推导公式可以得出上图右边的距离公式6。
这里是向量的模,表示在空间中向量的长度,就是支持向量样本点的坐标。就是决策面方程的参数。而追求W的最大化也就是寻找d的最大化。看起来我们已经找到了目标函数的数学形式。
优化的数据集是线性可分的前提下得到的最大化d,称为硬间隔(hard margin)最大化。(即d表示硬间隔)
如果数据集 X线性不可分,不存在满足约束条件的样本,会导致优化问题没有可行解;为使SVM适用于线性不可分的数据集,需要对目标函数和约束条件进行修改,最终得到的优化问题,称为软间隔(soft margin)最大化。
参照博客:https://zhuanlan.zhihu.com/p/60743894
--------------------以上至此我们只是明白了如何求解分界线的一个过程,下边才是添加约束条件优化的过程
1)并不是所有的方向都存在能够实现100%正确分类的决策面,我们如何判断一条直线是否能够将所有的样本点都正确分类?
2)即便找到了正确的决策面方向,还要注意决策面的位置应该在间隔区域的中轴线上,所以用来确定决策面位置的截距也不能自由的优化,而是受到决策面方向和样本点分布的约束。
3)即便取到了合适的方向和截距,公式(6)里面的x不是随随便便的一个样本点,而是支持向量对应的样本点。对于一个给定的决策面,我们该如何找到对应的支持向量?
以上三条的本质是“约束条件”,也就是说我们要优化的变量的取值范围受到了限制和约束。事实上约束条件一直是最优化问题里最让人头疼的东西。但既然我们已经论证了这些约束条件确实存在,就不得不用数学语言对他们进行描述。尽管上面看起来是3条约束,但SVM算法通过一些巧妙的小技巧,将这三条约束条件融合在了一个不等式里面。
那么这两个不等式再分别乘以他们的标签会怎么样?是不是可以统一为了(这也是为什么SVM在使用之前为什么要把两类标签设置为+1,-1,而不是0,1等等之类的了)
这里m是样本点的总个数,公式(2.14)描述的是一个典型的不等式约束条件下的二次型函数优化问题,同时也是支持向量机的基本数学模型。
在求取有约束条件的优化问题时,拉格朗日乘子法(Lagrange Multiplier)和KKT条件是非常重要的两个求取方法,对于等式约束的优化问题,可以应用拉格朗日乘子法去求取最优解;如果含有不等式约束可以应用KKT条件去求取。当然这两个方法求的的结果只是必要条件,只有当是凸函数的情况下,才能保证是充分必要条件。KKT条件是拉格朗日乘子法的泛化,
-----------------------------接下来是如何利用最优化技术求解公式(2.14)描述的问题--------------
-----------拉格朗日乘子法
首先来了解拉格朗日乘子法,为什么需要拉格朗日乘子法呢?记住,有需要拉格朗日乘子法的地方,必然是一个组合优化问题。拉格朗日乘子法,是寻找多元函数在一组约束(可以是等式约束也可以是不等式约束)下的极值的方法。通过引入拉格朗日乘子,将d个变量与k的约束条件的有约束优化问题转化为d+k个变量的无约束优化问题。那么带约束的优化问题很好说,就比如说下面这个:
在无约束优化问题中,如果一个函数是凸函数,那么总能通过求偏导等于0的方法求得函数的全局极小值点。如果不是凸函数,可能会陷入局部极小值点
约束条件分为等式约束和不等式约束。
构造拉格朗日函数其实就是:目标函数+λ倍的约束条件,然后对变量及λ求偏导,这样就能求出极值。(这只是一种构造方式,这种方式本身是没有意义的,但它可以使求条件极值的步骤变得相对简单方便一些,所以大家倾向于使用构造拉格朗日函数这种方式来求条件极值);拉格朗日函数用来求解等式约束的最优化问题;广义拉格朗日函数用来求解不等式约束的最优化问题。拉格朗日对偶:将最小化问题怎么变成了最大化问题。
拉格朗日乘子法:就是将约束条件整合到目标函数里面去。KKT(Karush–Kuhn–Tucker conditions)条件:如果约束条件是不等式的话,需要用到KKT去解决。
首先定义原始目标函数,拉格朗日乘子法的基本思想是把约束条件转化为新的目标函数的一部分,从而使有约束优化问题变成我们习惯的无约束优化问题。那么该如何去改造原来的目标函数使得新的目标函数的最优解恰好就在可行解区域中呢?这需要我们去分析可行解区域中最优解的特点。
我们观察上图中的红色虚线(可行解空间)和蓝色虚线(目标函数的等值线),发现这个被约束的最优解恰好在二者相切的位置。此处先引入一个梯度(梯度可以直观的认为是函数的变化量,可以描述为包含变化方向和变化幅度的一个向量)。
(1)在相遇点处即在等式约束条件下的优化问题的最优解即上图中的A点,原始目标函数的梯度向量必然与约束条件的切线方向垂直。
(2)函数的梯度方向也必然与函数自身等值线切线方向垂直。
与推论1 的论证基本相同,如果的梯度方向不垂直于该点等值线的切线方向,就会在等值线上有变化,这条线也就不能称之为等值线了。
根据(1)和(2),函数的梯度方向在点同时垂直于约束条件和自身的等值线的切线方向,也就是说函数的等值线与约束条件曲线在点具有相同(或相反)的法方向,所以他们在该点也必然相切。
到此我们可以将目标函数和约束条件视为两个具有平等地位的函数,可以得到如下推论:
---构造拉格朗日函数
我们按照本节初提到的思想,构造一个拉格朗日函数,将有约束优化问题转为无约束优化问题。拉格朗日函数具体形式如下:
新的拉格朗日目标函数有两个自变量下,根据我们熟悉的求解无约束优化问题的思路,将公式(3.3)分别对求导,令结果等于零,就可以建立两个方程。同学们可以自己试一下,很容易就能发现这两个由导数等于0构造出来的方程正好就是公式(3.1)和(3.2)。说明新构造的拉格朗日目标函数的优化问题完全等价于原来的等式约束条件下的优化问题。如下是构造过程:
这就是为什么构造拉格朗日目标函数可以实现等式约束条件下目标优化问题的求解。
-----那么问题来了?哈哈;如果约束条件是不等式怎么办?这个时候就要用到神秘的KKT条件了......(KKT条件
是一个线性规划问题能有最优解的
充分和必要条件。)
-------------------------------KKT条件--------------(约束条件为不等式,应用KKT条件去求取最优解)
对于不等式约束条件的情况,如下图所示,最优解所在的位置有两种可能,或者在边界曲线上或者在可行解区域内部满足不等式的地方。
第一种情况:最优解在边界上,就相当于约束条件就是。参考图4,注意此时目标函数的最优解在可行解区域外面,所以函数在最优解附近的变化趋势是“在可行解区域内侧较大而在区域外侧较小”,与之对应的是函数在可行解区域内小于0,在区域外大于零,所以在最优解附近的变化趋势是内部较小而外部较大。这意味着目标函数的梯度方向与约束条件函数的梯度方向相反。因此根据公式(3.1),可以推断出参数。
不等式约束条件下最优解位置分布的两种情况
第二种情况:如果在区域内,则相当于约束条件没有起作用,因此公式(3.3)的拉格朗日函数中的参数。整合这两种情况,可以写出一个约束条件的统一表达,如公式(3.4)所示。
下面对上式解释:
KKT条件的第一式:原来的约束条件
KKT条件的第二式:lambda>=0就是上面说的两个力方向相反,即梯度的方向相反
KKT条件的第三式:若最优点在约束平面内部,则lambda=0,约束条件无用
若最优点在约束平面的边界,g(x)=0
其中第一个式子是约束条件本身。第二个式子是对拉格朗日乘子的描述。第三个式子是第一种情况和第二种情况的整合:在第一种情况里,;在第二种情况下,。所以无论哪一种情况都有。公式(3.4)就称为Karush-Kuhn-Tucker条件,简称KKT条件。
推导除了KKT条件,感觉有点奇怪。因为本来问题的约束条件就是一个,怎么这个KKT条件又多弄出来两条,这不是让问题变得更复杂了吗?这里我们要适当的解释一下:
1)KKT条件是对最优解的约束,而原始问题中的约束条件是对可行解的约束。
2)KKT条件的推导对于后面马上要介绍的拉格朗日对偶问题的推导很重要。
---可以将KKT条件推广到多约束条件下(同时含有等式约束和不等式约束):
h(x) 是等式约束。g(x)是不等式约束。m,n表示约束的数量。
-----------------拉格朗日对偶--------------
按照前面等式约束条件下的优化问题的求解思路,构造拉格朗日方程的目的是将约束条件放到目标函数中,从而将有约束优化问题转换为无约束优化问题。我们仍然秉承这一思路去解决不等式约束条件下的优化问题,那么如何针对不等式约束条件下的优化问题构建拉格朗日函数呢?
因为我们要求解的是最小化问题,所以一个直观的想法是如果我能够构造一个函数,使得该函数在可行解区域内与原目标函数完全一致,而在可行解区域外的数值非常大,甚至是无穷大,那么这个没有约束条件的新目标函数的优化问题就与原来有约束条件的原始目标函数的优化是等价的问题。
拉格朗日对偶问题其实就是沿着这一思路往下走的过程中,为了方便求解而使用的一种技巧。于是在这里出现了三个问题:1)有约束的原始目标函数优化问题;2)新构造的拉格朗日目标函数优化问题;3)拉格朗日对偶函数的优化问题。我们希望的是这三个问题具有完全相同的最优解,而在数学技巧上通常第三个问题——拉格朗日对偶优化问题——最好解决。所以拉格朗日对偶不是必须的,只是一条捷径。
1)原始目标函数(有约束条件)
为了接下来的讨论,更具有一般性,我们把等式约束条件也放进来,进而有约束的原始目标函数优化问题重新给出统一的描述:
公式(3.5)表示m个等式约束条件和n个不等式约束条件下的目标函数的最小化问题。
新构造的目标函数(没有约束条件)
此时我们回想最初构造新目标函数的初衷,就是为了建立一个在可行解区域内与原目标函数相同,在可行解区域外函数值趋近于无穷大的新函数。看看公式(3.11)We did it。
现在约束条件已经没了,接下来我们就可以求解公式(3.12)的问题
这个问题的解就等价于有约束条件下的原始目标函数最小化问题(公式3.5)的解。
-----对偶问题--
啥是对偶?
对于原问题(1)我们通常用拉格朗日对偶的方式来求解。啥是对偶?对偶说白了就是实质相同但从不同角度提出不同提法的一对问题。有时候原问题 (Primal Problem) 不太好解,但是对偶问题 (Dual Problem) 却很好解,我们就可以通过求解对偶问题来迂回地解答原问题。
在这里我们用的是拉格朗日对偶的方法来解决,既然我们说用对偶的方法的原因在于原问题不好解,那么这里也是如此吗?
当然了。
首先我们来看看原问题有什么难的地方:
约束条件太多
很显然约束越多,问题就越难解决,原问题中总共有 k+1个约束,相当麻烦
原问题凹凸性不明确
之前我们说过,“不假定原函数 f的凹凸性”,这就意味着我们无法将凸优化的方法应用在原问题中
那么它的拉格朗日对偶问题有什么优点呢?(其实就是一个思想将复杂问题反向简单化计算)
只有一个约束
拉格朗日对偶问题一定是凹的
这里先做一个感性的认识,细节方面接下来慢慢说。
对比公式(3.13)和(3.14),发现两者之间存在一种对称的美感。所以我们就把(3.14)称作是(3.13)的对偶问题。现在我们可以解释一下中的P是原始问题Primary的缩写,中的D是对偶问题Dual的缩写。如果我们能够想办法证明(3.14)和(3.13)存在相同的解,那我们就可以在对偶问题中选择比较简单的一个来求解。
4)对偶问题同解的证明 见:https://zhuanlan.zhihu.com/p/24638007
----------SVM与LR的比较-------------
LR的详细介绍:https://blog.csdn.net/b285795298/article/details/88683987
相同点:
- LR和SVM都是分类算法
- LR和SVM都是监督学习算法。
- LR和SVM都是判别模型。
- 如果不考虑核函数,LR和SVM都是线性分类算法,也就是说他们的分类决策面都是线性的。
说明:LR也是可以用核函数的.但LR通常不采用核函数的方法.(计算量太大)
不同点:
1、LR采用log损失,SVM采用合页(hinge)损失。
逻辑回归的损失函数: 支持向量机的目标函数:
逻辑回归方法基于概率理论,假设样本为1的概率可以用sigmoid函数来表示,然后通过极大似然估计的方法估计出参数的值(基于统计的,其损失函数是人为设定的凸函数) 。支持向量机基于几何间隔最大化原理,认为存在最大几何间隔的分类面为最优分类面。
2、LR对异常值敏感,SVM对异常值不敏感(抗燥能力,SVM要强)
支持向量机只考虑局部的边界线附近的点,而逻辑回归考虑全局(远离的点对边界线的确定也起作用,虽然作用会相对小一些)。LR模型找到的那个超平面,是尽量让所有点都远离他,而SVM寻找的那个超平面,是只让最靠近中间分割线的那些点尽量远离,即只用到那些支持向量的样本。
(1)支持向量机改变非支持向量样本并不会引起决策面的变化: (2)逻辑回归中改变任何样本都会引起决策面的变化:
LR则受所有数据点的影响,如果数据不同类别strongly unbalance,一般需要先对数据做balancing。(引自http://www.zhihu.com/question/26768865/answer/34078149)
3、计算复杂度不同。对于海量数据,SVM的效率较低,LR效率比较高。 对于两者在feature和样本数量不同的情况下的效率问题,可以参考:https://blog.csdn.net/a244659184/article/details/81122521。该文章说明了:
当样本较少,特征维数较低时,SVM和LR的运行时间均比较短,SVM较短一些。准确率的话,LR明显比SVM要高。当样本稍微增加些时,SVM运行时间开始增长,但是准确率赶超了LR。SVM时间虽长,但在接收范围内。当数据量增长到20000时,特征维数增长到200时,SVM的运行时间剧烈增加,远远超过了LR的运行时间。但是准确率却和LR相差无几。(这其中主要原因是大量非支持向量参与计算,造成SVM的二次规划问题)
4、对非线性问题的处理方式不同,LR主要靠特征构造,必须组合交叉特征,特征离散化。SVM也可以这样,还可以通过kernel(因为只有支持向量参与核计算,计算复杂度不高)。(由于可以利用核函数,。SVM则可以通过对偶求解高效处理。LR则在特征空间维度很高时,表现较差。)
5、SVM的损失函数就自带正则!!!(损失函数中的1/2||w||^2项),这就是为什么SVM是结构风险最小化算法的原因!!!而LR必须另外在损失函数上添加正则项!!!
关于正则化:
给定一个数据集,一旦完成Linear SVM的求解,所有数据点可以被归成两类
1)一类是落在对应分界平面外并被正确分类的点,比如落在正分界左侧的正样本或落在负分界右侧的负样本
2)第二类是落在gap里或被错误分类的点。
假设一个数据集已经被Linear SVM求解,那么往这个数据集里面增加或者删除更多的一类点并不会改变重新求解的Linear SVM平面。这就是它区分与LR的特点,下面我们在看看LR。
值得一提的是求解LR模型过程中,每一个数据点对分类平面都是有影响的,它的影响力远离它到分类平面的距离指数递减。换句话说,LR的解是受数据本身分布影响的。在实际应用中,如果数据维度很高,LR模型都会配合参数的L1 regularization。
要说有什么本质区别,那就是两个模型对数据和参数的敏感程度不同,Linear SVM比较依赖penalty的系数和数据表达空间的测度,而(带正则项的)LR比较依赖对参数做L1 regularization的系数。但是由于他们或多或少都是线性分类器,所以实际上对低维度数据overfitting的能力都比较有限,相比之下对高维度数据,LR的表现会更加稳定,为什么呢?
因为Linear SVM在计算margin有多“宽”的时候是依赖数据表达上的距离测度(可以理解为度量标准,即在什么样的标准上计算gap的大小)的,换句话说如果这个测度不好(badly scaled,这种情况在高维数据尤为显著),所求得的所谓Large margin就没有意义了,这个问题即使换用kernel trick(比如用Gaussian kernel)也无法完全避免。所以使用Linear SVM之前一般都需要先对数据做normalization,(这里的normalization是对数据的归一化,注意区分之前的LR在类别不平衡的时候做的balancing)而求解LR(without regularization)时则不需要或者结果不敏感。
同时会有:feature scaling会使得gradient descent的收敛更好。
如果不归一化,各维特征的跨度差距很大,目标函数就会是“扁”的:
(图中椭圆表示目标函数的等高线,两个坐标轴代表两个特征)
这样feature scaling之后,在进行梯度下降的时候,梯度的方向就会偏离最小值的方向,走很多弯路。
如果归一化了,那么目标函数就“圆”了:如上图。每一步梯度的方向都基本指向最小值,可以大踏步地前进。(引自https://www.zhihu.com/question/37129350
-------核函数--------
另搞一篇吧,觉得这个再也到不了头了