线性判别函数学习教案

1、会计学1第一页，共92页。1,2,(.,)TnXx xx12,.,nx xxnn第1页/共92页第二页，共92页。,21NXXX第2页/共92页第三页，共92页。1x2x0（二维两类别模式(msh)的例子）第3页/共92页第四页，共92页。二维三类别(libi)模式的例子123边界2x1x第4页/共92页第五页，共92页。第5页/共92页第六页，共92页。0)(Xg0)(Xg0)(Xg第6页/共92页第七页，共92页。代入 判别(pnbi)第7页/共92页第八页，共92页。)(Xg第8页/共92页第九页，共92页。1 1220().,nng Xw xw xw xw01()nkkkg Xw xw

2、kw0w)(Xg第9页/共92页第十页，共92页。2. 线性判别函数的确定方法(fngf)设有已知类别的两类别样本集，分布如下： 1x2x0第10页/共92页第十一页，共92页。线性判别函数可以(ky)写成：参数 决定了 的方向和位置02211)(wxwxwXg021,www)(Xg1x2x0第11页/共92页第十二页，共92页。021,www)(Xg0)(Xg0)(Xg第12页/共92页第十三页，共92页。021,www)(Xg第13页/共92页第十四页，共92页。3.线性判别函数的一般表示 对于n维模式向量 ，其线性判别函数是所有(suyu)模式特征的线性组合，即 可以写成其中， 称为权向

3、量。TnxxxX),(2102211)(wxwxwxwXgnn0)(wXWXgTTnwwwW),(21第14页/共92页第十五页，共92页。4. 在向量空间的几何表示 取 作为决策面。 如果两个向量 和 都在决策面上(min shn)，则有： 或写成 由于 和 是决策面上(min shn)的任意两点，所以 也是在决策面上(min shn)的任意向量。 表明了什么？0)(wXWXgT()0g X 1X2X1020TTW XwW Xw12() 0TW XX12()XX1X2X12() 0TW XX第15页/共92页第十六页，共92页。 两个n维向量相互正交的充要条件是两向量的内积为零。即 所以,

4、表明(biomng): 权向量和决策面上的任一向量正交。所以权向量的方向就是决策面的法线方向。0),(BABAT12() 0TW XX第16页/共92页第十七页，共92页。 在两维模式下，决策面 把模式空间分成两个子空间，分别(fnbi)是对 类的决策域 和对 类的决策域 。 如果我们规定： 在 中， ；在 中， ，决策面的法向量的方向指向 。 1x2x0WX0)(Xg1R2R0)(Xg0)(XgHH121R2RX1R0)(Xg2R0)(Xg1R第17页/共92页第十八页，共92页。 1x2x0WX0)(Xg1R2R0)(Xg0)(XgHpX第18页/共92页第十九页，共92页。我们可以(ky

5、)把向量 表示为： 待求的距离 决策面 上一点 与 有什么样的关系? X|PWXXWH()g X第19页/共92页第二十页，共92页。()|g XWWWWXgWWWWXWWWWXWwXWXgpTpTpTT2000)()()()g XX第20页/共92页第二十一页，共92页。同理，可以得出：从原点到决策面 的距离为 。 如果 ，原点在 的正面； 如果 ，原点在 的反面(fnmin)； 如果 ，判别函数有齐次形式 决策面通过原点。0|wW00w H00w H00w HXWXgT)(第21页/共92页第二十二页，共92页。二类模式的线性分类器的决策法则是： 如果 则决策 ，即把 归到 类； 如果 则

6、决策 ，即把 归到 类；对于线性判别函数，关键的问题(wnt)是求如何求？ ()0,g X X()0,g X X1212TnwwwW),(21第22页/共92页第二十三页，共92页。1.感知准则函数 由前面介绍的知识，我们知道，对于一组两类别样本(yngbn)集：我们可以设线性判别函数为：决策面方程为：即 ,21NXXX0)(wXWXgT()0g X 00wXWT第23页/共92页第二十四页，共92页。 求得权向量 ，就可确定决策面方程。 由数学知识，知 的齐次形式比较容易。能否将 变换(binhun)成齐次形式呢？ 令 ，则， n维X空间 （n+1）维Y空间 Y称为增广模式向量，A称为增广权

7、向量 W00 wXWT0)(wXWXgTTnwwwwA),(210TnxxxY), 1 (210)(wXWXgTYAYgT)(第24页/共92页第二十五页，共92页。 经过这样的变换，求解的问题就变为：设有一组两类模式的增广模式向量样本集，利用(lyng)这些样本确定一个线性判别函数的权向量 ，使 能够对 正确分类。,21NYYYYAYgT)(A0)(YgiY第25页/共92页第二十六页，共92页。训练规则为：对于属于(shy) 类的所有样本，有: 对于属于(shy) 类的所有样本，有: 注意到 和能否使 ？ 在属于(shy) 类的样本前加上负号，则120iTYA1,2, 1Ni0jTYA2,

8、2, 1Nj0iTYA0jTYA0,jiTYA20)(jTYA第26页/共92页第二十七页，共92页。这样处理后，问题变为：求使对于所有训练样本都满足： ， 的权向量如何求 ？ 是一个(y )线性不等式组，而 是 维的，样本数量为 ，一般 比 大的多， 这样， 的解不唯一。 0iTYANi, 2 , 1AA0iTYAY1nNNn0iTYA第27页/共92页第二十八页，共92页。 为了解线性不等式组 ，需要构造一个准则函数，并希望构造的准则函数有极值的形式。 是由于使用权向量(xingling) 而被误分类的样本集合。当一个样本 被误分类时，就有 ,所以 。仅当 时， 达到最小值。 0TiA Y

9、 ()()ATpYyJAA YAyAY0TA Y ( ) 0pJ A Ay ( )pJA第28页/共92页第二十九页，共92页。我们称为感知(gnzh)准则函数。有了准则函数之后，我们就可以用最优化方法寻找使准则函数达到极小值的解权向量 。 如何求 ？AA( )()ATpYyJAA Y第29页/共92页第三十页，共92页。2. 梯度(t d)下降法 梯度的定义 梯度是函数(hnsh) 的一阶偏导数组成的向量, 记为 二元函数(hnsh)的等值线 定义:坐标面上函数(hnsh)相等的各点的连线叫等值线,也称等高线。 f x 12,.,nfffffxxxxx第30页/共92页第三十一页，共92页。

10、 函数 为不同值时，得到一系列的等值线，构成 的等值线族 。 在极值处的等值线聚成一点，并位于等值线的中心，当该中心为极小值时，离开它越远(yu yun)， 值越大，反之，若该中心为极大值时，离开它越远(yu yun)， 的值越小。 fx, , ,a b c d f x f x f x第31页/共92页第三十二页，共92页。 梯度(t d)方向 由梯度(t d)的定义知， 梯度(t d)的方向就是函数的法线的方向。1x2xTxfxfXf21,)(第32页/共92页第三十三页，共92页。第33页/共92页第三十四页，共92页。梯度下降法的基本思想：函数(hnsh) 在某点 的梯度 是一个向量，它

11、的方向与过点 的等量面 的法线方向重合，指向 增加的一方，是准则函数(hnsh)变化率最大的方向。反之，负梯度的方向则是函数(hnsh) 减少的最快的方向。所以在求准则函数(hnsh) 的极小值时，沿负梯度方向搜索有可能最快的找到最小值。 ( )pJAkA()pkG JAkA()pkJAC()pkJA( )pJA( )pJA第34页/共92页第三十五页，共92页。梯度下降法的实现： 先任意选择一个初始的权向量 ，计算 上的梯度 ，从 出发在最陡方向(fngxing)（即负梯度方向(fngxing)）上移动一个距离以得到下一个权向量 。可采用下面的迭代方法从 推出 。 比例因子，叫做步长或增量

12、因为 的第 个梯度分量是 。 1A1A1()pG JA1A2AkA1kA1()kkkpkAAG JA( )pJAj()pjJAA( )()ApYyG JAY 第35页/共92页第三十六页，共92页。 所以，可得到梯度下降法的迭代公式： 当第 步迭代用权向量 来分类时被误分类的样本集合 这种寻找(xnzho)解权向量的梯度下降法简述如下: 把第 次的权向量加上被误分类的样本的和与某个常数 的乘积，就得到第 次的权向量。1AkkkkYyAAYKkAKk(1)K 第36页/共92页第三十七页，共92页。kAkAykA第37页/共92页第三十八页，共92页。0)(wXWXgTYAYgT)()()ATp

