0%

SVM理论

  支持向量机的一些并不算深入的基本数理理论,包含SVM、SVR与LS-SVR。支持向量机具有非常强的数学与统计理论支撑,研究SVM的数理理论对加深对SVM的理解是大有裨益的。


  在我们开始以前,我想谈谈关于我与统计学。作为西南大学数学与统计学院统计系的学生,在修完数学课程如实变函数论、近世代数与泛函分析后,学院相继为全体学生开设了最优化理论、统计计算、多元统计分析与回归分析等多门统计课程,唯独不统一在学院开设机器学习。优化理论与统计计算算法在机器学习中扮演了重要角色,譬如大名鼎鼎的拟牛顿法之代表BFGS算法、用于非凸优化问题的退火算法和遗传算法都有广泛的应用,但修习了这些理论却不开设后续课程实属遗憾,这些理论当然也就没有了用武之地,成了一纸空谈。通过参考多方资料,我在没有教师帮助下独立探索了一些机器学习理论,希望结合数学理论与数理统计学方法,加深对机器学习的理解。本文主题是记录一些我关于“SVM”的想法与感悟,由于才疏学浅,只能做到泛泛而谈,如有纰漏与谬误恳请与我联系。

  个人认为,许多机器学习算法都或隐或明地蕴含了不少的数学与统计思想,如SVM的优化涉及最优化理论与统计计算算法(退火算法、遗传算法),核函数的提出源自Hilbert空间算子理论,正则化与空间息息相关,核方法的理论支持Mercer定理更是一个经典的泛函分析定理。本文大概读者具有一定的回归分析基础、优化理论基础与泛函分析基础时,阅读是没有问题的。

  鹦鹉学舌也好,拾人牙慧也罢,普通学生,普通家庭,确实没有动力与能力独立开创、推广新的理论,这篇文档的意义可能是十年后再回首,说明本科时的我曾经有试图学习些什么过吧。

  为方便表述,记表示范数的算术平方根,即欧氏空间意义下的距离;

  MSE:均方误差,,当估计无偏时,有,即方差之和。MSE综合考虑了无偏性与有效性,是常用的评估标准;

  维空间的超平面:维子空间;

  广义拉格朗日乘子法与KKT条件:用隐函数组定理是容易证明的,在任意一本数学分析与最优化理论教材都有证明过程;

  如无特殊说明,本文用表示样本量大小。

不同分类算法的比较

1. SVM(SVC)

1.1. SVM概论

1.1.1. SVM的思想

  SVM(支持向量机,Support Vector Machine)是一种有监督学习方法,属广义线性分类器家族,其目的是对数据进行二分类,既可以通过寻找一个当前样本空间的分割超平面进行线性分类,也可以通过核方法在更高维空间中寻求高维超平面进行非线性分类,并且可以被应用在回归分析。在我看来,SVM的想法是自然的,这与线性回归中OLS的思路如出一辙。如果说OLS的目的是获得使得RSS最小的估计,则二分类SVM的目的是获得某个超平面,使得其两边支持向量到超平面距离最大且相等。在高斯-马尔可定理条件成立情况设下,线性模型的OLS得到BLUE,误差在MSE意义下最小,对于良好的数据集大部分样本点都应该以较小的距离分布在拟合直线两侧;而SVM试图找出一个高维的超平面,使两类样本距离这个超平面最近的距离相等且最大,如下图所示。显然,三条一维直线中的划分要优于,拥有更强的分类能力。

  但OLS与SVM并非高度一致,在信息利用上有明显的差异:OLS的预测利用了所有的样本(最小化RSS),而SVM只利用到了支持向量,非支持向量的任何改变都不会对结果产生丝毫影响。

关于某地区GDP的一个线性回归 哪条线是我们希望的最佳分类?

