模式识别线性判别函数.ppt

1、第五章 线性判别函数（分类器，参数分类器）,5.1 引言 5.2 Fisher 线性判别 5.3 感知准则函数（Perceptron） 5.4 最小平方误差准则函数 5.5 多层感知的学习算法 误差反向传播算法,前面讲过，各种决策规则都导致似然比检验的形式：,5.1 引言,5.1 引言,若分布是正态的，其均值向量和协方差矩阵分别是mi 和 ki（i1, 2），则,定义,，则,5.1 引言,本质上在比较离均值的马氏距离。这是一个二次分类器。 展开h(x)并整理后有：,5.1 引言,式中：,5.1 引言,当两类的协方差矩阵相等时，即K=K1=K2， 决策规则变为：,5.1 引言,其中：,这是一个线

2、性分类器，是在正态分布、等协方差矩阵的情况下导出的。 这时的判别函数gk(x)的形式也是线性的，称为线性判别函数,5.1 引言,线性判别函数由一些参数所规定，所以由它们所确定的分类器又称为参数分类器。 参数分类器可以是线性（一次）的、二次的，或其它函数形式。 而近邻法是一种非参数分类器。,5.1 引言,在实际工作中，,所以发展了各种直接从样本中设计线性分类器的方法。这些方法本质上都是要确定线性判别函数中的参数（参数分类器中的参数估计）。,5.1 引言,线性分类器的设计过程,线性判别函数的一般形式为：,希望根据给出的已知类别的训练样本，确定参数w和w0.,5.1 引言,对分类器的性能提出要求,使

