模式識別-線性判別函數(shù)

模式識別原理華中科技大學(xué)圖像識別與人工智能研究所2022/12/151線性判別函數(shù)

問題描述線性判別函數(shù)

如下圖:三類的分類問題,它們的邊界線就是一個判別函數(shù)判別函數(shù)包含兩類:線性判別函數(shù):線性判別函數(shù)廣義線性判別函數(shù)(所謂廣義線性判別函數(shù)就是把非線性判別函數(shù)映射到另外一個空間變成線性判別函數(shù))分段線性判別函數(shù)非線性判別函數(shù)線性分類器的三種典型方法以Fisher準則為代表的傳統(tǒng)模式識別方法以感知準則函數(shù)為代表的機器自學(xué)習方法以支持向量機為代表的統(tǒng)計學(xué)習理論。分段線性判別函數(shù):近鄰法2022/12/1542022/12/1552022/12/156判別函數(shù)的形式模式的特征矢量：判別函數(shù)：稱為權(quán)矢量或系數(shù)矢量判別函數(shù)的形式增廣特征矢量：增廣權(quán)矢量：判別函數(shù)：兩類問題線性判別準則決策規(guī)則:線性分類器的分類界面分類界面的幾何解釋線性分類界面H是d維空間中的一個超平面；分類界面將d維空間分成兩部分，R1，R2分別屬于兩個類別；判別函數(shù)的權(quán)矢量w是一個垂直于分類界面H的矢量，其方向指向區(qū)域R1

；偏置w0與原點到分類界面H的距離有關(guān)：多類問題（情況一）每一類模式可以用一個超平面與其它類別分開；這種情況可以把c個類別的多類問題分解為c個兩類問題解決，需要c個線性分類界面；第i類與其它類別之間的判別函數(shù)：（1）二分法多類問題（情況一）判別規(guī)則若存在i，使得gi(x)>0，gj(x)<0，j≠i，則判別x屬于ωi類；其它情況，拒識。多類問題（情況二）每兩個類別之間可以用一個超平面分開；c個類別的問題需要c(c-1)/2個線性分類界面；第i類與第j類之間的判別函數(shù)為：多類問題（情況二）判別準則如果對任意j≠i

，有g(shù)ij(x)≥0

，則決策x屬于ωi。其它情況，則拒識。結(jié)論：判別區(qū)間增大，不確定區(qū)間減小IR（2）ωi/ωj二分法多類問題（情況三）情況三是情況二的特例，不存在拒識區(qū)域。多類問題（情況三）判別函數(shù)c個類別需要c個線性函數(shù)：判別準則：（3）最大判別準則結(jié)論：無不確定區(qū)間例：假設(shè)判別函數(shù)為：問屬于哪一類。解：所以三種方法小結(jié)分類方法判別函數(shù)個數(shù)不確定區(qū)難易ωi/ωi二分法ωi/ωj二分法最大判別準則MM(M-1)/2M最多較少沒有較難較易較易2022/12/1525判別函數(shù)的幾何意義2022/12/1526Fisher準則的基本原理2022/12/1527基本參量的定義2022/12/1528基本參量的定義2022/12/1529Fisher線性判別

Fisher線性判別

Fisher線性判別

Fisher線性判別

Fisher線性判別

2022/12/1535Fisher線性判別

2022/12/15372022/12/15382022/12/15392022/12/1540兩個問題：（1）構(gòu)造準則函數(shù)（2）如何最快地搜索到使準則函數(shù)取極小值的解線性判別函數(shù)的學(xué)習

問題的提出：假設(shè)有一個包含n個樣本的集合y1,y2,…,yn,一些標記為ω1,另一些標記為ω2，用這些樣本來確定一個判別函數(shù)g(x)=atx的權(quán)矢量a。在線性可分的情況下，希望得到的判別函數(shù)能夠?qū)⑺械挠?xùn)練樣本正確分類；線性不可分的情況下，判別函數(shù)產(chǎn)生錯誤的概率最小。訓(xùn)練樣本的規(guī)范化非規(guī)范化：規(guī)范化：最優(yōu)問題的求解：（1）一個適當?shù)拇鷥r函數(shù)（準則函數(shù)）（2）一個優(yōu)化算法梯度下降法一次準則函數(shù)及梯度下降法

(GradientDescentAlgorithm)感知準則函數(shù)（Rosenblatt）