1.1.2. SVM在应用中的的优缺点

  SVM在小样本、非线性以及高维模式识别等方面有出色的表现,且容易结合其他方法进行推广应用,在文本、超文本分类与生物、医学及其他科学领域已经有了广泛的运用,一些浅层语义分析也基于SVM,样本量适中而特征数不算多时有很好的分类能力;

  SVM的潜在问题包含,作为彻底的有监督学习、能利用的样本必需有完整的标记(决策树方法不需要),只适用于二分类任务,得到的模型参数难以得到现实意义的解释(业务上线性回归参数便有极强的可解释性,SVM通常不能做到),对缺失数据敏感。

  同时,SVM的优化目标为一个二次凸优化,有良好的凸优化性质(优化算法一定收敛到唯一全局最优解),但这也使得超大样本量情况下SVM求解异常困难,使带有核方法的SVM理论实践复杂度不低于;SVM通过核技巧一定程度避免了维度诅咒,但核技巧不是SVM的专属;对于扁平化数据,选择适合的核函数与正则化方式至关重要,否则非常容易导致过拟合,这是SVM最大的变数。

  与一些神经网络算法不同,SVM目前已有严格的数学与统计理论支持。SVM基于Vapnik 和 Chervonenkis提出的Vapnik-Chervonenkis 理论(下称VC理论)与结构风险最小原理,属于非概率二元线性分类器,并没有严格按照随机抽样的原则抽取样本,无法确定抽样误差,因此大数律与中心极限定理等极限理论也并不适用;同时这令他并没有过分在意样本空间的维数,以至于为了达到非线性分类的目的可以多次升维,而且折中了精度(Accuracy)与学习能力的原理令SVM有较好的泛化能力,但这需要对SVM进行一些改进以达到更好的效果,比如软间隔的方法。

  此外,由于非线性核的SVM理论上时间复杂度不低于,所以对极大的样本量非线性可分情况SVM的训练是困难的(虽然只利用了支持向量,但在确认全部可能的支持向量以前我们并不直到哪些向量是支持向量),因此人们基于SVM理论研究出了多种近似算法,比如CVM、随即傅里叶特征算法、Nyström算法等。

SVM通过映射到高维以达到非线性分类的例子

1.2. 支持向量

  假设我们需要找到的分割超平面为,其中为超平面的法向量(不一定单位化);从空间解析几何角度看,表示超平面的方向,表示位移,即超平面到远点的距离。

  根据空间解析几何理论,样本空间中任意一点到超平面的欧式距离   不妨设因变量取值为,如果超平面能正确对样本进行分类,方便起见,我们希望找到一个超平面,使得当则样本点位于超平面“下方”,;当则样本点位于超平面“上方”,,即   可以将两个不等式综合为一式,方便我们后续解决优化问题(这里也能看出,为什么我们设的值域为);此外,易见在这样的定义下,恒有

  令使得式中任意一不等式等号成立的样本为支持向量(Support Vector),直观上看支持向量全部落在决策边界上,是距离超平面最近的一组样本。当确定,仅与有关,由距离公式与所定义的式得出,支持向量一定满足(当且仅当时距离最小),因此两个互类支持向量到超平面距离之和为,称之为间隔,可以认为间隔是互异决策边界的距离。 间隔的直观展示

1.3. 优化问题

  SVM中一般考虑对直观下约束优化问题的拉格朗日对偶问题优化,相对原优化目标效率更高,这里有一点需要解释,关于为什么我们考虑对偶问题:我们可以不从原问题的对偶问题出发考虑求解,例如线性核SVM的原始优化问题为下文的式,从标准的不等式约束二次规划(QP问题,QP模型)模型来看   令   二次规划当下是非常成熟的理论,对于线性核SVM,线性等式约束下的原优化问题可以通过矩阵直接求解线性方程组,对于线性不等式约束也有内点法、增广拉格朗日函数与梯度投影法等多种方法可用以配合求解,这样可以在不利用对偶问题前提下得到解;。但在引入非线性核函数后,一是可能映射到高维空间后不能保证的正定性,而维数如果足够高时这个问题变成了NP难题,局部最小点也不一定唯一;与此同时,如果我们希望考虑广义的拉格朗日乘子法求解,记广义拉格朗日函数为,这相当于把不等式约束并入了优化目标式中,这时解原优化问题等价于解   这个式子中的作用只是限制原本约束式对优化的影响,对偏导以试图解出   不难看出,我们只得到了一个支持向量,满足,因此原问题的拉格朗日函数优化较为困难;如果我们考虑他的对偶问题,这等价于求解   不过,对偶问题的最优解可能不是原问题最优解,根据优化理论我们有,万幸的是原问题本身就是一个二次规划问题,属于强对偶,所以等号严格成立。关于优化问题将在后文再细致讨论。

  大体上,我们的求解办法是通过优化方法计算出对偶问题的解(即),然后代入KKT条件计算出,再同时将拉格朗日乘子与解得的代入KKT条件的稳定性条件即解出,至此我们得到超平面的解析式。

