課件第4章模式識別基礎(chǔ)

1、Media and Cognition電子工程系利: liyali13進(jìn)模式識別系統(tǒng)Ø 數(shù)據(jù)獲?。盒盘柨臻gØ 預(yù)處理Ø 特征提取和選擇：特征空間Ø 分類決策：模式空間尋找有利于分類的本質(zhì)特征2分類學(xué)習(xí)/測試模式識別系統(tǒng)決策例如：傳感器的感文本切割、腦電波的部分與整體關(guān)系基元例如：攝像機(jī)、麥克風(fēng)陣列傳感器因素：帶寬、靈敏度、失真、信噪比、延遲等等輸入3傳感器分割器特征提取器分類器后處理器模式識別系統(tǒng)決策輸入4傳感器分割器特征提取器類內(nèi)一致性：來自同一類別的不同樣本特征值相近類間差異性：來自不同類別的樣本特征值有很大差異表征能力、鑒別性、特征維度分類器后處理

2、器模式識別系統(tǒng)決策輸入5傳感器分割器特征提取器分類器根據(jù)特征提取器提取的特征向量給被測試對象(樣本)賦予類別標(biāo)記后處理器模式識別系統(tǒng)決策輸入6傳感器分割器特征提取器分類器根據(jù)特征提取器提取的特征向量給被測試對象(樣本)賦予類別標(biāo)記后處理器模式識別系統(tǒng)決策輸入7傳感器分割器特征提取器上下文信息： 魚在水里游 鳥在天空飛 人在地上走分類器根據(jù)上下文信息對分類進(jìn)行調(diào)整后處理器第四章模式識別基礎(chǔ)4.1 統(tǒng)計模式識別4.2決策4.3 參數(shù)估計方法4.4 非參數(shù)估計方法4.1 統(tǒng)計模式識別Ø 模式(pattern)u 人們在一定條件環(huán)境下，根據(jù)一定需要，對自然事物的一種抽象的分類概念。W=w1,

3、 w2,wM u 模式集合記為：Ø 樣本(sample, object) 是自然界的具體事物，具有一定的類別特性，是抽象模式的具體體現(xiàn)。X = ()T 樣本的觀測量記為：NØ 模式識別：尋求樣本觀測量與類別屬性的g(x)= wi：樣本類別9模式識別10基本問題:模式類的性Ø 臨界點(diǎn)的數(shù)量與總的點(diǎn)數(shù)相比很少Ø 集合內(nèi)的任意兩點(diǎn)的連線,上的點(diǎn)屬于同一集合Ø 集合內(nèi)的每一個點(diǎn)都有足夠大的鄰域,在鄰域內(nèi)只包含同一集合的點(diǎn)分類難度提升，分類錯誤率增加（a）沒有臨界點(diǎn)（b）有較多臨界點(diǎn)（c） 臨界點(diǎn)過多114.1.2 統(tǒng)計模式識別：經(jīng)驗(yàn)誤差Ø 錯

4、誤率(error rate)與精度(accuracy)：u 錯誤率：分類錯誤的樣本占樣本總數(shù)的比例u 假設(shè)𝑚個樣本中有𝑎個樣本分類錯誤，則𝐸 = 𝑎 𝑚u 精度：1-錯誤率1 𝑎 𝑚Ø 誤差(error)：u 學(xué)習(xí)器的實(shí)際輸出與樣本的真實(shí)輸出之間的差異u 訓(xùn)練誤差/經(jīng)驗(yàn)誤差(empirical error)u 測試誤差/泛化誤差(generalization error)124.1.2 統(tǒng)計模式識別：過擬合Ø 過擬合(overfitting)與欠擬合(underf

5、itting)：u 欠擬合：訓(xùn)練樣本的性質(zhì)沒學(xué)好，表現(xiàn)為訓(xùn)練誤差大u 過擬合：訓(xùn)練樣本學(xué)的”太好”，缺乏對本質(zhì)的理解，出現(xiàn)泛化性能下降134.1.2 統(tǒng)計模式識別：系統(tǒng)評價指標(biāo)Ø 分類結(jié)果的矩陣Ø率Recall、準(zhǔn)確率PrecisionTPTPRecall=, Precison=TP + FNTP + FPØ 真陽性率(True Positive Rate)、假陽性率(False Positive Rate)TPFPTPR=, FPR=TP + FNTP + FP14真實(shí)類別類別正例反例正例TP(真正例)FN(假反例)反例FP(假正例)TN(真反例)4.1.2 統(tǒng)

