模式识别-第5章线性判别函数

1、模式识别 线性判别函数第五章第五章 线性判别函数线性判别函数模式识别 概率密度函数的非参数估计5.1 线性判别函数和判别界面线性判别函数和判别界面模式识别 概率密度函数的非参数估计线性不可分情况线性不可分情况模式识别 概率密度函数的非参数估计线性判别函数线性判别函数n x=(x1, x2, xd)t: 特征矢量；特征矢量；n w=(w1, w2, , wd)t: 权矢量；权矢量；n w0：偏置：偏置(bias)。 0tgwxw x模式识别 概率密度函数的非参数估计线性判别函数的增广形式线性判别函数的增广形式n y=(1, x1, x2, xd)t: 增广的特征矢量；增广的特征矢量；n a=(w

2、0, w1, w2, , wd)t: 增广的权矢量；增广的权矢量； tgya y模式识别 概率密度函数的非参数估计两类问题线性判别准则两类问题线性判别准则 1020,0,0,tgwxxw xx拒识模式识别 概率密度函数的非参数估计线性分类器的分类界面线性分类器的分类界面模式识别 概率密度函数的非参数估计分类界面的几何解释分类界面的几何解释1.线性分类界面线性分类界面H是是d维空间中的一个超平面；维空间中的一个超平面；2.分类界面将分类界面将d维空间分成两部分，维空间分成两部分，R1，R2分别分别属于两个类别；属于两个类别；3.判别函数的权矢量判别函数的权矢量w是一个垂直于分类界面是一个垂直于分

3、类界面H的矢量，其方向指向区域的矢量，其方向指向区域R1 ；4.偏置偏置w0与原点到分类界面与原点到分类界面H的距离有关：的距离有关：00wr w模式识别 概率密度函数的非参数估计多类问题（情况一）多类问题（情况一）n 每一类模式可以用一个超平面与其它类别每一类模式可以用一个超平面与其它类别分开分开；n c类问题类问题c个两类问题，个两类问题，需要需要c个线性分个线性分类界面类界面；n 第第i类与其它类别之间的判别函数：类与其它类别之间的判别函数： tiigya y模式识别 概率密度函数的非参数估计多类问题（情况一）分类界面多类问题（情况一）分类界面模式识别 概率密度函数的非参数估计多类问题（

4、情况一）判别规则多类问题（情况一）判别规则n 若存在若存在i，使得，使得gi(x)0， gj(x)0，ji，则判，则判别别x属于属于i i类类；n 其它情况，拒识。其它情况，拒识。模式识别 概率密度函数的非参数估计多类问题（情况二）多类问题（情况二）n 每两个类别之间可以用一个超平面分开每两个类别之间可以用一个超平面分开；n c类问题类问题c(c-1)/2个两类问题；个两类问题；n 第第i类与第类与第j类之间的判别函数为：类之间的判别函数为： ,tijijgya yij模式识别 概率密度函数的非参数估计多类问题（情况二）分类界面多类问题（情况二）分类界面模式识别 概率密度函数的非参数估计多类问

5、题（情况二）判别准则多类问题（情况二）判别准则n 如果对任意如果对任意ji ，有，有gij(x)0 ，则决策，则决策x属于属于i。 n 其它情况，则拒识。其它情况，则拒识。模式识别 概率密度函数的非参数估计多类问题（情况三）多类问题（情况三）n 情况三是情况二的特例，情况三是情况二的特例，不存在拒识区域不存在拒识区域。 模式识别 概率密度函数的非参数估计多类问题（情况三）判别函数多类问题（情况三）判别函数n c个类别个类别需要需要c个线性函数个线性函数： 1 1220tiiiiiddigw xw xw xwya yn判别准则：判别准则： 1max,ijj cgg xxix模式识别 概率密度函数

6、的非参数估计5.2 线性判别函数的学习线性判别函数的学习 n 问题的提出问题的提出：假设有一个包含：假设有一个包含n个样本的集个样本的集合合y1, y2, , yn, 一些标记为一些标记为1 1, ,另一些标记另一些标记为为2 2，用这些样本来确定一个判别函数，用这些样本来确定一个判别函数g(y)=ag(y)=at ty y的权矢量的权矢量a。n 在线性可分的情况下在线性可分的情况下，希望得到的判别函数，希望得到的判别函数能够将所有的训练样本正确分类；能够将所有的训练样本正确分类；n 线性不可分的情况下线性不可分的情况下，判别函数产生错误的，判别函数产生错误的概率最小。概率最小。模式识别 概率