1.3.1. 支持向量与对偶问题

  容易想到,一般分割超平面间隔越大,分类能力越强,因为越大的分割对误差有更大的容许,对噪声导致的数据波动有更高的忍耐,而不至于某样本稍稍偏离主体便被错误划分为另一类。

  直观来看,为了找到这个最合适的超平面,我们需要解决一个如下的约束下最大化分隔的优化问题   值得注意的是对这个优化问题的结果也有影响,考虑到,因此的大小确会影响约束优化的解。为了方便优化,我们希望将其转化为一个凸优化问题,考虑到最小化与最大化是等价的,于是可以改写求解超平面问题为   由凸优化理论,拉格朗日对偶函数一定是凹函数、弱对偶的,且凹性与原目标函数与约束无关;当原优化问题为凸优化问题时,即满足Slater条件,拉格朗日对偶问题一定是强对偶的,便是一个典型的凸优化问题,因此其拉格朗日对偶问题与自身等价。再考虑到SVM优化目标,考虑他的拉格朗日乘子的优化比直接考虑的优化更简便,对偶问题处理起来也会更高效(也能看出拉格朗日乘子具有一定的约束意义,能帮助我们讨论模型),下求解的拉格朗日对偶问题,这根据最优化理论不难求出,应用广义拉格朗日乘子法,首先写出不等式约束问题下的拉格朗日函数   分别令偏导为,得到

  联立即的KKT条件(可认为是全局最优解的约束,从而间接得到的最优解),最终由得到的拉格朗日对偶问题   需要注意的是,KKT条件是原问题最优解的必要条件,当原问题是凸优化问题时当然是全局最优解(此时局部最优解与全局最优解等价),对于强对偶问题的拉格朗日对偶问题的最优解也一定满足KKT条件,这是为什么在这里可以认为拉格朗日对偶问题加上KKT条件的约束便得到全局最优解的原因。

  注意到,的限制使得如果某点的拉格朗日乘子,则必有,即此样本点为支持向量;若有则一定有,进一步观察Wolfe对偶问题可以发现拉格朗日乘子为的样本点对优化问题没有任何影响只有拉格朗日乘子非的样本点对于优化问题有意义,这表明了SVM的一个极其重要的性质:只有支持向量才会影响超平面的选取,而不在分割边界上的任何一点对超平面的选取都不产生任何影响,这也是SVM——支持向量机名字的由来。

  容易看出也是一个二次凸优化问题(实质上这是优化理论所保证的),实际应用中一般考虑二次规划优化算法求解,比较高效的算法有次梯度下降法、坐标下降法和SMO算法等等,其中,今天SMO算法对于SVM问题较为流行,他的思想与坐标下降法有异曲同工之处,关于优化算法在附录再稍做介绍。

  值得一提的是,SVM之所以在高位模式识别领域具有优势,是因为面对维数诅咒SVM只利用了比较少的样本(只利用了支持向量)。通常对于高维数据,常用的方法有① 特征选择,如Lasso回归;② 直接降维,如PCA、MDS、LLE;③ 正则化,以减轻高维样本空间带来的多重共线性等不良影响;④ 增加样本量,深度学习便是沿着这个思路;在今天大数据的时代下,一个大型深度学习模型拥有上百亿个参数都不足为奇。

