第05章 线性判别函数 模式识别课程 哈工大

1、第五章第五章 线性判别函数线性判别函数5.1 线性判别函数和判别界面线性判别函数和判别界面线性不可分情况线性不可分情况线性判别函数线性判别函数nx=(x1, x2, xd)t: 特征矢量；nw=(w1, w2, , wd)t: 权矢量；nw0：偏置(bias)。 0tgwxw x线性判别函数的增广形式线性判别函数的增广形式nx=(1, x1, x2, xd)t: 增广的特征矢量；na=(w0, w1, w2, , wd)t: 增广的权矢量； tgxa x两类问题线性判别准则两类问题线性判别准则 1020,0,0,tgwxxw xx拒识线性分类器的分类界面线性分类器的分类界面分类界面的几何解释分

2、类界面的几何解释1.线性分类界面H是d维空间中的一个超平面；2.分类界面将d维空间分成两部分，R1，R2分别属于两个类别；3.判别函数的权矢量w是一个垂直于分类界面H的矢量，其方向指向区域R1 ；4.偏置w0与原点到分类界面H的距离有关：00wr w多类问题（情况一）多类问题（情况一）n每一类模式可以用一个超平面与其它类别分开；n这种情况可以把c个类别的多类问题分解为c个两类问题解决，需要c个线性分类界面；n第i类与其它类别之间的判别函数： tiigxa x多类问题（情况一）分类界面多类问题（情况一）分类界面多类问题（情况一）判别规则多类问题（情况一）判别规则n若存在i，使得gi(x)0， g

3、j(x)0，ji，则判别x属于i类；n其它情况，拒识。多类问题（情况二）多类问题（情况二）n每两个类别之间可以用一个超平面分开；nc个类别的问题需要c(c-1)/2个线性分类界面；n第i类与第j类之间的判别函数为： ,tijijgxa xij多类问题（情况二）分类界面多类问题（情况二）分类界面多类问题（情况二）判别准则多类问题（情况二）判别准则n如果对任意ji ，有gij(x)0 ，则决策x属于i。 n其它情况，则拒识。多类问题（情况三）多类问题（情况三）n情况三是情况二的特例，不存在拒识区域。 多类问题（情况三）判别函数多类问题（情况三）判别函数nc个类别需要c个线性函数： 1 1220ti

4、iiiiddigw xw xw xwxa xn判别准则： 1max,ijj Mgg xxix5.2 线性判别函数的学习线性判别函数的学习 n问题的提出：假设有一个包含n个样本的集合y1, y2, , yn, 一些标记为1,另一些标记为2， 用 这 些 样 本 来 确 定 一 个 判 别 函 数g(x x)=a at tx x的权矢量a a。n在线性可分的情况下，希望得到的判别函数能够将所有的训练样本正确分类；n线性不可分的情况下，判别函数产生错误的概率最小。训练样本的规范化训练样本的规范化120,0,tiitiia yya yy120,0,tiitiia yya yyn非规范化：n规范化：解区

