第四章线性判别函数

第四章线性判别函数第1页，共130页，2023年，2月20日，星期四解决实际问题方法在实际中存在问题样本特征空间的类条件概率密度形式常常很难确定利用Parzen窗等非参数方法恢复分布往往需要大量样本，而且随着特征空间维数的增加所需样本数急剧增加。因此，在解决实际问题时，往往是利用样本集直接设计分类器，而不恢复类条件概率密度。即采用判别函数，首先给定某个判别函数类，然后利用样本集确定出判别函数中的未知参数。第2页，共130页，2023年，2月20日，星期四线性判别函数线性判别函数法是一类较为简单的判别函数。是统计模式识别的基本方法之一。它首先假定判别函数g(x)是x

的线性函数，即g(x)=wTx+w0

，对于c

类问题，可以定义c

个判别函数，gi(x)=wiTx+wi0

，i=1,2，…，c

。用样本去估计各wi

和wi0

，并把未知样本x

归到具有最大判别函数值的类别中去。关键是如何利用样本集求得wi

和wi0

。第3页，共130页，2023年，2月20日，星期四训练和学习“训练”和“学习”在待识别的模式中，挑选一批有代表性的样本，经过人工判读，成为已知分类的样本，把这批样本逐个输入到计算机中的“训练”程序或算法中，通过一次次的迭代，最后得到正确的线性判别函数。这样的迭代过程称之为训练过程，所构成的分类器称为有人监督或有教师的分类器。第4页，共130页，2023年，2月20日，星期四4.1.1线性判别函数的基本概念在正态分布的Bayesian判别中，已经遇到过在两类情况下判别函数为线性的情况。假设有ω1

和ω2

两类模式，在二维模式特征空间可用一直线把这两类模式划分开，如图4.1所示。第5页，共130页，2023年，2月20日，星期四x1x2g(x)=w2x2+w1x1+w0

图4.1两类模式的一个简单判别函数+－划分直线的方程参数坐标变量4.1.1线性判别函数的基本概念第6页，共130页，2023年，2月20日，星期四判别规则若给定一个未知类别的模式x当g(x)>0时，则决策x

属于ω1

；当g(x)<0，则决策x

属于ω2；若x处于划分边界上即g(x)=0，则x的类别不可确定，则可将x任意分到某一类或拒绝，g(x)=0为不可确定的条件。这一概念可以推广到有限维欧氏空间中的非线性边界的更一般情况。4.1.1线性判别函数的基本概念第7页，共130页，2023年，2月20日，星期四g(x)=wdxd+wd-1xd-1+…+w1x1+w0

=wTx+w0(4-1)一般的线性判别函数形式为：特征向量(样本向量)权向量阈值权(常数)4.1.1线性判别函数的基本概念第8页，共130页，2023年，2月20日，星期四简单线性分类器：4.1.1线性判别函数的基本概念第9页，共130页，2023年，2月20日，星期四对于两类问题的线性分类器决策规则：令g(x)=g1(x)－g2(x)如果g(x)＞0，则决策x∈ω1g(x)＜0，则决策x∈ω2(4-2)g(x)＝0，则可将x

任意分到某一类或拒绝4.1.1线性判别函数的基本概念第10页，共130页，2023年，2月20日，星期四对于两类问题的线性分类器决策规则：方程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线性判别函数的基本概念第11页，共130页，2023年，2月20日，星期四一般地，一个超平面H

把特征空间分成两个半空间，即对ω1

类的决策域R1

和对ω2

类的决策域R2

。因为当x

在R1

中时，g(x)>0，所以决策面的法向量是指向R1

的。因此，有时称R1

中的任何x

在H

的正侧，相应地，称R2

中的任何x

在H

的负侧。4.1.1线性判别函数的基本概念第12页，共130页，2023年，2月20日，星期四判别函数g(x)是特征空间中某点x

到超平面距离的一种代数量度。若把x

表示成式中xp

：是x

在H

上的投影向量；

r：是x

到H

的垂直距离；：是w方向上的单位向量。4.1.1线性判别函数的基本概念第13页，共130页，2023年，2月20日，星期四若x

为原点，则g(x)=w0(4-7)将(4-7)代入(4-6)，就得到从原点到超平面H

的距离(4-6)判别函数g(x)是特征空间中某点x