13、YyJAA Y1AkkkkYyAAY1()kkkpkAAG JA第38页/共92页第三十九页，共92页。2.3 固定增量(zn lin)算法及其收敛性 针对(zhndu)梯度下降法的缺点，作以下两点改变，得到固定增量算法： kAkAy（1）把全部样本看作是一个序列，每当前一步迭代的权向量把某个(mu )样本错误分类时，就对这一个权向量作一次修正，而不是等当前权向量 对全部样本计算后再找出错分类样本集 去进行修改。（2）考虑每次迭代时 保持不变。kAkkAy第39页/共92页第四十页，共92页。二类模式下用固定增量法求解权向量： 设已知二类模式的样本集 和 ，这些样本都已被变成增广模式向量的形式

14、，要求用固定增量的方法决定一个超平面 ，使它能正确(zhngqu)划分样本集 和 。 开 始 时 可 以 任 意 假 定 和 位于决策面的哪一边。同样可以任意选择广义向量 的初始值 。 然后把训练集 和 中的增广模式向量 依次取出，计算 与 的内积 。*1R*2R0TA Y *1R*2R*1R*2RA1A*1R*2RYAYTA Y第40页/共92页第四十一页，共92页。假定 在 的正面， 在它的反面权向量 用以下规则调整：如果 ，而 ，则用 代替 ；如果 ，而 ，则用 代替 ；如果 ，而 ，则 保持不变。如果 ，而 ，则 保持不变。 把属于 和 的全部模式都用上述方法处理一遍，称为一次迭代。

