模式识别-第2章 线性判别函数_第三讲

第二章线性判别函数线性不可分情况tibaymin:tiibay0tiibay不等式组求解方程组求解2.4最小平方误差算法(LMSE)LMSE方法的基本思想是将求解线性不等式组的问题转化为求解线性方程组：1011101202121202ddnnnddnyyyabyyyabyyyab,Ya=b0b当时，方程为超定方程nd超定方程的最小误差平方解最小平方误差的准则函数（MSE）定义误差矢量e，用e长度的平方作为准则函数：eYab221ntSiiiJbaYabay权值矢量的求解(伪逆求解法)2tSJaYYab0ttYYaYb1ttYYYbaYb1ttYYYY称为Y的伪逆矩阵，有2SJaYabYYI伪逆矩阵的更一般形式：1limttYYYIY该极限总存在，且是的MSE解aYbYab解由b决定，有用，却不一定线性可分有两类模式的训练样本：ω1：{(1,2),(2,0)}ω2：{(3,1),(2,3)}用LMSE算法求取判别函数，将两类样本分开。令所有裕量均为1，求判决边界方程。1，通过向量增广得到y：112120131123Y2，计算Y的伪逆1ttYYYY3，b=(1,1,1,1)t,计算a=Y+b5/413/123/47/121/21/61/21/601/301/3(11/3,4/3,2/3)t权值矢量的求解(迭代求解)2tSJaYYab2SJaYab1ttYYYY计算量巨大。迭代求解法：梯度下降法11ntiiiikkkbaaayy最小均方算法（Least-mean-squared，LMS）1()()tkkkkkbkkaaayy1/kk1/kk权值矢量的求解(迭代求解法)1.begininitializea(0),b,θ,η(•),k0；2.dokk+1；3.4.until5.returna6.end11ntiiiikkkbaaayy1ntiiiikbayyLMSE算法的特点算法的收敛依靠η(k)的衰减，一般取η(k)=η(1)/k；算法对于线性不可分的训练样本也能够收敛于一个均方误差最小解；取b=1时，当样本数趋于无穷多时，算法的解以最小均方误差逼近贝叶斯判别函数；当训练样本线性可分的情况下，算法未必收敛于一个分类超平面。线性判别函数下降法（小结）名称固定增量法准则算法条件备注若线性可分，收敛到的解；总有界ttpJayay01kkkaay=0tayka线性判别函数下降法（小结）名称可变增量法准则算法条件备注若线性可分，收敛到的解；若有限收敛ttpJbayayb1()kkkkaay=0tay0k10,lim,mmkkk2211lim0mmmkkkk线性判别函数下降法（小结）名称松弛法准则算法条件备注若线性可分，收敛到的解；若有限收敛到的解22ttpJbayayybtbay0b0221()()tkkkkkkbkaaayyy0tay线性判别函数下降法（小结）名称伪逆法准则算法条件备注典型的MSE解。特别选择b，将获得Fisher线性判别和对贝叶斯判别的MSE逼近2SJaYab1ttaYYYbYbtYY非奇异线性判别函数下降法（小结）名称最小均方（LMS）法准则算法条件备注趋于极小化的解221ntSiiiJbaYabay1()()tkkkkkbkkaaayy0,0,kkSJ最优分类界面样本集与分类界面之间的间隔定义为样本与分类界面之间几何间隔的最小值。最优分类界面：给定线性可分样本集，能够将样本分开的最大间隔超平面。支持矢量距离最优分类界面最近的这些训练样本称为支持矢量；最优分类界面完全由支持矢量决定，然而支持矢量的寻找比较困难。5.5支持矢量机(SVM,SupportVectorMachine)函数间隔：样本xi到分类界面g(x)=0的函数间隔定义为：几何间隔：缩放权向量和阈值不改变分类函数γixig(x)=wtx+w0=0ib0tiiibgwxwxiibwSVM的准则函数给定两类问题的线性可分样本集合{(y1,z1),…,(yn,zn)}，其中z为样本的类别标号：能够将样本线性分开的分类界面满足：亦即可以通过调整权值w和w0将样本集合的最小函数间隔调整为1。121,1,iiizyy01tiizwwySVM的准则函数样本集到分类界面的几何间隔：最大，亦即||w||最小，所以SVM可以变为如下优化问题：在满足的条件下，最小化准则函数：1w212SVMJw01tiizwwy把函数间隔固定为1，对离分类面最近的样本有：()1gy()gywKuhn-Tucker构造法Kuhn-Tucker定理1629Fermat定理——无约束条件下的函数极值1788Lagrange乘子法——等式约束下的函数极值1951Kuhn-Tucker定理：（凸）不等式约束下，最小化某一类型的（凸）目标函数01tiizwwy212SVMJwKuhn-Tucker定理凸集合：集合中任意两点的连线都属于该集合凸函数：对于任意两点x,y,Jensen不等式成立：(1)()(1)()fxfxfyX是一个线性空间，A是空间的一个凸子集，fk(x),k=0,1,…,m是凸函数凸优化：最小化泛函0()inffx约束条件为,()0,1,,kxAfxkm最小化泛函：0()inffx约束条件：,()0,1,,kxAfxkm011(,,)(),(,)mkkmkLLxfxλλ如果在满足约束条件下最小化，则存在不同时为0的使下列三条件成立：令x0()fx01,(,)mλ(a):最小值原理(b):非负性条件(c):Kuhn-Tucker条件00min(,,)(,,)xALxLxλλ0k()0,1,kkfxkmKuhn-Tucker定理1，构造Lagrange函数20011,,1,02ntiiiiiLwzwwαwwy01,,0niiiiLwzwαwyw010,,0niiiLwzwwα1niiiizwy(1)10niiiz(2)01,11,,2nntiijijijiijLwzzwαyy2，分别对参数w和w0求导：3，将(1),(2)代人0,,Lwwα二次规划问题10,niiiz0,iC1,,in约束条件：SVM解的讨论这是一个典型的不等式约束条件下的二次优化问题，其解法的基础是Kuhn-Tucker定理；首先求解的是n个Lagrange乘子，n为训练样本数。但根据Kuhn-Tucker定理，有：000,100,10tiiitiiizwzwwywy满足第2个条件的yi称为支持矢量。()0kkfx010tiiizwwySVM解的讨论根据找到的支持矢量yi以及相应的Lagrange乘子αi，计算权矢量w：1niiiizwy偏置w0可以用支持矢量满足的条件求得：01tiizwwy线性判别函数小结感知器算法松弛算法最小平方误差（伪逆、迭代）最优分类面（支持向量，K_T条件，二次规划）