數學 · 樸素貝葉斯（二*）· 推導與推廣

這章的內容會涉及到機率論的一些雖然基礎但不算平凡的概念和知識…… （ σ‘ω’）σ

貝葉斯公式與後驗機率

貝葉斯公式的定義如下：

它的直觀是：樣本

在引數

下的機率乘上引數本身的機率 = 樣本和引數的“聯合機率”

= 引數

在樣本

下的機率乘上樣本本身的機率（一點都不直觀啊喂！）。考慮到獨立性假設，可以得知樣本

的機率就是它組成部分

的機率的乘積：

有了上面這些公式之後，我們就可以分情況寫出後驗機率

的公式了

當引數空間

是離散集合

時，有：

單引數空間

是連續集合時，有：

離散型樸素貝葉斯演算法

上一章我們敘述了樸素貝葉斯演算法的極大似然估計但沒有給出推導，這裡會將該推導補足。需要指出的是，彼時給出的演算法是所有維度的特徵都是離散型隨機變數的情況下的演算法、亦即

離散型樸素貝葉斯演算法

（這個名詞是我自己瞎謅的不要把它當成是專業的）（喂）。它的推導相對簡單但比較繁瑣，核心的思想是利用示性函式將對數似然函式寫成比較“整齊”的形式、再運用拉格朗日方法進行求解