到超平面距离的一种代数量度。4.1.1线性判别函数的基本概念第14页，共130页，2023年，2月20日，星期四如果w0>0，则原点在H

的正侧；若w0<0，则原点在H

的负侧。若w0=0，则g(x)具有齐次形式wTx

，说明超平面H

通过原点。判别函数g(x)是特征空间中某点x

到超平面距离的一种代数量度。4.1.1线性判别函数的基本概念第15页，共130页，2023年，2月20日，星期四图4.2对这些结果作了几何解释。4.1.1线性判别函数的基本概念第16页，共130页，2023年，2月20日，星期四结论利用线性判别函数进行决策，就是用一个超平面把特征空间分割成两个决策区域。超平面的方向由权向量w

确定，它的位置由阈值权w0

确定。判别函数g(x)正比于x

点到超平面的代数距离（带正负号）当x

在H

正侧时，g(x)＞0，在负侧时，g(x)＜0。4.1.1线性判别函数的基本概念第17页，共130页，2023年，2月20日，星期四4.1.2广义线性判别函数如图4.3所示的二类问题。设有一维样本空间X

，所希望的划分是：如果x<b或x>a

，则x

属于ω1

类；如果b<x<a

，则x

属于ω2

类。xg(x)图4.3baω1ω1ω2第18页，共130页，2023年，2月20日，星期四4.1.2广义线性判别函数显然，没有任何一个线性判别函数能解决上述划分问题。这说明线性判别函数虽然简单，但局限性较大，不适用于非凸决策区域和多连通区域的划分问题。第19页，共130页，2023年，2月20日，星期四xg(x)baω1ω1ω2图4.3从图4.3中可以看出，如果建立二次判别函数

g(x)=(x-a)(x-b)

(4-9)则可以很好地解决上述分类问题，决策规则是：g(x)>0

，则决策

x∈ω1g(x)<0

，则决策x∈ω2二次判别函数可写成如下一般形式g(x)=c0+c1x+c2x2(4-10)如果适当选择x→y

的映射，则可把二次判别函数化为y

的线性函数4.1.2广义线性判别函数第20页，共130页，2023年，2月20日，星期四式中称为广义判别函数，a叫做广义权向量。

一般地，对于任意高次判别函数g(x)(这时的g(x)可看作对任意判别函数作级数展开，然后取其截尾部分的逼近)，都可以通过适当的变换，化为广义线性判别函数来处理。4.1.2广义线性判别函数第21页，共130页，2023年，2月20日，星期四存在问题经过变换后，维数大大增加了，这将使问题很快陷入所谓“维数灾难”。在统计学习理论中，对广义线性分类器进行研究，克服了“维数灾难”问题，进而发展出了最新的模式识别方法——支持向量机，成为解决有限样本情况下非线性分类问题的有效手段。4.1.2广义线性判别函数第22页，共130页，2023年，2月20日，星期四把(4-1)式定义的线性判别函数写成下面的形式(4-12)增广特征向量Augmentedfeaturevector增广权向量(广义权向量)Augmentedweightvector4.1.2广义线性判别函数第23页，共130页，2023年，2月20日，星期四结论y与

x

相比，虽然增加了一维，但保持了样本间的欧氏距离不变，变换后的样本向量仍然全部位于d

维子空间，即原X

空间中，方程(4-13)在Y空间确定了一个通过原点的超平面。它对d维子空间的划分与原决策面wTx+w0=0对原X

空间的划分完全相同。4.1.2广义线性判别函数第24页，共130页，2023年，2月20日，星期四例子这种方法的优缺点可通过例子来说明。考虑二次判别函数得到三维向量y从x到y的映射如图所示。4.1.2广义线性判别函数第25页，共130页，2023年，2月20日，星期四例子4.1.2广义线性判别函数数据仍保持固有的一维，因为改变x将导致y沿着一个三维曲线运动。如果x服从某一个概率分布时，得到的密度函数是退化的，即曲线之外是0，在曲线上是无穷大，这是从低维空间到高维空间映射的普遍问题。第26页，共130页，2023年，2月20日，星期四例子4.1.2广义线性判别函数图中映射y=(1,x,x2)T把一条直线映射为三维空间中的一条抛物线。由于两类问题，在三维空间中，一个平面就是一个分隔面。因此，由图可见，这产生了原始一维x空间的不连通性第27页，共130页，2023年，2月20日，星期四例子g(x)=－1+x+2x2x<－1和

