模式识别-第5讲-线性判别函数1.ppt

模式识别,授课教师 薛耀红 ,第5讲 线性判别函数（1）,本节课主要内容,线性判别函数和决策面 Fisher准则 3 感知准则,1 线性判别函数和决策面,线性判别函数是决策论模式识别方法中的一种重要的基本方法，是形式最简单的判别函数，由于它具有计算简单，在一定条件下能够实现最优分类的性质，因此在实际中得到了广泛的应用。此外，许多其它决策论识别方法也可用判别函数来研究（非线性判别函数），它也是研究神经网络的基础。现在我们就从线性判别函数开始介绍统计模式识别的各种方法。,在统计模式识别方法中，首先应把能代表模式的那些特征抽取出来，构成一个代表这个模式的特征向量，表示为 当我们观察待分类模式时，每次观察到的样本都是不同的，他们可以看成是随机产生的。所以每次抽取到的模式特征都应看成是随机变量，从而代表这些模式的 n 维向量也应是随机向量。,所以，如果根据以往大量的观察，知道模式类别的分布，从而能找出n 维空间中模式类之间的分界，就能解决模式的分类问题。这在实际上是一个通过给定样本的学习过程。 简便起见，在本章中我们假定抽取到的模式样本的边界是“整齐”而不混杂的，而且以后遇到的待分类模式基本上不超过学习样本的分布范围，从而利用这些样本得出的分类边界是无误差的。 为找出这些模式之间的分界面，可以利用判别函数来进行。对于n 维空间中的 c 个模式类别各给出一个由 n 个特征组成的单值函数，这叫做判别函数。在 c 类的情况下，我们共有 c个判别函数，记为,判别函数,假设对一模式X已抽取n个特征，表示为：,模式识别问题就是根据模式X的n个特征来判别模式属于1 ,2 , , c 类中的那一类。,例如下图：三类的分类问题，它们的边界线就是一个判别函数,判别函数,判别函数包含两类： 一类 是线性判别函数： 线性判别函数 广义线性判别函数（所谓广义线性判别函数就是把非线性判别函数映射到另外一个空间变成线性判别函数） 非线性判别函数 分段线性判别函数 二次判别函数,判别函数,判别函数的性质 假如一个模式 X 属于第 i 类，则有 而如果这个模式在第 i 类和第 j 类的分界面上，则有 事实上，这是由 n 维模式降为1维或1个数的一种变换。 线性判别函数是所有模式特征的线性组合，表示为,二类情况下的线性判别函数,可将其任意分类，或拒绝,用其可以构造一个二类模式的线性分类器，如图所示。,二类情况下，决策面与模式向量的几何关系 是决策面方程，它是两类模式的分界，对于二维空间的情况，它是一条直线。下面，对一些关系作几何解释，如图所示。,广义线性判别函数,这样一个非线性判别函数通过映射，变换成线性判别函数。,判别函数的一般形式：,广义线性判别函数,例：如右图。,广义线性判别函数,要用二次判别函数才可把二类分开：,广义线性判别函数,从图可以看出：在阴影上面是1类，在阴影下面是2类， 结论：在X空间的非线性判别函数通过变换到Y空间成为线性的，但X变为高维空间.,设计线性分类器的主要步骤,一组具有类别标志的样本集 X=x1,x2,xn 或增广样本集Y。 确定一个准则函数J，满足: a. 是样本集w,w0,或a的函数； b. J的值反映分类器的性能,极值解对应最好策略。用最优化技术求出准则函数的极值w*, w0*, 或a*。这样就可以得到线性判别函数,2. Fisher线性判别函数,在以后的统计模式识别方法中，维数或特征数是一个很大的问题，因此，降低维数有时就成为处理实际问题的关键。Fisher线性判别函数法就是其中一种，是R.A. Fisher（1936）在他的一篇论文中提出来的，其基本思想是把 d 维模式投影到一条通过原点的直线上，把维数压缩到1。参照如图所示的例子，进行分析。,基于这个例子可以看到， 投影线的方向起着至关重要的作用。下面着重讨论如何从数学上寻求最优的投影线方向。首先讨论从 d 维空间到 1 维空间的数学变换， 从几何上看， 就是相对应的 到方向为 的直线上的投影。寻找最好的投影方向即是寻找最好的变换向量 的问题。,这里建立一个准则函数，它能反映不同类别模式在 直线上投影分离程度的好坏。综合上述考虑，希望两类模式特征向量投影均值之差越大越好；同时希望同类模式特征向量的投影内部尽量密集。定义Fisher准则函数 寻找使 分子尽可能大，而分母尽可能小，也就是使 尽可能大的 作为投影方向。,将 变为 的显函数,称为 Rayleigh比,其具有以下性质： ，a 是一个实数； 的极值与 的大小无关，只与 的方向有关。 下面求准则函数的极大值。将标量 对向量 求导并令其为零向量，注意到 的分子分母均为标量，利用二次型关于向量求导的公式可得：,上式表明： 是矩阵 相应于特征值 的特征向量（本特值）。,由于我们的目的是寻求最好的投影方向， 的比例因子对此并无影响，因此，可得,线性可分性 讨论如下的两个问题 对于4个二维样本，其在平面上的分布如图所示。若把每个样本任意分到 两种类别之一 或 ，举出其中的两种线性不可分情况。 验证 N 个 d 维样本线性可分的概率阈值是,3 感知准则函数,线性可分性,样本的规范化 二类模式的线性分类器的决策规则为 引入增广样本向量和广义权向量,可将其任意分类，或拒绝,代入，决策规则可变为 取 可得 叫做规范化增广样本向量，为方便起见仍用 表示,解向量和解区,解向量：在线性可分情况下，满足 的权向量称作解向量。 解区：解向量往往不唯一，而是由无穷多个解向量组成的区域。我们称这样的区域为解区。,对解区的限制 对解区加以限制的 目的在于使解向量 更可靠。因为越靠 近解区中间的解向 量越能对新的样本 正确分类。同时也 可避免求解向量 的算法不致收敛到 解区边界的某点 上。,为了解线性不等式 （ 已规范化 ）需要构造一个准则函数。这里我们介绍一种常用的准则函数即所谓的感知准则函数，定义为如下的形式： 是由于使用权向量 而被误分类的样本集合。,感知准则函数及其梯度下降算法,也就是说，当对于某个向量 ，准则函数 达到极小值的话， 就是解向量，这时没有样本被错分类。现在用最优化方法梯度下降算法寻找使 达到极小值的解权向量。 梯度下降算法基本思想 函数 在某点 的梯度 是一个向量，它的方向与过点 的等量面 的法线方向重合，指向 增加的一方，是准则函数变化率最大的方向。反之，负梯度的方向则是函数 减小最快的方向。所以在求准则函数 的极小值时 ，沿负梯度方向搜索有可能最快地找到极小值。,梯度下降算法的实现 先任意选择一个初始的权向量 ，计算 上的梯度 ，从 出发在最陡方向（负梯度）上移动一个距离以得到下一个权向量值 ，用迭代公式表示为 请简述梯度下降算法？,梯度下降算法应用举例单样本修正法 把样本看作一个不断重复出现的序列而逐个加以考虑，样本组成的样本序列为：,2.3 最小平方误差准则函数,2.2.1 平方误差准则函数及其伪逆解 2.2.2 MSE准则函数的梯度下降算法,返回本章首页,前面我们介绍的感知器准则函数是在误分类样本的基础上建立的，它要求对于所有样本都能满足不等式 本节介绍的最小平方误差准则函数，它是一个基于全体样本的准则函数，要求满足等式 这样就可以将原来解一组线性不等式的问题转化为解一组线性方程组的问题。,返回本章首页,2.3.1 平方误差准则函数及其伪逆解,引入 其中 是规范化增广样本向量 将 写成联立方程组得形式 若 是非奇异方阵，则可以得到解 ； 若 是长方阵（一般为列满秩），则是矛盾方程组，没有精确解。定义误差向量,返回本章首页,引入 其中 是规范化增广样本向量 将 写成联立方程组得形式 若 是非奇异方阵，则可以得到解 ； 若 是长方阵（一般为列满秩），则是矛盾方程组，没有精确解存在。,返回本章首页,定义误差向量 定义平方和准则函数 为使广义权向量为最优，只需使平方和准则函数极小化，然后把相应的 作为问题的解，称其为矛盾方程组的最小二乘解（MSE解）。,返回本章首页,返回本章首页,这里 是一个 维方阵，且常为非奇异； 方阵 称为 的伪逆（矩阵论里称其为广义逆），且具有以下性质： 当 为非奇异方阵时， 的伪逆和它的逆相等 一般来说,返回本章首页,从上述推倒过程可以看出，MSE解依赖于向量 ， 的不同选择可以给予解以不同的性质（参考教材P102）。,返回本章首页,从前面的推导过程我们可以看到，用MSE方法按式 的计算工作量很大，首先要求证明 是非奇异的，然后计算 ，为 维矩阵的逆。 这样，我们引入梯度下降算法以避免这种问题。 误差平方和准则函数的梯度,返回本章首页,2.3.2 MSE准则函数的梯度下降算法,梯度下降算法为： （1）首先任意指定初始权向量 ； （2）如第 k 步不能满足要求 则按下式求第 (k+1) 步的权向量 对于任意的正常数，算法得到的权向量序列收敛于使,返回本章首页,返回本章首页,MSE最小平方误差方法与Fisher线性判别的关系 在此，我们将通过适当选择 b 来说明 MSE 判别函数是和 Fisher 线性判别有直接联系的。 我们假设一组 d 维样本集 ，其中 个属于 类的样本记为子集 ，其中 个属于 类的样本记为子集 。进一步，得到增广模式向量 ，并进行规范化。不失一般性，可以假设前 个样本属于 类，后 个样本属于 。这样矩阵 就可以写成分块矩阵,返回本章首页,是 个 1 的列向量， 是一个矩阵，它的行是属于 。 接下来，我们将证明MSE解和Fisher线性判别关系。,返回本章首页,返回本章首页,返回本章首页,返回本章首页,对于任意的 ，向量 都是在 的方向上，则就有 代入,2.5 多类情况下的线性判别函数,前面我们重点讨论了二类模式情况下的线性判别方法，不难把它们推广到多类别的情况。可以把多类问题化为二类问题来解决，也可以直接按多类问题来解。 1、按二类问题解 是把 c 类问题转化为 个二类模式的分类问题。其中第 i 个问题就是用线性判别函数把属于 类的模式同不属于 的模式分开。 是用 次二类模式线性判别，每次只从样本集中判别指定的二类的决策面。 两种方法都会产生模糊区域，结合下图进行分析。,返回本章首页,返回本章首页,返回本章首页,2 按多类问题解（结合第一节内容） 如果不用区别二类问题的线性判别函数，可采用一般的c 类线性判别函数： 如果对于所有的 ，有 则把模式 归到 类去 而如果这个模式在第 i 类和第 j 类的分界面上，则有,返回本章首页,返回本章首页,返回本章首页,线性机器的决策区域的特点 （1）所有决策区域是凸的； （2）每个决策区域都是单连通的； （3）不存在拒绝分类的死区；,返回本章首页,2.6 分段线性判别函数,以上我们介绍了线性判别函数，它的一个显著的优点是：算法简单和具有“学习”的能力，就是说，给定分好类的样本集后，能够根据样本“学习”，自动找到线性分界面。它的另一个优点是：如果给定的 分好类的n维模式样本集是线性可分的，则基于感知准则函数的算法一定收敛。不足是：必须线性可分，得到的分界面是一个超平面，应用有限，对于比较复杂的问题，如果样本不是线性可分时，就会导致较大的分类错误率。,返回本章首页,返回本章首页,为了解决比较复杂的线性不可分样本分类问题，提出了非线性判别函数，如图的分界面所示，为超曲面，非线性判别函数计算复杂，实际应用上受到较大的限制。 解决问题比较简便的方法是采用多个线性分界面，将它们分段连接，用分段线性判别划分去逼近分界的超曲面，如图。 其优点是：由于它的各段都是超平面，有可能利用已知的线性判别函数来解决分类问题；它由若干超平面组成，可以较好地逼近分类的超曲面，从而减少分类错误。,返回本章首页,返回本章首页,对于 n 维模式定义的线性判别函数为 若判别函数不是线性的，在判别函数中加入 项，就得到二次判别函数 不失一般性 对于同样维数的特征，系数就多出, 分段线性划分的解一般情况下不是唯一的，这是由于它可能由不同的样本分割方式形成。 分段线性划分也存在误差。因为，用有穷样本集得到的分类边界，当样本集发生变化时，总会有产生分类误差的可能。 处理误差的两种方法： 增加超平面数目，达到满足当前样本正确分类的目的； 适当限制超平面数目，而允许一定的分类误差存在。,返回本章首页,研究了不少分段线性函数的算法，下面介绍两种 先用二类线性判别函数找出一个分界面， 它将样本大致分成两类。因为样本集不是线性可分的，所以两面的模式