統(tǒng)計分類器及學(xué)習(xí)

第四章 統(tǒng)計分類器及學(xué)習(xí)在距離分類器和判別函數(shù)分類器中， 我們都是把模式看作是 N維歐氏空間中的一個點(diǎn)，而且統(tǒng)一類別的模式在空間中聚集在一定的區(qū)域， 不同模式的區(qū)域在空間中具有一定的分離性。在本章所討論的統(tǒng)計分類器中， 我們?nèi)匀徽J(rèn)為模式是歐氏空間中的一個點(diǎn)， 但是每一類模式不是分布在空間中的一個確定區(qū)域， 而是可能分布在整個空間， 只不過空間中每一點(diǎn)屬于某一類的概率不同，屬于這一類的可能性大一些，屬于另一類的可能性小一些。我們可以利用這樣的性質(zhì)來建立統(tǒng)計分類器。4.1概率論基本知識本章中我們使用的主要數(shù)學(xué)工具是概率論，因此先來復(fù)習(xí)一些概率論的知識。一、事件自然界的事件可以分為確定性事件和不確定性事件，確定性和不確定性主要體現(xiàn)在事件的概念和發(fā)生上。概念是確定的，發(fā)生也是確定的，這是確定事件，例如在標(biāo)準(zhǔn)大氣壓下，水加熱到100度就會開；概念是確定的，發(fā)生是不確定的，稱為隨機(jī)事件，例如擲骰子事件；還有一些事件的概念本身就不確定，這類事件稱為模糊事件，例如年青人的概念是不確定的，遇到的人是年青人的事件就是模糊事件。對模糊事件的處理，在模式識別中也占有重要的地位，本章中我們只討論隨機(jī)事件。二、隨機(jī)變量隨機(jī)事件的數(shù)量表示稱為隨機(jī)變量。取值為離散的稱為離散隨機(jī)變量，例如擲硬幣，只可能出現(xiàn)正、反兩面，分別用0和1表示；取值為連續(xù)的稱為連續(xù)隨機(jī)變量，例如測量物體的長度。三、頻率和概率設(shè)A為聯(lián)系于某個試驗的隨機(jī)事件，試驗在相同的條件下重復(fù) N次，其中M次A事件發(fā)生，則 A發(fā)生的頻率為 MN，計為： fN A MN。由于A事件的隨機(jī)性， A的頻率也是一個隨機(jī)變量。但是當(dāng) N很大時，頻率會趨向一個穩(wěn)定值，稱為 A的概率，即 PA limfN A。N四、聯(lián)合概率和條件概率聯(lián)合概率：設(shè)A,B是兩個隨機(jī)事件， A和B同時發(fā)生的概率稱為聯(lián)合概率， 記為：PA,B；條件概率：在B事件發(fā)生的條件下， A事件發(fā)生的概率稱為條件概率，記為： PAB；乘法定理：條件概率與聯(lián)合概率之間存在如下關(guān)系： PAB PA,B PB；五、概率密度函數(shù)概率分布函數(shù)：設(shè)X為連續(xù)型隨機(jī)變量，定義分布函數(shù)FxPXx；px使得Fxxx為X概率密度函數(shù)：如果存在一個非負(fù)函數(shù)ptdt成立，則稱p的概率密度函數(shù)。同時有：Fxpx，PXxpxdx。六、全概公式和貝葉斯公式互不相容事件：如果試驗時，若干個隨機(jī)事件中任何兩個事件都不可能同時發(fā)生，則稱它們是互不相容的。全概公式：若事件B只能與兩兩不相容的事件A1,A2,,AN之一同時發(fā)生，則有：NPB PAi PBAii1PBAPA貝葉斯公式：PABPBpBAPA當(dāng)B為連續(xù)隨機(jī)變量， A為離散隨機(jī)變量時： PAB 。pB4.2最小錯誤率準(zhǔn)則貝葉斯分類器在下面的討論中， 我們都假設(shè)

X為類別未知樣本，用N維特征矢量來表示， 現(xiàn)有

M

個類別

1,

2,

,

M，先驗概率

P

i

和類條件概率

PX

i

已知。我們要根據(jù)先驗概率和條件概率將

X