x>0.5时g(x)>0a=(-1,1,2)T4.1.2广义线性判别函数由aTy=0定义的平面将y空间分成两个判别区域，如图给出当a=(-1,1,2)T时的分类平面和x空间对应的判别区域。第28页，共130页，2023年，2月20日，星期四结论aTy=0在2维空间不穿过原点4.1.2广义线性判别函数一个三维增广特征空间y和增广权向量a(在原点)。满足aTy=0的点集是一个穿过y空间原点的超平面(用红色表示)，这个平面垂直于a。这个平面在其原来的二维空间中不一定穿过原点(即立方体顶部虚线所示的判决边界)。因此存在一个增广权向量a，可以获得x空间中任意的判定线。第29页，共130页，2023年，2月20日，星期四4.1.3设计线性分类器的主要步骤设计线性分类器，就是建立线性判别函数(4-l)式g(x)=wTx+w0或广义线性判别函数(4-12)式这样，设计线性分类器就转化为，利用训练样本集寻找准则函数的极值点和或。第30页，共130页，2023年，2月20日，星期四设计线性分类器的主要步骤如下：⒈要有一组具有类别标志的样本集X={x1，x2，…，xN}。如果在样本xn

抽出后，把它看作一个确定的观察值，则这组样本集称为确定性样本集；若把xn

看作一个随机变量，则这组样本集称为随机样本集。有时也将样本集X转换成增广样本集Y来处理。4.1.3设计线性分类器的主要步骤第31页，共130页，2023年，2月20日，星期四⒉要根据实际情况确定一个准则函数J它必须满足：⑵J

的值反映分类器的性能，它的极值解则对应于"最好"的决策。⑴

J是样本集X和w、w0或a

的函数；设计线性分类器的主要步骤如下：4.1.3设计线性分类器的主要步骤第32页，共130页，2023年，2月20日，星期四⒊用最优化技术求出准则函数的极值解和w*或a*。这样就可以得到线性判别函数或设计线性分类器的主要步骤如下：4.1.3设计线性分类器的主要步骤第33页，共130页，2023年，2月20日，星期四4.2Fisher线性判别Fisher线性判别函数是经典判别方法之一，应用非常广泛。应用统计方法解决模式识别问题时，困难之一是维数问题。在低维空间里行得通的方法，在高维空间里往往行不通。因此，降低维数有时就成为处理实际问题的关键。第34页，共130页，2023年，2月20日，星期四在数学上通常可以把d

维空间的样本投影到一条直线上，形成一维空间，即把维数压缩到一维。在一般情况下，总可以找到某个方向，使在这个方向的直线上，样本的投影能分开得最好。问题是如何根据实际情况找到这条最好的、使最易于分类的投影线。这就是Fisher法所要解决的基本问题(见图4.4)。4.2Fisher线性判别第35页，共130页，2023年，2月20日，星期四4.2Fisher线性判别第36页，共130页，2023年，2月20日，星期四从

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.2Fisher线性判别第37页，共130页，2023年，2月20日，星期四w*就是最好的投影方向从几何上看，如果||w||=1，则每个yn

就是相对应的xn到方向为w

的直线上的投影，实际上，w

的绝对值是无关紧要的，它仅使yn

乘上一个比例因子，重要的是选择w

的方向。w的方向不同，将使样本投影后的可分离程度不同，从而直接影响识别效果。因此，前述所谓寻找最好投影方向的问题，在数学上就是寻找最好的变换向量

w*的问题。4.2Fisher线性判别第38页，共130页，2023年，2月20日，星期四定义几个基本参量⒈在d

维

X

空间⑴各类样本均值向量mi，i=1，2⑵样本类内离散度矩阵Si

和总类内离散度矩阵Sw，i=1，2Sw=S1+S24.2Fisher线性判别第39页，共130页，2023年，2月20日，星期四⑶样本类间离散度矩阵SbSb=(m1

－m2)(m1

－m2)T其中Sw

是对称半正定矩阵，而且当N>d

时通常是非奇异的。Sb

也是对称半正定矩阵，在两类条件下，它的秩最大等于1。定义几个基本参量4.2Fisher线性判别第40页，共130页，2023年，2月20日，星期四⒉在一维Y

