模式识别ppt课件第四章线性判别函数.ppt

第四章 线性判别函数,Bayesian分类器设计方法，已知类条件概率密度 p(x|i) 参数表达式先验概率 P(i) 利用样本估计 p(x| i) 的未知参数用贝叶斯规则将其转换成后验概率 P(i|x) ，并根据后验概率的大小进行分类决策。,解决实际问题方法,在实际中存在问题样本特征空间的类条件概率密度形式常常很难确定利用 Parzen 窗等非参数方法恢复分布往往需要大量样本，而且随着特征空间维数的增加所需样本数急剧增加。因此，在解决实际问题时，往往是利用样本集直接设计分类器，而不恢复类条件概率密度。即采用判别函数，首先给定某个判别函数类，然后利用样本集确定出判别函数中的未知参数。,线性判别函数,线性判别函数法是一类较为简单的判别函数。是统计模式识别的基本方法之一。它首先假定判别函数 g(x) 是 x 的线性函数，即 g(x)=wTx+ w0 ，对于 c 类问题，可以定义 c 个判别函数， gi(x)=wiTx+ wi0 ， i=1,2 ， c 。用样本去估计各 wi 和 wi0 ，并把未知样本 x 归到具有最大判别函数值的类别中去。关键是如何利用样本集求得 wi 和 wi0 。,训练和学习,“训练”和“学习” 在待识别的模式中，挑选一批有代表性的样本，经过人工判读，成为已知分类的样本，把这批样本逐个输入到计算机中的“训练”程序或算法中，通过一次次的迭代，最后得到正确的线性判别函数。这样的迭代过程称之为训练过程，所构成的分类器称为有人监督或有教师的分类器。,4.1.1 线性判别函数的基本概念,在正态分布的Bayesian判别中，已经遇到过在两类情况下判别函数为线性的情况。假设有1 和2 两类模式，在二维模式特征空间可用一直线把这两类模式划分开，如图 4.1 所示。,划分直线的方程,参数,坐标变量,4.1.1 线性判别函数的基本概念,判别规则,若给定一个未知类别的模式x当g(x)0 时，则决策 x 属于1 ；当 g(x)0 ，则决策 x 属于2；若x处于划分边界上即g(x)=0，则x的类别不可确定，则可将x任意分到某一类或拒绝， g(x)=0 为不可确定的条件。这一概念可以推广到有限维欧氏空间中的非线性边界的更一般情况。,4.1.1 线性判别函数的基本概念,g(x)=wdxd+ wd-1xd-1+ +w1x1+w0 =wTx+w0 (4-1),一般的线性判别函数形式为：,特征向量 (样本向量),权向量,阈值权(常数),4.1.1 线性判别函数的基本概念,简单线性分类器：,4.1.1 线性判别函数的基本概念,对于两类问题的线性分类器决策规则：,令 g(x)=g1(x) g2(x)如果g(x) 0 ，则决策 x 1g(x) 0 ，则决策 x 2 (4-2)g(x) 0 ，则可将 x 任意分到某一类或拒绝,4.1.1 线性判别函数的基本概念,对于两类问题的线性分类器决策规则：,方程 g(x)=0 定义了一个决策面，把归类于1 类的点和归类于2 的点分割开。假设 x1 和 x2 都在决策面 H 上，则有 wTx1+ w0= wTx2+w0 (4-3)或 wT(x1 x2)=0 (4-4)表明， w 和超平面 H 上任一向量正交，即 w 是 H 的法向量。,4.1.1 线性判别函数的基本概念,一般地，一个超平面 H 把特征空间分成两个半空间，即对1 类的决策域 R1 和对2 类的决策域 R2 。因为当 x 在 R1 中时，g(x)0，所以决策面的法向量是指向 R1 的。因此，有时称 R1 中的任何 x 在 H 的正侧，相应地，称 R2 中的任何 x 在 H 的负侧。,4.1.1 线性判别函数的基本概念,判别函数 g(x) 是特征空间中某点 x 到超平面距离的一种代数量度。,若把 x 表示成,式中 xp ：是 x 在 H 上的投影向量； r ：是 x 到 H 的垂直距离；,：是w方向上的单位向量。,4.1.1 线性判别函数的基本概念,若 x 为原点，则 g(x)=w0 (4-7)将 (4-7) 代入 (4-6) ，就得到从原点到超平面 H 的距离,(4-6),判别函数 g(x) 是特征空间中某点 x 到超平面距离的一种代数量度。,4.1.1 线性判别函数的基本概念,如果 w00 ，则原点在 H 的正侧；若 w00 ，则原点在 H 的负侧。若w0=0 ，则 g(x) 具有齐次形式 wTx ，说明超平面 H 通过原点。,判别函数 g(x) 是特征空间中某点 x 到超平面距离的一种代数量度。,4.1.1 线性判别函数的基本概念,图 4.2 对这些结果作了几何解释。,4.1.1 线性判别函数的基本概念,结论,利用线性判别函数进行决策，就是用一个超平面把特征空间分割成两个决策区域。超平面的方向由权向量 w 确定，它的位置由阈值权 w0 确定。判别函数 g(x) 正比于 x 点到超平面的代数距离（带正负号）当 x 在 H 正侧时， g(x) 0 ，在负侧时， g(x) 0 。,4.1.1 线性判别函数的基本概念,4.1.2 广义线性判别函数,如图 4.3 所示的二类问题。设有一维样本空间 X ，所希望的划分是：如果 xa ，则 x 属于1 类；如果 b xa ，则 x 属于2 类。,b,a,1,1,2,4.1.2 广义线性判别函数,显然，没有任何一个线性判别函数能解决上述划分问题。这说明线性判别函数虽然简单，但局限性较大，不适用于非凸决策区域和多连通区域的划分问题。,从图 4.3 中可以看出，如果建立二次判别函数 g(x)=(x-a)(x-b) (4-9)则可以很好地解决上述分类问题，决策规则是： g(x)0 ，则决策 x1g(x)0 ，则决策 x2二次判别函数可写成如下一般形式g(x)=c0+c1x+ c2x2(4-10)如果适当选择 x y 的映射，则可把二次判别函数化为 y 的线性函数,4.1.2 广义线性判别函数,式中,称为广义判别函数，a叫做广义权向量。,一般地，对于任意高次判别函数 g(x)(这时的 g(x) 可看作对任意判别函数作级数展开，然后取其截尾部分的逼近)，都可以通过适当的变换，化为广义线性判别函数来处理。,4.1.2 广义线性判别函数,存在问题,经过变换后，维数大大增加了，这将使问题很快陷入所谓“维数灾难”。在统计学习理论中，对广义线性分类器进行研究，克服了“维数灾难”问题，进而发展出了最新的模式识别方法支持向量机，成为解决有限样本情况下非线性分类问题的有效手段。,4.1.2 广义线性判别函数,把 (4-1) 式定义的线性判别函数写成下面的形式,(4-12),增广特征向量Augmented feature vector,增广权向量(广义权向量)Augmented weight vector,4.1.2 广义线性判别函数,结论,y 与 x 相比，虽然增加了一维，但保持了样本间的欧氏距离不变，变换后的样本向量仍然全部位于 d 维子空间，即原 X 空间中，方程,(4-13),在Y空间确定了一个通过原点的超平面 。,它对 d 维子空间的划分与原决策面 wTx+ w0=0 对原 X 空间的划分完全相同。,4.1.2 广义线性判别函数,例子,这种方法的优缺点可通过例子来说明。考虑二次判别函数,得到三维向量y,从x到y的映射如图所示。,4.1.2 广义线性判别函数,例子,4.1.2 广义线性判别函数,数据仍保持固有的一维，因为改变x将导致y沿着一个三维曲线运动。,如果x服从某一个概率分布时，得到的密度函数是退化的，即曲线之外是0，在曲线上是无穷大，这是从低维空间到高维空间映射的普遍问题。,例子,4.1.2 广义线性判别函数,图中映射y=(1,x,x2)T把一条直线映射为三维空间中的一条抛物线。由于两类问题，在三维空间中，一个平面就是一个分隔面。因此，由图可见，这产生了原始一维x空间的不连通性,例子,g(x)=1+x+ 2x2,x0.5时,g(x)0,a=(-1, 1,2)T,4.1.2 广义线性判别函数,由aTy=0定义的平面将y空间分成两个判别区域，如图给出当a=(-1,1,2)T时的分类平面和x空间对应的判别区域。,结论,aTy=0,在2维空间不穿过原点,4.1.2 广义线性判别函数,一个三维增广特征空间y和增广权向量a(在原点)。满足aTy=0的点集是一个穿过y空间原点的超平面(用红色表示)，这个平面垂直于a。这个平面在其原来的二维空间中不一定穿过原点(即立方体顶部虚线所示的判决边界)。因此存在一个增广权向量a，可以获得x空间中任意的判定线。,4.1.3 设计线性分类器的主要步骤,设计线性分类器，就是建立线性判别函数(4-l)式g(x) =wTx+w0或广义线性判别函数(4-12)式,这样，设计线性分类器就转化为，利用训练样本集寻找准则函数的极值点 和 或 。,设计线性分类器的主要步骤如下：, 要有一组具有类别标志的样本集X=x1，x2，xN。如果在样本 xn 抽出后，把它看作一个确定的观察值，则这组样本集称为确定性样本集；若把 xn 看作一个随机变量，则这组样本集称为随机样本集。有时也将样本集 X 转换成增广样本集 Y 来处理。,4.1.3 设计线性分类器的主要步骤, 要根据实际情况确定一个准则函数 J 它必须满足：, J 的值反映分类器的性能，它的极值解则对应于 最好 的决策。, J是样本集X和w、w0或 a 的函数；,设计线性分类器的主要步骤如下：,4.1.3 设计线性分类器的主要步骤,用最优化技术求出准则函数的极值解 和 w*或a*。,这样就可以得到线性判别函数,或,设计线性分类器的主要步骤如下：,4.1.3 设计线性分类器的主要步骤,4.2 Fisher线性判别,Fisher线性判别函数是经典判别方法之一，应用非常广泛。应用统计方法解决模式识别问题时，困难之一是维数问题。在低维空间里行得通的方法，在高维空间里往往行不通。因此，降低维数有时就成为处理实际问题的关键。,在数学上通常可以把 d 维空间的样本投影到一条直线上，形成一维空间，即把维数压缩到一维。在一般情况下，总可以找到某个方向，使在这个方向的直线上，样本的投影能分开得最好。问题是如何根据实际情况找到这条最好的、使最易于分类的投影线。这就是Fisher法所要解决的基本问题 (见图 4.4) 。,4.2 Fisher线性判别,4.2 Fisher线性判别,从 d 维空间到一维空间的数学变换方法,假设有一集合 X 包含 N 个 d 维样本 x1 ， x2 ，xN ，其中 N1 个属于1 类的样本记为子集 X1 ，N2 个属于2 类的样本记为 X2 ，若对 xn 的分量作线性组合可得标量yn=wTxn, n=1 ， 2 ， Ni这样便得到 N 个一维样本 yn 组成的集合，并可分为两个子集 Y1 和 Y2 。,4.2 Fisher线性判别,w* 就是最好的投影方向,从几何上看，如果 |w|=1 ，则每个 yn 就是相对应的 xn 到方向为 w 的直线上的投影，实际上，w 的绝对值是无关紧要的，它仅使 yn 乘上一个比例因子，重要的是选择 w 的方向。w 的方向不同，将使样本投影后的可分离程度不同，从而直接影响识别效果。因此，前述所谓寻找最好投影方向的问题，在数学上就是寻找最好的变换向量 w*的问题。,4.2 Fisher线性判别,定义几个基本参量,在 d 维 X 空间各类样本均值向量mi,， i =1，2,样本类内离散度矩阵 Si 和总类内离散度矩阵 Sw,，i =1，2,Sw=S1+ S2,4.2 Fisher线性判别,样本类间离散度矩阵Sb,Sb=(m1 m2)(m1 m2)T其中 Sw 是对称半正定矩阵，而且当 Nd 时通常是非奇异的。Sb 也是对称半正定矩阵，在两类条件下，它的秩最大等于 1 。,定义几个基本参量,4.2 Fisher线性判别,在一维 Y 空间,各类样本均值,，i =1，2,样本类内离散度 和总类内离散度,4.2 Fisher线性判别,定义Fisher准则函数,希望投影后，在一维 Y 空间里各类样本尽可能分得开些，即希望两类均值之差越大越好；希望各类样本内部尽量密集，即希望类内离散度越小越好。因此，可以定义Fisher准则函数为：,4.2 Fisher线性判别,寻找使JF(w) 尽可能大的 w 作为投影方向。,但 JF(w)式并不显含w，因此必须设法JF(w) 将变成w的显函数。,尽可能大,尽可能小,Fisher准则函数,4.2 Fisher线性判别,Fisher准则函数,4.2 Fisher线性判别,Fisher准则函数,4.2 Fisher线性判别,Fisher准则的合理性：,JF(w)只与投影方向有关，与大小无关若w是一个最优解， kw也是最优解，k是任何不为零的常数。,4.2 Fisher线性判别,Fisher最佳投影方向的求解：,要求：Sw = S1 + S2正定。否则，存在投影方向w，使得wTSww=0，所有数据被投影到一点上。 JF(w)没有极大值。求出最佳投影方向上任何一个w即可。JF(w)有上界，最佳投影方向一定存在！,(Sb)max，(Sw)min分别是Sb，Sw矩阵的最大、最小的特征根。,4.2 Fisher线性判别,Fisher最佳投影方向的求解：,一定存在一个最优的w ，满足wTSww=1，因为Sw 正定。,无约束最优化：,等价于带约束的最优化： max wTSbw wTSww=1,4.2 Fisher线性判别,因为分母等于1是非零常数，wTSww=10定义 Lagrange 函数为,JF(w)是广义Rayleigh商，带等式约束的最优化，可以用Lagrange乘子法求解。,Fisher最佳投影方向的求解：,4.2 Fisher线性判别,式中 为Lagrange乘子，将上式对w求偏导数，得,Fisher最佳投影方向的求解：,4.2 Fisher线性判别,最优解满足：,其中 w*就是 JF(w) 的极值解。,因为Sw非奇异，上式两边左乘 ，可得,Fisher最佳投影方向的求解：,4.2 Fisher线性判别,解上式是求一般矩阵 的本征值问题。,根据类间离散度Sb 的定义，上式左边的 Sbw*可以写成,Fisher最佳投影方向的求解：,注意 是一个数，所以 总是在向量(m1m2)的方向上。,4.2 Fisher线性判别,只关心投影的方向：,w*就是使Fisher准则函数JF(w)取极大值时的解，也就是d维X空间到一维Y空间的最好投影方向。,Fisher最佳投影方向的求解：,4.2 Fisher线性判别,几种分类阈值的确定,均值中点法,类样本数加权法,4.2 Fisher线性判别,根据决策规则,先验概率加权法,就可判断x属于什么类别。,几种分类阈值的确定,4.2 Fisher线性判别,例子,4.2 Fisher线性判别,4.3 感知准则函数,感知器算法的基本思想是，对初始的或迭代中的增广权向量，用训练样本检测其合理性，当不合理时，对其校正，校正方法是优化技术中的梯度下降法。首先介绍几个概念。,4.3.1 几个基本概念 线性可分性,假设已知一组容量为N的样本集y1，y2，yN，其中yn为d维增广样本向量，分别来自1和2类。,则称样本集为线性可分的(Linearly Separable)；否则为线性不可分的。,如果存在一个权向量a,对于任何容量为N的样本集，线性可分的概率有多大呢？,例如假设有4个二维样本，N = 4，d = 2。若把每个样本任意分到1或2两种类别之一，则共有2N = 24 =16种可能的分法。只要不出现三个样本共线的情况，那么16种可能的分法中有14种是线性可分的，只有2种是线性不可分的，或线性可分的概率是7/8。,4.3.1 几个基本概念 线性可分性,N个样本为线性可分的概率为,对于任何容量为N的样本集，线性可分的概率有多大呢？,4.3.1 几个基本概念 线性可分性,对于任何容量为N的样本集，线性可分的概率有多大呢？,设阈值N0=2(d+1)，对N个样本的线性可分性给出一个粗略的估计。如图4.6所示。,阈值,d相同，N大于2(d+1)，p(N,d)急剧下降。N = 2(d+1)是d维模式为保证两分性至少应该具有的样本数N。一般地，N越大，训练出的判别函数越可靠。,4.3.1 几个基本概念 线性可分性, 样本的规范化,如果样本集y1,y2,yn是线性可分的，则必存在某个或某些权向量，使得,或者说，满足上式的一切权向量a，都能将全部N个样本正确分类。,4.3.1 几个基本概念 线性可分性,如果2类的样本yj前加上一个负号，用负号表示而不是用2表示2类的样本，用规范化(normalization)简化两类样本的训练过程。只要对全部样本都满足aTyn0，n=1，2，N的权向量a即可。a被称作分离向量(separating vector)或解向量(solution vector)。, 样本的规范化,4.3.1 几个基本概念 线性可分性, 解向量和解区,解向量如果存在，则必在 的正侧，因为只有在正侧才能满足 。,4.3.1 几个基本概念 线性可分性, 解向量和解区,4.3.1 几个基本概念 线性可分性,4.3.2 梯度下降算法,，n=1,2，N，,设有一组样本y1，y2，yN，其中yn是规范化增广样本向量，目的是找一个解向量 a，使,采用的方法是：定义一个准则函数J(a)，当a是解向量时，J(a)最小。标量函数最小化问题用梯度下降法。,4.3.2 梯度下降算法,梯度下降法的原理：从随意选择的权向量a(1)开始，计算其梯度向量 J(a(1)， a(2)由自a(1)向下降最陡的方向移一段距离得到。,设定步长的学习率(learn rate)或正的比例因子。,获得权向量序列，使J(a)极小,Algorithm 1 (Basic gradient descent) ：1 begin initialize a; criterion , (), k 02 do k k + 13 a a (k) J(a)4 until |(k) J(a)| 5 return a6 end,4.3.2 梯度下降算法,其中H是赫森矩阵，是J(a)在a(k)的二阶偏导：,4.3.2 梯度下降算法,梯度下降法存在问题：如何选择学习率(k)？如果(k)太小，收敛将非常慢；而如果(k)太大的话可能会过冲(overshoot)，甚至发散。牛顿下降法：,牛顿下降法：Algorithm 2 (Newton descent)1 begin initialize a; criterion 2 do3 a aH1J(a)4 until |H1J(a)| 5 return a6 end,4.3.2 梯度下降算法,简单梯度下降法和牛顿下降法的比较:,简单梯度下降法,牛顿(二阶)算法每一步都给出更好的步长但求赫森逆矩阵的计算量很大,4.3.2 梯度下降算法,4.3.3 感知器准则函数(perceptron criterion function),构造这样一个准则函数,式中Yk是被权向量a错分类的样本集合。当y被错分类时,也就是说，当且仅当不存在错分样本，即Yk为空集时,4.3.3 感知器准则函数,求准则函数的梯度,感知器准则函数的算法(批处理)：Algorithm 3 (Batch Perceptron)1 begin initialize a; (), criterion , k 02 do k k + 13 a a + (k) yYky4 until |(k) yYky| 5 return a6 end,4.3.3 感知器准则函数,感知器准则函数的简单例子：a(1)=0，(k)=1,注意：样本集的选择应具有代表性，包括各种情况。如果实际训练样本集线性不可分，算法不收敛。,4.3.3 感知器准则函数,单样本修正法把样本集看作一个不断重复出现的序列而逐个加以考虑。对于任意权向量a(k)，如果它把某个样本分错了，则对a(k)做一次修正单样本修正法,4.3.3 感知器准则函数,单样本修正法构造一个准则函数,当yn被错分类时， ，所以,4.3.3 感知器准则函数,单样本修正法,当yn正确分类时， ，所以，,使准则函数 达到极小值时的权向量 采用梯度下降法求解。,4.3.3 感知器准则函数,准则函数J(a)的梯度为,对(k)=1的情况，迭代公式为,4.3.3 感知器准则函数,线性分类的感知判别函数例,4.3.3 感知器准则函数,多分类的感知判别函数例,4.3.3 感知器准则函数,例4.1：如图4.9所示的二维两类模式，试建立用以分类的感知判别函数。,4.3.3 感知器准则函数,1与2类模式如下：1：y1= (0，0，1)T， y2= (0，1，1)T2：y3= (1，0，1)T， y4= (1，1，1)T,yi为增广向量，y = (x1，x2，1)T。对样本规范化 y3= (-1，0，-1)T， y4= (-1，-1，-1)T,令 ， ，则有,，误判,4.3.3 感知器准则函数,，判别正确,，误判,，判别正确,4.3.3 感知器准则函数,因为存在误判项，因此需要进行第二轮迭代过程，令,y5 = y1，y6 = y2，y7 = y3，y8 = y4,可得,，误判,，正确判别 ,4.3.3 感知器准则函数,，误判 ,，正确判别 ,因为上述迭代过程中仍有误判，因此需要进行第三轮迭代过程。,4.3.3 感知器准则函数,，误判 ,，正确判别,，正确判别 ,4.3.3 感知器准则函数,，正确判别 ,自 以后权向量一直保持不变，进行第四轮迭代后全部正确判别。,，正确判别,4.3.3 感知器准则函数,，正确判别,，正确判别,，正确判别,权向量的解 ，线性判别函数,4.3.3 感知器准则函数,决策面方程 g(x) =2x1+1 = 0 如图4.9所示。,4.3.3 感知器准则函数,4.4 最小错分样本数准则,由于感知准则函数及其梯度下降算法只适用于线性可分情况，对于线性不可分情况，迭代过程永远不会终结，即算法不收敛。但在实际问题中往往无法事先知道样本集是否线性可分，因此，希望找到一种既适用于线性可分情况，又适用于线性不可分情况的算法。,这种算法对于线性可分问题，可以得到一个如感知准则函数那样的解向量a*，使得对两类样本集做到将全部样本正确分类；而对于线性不可分问题，则得到一个使两类样本集错分数目最少的权向量 把它也记为a*最小错分样本数准则。,4.4 最小错分样本数准则,4.4.1解线性不等式组的共轭梯度法,对于规范化增广样本向量，线性判别函数可写作,则说yn被正确分类。因此，设计线性分类器就是求一组N个线性不等式(4-44)的解的问题。,如果存在权向量a，使得,若不等式组有解(不等式组一致)，说明样本集是线性可分的，可以找到这个解向量 a*。若不等式组无解(不等式不一致)，说明样本集是线性不可分的，对于任何权向量a必有某些样本被错分类，这时可以转而寻找使最多数目的不等式得到满足的权向量a ，把它作为问题的解a*。,4.4.1解线性不等式组的共轭梯度法,首先给出一个准则函数，然后用共轭梯度法求使准则函数取极值时的解向量a 。用矩阵形式重写式aTy0所表示的不等式组，,4.4.1解线性不等式组的共轭梯度法,为使解更可靠，引入余量b 0，那么,规范化增广样本矩阵,4.4.1解线性不等式组的共轭梯度法,对于(4-47)式可以定义准则函数,(4-47),N维向量,4.4.1解线性不等式组的共轭梯度法,如果 则 和 同号，因此， ，反之，如果有某些yi不满足 ，则 和 异号，因此， 。不满足的yi越多， 越大。,4.4.1解线性不等式组的共轭梯度法,显然， 取极小值时的a为最优解a*。并且在不等式组一致的情况下， ，在不等式组不一致情况下， 。,称为最小错分样本数准则1。,4.4.1解线性不等式组的共轭梯度法,共轭梯度算法的基本概念,设B是一个dd阶对称正定矩阵，若有两个d维向量u和v使(u，Bv)=0，则称u和v对于矩阵B互为共轭。显然，若u和v对于单位阵I互为共轭，则u和v正交，当x和y是B的本征向量时，有 (y，Bx)=(y,x)=(y，x) = 0因此，一个正定矩阵B的本征向量对于B互为共轭。,4.4.1解线性不等式组的共轭梯度法,共轭梯度算法就是以Ed空间中的一组对于B互为共轭的向量作为一维搜索方向，使二次正定函数f(x) = b0+bTx+xTBx 达到极小值的最优化算法。用共轭梯度法可以求得序列x0，x1，x2，使得f (x0)f (x1)f (x2)可以证明，对于二次正定函数f (x)，最多用d步，就可以使序列x收敛于f (x)的极值解x*。,4.4.1解线性不等式组的共轭梯度法,因此，在沿d个(对于增广空间则为d+1个)互为共轭的向量进行一维搜索后，有可能达不到准则函数的最小值，即算法经过d(或d+1)步可能不收敛，这时就要重新开始计算，若用r表示重新开始的周期，则r = d(或d+1)。,由于 式定义的准则函数不是一个二次正定函数，而是一个分段二次正定函数，,4.4.1解线性不等式组的共轭梯度法,在任意点 ， 的负梯度方向可表示为,4.4.1解线性不等式组的共轭梯度法,令,这种算法的具体步骤如下：,用k表示迭代步数，用 表示满足于 的不等式的数目， 表示最优解。,置k = 0，并任意给定初始权向量 ，计算 和 。,如果 ，则令,然后继续。,4.4.1解线性不等式组的共轭梯度法,如果 ，则令 ，停止；如果 ，则令 ，停止；否则继续。,计算gk。如果gk=0，则停止；否则计算 ，然后继续。,求k。如果k为r的整数倍，则令k= 0；否则令k=1，并计算,Sk表示第k次搜索时的梯度下降方向。若 表示对 的第一次逼近，则 。可以证明，由上述表达式所产生的S1，S2，对于二次函数中的正定矩阵是互为共轭的。,4.4.1解线性不等式组的共轭梯度法,寻找最佳步长vk，即计算使 取极小值时的v。,令 ， 并计算 。,令k = k + 1，转向步骤2。,4.4.1解线性不等式组的共轭梯度法,Nagaraja和Krishna证明，对于 表示的分段二次函数，在 的一致条件下，上述算法可以在有限步内使序列收敛于最优解。,4.4.1解线性不等式组的共轭梯度法,而在 不一致条件下，只要适当的选择b，使在 的唯一极小点 上，有,，i=1，2，N,则该算法产生的序列a也在有限步内收敛于 a* 。,对于 表示的准则函数，在不等式组不一致的情况下，对某些样本，可能存在,因此就产生了一个阈值问题。这时，由于 aTyi0，yi应被正确分类；但又由于 aTyibi ，所以在算法中是按错分类处理的。故提出下面的补充算法。,4.4.1解线性不等式组的共轭梯度法,如果在 式中，假定b = 0，那么准则函数为,上述算法可以使上式中的 Jq1(a)极小化，在一致的情况下Y(a)0收敛于的解a*。在不一致情况下，由于Jq1(a)是严格的凸函数，其唯一极小点是a=0，而且有,4.4.1解线性不等式组的共轭梯度法,因此，aTyi bi(i=1，2，N)的条件不成立，所以得不到解向量a*。,4.4.1解线性不等式组的共轭梯度法,作为准则函数来解决上述问题。显然，这时存在下列关系：,也就是说，使 最小，同在终止条件,和 下使 最小是等价的。这时需要将上述算法的步骤1和4改变如下：,4.4.1解线性不等式组的共轭梯度法,通过原有算法得到一个收敛点，记为 ，并以此作为补充算法的起点。,计算 和 ，并且继续。,可以证明，这样得到的Sk仍然是 的下降方向。,同时可以证明，假使Ya0是不一致的，且在求Jq1(a)最小值的过程中用步骤代替原算法的步骤4，若所得的序列a是有限的，则序列的最后一个元素就相当于F(a)的一个局部最小值的解。,4.4.1解线性不等式组的共轭梯度法,若序列是无限的，则它趋向于F(a)的一个局部最小值的解。在进行上述计算时，由于我们使用原算法的收敛点as 作为起始点，它常常是全局最优解F(a)的一个很好的逼近，故可以得到的全局最优解。,4.4.1解线性不等式组的共轭梯度法,4.4.2解线性不等式组的搜索法,考虑齐次线性不等式组,其中 矩阵,为规范化增广样本矩阵，每一行yi代表一个样本，N为样本数，,为yi的维数。,且有,式中,使Jq2(a)取最大值的a就是要求的解 a*。,现在定义另一种形式的最小错分样本数准则如下：,4.4.2解线性不等式组的搜索法,因此，N个样本向量所建立的超平面把权空间划分成为凸多棱锥的有限集合，每个锥C都由有限个支撑超平面所组成。,对于每个yi，方程yia =0在权空间中建立了一个超平面Hi，而且所有超平面都通过原点。,组成锥的一部分超平面，或超平面的截取部分，称为锥的“前沿”，欧氏空间Ed中 个超平面的交叫做锥的棱。,4.4.2解线性不等式组的搜索法,图4.10示出三维凸多棱锥及其前沿和棱的一个例子。,而且某个锥C中的任何权向量对样本集的划分都是相同的，或者说，某个锥中的所有权向量所满足的不等式的数目是相同的。,锥C中的每一个点，都对应一个权向量a,4.4.2解线性不等式组的搜索法,如果某个锥C中的任何权向量都能使上式的准则函数为最大，那么就称这个锥为最小错误锥，记为C*。,这样，求使最多数目的不等式得到满足的权向量 的问题，就转化为寻找一个或多个最小错误锥C*的问题了。,由于对于每个CEd，存在着对称反射，即 维权向量 和 所产生的分类情况恰好相反，所以，如果对于某个存在,4.4.2解线性不等式组的搜索法,其中,则必有 。,4.4.2解线性不等式组的搜索法,寻找最小错误锥C*的搜索算法。,定理 假设Y满足Haar(Y的每个 子阵的秩都是 )条件，令 是Ed中任何一条棱上的权向量，不失一般性，初始棱选作前 个样本yi确定的 个超平面的交，即令：,那么，最优权向量 一定在下面定义的搜索序列中，,4.4.2解线性不等式组的搜索法,定理确定的算法构成了一棵搜索树(见图4.11)。,4.4.2解线性不等式组的搜索法,4.4.2解线性不等式组的搜索法,简单例子说明,为清楚起见，用横截面来表示它们的超平面，见图4.12。,假设有八个三维样本组成的样本集，即,4.4.2解线性不等式组的搜索法,4.4.2解线性不等式组的搜索法,所以，I1=3，5，7。选I1中的第一个 元素i1=3，用H3代替中的H1，得,由于,4.4.2解线性不等式组的搜索法,接着选I2中的第一个元素i2=1，用H1代替中的H2，就得到,由于 ， ，所以I2=1，5因 所以搜索序列到此就终止了。,4.4.2解线性不等式组的搜索法,I2中的元素已全部考虑过，现在再考虑I1中的第二个元素，令i1=5，用H5代替中的H1，得,选I2中的第二个元素，i2=5，用H5代替中的H2，得到,4.4.2解线性不等式组的搜索法,由此可得I2=1，4，8,4.4.2解线性不等式组的搜索法,最后考虑I1中得第三个元素，取i1=7，从而得,由此可得I2=1，3，5，,至此，搜索过程结束。,这是一个非穷举型搜索算法，它比E3中全部可能的搜索数目 要小得多。,在上面的12条棱的搜索过程中，可以看到最优解出现在 和 上，由此便可求得最优权向量 。,4.4.2解线性不等式组的搜索法,