模式识别线性判别函数

1、模式识别线性判别函数第1页，共82页，2022年，5月20日，6点30分，星期四前面讲过，各种决策规则都导致似然比检验的形式：5.1 引言第2页，共82页，2022年，5月20日，6点30分，星期四5.1 引言 若分布是正态的，其均值向量和协方差矩阵分别是mi 和 ki（i1, 2），则定义 ，则 第3页，共82页，2022年，5月20日，6点30分，星期四5.1 引言 本质上在比较离均值的马氏距离。这是一个二次分类器。展开h(x)并整理后有：第4页，共82页，2022年，5月20日，6点30分，星期四5.1 引言式中： 第5页，共82页，2022年，5月20日，6点30分，星期四5.1 引言

2、 当两类的协方差矩阵相等时，即K=K1=K2， 决策规则变为：第6页，共82页，2022年，5月20日，6点30分，星期四5.1 引言其中： 这是一个线性分类器，是在正态分布、等协方差矩阵的情况下导出的。 这时的判别函数gk(x)的形式也是线性的，称为线性判别函数 第7页，共82页，2022年，5月20日，6点30分，星期四5.1 引言 线性判别函数由一些参数所规定，所以由它们所确定的分类器又称为参数分类器。 参数分类器可以是线性（一次）的、二次的，或其它函数形式。 而近邻法是一种非参数分类器。第8页，共82页，2022年，5月20日，6点30分，星期四5.1 引言在实际工作中， 所以发展了各

3、种直接从样本中设计线性分类器的方法。这些方法本质上都是要确定线性判别函数中的参数（参数分类器中的参数估计）。 第9页，共82页，2022年，5月20日，6点30分，星期四5.1 引言线性分类器的设计过程线性判别函数的一般形式为： 希望根据给出的已知类别的训练样本，确定参数w和w0.第10页，共82页，2022年，5月20日，6点30分，星期四5.1 引言对分类器的性能提出要求使所确定的w和w0尽可能满足这些要求。 利用各种 表示对应于准则函数的最优化（方法），求准则函数的极值问题。第11页，共82页，2022年，5月20日，6点30分，星期四5.1 引言 线性判别函数分类的错误率可能比贝叶斯错