分類到某一類中去。一、最小錯誤率準(zhǔn)則進(jìn)行分類就必須要有一個分類準(zhǔn)則。由于每一個類別都是分布在整個空間中，因此X有可能是任何一個類別，現(xiàn)在我們把它判別為某一類，必然要帶來錯誤，一般來情況下我們希望這種錯誤的概率越小越好。將 X分類為 i類所產(chǎn)生的誤判概率為：M MPie P j X P j X P i X 1 P i Xj 1 j 1j i要使得判別的錯誤率最小，也就是尋找一個類別 i，使得Pi e，這就等價于后驗概率P i X 最大。然而后驗概率 P i X 我們并不知道，但是可以利用貝葉斯公式轉(zhuǎn)換為先驗概率和類條件概率：PXiPiPiXPX由于PX每一類都相同，對比較大小沒有影響，因此可以取判別函數(shù)：di X PX i P i判別規(guī)則為：若i0argmaxdiX，則Xi01iM這就是貝葉斯分類器的判別準(zhǔn)則。下面來看一下 M 2的情況，判別準(zhǔn)則可以寫成：d1Xd2X,X1d2Xd1X,X2進(jìn)一步可以寫成：PX1P1PX2P2,XPX1P1PX2P2,X令：l12XPX1，21P2，則有：PX2P1l12X21,X1l12X21,X2其中：l12稱為似然比，21稱為似然比的閾值。例4.1二、貝葉斯分類器的錯誤率估計有了貝葉斯分類器的判決準(zhǔn)則后，我們還可以計算出誤判的概率。

12以一維特征和兩類別情況為例來進(jìn)行說明。錯誤率 Pe是有兩部分產(chǎn)生的，一部分是X實(shí)際應(yīng)該屬于 1而將X誤判為 2類（對應(yīng)于右面部分），一部分X實(shí)際應(yīng)該屬于 2類而被誤判為 1類（對應(yīng)左面部分）。因此有：tPepx1P1dxpx2P2dxt4.3最小平均風(fēng)險準(zhǔn)則貝葉斯分類器前面我們以最小錯誤率為準(zhǔn)則建立的貝葉斯分類器， 然而對某些問題來說這樣的準(zhǔn)則并不適合。這是因為每次誤判所帶來的后果并不一樣， 有一些類別被誤判的后果非常嚴(yán)重， 而另一些類別被誤判的后果卻并不嚴(yán)重， 例如對于癌癥診斷問題， 如果一個癌癥患者被誤判為正常，那么后果非常嚴(yán)重，有可能耽誤治療； 而一個正常人被誤診為患有癌癥，后果并不很嚴(yán)重，隨著進(jìn)一步的診斷，可以改變這種誤判。下面我們就來介紹一種依據(jù)最小平均風(fēng)險準(zhǔn)則的貝葉斯分類器。設(shè)由M個類別， 1, 2, , M。首先我們需要根據(jù)實(shí)際問題定義一組數(shù)據(jù) Lij，表示將 i類的樣本誤判為 j類的代價，這應(yīng)該是一個 M M的矩陣。然后我們可以用下面的公式計算將未知模式 X判別為 j類的平均風(fēng)險：Mj X LijPiXi1其中LijP i X為用Lij加權(quán)的后驗概率。因為當(dāng)我們將 X分類為 j時，它有可能是類的任何一類，因此總的平均風(fēng)險就是對加權(quán)后的后驗概率求和。我們的判決準(zhǔn)則應(yīng)該是選擇一個平均風(fēng)險最小的類別作為輸出的決策類別。因此可以構(gòu)造判別函數(shù)：dj X

j X。現(xiàn)在的問題同最小錯誤率準(zhǔn)則一樣，我們并不知道后驗概率 P i X ，而是已知先驗概率P i 和條件概率 PX i ，因此我們還需要使用貝葉斯公式將后驗概率轉(zhuǎn)換為先驗概率：1j XPX

MLijPX i P ii11因為 是公共項，對比較大小沒有影響，因此可以舍去：XMj X LijPXiPii1現(xiàn)在還是看一下兩類問題的情況：將X判別為 1類的平均風(fēng)險為：1 X L11PX1P1 L21PX2P 2將X判別為 2類的平均風(fēng)險為：2XL12PX1P1L22PX2P2當(dāng)1X2X時，判別X為1類；當(dāng)1X2X時，判別X為2類。以第一種情況進(jìn)行推導(dǎo)：L11PX1P1L21PX2P2L12PX1P1L22PX2P2即：L21L22PX2P2L12L11PX1P1XX

12

PP

2 L21 L221 L12 L11定義似然比：l12PX1PX，定義閾值：21PX2P這樣就可以得到最小平均風(fēng)險準(zhǔn)則下的貝葉斯判決條件：若l12X21，則X1；若l12X21，則X2。例4.2