5、域的几何解释解区域的几何解释(特征空间中）特征空间中）n特征空间中：矢量a是垂直于分类界面的矢量矢量：解区域的几何解释解区域的几何解释(权空间中）权空间中）n权空间中，atyi=0是一个通过原点的超平面，yi是法向量，而a是空间中一个点。一般求解方法一般求解方法梯度下降法梯度下降法n求解不等式组采用的最优化的方法：1.定义一个准则函数J(a)，当a是解向量时，J(a)为最小；2.采用最优化方法求解标量函数J(a)的极小值。n最优化方法采用最多的是梯度下降法，设定初始权值矢量a(1)，然后沿梯度的负方向迭代计算： 1kkkJkaaa其中(k)称为学习率，或称步长。5.3 感知器算法感知器算法(P

6、erceptron)n最直观的准则函数定义是最少错分样本数准则： JN(a) = 样本集合中被错误分类的样本数；感知器准则感知器准则n以错分样本到判别界面距离之和作为准则： tPJyaa yYPJyyY感知器算法感知器算法(批量调整版本批量调整版本)1.begin initialize , , k02. do kk+13. 4. until 5.return a6.end 0a 1kkkkyaayY kkyyY感知器算法感知器算法(单样本调整版本单样本调整版本)1.begin initialize , k02. do k(k+1)mod n3. if yk is misclassified b

7、y a then 4. until all patterns properly classified5.return a6.end 0a 1kkkaay例例5.1n有两类模式的训练样本：1： (0,0), (0,1) 2： (1,0), (1,1) 用感知器算法求取判别函数，将两类样本分开。感知器算法的特点感知器算法的特点n当样本线性可分情况下，学习率 合适时，算法具有收敛性；n收敛速度较慢；n当样本线性不可分情况下，算法不收敛，且无法判断样本是否线性可分。 5.4 最小平方误差算法最小平方误差算法(LMSE)nLMSE方法的基本思想是将求解线性不等式组的问题转化为求解线性方程组：101110

8、1202021202ddnnnddnyyyabyyyabyyyab,Ya = b0b最小平方误差的准则函数最小平方误差的准则函数n定义误差矢量e，用e长度的平方作为准则函数：eYab 2SJaYab权值矢量的求解权值矢量的求解(伪逆求解法伪逆求解法) 2tSJaYYab0ttY YaY b1ttaY YY bY b1ttYY YY称为伪逆矩阵例例5.2 n有两类模式的训练样本：1： (0,0), (0,1) 2： (1,0), (1,1) 用LMSE算法求取判别函数，将两类样本分开。权值矢量的求解权值矢量的求解(迭代求解法迭代求解法)1.begin initialize a(0), b, ,

9、(), k0；2. do kk+1；3. 4. 5. until 6.return a7.end 11ntiiiikkkbaaa yy 1ntiiiikba yyLMSE算法的特点算法的特点n算法的收敛依靠(k)的衰减，一般取(k)=(1)/k；n算法对于线性不可分的训练样本也能够收敛于一个均方误差最小解；n取b=1时，当样本数趋于无穷多时，算法的解以最小均方误差逼近贝叶斯判别函数；n当训练样本线性可分的情况下，算法未必收敛于一个分类超平面。5.5 支持矢量机支持矢量机(SVM, Support Vector Machine)n函数间隔：样本xi到分类界面g(x)=0的函数间隔 定义为：n几何

10、间隔：ib0tiiibgwxw xiibw最优分类界面最优分类界面n样本集与分类界面之间的间隔 定义为样本与分类界面之间几何间隔的最小值。n最优分类界面：给定线性可分样本集，能够将样本分开的最大间隔超平面。支持矢量支持矢量n距离最优分类界面最近的这些训练样本称为支持矢量；n最优分类界面完全由支持矢量决定，然而支持矢量的寻找比较困难。SVM的准则函数的准则函数n给定两类问题的线性可分样本集合(y1,z1), , (yn,zn)，其中z为样本的类别标号：n能够将样本线性分开的分类界面满足：亦即可以通过调整权值w和w0将样本集合的最小函数间隔调整为1。121,1,iiizyy01tiizww ySV

11、M的准则函数的准则函数n样本集到分类界面的几何间隔：n 最大，亦即|w|最小，所以SVM可以变为如下的优化问题：在满足的条件下，最小化准则函数：1w212SVMJw01tiizww yKuhn-Tucker构造法构造法n构造Lagrange函数n分别对参数w和w0求导：20011,1 ,02ntiiiiiLwzwwww y01,0niiiiLwzwwyw010,0niiiLwzwwKuhn-Tucker构造法构造法n因此有：n带入Lagrange函数，有：1niiiizwy10niiiz01,11,2nntiijijijii jLwz zwy yKuhn-Tucker构造法构造法n因此SVM的

12、优化问题可以转化为一个经典的二次规划问题：约束条件： 1,112nntiijijijii jLz zy y10niiiz0,i1,in SVM解的讨论解的讨论n这是一个典型的不等式约束条件下的二次优化问题，其解法的基础是Kuhn-Tucker定理；n首先求解的是n个Lagrange乘子，n为训练样本数。但根据Kuhn-Tucker定理，有：01,tiizww y0i01,tiizww y0i满足第2个条件的yi称为支持矢量。SVM解的讨论解的讨论n根据找到的支持矢量yi以及相应的Lagrange乘子i，计算权矢量w w：1niiiizwyn偏置w0可以用支持矢量满足的条件求得：01tiizww

13、 y5.6 多类别线性判别函数的学习多类别线性判别函数的学习 n方法一：根据5.1节介绍的前两种情况，分别转换为c个两类问题，或c(c-1)/2个两类问题分别处理；n方法二：对于情况三，可以采用Kesler构造法训练；n方法三：设计感知器网络进行识别。Kesler构造法（扩展的感知器算法）构造法（扩展的感知器算法）1.初始化c个权向量ai(1)，k1；2.输入增广特征矢量yk，计算c个判别函数的输出： Tikikdkyay3.修改权矢量：若yk属于i类，而存在di(yk)dj(yk)，则： ai(k+1) = ai(k) + yk； aj(k+1) = aj(k) - yk al(k+1) =

14、 al(k)，lj, i4.重复上述过程，直到全部样本被正确分类为止。两类问题的感知器网络两类问题的感知器网络多类问题的感知器网络多类问题的感知器网络两层感知器网络的训练样本两层感知器网络的训练样本n给定样本集合(y1,t1), (y2,t2), , (yn,tn)，其中yi为增广特征矢量，ti称为期望输出；nc个输出层神经元时，可设定期望输出为：第1类样本：( 1,-1,-1,-1) 第2类样本：(-1, 1,-1,-1)第3类样本：(-1,-1, 1,-1) 第4类样本：(-1,-1,-1, 1)n编码输出时：第1类样本：(-1,-1) 第2类样本：(-1, 1)第3类样本：( 1,-1)

15、 第4类样本：( 1, 1)两层感知器网络的训练方法两层感知器网络的训练方法n可以采用最小均方误差算法，权值调整公式为： 11ntiiiikkkAAtA yy其中A为权值矢量矩阵，ti为第i个样本yi 的期望输出矢量。5.7 线性分类器的局限性线性分类器的局限性n线性分类器的分类能力不强，能够很好地解决线性可分的问题，而对非线性可分的问题无法解决，如著名的异或问题：解决途径解决途径n广义线性判别函数；n分段线性判别函数；n多层感知器；n核函数方法。广义线性判别函数广义线性判别函数n增加特征的高次项，将低维特征转化为高维特征；n2维特征的二次判别函数。 221 12231425126da xa xa xa xa x xaxXOR问题的二次函数解问题的二次函数解 221212120.66361.00560.418