模式识别线性判别函数

《模式识别线性判别函数》由会员分享，可在线阅读，更多相关《模式识别线性判别函数（82页珍藏版）》请在金锄头文库上搜索。

1、第五章 线性判别函数 （分类器，参数分类器）5.1 引言 5.2 Fisher 线性判别 5.3 感知准则函数（Perceptron） 5.4 最小平方误差准则函数 5.5 多层感知的学习算法误差反向传播算法 1.前面讲过，各种决策规则都导致似 然比检验的形式：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 引言2.线性分类器的设计过程线性判别函数的一般形式为： 希望根据给出的已知类别的训练样 本，确定参数w和w0.5.1 引言对分类器的性能 提出要求使所确定的w

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

4、 任意两点，由于即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的正侧； 若w0b，三个区域，两类这样做的结果是增加了特征的维数。如上例 由一维三维。5.1 引言另外,为了处理上的方便，线性判别函数常写成齐次的形式5.1 引言其中 ，增广样样本向量 广义权义权 向量5.1 引言y和x相比，维数增加

5、了一维各次形式的线性判别函数（即增广的权及样本 向量）以后常用。 第五章 线性判别函数 （分类器，参数分类器）5.1 引言 5.2 Fisher 线性判别 5.3 感知准则函数（Perception） 5.4 最小平方误差准则函数 5.5 多层感知的学习算法误差反向传播算法 对于线性判别函数（5.2 Fisher 线性判别），的样本投影到一条直线上（设b (w) 的长度 为1）。 相当于把n维特征空间5.2 Fisher 线性判别5.2 Fisher 线性判别要找一个最好的投影方向b，使下面的准则 函数达到最大值。5.2 Fisher 线性判别其中： 而 投影后的 投影前的 5.2 Fishe

6、r 线性判别由求JF的极值问题，最后得到和贝叶斯最小错误率决策的b只差一个常数，方向 相同。投影到一维后的两类分界点，可以用一维分类时 的一些办法作。 当k1=k2=k时，第五章 线性判别函数 （分类器，参数分类器）5.1 引言 5.2 Fisher 线性判别 5.3 感知准则函数（Perceptron）5.4 最小平方误差准则函数 5.5 多层感知的学习算法误差反向传播算法 5.3 感知准则函数（Perceptron）一几个基本概念1线性可分性 对一组样本y1, , yN（增广表示），假 定来自两类，若存在一个权向量a，使得当时时，有时时，有则称这组样 本是线性可分的。5.3 感知准则函数（

7、Perceptron）若样本是线性可分的，则总存在权 向量a能把每个样本正确分类。即使得2样本的规范化，对，对对第二类的样本，若在yj前加一负 号 yj=-yj，则 aTyi0 。5.3 感知准则函数（Perceptron）即若令 ，当 ，当 这时问题就化为找一个a，使对所有的yn，有aTyn0 。上述的处理称为规范化。 称为规范化的增广样本 。以后为书写方便，仍用y来表示规范化的增广样本 。（可根据上下文定 ）5.3 感知准则函数（Perceptron）3解向量和解区 在线性可分的情况下，满足aTyi0，i=1, 2, , N的a称为权向量，记为a*。方程aTyi=0中的a和yi的作用是对偶

8、的。一个权向量a是权空间中的一个点。每个 样本yi对a的可能位置都起到限制作用。即要满 足aTyi0。对所有样本满足aTyi0的a即为一个 解。5.3 感知准则函数（Perceptron）方程aTyi=0确定了权空间中过原点的一个超 平面Hi，它的法向量是yi。解应在Hi的正侧（因 为要求aTyi0） 正半空间。N个样本确定了权空间中的N个平面，每个 平面把权空间分成了三部分，正侧、负侧和平面 本身。5.3 感知准则函数（Perception）所以，如果解存在，则必定在N个超 平面的正半空间的相交区。这个区域称为 解区。区域中的每个向量都是解向量a*。 解和解区的两维示意图如下： 5.3 感知

9、准则函数（Perceptron）为使所得的a*对新的样本也能正确分类， a*最好位于解区的中央。为提高泛化能力，使解更可靠，引入余量 b0，寻找满足aTyi=b, i=1, 2, , N的解区。显然，满足aTyi=b0的解区位于原aTyi0的 解区之内，且离原解区边界的距离为5.3 感知准则函数（Perceptron）4对解区的限制 。 5.3 感知准则函数（Perceptron）。 二感知准则函数及其梯度下降算法设有一组样本y1, , yN（规范的 增广样本向量）。目的是求一a*，使 得a*Tyi0, i=1, 2, , N。5.3 感知准则函数（Perceptron）。 构造一个准则函数，