15、这个算法重复(chngf)执行，直至权向量 不再变化，则 ，即求得解权向量 。 A*1YRAYA*2YR0TA Y A YA*1YR0TA Y A*2YR0TA Y A*1R0TA Y *2R*1R*2RA*AA0TA Y *A第41页/共92页第四十二页，共92页。 2.7 Fisher 线性判别函数 在应用统计方法进行模式识别(m sh sh bi)时，许多问题涉及维数，在低维空间行得通的方法，往往在高维空间行不通。因此，发展了一些降低特征空间维数的方法，Fisher线性判别函数就是其中之一。 在介绍Fisher线性判别函数之前，先补充介绍要用到的Lagrange乘子法一种带等式约束的函数

16、极值求解方法。 第42页/共92页第四十三页，共92页。Lagrange乘子法一. 等式约束最优化问题(wnt)二. Lagrange乘子的概念 0mins.t. f x数学模型 g xf (x1,x2)的等值线x2x1s是g (x1,x2)=0的法线方向g (x1,x2)=0第43页/共92页第四十四页，共92页。极值(j zh)点必须满足两个条件:1.目标函数 沿约束曲线 的切线方向 的方向导数 , 即2.约束函数 沿约束曲线 的切线 方向 的方向导数 , 即12,f x x12,0g x xs0fs12120 xxfffsxsxs12,g x x12,0g x xs0gs12120 xx

17、gggsxsxs第44页/共92页第四十五页，共92页。比较上述(shngsh)两式可以得到:令可得: 为待定系数,解这个联立 方程可以求出 , 为问题的极小点， 极小值为 。1122fgfgxxxx1122fgfgxxxx11221200,0fgxxfgxxg xx*12,x x*12,xx*12,f x x第45页/共92页第四十六页，共92页。 设 对各变量分别求偏导数并令其等于0,可得到： 实际上是求函数 的极值(j zh)这个形式与前述形式一样。121212,L x xf x xg x x1112221200,0LfgxxxLfgxxxLg x x12,L xx第46页/共92页第四

