资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第,2,章 线性判别函数,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,模式识别,讲课教师 薛耀红,xueyh,1/76,第,5,讲 线性判别函数（,1,）,2/76,本节课主要内容,线性判别函数和决议面,Fisher,准则,3,感知准则,3/76,1,线性判别函数和决议面,线性判别函数是决议论模式识别方法中一个主要基本方法，是形式最简单判别函数，因为它含有计算简单，在一定条件下能够实现最优分类性质，所以在实际中得到了广泛应用。另外，许多其它决议论识别方法也可用判别函数来研究（非线性判别函数），它也是研究神经网络基础。现在我们就从线性判别函数开始介绍统计模式识别各种方法。,4/76,在统计模式识别方法中，首先应把能代表模式那些特征抽取出来，组成一个代表这个模式特征向量，表示为,当我们观察待分类模式时，每次观察到样本都是不一样，他们能够看成是随机产生。所以每次抽取到模式特征都应看成是随机变量，从而代表这些模式,n,维向量也应是随机向量。,5/76,所以，,假如依据以往大量观察，知道模式类别分布，从而能找出,n,维空间中模式类之间分界，就能处理模式分类问题。,这在实际上是一个经过给定样本学习过程。简便起见，在本章中我们假定抽取到模式样本边界是“整齐”而不混杂，而且以后碰到待分类模式基本上不超出学习样本分布范围，从而利用这些样本得出分类边界是无误差。,为找出这些模式之间分界面，能够利用判别函数来进行。对于,n,维空间中,c,个模式类别各给出一个由,n,个特征组成单值函数，这叫做判别函数。在,c,类情况下，我们共有,c,个判别函数，记为,6/76,判别函数,假设对一模式,X,已抽取,n,个特征，表示为：,模式识别问题就是依据模式,X,n,个特征来判别模式属于,1,2,c,类中那一类。,7/76,例以下列图：三类分类问题，它们边界限就是一个判别函数,判别函数,8/76,判别函数包含两类：,一类 是线性判别函数,：,线性判别函数,广义线性判别函数,（所谓广义线性判别函数就是把非线性判别函数映射到另外一个空间变成线性判别函数）,非线性判别函数,分段线性判别函数,二次判别函数,判别函数,9/76,判别函数性质,假如一个模式,X,属于第,i,类，则有,而假如这个模式在第,i,类和第,j,类分界面上，则有,实际上，这是由,n,维模式降为,1,维或,1,个数一个变换。,线性判别函数是全部模式特征线性组合,，表示为,10/76,二类情况下线性判别函数,可将其任意分类，或拒绝,11/76,用其能够结构一个二类模式线性分类器，如图所表示。,12/76,二类情况下，决议面与模式向量几何关系,是决议面方程，它是两类模式分界，对于二维空间情况，它是一条直线。下面，对一些关系作几何解释，如图所表示。,13/76,14/76,广义线性判别函数,这么一个非线性判别函数经过映射，变换成线性判别函数。,判别函数普通形式：,15/76,广义线性判别函数,例：如右图。,16/76,广义线性判别函数,要用二次判别函数才可把二类分开：,2,1,2,17/76,广义线性判别函数,从图能够看出：在阴影上面是,1,类，,在阴影下面是,2,类，,结论：在,X,空间非线性判别函数经过变换到,Y,空间成为线性，但,X,变为高维空间,.,2,1,2,18/76,设计线性分类器主要步骤,一组含有类别标志样本集,X=x,1,x,2,x,n,或增广样本集,Y,。,确定一个准则函数,J,，满足,:,a.,是样本集,w,w,0,或,a,函数；,b.J,值反应分类器性能,极值解对应最好策略。用最优化技术求出准则函数极值,w,*,w,0,*,或,a,*。这么就能够得到线性判别函数,19/76,2.Fisher,线性判别函数,在以后统计模式识别方法中，,维数或特征数,是一个很大问题，所以，,降低维数有时就成为处理实际问题关键,。,Fisher,线性判别函数法就是其中一个，是,R.A.,Fisher,（,1936,）在他一篇论文中提出来，其基本思想是,把,d,维模式投影到一条经过原点直线上，把维数压缩到,1,。参考如图所表示例子，进行分析。,20/76,21/76,基于这个例子能够看到，投影线方向起着至关主要作用。下面着重讨论怎样从数学上寻求最优投影线方向。首先讨论从,d,维空间到,1,维空间数学变换，,从几何上看，就是相对应 到方向为 直线上投影。寻找最好投影方向即是寻找最好变换向量 问题。,22/76,23/76,24/76,这里建立一个准则函数，它能反应不一样类别模式在 直线上投影分离程度好坏。综合上述考虑，,希望两类模式特征向量投影均值之差越大越好；同时希望同类模式特征向量投影内部尽可能密集,。定义,Fisher,准则函数,寻找使 分子尽可能大，而分母尽可能小，也就是使 尽可能大 作为投影方向。,25/76,将 变为 显函数,26/76,称为,Rayleigh,比,其含有以下性质：,，,a,是一个实数；,极值与 大小无关，只与 方向相关。,下面求准则函数极大值。将标量 对向量,求导并令其为零向量，注意到 分子分母均为标量，利用二次型关于向量求导公式可得：,27/76,上式表明：是矩阵 对应于特征值 特征向量（本特值）。,28/76,因为我们目标是寻求最好投影方向，百分比因子对此并无影响，所以，可得,29/76,线性可分性,讨论以下两个问题,对于,4,个二维样本，其在平面上分布如图所表示。若把每个样本任意分到 两种类别之一 或 ，举出其中两种线性不可分情况。,验证,N,个,d,维样本线性可分概率阈值是,3,感知准则函数,30/76,线性可分性,31/76,样本规范化,二类模式线性分类器决议规则为,引入增广样本向量和广义权向量,可将其任意分类，或拒绝,32/76,代入，决议规则可变为,取,可得,叫做规范化增广样本向量，为方便起见仍用 表示,33/76,解向量和解区,解向量,：在线性可分情况下，满足,权向量称作解向量。,解区,：解向量往往不唯一，而是由无穷多个解向量组成区域。我们称这么区域为解区。,34/76,35/76,36/76,对解区限制,对解区加以限制,目标,在于使解向量,更可靠。因为越靠,近解区中间解向,量越能对新样本,正确分类。同时也,可防止求解向量,算法不致收敛到,解区边界某点,上。,37/76,为了解线性不等式 （已规范化）需要结构一个准则函数。这里我们介绍一个惯用准则函数即所谓感知准则函数，定义为以下形式：,是因为使用权向量 而被误分类样本集合。,感知准则函数及其梯度下降算法,38/76,也就是说，当对于某个向量 ，准则函数 到达极小值话，就是解向量，这时没有样本被错分类。现在用最优化方法,梯度下降算法寻找使 到达极小值解权向量。,梯度下降算法基本思想,函数 在某点 梯度 是一个向量，它方向与过点 等量面 法线方向重合，指向 增加一方，是准则函数改变率最大方向。反之，负梯度方向则是函数 减小最快方向。所以在求准则函数 极小值时，沿负梯度方向搜索有可能最快地找到极小值。,39/76,梯度下降算法实现,先任意选择一个初始权向量 ，计算 上梯度,，从 出发在最陡方向（负梯度）上移动一个距离以得到下一个权向量值 ，用迭代公式表示为,请简述梯度下降算法,？,40/76,梯度下降算法应用举例,单样本修正法,把样本看作一个不停重复出现序列而逐一加以考虑，样本组成样本序列为：,41/76,42/76,43/76,44/76,2.3,最小平方误差准则函数,2.2.1,平方误差准则函数及其伪逆解,2.2.2 MSE,准则函数梯度下降算法,返回本章首页,45/76,前面我们介绍感知器准则函数是在,误分类样本基础,上建立，它要求对于全部样本都能满足不等式,本节介绍最小平方误差准则函数，它是一个基于,全体样本,准则函数，要求满足等式,这么就能够将原来解一组线性不等式问题转化为解一组线性方程组问题。,返回本章首页,2.3.1,平方误差准则函数及其伪逆解,46/76,引入,其中 是规范化增广样本向量,将 写成联立方程组得形式,若 是非奇异方阵，则能够得到解 ；,若 是长方阵（普通为列满秩），则是矛盾方程组，没有准确解。定义误差向量,返回本章首页,47/76,引入,其中 是规范化增广样本向量,将 写成联立方程组得形式,若 是非奇异方阵，则能够得到解 ；,若 是长方阵（普通为列满秩），则是矛盾方程组，没有准确解存在。,返回本章首页,48/76,定义误差向量,定,义平方和准则函数,为使广义权向量为最优，只需使平方和准则函数极小化，然后把对应 作为问题解，称其为矛盾方程组最小二乘解（,MSE,解）。,返回本章首页,49/76,返回本章首页,50/76,这里 是一个 维方阵，且常为非奇异；,方阵 称为 伪逆（矩阵论里称其为广义逆），且含有以下性质：,当 为非奇异方阵时，伪逆和它逆相等,普通来说,返回本章首页,51/76,从上述推倒过程能够看出，,MSE,解依赖于向量,，不一样选择能够给予解以不一样性质（参考教材,P102,）。,返回本章首页,52/76,从前面推导过程我们能够看到，用,MSE,方法按式 计算工作量很大，首先要求证实 是非奇异，然后计算 ，为,维矩阵逆。这么，我们引入梯度下降算法以防止这种问题。,误差平方和准则函数梯度,返回本章首页,2.3.2 MSE,准则函数梯度下降算法,53/76,梯度下降算法为：,（,1,）首先任意指定初始权向量 ；,（,2,）如第,k,步不能满足要求,则按下式求第,(,k,+1),步权向量,对于任意正常数，算法得到权向量序列收敛于使,返回本章首页,54/76,返回本章首页,MSE,最小平方误差方法与,Fisher,线性判别关系,在此，我们将经过适当选择,b,来说明,MSE,判别函数是和,Fisher,线性判别有直接联络。,我们假设一组,d,维样本集 ，其中 个属于 类样本记为子集 ，其中 个属于 类样本记为子集,。深入，得到增广模式向量 ，并进行规范化。不失普通性，能够假设前 个样本属于 类，后 个样本属于 。这么矩阵 就能够写成份块矩阵,55/76,返回本章首页,是 个,1,列向量，是一个矩阵，它行是属于 。,接下来，我们将证实,MSE,解和,Fisher,线性判别关系。,56/76,返回本章首页,57/76,返回本章首页,58/76,返回本章首页,59/76,返回本章首页,对于任意 ，向量 都是在 方向上，则就有,代入,60/76,2.5,多类情况下线性判别函数,前面我们重点讨论了二类模式情况下线性判别方法，不难把它们推广到多类别情况。能够把多类问题化为二类问题来处理，也能够直接按多类问题来解。,1,、按二类问题解,是把,c,类问题转化为 个二类模式分类问题。其中第,i,个问题就是用线性判别函数把属于 类模式同不属于 模式分开。,是用 次二类模式线性判别，每次只从样本集中判别指定二类决议面。,两种方法都会产生含糊区域，结合下列图进行分析。,返回本章首页,61/76,返回本章首页,62/76,返回本章首页,63/76,2,按多类问题解（结合第一节内容）,假如不用区分二类问题线性判别函数，可采取普通,c,类线性判别函数：,假如对于全部 ，有,则把模式 归到,类去,而假如这个模式在第,i,类和第,j,类分界面上，则有,返回本章首页,64/76,返回本章首页,65/76,返回本章首页,66/76,线性机器决议区域特点,（,1,）全部决议区域是凸；,（,2,）每个决议区域都是单连通；,（,3,）不存在拒绝分类死区；,返回本章首页,67/76,2.6,分段线性判别函数,以上我们介绍了线性判别函数，它一个显著优点是：,算法简单和含有“学习”能力，就是说，给定分好类样本集后，能够依据样本“学习”，自动找到线性分界面。,它另一个优点是：,假如给定 分好类,n,维模式样本集是线性可分，则基于感知准则函数算法一定收敛。,不足是,：,必须线性可分，得到分界面是一个超平面，应用有限，对于比较复杂问题，假如样本不是线性可分时，就会造成较大分类错误率。,返回本章首页,68/76,返回本章首页,69/76,为了处理比较复杂线性不可分样本分类问题，提出了非线性判别函数，如图分界面,所表示，为超曲面，非线性判别函数计算复杂，实际应用上受到较大限制。,处理问题比较简便方法是采取多个线性分界面，将它们分段连接，用分段线性判别划分去迫近分界超曲面，如图,。其优点是：因为它各段都是超平面，有可能利用已知线性判别函数来处理分类问题；它由若干超平面组成，能够很好地迫近分类超曲面，从而降低分类错误。,返回本章首页,70/76,返回本章首页,对于,n,维模式定义线性判别函数为,若判别函数不是线性，在判别函数中加入 项，就得到二次判别函数,不失普通性,对于一样维数特征，系数就多出,71/76,分段线性划分解普通情况下不是唯一，这是因为它可能由不一样样本分割方式形成。,分段线性划分也存在误差。因为，用有穷样本集得到分类边界，当样本集发生改变时，总会有产生分类误差可能。,处理误差两种方法：,增加超平面数目，到达满足当前样本正确分类目标；,适当限制超平面数目，而允许一定分类误差存在。,返回本章首页,72/76,研究了不少分段线性函数算法，下面介绍两种,先用二类线性判别函数找出一个分界面，它将样本大致分成两类。因为样本集不是线性可分，所以两面模式,是混杂。再对正反面模式样本分别应用线性判别函数求得 如此继续下去，直到每个分界面都将样本正确分类为止。连接对应各分界面，即得分段线性判别函数所决定决议面。,用一个超平面将空间划分为两个半空间，它正面仅包含一类纯样本；它反面则允许两类样本混杂。下一步则是对反面混杂样本再次使用一个超平面分割，其正面分离出一类纯样本，而反面允许两类样本混杂。直至样本被超平面完全划分为止。,返回本章首页,73/76,返回本章首页,74/76,返回本章首页,75/76,THANK YOU VERY MUCH,！,本章到此结束,下一章“,Bayes,决议理论,”,返回本章首页,结 束放映,76/76,
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