在正式推導前，我們先說明一下符號約定（在 Word 上打過一遍、不想再打了（´>ω∂`）☆）：

接下來就可以開始寫公式了

計算對數似然函式

其中

極大化似然函式。為此，只需分別最大化

和

對於後者，由條件獨立性假設可知、我們只需要對

分別最大化：

即可。我們可以利用拉格朗日方法來求解該問題，用到的約束條件是：

從而可知

由一階條件

可以解得

同理，對

應用拉格朗日方法，可以得到

以上，我們完成了離散型樸素貝葉斯演算法的推導

連續型和混合型樸素貝葉斯

在處理完離散型的情況後，首先容易想到的就是：如果我想處理連續型特徵應該怎麼做？

一般而言會有兩種方法：

使用小區間切割、直接使其離散化。這種方法較難控制小區間的大小、而且對訓練集質量的要求比較高

假設該變數服從正態分佈、再利用極大似然估計來計算該變數的“條件機率”，這種方法相對而言用的要多一些。具體而言：

計算“條件機率”

：

這裡有兩個引數：

、

，它們可以用極大似然估計法定出：

其中，

是類別

的樣本數

需要注意的是，這裡的“條件機率”其實是“條件機率密度”，真正的條件機率其實是 0（因為連續型變數單點機率為0）。這樣做的合理性涉及到了比較深的機率論知識，此處不詳細展開（其實就是我還沒做而且懶得做也大概不會做）（喂

知道怎麼處理連續型特徵後，進一步我們可能會想處理混合型的資料（即有些特徵是離散的、有些特徵是連續的）。個人認為混合型樸素貝葉斯演算法可以有兩種提法（僅代表

個人意見

、可參考而不可盡信、因為這一塊也沒查到太好的資料……如果有觀眾老爺有這方面的研究的話，希望能夠不吝賜教！（ σ‘ω’）σ）：

用某種分佈的密度函式算出訓練集中各個樣本連續型特徵相應維度的密度之後，根據這些密度的情況將該維度離散化、最後再訓練離散型樸素貝葉斯模型

直接結合離散型樸素貝葉斯和連續型樸素貝葉斯——亦即將離散維度的條件機率和連續維度的機率密度直接帶入離散型樸素貝葉斯的決策函式

從直觀可以看出、第二種提法可能會比第一種提法要“激進”一些，因為如果某個連續型維度採用的分佈特別“大起大落”的話、該維度可能就會直接“主導”整個決策

樸素貝葉斯的推廣

樸素貝葉斯匯出的分類器只是貝葉斯分類器中的一小類，它所作的獨立性假設在絕大多數情況下都顯得太強，現實任務中這個假設往往難以成立。為了做出改進，人們嘗試在不過於增加模型複雜度的前提下、將獨立性假設進行各種弱化。由此衍生出來的模型中，比較經典的就是半樸素貝葉斯（Semi-Naïve Bayes）模型和貝葉斯網模型（Bayesian Network）

半樸素貝葉斯

由於提出條件獨立性假設的原因正是聯合機率難以求解，所以在弱化假設的時候同樣應該避免引入過多的聯合機率，這也正是半樸素貝葉斯的基本想法。比較常見的半樸素貝葉斯演算法有如下三種：

ODE 演算法（One-Dependent Estimator，可譯為“獨依賴估計”）

顧名思義，在該演算法中、各個維度的特徵至多依賴一個其它維度的特徵。從公式上來說，它在描述條件機率時會多出一個條件：

這裡的代表著維度 j 所“獨依賴”的維度

SPODE 演算法（Super-Parent ODE，可譯為“超父獨依賴估計”）

這是ODE演算法的一個特例。在該演算法中，所有維度的特徵都獨依賴於同一個維度的特徵，這個被共同依賴的特徵就叫“超父（Super-Parent）”。若它的維度是第pa維，知：

一般而言，會選擇透過交叉驗證來選擇超父

AODE 演算法（Averaged One-Dependent Estimator，可譯為“整合獨依賴估計”）

這種演算法背後有提升方法的思想。AODE 演算法會利用 SPODE 演算法並嘗試把許多個訓練後的、有足夠的訓練資料量支撐的SPODE模型整合在一起來構建最終的模型。一般來說，AODE 會以所有維度的特徵作為超父訓練 n 個 SPODE 模型、然後線性組合出最終的模型

貝葉斯網

貝葉斯網又稱“信念網（Belief

Network）”，比起樸素貝葉斯來說、它背後還蘊含了圖論的思想。貝葉斯網有許多奇妙的性質，詳細的討論不可避免地要使用到圖論的術語，這裡僅擬對其做一個直觀的介紹。

貝葉斯網既然帶了“網”字，它的結構自然可以直觀地想成是一張網路，其中：

網路的節點就是單一樣本的各個維度上的隨機變數

連線節點的邊就是節點之間的依賴關係

需要注意的是，貝葉斯網一般要求這些邊是“有方向的”、同時整張網路中不能出現“環”。無向的貝葉斯網通常是由有向貝葉斯網無向化得到的，此時它被稱為 moral graph（除了把所有有向邊改成無向邊以外，moral graph 還需要將有向網路中不相互獨立的隨機變數之間連上一條無向邊，細節不表），基於它能夠非常直觀、迅速地看出變數間的條件獨立性

顯然，有了代表各個維度隨機變數的節點和代表這些節點之間的依賴關係的邊之後，各個隨機變數之間的條件依賴關係都可以透過這張網路表示出來。類似的東西在條件隨機場中也有用到，可以說是一個適用範圍非常寬泛的思想

貝葉斯網的學習在網路結構已經確定的情況下相對簡單，其思想和樸素貝葉斯相去無多：只需要對訓練集相應的條件進行“計數”即可，所以貝葉斯網的學習任務主要歸結於如何找到最恰當的網路結構。常見的做法是定義一個用來打分的函式並基於該函式透過某種搜尋手段來決定結構，但正如同很多最最佳化演算法一樣、在所有可能的結構空間中搜索最優結構是一個 NP 問題、無法在合理的時間內求解，所以一般會使用替代的方法求近似最優解。常見的方法有兩種，一種是貪心法、比如：先定下一個初始的網路結構並從該結構出發，每次增添一條邊、刪去一條邊或調整一條邊的方向，期望透過這些手段能夠使評分函式的值變大；另一種是直接限定假設空間、比如假設要求的貝葉斯網一定是一個樹形的結構

相比起學習方法來說，貝葉斯網的決策方法相對來說顯得比較不平凡。雖說最理想的情況是直接根據貝葉斯網的結構所決定的聯合機率密度來計算後驗機率，但是這樣的計算被證明了是 NP 問題 ［Cooper， 1990］。換句話說，只要貝葉斯網稍微複雜一點，這種精確的計算就無法在合理的時間內做完。所以我們同樣要藉助近似法求解，一種常見的做法是吉布斯取樣（Gibbs Sampling），它的定義涉及到馬爾科夫鏈相關的（我還沒有學的）知識，這裡就不詳細展開了（……）

========== 作為總結的分割線 ==========

這章講了離散型樸素貝葉斯演算法的推導，同時還介紹了連續型和混合型樸素貝葉斯演算法

此外、還概括性地介紹了半樸素貝葉斯和貝葉斯網，它們的目的都是適當地削弱獨立性假設

希望觀眾老爺們能夠喜歡~