18、十七页，共92页。 三、二维情况下的Lagrange乘子法 对于等式约束优化函数 构造Lagrange函数： 使 达到(d do)极小值， 称为Lagrange乘子。 用Lagrange乘子法可以将等式约束优化问题转化为无约束优化问题。min( ). .( )0f xstg x ,L xf xg x,L x第47页/共92页第四十八页，共92页。四、对于 维的情况 数学模型 首先(shuxin)由情况引入Lagrange系数 ，构造Lagrange函数： min. .01,2,.,nif xxEst gxim12,.,m 121 122, ,.,.mmmL xf xg xg xgx 1miii

19、f xgxn第48页/共92页第四十九页，共92页。 Fisher方法的基本思想(sxing)： 把 维空间的所有模式投影到一条过原点的直线上，就可以把维数压缩到1。 过原点的直线有无数条，投影到那条直线好呢？dx1x2第49页/共92页第五十页，共92页。 我们的目标就是找到这样一条直线，使得模式样本在这条直线上的投影最有利于分类。 设给定(i dn)两类模式样本集， 和 ， 它们各有 和 个 维样本。设 为这条直线正方向的单位向量， 。将样本集中的样本向直线投影，相应地得到集合 和 。每个 就是 在单位向量 上的投影。 有： 这样，就得到了一个一维样本集合，样本数量为 1n2ndW1WW1