可微函數(shù)在某點的梯度是一個向量函數(shù)在該點的變化率最大的方向函數(shù)的梯度向量定義為

梯度下降法的迭代公式為：

任給定初始權(quán)矢量，第k+1次迭代時的權(quán)矢量等于第k次的權(quán)矢量加上被w（k）錯分的樣本之和乘以某個系數(shù)。

批量修正準則函數(shù)的梯度：將梯度下降法應(yīng)用到一次準則函數(shù)中感知器算法把樣本集看成不斷出現(xiàn)的序列逐一考慮，稱為單樣本修正法。且令，稱為固定增量法。若使得+-+-感知器算法(PerceptronApproach)

算法思想任選一初始增廣權(quán)矢量用訓(xùn)練樣本檢驗用分類正確否對進行校正對所有訓(xùn)練樣本都能正確分類？ENDYesYesNoNo一、感知器算法算法步驟：增廣的訓(xùn)練樣本集每個類別已知，（1）令步數(shù)k=1,增量為正的常數(shù)，的各分量為較小的任意值（2）輸入訓(xùn)練模式，計算判別函數(shù)值（3）調(diào)整增廣權(quán)矢量，規(guī)則：（a）如果

（b）如果（c）如果（4）如果k<N，令k=k+1，GOTO（2）如果k=N，則檢驗對所有訓(xùn)練樣本是否都正確分類，是則結(jié)束，否則，令k=1，GOTO（2）一、感知器算法收斂定理：如果訓(xùn)練模式是線性可分的，感知器訓(xùn)練算法在有限次迭代后可以收斂到正確的解矢量證明：。。。。。。

一、感知器算法感知器算法在多類問題中的運行步驟：增廣的訓(xùn)練樣本集每個類別已知，（1）令步數(shù)k=1,增量為正的常數(shù)，C個權(quán)矢量賦任意初值（2）輸入符號未規(guī)范化的增廣訓(xùn)練模式，計算C個判別函數(shù)值（3）調(diào)整增廣權(quán)矢量，規(guī)則：（a）如果

（b）如果

（4）如果k<N，令k=k+1，GOTO（2）如果k=N，則檢驗對所有訓(xùn)練樣本是否都正確分類，是則結(jié)束，否則，令k=1，GOTO（2）感知器算法(批量調(diào)整版本)begininitialize,,θ,k0do

kk+1

untilreturnaend例有兩類模式的訓(xùn)練樣本：

ω1：{(0,0),(0,1)}

ω2：{(1,0),(1,1)}

用感知器算法求取判別函數(shù)，將兩類樣本分開。解：(1)訓(xùn)練樣本分量增廣化及符號規(guī)范化：

(2)給增廣權(quán)矢量賦任意初值，取增量=1，57例題:已知訓(xùn)練樣本(0,0)T1，(1,1)T2，(-1,1)T3,

試求解向量w1、w2和w3。

（2）運用感知器訓(xùn)練算法。置k=1，增量=1，賦初值：w1=(0,0,0)T,w2=(0,0,0)T,w3=(0,0,0)T,進行迭代運算：解:（1）訓(xùn)練樣本分量增廣化。將訓(xùn)練樣本變成增廣訓(xùn)練模式：x1=(0,0,1)T,x2=(1,1,1)T,x3=(-1,1,1)T,

這里的下標恰是所屬類別，各類樣本不需符號規(guī)范化。58例題:已知訓(xùn)練樣本(0,0)T1，(1,1)T2，(-1,1)T3,

試求解向量w1、w2和w3。

k=1,xk=x11,因為d1(x1)=d2(x1)=0，d1(x1)=d3(x1)=0，錯分，所以:w1(2)=w1(1)+x1=(0,0,1)Tw2(2)=w2(1)-x1=(0,0,-1)Tw3(2)=w3(1)-x1=(0,0,-1)Tk=2,xk=x22,因為d2(x2)=-1<d1(x2)=1，d2(x2)=d3(x2)=-1，錯分，所以w1(3)=w1(2)-x2=(-1,-1,0)Tw2(3)=w2(2)+x2=(1,1,0)T

w3(3)=w3(2)-x2=(-1,-1,-2)T59例題:已知訓(xùn)練樣本(0,0)T1，(1,1)T2，(-1,1)T3,

試求解向量w1、w2和w3。