3、所确定的w和w0尽可能满足这些要求。,利用各种,表示,对应于准则函数的最优化（方法），求准则函数的极值问题。,5.1 引言,线性判别函数分类的错误率可能比贝叶斯错误率大，但它简单，容易实现，它是P.R.中最基本的方法之一，人们对它进行了大量的研究工作。,（分段线性可以逼近任意复杂的判别边界面）,5.1 引言,几种常用的准则函数：,5.1 引言,线性判别函数的基本概念,形式：,其中：,( w 称为权向量 ）,线性判别函数g(x)=0 定义了一个超平面H，称为决策面，即分界面，它把特征空间分成了三部分，,5.1 引言,对于两类问题，决策规则,正负半空间和超平面本身。,5.1 引言,假定x1和x2是

4、超平面H（分界面）上的任意两点，由于,即w是H的法向量，它和H上的任一向量正交。 判别函数g(x)是特征空间中的某点x到超平面g(x)=0的代数距离（有正负）的一种度量。,超平面的一些性质,5.1 引言,两类情况,5.1 引言,则,代入g(x) 中有：,5.1 引言,（点面距离）,点 (x0, y0, z0) 到平面 Ax+By+Cz+D=0的距离为：,5.1 引言,若x为原点，则,若w00，则原点在H的正侧； 若w00，则原点在H的负侧； 若w0=0，则H通过原点，具有齐次形式。,为原点到超平面的距离。,5.1 引言,广义线性判别函数,有时，有些判别函数不是线性的，但通过适当的变换可以转换为

5、线性判别函数。,例如：,二次判别函数,5.1 引言,若令：,，,则,，是y的线性函数。,5.1 引言,例：一维 ，ab，三个区域，两类,这样做的结果是增加了特征的维数。如上例由一维三维。,5.1 引言,另外,为了处理上的方便，线性判别函数,常写成齐次的形式,5.1 引言,其中,，,增广样本向量 广义权向量,5.1 引言,y和x相比，维数增加了一维,各次形式的线性判别函数（即增广的权及样本向量）以后常用。,第五章 线性判别函数（分类器，参数分类器）,5.1 引言 5.2 Fisher 线性判别 5.3 感知准则函数（Perception） 5.4 最小平方误差准则函数 5.5 多层感知的学习算法

6、 误差反向传播算法,对于线性判别函数（,5.2 Fisher 线性判别,），,的样本投影到一条直线上（设b (w) 的长度为1）。,相当于把n维特征空间,5.2 Fisher 线性判别,5.2 Fisher 线性判别,要找一个最好的投影方向b，使下面的准则函数达到最大值。,5.2 Fisher 线性判别,其中：,而,投影后的 投影前的,5.2 Fisher 线性判别,由求JF的极值问题，最后得到,和贝叶斯最小错误率决策的b只差一个常数，方向相同。 投影到一维后的两类分界点，可以用一维分类时的一些办法作。,当k1=k2=k时，,第五章 线性判别函数（分类器，参数分类器）,5.1 引言 5.2 F

7、isher 线性判别 5.3 感知准则函数（Perceptron） 5.4 最小平方误差准则函数 5.5 多层感知的学习算法 误差反向传播算法,5.3 感知准则函数（Perceptron）,一几个基本概念,1线性可分性,对一组样本y1, , yN（增广表示），假定来自两类，若存在一个权向量a，使得当,时，有,时，有,则称这组样本是线性可分的。,5.3 感知准则函数（Perceptron）,若样本是线性可分的，则总存在权向量a能把每个样本正确分类。即使得,2样本的规范化,，对,，对,对第二类的样本，若在yj前加一负号 yj=-yj，则 aTyi0 。,5.3 感知准则函数（Perceptron）

8、,即若令,，当,，当,这时问题就化为找一个a，使对所有的yn，有aTyn0。 上述的处理称为规范化。 称为规范化的增广样本。 以后为书写方便，仍用y来表示规范化的增广样本。（可根据上下文定 ）,5.3 感知准则函数（Perceptron）,3解向量和解区,在线性可分的情况下，满足aTyi0，i=1, 2, , N的a称为权向量，记为a*。 方程aTyi=0中的a和yi的作用是对偶的。 一个权向量a是权空间中的一个点。每个样本yi对a的可能位置都起到限制作用。即要满足aTyi0。对所有样本满足aTyi0的a即为一个解。,5.3 感知准则函数（Perceptron）,方程aTyi=0确定了权空间中

9、过原点的一个超平面Hi，它的法向量是yi。解应在Hi的正侧（因为要求aTyi0） 正半空间。 N个样本确定了权空间中的N个平面，每个平面把权空间分成了三部分，正侧、负侧和平面本身。,5.3 感知准则函数（Perception）,所以，如果解存在，则必定在N个超平面的正半空间的相交区。这个区域称为解区。区域中的每个向量都是解向量a*。,解和解区的两维示意图如下：,5.3 感知准则函数（Perceptron）,为使所得的a*对新的样本也能正确分类，a*最好位于解区的中央。 为提高泛化能力，使解更可靠，引入余量b0，寻找满足aTyi=b, i=1, 2, , N的解区。 显然，满足aTyi=b0的解

10、区位于原aTyi0的解区之内，且离原解区边界的距离为,5.3 感知准则函数（Perceptron）,4对解区的限制,。,5.3 感知准则函数（Perceptron）,。,二感知准则函数及其梯度下降算法,设有一组样本y1, , yN（规范的增广样本向量）。目的是求一a*，使得a*Tyi0, i=1, 2, , N。,5.3 感知准则函数（Perceptron）,。,构造一个准则函数，,Ye ：被a所错分的样本集合。 即aTy=0。,5.3 感知准则函数（Perceptron）,。,只有当Ye为空集时，不存在错分样本，才有,这一准则函数是Rosenblat在五十年代末提出来的，用来模拟人脑神经细胞

11、的模型，所以一般称为感知准则函数。,5.3 感知准则函数（Perceptron）,可以用梯度下降法求使Jp(a)最小的a*。,Ye 是被a所错分的样本集。,5.3 感知准则函数（Perceptron）,函数Jp(a)在某点ak的梯度Jp(ak)是一个向量，其方向是Jp(a)增长最快的方向，而负梯度是减小最快的方向。 沿梯度方向极大值 沿负梯度 极小值,：被a(k)错分的样本集。 即，当任意给定初始权向量a(1)后，a(k+1)等于a(k)加上,5.3 感知准则函数（Perceptron）,迭代公式：,5.3 感知准则函数（Perception）,可以证明，若样本线性可分，则经过有限次迭代修正后

12、，一定可以找到一个解向量，即算法收敛。 上述的算法是一种“批处理”方式。用a(k)把所有的样本分类一次，然后统计错分的样本，修改一次权。,5.3 感知准则函数（Perceptron）,也可采用“单样本修正”：顺序对各个样本进行分类，分错了就修正权。 单样本修正算法为：,5.3 感知准则函数（Perceptron）,假定令,，则,5.3 感知准则函数（Perceptron）,当,为固定值时，称为固定增量法。,随k变化时，称为可变增量法。,选的一次越过超平面时，即,当,当,称为绝对增量法。,5.3 感知准则函数（Perceptron）,例1线性可分与不可分的情况,下面证明在线性可分的情况下，单样本

13、固定增量法（,5.3 感知准则函数（Perceptron）,收敛，即经过有限次修正后，一定可以找到解向量a*。,）一定,5.3 感知准则函数（Perceptron）,证明：假定固定的增量系数,这并不失一般性，因为改变,仅仅是改变了坐标系的比例。坐标系比例的改变并不影响数据结构和线性分类器。,，,5.3 感知准则函数（Perceptron）,这时的迭代规则为,yk是被a(k)错分的，即,由于假定两类是线性可分的，则一定存在一个as，使得astyi0, i=1, , N.,5.3 感知准则函数（Perceptron）,令,可以改变a的比例，使得,改变a的比例并不影响（并不改变）决策规则。,( *

14、),( * ),常数,5.3 感知准则函数（Perceptron）,a(k)和as间的距离平方为（记a(k)ak, a(k+1)ak+1）,而,5.3 感知准则函数（Perceptron）,，和 ( * ) 及 ( * ) 式，,上式说明，当利用一个yk时（被错分的样本），|as-ak|2就减少了一定的量。因此，经过有限次的利用错分样本后，ak应收敛于as。 绝对增量法的证明，可以利用上面固定增量法的结果。P373,对两类问题线性分类器的设计可以推广到多维。 对C类问题，可以建立C个线性判别函数aiTy, i=1, , C. 判决规则为：,5.3 感知准则函数（Perceptron）,。,三多

15、类问题的线性分类器,当所有样本,( i=1, , C ) 都满足上式时，,若,称这C类是线性可分的。,5.3 感知准则函数（Perceptron）,* 求多类问题的ai (i=1, , C)的算法如下：,， 则,若对,2. 若,，对,，则,且,这个多类问题的迭代算法的证明，可以通过把上述算法转换为两类问题，然后利用上面的结果进行。,有：,第五章 线性判别函数（分类器，参数分类器）,5.1 引言 5.2 Fisher 线性判别 5.3 感知准则函数（Perceptron） 5.4 最小平方误差准则函数 5.5 多层感知的学习算法 误差反向传播算法,5.4 最小平方误差准则函数,一引言,上节的感知

16、准则函数只适合于线性可分的情况。对线性不可分情况，算法不收敛。但在实际问题中， 1有许多问题不是线性可分的 2事先不知道是否线性可分,5.4 最小平方误差准则函数,因此我们希望找到一些算法既适合线性可分的情况，又适合线性不可分的情况。 对线性可分的问题，算法求得的解能把两类正确分开； 而对线性不可分的问题，算法也能找到在一定准则下的最优解。,5.4 最小平方误差准则函数,对于规范化的增广样本向量，yi=1, , N，要找a，使得aTyi0, i=1, , N。这是求N个不等式组解的问题。 若线性可分-线性不等式组是一致的，有解-能求出a，使aTyi0, i=1, , N； 若线性不可分-线性不

17、等式组不一致，无解-求一个a，比如说使正确分类的样本数最多，使成立的不等式的个数最多。,5.4 最小平方误差准则函数,这样，线性分类器的设计就转化为解线性不等式组的问题。 这时的准则函数是一类最少错分样本数准则。（略） 下面要介绍的方法是把线性分类器的设计转换为解线性方程组。,5.4 最小平方误差准则函数,二最小平方误差准则函数,把aTyi0, i=1, , N写成联立方程的形式 Ya=b,求使 极小的a作为问题的解。这是矛盾方程组的最小二乘解。 称为最小平方误差准则函数（MSE）。,和平方误差准则函数,大于未知数的个数，所以上述方程组一般为矛盾方程组，没有准确解。但可以定义一个误差向量,5.

18、4 最小平方误差准则函数,由于通常,，即样本数（方程的个数）,（向量）,对 求梯度,5.4 最小平方误差准则函数,下面推导在MSE下的解。,令,，有,而,是,的矩阵，一般是非奇异的。,( * ),5.4 最小平方误差准则函数,式中,是,y的伪逆。,在a*的解( * )式中，a*显然依赖于b。如何选择b呢？,当b取某些特殊值时，MSE（最小平方误差）解有较好的性质。,的矩阵，称为,( * ),5.4 最小平方误差准则函数,当取,MSE解a*等价于Fisher解。,时，,时，MSE的解a*在最小均方误差意,5.4 最小平方误差准则函数,当取,式中,时，,当,义逼近贝叶斯判别函数：,最小。,即使MSE最小的解使,5.4 最小平方误差准则函数,还可以由实际问题确定bi，aTyi=bi,5.4 最小平方误差准则函数,三MSE准则函数的梯度下降法,