空间⑴各类样本均值，i=1，2⑵样本类内离散度和总类内离散度4.2Fisher线性判别第41页，共130页，2023年，2月20日，星期四定义Fisher准则函数希望投影后，在一维Y

空间里各类样本尽可能分得开些，即希望两类均值之差越大越好；希望各类样本内部尽量密集，即希望类内离散度越小越好。因此，可以定义Fisher准则函数为：4.2Fisher线性判别第42页，共130页，2023年，2月20日，星期四寻找使JF(w)尽可能大的w

作为投影方向。但JF(w)式并不显含w，因此必须设法JF(w)

将变成w的显函数。尽可能大尽可能小Fisher准则函数4.2Fisher线性判别第43页，共130页，2023年，2月20日，星期四Fisher准则函数4.2Fisher线性判别第44页，共130页，2023年，2月20日，星期四Fisher准则函数4.2Fisher线性判别第45页，共130页，2023年，2月20日，星期四Fisher准则的合理性：JF(w)只与投影方向有关，与大小无关—若w是一个最优解，kw也是最优解，k是任何不为零的常数。4.2Fisher线性判别第46页，共130页，2023年，2月20日，星期四Fisher最佳投影方向的求解：要求：Sw

=S1

+S2正定。否则，存在投影方向w，使得wTSww=0，所有数据被投影到一点上。JF(w)没有极大值。求出最佳投影方向上任何一个w即可。JF(w)有上界，最佳投影方向一定存在！λ(Sb)max，λ(Sw)min分别是Sb，Sw矩阵的最大、最小的特征根。4.2Fisher线性判别第47页，共130页，2023年，2月20日，星期四Fisher最佳投影方向的求解：一定存在一个最优的w

，满足wTSww=1，因为Sw

正定。无约束最优化：等价于带约束的最优化：

maxwTSbw

wTSww=14.2Fisher线性判别第48页，共130页，2023年，2月20日，星期四因为分母等于1是非零常数，wTSww=1≠0定义Lagrange函数为JF(w)是广义Rayleigh商，带等式约束的最优化，可以用Lagrange乘子法求解。Fisher最佳投影方向的求解：4.2Fisher线性判别第49页，共130页，2023年，2月20日，星期四式中为Lagrange乘子，将上式对w求偏导数，得Fisher最佳投影方向的求解：4.2Fisher线性判别第50页，共130页，2023年，2月20日，星期四最优解满足：其中w*就是JF(w)的极值解。因为Sw非奇异，上式两边左乘，可得Fisher最佳投影方向的求解：4.2Fisher线性判别第51页，共130页，2023年，2月20日，星期四解上式是求一般矩阵的本征值问题。根据类间离散度Sb

的定义，上式左边的Sbw*可以写成Fisher最佳投影方向的求解：注意是一个数，所以总是在向量(m1－m2)的方向上。4.2Fisher线性判别第52页，共130页，2023年，2月20日，星期四只关心投影的方向：w*就是使Fisher准则函数JF(w)取极大值时的解，也就是d维X空间到一维Y空间的最好投影方向。Fisher最佳投影方向的求解：4.2Fisher线性判别第53页，共130页，2023年，2月20日，星期四几种分类阈值的确定均值中点法类样本数加权法4.2Fisher线性判别第54页，共130页，2023年，2月20日，星期四根据决策规则

先验概率加权法就可判断x属于什么类别。y>y0→

x∈ω1ω2<几种分类阈值的确定4.2Fisher线性判别第55页，共130页，2023年，2月20日，星期四例子4.2Fisher线性判别第56页，共130页，2023年，2月20日，星期四4.3感知准则函数

感知器算法的基本思想是，对初始的或迭代中的增广权向量，用训练样本检测其合理性，当不合理时，对其校正，校正方法是优化技术中的梯度下降法。首先介绍几个概念。第57页，共130页，2023年，2月20日，星期四4.3.1几个基本概念㈠线性可分性假设已知一组容量为N的样本集y1，y2，…，yN，其中yn为d维增广样本向量，分别来自ω1和ω2类。则称样本集为线性可分的(LinearlySeparable)；否则为线性不可分的。如果存在一个权向量a第58页，共130页，2023年，2月20日，星期四对于任何容量为N的样本集，线性可分的概率有多大呢？