1.3.2. 参数的解及预测

  求参数的解我们仅用到了支持向量,因此在优化求拉格朗日乘子完成以后,我们需要的样本便只剩下支持向量了。

  对于,在通过求解优化问题解得后由直接得到,理论上只需要考虑为支持向量的样本(否则其拉格朗日乘子,与和式结果无关);

  对于,我们知道对任何支持向量,都有,结合,有   为了利用更多的样本以增强稳健性,常常使用全部的支持向量计算以减轻误差、噪声等因素带来的影响;记支持向量的集合为,势为,则有   上式可认为是利用所有支持向量分别求解后取他们的算数平均值。

  在通过算法求出后,由式即可得出我们所需要超平面的解析式:记所求超平面为,则

  这一章节中所有需要预测的样本,都代入式的便能得到结果;如果存在多种拉格朗日乘子,这是后文软间隔与SVR中的情况,则将形式上代入式中即可;如果涉及到核方法,则

  注意代表训练集的第个数据,即的第行(而不是个分量),这时一个新数据的预测分类为

1.4. 核方法

1.4.1. 核方法的思想

  目前为止,我们的SVM算法只能求解线性分类问题,比如“且”问题、“并”问题与“非”问题,但“异或”这样的非线性分类问题并没有办法解决,从我们的思路与式可以观察出现在我们只是在当前样本空间中寻找合适的分割超平面,譬如有两个自变量的分类问题里,从出发我们只能得到平面图的一条直线的分割,而当样本类别分布的分界线呈现出明显的O形,我们目前的方法便不再可行了。

  不过我们仍有解决办法让SVM有能力处理非线性分类问题:我们可以将样本空间映射到一个更高维的空间,使样本在这个更高维的空间可分,例如下图左部分的分类问题,当我们把二维的自变量空间升至维,即下图右部分,便能够找到一个超平面使得样本可分;如果升维仍不线性可分,可以继续升高维数。升维时是可以将样本映射到无穷维空间的。

当前样本空间线性可分情况在高维下的体现

二分类的例子,高维空间中的超平面投影到三维空间为一个抛物面,这个抛物面在平面上的投影为一个圆,通过这个圆得以分类

  对于有限维的样本空间,即属性数或者将向量的分量数是有限的,则必存在一个高维空间使得样本线性可分,这是显而易见的,只不过可能在这一高维空间下的内积难以计算。

  对于非线性分类问题,用表示将映射至高维空间后的特征向量,需要寻得的高维空间下新超平面为,于是得到高维空间下的优化问题,把替换为即可。   中涉及到高维空间下的内积计算,这可能不是很好解决,因为SVM在升维的时候可以升至极高的维数甚至无穷维,用计算机计算无穷维的向量内积并不现实。不过不要担心,我们可以通过核技巧(凡是涉及升维内积计算都可以运用核技巧,如分布式运算、深度学习中的运用)绕过这个障碍。我们可以试图找到一个函数称之为核函数,使得从而避开对升维后内积的直接计算,如果能够找到这样一个核函数,那么优化问题进一步转化为   则由用替换后的式并用替换推导,或直接对式做同样替换,得到我们称之为支持向量展式   看上去,只要我们能找出这样一个合适的核函数,就能由式,通过训练样本中的核函数展开得到最优解,故而我们仅需要针对支持向量这少量的样本寻找一个合适的核函数,而不需要关心具体是何种映射。接下来的问题是,我们是否总能找到这样一个核函数?或者,我们如何找到这样一个核函数?

  核函数的Mercer定理:二元对称实值函数是核函数当且仅当对任意一组向量的核矩阵半正定。

  Mercer定理确保了这样一个核函数必定存在,但是否可行、如何寻找最佳核函数,同岭估计最佳岭值的确定一样目前没有普遍适用且最佳的方法,这是值得研究的问题。现在有一些综合多种常用核函数考量的技术,这借助了集成学习的算法。

1.4.2. 核方法的泛函分析理论支持

  这一部分是纯粹理论的推导,如果不关心底层理论可以略过,毕竟这需要一定的数学基础;

  希望这部分读者拥有数学及相关专业本科生或理工研究生以上的泛函分析水平,起码对泛函延拓定理要有所耳闻。

1.4.2.1. 核函数与Mercer定理

  Mercer定理确保了只要一个对称函数对应的核矩阵半正定,那么他就能被当作核函数应用,这是核技巧的关键,是核技巧得以存在的理论支持。事实上,定义核函数等价于定义了一个RHKS(再生核的Hilbert空间)。

  首先定义核函数,若二元实值可积函数满足正定性与对称性,则称为空间上的一个核函数。记某组数据关于一核函数的核矩阵为