Ch.3 线性与非线性判别函数

第3章 线性与非线性判别函数
3.2 最小均方误差准则与最小错分样本准则函数 本节介绍几种适用于线性可分未知时的通用方法。 3.2.1 最小均方误差准则 即LMSE算法，又称H-K算法。主要利用讨论问题的最小 均方误差建立的准则函数。 任给一小的正数向量B=(b1,b2,…,bn)T ，找到一个解向 量W，使得WTX=B成立。其中，
对于B的前后两次迭代，B(k+1)=B(k)＋δb(k)，考虑到 B>0，增量δb(k)为： 11
第3章 线性与非线性判别函数
δb(k)＝c[XW(k)-b(k)+|XW(k)-b(k)|] 令ek＝XW(k)-B(k)，则δb(k)＝c[ek +|ek|]，代入W*得： W*(k+1)=X*B(k+1)=X*b(k)+X*δB(k)＝W*(k)+ X*δB(k) ＝ W*(k)+ X* c[ek +|ek|] 这就建立了最小均方误差算法，其迭代式为： W*(k+1)=W*(k)+ X* c[ek +|ek|] W*(1)=X*B(1) B(1)>0 当ek<0时，不可分 当ek>0时，继续迭代。若ek各值已经稳定，不可分 当ek＝0时，线性可分，找到解
1 ni
X∈
∑χ X
i
映射后各类的均值向量为：
1 ni y k ∈Yi
∑y
k
类内离散度为： Si2=Σ(yk-mi)2
其中：i=1,2；yk∈Yi
17
第3章 线性与非线性判别函数
希望变换后易于分类，即类间距离大，类内离散度小。根 据此标准，Fisher定义为： J(W)=||m1-m2||2/S12+S22 使J(W)取得最大值的W*就是最佳解向量。 3.3.2 线性求解向量
W(10)=W(9)+p1=(-2,0,1)T W(11)=W(10) W(12)=W(11) W(13)=W(12) W(14)=W(13) W(15)=W(14) W(16)=W(15) W(17)=W(16)
x2 1
X 1 = 0 .5
0
1
8
x1
第3章 线性与非线性判别函数
3. 梯度法 在数学上，函数在某点的梯度表示函数在该点的变化率。 其正向函数增长最快，负向函数值减小最快，分别可达最大 值和最小值。本节先定义一个准则函数J（W,X)，其最小值 对应着W的最优解。据此可得到梯度法的公式： W(k＋1)＝W(k)-ρ(∇J)w=w(k) 式中ρ 为一正比例因子，通过J（W,X)和W(1)迭代可求得W。 4. 感知器准则函数 J(W,X)=k(|WTX|-WTX) （ k>0） 当 WTX>0时，J(W,X)取得最小值。令k=1/2，得 ∇Jw＝[xsgn(WTX)-X]/2 ⇒ W(k＋1)＝W(k)-ρ(∇J) WTX>0 ⇒W(k＋1)＝W(k) WTX≤0 ⇒W(k＋1)＝W(k)+ ρxk 注意：感知器算法为梯度法特例，仅适用线性可分情况。 9
第3章 线性与非线性判别函数
3.3 Fisher线性判别函数 在统计模式识别中，降低维数有时就成为处理实际问题的 关键。Fisher线性判别函数法基本思想是把 d 维模式投影到 一条通过原点的直线上，把维数压缩到1。 3.3.1 线性投影与Fisher准则函数 1.线性投影 投影的方向对模 式的划分起着重要 的作用。在图中， W的投影线性可分， W’的投影不可线性 划分。分类主要取 决于W的方向。分界 面为与W垂直的方向。
x2
+ −
1
ห้องสมุดไป่ตู้ω2
g(x)=wx +wx2 +w 11 2 3
x1
3
第3章 线性与非线性判别函数
在两类情况下，令g(X)=g1(X)-g2(X) 判别规则为： 1 2
x
+ −
ω
ω2
g(x) =wx1 +w x2 +w 1 2 3
x1
线性分类器的设计就是确定权向量W的过程。方法为： 采集训练样本 确定可以反映分类性质的准则函数J＝J(X，W) 设计求解W的最优算法，求解W。 建立分类函数g(X) 一旦得到W后，就可将模式正确分类。
线性与非线性判别函数
模式识别
钟珞等编著 武汉大学出版社 2006.9
1
第3章 线性与非线性判别函数
本章主要内容 感知准则函数 最小平方误差准则 最小错分样本数准则 Fisher线性判别准则 分段线性判别函数 二次判别函数
2
第3章 线性与非线性判别函数
第2章中介绍了在样本的先验概率和分别函数已知时的Bayes 分类器的设计。本章主要直接根据训练样本提供的信息，直接 设计分类器，进行特征空间的划分。 3.1 感知器准则函数 3.1.1 线性判别函数的基本概念 在Rd中，向量X=(x1,x2,…,xd)T的线性判别函数为： g(X)=w1x1+w2x2+…+wdxd+wd+1 =WTX+wd+1 其中：W=(w1,w2,…,wd)T为权向量 若令 W=(w1,w2,…,wd，wd+1)T为增广权向量 X=(x1,x2,…,xd ,1)T为增广模式向量 则： g(X)=WTX ω
第3章 线性与非线性判别函数
除令Jp(W)=0的其它任意点W,Jp(W)的负梯度为： g(X)=-∇WJp(W)/4=XT[|XW-B|-(XW-B)] 共轭梯度算法 设λ=1/‖g‖2，k迭代步数，γ为向量W满足WTX>0的不等 式数目，W*为最优解。 (1)令k=0，W0任意。计算XW0和γ0。若0<γ0<n/2,则令W0←-W0, XW0←-XW0, γ0←n-γ0 ,重复(1). (2)若γk=n,令W*←WK，停止。若γk=0,令W*←-WK，停止;否则， γ γ 继续。 (3)计算gk，如gk=0,停止；否则计算λk，然后继续。 (4)若k为λ的整数倍，θk=0,否则θk=1，并计算第K次梯度下 的 S 降方向：SK= θkSK-1+λkgk (5)令vk←J(WK+vSK)取最小值的v。 (6)令WK+1←WK+VKSK，XWK+1=XWK+VKXSK。计算γk+1。 (7)令k←k+1，转（2）。 15
1 X* = −1 1 1 −1 2 1.5 0.5 −0.5 0.5
令C=1，B(1)=(1,1,1,1)T,则W(1)=X*B=(-2,0,1)T e1=XW(1)-B(1)=(0,0,0,0)T 因e1得各个分量为0，故W(1)即为所求。W*=(-2,0,1)T 模式先行可分，其决策面方程为：g(X)=W*TX=0,即 x1＝0.5
4
第3章 线性与非线性判别函数
3.1.2 感知器概念及其训练算法 1.感知器概念 1.感知器概念 感知器是F.Rosenblatt在1957年提出的具有单层计算能力 的神经元模型。
x1 W 1 x2
w2
y
wd
Y=f(Σwixi-θ) 如Σwixi-θ>0 ,那么y=1,否则，y=-1. 其中：W=(w1,w2,…,wd)T,X=(x1,x2,…,xd)T 。权值W是通过训练 学习进行调整，实现线性可分函数。Rosenblatt已经证明：如 果两类模式线性可分，那么算法一定收敛。
16
第3章 线性与非线性判别函数
2 Fisher准则函数 设有两类问题ω1/ω2，n个训练样本xk（k＝1,2,…,n), 通过W对xk进行变换： yk＝WTxk yk是xk在方向为W直线上的投影。寻找最好的投影方向 即是寻找最好的变换向量的问题 在d维特征空间中，各类样本的均值向量为：
Mi = mi =
6
第3章 线性与非线性判别函数
例：用感知器法求权向量W,其中样本ω1={p1,p2},ω2={p3,p4}, p1=(0,0)T,p2=(0,1)T,p3=(1,0)T,p4=(1,1,)T 解：给样本乘－1，得到样本的增广向量： p1=(0,0,1)T,p2=(0,1,1)T,p3=(-1,0,-1)T,p4=(-1,-1,-1)T 取C=1，W(1)=(0,0,0)T C=1， 第1轮： WT(1)p1=(0,0,0)(0,0,1)T=0 W(2)=W(1)+p1=(0,0,1)T WT(2)p2=(0,0,1)(0,1,1)T=1 W(3)=W(2) WT(3)p3=(0,0,1)(-1,0,-1)T=-1 W(4)=W(3)+p3=(-1,0,0)T WT(4)p4=(-1,0,0)(-1,-1,-1)T=1 W(5)=W(4) 第2轮： WT(5)p1=(-1,0,0)(0,0,1)T=0 W(6)=W(5)+p1=(-1,0,1)T WT(6)p2=(-1,0,1)(0,1,1)T=1 W(7)=W(6) WT(7)p3=(-1,0,1)(-1,0,-1)T=0 W(8)=W(7)+p3=(-2,0,0)T WT(8)p4=(-2,0,0)(-1,-1,-1)T=2 W(9)=W(8) 7
13
第3章 线性与非线性判别函数
3.2.2 最小错分样本准则函数 1 基本思想 在LMSE中，当WTX>0无解时样本线性不可分（必有错分）， 可寻找一种错分样本最少的方法。 设余量B =(1,1,…,1)T >0,则有WTX>B>0。可定义错分样本 数准则函数： J(W)=‖(XW-B)-|XW-B|‖2 （*) 若XW>B,则正确分类，J(W)取最小值0;若有错分样本，必 有J(W)>0。错分样本越多，J(W)越大。显然，J(W)取最小值的 W*为最优解。 2 共轭梯度法求解W* 共轭梯度法求解W 向量共轭：设B为(d+1)×(d+1)矩阵，若存在d+1维向量U和V， 使(U,BV)=0成立，称U和V对矩阵B共轭 共轭。 共轭 算法以d+1维空间中B的一组共轭向量为一维搜索方向。已证 明：二次正定函数f(X)=a0+aTX+XTBX，最多d+1步使序列｛xk｝ 收敛于f(X)的极值X*。式(*)经d+1步不收敛时，重新计算。 14