20、X2X1Y2YiYyiXxXWyT21nnN第50页/共92页第五十一页，共92页。XWyTWW第51页/共92页第五十二页，共92页。imiXxiixnm12 , 1iTiXxiimxmxSi)(21SSSw2 , 1i第52页/共92页第五十三页，共92页。TBmmmmS)(2121第53页/共92页第五十四页，共92页。2 , 1i2 , 1i*imiyyiiynm1*2*2*)(iYyiimyS2*22*1*SSSw第54页/共92页第五十五页，共92页。2*12*2*212()mmJ WSS)(*2*1mm 2*22*1*SSSw第55页/共92页第五十六页，共92页。)(WJWWW

21、)(WJ*11iiTTiiy yx xiimyW XW mnn第56页/共92页第五十七页，共92页。WSWWmmmmWmmWmmWmWmWmWmWmWmWmmBTTTTTTTTTTT)()()()(2121212121212212*2*1第57页/共92页第五十八页，共92页。WSWWmxmxWWmxmxWmWxWmySiTTiXxiTTiiXxTiTXxTiYyiiiii)()()()(22*2*WSWWSSWWSWWSWSSWTTTT)(21212*22*1第58页/共92页第五十九页，共92页。因此，准则函数 可改写为： (2.43)这就是Rayleigh比，它有如下性质：（1） 是一

22、个实数。（2） 的极值与大小无关，只与 的方向有关(yugun)。 因此， 可以用Lagrange乘数法求极值。由性质(2)，可令式(2.43)分母为非零常数，即()TBTWW S WJ WW S W()J W()(),J WJ aWa( )J WW0TWW S WC()J W第59页/共92页第六十页，共92页。构造(guzo)Lagrange函数 极大值的条件为：即 如果 非奇异，左乘 ，则有 解这个式子，就是求矩阵 的本征值。 (, )()TTBWL WW S WCW S W(, )220BWL WS WS WW0BWS WS WBWS WS W1WS1WBSS WWWSBWSS1第60

23、页/共92页第六十一页，共92页。考虑(kol)到我们求解问题的特殊性（只确定方向 ），其中 是常数，所以 总是在 的方向上。从而 所以略去比例因子 ，它不影响直线的方向，得： 121212()()()TBS WmmmmWmmR12()TRmmWBS W12()mm112()WWSmm R112()WRWSmmR112()WWSmm第61页/共92页第六十二页，共92页。 这就是使准则函数 极大的解。 就是使模式样本的投影(tuyng)在类间最分散，类内最集中的最优解。有了 后，得 就可将各样本由维空间投影(tuyng)到一维空间，即直线上，变成一维样本，它们给出较好的分类结果。 此类方法有一

24、定的局限性：只对准则函数最优；没有利用样本的分布信息，错误概率不能达到最小。 ()J WWW,TiiyW X yy Xx第62页/共92页第六十三页，共92页。2.8 支持(zhch)向量机 Support Vector Machine SVM 回顾：用线性判别(pnbi)函数方法解决分类问题的方法1.思路（1）训练样本集 特征空间划分 决策面 线性判别(pnbi)函数（2）待识别模式 判别(pnbi)2.问题核心： 求线性判别(pnbi)函数的权向量3.求解方法：感知准则函数，梯度下降法，固定增量法求得权向量=确定了特征空间的两类分界面（决策面） 第63页/共92页第六十四页，共92页。一.

25、 最优分界面 从线性判别函数的讨论中，我们已经知道，对于(duy)线性可分的两类样本，总可以找到一个分界面，将两类样本正确分类，而且，这样的分界面不是唯一的。第64页/共92页第六十五页，共92页。1x2x0H1和H2都可以将两类训练样本正确分类(fn li)，但是，对于训练样本以外的样本，以哪个作为分界面，分类(fn li)效果更好呢？H1H2第65页/共92页第六十六页，共92页。第66页/共92页第六十七页，共92页。1x2x0 H1是两类各自(gz)最近样本距离相同的分界面， H2也是两类各自(gz)最近样本距离相同的分界面.H1H2第67页/共92页第六十八页，共92页。第68页/共

26、92页第六十九页，共92页。1XCXg)(2XCXg)(C1X2X0)(Xg0)(Xg第69页/共92页第七十页，共92页。为了方便，训练样本集的样本用二元对来表示(biosh)： 其中 和 分别是样本模式向量和它的相应的类别表示(biosh)， 假定当 时， 。而当 时 。 设给定的有穷训练样本集可以被超平面 正确分开。 使每类离开分界超平面最近的样本向量与超平面之间的距离最大，位于间隔中间的超平面是最优的。niXR1, 1iy 00TW Xw1iy 1iy 1iX2iX),( ,),(),(2211nlyXyXyX第70页/共92页第七十一页，共92页。WwXWWXgT0)(0)(wXWX

27、gTW0wWXH第71页/共92页第七十二页，共92页。1TiW Xb W0w0wWXW11TiW Xb 1iy 1iy 1,1,2,.,Tiiy W Xbil第72页/共92页第七十三页，共92页。W2W2W2W1bXWyiTi第73页/共92页第七十四页，共92页。 设目标函数为：将寻找最优分界面问题转化为有约束(yush)优化问题： 如何求解？ 221)(WW )(2121)(2WWWWT1,1,2,.,Tiiy W Xbilmin. .ts第74页/共92页第七十五页，共92页。 构造(guzo)Lagrange函数： 其中 为Lagrange乘子，1)(21),(1iiTliiTyb

28、XWWWbWLi0i第75页/共92页第七十六页，共92页。 达到极值的必要条件为： (1) , 得(2) , 得 而对于最优分界面(jimin)，解 必须满足：(1)(2) 最优分界面(jimin)的解权向量是训练样本集中模式向量的线性组合. (, , )0L W b ab10liiiiWX y(, , )0L W b aW10liiiy0i0010,0,1,2,.,liiiiyil001liiiiWyX),(bWL第76页/共92页第七十七页，共92页。 对于约束条件,等号在支持向量下才成立，也就是说，只有支持向量可以在 的展开中具有非零系数 ，因此(ync)有 其中 是支持向量集。 如何

29、知道哪些样本是支持向量呢? 0W0i00iiiSWyXS第77页/共92页第七十八页，共92页。求最优分类(fn li)超平面问题： 1,112llTiijijijii jWy yX X1)(21),(1iiTliiTybXWWWbWL1,1,2,.,Tiiy W Xbil0imax等价转换对偶(du u)问题第78页/共92页第七十九页，共92页。i0b0W0W0b00iiiSWyX 0001* 1*12TTbW XW X * 1X * 1X第79页/共92页第八十页，共92页。2TX0 , 01TX0 , 1 2TX0 , 23TX2 , 041第80页/共92页第八十一页，共92页。0jTiXX122XXT22232XXT322042XXT00322433XXT234043XXT0444XXT244)(21)(1,1jTijijnjiiniiXXyyW第81页/共92