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