SVM理论和算法分析报告

1、硬间隔线性支撑向量机假设给定一个特征空间上的训练数据集:T= (xi,yi)，(X2,y2)，(xn$n)其中，x i Rn, yi + 1,- 1, i = 1,2,N Xi为第i个特征向量或实例，yi为xi的类标记，当yi = 1时，称 Xi为正例，当yi = - 1时，称xi为负例；（Xi , yi）为样本点。假设训练数据集是线性可分的（存在硬间隔），那么学习的目标是在特征空间找到一个分离超平面，能将实例分到不同的类。分离超平面方程w?x + b = 0，它由法向量 w和截距b决定，可用（w,b）表示。分离超平面将特征空间分为两部分，一部分是正类，一部分是负类。法向量指向的一侧为正类，另

2、一侧是负类。一般地，当训练数据集线性可分时，存在无穷个分离超平面可将两类数据正确分开，感知机利用误分类最小的策略，求得分离超平面，不过这是的解有无穷多。线性可分支撑向量机利用间隔最大化求最优分离超平面， 解唯一、模型推导1.函数间隔：一般来说，一个点距离分离超平面的远近可以表示分类预测的确信程度。在超平面w?x+ b= 0确定的情况下，|w?x+ b|能够相对地表示（注意：真实距离为 也艺）点x距离超平面的远近。而w ?x + b的符/w/号与类标记y的符号是否一致能够表示分类是否正确。所以可用标量y（w?x + b）来表示分类的正确性及确信度，值为正表示分类正确，值为负表示分类错误。超平面（

3、?, ?）关于样本点（？?, ?）的函数间隔为：? = ?(? ?+ ?)超平面(?, ?)关于训练数据集T的函数间隔：? = ? ? = ? ?(? + ?) ? ?、 ? /CC CC CC /2.几何间隔：函数间隔可以表示分类预测的正确性及确信度，但是选择分离超平面时，只有函数间隔还不够。 因为只要成比例地改变 w和b,虽然超平面并没有改变，但函数间隔（它是（w,b）的线性函数）却依原比例同等改变。为了将（w,b）表示的超平面的唯一化，即每个超平面对应Rn+1中的唯一向量（w,b），可以对法向量 w加以规范化约束/w / = 1，这时函数间隔称为几何间隔。超平面（?, ?）关于样本点（？

4、?, ?）的几何间隔为：?超平面（?, ?）关于训练数据集T的几何间隔为:? ?=?,?, ? ?= ?,?; ? -'/? / /? /? = ? ?= ?( ? +on on on cc on no no'二 cc ' ' II ' ' ' ' '/3间隔最大化支撑向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对于线性可分 的训练数据集而言，线性可分分离超平面有无穷多个，每一个都是一个感知机，但是几何间隔最大的分离超 平面时唯一的。间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超

5、平面意味着以充分大的却新都对训练数据进 行分类。也就是说，不仅将正负实例点要分开，而且对最难分的实例点（离超平面最近的点）也有足够多大 的确信度将它们分开。因此所要优化的问题表示为：?,?> ?, ? = ?, ?,? ?改写为,?,?II? /? ?(?+ ?) >?,? = ?,?,?Y的取值不影响最优化问题的解（如果w ?,b?是最优解，那么入w ?,入b?也是最优解，因此丫？是变动的可以取到 任意值，如果固定Y? ,w?,b?也就变得唯一了），令丫 ？ = 1,等价变换为，?,? /? /? ? ?(? ? + ?) > ? ?=?？这是为了运算方便)， ? II?

6、/?'?,? ?- ?"(?"+ ?) < ? ?=?？ ?, b?。(目标函数是支撑间隔，约束是样本点在间隔边界或外侧，目标是寻找支撑向量使得间隔最大化)等价变换 为(标准无等式约束的凸二次规划，?.?凸二次规划问题存在全局最优解w(4)分离超平面与分类决策函数 分离超平面：? ? + ? = ?分类决策函数:?(?) = ?(?+ ?)(5)支撑向量与间隔边界在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支撑向量，支撑向量是使约束条件等号成立的点，即？- ?(? ?+ ?) = ?，对于正例点，支撑向量在超平面? +?= ?上