4、误率大，但它简单，容易实现，它是P.R.中最基本的方法之一，人们对它进行了大量的研究工作。（分段线性可以逼近任意复杂的判别边界面）第12页，共82页，2022年，5月20日，6点30分，星期四5.1 引言几种常用的准则函数：第13页，共82页，2022年，5月20日，6点30分，星期四5.1 引言线性判别函数的基本概念形式： 其中：( w 称为权向量 ）第14页，共82页，2022年，5月20日，6点30分，星期四 线性判别函数g(x)=0 定义了一个超平面H，称为决策面，即分界面，它把特征空间分成了三部分，5.1 引言 对于两类问题，决策规则 正负半空间和超平面本身。第15页，共82页，20

5、22年，5月20日，6点30分，星期四5.1 引言 假定x1和x2是超平面H（分界面）上的任意两点，由于 即w是H的法向量，它和H上的任一向量正交。 判别函数g(x)是特征空间中的某点x到超平面g(x)=0的代数距离（有正负）的一种度量。超平面的一些性质第16页，共82页，2022年，5月20日，6点30分，星期四5.1 引言 第17页，共82页，2022年，5月20日，6点30分，星期四 两类情况第18页，共82页，2022年，5月20日，6点30分，星期四5.1 引言 则代入g(x) 中有：第19页，共82页，2022年，5月20日，6点30分，星期四5.1 引言 （点面距离）点 (x0,

6、 y0, z0) 到平面 Ax+By+Cz+D=0的距离为：第20页，共82页，2022年，5月20日，6点30分，星期四5.1 引言若x为原点，则若w00，则原点在H的正侧；若w0b，三个区域，两类 这样做的结果是增加了特征的维数。如上例由一维三维。第24页，共82页，2022年，5月20日，6点30分，星期四5.1 引言另外,为了处理上的方便，线性判别函数常写成齐次的形式第25页，共82页，2022年，5月20日，6点30分，星期四5.1 引言其中 ，增广样本向量 广义权向量第26页，共82页，2022年，5月20日，6点30分，星期四5.1 引言y和x相比，维数增加了一维 各次形式的线性

7、判别函数（即增广的权及样本向量）以后常用。 第27页，共82页，2022年，5月20日，6点30分，星期四第五章 线性判别函数（分类器，参数分类器）5.1 引言5.2 Fisher 线性判别5.3 感知准则函数（Perception）5.4 最小平方误差准则函数5.5 多层感知的学习算法 误差反向传播算法 第28页，共82页，2022年，5月20日，6点30分，星期四对于线性判别函数（5.2 Fisher 线性判别），的样本投影到一条直线上（设b (w) 的长度为1）。 相当于把n维特征空间第29页，共82页，2022年，5月20日，6点30分，星期四5.2 Fisher 线性判别第30页，共

8、82页，2022年，5月20日，6点30分，星期四5.2 Fisher 线性判别 要找一个最好的投影方向b，使下面的准则函数达到最大值。第31页，共82页，2022年，5月20日，6点30分，星期四5.2 Fisher 线性判别其中： 而 投影后的 投影前的 第32页，共82页，2022年，5月20日，6点30分，星期四5.2 Fisher 线性判别由求JF的极值问题，最后得到 和贝叶斯最小错误率决策的b只差一个常数，方向相同。 投影到一维后的两类分界点，可以用一维分类时的一些办法作。 当k1=k2=k时，第33页，共82页，2022年，5月20日，6点30分，星期四第五章 线性判别函数（分类

9、器，参数分类器）5.1 引言5.2 Fisher 线性判别5.3 感知准则函数（Perceptron）5.4 最小平方误差准则函数5.5 多层感知的学习算法 误差反向传播算法 第34页，共82页，2022年，5月20日，6点30分，星期四5.3 感知准则函数（Perceptron）一几个基本概念1线性可分性 对一组样本y1, , yN（增广表示），假定来自两类，若存在一个权向量a，使得当时，有 时，有则称这组样本是线性可分的。第35页，共82页，2022年，5月20日，6点30分，星期四5.3 感知准则函数（Perceptron） 若样本是线性可分的，则总存在权向量a能把每个样本正确分类。即使

10、得2样本的规范化，对，对 对第二类的样本，若在yj前加一负号 yj=-yj，则 aTyi0 。第36页，共82页，2022年，5月20日，6点30分，星期四5.3 感知准则函数（Perceptron）即若令 ，当 ，当 这时问题就化为找一个a，使对所有的yn，有aTyn0。 上述的处理称为规范化。 称为规范化的增广样本。 以后为书写方便，仍用y来表示规范化的增广样本。（可根据上下文定 ）第37页，共82页，2022年，5月20日，6点30分，星期四5.3 感知准则函数（Perceptron）3解向量和解区 在线性可分的情况下，满足aTyi0，i=1, 2, , N的a称为权向量，记为a*。 方

11、程aTyi=0中的a和yi的作用是对偶的。 一个权向量a是权空间中的一个点。每个样本yi对a的可能位置都起到限制作用。即要满足aTyi0。对所有样本满足aTyi0的a即为一个解。第38页，共82页，2022年，5月20日，6点30分，星期四5.3 感知准则函数（Perceptron） 方程aTyi=0确定了权空间中过原点的一个超平面Hi，它的法向量是yi。解应在Hi的正侧（因为要求aTyi0） 正半空间。 N个样本确定了权空间中的N个平面，每个平面把权空间分成了三部分，正侧、负侧和平面本身。第39页，共82页，2022年，5月20日，6点30分，星期四5.3 感知准则函数（Perception

12、） 所以，如果解存在，则必定在N个超平面的正半空间的相交区。这个区域称为解区。区域中的每个向量都是解向量a*。 解和解区的两维示意图如下： 第40页，共82页，2022年，5月20日，6点30分，星期四5.3 感知准则函数（Perceptron）第41页，共82页，2022年，5月20日，6点30分，星期四 为使所得的a*对新的样本也能正确分类，a*最好位于解区的中央。 为提高泛化能力，使解更可靠，引入余量b0，寻找满足aTyi=b, i=1, 2, , N的解区。 显然，满足aTyi=b0的解区位于原aTyi0的解区之内，且离原解区边界的距离为5.3 感知准则函数（Perceptron）4对

13、解区的限制 。 第42页，共82页，2022年，5月20日，6点30分，星期四5.3 感知准则函数（Perceptron）。 二感知准则函数及其梯度下降算法 设有一组样本y1, , yN（规范的增广样本向量）。目的是求一a*，使得a*Tyi0, i=1, 2, , N。第43页，共82页，2022年，5月20日，6点30分，星期四5.3 感知准则函数（Perceptron）。 构造一个准则函数， Ye ：被a所错分的样本集合。 即aTy=0。 第44页，共82页，2022年，5月20日，6点30分，星期四5.3 感知准则函数（Perceptron）。 只有当Ye为空集时，不存在错分样本，才有

14、这一准则函数是Rosenblat在五十年代末提出来的，用来模拟人脑神经细胞的模型，所以一般称为感知准则函数。 第45页，共82页，2022年，5月20日，6点30分，星期四5.3 感知准则函数（Perceptron）可以用梯度下降法求使Jp(a)最小的a*。Ye 是被a所错分的样本集。 第46页，共82页，2022年，5月20日，6点30分，星期四5.3 感知准则函数（Perceptron） 函数Jp(a)在某点ak的梯度Jp(ak)是一个向量，其方向是Jp(a)增长最快的方向，而负梯度是减小最快的方向。 沿梯度方向极大值 沿负梯度 极小值第47页，共82页，2022年，5月20日，6点30分

15、，星期四 ：被a(k)错分的样本集。即，当任意给定初始权向量a(1)后，a(k+1)等于a(k)加上5.3 感知准则函数（Perceptron）迭代公式： 第48页，共82页，2022年，5月20日，6点30分，星期四5.3 感知准则函数（Perception） 可以证明，若样本线性可分，则经过有限次迭代修正后，一定可以找到一个解向量，即算法收敛。 上述的算法是一种“批处理”方式。用a(k)把所有的样本分类一次，然后统计错分的样本，修改一次权。 第49页，共82页，2022年，5月20日，6点30分，星期四5.3 感知准则函数（Perceptron） 也可采用“单样本修正”：顺序对各个样本进行

16、分类，分错了就修正权。 单样本修正算法为： 第50页，共82页，2022年，5月20日，6点30分，星期四5.3 感知准则函数（Perceptron） 假定令，则 第51页，共82页，2022年，5月20日，6点30分，星期四5.3 感知准则函数（Perceptron） 当为固定值时，称为固定增量法。随k变化时，称为可变增量法。选的一次越过超平面时，即当当称为绝对增量法。第52页，共82页，2022年，5月20日，6点30分，星期四5.3 感知准则函数（Perceptron）例1线性可分与不可分的情况第53页，共82页，2022年，5月20日，6点30分，星期四 下面证明在线性可分的情况下，单

17、样本固定增量法（5.3 感知准则函数（Perceptron）收敛，即经过有限次修正后，一定可以找到解向量a*。 ）一定第54页，共82页，2022年，5月20日，6点30分，星期四5.3 感知准则函数（Perceptron）证明：假定固定的增量系数这并不失一般性，因为改变仅仅是改变了坐标系的比例。坐标系比例的改变并不影响数据结构和线性分类器。 ，第55页，共82页，2022年，5月20日，6点30分，星期四5.3 感知准则函数（Perceptron）这时的迭代规则为yk是被a(k)错分的，即由于假定两类是线性可分的，则一定存在一个as，使得astyi0, i=1, , N. 第56页，共82页

18、，2022年，5月20日，6点30分，星期四5.3 感知准则函数（Perceptron）令 可以改变a的比例，使得改变a的比例并不影响（并不改变）决策规则。 ( * ) ( * )常数第57页，共82页，2022年，5月20日，6点30分，星期四5.3 感知准则函数（Perceptron）a(k)和as间的距离平方为（记a(k)ak, a(k+1)ak+1）而 第58页，共82页，2022年，5月20日，6点30分，星期四5.3 感知准则函数（Perceptron），和 ( * ) 及 ( * ) 式， 上式说明，当利用一个yk时（被错分的样本），|as-ak|2就减少了一定的量。因此，经过有

19、限次的利用错分样本后，ak应收敛于as。 绝对增量法的证明，可以利用上面固定增量法的结果。P373 第59页，共82页，2022年，5月20日，6点30分，星期四对两类问题线性分类器的设计可以推广到多维。对C类问题，可以建立C个线性判别函数aiTy, i=1, , C. 判决规则为：5.3 感知准则函数（Perceptron）。 三多类问题的线性分类器当所有样本( i=1, , C ) 都满足上式时，若称这C类是线性可分的。 第60页，共82页，2022年，5月20日，6点30分，星期四5.3 感知准则函数（Perceptron）* 求多类问题的ai (i=1, , C)的算法如下：， 则 若

20、对 2. 若 ，对，则且 这个多类问题的迭代算法的证明，可以通过把上述算法转换为两类问题，然后利用上面的结果进行。 有：第61页，共82页，2022年，5月20日，6点30分，星期四第五章 线性判别函数（分类器，参数分类器）5.1 引言5.2 Fisher 线性判别5.3 感知准则函数（Perceptron）5.4 最小平方误差准则函数5.5 多层感知的学习算法 误差反向传播算法 第62页，共82页，2022年，5月20日，6点30分，星期四5.4 最小平方误差准则函数一引言 上节的感知准则函数只适合于线性可分的情况。对线性不可分情况，算法不收敛。但在实际问题中， 1有许多问题不是线性可分的

21、2事先不知道是否线性可分 第63页，共82页，2022年，5月20日，6点30分，星期四5.4 最小平方误差准则函数 因此我们希望找到一些算法既适合线性可分的情况，又适合线性不可分的情况。 对线性可分的问题，算法求得的解能把两类正确分开； 而对线性不可分的问题，算法也能找到在一定准则下的最优解。 第64页，共82页，2022年，5月20日，6点30分，星期四5.4 最小平方误差准则函数 对于规范化的增广样本向量，yi=1, , N，要找a，使得aTyi0, i=1, , N。这是求N个不等式组解的问题。 若线性可分-线性不等式组是一致的，有解-能求出a，使aTyi0, i=1, , N； 若线

22、性不可分-线性不等式组不一致，无解-求一个a，比如说使正确分类的样本数最多，使成立的不等式的个数最多。第65页，共82页，2022年，5月20日，6点30分，星期四5.4 最小平方误差准则函数 这样，线性分类器的设计就转化为解线性不等式组的问题。 这时的准则函数是一类最少错分样本数准则。（略） 下面要介绍的方法是把线性分类器的设计转换为解线性方程组。第66页，共82页，2022年，5月20日，6点30分，星期四5.4 最小平方误差准则函数二最小平方误差准则函数把aTyi0, i=1, , N写成联立方程的形式 Ya=b 第67页，共82页，2022年，5月20日，6点30分，星期四 求使 极小

23、的a作为问题的解。这是矛盾方程组的最小二乘解。 称为最小平方误差准则函数（MSE）。 和平方误差准则函数大于未知数的个数，所以上述方程组一般为矛盾方程组，没有准确解。但可以定义一个误差向量 5.4 最小平方误差准则函数 由于通常，即样本数（方程的个数）（向量）第68页，共82页，2022年，5月20日，6点30分，星期四对 求梯度5.4 最小平方误差准则函数下面推导在MSE下的解。令，有 而是的矩阵，一般是非奇异的。( * ) 第69页，共82页，2022年，5月20日，6点30分，星期四5.4 最小平方误差准则函数式中是y的伪逆。 在a*的解( * )式中，a*显然依赖于b。如何选择b呢？

24、当b取某些特殊值时，MSE（最小平方误差）解有较好的性质。的矩阵，称为( * ) 第70页，共82页，2022年，5月20日，6点30分，星期四5.4 最小平方误差准则函数 当取MSE解a*等价于Fisher解。时，第71页，共82页，2022年，5月20日，6点30分，星期四时，MSE的解a*在最小均方误差意5.4 最小平方误差准则函数 当取式中时，当义逼近贝叶斯判别函数：最小。即使MSE最小的解使第72页，共82页，2022年，5月20日，6点30分，星期四5.4 最小平方误差准则函数 还可以由实际问题确定bi，aTyi=bi第73页，共82页，2022年，5月20日，6点30分，星期四5.4 最小平方误差准则函数三MSE准则函数的梯度下降法 在伪逆解中，需要计算Y+。 这时要求 存在 的计算量大，而且可能引入更大的计算误差。 第74页，共82页，2022年，5月2