例如假设有4个二维样本，N=4，d=2。若把每个样本任意分到ω1或ω2两种类别之一，则共有2N=24=16种可能的分法。只要不出现三个样本共线的情况，那么16种可能的分法中有14种是线性可分的，只有2种是线性不可分的，或线性可分的概率是7/8。4.3.1几个基本概念㈠线性可分性第59页，共130页，2023年，2月20日，星期四N个样本为线性可分的概率为对于任何容量为N的样本集，线性可分的概率有多大呢？4.3.1几个基本概念㈠线性可分性第60页，共130页，2023年，2月20日，星期四对于任何容量为N的样本集，线性可分的概率有多大呢？设阈值N0=2(d+1)，对N个样本的线性可分性给出一个粗略的估计。如图4.6所示。

阈值0123450.00.20.40.60.81.0P(N,d)d=∞2551图4.6d相同，N大于2(d+1)，p(N,d)急剧下降。N=2(d+1)是d维模式为保证两分性至少应该具有的样本数N。一般地，N越大，训练出的判别函数越可靠。4.3.1几个基本概念㈠线性可分性第61页，共130页，2023年，2月20日，星期四㈡样本的规范化

如果样本集y1,y2,…,yn是线性可分的，则必存在某个或某些权向量，使得对于一切yi∈ω1对于一切yj∈ω2

或者说，满足上式的一切权向量a，都能将全部N个样本正确分类。4.3.1几个基本概念㈠线性可分性第62页，共130页，2023年，2月20日，星期四如果ω2类的样本yj前加上一个负号，用负号表示而不是用ω2表示ω2类的样本，用规范化(normalization)简化两类样本的训练过程。只要对全部样本都满足aTyn>0，n=1，2，…，N的权向量a即可。a被称作分离向量(separatingvector)或解向量(solutionvector)。㈡样本的规范化

4.3.1几个基本概念㈠线性可分性第63页，共130页，2023年，2月20日，星期四㈢解向量和解区解向量如果存在，则必在的正侧，因为只有在正侧才能满足。4.3.1几个基本概念㈠线性可分性第64页，共130页，2023年，2月20日，星期四㈢解向量和解区4.3.1几个基本概念㈠线性可分性第65页，共130页，2023年，2月20日，星期四4.3.2梯度下降算法

，n=1,2，…，N，设有一组样本y1，y2，…，yN，其中yn是规范化增广样本向量，目的是找一个解向量a，使采用的方法是：定义一个准则函数J(a)，当a是解向量时，J(a)最小。标量函数最小化问题－用梯度下降法。第66页，共130页，2023年，2月20日，星期四4.3.2梯度下降算法

梯度下降法的原理：从随意选择的权向量a(1)开始，计算其梯度向量▽

J(a(1))，a(2)由自a(1)向下降最陡的方向移一段距离得到。设定步长的学习率(learnrate)或正的比例因子。获得权向量序列，使J(a)极小第67页，共130页，2023年，2月20日，星期四Algorithm1(Basicgradientdescent)：1begin

initializea;criterionθ,η(·),k←02do

k←k+13a←a－η(k)▽J(a)4until|η(k)▽J(a)|<θ5returna6end4.3.2梯度下降算法

第68页，共130页，2023年，2月20日，星期四其中H是赫森矩阵，是J(a)在a(k)的二阶偏导：4.3.2梯度下降算法

梯度下降法存在问题：如何选择学习率η(k)？如果η(k)太小，收敛将非常慢；而如果η(k)太大的话可能会过冲(overshoot)，甚至发散。牛顿下降法：第69页，共130页，2023年，2月20日，星期四牛顿下降法：Algorithm2(Newtondescent)1begin

initializea;criterionθ2do3a←a－H－1▽J(a)4until|H－1▽J(a)|<θ5returna6end4.3.2梯度下降算法

第70页，共130页，2023年，2月20日，星期四简单梯度下降法和牛顿下降法的比较:简单梯度下降法牛顿(二阶)算法每一步都给出更好的步长但求赫森逆矩阵的计算量很大4.3.2梯度下降算法

