模式識別學習筆記

04-30

本文是對凌桑的自我修養--You are the Eternity關於模式識別博客的要點做總結，若有涉及版權問題，還望告知。

1. 模式和模式識別

人類在識別和分辨事物時，往往是在先驗知識和以往對此類事物的多個具體實例觀察基礎上產生的整體性質和特徵的認識。其實，每一種外界事物都可以看作是一種模式，人們對外界事物的識別，很大部分是把事物進行分類來完成的。中文的模和式是一個意思，簡單來說就是一種規律，識別主是對事物對象進行分門別類，模式識別可以看作對模式的區分和認識，是事物樣本到類別的映射；而英文中pattern則表示兩層意思，一層代表事物的模板或原形，第二層則是表徵事物特點的特徵或性狀組合。在模式識別學科中，模式可以看做是對象的組成成分或影響因素間存在的規律性關係，或者是因素間存在的確定性或隨機性規律的對象、過程或事件的集合。因此，也有人把模式成為模式類，模式識別也被稱作為模式分類（Pattern Classification）。

模式識別的專業術語：

樣本（sample），要研究對象的一個個體，注意與統計學中的不同，類似於統計學中的實例（instance）；
樣本集（sample set），樣本的集合，統計學中的樣本就是指樣本集；
類或類別（class），在所有樣本上定義的一個子集，處於同一類的樣本，我們說她們具有相同的模式；習慣性地，我們用w1，w2等來表示類別，兩類問題中也會用{0,1}或{-1,1}；
特徵（feature），表徵樣本的特點或性狀的量化集合，通常是數值表示（對於非數值形式，要轉化為數值特徵），也被稱作為屬性，如果是多個特徵，就組成了特徵向量（feature vector）。樣本的特徵構成了樣本特徵空間，空間的維數就是特徵的個數，每一個樣本就是特徵空間中的一個點。
已知樣本（known sample），已經事先知道類別的樣本；
未知樣本（unknown sample），類別標籤未知但特徵已知的樣本；

模式識別的方法主要有：模板匹配法，ANN法、基於知識的方法和基於數據的方法。基於知識的方法就是專家系統；基於數據的方法也就是基於統計的方法，即依據統計原理構造分類器，對未知樣本進行預測，是機器學習中研究最多的一個方向，也是模式識別採用的最主要方法。

模式識別可以劃分為有監督的和無監督的，類別已定的叫做監督分類，反之則無監督分類。常見的模式識別系統主要有：語音識別，說話人識別，OCR，複雜圖像中特定目標的識別，根據地震勘探數據對地下儲層性質的識別，利用基因表達數據進行癌症的分類等等。

典型的模式識別系統主要分為四個部分：對原始數據的獲取和預處理，特徵提取與特徵選擇，分類或聚類，後處理。

2. 貝葉斯決策

舉個簡單例子，假設有一枚未知面值的硬幣，我們來猜是多少錢的硬幣。顯然我們會猜測硬幣出現的概率更大的面值。這就用到了貝葉斯決策中的先驗概率（priori probability），即在沒有對樣本進行任何觀測情況下的概率。接下來，我們可以增加一些觀察值，比如硬幣的重量。假設硬幣重量記為x，然後計算已知重量的情況下屬於不同類別的概率，這就是所謂的後驗概率（posterior probability），分別記作 $P(w_{1}),P(w_{2} )$ 。同樣可以根據後驗概率的大小判斷類別。後驗概率的計算就就需要用到貝葉斯公式：

$P(w_{i}|x)=p(x,w_{i})/p(x)=p(x|w_{i})P(w_{i})/p(x), i=1,2$

其中， $P(w_{i})$ 是先驗概率， $p(x,w_{i})$ 是聯合概率密度， $p(x)$ 是兩類硬幣重量的總體概率密度， $p(x|w_{i})$ 是第i類重量的概率密度，稱作條件概率密度。利用貝葉斯公式，後驗概率可以轉化為先驗概率與類條件概率密度的乘積，再用概率密度進行歸一化（一般而言，總體密度對於各個類別是一樣的，可以忽略分母）。先驗概率可以根據兩類硬幣的流通比例來獲得，類條件概率密度則需要對應類別一定數量的訓練樣本估計得到。

貝葉斯決策的幾種常用標準：最小錯誤率準則、最小風險準則、最小最大決策準則。

最小錯誤率準則。我們分類時最希望分類錯誤得到最低，其對應的就是最小錯誤率貝葉斯決策： $minP(e)=int_{}^{} P(e|x)p(x)dx=E[P(e|x)]$ 。而我們通常所說的貝葉斯決策均是指最小錯誤率貝葉斯決策。

