模式识别4

2020/1/311模式识别原理华中科技大学图像识别与人工智能研究所图像分析与智能系统研究室曹治国第3章线性判别函数第3章线性判别函数3.1线性判别函数在n维特征空间中，特征矢量一、基本概念)',,(21nxxxx线性判别函数：xwwxwwxwxwxwxdnnnn')(1'012211)',,,(121nn)',,(210n)'1,,,(21nxxxx权矢量增广权矢量增广特征矢量3.1线性判别函数对C类中的每一类建立一个判别函数，C类问题就有C个判决函数则判决规则为：二、利用线性判别函数分类)(xdicixwxdii,2,1,)('ijixijxdxd则判如果)()(另一种表述形式：ijjixxdxd则判如果)]([max)(3.1线性判别函数实际情况是，输入N个样本集：求出解向量三、判别函数的求解对于两类问题：)'1,,,(21nxxxxxwxd')(},,{21Nxxx)',,,(121nn*w210'0'iiiixxwxxw对样本规范化，即对于来自类的样本，的前面加负号2ix则正确分类时：0'ixw3.1线性判别函数四、判别函数的几何意义五、求解解向量的原则采用最优化技术求解线性判决函数中的增广权矢量，需要构造准则函数，如这个准则函数达到最小/大时，取得最优解，此时用构造的判别函数对所有模式均能正确分类。*w*w3.2准则函数及其解法两个问题：（1）构造准则函数（2）如何最快地搜索到使准则函数取极小值的解*w3.2准则函数及其解法一、感知器算法算法步骤：增广的训练样本集每个类别已知，（1）令步数k=1,增量为正的常数，的各分量为较小的任意值（2）输入训练模式，计算判别函数值（3）调整增广权矢量，规则：（a）如果（b）如果（c）如果（4）如果kN，令k=k+1，GOTO（2）如果k=N，则检验对所有训练样本是否都正确分类，是则结束，否则，令k=1，GOTO（2）},,{21Nxxx21或)1(wkxkxkw)'(kkkxkwkwxkwx)()1(,0)'(1则和kkkxkwkwxkwx)()1(,0)'(2则和)()1(,0)'(0)'(21kwkwxkwxxkwxkkkk则和或和kxkw)'(3.2准则函数及其解法一、感知器算法收敛定理：如果训练模式是线性可分的，感知器训练算法在有限次迭代后可以收敛到正确的解矢量证明：。。。。。。*w3.2准则函数及其解法一、感知器算法感知器算法在多类问题中的运行步骤：增广的训练样本集每个类别已知，（1）令步数k=1,增量为正的常数，C个权矢量赋任意初值（2）输入符号未规范化的增广训练模式，计算C个判别函数值（3）调整增广权矢量，规则：（a）如果（b）如果（4）如果kN，令k=k+1，GOTO（2）如果k=N，则检验对所有训练样本是否都正确分类，是则结束，否则，令k=1，GOTO（2）},,{21Nxxxi),2,1(),1(ciwikxkiixkwkd)'()()2,1(),()1(),(),()(cikwkwijxdxdxiikjkiik则和),(),()1()()1()()1()(),()(lijkwkwxkwkwxkwkwilxdxdxjjkllkiikiklik则和),2,1(,)'(cixkwki3.2准则函数及其解法二、寻优方法--------梯度下降法函数在某点的梯度是一个向量，其方向是增长最快的方向，负梯度方向则是减少最快的方向。对于任意点，沿其负梯度方向走，下降最快，那么下一步：，为步长泰勒展开式：，其中)(aJka)(kaJ)(aJ)(aJka)(aJ))((1kkkkaJaak)()'(21)()'()()(kkkkkaaDaaaaaJaJaJ][2jiaaJD)()'(21||)(||)()(221kkkkkkkaJDaJaJaJaJ令缺点：搜索过程收敛很慢。)()'(||)(||0*kkkkkaJDaJaJddJ3.2准则函数及其解法二、寻优方法--------梯度下降法函数在某点的梯度是一个向量，其方向是增长最快的方向，负梯度方向则是减少最快的方向。对于任意点，沿其负梯度方向走，下降最快，那么下一步：，为步长泰勒展开式：，其中)(aJka)(kaJ)(aJ)(aJka)(aJ))((1kkkkaJaak)()'(21)()'()()(kkkkkaaDaaaaaJaJaJ][2jiaaJD)()'(21||)(||)()(221kkkkkkkaJDaJaJaJaJ令缺点：搜索过程收敛很慢。)()'(||)(||0*kkkkkaJDaJaJddJ3.2准则函数及其解法二、寻优方法--------牛顿法它的基本思想是企图一步达到最优点，min)(aJ)(0)()()(min)(?1111111kkkkkkkkkkaJDaaaaDaJaaJaJa)()'(21)()'()()(kkkkkaaDaaaaaJaJaJ)()'(21)()'()()(1111kkkkkkkkkaaDaaaaaJaJaJ目的：当初始点靠近极小点时，牛顿法的收敛速度快当初始点远离最优解时，D不一定正定，收敛性得不到保证D的计算量大，还要求D的逆矩阵，若D奇异，牛顿法失效3.2准则函数及其解法二、寻优方法--------共轭梯度法它的性能介于梯度下降法与牛顿法之间，它仅需要计算一阶导数的信息，但克服了梯度下降法收敛慢的缺点，又避免了存储和计算牛顿法所需的二阶导数信息。基本思想：改进搜索方向的方法，它把前一点的梯度乘以适当的系数，加到该点的梯度上，得到新的搜索方向，因此，可以说共轭梯度法是把过去的梯度和现在某点的梯度信息综合利用，用线性组合来构造更好的搜索方向kkkkkkkksaJssvaa)(111??kksvv3.2准则函数及其解法二、寻优方法--------共轭梯度法共轭梯度法是以一组对于互为共轭的向量作为一维搜索方向，使二次正定函数：达到极小值的最优化方法共轭梯度法的收敛定理：用共轭梯度法可以求得序列，使得可以证明，对于二次正定函数最多n+1步就可以使序列收敛于的极值解BxBxxbbxf'')(0,,10xx)()(10xfxf)(xf}{kx)(xf*x观察：)()'(21)()'()()(kkkkkaaDaaaaaJaJaJDBaJbaJbafxfkk)'('),(),()(03.2准则函数及其解法二、寻优方法--------共轭梯度法共轭：某一组搜索向量如果对于某个对称正定矩阵D满足：则称关于D互为共轭，且线性无关),2,1(,0'),2,1,(,0'nisDsnjjisDsiiji和nsss,,1011),(gsaJgkk则令2a从起始点开始考虑：从点出发沿方向搜索得到，假设是最佳步长则nnjiss,nsss,,101s1a2a*1v1*112svaa在点的搜索方向1122gss如果满足共轭条件，则因为则因为则21,ss0D'21sskkaaaJaa)()(J)(Jk21*1121212))((J)(J)(JsDvaaaaa'DD*11'1)]'()(J[vDaJask3.2准则函数及其解法二、寻优方法--------共轭梯度法将上式代入共轭条件：根据共轭方向法基本定理（见《最优化理论与方法》，科学出版社，p184）有：展开上式：kkkkkggggggggaJaaJa'1'11'12'211'22'1)()(J)()(J0])([)]'(J)(J[11212saJaa0)()(J0)(J12'12'aJasa0)(J)()(J111'22'saaJa3.2准则函数及其解法二、寻优方法--------共轭梯度法共轭梯度法的基本公式：kkkkkkggggg'1'1)(00)(gsaJgkkkk1k1ksgskkkksvaa*1)(min)(:kkvkkkksvaJsvaJv3.2准则函数及其解法三、一次准则函数)0()'|'(|)(kxwxwkwJ0'|'|,0'0'2'|'|,0'xwxwxwxwxwxwxw时当时当0)(minwJ对于符号已规范化的训练模式，取极小值时实现正确分类)(wJ3.2准则函数及其解法三、一次准则函数)0()'|'(|)(kxwxwkwJ将梯度下降法应用到一次准则函数中])'sgn([21J)(xxwxwwJ0'10'1)'sgn(,2/1xwxwxwk定义令准则函数的梯度：0,0')(,0')(]))('sgn([21)())(()()1(kkkkkkkkxwxkwxwkwxxkwxkwkwJkwkw感知器算法3.2准则函数及其解法四、分段二次准则函数一次准则函数只适用于线性可分情况，如果训练模式集是非线性可分的，则分类过程将不会收敛。我们构造二次准则函数，使其能够适应线性可分和非线性可分两种情况，对于线性可分，所求得的解矢量对所有模式都能正确分类，对于非线性可分，所求的解矢量使得错分的模式数目最少。3.2准则函数及其解法四、分段二次准则函数对于两类问题，设n+1维增广训练模式已符号规范化。Nxxx,,21如果训练模式是线性可分的，则存在权矢量使不等式组：成立。wNixwi,2,1,0'将上面的不等式组写成矩阵方程形式，并引入N维余量矢量0b为样本维数为样本数量矩阵是nNnNXxxxXbwXN,,)1(,)',,(021分段二次准则函数：min||||)(||)(2bwXbwXwJ3.2准则函数及其解法四、分段二次准则函数—算法步骤)2(,1),7(,,),6(min)(),5(,,,,,1,0,10),4(,,,0,),3(,,*,N,*,0),2(,,,,20,,,,0),1(,,||||1)](|[|')(4111121001000000000002GOTOkksXvwXwXsvwwvsvwJssgsgssnkkSTOPggSTOPwwSTOPwwNwXwXwwNwXwkkgbwXbwXXwJgkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk令求令时的计算互为共轭计算否则则令的整数倍为或若计算否则则如果计算否则继续则令若则令若继续令若求得计算表示不等式成立的数目用表示迭代次数