第71页，共130页，2023年，2月20日，星期四4.3.3感知器准则函数(perceptroncriterionfunction)构造这样一个准则函数式中Yk是被权向量a错分类的样本集合。当y被错分类时也就是说，当且仅当不存在错分样本，即Yk为空集时第72页，共130页，2023年，2月20日，星期四4.3.3感知器准则函数求准则函数的梯度第73页，共130页，2023年，2月20日，星期四感知器准则函数的算法(批处理)：Algorithm3(BatchPerceptron)1begin

initializea;η(·),criterionθ,k←02dok←k+13a←a+η(k)Σy∈Yky4until

|η(k)∑

y∈Yky|<θ5returna6

end4.3.3感知器准则函数第74页，共130页，2023年，2月20日，星期四感知器准则函数的简单例子：a(1)=0，η(k)=1注意：⑴样本集的选择应具有代表性，包括各种情况。⑵如果实际训练样本集线性不可分，算法不收敛。4.3.3感知器准则函数第75页，共130页，2023年，2月20日，星期四单样本修正法把样本集看作一个不断重复出现的序列而逐个加以考虑。对于任意权向量a(k)，如果它把某个样本分错了，则对a(k)做一次修正——单样本修正法4.3.3感知器准则函数第76页，共130页，2023年，2月20日，星期四单样本修正法构造一个准则函数当yn被错分类时，，所以4.3.3感知器准则函数第77页，共130页，2023年，2月20日，星期四单样本修正法当yn正确分类时，，所以，使准则函数达到极小值时的权向量采用梯度下降法求解。4.3.3感知器准则函数第78页，共130页，2023年，2月20日，星期四准则函数J(a)的梯度为对η(k)=1的情况，迭代公式为4.3.3感知器准则函数第79页，共130页，2023年，2月20日，星期四线性分类的感知判别函数例4.3.3感知器准则函数第80页，共130页，2023年，2月20日，星期四多分类的感知判别函数例4.3.3感知器准则函数第81页，共130页，2023年，2月20日，星期四例4.1：如图4.9所示的二维两类模式，试建立用以分类的感知判别函数。

x1x2011(a)图4.9感知判别例∈ω1∈ω24.3.3感知器准则函数第82页，共130页，2023年，2月20日，星期四ω1与ω2类模式如下：ω1：y1=(0，0，1)T，

y2=(0，1，1)Tω2：y3=(1，0，1)T，

y4=(1，1，1)Tyi为增广向量，y=(x1，x2，1)T。对样本规范化y3=(-1，0，-1)T，

y4=(-1，-1，-1)T令，，则有，误判∴4.3.3感知器准则函数第83页，共130页，2023年，2月20日，星期四，判别正确∴

，误判∴，判别正确∴4.3.3感知器准则函数第84页，共130页，2023年，2月20日，星期四因为存在误判项，因此需要进行第二轮迭代过程，令y5=y1，y6=y2，y7=y3，y8=y4可得，误判∴，正确判别∴4.3.3感知器准则函数第85页，共130页，2023年，2月20日，星期四，误判

∴

，正确判别∴因为上述迭代过程中仍有误判，因此需要进行第三轮迭代过程。4.3.3感知器准则函数第86页，共130页，2023年，2月20日，星期四，误判∴，正确判别∴，正确判别

∴

4.3.3感知器准则函数第87页，共130页，2023年，2月20日，星期四，正确判别

∴

自以后权向量一直保持不变，进行第四轮迭代后全部正确判别。，正确判别4.3.3感知器准则函数第88页，共130页，2023年，2月20日，星期四，正确判别，正确判别

，正确判别权向量的解，线性判别函数4.3.3感知器准则函数第89页，共130页，2023年，2月20日，星期四决策面方程

g(x)=－2x1+1=0

如图4.9所示。

x1x2011g(x)=－2x1+1+-(b)图4.9感知判别例4.3.3感知器准则函数第90页，共130页，2023年，2月20日，星期四4.4最小错分样本数准则由于感知准则函数及其梯度下降算法只适用于线性可分情况，对于线性不可分情况，迭代过程永远不会终结，即算法不收敛。但在实际问题中往往无法事先知道样本集是否线性可分，因此，希望找到一种既适用于线性可分情况，又适用于线性不可分情况的算法。

第91页，共130页，2023年，2月20日，星期四这种算法对于线性可分问题，可以得到一个如感知准则函数那样的解向量a*，使得对两类样本集做到将全部样本正确分类；而对于线性不可分问题，则得到一个使两类样本集错分数目最少的权向量把它也记为a*——最小错分样本数准则。4.4最小错分样本数准则第92页，共130页，2023年，2月20日，星期四4.4.1解线性不等式组的共轭梯度法