k=3,xk=x33,因為d3(x3)=-2<d1(x3)=0，d3(x3)=d2(x3)=0，錯分，所以w1(4)=w1(3)-x3=(0,-2,-1)Tw2(4)=w2(3)-x3=(2,0,-1)T

w3(4)=w3(3)+x3=(-2,0,-1)Tk=4,xk=x11,因為d1(x1)=d2(x1)=-1，d1(x1)=d3(x1)=-1，錯分，所以w1(5)=w1(4)+x1=(0,-2,0)Tw2(5)=w2(4)-x1=(2,0,-2)T

w3(5)=w3(4)-x1=(-2,0,-2)T60例題:已知訓(xùn)練樣本(0,0)T1，(1,1)T2，(-1,1)T3,

試求解向量w1、w2和w3。

k=5,xk=x22,因為d2(x2)=0>d1(x2)=-2，d2(x2)=0>d3(x2)=-4，正確，所以w1(6)=w1(5)=(0,-2,0)Tw2(6)=w2(5)=(2,0,-2)T

w3(6)=w3(5)=(-2,0,-2)Tk=6,xk=x33,因為d3(x3)=0>d1(x3)=-2，d3(x3)=0>d2(x3)=-4，正確，所以w1(7)=w1(6)=(0,-2,0)Tw2(7)=w2(6)=(2,0,-2)T

w3(7)=w3(6)=(-2,0,-2)T61例題:已知訓(xùn)練樣本(0,0)T1，(1,1)T2，(-1,1)T3,

試求解向量w1、w2和w3。

k=7,xk=x11,因為d1(x1)=0>d2(x1)=-2，d1(x1)=0>d3(x1)=-2，正確，三個權(quán)矢量不再變化，因此可以確定所有訓(xùn)練樣本均已被正確分類，由此得到三個解矢量：w1*=w1(5)，w2*=w2(5)，w3*=w3(5)同時可得三個判別函數(shù): d1(x)=-2x2 d2(x)=2x1-2 d3(x)=-2x1-2二次準則函數(shù)及其解法

問題：

一次準則函數(shù)及其算法（如感知器算法）只適用于線性可分的情況，如果是線性不可分的，分類過程將不收斂?

能否找到一種算法，使之能夠測試出模式樣本集是否線性可分，并且對線性不可分的情況也能給出“次最優(yōu)”的解？

如果訓(xùn)練模式是線性不可分不等式組是不一致的，不等式組沒解。此時，目標最少的訓(xùn)練模式被錯分。（一）最小錯分模式數(shù)目準則

對線性不可分樣本集，求一解矢量使得錯分的模式數(shù)目最少。

對于兩類問題，設(shè)n+1維增廣訓(xùn)練模式已符號規(guī)范化。

如果訓(xùn)練模式是線性可分的，則存在權(quán)矢量使不等式組成立。式中是矩陣。

將上面的不等式組寫成矩陣方程形式，并引入N

維余量矢量，于是不等式方程組變?yōu)椋ǘ┳钚》讲顪蕜t及W-H算法

針對方程組,構(gòu)造方差準則函數(shù)

對于,此時的,而對于,此時的。如果方程組有唯一解,說明訓(xùn)練模式集是線性可分的,如果方程組無解,極小點值是最小二乘解。一般情況下使極小等價于誤分模式數(shù)目最少。

⑴偽逆法

求對的梯度并令其為零，有可得(3-6-12)

當(X’X)-1存在時，

X+=(X’X)-1X’稱為X的偽逆(也稱廣義逆或M-P逆)， 稱為的偽逆解。

X’X是(n+1)×(n+1)矩陣，一般是非奇異的。 當(X’X)-1不存在時，可用廣義逆法解 這里(X

’X)+為X’X的廣義逆矩陣。求解最佳權(quán)矢量的方法：⑵梯度法由前述知，的梯度為梯度下降算法迭代公式為Step1.任取Step2.(3-6-13)可以證明，當為任意正的常數(shù)，

則該算法使權(quán)矢量序列收斂于;滿足，也稱為MSE解。

此算法的兩個性質(zhì):1.當時,MSE解等價于Fisher解。

2.令,在樣本數(shù)時,MSE解以最小均方誤差逼近貝葉斯判決函數(shù)Step1.任取Step2.此算法通常稱為W－H(Widrow－Hoff)算法仿前采用單樣本修正法，則式(3-6-