2L21L22。1L12L114.4貝葉斯分類器的學(xué)習(xí)貝葉斯分類器的工作原理非常簡單，完全是根據(jù)待識模式 X對各個類別的后驗概率P iX 來分類的，判別為后驗概率最大的類別。后驗概率可以根據(jù)貝葉斯公式轉(zhuǎn)化為先驗概率Pi和類條件概率PXi。下面我們來研究貝葉斯分類器的學(xué)習(xí)問題，也就是說如何通過訓(xùn)練樣本集來得到Pi和PXi的問題。對于一個具體問題來說，Pi和PXi我們并不知道，而是已知各個類別的訓(xùn)練樣本集合：Xiiii，i1,2,ij個訓(xùn)練X1,X2,,XNi,M。Xj表示第i個類別的第樣本，第i類共有Ni個訓(xùn)練樣本。一般來說P i 比較容易得到，因為類別數(shù)是有限的，可以通過統(tǒng)計多個樣本得到各個類別出現(xiàn)的幾率，用它來近似概率，比如可以根據(jù)大量病例統(tǒng)計出在普通人中癌癥的患病率，也可以根據(jù)先驗知識來確定，比如擲兩枚樣幣同時出現(xiàn)正面的概率。然而類條件概率 PX i 的獲得卻往往是一個比較困難的事情。 如果X是離散型的時候，問題相對來說還比較簡單一些， 如果樣本量足夠多的話， 可以分別統(tǒng)計出各個類別中出現(xiàn)某個特征矢量的幾率。然而當(dāng) X為一個連續(xù)型的特征是矢量時，問題就會非常復(fù)雜。因為這種情況下我們要找到的是條件概率密度函數(shù)pXi，而概率密度函數(shù)可以是任意形式，而我們的訓(xùn)練樣本的數(shù)量畢竟是有限的，因此不可能很好的擬合出概率密度函數(shù)。因此我們往往采用一些簡化的辦法。這些簡化辦法中最重要的一點(diǎn)就是要對所求的概率密度函數(shù)的形式作出一定的限制，假設(shè)概率密度函數(shù)符合某種概率模型，而概率模型是可以用一組參數(shù)來描述的，這樣我們就可以使用數(shù)理統(tǒng)計的方法，利用訓(xùn)練樣本來估計這組參數(shù)，有了模型參數(shù)，就可以得到概率密度數(shù)。下面介紹幾種常用的概率模型及其估計方法。一、高斯模型（GaussianModel）高斯模型也稱為正態(tài)分布模型，是一種最常見的概率模型，自然界中很多物理現(xiàn)象都符合正態(tài)分布假設(shè)，比如說我們對一個物理量的測量。N維的正態(tài)分布函數(shù)可以表示為：pXi1exp1T1XmiN212XmiCi2Ci2正態(tài)分布函數(shù)完全可以有兩個參數(shù)來描述：均值矢量：mi EiX；協(xié)方差矩陣：CiEiXmiXmiTmimiTEiXXT正態(tài)分布的參數(shù)的估計方法非常簡單，根據(jù)數(shù)理統(tǒng)計的理論，雖然均值和協(xié)方差都需要求一個數(shù)學(xué)期望，也就是當(dāng)數(shù)量N趨近于無窮大時求平均，但是當(dāng)樣本量足夠大時可以用有限樣本的算術(shù)平均來近似，即：1NimiXjiNij11NimiXjiT1NiXjiXjiTCiXjimimimTiNij1Nij1例4.3二、混合高斯模型

（MixedGaussianModel,GMM

）正態(tài)分布模型的訓(xùn)練和使用非常簡單， 然而對于一個實(shí)際問題來說， 特征的分布函數(shù)并不一定滿足正態(tài)分布，其分布形式可能非常復(fù)雜，并且往往呈現(xiàn)一種多峰情況，如下圖所示。這時再用高斯模型來描述它的概率密度函數(shù)就會產(chǎn)生很大的誤差。為了描述這些復(fù)雜的分布函數(shù)，我們可以采用簡單函數(shù)的線性組合來逼近復(fù)雜函數(shù)。GMM模型就是用多個高斯函數(shù)的線性組合來描述復(fù)雜的分布函數(shù)。我們可以用Nm,C來表示一個高斯分布函數(shù)，m為均值矢量，C為協(xié)方差矩陣。那么一個GMM概率密度函數(shù)可以表示為：KKpXiajiNmji,Cji，其中aji1j1j1上述GMM模型是由K各高斯模型線性組合而成， aj為組合系數(shù)。例如下圖就是由兩個高斯函數(shù)組合而成：px 0.7N 10,2 0.3N(5,3)GMM