对于规范化增广样本向量，线性判别函数可写作则说yn被正确分类。因此，设计线性分类器就是求一组N个线性不等式(4-44)的解的问题。，n=1,2,…,N

(4-44)如果存在权向量a，使得第93页，共130页，2023年，2月20日，星期四若不等式组有解(不等式组一致)，说明样本集是线性可分的，可以找到这个解向量a*。若不等式组无解(不等式不一致)，说明样本集是线性不可分的，对于任何权向量a必有某些样本被错分类，这时可以转而寻找使最多数目的不等式得到满足的权向量a

，把它作为问题的解a*。4.4.1解线性不等式组的共轭梯度法

第94页，共130页，2023年，2月20日，星期四首先给出一个准则函数，然后用共轭梯度法求使准则函数取极值时的解向量a。用矩阵形式重写式aTy>0所表示的不等式组，4.4.1解线性不等式组的共轭梯度法

第95页，共130页，2023年，2月20日，星期四为使解更可靠，引入余量b>0，那么规范化增广样本矩阵4.4.1解线性不等式组的共轭梯度法

第96页，共130页，2023年，2月20日，星期四对于(4-47)式可以定义准则函数

(4-47)N维向量4.4.1解线性不等式组的共轭梯度法

第97页，共130页，2023年，2月20日，星期四如果则和同号，因此，，反之，如果有某些yi不满足，则和异号，因此，。不满足的yi越多，越大。

4.4.1解线性不等式组的共轭梯度法

第98页，共130页，2023年，2月20日，星期四显然，取极小值时的a为最优解a*。并且在不等式组一致的情况下，，在不等式组不一致情况下，。称为最小错分样本数准则1。4.4.1解线性不等式组的共轭梯度法

第99页，共130页，2023年，2月20日，星期四共轭梯度算法的基本概念设B是一个d×d阶对称正定矩阵，若有两个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解线性不等式组的共轭梯度法

第100页，共130页，2023年，2月20日，星期四共轭梯度算法就是以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解线性不等式组的共轭梯度法

第101页，共130页，2023年，2月20日，星期四因此，在沿d个(对于增广空间则为d+1个)互为共轭的向量进行一维搜索后，有可能达不到准则函数的最小值，即算法经过d(或d+1)步可能不收敛，这时就要重新开始计算，若用r表示重新开始的周期，则r=d(或d+1)。由于式定义的准则函数不是一个二次正定函数，而是一个分段二次正定函数，4.4.1解线性不等式组的共轭梯度法

第102页，共130页，2023年，2月20日，星期四在任意点，的负梯度方向可表示为4.4.1解线性不等式组的共轭梯度法

令第103页，共130页，2023年，2月20日，星期四这种算法的具体步骤如下：用k表示迭代步数，用表示满足于的不等式的数目，表示最优解。⒈置k=0，并任意给定初始权向量，计算和。

如果，则令然后继续。

4.4.1解线性不等式组的共轭梯度法

⒉如果，则令，停止；如果，则令，停止；否则继续。第104页，共130页，2023年，2月20日，星期四⒊计算gk。如果gk=0，则停止；否则计算，然后继续。

⒋求θk。如果k为r的整数倍，则令θk=0；否则令θk=1，并计算Sk表示第k次搜索时的梯度下降方向。若表示对的第一次逼近，则。可以证明，由上述表达式所产生的S1，S2，…，对于二次函数中的正定矩阵是互为共轭的。4.4.1解线性不等式组的共轭梯度法

第105页，共130页，2023年，2月20日，星期四⒌寻找最佳步长vk，即计算使取极小值时的v。

⒍令，并计算。

⒎令k=k+1，转向步骤2。

4.4.1解线性不等式组的共轭梯度法

第106页，共130页，2023年，2月20日，星期四Nagaraja和Krishna证明，对于表示的分段二次函数，在的一致条件下，上述算法可以在有限步内使序列收敛于最优解。4.4.1解线性不等式组的共轭梯度法

