我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:双彩网 > 约束推理 >

从零推导支持向量机 (SVM)

归档日期:07-05       文本归类:约束推理      文章编辑:爱尚语录

  雷锋网 AI 科技评论按,本文作者张皓,目前为南京大学计算机系机器学习与数据挖掘所(LAMDA)硕士

  雷锋网 AI 科技评论按,本文作者张皓,目前为南京大学计算机系机器学习与数据挖掘所(LAMDA)硕士生,研究方向为计算机视觉和机器学习,特别是视觉识别和深度学习。

  个人主页:。该文为其给雷锋网 AI 科技评论的独家供稿,未经许可禁止转载。

  支持向量机 (SVM) 是一个非常经典且高效的分类模型。但是,支持向量机中涉及许多复杂的数学推导,并需要比较强的凸优化基础,使得有些初学者虽下大量时间和精力研读,但仍一头雾水,最终对其望而却步。本文旨在从零构建支持向量机,涵盖从思想到形式化,再简化,最后实现的完整过程,并展现其完整思想脉络和所有公式推导细节。本文力图做到逻辑清晰而删繁就简,避免引入不必要的概念、记号等。此外,本文并不需要读者有凸优化的基础,以减轻读者的负担。对于用到的优化技术,在文中均有介绍。

  尽管现在深度学习十分流行,了解支持向量机的原理,对想法的形式化、简化,及一步步使模型更一般化的过程,及其具体实现仍然有其研究价值。另一方面,支持向量机仍有其一席之地。相比深度神经网络,支持向量机特别擅长于特征维数多于样本数的情况,而小样本学习至今仍是深度学习的一大难题。

  ,二分类任务的目标是希望从数据中学得一个假设函数 h: R → {−1,1},使得 h(xi) =yi,即

  更进一步,线性二分类模型认为假设函数的形式是基于对特征 xi 的线性组合,即

  定理 1. 线性二分类模型的目标是找到一组合适的参数 (w, b),使得

  即,线性二分类模型希望在特征空间找到一个划分超平面,将属于不同标记的样本分开。

  线性支持向量机 (SVM) [4]也是一种线性二分类模型,也需要找到满足定理 1 约束的划分超平面,即 (w, b)。由于能将样本分开的超平面可能有很多,SVM 进一步希望找到离各样本都比较远的划分超平面。

  当面对对样本的随机扰动时,离各样本都比较远的划分超平面对扰动的容忍能力比较强,即不容易因为样 本的随机扰动使样本穿越到划分超平面的另外一侧而产生分类错误。因此,这样的划分超平面对样本比较稳健,不容易过拟合。另一方面,离各样本都比较远的划分超平面不仅可以把正负样本分开,还可以以比较大的确信度将所有样本分开,包括难分的样本,即离划分超平面近的样本。

  在支持向量机中,我们用间隔 (margin) 刻画划分超平面与样本之间的距离。在引入间隔之前,我们需要 先知道如何计算空间中点到平面的距离。

  定义 1 (间隔 γ ). 间隔表示距离划分超平面最近的样本到划分超平面距离的两倍,即

  即,线性支持向量机希望在特征空间找到一个划分超平面,将属于不同标记的样本分开,并且该划分超平面距离各样本最远。

  定理 3 描述的优化问题十分复杂,难以处理。为了能在现实中应用,我们希望能对其做一些简化,使其变 为可以求解的、经典的凸二次规划 (QP) 问题。

  定义 2 (凸二次规划). 凸二次规划的优化问题是指目标函数是凸二次函数,约束是线性约束的一类优化问题。

  由于对 (w, b) 的放缩不影响解,为了简化优化问题,我们约束 (w, b) 使得

  推论 6. 线性支持向量机基本型中描述的优化问题属于二次规划问题,包括 d + 1 个优化变量,m 项约束。

  现在,我们可以通过调用现成的凸二次规划软件包来求解定理 5 描述的优化问题。不过,通过借助拉格朗 日 (Lagrange) 函数和对偶 (dual) 问题,我们可以将问题更加简化。

  推论 8 (KKT 条件). 公式 21 描述的优化问题在最优值处必须满足如下条件。

  证明. 由引理 7 可知,u 必须满足约束,即主问题可行。对偶问题可行是公式 21 描述的优化问题的约束项。αigi(u) = 0 是在主问题和对偶问题都可行的条件下的最大值。

  引理 10 (Slater 条件). 当主问题为凸优化问题,即 f 和 gi为凸函数,hj为仿射函数,且可行域中至少有一点使不等式约束严格成立时,对偶问题等价于原问题。

  证明. 因为公式 26 内层对 (w,b) 的优化属于无约束优化问题,我们可以通过令偏导等于零的方法得到 (w,b)的最优值。

  推论 13. 线性支持向量机对偶型中描述的优化问题属于二次规划问题,包括 m 个优化变量,m + 2 项约束。

  代入公式 10 即得。其中,ei是第 i 位置元素为 1,其余位置元素为 0 的单位向量。我们需要通过两个不等式约束

  定理 14 (线性支持向量机的 KKT 条件). 线性支持向量机的 KKT 条件如下。

  引理 15. 线性支持向量机中,支持向量是距离划分超平面最近的样本,落在最大间隔边界上。

  定理 16. 支持向量机的参数 (w, b) 仅由支持向量决定,与其他样本无关。

  其中 SV 代表所有支持向量的集合,b 可以由互补松弛算出。对于某一支持向量 xs及其标记 ys,由于

  实践中,为了得到对 b 更稳健的估计,通常使用对所有支持向量求解得到 b 的平均值。

  至此,我们都是假设训练样本是线性可分的。即,存在一个划分超平面能将属于不同标记的训练样本分开。但在很多任务中,这样的划分超平面是不存在的。支持向量机通过核技巧 (kernel trick) 来解决样本不是线 非线性可分问题

  证明. 此证明已超出本文范围,感兴趣的读者可参考计算学习理论中打散 (shatter) 的相应部分 [16]。

  + 1 个优化变量,m 项约束的二次规划问题;对偶型对应于 m 个优化变量,m + 2 项约束的二次规划问题。

  注意到,在支持向量机的对偶型中,被映射到高维的特征向量总是以成对内积的形式存在,即

  。当特征被映射到非常高维的空间,甚至是无穷维空间时,这将会是沉重的存储和计算负担。

  表 1 列出了几种常用的核函数。通常,当特征维数 d 超过样本数 m 时 (文本分类问题通常是这种情况),使用线性核;当特征维数 d 比较小,样本数 m 中等时,使用 RBF 核;当特征维数 d 比较小,样本数 m 特别大时,支持向量机性能通常不如深度神经网络。

  新的核函数还可以通过现有核函数的组合得到,使用多个核函数的凸组合是多核学习 [9] 的研究内容。

  即 Φα 比 w 有更小的目标函数值,说明 w 不是最优解,与假设矛盾。因此,最优解必定是样本的线性组合。

  此外,原版表示定理适用于任意单调递增正则项 Ω(w)。此证明已超出本文范围,感兴趣的读者可参考 [13]。

  通过核函数,我们可以将线性模型扩展成非线性模型。这启发了一系列基于核函数的学习方法,统称为核方法 [8]。

  不管直接在原特征空间,还是在映射的高维空间,我们都假设样本是线性可分的。虽然理论上我们总能找 到一个高维映射使数据线性可分,但在实际任务中,寻找到这样一个合适的核函数通常很难。此外,由于数据中通常有噪声存在,一味追求数据线性可分可能会使模型陷入过拟合的泥沼。因此,我们放宽对样本的要求,即允许有少量样本分类错误。

  是指示函数,C 是个可调节参数,用于权衡优化间隔和少量分类错误样本这两个目标。但是,指示函数不连续,更不是凸函数,使得优化问题不再是二次规划问题。所以我们需要对其进行简化。

  公式 60 难以实际应用的原因在于指示函数只有两个离散取值 0/1,对应样本分类正确/错误。为了能使优 化问题继续保持为二次规划问题,我们需要引入一个取值为连续值的变量,刻画样本满足约束的程度。我们引入松弛变量 (slack variable) ξi,用于度量样本违背约束的程度。当样本违背约束的程度越大,松弛变量值越大。即,

  其中,C 是个可调节参数,用于权衡优化间隔和少量样本违背大间隔约束这两个目标。当 C 比较大时,我们希望更多的样本满足大间隔约束;当 C 比较小时,我们允许有一些样本不满足大间隔约束。

  因为内层对 (w, b, ξ) 的优化属于无约束优化问题,我们可以通过令偏导等于零的方法得到 (w, b, ξ) 的最优值。

  推论 26. 软间隔支持向量机对偶型中描述的优化问题属于二次规划问题,包括 m 个优化变量,2m+2 项约束。

  引理 28. 软间隔支持向量机中,支持向量落在最大间隔边界,内部,或被错误分类的样本。

  定理 29. 支持向量机的参数 (w, b) 仅由支持向量决定,与其他样本无关。

  其中,第一项称为经验风险,度量了模型对训练数据的拟合程度;第二项称为结构风险,也称为正则化项,度量了模型自身的复杂度。正则化项削减了假设空间,从而降低过拟合风险。λ 是个可调节的超参数,用于权衡经验风险和结构风险。

  ,当训练样本很多时,这将是一个很大的存储和计算开销。序列最小化 (SMO) [10]是一个利用支持 向量机自身特性高效的优化算法。SMO 的基本思路是坐标下降。

  定义 7 (坐标下降). 通过循环使用不同坐标方向,每次固定其他元素,只沿一个坐标方向进行优化,以达到目标函数的局部最小,见算法 1.

  ,当其他变量固定时,αi也随着确定。这样,我们无法在不违背约束的前提下对 αi进行优化。因此,SMO 每步同时选择两个变量 αi和 αj进行优化,并固定其他参数,以保证不违背约束。

  推论 33. SMO 每步的优化目标可等价为对 αi的单变量二次规划问题。

  ,我们可以将其代入 SMO 每步的优化目标,以消去变量 αj。此时,优化目标函数是对于 αi的二次函数,约束是一个取值区间 L ≤ αi≤ H。之后根据目标函数顶点与区间 [L, H] 的位置关系,可以得到 αi的最优值。理论上讲,每步优化时 αi和 αj可以任意选择,但实践中通常取 αi为违背 KKT 条件最大的变量,而 αj取对应样本与 αi对应样本之间间隔最大的变量。对 SMO 算法收敛性的测试可以用过检测是否满足 KKT 条件得到。

  ,因此,有许多学者致力于研究一些快速的近似算法。例如,CVM [15]基于近似最小包围球算法,Nyström 方法[18]通过从 K 采样出一些列来得到 K 的低秩近似,随机傅里叶特征[12]构造了向低维空间的随机映射。本章介绍了许多优化算法,实际上现在已有许多开源软件包对这些算法有很好的实现,目前比较著名的有 LibLinear[7] 和 LibSVM[3],分别适用于线性和非线. 支持向量机的其他变体

  ProbSVM. 对数几率回归可以估计出样本属于正类的概率,而支持向量机只能判断样本属于正类或负类,无法得到概率。ProbSVM[11]先训练一个支持向量机,得到参数 (w, b)。再令

  对数几率回归模型可以认为是对训练得到的支持向量机的微调,包括尺度 (对应 θ1) 和平移 (对应 θ0)。通常 θ1 0,θ0≈ 0。

  [2] S. Boyd and L. Vandenberghe. Convex optimization. Cambridge university press, 2004. 4

本文链接:http://ksbuilders1.com/yueshutuili/198.html