貝葉斯分類器解讀
寫在前面,對應部落格地址:
金良的部落格 | Jinliang Blog
1。 貝葉斯決策論
首先介紹
貝葉斯決策論
的定義:
貝葉斯決策論是機率框架下實施決策的基本方法。
首先,根據定義提取兩個關鍵詞:
機率框架
、
實施決策
我認為學習一個東西最重要要清楚它是做什麼的,前提條件是什麼。
根據關鍵詞,我們可知貝葉斯決策論是用來做決策的(透過名字也知道,廢話~),它的前提條件是機率已知。
以分類任務為例,在所有機率都已知的理想情況下,貝葉斯決策論用來基於這些機率來選擇最優的類別標記。
下面以多分類任務做具體分析:
目前分類任務有N種可能的類別標記,即
;
表示將一個真實標記為
的樣本錯誤分類為
標記的損失;
通過後驗機率
可獲得樣本
分類為
所產生的
期望損失
,即在樣本
上的
條件風險
:
公式1-1求的是在樣本
下分類為
的條件損失,其實就是遍歷所有樣本,求取每個樣本被分類為類別
的損失,再求和。
公式1-1求得分類為
的風險,作為多分類任務,我們的目標就是分類準確,那麼反過來說就是降低總體期望損失或者說是總體風險,總體風險公式如下:
根據公式1-2所示,若單個類別的條件風險
最小,那麼總體風險
也會最小。
其實到此就總結出了
貝葉斯判別準則:
為最小化總體風險,只需在每個樣本上選擇能使條件風險
最小的類別標記,即:
公式1-3中的
稱為
貝葉斯最優分類器
,對應的總體風險
稱為
貝葉斯風險
。
其中
反映了分類器所能達到的最好效能,即透過機器學習方法所學習的模型精度的理論上限,我們稱為貝葉斯最優。在深度學習中,判斷一個模型欠擬合多一些還是過擬合多一些,主要透過貝葉斯最優和模型在開發集和測試集上的精度。
上述分析針對多分類任務的概述,下面我們再具體一點:
我們增加了當前分類任務的目標:最小化分類錯誤率
那麼我們的
可設定為0/1損失函式(在支援向量機中涉及到):
根據公式1-4,我們修改一下公式1-1:
呀,是不是變化好多,其實根據公式1-4可知,只有當i=j的時候,
為0,其餘情況下相當於每個類別機率的和。那麼樣本為所有類別的和為1,我們減去為0的情況,就是條件風險了,具體為公式1-5所示。
進而修改公式1-3,求取貝葉斯最優分類器:
公式1-6最終推匯出,選擇後驗機率最大的類別標記即為貝葉斯最優分類器。
是不是感覺白推導了那麼多,這不就是我們的常識~
既然回到了我們的常識上,那麼我們肯定知道後驗機率
一般是木有的!
所以想要透過貝葉斯判定準則(也就是上面那一套)最小化決策風險,那麼我們需要求得後驗機率
。
又所以扯了一大頓,回到我們的真實問題:
基於有限的訓練樣本集儘可能準確的估計後驗機率
目前把解決上述問題的所有方法分為兩種:
判別式模型:
給定訓練樣本
,直接建模
來預測
。
決策樹、BP神經網路、支援向量機
生成式模型:
先對聯合機率分佈
建模,然後再求得
。
對判別式模型比較熟悉,因為之前講的決策樹、BP神經網路、支援向量機方法都屬於判別式模型,下面,我們針對生成式模型做具體分析:
根據生成式模型的概念,得出如下公式:
根據公式1-7,我們來分析我們需要求解的問題到底是什麼。
是類先驗機率;
是樣本
相對於類別
的類條件機率,也叫“
似然
”(說法很高大上);
是用於歸一化的證據因子(想想也知道它對於所有類都是不變的,因此忽略它)。
因此,我們未知的就是類先驗機率
與似然
了。
關於類先驗機率
:
它的直觀理解就是某個類別在空間中各個類別中所佔的比例;
在訓練集充足且樣本獨立同分布時,我們可以根據各個樣本出現的頻率進行估計。
因此,,,解決了!(還有似然呢,聽這高大上的名字,肯定是大BOSS了)
關於似然
我們同樣按照出現的頻率估計,發現與類先驗機率不同,同樣的方法不成立!
原因是
設計到所有屬性的聯合值,解釋一下,如果每個樣本有有d個屬性,每個屬性都是二值的,那麼所有的可能性為
種,一般情況下,我們的訓練集覆蓋不了全部的可能性,因此不能通過出現頻率估計。
也許某些人說可以透過將未出現的設為0,但是這是不準確的,因為未被觀測到和出現機率為0是不一樣的。
所以,第一節就是為了引出這個問題,
如何求解或者估計似然
???
2。 極大似然估計
上一節我們引出問題:如何求解類條件機率,也就是似然
。
估計似然的常用策略或者說是方法為:先假定其具有某種確定的機率分佈形式,再基於訓練樣本對機率分佈的引數進行估計。
既然如此,那我們就按照常用方法來哈!
假設似然
具有確定性的機率分佈形式並且被引數向量
唯一確定,那麼我們的任務就是利用訓練集估計引數
。
問題轉換成引數估計,看一下常用的引數估計方法:
頻率主義學派:引數未知但是確實存在,因此可使用最佳化似然函式等準則確定引數
貝葉斯學派:引數屬於為觀測的隨即變數,其本身也有分佈,因此假定引數服從一個先驗分佈,然後再根據訓練集計算引數的後驗分佈(說實話,不太懂 )
本節的主題是
極大似然估計
,它是頻率主義學派的方法,簡稱
MLE
,是根據資料取樣來估計機率分佈引數的經典方法。
令
表示資料集D中的第
類樣本組成的集合,則引數
對於資料集
的似然是:
對
行極大似然估計,就是去尋找能夠最大化似然
的引數
,即
。
直觀理解,就是在
的所有取值中,找到能使資料出現機率最大的值。
公式2-1中的連乘操作容易造成下溢,因此我們將其替換成對數似然:
那麼引數
的極大似然估計
為
以上都是對離散屬性的處理,在連續屬性下,假設機率密度函式
,則引數
和
的極大似然估計為:
透過公式2-4,可以發現在連續情況下,透過極大似然法求得的正態分佈均值就是樣本均值,方差就是
的均值,這顯然就是計算均值與方差的流程方法。
上述方法透過假定其具有某種確定的機率性分佈,然後對其引數進行估計,雖然這使得求解過程相對簡單,但是估計結果的準確性嚴重依賴於
所假設的機率分佈形式是否符合潛在的真實資料分佈
。
在真實的應用中,想要作出更能接近資料分佈規律的假設,需要在一定程度上利用關於任務本身的經驗知識,我們可以稱其為先驗知識,不然僅根據我們猜測的機率分佈,效果往往並不好。
3。 樸素貝葉斯分類器
問題:透過公式1-7可知,需要估計類條件機率,也就是似然,但是直接從有限的訓練樣本中估計是不可能的。
原因是:基於有限的樣本估計聯合機率,在計算上與遭遇組合爆炸的問題,在資料上也會遇到樣本稀疏問題,並且隨著屬性值的增加越嚴重。怎麼理解呢,就是咱們估計的類條件機率,首先需要計算所有屬性值的組合問題,這就是很耗費資源的一件事;並且在將屬性值的所有組合計算完成後,會發現大部分的屬性組合根本沒有樣本,因此會遇到樣本稀疏問題。
於是,方法總比困難多~,樸素貝葉斯分類器採用
屬性條件獨立性假設
,即假設所有屬性相互獨立,每個屬性獨立的對分類結果產生影響。
在屬性條件獨立性假設的思想下,我們改寫1-7:
公式1-7中,
為屬性的數目,
為在第i個屬性上的取值。
因為
對所有樣本是一樣的,我們根據公式1-7,求解在屬性條件獨立性假設下的貝葉斯最優分類器,即
樸素貝葉斯最優分類器
:
公式3-2就是樸素貝葉斯最優分類器的表示式,實際上是公式3-1和1-6的組合。
擁有的核心思想,那麼可以推匯出樸素貝葉斯分類器的
訓練過程
就是:
根據樣本估計類先驗機率
,並且估計每個屬性的類條件機率
。
如果
表示訓練集
中第
類樣本組成的集合,那麼可容易的估計出類先驗機率:
類先驗機率能夠簡單求解,下面是類條件機率:
針對離散屬性而言,令
表示在
中第
個屬性取值為
的樣本組成的集合,那麼類條件機率
為:
針對連續屬性而言,可考慮機率密度函式,假定
,其中
分別是第
類樣本在第
個屬性上取值的均值和方差,則有:
但是在實際使用中,會出現類先驗機率和類條件機率為0的情況,即當某個類別或者某個類別中的某個屬性沒有出現時,按照公式3-2所示,若有一項為0,那麼得到的機率就為0,這顯然是不合理的。
因此,需要對估計類先驗機率和類條件機率進行修正,方法為:
拉普拉斯修正
令
表示
中可能出現的類別的數量,
表示第
個屬性可能的取值數量,得到引入拉普拉斯修正後的
和
:
拉普拉斯修正的好處:
避免了因資料集不充分引起的機率估計為0的問題
在資料量變大時,修正引入的先驗(即
和
)的影響會逐漸變得可忽略,使得估計值逐漸趨向於真實值。
樸素貝葉斯分類的多種使用方式:
若對預測速率要求高,則可以提前將所有的類先驗機率
和類條件機率
估計好,在測試時,直接透過查表的方式進行計算判別
若任務資料更替頻繁,那就進行“懶惰訓練”,其實就是上一種方式的相反情況,不提前計算所有機率,在測試時需要使用的時候再進行臨時計算。
若資料不斷增加,則可將上述兩種方式結合,提前估計好所有的機率,在資料增加後,對增加的資料所涉及的機率進行增量更新,然後再進行預測。
4。 半樸素貝葉斯分類器
在樸素貝葉斯分類器的引入過程中,由於類條件機率因為組合屬性的原因導致很難算(具體看樸素貝葉斯分類器小節開頭),因此提出了“屬性條件獨立性假設”,但是這個假設在真實的資料集很難成立,因此對屬性條件獨立性假設進行一定的放鬆,就提出了“
半樸素貝葉斯分類器
”。
核心思想
:適當考慮一部分屬性間的相互依賴資訊,這樣既不需要計算聯合機率(算不出來~),又不至於徹底忽略了比較強的依賴關係(實際上就是在能夠算出來的前提下儘可能考慮屬性間的依賴關係)。
思想有了,到底怎麼做,下面介紹半樸素貝葉斯分類器最常用的一種策略:
獨依賴估計
,簡稱
ODE
獨依賴就是假設每個屬性在類別之外最多僅依賴一個其他屬性。公式為:
公式4-1中
為
所依賴的屬性,稱為
的父屬性。若父屬性已知,那麼就可以用公式3-4求解ODE下的類條件機率。
因此最關鍵的做法就是如何確定每個屬性的父屬性,不同的做法產生不同的獨依賴分類器。
下面列舉常見的方法:
SPODE(Super-Parent ODE)
假設所有屬性都依賴同一個屬性,這個被依賴的屬性稱為
超父
。
超父屬性的選擇可以透過交叉驗證等模型選擇方法。
TAN(Tree Augmented naive Bayes)
在最大帶權生成樹演算法的基礎上將屬性間的依賴關係約簡為下圖所示。
約簡步驟為:
計算任意兩個屬性之間的條件互資訊:
以屬性為節點構建完全圖,任意兩個節點之間邊的權重設為
構建此完全圖的最大帶權生成樹,挑選根變數,將邊設定為有向。
加入類節點
,增加從
到每個屬性的有向邊
AODE(Averaged One-Dependent Estimator)
嘗試將每個屬性作為超父構造SPODE,然後將具有足夠訓練資料支撐的SPODE整合起來作為最終結果。
基於整合學習機制、更為強大的獨依賴分類器
公式為:
公式4-3中,
是在第
個屬性上取值為
的集合,
為閾值常數。公式的後半部分就是公式4-1的原理,前半部分對屬性進行了篩選,選擇屬性相關的資料大於閾值的屬性。
在這基礎上增加拉普拉斯修正類似公式3-4:
以上就是不同的獨依賴估計的實現方法。
現在考慮這樣一個問題,我們知道獨依賴估計是僅考慮依賴一個屬性,那麼,能夠將一個屬性提高為依賴所個屬性,來提高模型的準確率呢?
實際上是可以的,但是隨著考慮依賴屬性個數的增加,估計類條件機率所需樣本數量成
指數級增加
,因此在訓練樣本非常充分時,能夠提高泛化能力,但是在有限樣本的情況下,又陷入了高階聯合機率的泥沼。
5。 貝葉斯網
貝葉斯網也稱
信念網
,藉助
有向無環圖
來刻畫屬性之間的依賴關係,並使用
條件機率表
來描述屬性的聯合分佈機率。
一個貝葉斯網B由結構G和引數
兩部分組成,即
。
其中網路結構G是一個有向無環圖,其每個節點對應於一個屬性,若兩個屬性有直接依賴關係,則他們透過一條邊連線;引數$\Theta$定量描述這種依賴關係,假設屬性
在G中的父節點集為
,則
包含每個屬性的條件機率表
。
結構(介紹)
貝葉斯網結構表達了屬性間的條件獨立性,它假設每個屬性與它的非後裔屬性獨立。
將屬性
的
聯合機率分佈定義
為:
可以理解為屬性在給定它的父屬性後與其他屬性獨立。
下面介紹貝葉斯網中三類典型的結構,並加以分析
同父結構,在給定
確定值的情況下,
與
相互獨立
V型結構(衝撞結構),在給定確定值
的情況下,
與
必不獨立;在
的值未知的情況下,
與
卻是相互獨立的
證明如下:
公式5-2所示的獨立性稱為
邊際獨立性
順序結構,給定
的值,
與
相互獨立
下面提出一種分析有向圖中變數間的條件獨立性的方法,叫做
有向分離
:
先把有向圖轉化為
無向圖
:
找出有向圖中的所有V型結構,然後在V型結構的兩個父節點之間加上一條無向邊。
將所有有向邊改為無向邊
透過上述步驟產生的無向圖稱為
道德圖
,令父節點相連的過程即步驟1稱為“
道德化
”
基於道德圖能直觀、迅速找出變數間的獨立性關係
假定道德圖中有變數
和集合
,如果變數
能夠被變數
分開,即
僅透過
,才能成為一個連通分支,那麼就成
被
有向分離
。
學習(訓練)
上面介紹了貝葉斯網的結構,貌似很有用,透過貝葉斯網我們可以直接計算出每個節點的條件機率,透過簡單計數方法即可。
但是問題來了,怎麼獲取一個訓練集的貝葉斯網?
下面介紹一種常用的方法:
評分搜尋
具體步驟為需要先定義一個評分函式,透過它來判斷貝葉斯網和訓練集的契合程度,然後基於評分函式來尋找結構最優的貝葉斯網。
因此我們的重點又轉移到
評分函式
,在介紹評分函式之前,先提及一下
資訊理論準則
。
資訊理論準則將學習問題看做一個數據壓縮任務,學習的目標是找到一個能以最短編碼長度描述訓練資料的模型,此時編碼的長度包括了
描述模型自身
所需的編碼位數和使用該模型
描述資料
所需的編碼位數。
常用的評分函式通常基於資訊理論準則,對貝葉斯網而言,模型就是貝葉斯網(無環有向圖),每個貝葉斯網描述了一個在訓練集上的機率分佈,我們應該使用綜合編碼長度(描述網路和編碼資料)最短的貝葉斯網,這就是
最小描述長度(MDL)
準則。
給定訓練集
(類別也為屬性之一),貝葉斯網$B=\left$在$D$上的評分函式為:
在公式5-3中,
是貝葉斯網引數個數,
描述每個引數
所需的編碼位數。
其中
具體如下:
公式5-4描述的是貝葉斯網的對數似然。
因此,根據上述兩式,可以總結出公式5-3的第一項描述的是貝葉斯網B所需的編碼位數;第二項計算對應的機率分佈
對
描述的有多好。
因此,我們只要找到一個貝葉斯網,是的公式5-3最小即可,轉化為一個最佳化任務。
若
,即每個引數僅用1位編碼描述,則得到AIC評分函式:
若
,即每個引數用
位編碼描述,則得到BIC評分函式:
若
,則不計算網路的編碼長度,則評分函式為負對數似然,學習任務變為極大似然估計:
透過公式5-3可以發現,如果固定網路
不變,那麼第一項為常數,最小化
等價於對引數
的極大似然估計。
根據公式5-1與公式5-4可得,引數
可直接在訓練集
上透過經驗評估獲得:
公式5-7中
是D上的經驗分佈。因此,最小化評分函式5-3,只需對網路結構進行搜尋,候選結構的最優引數可以直接在訓練集上計算得到。
然後,從所有的網路結構中搜索最優貝葉斯網結構是一個NP難問題,一般有兩種策略解決:
貪心法:從某個網路結構出發,每次調整一條邊(增加、刪除、改變方向),直到評分函式不在降低為止
透過給網路結構施加約束來消減搜尋空間,例如將網路結構限定為樹形結構。
推斷(預測)
透過已知變數值來推斷待查詢變數的過程稱為
推斷
,已知變數觀測值稱為
證據
最理想也是最直接的是透過貝葉斯網定義的聯合機率分佈來精確計算後驗機率,但是這是NP難問題,在網路節點較多、連線稠密時,難以進行精確推斷。
因此,我們需要使用
近似推斷
避免NP難問題,即透過降低精度要求,在有限時間內求得近似解。
下面介紹近似推斷的一種常用方法:
吉布斯取樣
(一種隨機取樣方法)
令
表示待查詢變數;
令
表示證據變數,其取值為
。
目標是計算後驗機率
,其中
為待查詢變數的取值。
如上圖所示,吉布斯取樣演算法先隨機產生一個與證據
一致的樣本
作為初始點,然後每步從當前樣本中產生下一個樣本。在第t次取樣中,演算法假設
,然後對非證據變數逐個進行取樣個改變其取值,取樣機率根據貝葉斯網B和其他變數的當前取值(即
)計算獲得。
假定經過
次取樣得到的與
一致的樣本共有
個,則可近似估算出後驗機率:
實際上,吉布斯取樣的本質實在貝葉斯網所有變數的聯合狀態空間與證據
一致的子空間中進行
隨機漫步
。每一步僅依賴前一步的狀態,即
馬爾科夫鏈
。無論從什麼狀態開始,馬爾科夫鏈的第t步狀態分佈在
時必收斂於一個平穩分佈。對於吉布斯取樣而言,恰好是
。因此在T很大時,吉布斯取樣相當於根據
取樣,從而保證公式5-8收斂於
由於馬爾科夫鏈通常需要很長的時間才能趨於平穩分佈,因此吉布斯取樣演算法的收斂速度較慢;並且如果貝葉斯網中存在極端機率0或1,則不能保證馬爾科夫鏈存在平穩分佈,此時吉布斯取樣才產生錯誤的估計。
6。 EM演算法
在之前幾節中,我們假設訓練樣本的所有屬性的值都已被觀測到,即訓練樣本是完整的,但是在現實應用中,往往會遇到不完整的訓練樣本。這種情況下,怎樣對模型引數進行估計
我們稱未觀測變數為隱變數,令
表示已觀測變數集,
表示隱變數集,
表示模型引數。
對
做極大似然估計,則應最大化對數似然:
在公式6-1中,由於
是隱變數,因此無法直接求解,不過我們可以透過對
計算期望,來最大化已觀測資料的
對數"邊際似然"
:
EM
演算法那是常用的
估計引數隱變數
的利器,是一種迭代式方法。
基本思想:
E步:若引數
已知,則可根據訓練資料推斷出最優隱變數
的值
M步:若
已知,則可根據極大似然估計求解引數
根據公式6-2,以初始值
為起點,迭代執行以下步驟直至收斂:
基於
推斷隱變數
的期望,記為
基於已觀測變數
和
對引數
做極大似然估計,記為
以上就是EM演算法的原型。
事實上,隱變數估計問題也可透過梯度下降法求解,但是由於求和的項數將隨著隱變數的數目以指數上升,會給梯度下降計算帶來麻煩;EM演算法可以看做是非梯度最佳化的方法,為座標下降法。
總結
上文中的第3、4、5小節其實是有關聯的,樸素貝葉斯分類器不考慮屬性間的依賴關係(結果在一般情況下不錯),貝葉斯網能夠能表示任意屬性間的依賴性,而半樸素貝葉斯分類器則是介於兩者之間,考慮屬性間的部分依賴。
至於極大似然估計是一種引數估計方法,在機器學習中經常被用到,EM演算法則是一種隱變數估計方法,也是一種常用方法。
上述學習筆記主要參考周志華的《機器學習》一書。