7、，对于负例点，支撑向量在超平面 ？ ？?？+ ?= - ?上，没有实例点落在这两个平行的超平面?(间隔边界)之间，这两个超平面之间的距离称为间隔，它依赖于分离超平面的法向量W等于用几。在决定分离超平面时只有支持向量起作用，而其他实例点并不起作用。如果移动支持向量将改变所求的解， 但是如果在间隔边界以外移动其他实例点，甚至去掉这些点，则解是不会改变的。显然支撑向量是训练集中 重要的样本。二、模型求解 将原始问题转化为Lagrange对偶问题，通过求解对偶问题来获得原始问题的最优解：对每个不等式约束引入 Lagrange 乘子 a i ,1. Lagrange对偶函数：?刀?= ?(?,?,?)

8、= ? /? /?- 刀 ?(? ?+ ?) ?= ?1,2,，N。其中a = ( a 1, a 2,，a n)T为拉格朗日乘子向量，a i > 0 , i = 2.对偶问题：maxmin L(w b, a )a Wb(1) 求?(?, ?,?)?W_(W,b, a ) = W-?bL(W,b, a )=-N刀i = 1N刀i = 1a iyi Xi = 0a iyi = 0得出NW=刀 a i yii =1NXi刀 a i yi = 0i =1带入拉格朗日函数，得出? ?(? ? ?)? ' ? ?= 工 工 ? ?(? ?)?= ? ?= ?刀？?？?？（?=?刀 ？?？?？

9、 ?) ? + ?) + 刀 ?= ? ?= ? ?-?刀刀？?？?？?？?(？?？?？?)+ 刀?= ? ?= ? ?= ?(2) 求? ? ?(?, ?, ?)? ?,? 1 1? ? (-?刀 刀? ?(? ?) + ?= ?=?刀?)?= ?. ?.刀? = ?= ? > ? , ?= ?,?, ,?转换为求极小? ? ( T？?厶?刀?(?)-?= ? ?= ?刀?)?= ?根据对偶理论，对上述对偶优化存在，使w 可以转化为求解对偶问题。3.最优解根据KKT条件?. ?.刀? = ?= ? > ? , ?= ?,?, ,？a ?是对偶问题的解，因此求解原始问题,?,b?是