最小風險貝葉斯：所謂最小風險貝葉斯決策，就是各種錯誤決策所造成不同損失時，選擇造成損失（風險）最小的決策。主要針對一些特殊情況，比如癌細胞的判別，相對於錯誤率，更關心判別錯誤帶來的風險。基本思路和最小錯誤準則差不多，但最小風險貝葉斯決策中用到的決策表需要我們人為確定，而決策表設計的不同可能導致不同決策結果。

3. 概率密度函數（pdf）

貝葉斯決策的後驗概率可以由先驗概率和類條件概率密度兩個量估計得到。先驗概率的估計可以採用訓練數據中各類出現的頻率估計得到，也可以依靠經驗獲得。而類條件概率密度的估計相對難一些，因此對於它的估計是貝葉斯決策的重點。沒有特別說明，我們假定所有樣本都來自於同一類別，即利用同一類的樣本來估計本類的類條件概率密度（簡稱PDF）。

PDF估計主要兩類，參數估計和非參數估計。前者PDF形式確定，部分或全部參數不確定，需要用樣本來估計這些參數，主要方法有最大似然估計和貝葉斯估計；後者不僅參數未知，PDF形式也未知，也就是說樣本不符合任何一種分布模型，我們不能夠單單估計出參數，而是首要估計出PDF的數值化模型。

最大似然估計：在參數空間中找到一個能夠使得似然函數 $L( heta )$ 極大化的 $heta$ 值，這個值當作最大似然估計量，最大化的方法是求偏導。貝葉斯估計在很多實際情況下與最大似然估計是相同的，但他們處理問題的角度不同，根本區別在於前者將待估計的參數當作一個確定量，而後者將其當作一個隨機變數。貝葉斯學習（Bayesian Learning）是利用貝葉斯估計對PDF進行迭代估計的一種學習策略。在貝葉斯估計中，我們是把對參數的估計當作一個貝葉斯決策，不同的是決策結果不是離散的類別，而是參數的值，並且是在一個連續的參數空間作決策。

註：貝葉斯估計本來的目的是估計概率密度函數 $p(x| heta)$ ，當問題的PDF形式已知時，才轉化為估計參數。另外，在估計參數時，與最大似然估計不同的是，貝葉斯估計並非直接把似然函數最大或者後驗概率最大值當作對樣本PDF參數的估計，而是考慮了所有可能的參數值，並用他們的似然函數作為加權平均一個對參數的估計值。

對於PDF的參數估計方法（最大似然估計和貝葉斯估計）需要有確定形式的PDF，而很多實際情況下並不能知道PDF的確切形式，只能通過所有樣本對整個PDF進行估計，而且這種估計只能是利用數值方法求解。通俗地講，如果參數估計是從指定的某一類函數中選擇一個作為目標估計，那麼非參數估計就是從所有可能的函數中找到一個最合適的選擇。

非參數估計的方法主要有三種：直方圖法、k近鄰法和核函數法（Parzen窗法或核密度法）。直方圖法的目的是求出每個樣本的概率密度所服從的函數分布，即求出p(x)的估計量（不考慮類別問題，假設所有樣本都是同一類的），影響估計結果的問題就是bin的體積V的選擇。k近鄰方法的基本思想是在樣本x的取值範圍內，把個取值作為一個bin的中心點，根據總樣本確定k，再來規定每個bin內落入的樣本個數，這樣在求p(x)的估計量時，找到當前中心點最近的k個樣本放進到bin中。k近鄰法容易陷入到維數災難中，尤其是在x維度較高時。Parzen窗法是一種用核函數來估計當前樣本x處的概率密度方法，可以看作是一種在x的取值空間內用核函數對樣本進行插值的過程。

概率密度函數的非參數估計要求樣本數量足夠多，而且足夠多的樣本總能夠保證收斂於任何密度函數，但計算量和存儲量也相對較大。而參數估計則更適合於小樣本的情況，並且對密度函數要求有充分的先驗知識，參數估計可能會達到更好的估計效果。

4. 線性分類器及判別函數

對於統計決策中的貝葉斯決策，一般根據樣本進行PDF估計，再根據估計出的PDF來求分類面。但模式識別的目的並非估計PDF，而是在特徵空間中找到各類的分界線或分界面。因此，可以直接根據樣本求出分類面，從而省略估計PDF的步驟。