而在不一致条件下，只要适当的选择b，使在的唯一极小点上，有，i=1，2，…，N第107页，共130页，2023年，2月20日，星期四则该算法产生的序列{a}也在有限步内收敛于a*。对于表示的准则函数，在不等式组不一致的情况下，对某些样本，可能存在因此就产生了一个阈值问题。这时，由于aTyi>0，yi应被正确分类；但又由于aTyi<bi

，所以在算法中是按错分类处理的。故提出下面的补充算法。4.4.1解线性不等式组的共轭梯度法

第108页，共130页，2023年，2月20日，星期四如果在式中，假定b=0，那么准则函数为上述算法可以使上式中的Jq1(a)极小化，在一致的情况下Y(a)>0收敛于的解a*。在不一致情况下，由于Jq1(a)是严格的凸函数，其唯一极小点是a=0，而且有4.4.1解线性不等式组的共轭梯度法

第109页，共130页，2023年，2月20日，星期四因此，aTyi≠bi(i=1，2，…，N)的条件不成立，所以得不到解向量a*。4.4.1解线性不等式组的共轭梯度法

作为准则函数来解决上述问题。显然，这时存在下列关系：

第110页，共130页，2023年，2月20日，星期四也就是说，使最小，同在终止条件和下使最小是等价的。这时需要将上述算法的步骤1和4改变如下：4.4.1解线性不等式组的共轭梯度法

⑴通过原有算法得到一个收敛点，记为，并以此作为补充算法的起点。⑷计算和，并且继续。第111页，共130页，2023年，2月20日，星期四可以证明，这样得到的Sk仍然是的下降方向。同时可以证明，假使Ya>0是不一致的，且在求Jq1(a)最小值的过程中用步骤⑷代替原算法的步骤4，若所得的序列{a}是有限的，则序列的最后一个元素就相当于F(a)的一个局部最小值的解。4.4.1解线性不等式组的共轭梯度法

第112页，共130页，2023年，2月20日，星期四若序列是无限的，则它趋向于F(a)的一个局部最小值的解。在进行上述计算时，由于我们使用原算法的收敛点as

作为起始点，它常常是全局最优解F(a)的一个很好的逼近，故可以得到的全局最优解。4.4.1解线性不等式组的共轭梯度法

第113页，共130页，2023年，2月20日，星期四4.4.2解线性不等式组的搜索法考虑齐次线性不等式组其中矩阵为规范化增广样本矩阵，每一行yi代表一个样本，N为样本数，为yi的维数。且有第114页，共130页，2023年，2月20日，星期四式中

实际上是所满足的不等式的数目。称之为最小错分样本数准则2。使Jq2(a)取最大值的a就是要求的解a*。现在定义另一种形式的最小错分样本数准则如下：

4.4.2解线性不等式组的搜索法

第115页，共130页，2023年，2月20日，星期四因此，N个样本向量所建立的超平面把权空间划分成为凸多棱锥的有限集合，每个锥C都由有限个支撑超平面所组成。对于每个yi，方程yia=0在权空间中建立了一个超平面Hi，而且所有超平面都通过原点。组成锥的一部分超平面，或超平面的截取部分，称为锥的“前沿”，欧氏空间Ed中个超平面的交叫做锥的棱。4.4.2解线性不等式组的搜索法

第116页，共130页，2023年，2月20日，星期四图4.10示出三维凸多棱锥及其前沿和棱的一个例子。C+C－α+∈C+α－∈C－原点前沿棱图4.10而且某个锥C中的任何权向量对样本集的划分都是相同的，或者说，某个锥中的所有权向量所满足的不等式的数目是相同的。锥C中的每一个点，都对应一个权向量a4.4.2解线性不等式组的搜索法

第117页，共130页，2023年，2月20日，星期四如果某个锥C中的任何权向量都能使上式的准则函数为最大，那么就称这个锥为最小错误锥，记为C*。这样，求使最多数目的不等式得到满足的权向量的问题，就转化为寻找一个或多个最小错误锥C*的问题了。由于对于每个C∈Ed，存在着对称反射，即维权向量和所产生的分类情况恰好相反，所以，如果对于某个存在4.4.2解线性不等式组的搜索法

第118页，共130页，2023年，2月20日，星期四其中则必有。由于我们只关心最小错误锥，因此，我们只限于研究使锥就可以了。如果遇到的情况，则用代替。的那些4.4.2解线性不等式组的搜索法

第119