6、計模式識別：系統(tǒng)評價指標(biāo)Ø ROC曲線u ROC（Receiver Operator Characteristic）曲線，稱為受試者工作特征曲線，又稱為接收者操作特性曲線，是以真陽性率(true positive rate, TPR)為縱坐標(biāo)，假陽性率（false positive rate, FPR）為橫坐標(biāo)繪制的曲線。15Q1: 什么樣的ROC曲線代表高性能的模式識別系統(tǒng)？4.1.3 統(tǒng)計模式識別：測試方法Ø 交叉驗(yàn)證方法(CrossValidation)u CV是用來驗(yàn)證分類器的性能一種統(tǒng)計分析方法，將原始數(shù)據(jù)(dataset)進(jìn)行分組,一部分做為訓(xùn)練集(traini

7、ng set),另一部分做為驗(yàn)證集(validation set)u K-折交叉驗(yàn)證（K-fold Cross Validation） 將原始數(shù)據(jù)分成K組(一般是均分)，將每個子集數(shù)據(jù)分別做一次驗(yàn)證集,其余的K-1組子集數(shù)據(jù)作為訓(xùn)練集，這樣得到K個模型 K個模型最終的驗(yàn)證集的分類準(zhǔn)確率的平均數(shù)作為分類器的性能指標(biāo)eave-One-Out）u 留一 每個樣本單獨(dú)作為驗(yàn)證集,其余的N-1個樣本作為訓(xùn)練集16統(tǒng)計模式識別統(tǒng)計模式識別結(jié)構(gòu)模式識別類條件概率函數(shù)P(x|i)17非參數(shù)參數(shù)非參數(shù)參數(shù)非監(jiān)督學(xué)習(xí)監(jiān)督學(xué)習(xí)已知決策理論未知神經(jīng)網(wǎng)絡(luò)4.1 統(tǒng)計模式識別Ø 基本概念(小結(jié))u 錯誤率，精度

8、u 誤差、經(jīng)驗(yàn)誤差、泛化誤差u 過擬合、欠擬合矩陣率、準(zhǔn)確率uuu ROC曲線、AUC數(shù)值u 測試方法18第四章模式識別基礎(chǔ)4.1 統(tǒng)計模式識別4.2決策4.3 參數(shù)估計方法4.4 非參數(shù)估計方法4.2決策：數(shù)學(xué)基礎(chǔ)Ø 條件概率和概率：u 假設(shè)A和B是一個樣本空間中的兩個B發(fā)生的條件下，A發(fā)生的條件概率為，在假定P ( A, B) P ( B)概率為P ( A B)=A和B的uP ( A, B) =P ( A B ) P (B ) =P (BA) P ( A)204.2決策：數(shù)學(xué)基礎(chǔ)Ø定理：u 假設(shè)𝐴1和𝐴2是互斥的兩個生的概率（邊際概率）為

9、全空間，且𝐴1 𝐴2= 𝑆，𝐵發(fā)P ( B) =P (BA1 ) P ( A1 ) +P (BA2 ) P ( A2 )u 兩的定理定理為：P ( Ai ) P (BAi )P ( AiB)=, i = 1, 2P ( A1 ) P (BA1 )+P ( A2 ) P (BA2 )的定理定理為：u 𝑛P ( Ai ) P (BAi )P ( AiB)=, i = 1, 2, nP ( A1 ) P (BA1 )+P ( A2 ) P (BA2 )+P ( An ) P (BAn )214.2決策：數(shù)學(xué)基礎(chǔ)Ø

