文档介绍：人工智能课程项目报告
姓名：
□moiuiuimc
班级：
4■亠4■亠4■亠4・亠4・亠4・亠4・亠4・亠」・亠4・亠4・亠4・亠4・亠丄・亠
目录
一、实验背景1
二、实验目的1
三、实验原理1
线性可分：1
。幸运的是，数学中有这样一些函数，他们叫核函数，计算效果相当于转化到高维后的内积。
百度百科的解释：核函数将m维高维空间的内积运算转化为n维低维输入空间的核函数计算，从而巧妙地解决了在高维特征空间中计算的“维数灾难”等问题，从而为在高维特征空间解决复杂的分类或回归问题奠定了理论基础。几个核函数：
多项式核：Jin
它能将原始空间映射为无穷维空间。不过，如果sita选得很大的话,就相当于一个低维的子空间；反过来，如果选得很小，则可以将任意的数据映射为线性可分——当然，这并不一定是好事，因为随之而来的可能是非常严重的过拟合问题。不过，总的来说，通过调控参数，高斯核实际上具有相当高
的灵活性，
也是使用最广泛的核函数之一。
经过数学推导，非线性SVM的目标函数为：
同样，
同样，可以用SMO求解。
17
如上图：如果转化到高维还是不可分呢？或者转的维数不够，或者存在
噪声点？这个时候怎么办？引入松弛变量:
min*|
|2
•f-i
其中称为松弛变量，c是一个参数。同样，经过转化:
您幻力刃0（芯）铀（可）■
（iij
.》aiyt=OrQ<at<Cyi
7
此时，我们发现没有了参数「，与之前模型唯一不同在于c的限制条件。为了不失一般性，我们使用引入松弛变量的模型。也就是需要求解的目
max.
a
如勾旳丹0（御）环（巧）
a--
IIJ
=OrO<at<C,Vi
标问题。
根据KKT条件可以得出目标函数中取值的意义：
17
a=〔〕少另吗>L
0<aJ<C<^>y“=lt
a=Coy-u.<1.
这里的还是拉格朗日乘子：
对第1种情况，表明是正常分类，在边界内部(我们知道正确分类的点)；
对第2种情况，表明了是支持向量，在边界上；
对第3种情况，表明了是在两条边界之间；
：
在最后讨论W(a)的求解之前，我们先看看坐标上升法的基本原理。假
max…,^帼)’
设要求解下面的优化问题：
这里W是a向量的函数(也就是前面转化后的目标函数)。求最优解
的方法有多种：一种是梯度下降法，一种是牛顿法，还有一种是坐标上升法。
Loopuntilconvergence:{
Fori—L.,..{
%:-=tagIIL^v(^1ffL(ij,Ufj+|....,<¥rn)*
方法过程：
坐标上升法可以用一张图来表示：
9
3・4SMO算法:
，并成为最快的二次规划优化算法，特别针对线性SVM和数据稀疏时性能更优。关于SMO最好的资料就是他本人写的论文《SequentialMinimalOptimizationAFastAlgorithmforTrainingSupportVectorMachines》。
算法框架：
fori=1:iter
，从所有样本中选出两个
，更新所选样本对应的拉格朗日乘子end
样本选取规则：
第一个参数是违反kkt条件的。
第二个参数：选择使得-'（实际输出和期望输出的误差）最大的参数。情况比较复杂，原算法分了很多情况。当所有变量都满足kkt条件时，算法结束，求得a。
选出了参数就要进行计算。其中一个参数是可以求导等于0然后解出来（不失一般性，记为a2）。另一个参数随之发生变化（记为al）。解之前要先确定取值范围：
C
a
C
0
C
a
3
0
0
a
a
iTj=0
旳二旳=＞码+弼=氐
根据yl和y2异号或同号，可得出a2的上下界分别为:
L=nwx（g翼-a^d）tH=ininfCC+毎-屮）if加/也L—+<V严—C）,li-min（G+◎嘗）ifyi=虫
10
如果是极值点，二阶导应该大于0关于a2的二阶导为:
7；=K（元|,元J+K（召，元J—2K（耳,爲）.
经过数学计算，在二阶导大于0的情况下，
讦
ifL<r<//;if疣尹<L.
结合取值范围:
在一些情况下，二阶导不是正数，这时候需要用到目标函数在取最小值
和最大值时候的值：
f\=yAE\+Z＞）-»^i）-Jsa2K（x^x2\
fi=y2（E2^b）-sa}K（x^jc2）-a2K（x29x2\
厶=+s（a3