分類器設計的三大基本要素：判別函數的類型（即從什麼類型的差別函數中求分類面）、分類器設計的最優函數（一般就是確定函數中的某些特定參數）、搜索最優函數參數。用數學的形式來描述：在判別函數（集）{ ${ g(alpha,alpha in Lambda) }$ }中確定參數 $alpha^{*}$ ，使得準則函數 $L(alpha)$ 最大化或者最小化。

分類器設計中判別函數最為關鍵，而一般情況下線性分類器只能是次優分類器，但由於設計簡單，而且在一些特殊情況（例如樣本分布服從正態分布且各類協方差矩陣相等）下，判別函數可以是最小錯誤率呀最小風險意義下的最優分類器。線性判別函數應用廣泛，尤其是在有限樣本的情況下甚至優於線性分類器。

對於判別函數的表達，兩類的情況： $g(x)=w^{T}x+w_{0}$ ，很明顯w是分類面的法向量，決定的決策面H的方向，而判別函數g(x)可以看成樣本特徵空間中某一點x到分類面H的距離的一種代數度量。

線性判別分析（Linear Discriminant Analysis）由Fisher與1936年提出的，是最具代表性的線性差別方法之一，簡稱LDA，又稱作Fisher判別。對於兩類問題，區別的方法就是找到一條適合的分界線，如果將所有樣本都投影到這條分界線的垂直向量上，能夠很容易找到一個閾值點將它們分開，而那條最合適的分界線剛好經過這個閾值點。因此，我們可以倒過來思考，為了找到分界線，可以通過將樣本點做投影（關鍵是確定投影的方向），找到合適的閾值，再對這個閾值點做法向量就可以實現。Fisher判別的思想：選擇一個最合適的投影方向，使得投影后兩類樣本相隔儘可能遠，同時保證類內部的樣本儘可能緊湊，所以Fisher判別的關鍵是尋找投影方向。

為了衡量各類內樣本間的離散度（使其值儘可能小），需要定義類內離散度矩陣（within-class scatter matrix）和總的類內離散矩陣（pooled within-class scatter matrix）。而類間離散度（between-class scatter matrix）則越大越好。

5. 感知器

感知器是一種可以直接獲得線性差別函數 $g(x)=w^{T}x+w_{0}$ 的線性分類方法，是在樣本線性可分的前提下使用的。對於一組線性可分的樣本 $y_{1},y_{2},...,y_{n}$ ，如果權向量滿足 $alpha^{T}y_{i}>0$ ，則 $alpha$ 就是權值空間的解向量，所有的解向量組合的區域就是解區。由於雜訊和數值誤差因素的影響，引入餘量b，則 $alpha^{T}y_{i}>b$ 。為了求解向量，利用錯誤分類的樣本求和運算定義懲罰函數： $J(alpha)=sum_{}^{}{-alpha^{T}y_{i}}$ ，這就是感知器線性可分樣本下的準則函數。

感知器的求解就是找到一個解向量，使得懲罰函數最小化，對於錯分的樣本都滿足 $alpha^{T}y_{i}leq 0$ ，顯然當其值為0時最小，可以採用機器學習中常用的梯度下降法迭代計算。

6. 范化能力

模式識別是一種基於數據的機器學習，學習的目的不僅是對訓練樣本正確分類，還要能夠正確分類測試樣本，這種能力叫做推廣能力或范化能力。機器學習的范化能力評估，設某一樣本x，其真實標籤y，用判別函數f(x,w)來估計y，估計帶來的損失為L(y,f(x,w))，則某個w下所有訓練樣本的決策損失為： $R_{emp}(w)=frac{1}{N} sum_{N}^{i=1}L(y_{i},f(x_{i},w))$ ，稱作經驗風險，而我們更加關心的是測試樣本在某個w下的風險： $R(w)=int_{}^{} L(y_{i},f(x_{i},w))dF(x,y)$ ，稱作期望風險，其中 $F(x,y)$ 是所有可能樣本及其類別標籤的聯合概率分布模型。而Vapnik指出，有限樣本下，經驗風險與期望風險是有差別的，後者可能大於前者，兩者之間滿足一個規律： $R(w)leq R_{emp}(w)+varphi (frac{h}{N} )$ ，而右邊第二項是一個關鍵項，表示置信範圍，與h呈正比，而這裡的h很重要，它就是著名的VC維，反映了機器的複雜度。根據這個規律可以得出：在訓練誤差相同的情況下，機器的VC維越低，期望風險與經驗風險差別就越小，而機器的推廣範圍也就越好。

參考：

凌桑的自我修養--You are the Eternity