10、;定理：的u 兩定理定理為：P ( Ai ) P (BP ( B)Ai )P ( AiB)=, i = 1, 2u 模式識別中的P (wi定理表示：P (wi ) P ( x wi )x)=, i = 1, 2P ( x)先驗(yàn)概率似后驗(yàn)概率posterior= prior ´ likelihoodevidence22通過觀測𝑥將先驗(yàn)概率𝑃 𝜔𝑖 轉(zhuǎn)化為后驗(yàn)概率𝑃 𝜔𝑖|𝑥4.2決策：數(shù)學(xué)基礎(chǔ)Ø(正態(tài))分布：23Q2： why Gaussian?4.

11、2決策Ø決策u 概率框架下實(shí)施決策的基本方法決策：在所有相關(guān)概率已知的條件下，考慮如何利用已知概率，以最小化誤判損失函數(shù)為目標(biāo)來選取最優(yōu)的類別標(biāo)記u24Duda, Hart, Stork, Pattern Recognition4.2 貝葉斯決策ìï P (w1x) x)判定為w2判定為w1P (errorx)= íØ 誤分類ïîP (w2Ø 平均誤差概率¥¥P (error ) = ò P (error, x)dx= ò P (error | x )P ( x ) dx-&

12、#165;-¥ìïP (w1x) > P (w2x) x)判定為w1íP (w x) < P (w判定為wïî122x), P (w2x)=minP (w1x)P (error貝葉斯決策函數(shù)一般形式ìïP ( x w1 ) P (w1 ) > P ( x w2 ) P (w2 )判定為w1íP ( x w) P (w) < P ( x w ) P (w )判定為wïî2511222Gi (x) = p( x | i ) p(i )4.2決策Ø 正態(tài)分布

13、條件下的決策u 假設(shè)類條件概率密度函數(shù)為正態(tài)分布u 判別函數(shù)定義為:u 取對數(shù)后判別函數(shù)為:264.2決策4.2決策Ø 正態(tài)分布條件下的決策假設(shè)各類先驗(yàn)概率相等，協(xié)方差矩陣的三種情況= 𝜎2𝐼= (1) 𝑖(2) 𝑖最小距離分類器最小馬氏距離分類器馬氏距離 Mahalanobis distance= (x - )T -1(x - )d 2iii(3) 𝑖𝑖 𝑗 ，二次判別函數(shù) 𝑗284.2決策Ø 正態(tài)分布條件下的u 情況1：𝑖 =

14、𝜎2𝐼決策294.2決策Ø 正態(tài)分布條件下的u 情況2：𝑖 = 決策g (x) = - 1 (x - )T -1(x - ) + ln p( )iiiii24.2決策314.2決策Ø 正態(tài)分布條件下的決策u 情況3：𝑖 𝑗𝑖 𝑗g (x) = - 1 (x - )T -1 (x - ) - 1 ln + ln p( )iiiiii22324.2決策334.2決策Ø線性判別函數(shù)(Linear Discriminant Function, LDF)g (x)

15、 = - 1 (x - )T -1(x - ) - d ln(2) - 1 ln + ln p( )iiiiii222假設(shè)各類協(xié)方差矩陣都相等，去除判別函數(shù)公式中對各類別相同的項，并忽略先驗(yàn)概率，得到線性判別函數(shù)(x) = AT x + bgLDFiib = - 1 T -1 A =-1 i0iii0i2344.2決策Ø二次判別函數(shù)(Quadratic Discriminant Function,QDF)假設(shè)各類的協(xié)方差陣𝑖不相等,得二次判別函數(shù):(x) = - 1 (x - )T -1(x - ) - 1 ln gQDFiiii22對判別函數(shù)取負(fù)數(shù)并乘以系數(shù)2，利用

16、協(xié)方差矩陣的特征分解，得到：)T -1(x - (x) = -2g(x) = (x - ) + ln gQDFQDFMMMMn= åi=1 1nÕi=1(x -i) + lnT2iMi354.2決策Ø二次判別函數(shù)(Quadratic Discriminant Function,QDF)對判別函數(shù)取負(fù)數(shù)并乘以系數(shù)2，利用協(xié)方差矩陣的特征分解， 得到：(x) = -2g(x) = (x - )T -1(x - ) + ln gQDFQDFMMMMn= åi=1nnÕ 1(x -i) + lnT2iMi=1iå，M、T其中，為對應(yīng)第

17、19894; （原類別下標(biāo)i暫且省略）=MiiiM類均值和協(xié)i=方1 差矩陣的最大似然估計； 的特征值及對應(yīng)特M（ii = 1,., n）、i征向量為，特征值為降序排列。從式中可以看出，計算結(jié)果對于較小特征值的估計誤差更為敏感36MQDF： 第一種類型Ø MQDF（ Modified Quadratic Discriminant Function ）u 在協(xié)方差矩陣的對角線上加一個小的常量 h2 ，保證矩陣的（非奇異性），由此取代協(xié)方差矩陣的最大似然估計，即為：P= M+ h2 In1nåi=1 (x - ) + ln Õ(i +h )(x) =T22gMQDF1

18、iM2 +hi=1i37MQDF： 第二種類型Ø 用 h2（i ³ k +1;i £ n），k為主子代替較小特征值i空間截斷維數(shù)k1n1kåi=1åi=k +1Õ i )i=1(x) =(x - ) +(x - ) + ln(h2(n-k )T2T2gMQDF2iMiM2hiØ 利用nåi (x - 2=x - MT2)Mi=1é2 ùh21kk- å(1-)i (x - M ) ú + ln(hÕ i )i=122(n-k )gMQDF2 (x) = h2 

19、34; x - MTëûi=1iØh2可以有多種取值方式，比如取所有較小特征值 （ii ³ k +1;i £ n）的平均值38實(shí)例：脫機(jī)手寫漢字識別Ø 脫機(jī)手寫漢字識別的u 統(tǒng)計方法：維數(shù)和過訓(xùn)練39MQDF分類器特征提取預(yù)處理基于線性判別分析LDA 的特征降維限定式的工整手寫B(tài)lock PrintingManuscript Writing手稿式的自由手寫31便箋式的隨意手寫 Cursive Scripts線性鑒別分析實(shí)驗(yàn)Ø 目的：選擇合適的特征壓縮維數(shù) 結(jié)果： 條件：9599.6原始輸入392 維筆畫邊緣方向特征94.49

20、9.5分類器最近距離分類器93.899.5Top 1 Choice (Left)Top 10 Choices (Right)93.299.450100150200250300350最近距離分類器的識別率 隨特征壓縮維數(shù)的變化曲線41MQDF實(shí)驗(yàn)Ø 目的：選擇合適的MQDF主子空間截斷維數(shù)k 結(jié)果： 條件：96LDA特征壓縮維數(shù)：12895.895.695.495.295104070100MQDF 識別率隨主子空間維數(shù) k 的變化曲線424.2決策(小結(jié))Ø 數(shù)學(xué)基礎(chǔ)：Ø 名詞概念：u 先驗(yàn)概率、后驗(yàn)概率、似然概率定理、分布決策：先驗(yàn)概率至后驗(yàn)概率的轉(zhuǎn)化uØ

21、; 正態(tài)分布下的u 三種情況分析u 歐式距離、馬氏距離u 線性判別函數(shù)、二次判別函數(shù)u 拓展：MQDF決策43第四章模式識別基礎(chǔ)4.1 統(tǒng)計模式識別4.2決策4.3 參數(shù)估計方法4.4 非參數(shù)估計方法4.3 參數(shù)估計方法：最大似然估計Ø決策：根據(jù)先驗(yàn)概率𝑃𝑃 𝑥|𝜔𝑖設(shè)計最優(yōu)分類器；𝜔𝑖和類條件概率u 問題：實(shí)際應(yīng)用中，概率(密度函數(shù))很難獲取Ø 參數(shù)估計：利用訓(xùn)練樣本估計決策問題中的先驗(yàn)概率和條件密度函數(shù)，在此基礎(chǔ)上設(shè)計分類器。Ø 先驗(yàn)概率估計：離散二

22、項式分布nP ( z , zzw) = Õ P (w)é1- P (w)ù1- zz,ikikëûi1i 2iniiik =1n1n()åk =1Þ P w =ziik454.3 參數(shù)估計方法：最大似然估計Ø 假設(shè)有樣本集𝐷，服從參數(shù)為𝜃的概率分布，𝐷中包含有𝑛個抽取的樣本，則n()p x q)(Õk =1p D q=kØ 對數(shù)似然函數(shù)：n()(q)åk =1( )l q ºln p D q =ln p xk&#

23、216; 最大似然估計：q= arg max l (q)q464.3 參數(shù)估計方法：最大似然估計Ø 假設(shè)有樣本集𝐷，服從參數(shù)為𝜃的概率分布，𝐷中包含有𝑛個抽取的樣本，則n()(q)Õk =1p D q=p xkØ 對數(shù)似然函數(shù)：n()ln p x q)(å( )l q º ln p D q =kk =1nln p x q)=0(åk =1( )Ñ l q ºÑØ 最大似然估計：qqkq= arg max l (q)q474.3 參數(shù)

24、估計方法：最大似然估計Ø 多元正態(tài)分布u 概率密度函數(shù)p(x) N (m, S)112p(12(2p)S2u 情況1：均值未知，協(xié)方差矩陣已知n= 1 åm =qx1knk =1u 情況2：均值和協(xié)方差矩陣均未知1nnå xkk =1n1m=q =S =q =å(x -m)(x-m)T12kknk =1484.3 參數(shù)估計方法：最大似然估計Ø 多元正態(tài)分布u 概率密度函數(shù)p(x) N (m, S)1exp- 1 (x - m)T S-1(x - m) 2，S) =p(d(2p) 212Su 情況1：均值𝜇未知，協(xié)方差矩陣已知m)

25、 = - 1 ln éë(2p)dS ùû - 1 (x - m)T S-1(x - m)kkln p(22ßÑm) = S-1(x - m)ln p(xukkßk最大似然估計nnåÑk =1m) = åS-1(x- m) = 0nln p(x()ln p x q)(å( )l q º ln p D q=ukik =1i=1nm = 1 å xÞq= arg max l (q)kn49k =1q4.3 參數(shù)估計方法：最大似然估計Ø 多元正態(tài)分布u

26、 概率密度函數(shù)p(x) N (m, S)1exp- 1 (x - m)T S-1(x - m) 2，S) =p(d(2p) 212Su 情況2：均值𝜇、協(xié)方差矩陣未知(單變量推導(dǎo)) = - 1 ln(2pq ) -1(x -q)2ln p(xk2k12q22ßéêùúú 1q ( xk-q1 ) = ê2Ñln p(xêúk(x -q)21最大似然估計ê-+k1únl (q) º ln p (D q) = åln p ( x q)2q2q2

27、ëû22ii=1q= arg max l (q)50q4.3 參數(shù)估計方法：最大似然估計Ø 多元正態(tài)分布u 概率密度函數(shù)p(x) N (m, S)1exp- 1 (x - m)T S-1(x - m) 2，S) =p(d(2p) 212Su 情況2：均值𝜇、協(xié)方差矩陣未知(單變量推導(dǎo))éêùúú1 ( xn1(x -q1 ) = 0-q)åk =1k1qk極值條件q) = ê2ÑÞln p(x2êúk(x -q)2(xk -q1 )12&#

28、234;-+k1ún1n-åk =1+ åk =1ß2q2q2= 0ëû22qq222最大似然估計n()(q) m =q=å( )l q º ln p D q =ln p x1nn1nnåk =1åk =1(x - m)2s=q =2ix ,i=11k2kq= arg max l (q)51q4.3 參數(shù)估計方法：最大似然估計Ø 多元正態(tài)分布u 概率密度函數(shù)p(x) N (m, S)1exp- 1 (x - m)T S-1(x - m) 2，S) =p(d(2p) 212Su 情況2：

29、均值𝜇、協(xié)方差矩陣未知(多變量拓展)n= 1 åm =qx1knk =1n= 1 åS =q-m)(xk -m)T(xk2nk =1最大似然估計n()ln p x q)(å( )l q º ln p D q =ii=1q= arg max l (q)52q4.3 參數(shù)估計方法：最大似然估計Ø 多元正態(tài)分布u 概率密度函數(shù)p(x) N (m, S)112p(12(2p)S2u 情況1：均值未知，協(xié)方差矩陣已知n= 1 åm =qx1knk =1u 情況2：均值和協(xié)方差矩陣均未知1nnå xkk =1n1m=q

30、=S =q =å(x -m)(x-m)T12kknk =1534.3 參數(shù)估計方法：無偏估計Ø 多元正態(tài)分布u 概率密度函數(shù)p(x) N (m, S)112p(12(2p)S2u 協(xié)方差矩陣的最大似然估計n= 1 åS =q(x -m)(xk-m)T2knk =1樣本均值n -1é 12 ùnåe(x - x ) ú =s ¹ s22有偏估計êknnëk =1û最大似然估計值的期望544.3 參數(shù)估計方法：無偏估計Ø 多元正態(tài)分布u 概率密度函數(shù)p(x) N (m, S)11

31、2p(12(2p)S2u 協(xié)方差矩陣的漸進(jìn)無偏估計nC = 1å(x -m)(xk-m)Tkn -1k =155樣本協(xié)方差矩陣Sample covariance matrix4.3 參數(shù)估計方法Ø 第一部分小結(jié)：u 最大似然估計n()ln p x q)(å( )l q º ln p D q =ii=1q= arg max l (q)q分布假設(shè)的最大似然估計(情況1、2)u1nnå xkk =1n1m=q =S =q =å(x -m)(x -m)T12kknk =1u 無偏估計nC = 1å(xk - m)(x - m)Tkn

32、 -156k =14.3.2 參數(shù)估計方法：混合模型Ø模型（Gaussian Mixture M混合）多峰分布的假設(shè)擬合4.3.2 參數(shù)估計方法：混合模型Ø模型（Gaussian Mixture M混合）多峰分布的假設(shè)擬合4.3.2 參數(shù)估計方法：混合模型Ø模型（Gaussian Mixture M混合）多峰分布的假設(shè)擬合4.3.2 參數(shù)估計方法：混合模型Ø模型（Gaussian Mixture M混合）混合分布的概率密度估計問題：u1. 所有樣本都來自于K種類別，K已知；2. 每種類別的先驗(yàn)概率 P (w j ) 未知；p (x w j , j )，但參3. 類條件概率的數(shù)學(xué)形式已知數(shù) j 未知；4. 樣本類別未被標(biāo)記。K()()()åj =1p x =w, P wp xjjj4.3.2 參數(shù)估計方法：混合模型實(shí)際字符樣本特征分布的非MNIST樣本集訓(xùn)練樣本數(shù)：60,000性測試樣本數(shù)：10,0000312圖像規(guī)一化為28×28456789手寫數(shù)字09的特征分布在前二維主分量平面上的投影顯示614.3.2 參數(shù)估計方法：混合模型Ø 混合模型比模型具有更強(qiáng)的描述能力，但其需要的參數(shù)也成倍增加，實(shí)際中通常對節(jié)點(diǎn)方差矩陣結(jié)構(gòu)進(jìn)行約束KKåpkk