1. SMO

  1. 设训练样本数目为,原始观测空间的维数为。支持向量机所对应的二次规划问题往往使用SMO(Sequential Minimal Optimization)算法求解。SMO算法不断地求解仅涉及两个优化变量的二次规划问题。设给定训练样本为,对偶问题为: 。 具体地,在每次迭代时,选中两个优化变量,同时保持其它变量固定,求解关于的二次规划问题。请结合线性支持向量机(分为线性可分和线性不可分情况),给出在每次迭代过程中关于两个变量的解。

SVM使用一种非线性映射,把原训练数据映射到较高的维。在新的维上,搜索最佳分离超平面,两个类的数据总可以被超平面分开。

1.1. 1. 线性可分

要找到具有“最大间隔”的划分超平面,即 等价于

1.2. 2. 线性不可分

线性可分问题的支持向量机学习方法,对线性不可分训练数据是不适用的,为了满足函数间隔大于1的约束条件,可以对每个样本$(\mathbf x_i,y_i)$引进一个松弛变量$ξ_i≥0$,使函数间隔加上松弛变量大于等于1: 目标函数为 其中为惩罚参数。 因此,最小化目标函数也就是使尽量小,同时使误分类点的个数尽量小。线性不可分的线性支持向量机问题变成下面的凸二次规划问题:

1.3. 3. 对偶问题

使用拉格朗日乘子法得到其“对偶问题”: 其中。令中的的偏导为0可得

即可将中的消去,得到对偶问题

1.4. 4. SMO算法

约束重写为: 用上式中的消去中的 假设 为常数,

固定,得到: 为变量,则得到一个关于的单变量二次规划问题,仅有的约束是

求偏导以求得最大值,有 由此可得: 根据的定义,展开得到: 规定误差项,取,并规定, 上式可化简为: 再考虑限制条件的取值只能为直线落在矩形中的部分。 此处输入图片的描述 因此需要检查的值以确认这个值落在约束区间之内: 其中 假设,则新的

results matching ""

    No results matching ""