10、原始问题的解,)=w?-寸*=1 a ?yi)=-寸=1 a ?yi =a ?(yi (w/? ?xi + b?) - 1) = 0 , i = 1,2,N-yi (w7?Xi + b?) - 1 > 0, i = 1,2,-,Na ? > 0, i =-(e)?ML(W b?,?b?L(w?, b?.12,，N由（a）求得其中至少有一个a 条件（C），得出? > 0 (如果a将?带入KKT条件，得出Xj = 0 0(a)(b )(c)(d )?=刀? ?= ?0，那么w?= 0 ,b?无解，显然它不是原始最优化问题的解），结合 KKTyk(w ?xk + b?) - 1 =

11、 0Nyk (刀 a ?yiXi) ? xk+ b?) = 1i =1两边同时乘以yk，由于（yj2= 1N?ykVk(刀 a iyxj ? Xk+ b?) = yki = 1N刀 a ?yi (Xi ?Xk) + b? = yki =1? ?' = ?- X ?(?)?= ?因此分类决策函数为? ?(?) = ?( X ?(?) + ?)?= ?从?, ?中可以看出它们仅仅依赖于？ ? > 0的特征点，即支撑向量（因为yk（肿？Xk+ b?） - 1=0? W Xk + b? = ±1，所有x k在分隔边界上）；这仍是一个二次凸优化，存在全局最优解, 二、模型求解仍使

12、用Lagrange对偶方法求解1.Lagrange 函数软间隔线性支撑向量机一、模型推导如果样本集中存在特异点使得样本集线性不可分，即不能满足函数间隔大于等于1不等式约束条件，为了解决这个问题，可以对每个样本点 (Xi , yi)引入一个松弛变量E i > 0，使函数间隔加上松弛变量大于等于1.这样约束条件变为?(?+ ?) > ?- ?同时对每个松弛变量E i，支付一个代价E i，目标函数变成? ?II? /'+ ?刀 E i? ? ?' ?= ?这里，C > 0称为惩罚参数，一般由应用问题决定，C值大时对误分类的惩罚增大，C值小时对误分类的惩罚减小。最小化

13、上述目标函数有两层含义，要使的1 /W I2尽量小即间隔尽量大，同时使的误分类的点的个数尽量小，C是调和二者的系数。这时的间隔称为软间隔，因为间隔内含义特异点。原始优化问题：? II? /?+ ?刀? ? ?, ?=?.?. ?- ?- ?(?+ ?) < ?, ? = ?,?,? > ?=?？: , , , , ?(?,?,?,?,?)= 刁 /?刀?= ?-刀?(?(?+ ?) - ?+ ?)-刀?= ? ?= ?其中，? > ?, ? > ?。2.对偶问题：?第?？?(?,？?,？?,？?,？?) ! - - -?,?(1)求? ?(?, ?, ?, ?, ?)?

14、 ? ? ' ' ' ' ! - - -?wL(w,b, Ew-刀 a i yi xi = 0i = 1N得出?bL(wb,=-刀 a iyji = 1C?1Tw=刀 a i yi xii =1N刀 a i yi = 0i =1C- a i - 口 i =w的解是唯一的，但 b的解不唯一，b的解存在于一个区间。带入拉格朗日函数，得出? ?(?,?,?,?,?)=- 刀 刀？?？?？?？?(？?？?？?)+ 刀？? ? ? ''?=? ?= ?= ?注意它与口无关。(2) 求 ? ?(? ? ? ? ?) ? ? ? ?' ' &#

15、39; ' ! - -? ?(- 刀刀?(? ?) + 刀?) ? -? ?刀?=:?= ?> ? >?=? ? 5 5？5 ?> ?,?=? ? 5 5？5 ?-?=? >?= ?,?,?-？5 ''?= ?=? ?= ?消去口 i ,转换为求极小? ?(刃刀 刀? ?(? ?)- ？=?= ?刀?)?= ?. ?.刀? = ?= ? > ? ?= ? ? < ? < ?(3)最优解根据KKT条件?w?L(w? ,b?,?,a ?,?):=W -寸=1 a ?yi Xi?b?L(w?,b',?,a ?,?):=-XN=

16、1 a ?yi = 0-?L(w7,b',?',a ?,?')To?=C?1T- a ? - ?a ?(yi (w? ?Xi + b?) - 1?+ ?i)=0 , i = 1,2, -, N-=0-0Q Q?i?i =0 , i = 12,(a)(b) -(c)-(d)(e)?i > 0 , i = 12,N-(f)yi (w/?xi + b?) - 1 + ? > 0, i = 1,2，N(g)a ? > 0, i = 12,-",N-(h)? > 0, i = 12,-,N-(i)由(a)求得?=oX ? ? ? ?= ?由(c)

17、、( e)(i )得出? ?(? - ?) ? = ?Q? - ? > ?再结合(f)得出如果? ? <?，那么？ =?;如果?=? ?5? > ?;-:J (j )由(d) ,( h)得出如果?> 0,那么?(? ? +? ?) - ?+ ?=?;如果? =? ?:?, ?(? ?+ ?)? +?不确定；-(k)由(j) , (k)得出 如果? <?< ?,那么？?？= ?,?(?+ ?)-?+?= ?，因此？?(？?？?+?)= ?；? ?' = ?- X ?(?)?= ?由(j) , (g)得出 如果?= ?，那么?= ?, ?K?+ ?) &

18、gt; ?;这说明位于间隔边界上或以外；由(j)，(k)得出如果?= ?，那么?(? ?+ ?) = ?- ?, ? > ?； 此种情况下，进一步讨论：?如果？?？= ?，那么？?在间隔边界上； 如果? < ?< 1那么？勿分类正确，？?在间隔边界与分离超平面之间； 如果? = ?，那么？活在分界面上； 如果? > 1那么？?在分离超平面误分一侧；因此可以看出，软间隔的支撑向量(？ ？> 0) ?或者在间隔边界上，或者在间隔边界与分离超平面之间， 或者在分离超平面误分一侧。3.支撑向量的另一种解释 最小化以下目标函数：NX 1 - yi (w?xi + b)+ +

19、 入 IIw fi =1第一项是经验损失或经验风险，函数称为合页损失函数L(y(w?x + b) = 1 - yj (w?xi + b) +，下标“ + "表示以下取正值得函数。+z z > 0z+ = 0 z < 0也就是说，当样本点被正确分类且函数间隔大于1时，损失函数为0,否则(x i为支撑向量时)损失函数是1- yj (w?xj + b)，第二项是系数为入的 w的L 2范数，是正则化项；这两种优化是等价的(通过变量替换方 法);非线性支撑向量机对于分类问题是非线性的(线性模型无法将正负实例正确分开)，可以利用核技巧，进行一个非线性变换， 将非线性问题变换为线性问题

20、，通过解变换后的线性问题的方法求解原来的非线性问题。用线性分类方法求解非线性分类问题问题分两步：首先使用一个变换将原空间的数据映射到新空间；然后再新空间里用线性分类学习方法从训练数据中学习分类模型；核技巧应用到支持向量机，其基本思想：通过一个非线性变换将输入空间(欧氏空间Rn或离散集合)对应于一个特征空间(希尔伯特空间H),使得在输入空间R n中的超曲面模型对应于特征空间H中的超平面模型(支撑向量机)，这样分类问题的学习任务通过在特征空间中求解线性支撑向量机就可以完成。一、非线性支撑向量机在线性支撑向量机的对偶问题中，无论是目标函数还是决策函数(分离超平面)都只涉及输入实例与实 例之间的內积，

21、如果把这个內积？?？?看作是希尔伯特空间中的两个特征的內积 ？?)? ?(?)= ?(?,?) = ? ?，其中？?？= ?(?) , ?= ? (?)，那么对于在低维线性不可分的样本集 ?，?= 1,2, ,?，如果通过映射？?变换到高维希尔伯特空间?，?= 1,2,?变得线性可分(假设 能找到这样的合适的映射？?)，那么就可以使用核函数？?,？?)代替计算?，这里？?， ?未/ / / /知，但？?，?，?(?,?)已知。使用核函数后的对偶问题的目标函数成为：? ? ?(?) = ?刀 刀? ?(? ?)-刀? ?= ?=?= ?最优解成为?'=刀? ?= ? ? ? = ?- 刀

22、 ?( ? ?)?= ?分类决策函数成为?(?) = ?(刀?(? ?) + ?)?=?在实际应用中，往往依赖领域知识直接选择核函数，核函数选择的有效性需要通过实验验证。二、核函数方法核函数：设X是输入空间(欧氏空间R n的子集或离散集合)，H为特征空间(希尔伯特空间)，如果存在一 个从X到H的映射，?(x):X f H使得对所有x ,z X，函数K (x,z)满足条件K(x,z) = ?(x) ?(z)则称K(x,z)为核函数，？(x)为映射函数，？(x)?(z)为?(x)和?(z)內积；(希尔伯特空间是完备化的內积空间，其中的每个元素是一个向量(可以无穷维)，向量之间定义有內积运 算，且空

23、间关于內积诱导出的范数是完备的) 核技巧的想法是：在学习与预测中只定义核函数K (x,z)，而不显示地定义映射函数？，因为通常直接计算 K(x,z)比较容易，而通过?(x)和?(z)计算K(x,z)并不容易。注意，？(x)是输入空间R n到特征空间H的映射， 特征空间H般是高维的，甚至是无穷维的。我们需要的是特征空间中两个特征的內积结果，而不是特征的 表示。如果我们能通过简单的函数K(x,z)得到?(x) ?(z)的內积，那就简化了问题，不用考虑？?的形式，这正是核函数的妙用之处。对于给定的核函数K (x,z)，特征空间H (希尔伯特子空间)和映射函数？?的取法不唯一，因为核函数给出 的是映射

24、后的內积结果，所选取的映射过程可能是不同的。核函数判定定理：设K:X XX- F是对称函数，贝叮(x,z)为正定核函数的充要条件是对任意xi X,i =1,2,m K(x,z)对应的 Gram矩阵:K= K(?, ?)mxm是半正定的。对于一个具体函数K (x,z)来说，检验它是否为正定核函数并不容易，因为要去对任意有限输入集验证K对应的Gram矩阵是否为半正定。在实际问题中往往应用已有的核函数。常用核函数：(1) 多项式核函数：K(x,z) = (x?z+ 1)p,对应的支撑向量机是一个 p次多项式分类器；(2) 高斯核函数：K(x,z) = exp (- 謬)，对应的支撑向量机是高斯径向基

25、函数分类器；(3) 字符串核函数：1) 基本定义： 有限字符表工；字符串s: s(1)s(2)s(|s|),字符串s的长度|s|，空字符串长度为0;字符串连接：st , s和t分别是字符串；长度为n的字符串集合工n;所有字符串的集合：工?= ?n=0工n;s 的子串 u:给定一个指标序列i = (i 1, i 2, ,i |u|), 1 < i 1 < i 2 < ? << |s|, u = s(i)=s(ijs(i2)s(i|u|)，其长度记作 l (i ) = i|u| - i 1 + 1，如果 i 是连续的，则1 (i) = |u|；否则1 (i) >

26、 |?|。2) 映射定义：?假设S是长度大于或等于n字符串的集合，s是S的元素，建立字符串集合S到特征空间？?？= ?-的映射 ? ?(?), ?表示定义在?-上的实数空间，其每一维对应一个字符串 ？£?，映射？?(？?)将字符串s ?对应于空间中？?？的一个向量，其在u维上的取值为?(?)?(?) ? = E?:?(?)=?，这里，0 < ? < 1是一个衰减参数，？?)表示字符串i的长度，求和在s中所有与u相同的子串上进行。 说明：u代表维，如在字符串u维，显然空间有|艺|n维，每一维是字母表艺上的一个长度为n的字符串； ?(?)是表示通过指标序列i，表示的一个s的子

27、串，这个子串可以不连续；？?(？?)= u表示s的子串?(?)等于u;l (i)是子串？?(？?)在s中的指标序列i的最后一个分量减去第一个分量然后加一；例子：假设工为英文字符集，n为3，S为长度大于或等于3的字符串集合，考虑将字符集S映射到特征空间?3?3= ?"，?3的一维对应于字符串 asd，这是，字符串“ Nasdaq”在这一维上的值是?(?asdaq)asd = ?3,只有一个子串asd，序号是234；字符串“ lass das ”在这一维上的值是?(lass das) asd = 2?5，因 为有两个asd，序号分别为236,246;3) 核函数两个字符创s和t的字符串核

28、函数是基于映射的特征空间中的內积：kn(S,t)= 刀?(?) ?(?) ?= 刀?(?)?(?)? (i j )：s(i ) = t(j )= u它给出了字符串s和t中长度等于n的所有子串组成的特征向量的余弦相似度。直观上，两个字符串相同的 子串越多，它们就越相似，字符串核函数的值就越大，字符串核函数可以由动态规划快速计算。序列最小最优化算法支撑向量机的学习问题可以形式化为求解凸二次规划问题，具有全局最优解，并且有很多最优化算法可以用 于求解这一问题。但是当训练样本容量很大时，这些算法往往变得非常低效。序列最小最优化算法，由 Platt在1998年提出，它是一种启发式算法，相对比较高效。SM

29、(算法基本思路是：如果所有变量的解都满足次最优化问题的KKT条件，那么这个最优化问题的解就得到了，因为KKT条件是该最优化问题的充分必要条件，否则，选择两个变量，固定其他变量，针对这个两个变量构建一个二次规划问题，这个二次规划问题关于这两个变量的解应该更接近原始二次规划问题的解，因为 这会使得原始二次规划问题的目标函数值变得更小。重要的是，这时子问题可以通过解析方法求解，子问题 有两个变量，一个是违反 KKT条件最严重的那一个，另一个由约束条件自动确定。如此，算法将原问题不断 分解为子问题并对子问题求解，进而达到求解原问题的目的。原始优化问题：Nmin /w+ CE E i w,b, E 2i

30、 =1s.t yi (w?Xi + b) > 1 - E i , i = 1,2，,NE i >0,i = 1,2，N对偶问题:N1min 刀a 2刀 a ii =1j =1a jyiyjK(Xi ,Xj)-刀 a ii =1S.t .0 <子问题的两个变量只有一个是自由变量，假设a 的等式约束可知：NE a i yi = 0i =1< C,i = 1,2,N,a 2为两个变量，固定a3,a 4,，a N,那么根据上面N*1 =-刀 a i yii =3由于y i ?yi = 1，所以1 = - y 1 刀 a i yii =2如果a 2确定，那么a 1也随之确定，所以

31、子问题中同时更新两个变量。优化子问题：SMO?法包含两个部分：求解两个两个变量二次规划的解析方法和选择变量的启发式方法。不失一般性，假3 ,1 2K22 a 2+ y1y2K12 a 1 a 2 - ( a 1 + a 2) + y1 a 1 刀 yi a i K1i =3设选择的两个变量是a 1 ,a 2，其他变量a 3 , a 4,，a n固定，于是SMO勺优化问题的子问题可以写成:N1 2min W a 1, a 2） = 2 K11 a 1 + a 1 , a 22N+ y2 a 2 刀 yi ai = 3i K2S.t .其中，K ij = K(Xi,Xj) , i,j = 1,2,

32、，N,?是常数，目标函数中省略了不含aa 2的常数项。a 1y 1 + a 2y2 =-刀 a i yi = ?i =3（1）求解两变量二次规划的解析方法:可行解范围:假设子问题的初始可行解为a old , 不等式约束（盒子约束）条件的限制:a Old，最优解为a new,a 2eW，显然最优解受等式约束（直线约束）和(a)化简为new1=y1? - anew2 :old呵、=y1( a 1丄 old 、y1 + a 2y2)-newa 2 y2y1 w Cnew1 = y1?-new2 .、亦1 = a 1ld+ a 2ldy2y1- a2°切1 w c?如果y 2 = y1，那么

33、old1olda 2newa 2 W Ca old +oldnew olda 2- C W a 2 W a 1olda 2(b)由(a) , (b)得出:如果?= ?，那么？=?) = ?(? ?y ) :?)?W ?W ? ( ?+(c)? 如果y 2工，那么oldW a 1old2 +oldold久 2- a 1W a 2ew W C-olda 2(d)由(a) , (d)得出:如果？?？工？?？，那么？=?) = ? I I)?(?,? )?< ?W ?(? - ?+(e)如果最优解不在约束内，必须被剪辑。假设在沿着约束方向a?;a 2y2 = ?未经剪辑时a 2的最优解为a 2e

34、w unc;然后再求剪辑后a 2的解?F面忽略不等式约束,求取迭代解new, unc2min W( a 1,a 1 , a 21a 2)= 2K11Ny +22a2kk1 一 2+21aa2y2(a 1 + a 2) + y1 a 1 (刀 yi a i K1 )i =3+ y2 a 2 (刀 yi a i K2)i =3由于 a iy1 = ?- a 2y2，得出%1y"1=(?- a 2y2)y1a 1 = (? - a 2y2)y1带入目标函数1W a 2)= 21(?-1 一 2+2吩2ya22y2K12(? - a 2y2)a 2 - (? - a 2丫2)丫1- a 2

35、N+ (?-a 2丫2)( 刀 yi a i Ki1 ) + y2 a 2 (刀 yi a i Ki2)对a 2求导?W=-y2Kii( ?- a 2y2) + K22 a 2 + y2Ki2? - 2Ki2 a 2 + yiy2 - i - y2 (刀 yi a i Ki )i = 3+ y2 (刀 yi a i K2 )i =3=-y2Kii? + a 20i + K22 a 2 + y2Ki2? - 202 a 2 + yiy2 - iN-y2(刀 yi a i Ki) + y2 (刀 yi a i %2)i = 3i =3= -2?+ a 2(Kii+ K22 - 2Ki2) + y2

36、Ki2?+ yiy2 - i-y2(刀 yii = 3a i Ki )+ y2(刀 yi a i Ki2 )i =3a 2(Kii + K22 - 2Ki2)- y2 ( y2 - yi + Kii? - K12? +i Ki )-(刀 yi a i K2 )i = 3令其为0,得到new, unc /、a 2(Kii + K22 - 2Ki2)=y2(Ny2- yi + Kii?- Ki2?+ (刀 yii = 3Na i Ki)-(刀 yi a i 2)i = 3将?= a ildyi + a 2ldy2带入，得到new, unca 2(Kii + K22 - 2Ki2)=y2 ( y2

37、- yi + Kii a old yi + Kii aold2 y2-Ki2 a ildyi- Ki2 a 尸 y?i Ki )-(刀 yi a i K2 )i = 3old、，=y2 ( y2 - yi + Kii a i yi+ Kii a oldy2-Ki2 a old yi - Ki2a0ldy2oldoldiii - yi a 1 Zi-y2 a 2氏21)-a i K2 -old $old / 、yi a i 22 - y2a 2 k22)=y2( y2- yi + Kii aildyi + Kii a oldy2-Ki2 a ild yi -oldKi2 a 2 y2 - yia

38、 ild Kii - y2 a 2ld K?iN+ yi a oldKi2+ y2 a oldK?2 +NNy2( y2 -yi+ (Kii +K?2 -2Ki2)aold2 y2 + (刀 yi =iq a i Ki-刀 yi a i Ki2 )i = iNN(Kii +K22-2K12)aold2 +y2 ( y2' yi + (刀 yia i Ki -刀 yi a i K2 )i = ii =i(刀 yi a i Ki -刀 yi a i Ki2)i =ii = i=(K11 + K22 - 2K12)olda 2+ y2(刀 yi a iKi1 - y1)-(刀 yi a i

39、Ki2 - y2)i = 1i =1令Ei = £=' a j Kji + b- yi , i 的预测与真实输出y i之差；那么1,2；其中斗=1片a j Ki + b是对输入x i的预测,因此E i表示对输入x inew, a 2unc(K11 + K22 - 2K|2)= (K11old+ K22 - 2K12) a 2N+ y2(刀yi a M1 - yj -i = 1N(刀 yi a i 氏2 - y2)i = 1(K11 + K22 - 2K12)olda 2+ y2(E1 - E2)new unca 2old ,y2(E1 - E2)a 2+2(Ku + K22

40、- 22)old ,y2(E1 - E2)a 2 +/ 0(X1)- 0(X2)!f-因此?H,a 2ew =new, unc2a 2L,new unca 2> ?new, uncL W a 2new, unca 2new ,new由y a 1+ y2a 2= y11ld + y2 a 2ld 得出new ,y1(y1a 1 +new、y2a 2 )/ old=y1(y1a 1y2 a old )（2）变量的（启发式）选择方法:? ? = ?+ ? ( ?)SMO算法在每个子问题中选择两个变量优化，其中至少一个变量是违反KKT条件的。1）第一个变量的选择SMO尔选择第1个变量的过程为外层

41、循环。外层循环在训练样本中选取违反 其对应的变量作为第1个变量。具体地，检验训练样本点 （Xj , yi）是否满足 隔SVM文章）KKT条件最严重的样本点，并将KKT条件，即（具体推导见软间如果? = ?，那么 ？?？=?, ?(? ? + ?) > ?；如果? <?<?,那么？?= ?,?如(？?？?？?？+?)- ?+?= ?，因此？?(？?？?？+?)= ?；如果?= ?，那么？?(？?？+ ?) = ?- ?, ? >?；Na i = 0 ? yi (刀 a j yj K(xj ?xi) + b)j = 1N0 < a i < ? ? yi (刀 a

42、 j yj K(xj ?xi ) +j =1b) = 1a i = C? yi (刀 a j yj K(xj ?xi) + b)j = 1该检验是在？?范围内进行的。在检验过程中，外层循环首先遍历所有满足条件0< a i < ?的样本点，即在间隔边界上的支撑向量点，检验它们是否满足KKT条件；如果这些样本点都满足KKT条件，那么遍历整个训练集，检验它们是否满足 KKT条件；2）第二个变量的选择SMO尔选择第2个变量的过程为内层循环。假设在外层循环中已经找到第1个变量?，现在要在内层循环中找第2个变量？?。第2个变量的选择的标准是希望能使 ？?有足够大的变化（这样新的a i也会有足够

43、大的 变化，从而尽快趋向满足 KKT条件的值）。从上面的推导中可以发现，a 2eW<赖于|Ei - E2|，为了加快计算速度，一种简单的做法是选择?,使其对应的|Ei -巨|最大。因为?已定，Ei也是确定的。如果E i是正，那么选择最小的E i作为E2；如果如果E i是负， 那么选择最大的E i作为E2;（为了节省时间，将所有的E i值保存在一个列表中）；在特殊情况下，如果内层循环通过以上方法选择的？?不能使目标函数有足够的下降，那么采用以下启发式规则继续选择？?；遍历在间隔边界上的支撑向量点，依次将其对应的变量作为？ ？?试用，直到目标函数有足够的下降。若找不到合适的？ ？?，那么遍历

44、训练数据集；若仍找不到合适的 ？ ？?，则放弃第i个?，再通 过外层循环寻求另外的？ ？?。3）计算阈值b和差值? ?每次完成两个变量的优化后，都要重新计算阈值b和?,使用迭代的方法更新b；根据定义预测误差 Ei = f=iyj aj Ki + b- yi，展开得NEi + yi - XjJ=3yj下面讨论如何迭代更新 显然每次更新完a new,?a）.如果? < ?" Ei =刀 yj a j Ki + b°ldj = 3 a j Ki = a °ld yi Kii?yi +oldolda iyi Kii + a 2 y2K2ia old y2K2i + bold(f)?带入（f），得出b,即获得?:a new后 b new的选择应该使得KKT条件成立;?时，由KKT条件可知：Nyi (刀 a i yi K(Xi ?xi) + b) = ii = iNa iyiK(Xi ?xi) + b = yi?=?-刀 ? (? ?)?= ?=