10、 Ye ：被a所错分的样本集合。即aTy=0。 5.3 感知准则函数（Perceptron）。 只有当Ye为空集时，不存在错分样本， 才有 这一准则函数是Rosenblat在五十年代 末提出来的，用来模拟人脑神经细胞的模 型，所以一般称为感知准则函数。 5.3 感知准则函数（Perceptron）可以用梯度下降法求使Jp(a)最小的a*。Ye 是被a所错分的样本集。 5.3 感知准则函数（Perceptron）函数Jp(a)在某点ak的梯度Jp(ak)是一 个向量，其方向是Jp(a)增长最快的方向，而负梯度是减小最快的方向。 沿梯度方向极大值沿负梯度 极小值：被a(k)错分的样本集。即，当任意

11、给定初始权向量a(1)后， a(k+1)等于a(k)加上5.3 感知准则函数（Perceptron）迭代公式： 5.3 感知准则函数（Perception）可以证明，若样本线性可分，则经过有 限次迭代修正后，一定可以找到一个解向量 ，即算法收敛。上述的算法是一种“批处理”方式。用 a(k)把所有的样本分类一次，然后统计错分 的样本，修改一次权。 5.3 感知准则函数（Perceptron）也可采用“单样 本修正”：顺序对各 个样本进行分类，分错了就修正权。单样 本修正算法为：5.3 感知准则函数（Perceptron）假定令，则5.3 感知准则函数（Perceptron）当为固定值时 ，称为固

12、定增量法。随k变化时，称为可变增量法。 选的一次越过超平面时，即当当称为绝对增量法。5.3 感知准则函数（Perceptron）例1线性可分与不可分的情况下面证明在线性可分的情况下， 单样 本固定增量法（5.3 感知准则函数（Perceptron）收敛，即经过 有限次修正后，一 定可以找到解向量a*。 ）一定5.3 感知准则函数（Perceptron）证明：假定固定的增量系数这并不失一般性，因为改变仅仅是改变了坐标系的比例。坐 标系比例的改变并不影响数据结 构和线性分类器。 ，5.3 感知准则函数（Perceptron）这时 的迭代规则为yk是被a(k)错分的，即由于假定两类是线性可分的，则一

13、定 存在一个as，使得astyi0, i=1, , N. 5.3 感知准则函数（Perceptron）令 可以改变a的比例，使得改变a的比例并不影响（并不改变） 决策规则。 ( * )( * )常数5.3 感知准则函数（Perceptron）a(k)和as间间的距离平方为为（记记a(k)ak, a(k+1)ak+1）而 5.3 感知准则函数（Perceptron），和 ( * ) 及 ( * ) 式，上式说明，当利用一个yk时（被错分的样本）， |as-ak|2就减少了一定的量。因此，经过有限次的利用 错分样本后，ak应收敛于as。绝对增量法的证明，可以利用上面固定增量法的 结果。P373 对

14、两类问题线 性分类器的设计可以推广到多维。 对C类问题 ，可以建立C个线性判别函数aiTy, i=1, , C. 判决规则为：5.3 感知准则函数（Perceptron）。 三多类问题的线性分类器当所有样本( i=1, , C ) 都满足上式时，若称这C类是线性可分的。 5.3 感知准则函数（Perceptron）* 求多类问题的ai (i=1, , C)的算法如下：， 则1. 若对 2. 若 ，对对，则且 这个多类问题的迭代算法的证明，可以通过把上述算 法转换为两类问题，然后利用上面的结果进行。 有：第五章 线性判别函数 （分类器，参数分类器）5.1 引言 5.2 Fisher 线性判别 5

15、.3 感知准则函数（Perceptron）5.4 最小平方误差准则函数 5.5 多层感知的学习算法误差反向传播算法 5.4 最小平方误差准则函数一引言 上节的感知准则函数只适合于线性可 分的情况。对线性不可分情况，算法不收 敛。但在实际问题中，1有许多问题不是线性可分的2事先不知道是否线性可分 5.4 最小平方误差准则函数因此我们希望找到一些算法既适合线性 可分的情况，又适合线性不可分的情况。对线性可分的问题，算法求得的解能把 两类正确分开；而对线性不可分的问题，算法也能找到 在一定准则下的最优解。 5.4 最小平方误差准则函数对于规范化的增广样本向量，yi=1, , N，要 找a，使得aTy

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