下载文档原格式
![[工学]第5章 线性判别函数](https://uimg.taocdn.com/b16c393b227916888486d7dd.webp)
分段线性函数分段线性函数（PiecewiseLinearFunction）是一种重要的数学函数，它是将函数定义域分割为几个有界区间，在每个区间上均为定值线性函数的线性函数。
它可以表示有限个线性函数的连接，作为这些线性函数的求和。
由于其简单的表达形式和特殊的性质，分段线性函数在数学分析、概率论与统计学、统计优化等领域有着广泛的应用。
一般来说，分段线性函数定义为具有 m 个分段线性子函数的函数，并将函数定义域分为 m+1 个有界区间，其中，第 i 个子函数定义的定义域f[i]的范围是 [a_i, b_i]。
它们的关系式可以写成：f(x)={f_1(x),x∈[a_1,b_1]f_2(x),x∈[a_2,b_2]……f_m(x),x∈[a_m,b_m]分段线性函数的定义域的表示与区间的边界密切相关，它们的数量与形式取决于给定的函数表达式。
在每个区间上，分段线性函数是定义在它们每个区间上的线性函数，只有在这些区间边界处，函数可能改变其斜率，而整体函数自身仍然是连续的。
分段线性函数的特性可以通过很多例子来说明。
最简单的例子用两个分段函数来表示：f(x)={5x 『x<0』0 『0≤x<1』5-5x 『x≥1』此例子中，函数的定义域包含两个有界区间：[-∞, 0]和[0, 1]。
分段函数的一个重要应用是在优化问题中，可以用分段线性函数减少优化问题中的不确定性。
由于分段线性函数的有效性和简洁性，它在概率论的数学模型以及统计学的实际应用中具有重要意义。
分段线性函数可以用来表示一般概率分布中函数的不同表达形式，并由此可以用来分析和求解更复杂的问题。
此外，分段线性函数还可以用来表示连续函数的有限个连续区间。
在某些情况下，这样可以更有效的描述某个特定的函数，从而简化计算过程。
在报表分析中，分段线性函数也可以用来表示大量数据的定量化模型，通过引入分段变量，可以更加准确地拟合一个模型。
在进行实际计算时，由于分段线性函数不同区间上的参数计算存在一定的复杂性，因此常常需要采用一定的迭代算法来计算出分段参数，以便对函数进行拟合。
第5章：线性判别函数第一部分：计算与证明1． 有四个来自于两个类别的二维空间中的样本，其中第一类的两个样本为(1,4)T 和(2,3)T ，第二类的两个样本为(4,1)T 和(3,2)T 。
这里，上标T 表示向量转置。
假设初始的权向量a=(0,1)T ，且梯度更新步长ηk 固定为1。
试利用批处理感知器算法求解线性判别函数g(y)=a T y 的权向量。
解：首先对样本进行规范化处理。
将第二类样本更改为(4,1)T 和(3,2)T . 然后计算错分样本集：g(y 1) = (0,1)(1,4)T = 4 > 0 (正确) g(y 2) = (0,1)(2,3)T = 3 > 0 (正确) g(y 3) = (0,1)(-4,-1)T = -1 < 0 (错分) g(y 4) = (0,1)(-3,-2)T = -2 < 0 (错分) 所以错分样本集为Y={(-4,-1)T , (-3,-2)T }.接着，对错分样本集求和：(-4,-1)T +(-3,-2)T = (-7,-3)T第一次修正权向量a ，以完成一次梯度下降更新：a=(0,1)T + (-7,-3)T =(-7,-2)T 再次计算错分样本集：g(y 1) = (-7,-2)(1,4)T = -15 < 0 (错分) g(y 2) = (-7,-2)(2,3)T = -20 < 0 (错分) g(y 3) = (-7,-2)(-4,-1)T = 30 > 0 (正确) g(y 4) = (-7,-2)(-3,-2)T = 25 > 0 (正确) 所以错分样本集为Y={(1,4)T , (2,3)T }.接着，对错分样本集求和：(1,4)T +(2,3)T = (3,7)T第二次修正权向量a ，以完成二次梯度下降更新：a=(-7,-2)T + (3,7)T =(-4,5)T 再次计算错分样本集：g(y 1) = (-4,5)(1,4)T = 16 > 0 (正确) g(y 2) = (-4,5)(2,3)T = 7 > 0 (正确) g(y 3) = (-4,5)(-4,-1)T = 11 > 0 (正确) g(y 4) = (-4,5)(-3,-2)T = 2 > 0 (正确)此时，全部样本均被正确分类，算法结束，所得权向量a=(-4,5)T 。
第五章线性判别函数5.1 引言5.2 线性判别函数的一般形式5.3 广义线性判别函数5.4 多类问题的线性判别函数5.5 设计线性分类函数的主要步骤5.6 感知准则函数5.7 最小距离分类器5.8 最小误差准则函数第五章线性判别函数5.1引言Bayes 决策方法：已知先验概率类条件概率密度①样本估计未知参数②求后验概率③Bayes 决策分类结果{)(i P ω()i p x ω()i p x ω()i P x ω缺点:形式难确定，利用非参数方法估计分布样本大．因此，可利用样本集直接设计分类器。
()i p x ω给定某个判别函数类利用样本集判别函数的未知函数。
本章的基本思想：假定判别函数i=1, 2, 3,…利用样本估计若i=1, 2, 3,…则()0i Tii w x W x g +=i W 0i w ()()x g x g i i max =ix ω∈⇒⎧⎨⎩⎧⎪⎨⎪⎩最优：错误率，风险最小最优分类器简单次优：其他方法，准则函数最优求极值实现容易采用判别步骤：1. 线性函数（分界面－超平面）2. 非线性函数满足准则函数:几种常用准则函数的线性分类器设计方法准则函数：Fisher准则感知准则最小错分样本数准则最小平方误差准则最小错误率线性判别函数准则５.2线性判别函数的基本概念１. 一般形式其中样本向量权向量阈值权令()0Tg x W x w =+Td x x x x ],,[21L =12[,,]Td W w w w =L 0w ()()()x g x g x g 21−=如果()()()12120,0,0,,g x x g x x gx x ωωωω>∈<∈⎧=∈⎨⎩则则则或者拒绝()1,2,033,d dg x d d=⎧⎪=⎪=⇒⎨=⎪⎪>⎩点直线定义一个决策面，平面超平面()g x ⇒⇒当线性函数，决策面超平面2. 超平面的几何性质设都在决策面H上(H ——超平面)则有H ——把特征空间分成两部分⎩⎨⎧<>0)(0)(x g x g 2211R x R x ⇒∈⇒∈ωω21x x ，102012()0T TTW x w W x w W x x +=+−=W W H H ⊥—，是的法向量H H 正侧反侧线性判别函数+ g>0-g<0W0w WHρx 2x 1x ()g x W)(22ωR )(11ωR H:g=0的决策线—的决策线—2211ωωR R 21x x x −是坐标中任意一点x式中：Wx x rWρ=+x x Hr x HWWWρ−−−是在上的投影向量是到的垂直距离方向上的单位向量00()()TTTW W W g x W x r w W x w r r WW Wρρ=++=++=()0g x w r W∴==0w r W∴=若x为原点，则()g x w =从原点到超平面Ｈ的距离00000000w H w r w H W w H >⇒⎧⎪=⇒<⇒⎨⎪=⇒⎩原点在正侧原点在负侧通过原点用线性判别函数进行决策120()0()0R R w x H g x x H g x ⎧⇒⇒⎨⎩⇒⇒⇒>⎧⎨⇒<⎩超平面特征向量权向量确定超平面方向阈值确定超平面位置在正侧在负侧5.3广义线性判别函数考虑两类问题,设有一维样本空间X如果x<b 或x>a,则；b<x<a,则。
分段线性函数
分段线性函数是一种常见的数学函数，它将实数域上的一段区间映射到另一段区间，具有多个断点，每个断点对应一个直线段。
它可以用来简化和求解很多复杂的数学问题，广泛应用于工程计算和统计学中。
首先，我们来了解一下分段线性函数的定义和特点。
分段线性函数是一种函数，它在实数域上的一个区间内是一段直线，在另一个区间内又是另一段直线，它具有多个断点，每个断点对应一个直线段。
它的图像在不同的区间内具有不同的斜率，其斜率是恒定的，而且每一个断点都是函数的可导点。
其次，我们来谈谈分段线性函数的应用。
分段线性函数在工程计算中非常有用，可以用来简化复杂的问题，比如在建筑设计中，可以利用分段线性函数来计算建筑物的抗震性能。
在统计学中，也可以使用分段线性函数来进行数据分析，以更好地了解数据的特征和趋势。
最后，我们来看一下分段线性函数的求解方法。
分段线性函数的求解可以使用一般的求根法，如牛顿迭代法和二分法，也可以使用图解法，即将函数图形画出来，然后根据图形的特征，求出函数的值。
当然，还可以使用积分法，将函数求积分，从而求出函数的值。
总之，分段线性函数是一种常用的数学函数，它具有多个断点，每个断点对应一个直线段，可以用来简化和求解复杂的数学问题，广泛应用于工程计算和统计学中，其求解方法有一般的求根法，图解法和积分法。
【模式识别与机器学习】——3.3分段线性判别函数3.4模式空间和权空间出发点： 线性判别函数在进⾏分类决策时是最简单有效的，但在实际应⽤中，常常会出现不能⽤线性判别函数直接进⾏分类的情况。
采⽤⼴义线性判别函数的概念，可以通过增加维数来得到线性判别，但维数的⼤量增加会使在低维空间⾥在解析和计算上⾏得通的⽅法在⾼维空间遇到困难，增加计算的复杂性。
引⼊分段线性判别函数的判别过程，它⽐⼀般的线性判别函数的错误率⼩，但⼜⽐⾮线性判别函数简单。
图例： ⽤判别函数分类可⽤⼀个⼆次判别函数来分类也可⽤⼀个分段线性判别函数来逼近这个⼆次曲线分段线性判别函数的设计（1）采⽤最⼩距离分类的⽅法图例：分段线性分类设计3.4 模式空间和权空间模式空间： 对⼀个线性⽅程w1x1+w2x2+w3x3=0，它在三维空间(x1 x2 x3)中是⼀个平⾯⽅程式，w=(w1 w2 w3)T是⽅程的系数。
把w向量作为该平⾯的法线向量，则该线性⽅程决定的平⾯通过原点且与w垂直。
若x是⼆维的增⼴向量，此时x3=1，则在⾮增⼴的模式空间中即为{x1, x2 }⼆维坐标，判别函数是下列联⽴⽅程的解（a）增⼴向量决定的平⾯（b）⾮增⼴向量决定的直线权空间:若将⽅程x1w1+x2w2+w3=0绘在权向量w=(w1 w2 w3)T的三维空间中，则x=(x1 x2 1)T为⽅程的系数。
若以x向量作为法线向量，则该线性⽅程所决定的平⾯为通过原点且与法线向量垂直的平⾯，它同样将权空间划分为正、负两边。
在系数x不变的条件下，若w值落在法线向量离开平⾯的⼀边，则wTx>0，若w值落在法线向量射向平⾯的⼀边，则wTx <0。
权空间中判别界⾯的平⾯⽰意图。
线性判别函数5.1引言在第三章中我们假设概率密度函数的参数形式已知,于是可以使用训练样本来估计概率密度函数的参数值.在本章中,我们将直接假定判别函数的参数形式已知,而用训练的方法来估计判别函数的参数值.我们将介绍求解判别函数的各种算法,其中一部分基于统计方法,而另一些不是.这里都不要求知道有关的概率密度函数的确切的(参数)形式,从这种意义上来说,它们都属于非参数化的方法.在这一章中,我们将关注以下形式的判别函数:它们或者是X的各个分量的线性函数,或者是关于以X为自变量的某些函数的线性函数.线性判别函数具有许多优良的特性,因而便于进行分析.就像我们在第二章看到的一样,如果内在的概率密度函数恰当的话,那么采用线性判别函数是最优的,比如通过适当的选择特征提取方法,可以使得各个高斯函数具有相等的协方差矩阵.即使它们不是最优的,我们也愿意牺牲一些分类准确率,以换取处理简便的优点.线性判别函数的计算是相当容易的,另外,当信息比较缺乏时,线性分类器对处于最初的.尝试阶段的分类器来说也是很有吸引力的选择.它们所展示的一些非常重要的原理在第6章的神经网络中将得到更充分的应用.寻找线性差别函数的问题将被形式为极小化准则函数的问题.以分类为目的的准则函数可以是样本风险,或者是训练误差,即对训练样本集进行分类所引起的平均损失.但在这里我们必须强调的是:尽管这个准则是很有吸引力的,但它却有很多的问题.我们的目标是能够对新的样本进行分类,但一个小的训练误差并不能保证测试误差同样的小-------这是一个吸引人而又非常微妙的问题,我们将在第9章中进一步论述这个问题.这里我们将看到,准确的计算极小风险判别函数通常是困难的,因此我们将考查一些有关的更易于分析的准则函数.我们的注意力将在很大程度上放在收敛性用各种应用于极小化准则函数的梯度下降法的计算复杂度上,它们当中一些方法的是很相似的,这使得清晰地保持它们之间的不同变得困难,因此,我们在后面的章节里会作出总结.5.2线性判别函数的判定面一个判别函数是指X的各个分量的线性组合而成的函数g(x)=w’x+w0 (1)这里W是权向量,w0被称为阈值权或偏置.和我们在第二章所看到的一样,一般情况下有C个这样的判别函数,分别对应C类的一类.我们在后面将讨论这样的情况,但首先考虑中人两个类别的简单情况.5.2.1两类情况对具有式(1)形式的判别函数的一个两类线性分类器来说,要求实现以下判定规则:如果G(x)>0则判定w1,如果g(x)<0,那么x可以被随意归到任意一类,但是在本章我们将它们归为未定义的.图5-1给出了一个典型的系统实现结构,是第二章所讨论的典型的模式识别系统结构的一个例子.图5-1一个简单线性分类器,有d个输入的单元,每个对应一个输入向量在各维上的分量值.每个输入特征值xi被乘以它对应的权wi, 输出单元为这些乘积的和∑wixi.因此这d个输入单元都是线性的,产生的是它对应的特征的值.惟一的一个偏差单元总是产生常数 1.0.如果w’x+w0>0的话,输出单元输出a+1,反之为a-1方程g(x)=0定义了一个判定面,它把归类于w1的点与归类于w2的眯分开来.当g(x)是线性的,这个平面被称为超平面.如果x1和x2都在判定面上,则w’x1+w0=w’x2+w0或W’(x1-x2)=0这表明,w和超平面上的任意向量正交.通常,一个超平面H将特征空间分成两个半空间,即对应于W1类的决策域R1和对应于W2的决策域R2.因为当X在R1中时,g(x)>0,所以判定面的法向量W指向R1,因此,有时称R1中的任何X在H的”正侧”,相应地,称R2中的任何向量在H的负侧.判别函数g(x)是特征空间中某点X到超平面的距离的一种代数度量.或许这一点最容易从表达式X=xp+r(w/IIwII)看出来,这里的XP是X在H上的投影向量,r是相应的算术距离------如果为正,表示X在H的正侧;如果为负,表示X在H的负侧.于是,由于g(xp)=0,有g(x)=w’x+w0=rIIwII或R=g(X)/IiwII特别,从原点到H的距离为W0/IiwII.如果W0>0表明原点在H的正侧,w0<0表明原点在H的负侧.如果W0=0,那么g(x)有齐次形式w’x,说明超平面H通过原点.图5---2对这些代数结果给出了几何解释.总之,线性判别函数利用一个超平面判定面把特征空间分割成两个区域.超平面的方向由法向量W确定,它的位置由阈值权W0确定.判别函数g(x)正比于x点到超平面的代数距离(带正负号).当X在H正侧时,g(x)>0,在负侧时,g(x)<0.5.2.2多类的情况利用线性判别函数设计多类分类器有多种方法,例如,可以把C类问题转化为C个两类问题,其中第I个问题是用线性判别函数把属于WI类的点与不属于W1类的分开.更复杂一些的方法是用c(c-1)/2个线性判别函数,把样本分为C个类别,每个线性判别函数只对其中的两个类别分类,如图5-3所示.这两种方法都会产生如无法确定其类型的区域.为此,我们采用在第二章采用的方法,通过定义C个判别函数Gt(x)=wt’xt+wi0 i=1......c (2)5.4二类线性可分的情况假设我们在一个包含N个样本的集合y1,y2,……yn,一些标记为w1,另一些标记为w2.我们希望用这样的样本确定一个判别函数g(x)=a’y的权向量a.假设我们有理由相信存在一个解,它产生错误的概率非常小.那么一个很合理的想法是寻找一个能将所有这些样本正确分类的权向量.如果这个权向量存在,这些样本就被称为线性可分的.对于一个样本yi,如果有a’yi>0就标记为w1,如果小于0,就标记为w2.这样,我们可以用一种规范化操作来简化二类样本的训练过程,也就是说对属于W2的样本,用负号表示而不是标记W2.有了规范化,我们可以忘掉这些标记,而寻找一个对所有样本都有a’yi>0的权向量a.这样的向量被称为分离向量,更正规的说法是解向量.5.4.1几何解释和术语求解权向量的过程可认为是确定权空间中的一点.每个样本都对解向量的可能位置给出限制.等式a’yi=0确定一个穿过权空间原点的超平面,yi为其法向量.解向量-----如果存在的话,必须在每个超平面的正侧.也就是说,解向里如果存在,必在N个正半空间的交叠区,而且该区中的任意向量都是解向量.我们称这样的区域为解区域,注意不要将它和任何特定类对应的特征空间的判决区域相混淆.对于二维问题.我们用图5.8说明解区域的情况,其中包含了规范化样本和未规范化样本.从以上讨论可知,解向量如果存在的话,通常不是惟一的.有许多方法引入一些附加要求来对解向量进行限制.一种可能的方法是找到一个单位长度的权向量,它使得从样本到分类平面最小距离达到最大.另一种方法是在所有I中寻找满足a’yi>=b的有最小长度的权向量,这里的b是被称为边沿裕量或间隔的正常数.正如图5—9所示的,新的解区域位于由a’yi>=b>0所产生的正半空间的交叠区,它是在原解区之中,且它和原解区边界被隔开的距离为b/IIyiII.我们一般试图在解区域的中间位置来寻找解向量,这背后的动机是一个自然的信念,认为这样的解更能将新测试样本正确地分类.但在大多数情况下,我们对解区域中的任何解都感到满意.而主要关心的是任何一种可行的递归算法,只是它的递归过程能够不收敛到边界点上即可.这个问题可通过引入一个边沿裕量来解决,比如要求对所有的I都有a’yi>=b>0.5.7不可分的情况当样本是线性可分的时候,感知器法和松弛法给我我们许多寻找分类向量的简单方法.这些都被称为误差校正方法,这是因为它们只在遇到错分样本时才对权向量进行校正.它们对可分问题的成功之处在于对求得一个无解进行坚持不懈的摸索.实际上只有在有理由认为最优线性判别函数的误差率比较低的时候才会考虑使用这些方法.当然,即使对训练样本的分离向量已经找到,也不能保证它对独立的测试数据都能很好地分类.我们感觉有种直觉印象,它表明数目少于2d的样本集很可能是线性可分的----我们会在第九章再次考察这一点.因此有人可能会想到:对设计好的样本集使用多次,综合多种因素来获得分类器,并由此确保它在训练和实际数据上的分类性能是相同的.不幸的是,如果使用非常多的数据的话,它们往往不是线性可分的.这样,当样本不是线性可分时了解误差校正方法的效果如何就变得非常重要了.由于不存在可以将不可分数据集中的样本都能正确分类的权向量(由定义可知),显然误差校正过程永远不会结束.这些算法都将产生一个无限的权向量序列,所有的成员都有可能或者不可能得到有用的解.在一些特殊的例子中,这些算法在不可分的情况下的行为被全面的研究过.比如,固定增量算法得到的权向量的幅值波动的趋势.从理论的观点来看,如果样本的分量是整数值的话,固定增量算法将产生一个有限状态过程.如果校正过程停在任意一个状态上,权向量可能正处于,也可能不处于好的状态上.如果对校正算法得到的权向量求均值的话,就可以降低偶然选到处于不好状态上的坏向量的风险.有许多类似的启发式规则被用于修改误差校正算法,并进行了实验研究.修改的目的是在不可分的问题中得到令人接受的结果,同时保持它对可分问题仍能正确分类的性质.最普通的想法是使用变增量Q(K),且当K趋向无穷大时Q(K)趋向0.Q(K)趋向0的速度是相当重要的.如果它太慢的话,得到的结果对那些使得集合为不可分的样本仍然敏感.如果太快,权向量在还没有得到最优结果的时候就收敛了.一种选择Q(K)的方法是今它为当前性能的函数,也即当性能提高的时候减小Q(K).另一种方法是选择Q(K)=Q(1)/K.当研究随机逼近技术的时候,我们发现后一种方法是一种类似问题的理论解.但在展开这个主题之前,我们先考一种在可分和不可分情况下都有很好性能的折中方法,它不再试图直接获取分离向量.本章小结本章给出了一些判别函数,它们都是某个参数集的线性函数,而这些参数一般被称为权系数.在所有两类样本集的情况下这些判别都能确定一个判定超平面,它可能是位于样本自身的原始特征空间中,也可能是位于原始特征通过一个非线性函数(通常是线性判别式)映射而得到的空间.从更广的角度看.感知器算法是一类技术是通过调整参数来提高与W1的样本的内积,而降低与W2的样本的内积.一个更通用的方法是构造准则函数进行梯度下降.不同的准则函数在计算复杂度和收敛性方面各有不同的优缺点,没有哪个方法说是比别的方法都好.我们也可以通过线性代数运算来直接求得权(参数).比如对小型问题采用伪逆的方法.在支持向量机中,输入被非线性函数映射到一个更高维的空间,最优超平面就是具有最大“间隔”(margin)的平面.支持向量就是用来确定间隔的(变换后的)样本,它们通常是那些最难被分类,却能给分类器提供最多信息的样本.分类器期望误差率的上界线性依赖于支持向量的期望个数.对多类问题,线性机产生了由一些部分超平面构成的判定面.为了证明多类算法的收敛性可先将它们转化成两类算法再用两类法的证明.单纯型算法用来寻找由(不等式)约束的一个线性函数的优化.它也能被用来训练线性分类器.线性判别函数虽然很有用,对任意的很具挑战性的模式识别问题却不有足够的通用性(比如那些包含多模的或非凸密度的问题),除非能找到一个适当的非线性映射(Q函数).这一章我们没有给出如何选择这些函数的原则,但我们会在第六章讲述这个主题.文献的历史评述因为线性判别函数是易于分析的,在这方面有极大量的文章,尽管它的内容有限而不值得有这么多的文章.历史上,所有这方面的工作都是从ronald A.Fisher(5)的经典论文开始的.文献9很好描述了线性判别函数在模式识别中的应用,它提出了最优化(最小风险)线性判别问题并建议采用适当的梯度下降从样本中求得解.然而,在不知道内在的分布时,我们对这些方法的适用程度的了解是很有限的,即使是有条件的分析也是很复杂的.用两类方法来设计多类分类器来自于文献16.Minsky和papert的感知器一书强有力地指出了线性分类器的弱点------但可以用我们将在第六章中学习的方法来解决.无差错情况下的Winnow算法10以及更一般情况下的后续工作在计算(机器)学习领域是非常有用,它们都允许导出收敛的界.虽然这些工作都是基于统计的,许多从其他观点出发的模式识别的文章出现在20世纪50年代末和60年代初.其中一种观点是神经网络的,每一个单独的神经无被建模成阈值元----即两类的线性机,这些工作都是从McCulloch和Pitts12的著名的论文开始的.。