7、密度函数的非参数估计训练样本的规范化训练样本的规范化120,0,tiitiia yya yy120,0,tiitiia yya yyn 非规范化：非规范化：n 规范化：规范化：模式识别 概率密度函数的非参数估计解区域的几何解释解区域的几何解释(特征空间中）特征空间中）n 特征空间中：矢量特征空间中：矢量a是垂直于分类界面的是垂直于分类界面的矢量：模式识别 概率密度函数的非参数估计解区域的几何解释解区域的几何解释(权空间中）权空间中）n 权空间中，权空间中，atyi=0是一个通过原点的超平面，是一个通过原点的超平面，yi是法向量，而是法向量，而a是空间中一个点。是空间中一个点。模式识别 概率密度

8、函数的非参数估计一般求解方法一般求解方法梯度下降法梯度下降法n求解不等式组采用最优化的方法求解不等式组采用最优化的方法：1.定义一个准则函数定义一个准则函数J(a)，当，当a是解向量时，是解向量时，J(a)为最小；为最小；2.采用最优化方法求解标量函数采用最优化方法求解标量函数J(a)的极小值。的极小值。n最优化方法采用最多的是最优化方法采用最多的是梯度下降法梯度下降法，设定初始，设定初始权值矢量权值矢量a(1)，然后沿梯度的负方向迭代计算：，然后沿梯度的负方向迭代计算： 1kkkJkaaa其中其中(k)(k)称为学习率，或称步长。称为学习率，或称步长。模式识别 概率密度函数的非参数估计5.3

9、 感知器算法感知器算法(Perceptron)n 最直观的准则函数定义是最直观的准则函数定义是最少错分样本数准则最少错分样本数准则： JN(a) = 样本集合中被错误分类的样本数；样本集合中被错误分类的样本数；模式识别 概率密度函数的非参数估计感知器准则感知器准则n 以错分样本到判别界面以错分样本到判别界面距离之和作为准则（距离之和作为准则（感感知器准则知器准则）：）： tPJyaa yYPJyyY模式识别 概率密度函数的非参数估计感知器算法感知器算法(批量调整版本批量调整版本)1.begin initialize , , k02. do kk+13. 4. until 5.return a6

10、.end 0a 1kkkkyaayY kkyyY模式识别 概率密度函数的非参数估计感知器算法感知器算法(单样本调整版本单样本调整版本)1.begin initialize , k02. do k(k+1)mod n3. if yk is misclassified by a then 4. until all patterns properly classified5.return a6.end 0a 1kkkaay模式识别 概率密度函数的非参数估计例例5.1n 有两类模式的训练样本：有两类模式的训练样本：1： (0,0), (0,1) 2： (1,0), (1,1) 用感知器算法求取判别函数

11、，将两类样本分用感知器算法求取判别函数，将两类样本分开。开。模式识别 概率密度函数的非参数估计感知器算法的特点感知器算法的特点n 当样本线性可分情况下，学习率当样本线性可分情况下，学习率 合适时，合适时，算法具有收敛性；算法具有收敛性；n 收敛速度较慢；收敛速度较慢；n 当样本线性不可分情况下，算法不收敛，且当样本线性不可分情况下，算法不收敛，且无法判断样本是否线性可分。无法判断样本是否线性可分。 模式识别 概率密度函数的非参数估计5.4 最小平方误差算法最小平方误差算法(LMSE)n LMSE方法的基本思想是将求解线性不等式组的方法的基本思想是将求解线性不等式组的问题转化为求解线性方程组：问

12、题转化为求解线性方程组：1011101202121202ddnnnddnyyyabyyyabyyyab,Ya = b0b模式识别 概率密度函数的非参数估计最小平方误差的准则函数最小平方误差的准则函数n 定义误差矢量定义误差矢量e，用，用e长度的平方作为准则长度的平方作为准则函数（函数（LMSE准则准则）：）：eYab 2SJaYab模式识别 概率密度函数的非参数估计权值矢量的求解权值矢量的求解(伪逆求解法伪逆求解法) 2tSJaYYab0ttY YaY b1ttaY YY bY b1ttYY YY称为伪逆矩阵称为伪逆矩阵模式识别 概率密度函数的非参数估计例例5.2 n 有两类模式的训练样本：有

13、两类模式的训练样本：1： (0,0), (0,1) 2： (1,0), (1,1) 用用LMSE算法求取判别函数，将两类样本分算法求取判别函数，将两类样本分开。开。模式识别 概率密度函数的非参数估计权值矢量的求解权值矢量的求解(迭代求解法迭代求解法)1.begin initialize a(0), b, , (), k0；2. do kk+1；3. 4. until 5.return a6.end 11ntiiiikkkbaaa yy 1ntiiiikba yy模式识别 概率密度函数的非参数估计LMSE算法的特点算法的特点n 算法的收敛依靠算法的收敛依靠(k)的衰减，一般取的衰减，一般取(k)

14、=(1)/k；n 算法对于线性不可分的训练样本也能够收敛于算法对于线性不可分的训练样本也能够收敛于一个均方误差最小解；一个均方误差最小解；n 取取b=1时，当样本数趋于无穷多时，算法的解时，当样本数趋于无穷多时，算法的解以最小均方误差逼近贝叶斯判别函数；以最小均方误差逼近贝叶斯判别函数；n 当训练样本线性可分的情况下，算法未必收敛当训练样本线性可分的情况下，算法未必收敛于一个分类超平面。于一个分类超平面。模式识别 概率密度函数的非参数估计LMSE算法算法模式识别 概率密度函数的非参数估计5.5 支持矢量机支持矢量机(SVM, Support Vector Machine)n 问题的提出问题的提

15、出：模式识别 概率密度函数的非参数估计函数间隔和几何间隔函数间隔和几何间隔n 函数间隔函数间隔：样本：样本xi到分类界到分类界面面g(x)=0的函数间隔的函数间隔 定定义为：义为：n 几何间隔几何间隔：ib0tiiibgwxw xiibw模式识别 概率密度函数的非参数估计最优分类界面最优分类界面n 样本集与分类界面样本集与分类界面之间的间隔之间的间隔 定义定义为样本与分类界面为样本与分类界面之间几何间隔的最之间几何间隔的最小值。小值。n 最优分类界面最优分类界面：给：给定线性可分样本集，定线性可分样本集，能够将样本分开的能够将样本分开的最大间隔超平面。最大间隔超平面。模式识别 概率密度函数的非

16、参数估计支持矢量支持矢量n 距离最优分类界面最近的这些训练样本称为距离最优分类界面最近的这些训练样本称为支持矢量支持矢量；n 最优分类界面完全由支持矢量决定，然而支最优分类界面完全由支持矢量决定，然而支持矢量的寻找比较困难。持矢量的寻找比较困难。模式识别 概率密度函数的非参数估计SVM的准则函数的准则函数n 给定两类问题的线性可分样本集合给定两类问题的线性可分样本集合(y1,z1), , (yn,zn)，其中其中z为样本的为样本的类别标号类别标号：n 可分性约束可分性约束：能够将样本线性分开的分类界面满足：能够将样本线性分开的分类界面满足：亦即可以通过调整权值亦即可以通过调整权值w和和w0将样

17、本集合的最小函数间将样本集合的最小函数间隔调整为隔调整为1。121,1,iiizyy01tiizww y模式识别 概率密度函数的非参数估计SVM的准则函数的准则函数n 样本集到分类界面的几何间隔：样本集到分类界面的几何间隔：n 最大，亦即最大，亦即|w|最小，所以最小，所以SVM可以变为如下的优可以变为如下的优化问题：在满足化问题：在满足的条件下，最小化准则函数（的条件下，最小化准则函数（SVM准则准则）：）：1w212SVMJw01tiizww y模式识别 概率密度函数的非参数估计Kuhn-Tucker构造法构造法n 构造构造Lagrange函数函数n 分别对参数分别对参数w和和w0求导：求

18、导：20011,1 ,02ntiiiiiLwzwwww y01,0niiiiLwzwwyw010,0niiiLwzww模式识别 概率密度函数的非参数估计Kuhn-Tucker构造法构造法n 因此有：因此有：n 带入带入Lagrange函数，有：函数，有：1niiiizwy10niiiz01,11,2nntiijijijii jLwz z wy y模式识别 概率密度函数的非参数估计Kuhn-Tucker构造法构造法n 因此因此SVM的优化问题可以转化为一个经典的的优化问题可以转化为一个经典的二次规划问二次规划问题题：约束条件：约束条件： 1,112nntiijijijii jLz z y y10

19、niiiz0,iC1,in模式识别 概率密度函数的非参数估计SVM解的讨论解的讨论n 这是一个典型的不等式约束条件下的二次优化这是一个典型的不等式约束条件下的二次优化问题，其解法的基础是问题，其解法的基础是Kuhn-Tucker定理；定理；n 首先求解的是首先求解的是n个个Lagrange乘子，乘子，n为训练样为训练样本数。但根据本数。但根据Kuhn-Tucker定理，有：定理，有：满足第满足第2，3个条件的个条件的yi称为称为支持矢量支持矢量。0001,01,01,tiiitiiitiiizwzwCzwCw xw xw x模式识别 概率密度函数的非参数估计支持向量和支持向量和Lagrange

20、系数系数模式识别 概率密度函数的非参数估计SVM解的讨论解的讨论n 根据找到的支持矢量根据找到的支持矢量yi以及相应的以及相应的Lagrange乘子乘子i i，计算，计算权矢量权矢量w w：1niiiizwyn 偏置偏置w w0 0可以用支持矢量满足的条件求得：可以用支持矢量满足的条件求得：01tiizww y模式识别 概率密度函数的非参数估计Matlab实现实现n Bioinformatics ToolboxBioinformatics Toolbox中包含了中包含了LibSVMLibSVM的实现的实现函数；函数；n 学习学习函数函数： SVMSTruct = svmtrain( X,L,

21、KERNELFUNCTION, linear, BOXCONSTRAIN, C, AUTOSCALE, false）；）；X: n*d矩阵，矩阵，L：n*1矢量矢量n 识别函数识别函数： Labels = svmclassify( X, SVMSTruct );模式识别 概率密度函数的非参数估计5.6 多类别线性判别函数的学习多类别线性判别函数的学习 n 方法一方法一：根据：根据5.1节介绍的前两种情况，分别转换节介绍的前两种情况，分别转换为为c个两类问题，或个两类问题，或c(c-1)/2个两类问题分别处理；个两类问题分别处理；n 方法二方法二：对于情况三，可以采用：对于情况三，可以采用Kes

22、ler构造法训构造法训练；练；n 方法三方法三：设计感知器网络进行识别。：设计感知器网络进行识别。模式识别 概率密度函数的非参数估计Kesler构造法（扩展的感知器算法）构造法（扩展的感知器算法）1.初始化初始化c个权向量个权向量ai(1)，k1；2.输入增广特征矢量输入增广特征矢量yk（只增加一维（只增加一维1，不改变特征的符，不改变特征的符号），计算号），计算c个判别函数的输出：个判别函数的输出： tikikgkyay3.修改权矢量：修改权矢量：若若yk属于属于i i类类，而存在，而存在gi(yk)gj(yk)，则：，则： ai(k+1) = ai(k) + yk； aj(k+1) = a

23、j(k) - yk al(k+1) = al(k)，lj, i4.重复上述过程，直到全部样本被正确分类为止。重复上述过程，直到全部样本被正确分类为止。模式识别 概率密度函数的非参数估计两类问题的感知器网络两类问题的感知器网络模式识别 概率密度函数的非参数估计多类问题的感知器网络多类问题的感知器网络模式识别 概率密度函数的非参数估计两层感知器网络的训练样本两层感知器网络的训练样本n 给定样本集合给定样本集合(y1,t1), (y2,t2), , (yn,tn)，其中，其中yi为增广特征矢量，为增广特征矢量，ti称为期望输出；称为期望输出；n c个输出层神经元时，可设定期望输出为：个输出层神经元时

24、，可设定期望输出为：第第1类样本：类样本：(+1,-1,-1,-1) 第第2类样本：类样本：(-1,+1,-1,-1)第第3类样本：类样本：(-1,-1,+1,-1) 第第4类样本：类样本：(-1,-1,-1,+1)n 编码输出时：编码输出时：第第1类样本：类样本：(-1,-1) 第第2类样本：类样本：(-1,+1)第第3类样本：类样本：(+1,-1) 第第4类样本：类样本：(+1,+1)模式识别 概率密度函数的非参数估计两层感知器网络的训练方法两层感知器网络的训练方法n 可以采用最小均方误差算法，权值调整公式为：可以采用最小均方误差算法，权值调整公式为： 11ntiiiikkkAAtAyy其中其中A为权值矢量矩阵，为权值矢量矩阵，ti为第为第i个样本个样本yi 的期的期望输出矢量。望输出矢量。模式识别 概率密度函数的非参数估计5.7 线性分类器的局限性线性分类器的局限性n 线性分类器的分类能力不强，能够很好地解决线线性分类器的分类能力不强，能够很好地解决线性可分的问题，而对非线性可分的问题无法解决，性可分的问题，而对非线性可分的问题无法解