模式识别第5章SVM

1、系统(S)F(x,y)学习机器(LM)f(x,),输入x输出y预测输出y已知输出变量y和输入变量x间存在一未知关系F(x,y)。机器学习问题：机器学习问题：就是根据n个独立同分布的观察： (x1,y1), (x2,y2),(xn,yn) 从给定的函数集 f(x,), 中选择出能最好逼近系统响应的函数 f(x,0)。f(x,) ：预测函数集（学习函数，学习模型，学习机器）: 函数的参数何谓最好？2、 机器学习问题的表示系统，F(x,y)f(x,)xyy0( ,)( ,( ,)1( ,)yf xL y f xyf x()( ,( ,)( ,)RL y f xdF x y11()( ,( ,)Nem

2、piRL y f xN211()( ,)NempiRyf xN11()log( ,)NempiRp xNRRRemp*经验风险和期望风险例2：过学习，过拟合图中，“*”点为10个已知样本点，采用二次模型 y=x2+n 产生，n是随机噪声100次实验中，有71次的结果是一次模型拟合结果好于二次模型的，更逼近实际的二次曲线。二次曲线一次曲线实际曲线例3（左图）：过学习，过拟合复杂分界面，训练无误差；新样本（图中红色圆点），分类错误！例4（右图）：线性可分问题各分解面的经验风险都是0，那条直线（分界面）使期望风险最小？limsup()()0,0empnPRR 对于有界的损失函数，经验风险最小化学习一

3、致性的充分必要条件是经验风险在如下意义上收敛于期望风险。或：limsup |()() |0,0empnPRR( )ln 2G nn( )(ln1),nG nhnhh( )(ln1),nG nhnhh n4、函数集学习一致收敛的充要条件：、函数集学习一致收敛的充要条件：对任意样本分布，有此时，学习过程收敛速度一定是快的。 这里，n 表示样本数，G(n) 称为函数集的生长函数。n5、经验风险最小化过程一致收敛的充要条件：、经验风险最小化过程一致收敛的充要条件：VC维有限维有限此时，学习过程收敛速度一定是快的。( )lim0nG nn欠学习 过学习 真实风险的界 置信范围 经验风险 S 1 S2 S

4、3风险 h 函数集子集： S1 S2 S3 ；VC维：h1h20的点的数目尽量少 设：I(i) = 1 , i0 I(i) = 0 , i=0目标函数目标函数可写为： J(W, i) = |W|2/2+ CI(i ) 上式中，I是不连续的量，计算困难。采用最相关的量i 取代此时， J(W, i) = |W|2/2+ C i 约束条件： 0()(1)00Tiiiiy WXw201( , , )| () 12Tiiiiii iiiiLW aWca y W Xwu 0(, , )00(1)(, , )0(2)(, , )0(3)iiiiiiiiiiiiiiL W aWa y XWa y XWL W

5、aa ywL W acau00()10(4)()10(5)0(6)0(7)0(8)TiiiTiiiiiiiy W Xway W Xwau 上面（4）（5）式可见:（1）只有满足 条件的点, （支持向量，少量）（支持向量，少量）其拉格朗日乘子ai才可能不为零; 显然只有部分(经常是少量)的样本数据的 ai 不为零（2）满足 的样本，其拉格朗日乘子ai必为零。由（1）可得最佳权向量W:*iiiiWa y X0()(1)0Tiiiy WXw0()(1)0Tiiiy WXw最佳的ai的求解为了求出最佳的ai，将 代回 L(W, a，) 得到：上式极大值的解即是最佳解。约束条件： c ai 0 ，i=1

6、,2,N 1111111( )21,2,NNNTiijijijiijNNNiijijijiijTijijL aaa a y y XXaa a y yXXXXXX 1NiiiiWa y X10Niiia y*1112NNiiiDiijijijiiiWa y XLaa a y yXX*()TjiiijiiijiiW Xa yXXa yX X*01()()0Niiijia yf Xf Xw 111()()2NNDiijijijiiLaa a y yf Xf X*()iiiiWa y f X111(,)2NNDiijijijiiLaa a y y K XX*01(,)0Niiijia y K XXw(,)1qijijK XXXX 22|(,)exp()ijijXXK XX(,)tanhijijK XXvXXc X1X2XdK(X1,X)K(X2,X)K(X