分布函數(shù)的訓(xùn)練要比單個高斯模型復(fù)雜得多，這里需要訓(xùn)練的參數(shù)有

aj，mj和Cj，而K值是要預(yù)先確定的。 GMMAlgorithm)，稱為期望最大化算法

的訓(xùn)練一般采用。

EM迭代算法

(ExpectationMaximization三、隱含

Markov

模型 （HiddenMarkovModel,HMM

）在實(shí)際問題中，有時我們遇到的識別對象是連續(xù)信號， 例如語音信號。下圖分別顯示了三個元音的一段采樣信號， ’a’,‘o’,‘e’。這樣的連續(xù)信號， 如果還是用特征矢量來描述， 無法反映出信號之間的時間相關(guān)性， 往往需要用一個隨機(jī)過程來描述。 對于連續(xù)信號，一般是采用分段來處理的， 例如以512點(diǎn)為一段，稱為一幀信號。在每一幀信號中抽取出特征，構(gòu)成特征矢量，例如語音信號中可以抽取Fourier變換系數(shù)，信號通過零點(diǎn)的次數(shù)等等作為這一幀的特征。這樣一段信號就可以用一個特征矢量的序列來表示，一般稱為觀察序列：O1,O2,,ON其中的

Oi稱為觀察值，是一個特征矢量。如果我們要對這樣的模式構(gòu)造貝葉斯分類器，

也要知道每個類別的條件概率

PO

i

，然而對于這樣的觀察序列，顯然無法用高斯模型或高斯混合模型來描述，需要有一個新的模型—隱含Markov模型來描述。對每一個類別建立一個HMM，有這樣一個HMM可以計算出觀察序列

O在每個類別的條件概率

PO

i

，再結(jié)合類的先驗概率

P

i

，就可以構(gòu)造出一個貝葉斯分類器。下面簡單介紹一下 HMM的基本知識，在隨機(jī)過程中，每一時刻的取值只與之前的過程有關(guān)，而與之后的過程無關(guān)，這樣的過程稱為 Markov過程，只與前一時刻的值有關(guān)，則稱為一階Markov過程。HMM 的模型結(jié)構(gòu)可以多種多樣，下面先以語音識別中常用“左 -右”模型為例介紹一下。1

2

3每一個HMM 都是由若干個隱狀態(tài)構(gòu)成的， 隱狀態(tài)之間可以進(jìn)行轉(zhuǎn)移， 所以HMM是一個狀態(tài)轉(zhuǎn)移模型。這里表示的三個隱狀態(tài)的 HMM，每一個狀態(tài)在下一時刻可以轉(zhuǎn)移到下一個狀態(tài)，也可以轉(zhuǎn)移到自身狀態(tài)。隱狀態(tài)是不可見的，我們所能夠看見的是觀察序列， 每一個隱狀態(tài)可以輸出任何觀察值，只不過輸出每個觀察值得概率不同。 例如在時刻t，模型處于第i個狀態(tài)，這時第i個狀態(tài)輸出Ot的概率可以表示為：

bi

Ot

。同時第

i

個狀態(tài)在

t

1時刻有可能轉(zhuǎn)移到多個狀態(tài)，轉(zhuǎn)移到每個狀態(tài)的概率不同，例如由第i個狀態(tài)轉(zhuǎn)移到第j個狀態(tài)的概率為a。ij同時HMM開始的第一個狀態(tài)也是不確定的，有可能開始于任何狀態(tài)，開始于第i個狀態(tài)的概率可以表示為：i。這樣一個HMM就可以用一個三元組表示：A,B,π其中Aaij為一個MM的方陣，稱為狀態(tài)轉(zhuǎn)移矩陣，M為模型的狀態(tài)數(shù)。BbiO為由一組M個概率密度函數(shù)構(gòu)成的矢量，πi為M維矢量，稱為初始概率分布。明顯應(yīng)該有：MMi1，aij1,biOdO1i1j1O現(xiàn)在我們關(guān)心的是兩個問題：識別問題和訓(xùn)練問題。識別問題識別問題可表述為如果我們已知一個

HMM

模型

A,B,π，如何計算該模型輸出待識模式觀察序列

O的概率：

PO

。因為HMM是一個狀態(tài)轉(zhuǎn)移模型， 每一個時刻處于一個狀態(tài)， 每個狀態(tài)可以輸出任何的觀察值，因此每一種可能的狀態(tài)轉(zhuǎn)移過程都可能輸出這