引言
前面介紹的分類算法蛙粘，我們都是期望這個分類算法能夠給我們一個確定的分類垫卤。但是，有時候组题，分類器也像我們?nèi)祟愐粯雍校瑢ψ约旱呐袛嗖⒉皇欠浅Ｓ邪盐铡＿@時候崔列，我們需要分類器告訴我們梢褐，它將樣本x歸為A類的“把握”有多大旺遮，即概率有多大。
本文介紹一個非常常見的基于概率框架的分類器：貝葉斯分類器盈咳。這個主題分為兩個部分：這篇屬于理論篇耿眉，下一篇文章屬于實戰(zhàn)篇。
這篇文章分四個部分：1. 貝葉斯決策論鱼响；2. 樸素貝葉斯分類器鸣剪； 3. 半樸素貝葉斯分類器及4.貝葉斯網(wǎng)絡
貝葉斯決策論
在介紹貝葉斯決策論之前，先介紹兩個概念：先驗概率（prior probability）和后驗概率（posterior probability）丈积。
直觀上來講筐骇， 先驗概率 是指在事件未發(fā)生時，估計該事件發(fā)生的概率江滨。比如投擲一枚勻質(zhì)硬幣铛纬，“字”朝上的概率。后驗概率是指基于某個發(fā)生的條件事件唬滑，估計某個事件的概率告唆，它是一個條件概率。比如一個盒子里面有5個球晶密，兩個紅球擒悬，三個白球，求在取出一個紅球后稻艰，再取出白球的概率懂牧。
在wiki上， 先驗概率的定義為：A prior probability is a marginal probability, interpreted as a description of what is known about a variable in the absence of some evidence连锯。 后驗概率的定義為：The posterior probability is the conditional probability of the variable taking the evidence into account. The probability is computed from the prior and the likelihood function via Baye's theorem.
現(xiàn)在以分類任務為例归苍。 首先假設有N種可能的類別標簽， 即y={c1, c2, ..., cN}, λij 表示將一個真實標記為cj的樣本誤分類為ci時產(chǎn)生的損失运怖。后驗概率p(ci|x)表示將樣本x分類給ci是的概率拼弃。那么將樣本x分類成ci產(chǎn)生的條件風險（conditional risk）為：
其中，P(cj|x) 表示樣本x分類成cj類的概率摇展，λij 表示將真實cj類誤分類為ci類的損失吻氧。所以這個公式就是將x屬于其他類（除ci類外）的概率與對應的誤分類為ci的損失乘積之和。
我們的目標是尋找一個判定標準咏连，以最小化總體的風險盯孙。這個判定準則也叫做貝葉斯判定準則(Bayes decision rule)： 為最小化總體風險，只需要在每個樣本上選擇那個能使條件風險R(c|x)最小的類別標記祟滴，即
此時振惰，h稱為貝葉斯最優(yōu)分類器(Bayes optional classifier)，與之對應的總體風險R(h)稱之為貝葉斯風險(Bayes risk). 1-R(h*)反映了分類器所能達到的最好性能垄懂，即理論上限骑晶。
如果把λij定義為：
那么風險函數(shù)可以改寫為：
那么貝葉斯最優(yōu)分類器的公式可以改寫為：
為了最優(yōu)化上面的函數(shù)痛垛，我們必須要知道后驗概率p(c|x).但是在現(xiàn)實任務中，很難直接知道這個概率值桶蛔，所以需要我們使用現(xiàn)有的訓練數(shù)據(jù)估計出這個后驗概率匙头。這時候就需要使用貝葉斯公式：
其中，P(c)是類先驗概率仔雷，表示在樣本空間中蹂析，各類樣本所占的比例。P(x|c)表示樣本x相對于類標簽c的類條件概率碟婆。直接通過樣本計數(shù)的方式計算會有點麻煩电抚。原因如下： 假設樣本共有d個屬性，且屬性值都是二值的脑融。那么樣本空間至少有2^d個不同的樣例喻频。但是在現(xiàn)實生活中，樣本空間的個數(shù)會遠遠小于這個數(shù)肘迎。所以通過計數(shù)的方式，直接算出這個概率的方式是不可靠的锻煌。
極大似然估計 一般估計類條件概率使用的是極大似然估計妓布。首先我們假設樣本符合某個確定的概率分布形式，然后使用極大似然法估計這個分布的參數(shù)θ宋梧。公式如下：
其中匣沼，Dc表示樣本空間中c類組成的樣本集和。所以對參數(shù)θ的最大似然估計為：
樸素貝葉斯
前面我們已經(jīng)講到捂龄，要估計條件概率P(c|x)释涛，我們必須得求得類條件概率P(x|c)。但是這個類條件概率很難從有限的訓練樣本中直接獲得倦沧，為了避開這個假設唇撬，我們使用樸素貝葉斯分類器（naive Bayes Classifier)，樸素貝葉斯分類器采用了“屬性條件獨立性假設”(attribute conditional independence assumption): 即對已知類別展融，假設所有的屬性相互獨立窖认，那么P(c|x)可以重寫為：
對應的樸素貝葉斯判定準則為：
半樸素貝葉斯分類器
前面講到， 為了降低估計后驗概率P(c|x)的難度告希，樸素貝葉斯分類器采用了屬性條件獨立性假設扑浸，但是在現(xiàn)實任務中這個假設往往不成立。于是燕偶，人們放松了這個假設的限制喝噪，提出了半樸素貝葉斯分類器的假設(semi-naive Bayes classifiers)的學習方法。其中指么， 獨依賴估計(one-Dependent Estimator ODE)是半樸素貝葉斯分類器的一種常用的策略酝惧。獨依賴估計假設所有的屬性都依賴于某一個屬性驰吓。這里介紹三種基于獨依賴估計的半樸素貝葉斯分類器。第一種是SPODE(Super-Parent ODE),即假設所有的屬性都依賴于同一個屬性系奉，這個屬性也被稱之為超父檬贰。超父屬性的確定通過交叉驗證的方式確定。第二種是TAN(Tree Augmented navie Bayes)缺亮。這種方法的做法是先計算任意兩個屬性之間的條件互信息(conditional mutual information),這樣就可以建立一個完全連接圖翁涤。基于這個圖萌踱，就可以生成一棵最大帶權生成樹葵礼。這棵樹之間的連接關系便是屬性之間的依賴關系。最后一種是AODE(Averaged One-Dependent Estimator)并鸵，這種方法的做法是使用每個節(jié)點作為超父屬性來構造SPODE鸳粉，然后將具有足夠訓練數(shù)據(jù)支撐的SPODE集成起來作為最終的結果。
貝葉斯網(wǎng)
貝葉斯網(wǎng)(Bayesian network) 也稱為信念網(wǎng)(belief network) ,它借助有向無環(huán)圖來刻畫屬性之間的依賴關系园担，并使用條件概率表來描述屬性的聯(lián)合概率分布届谈。在貝葉斯網(wǎng)中三個變量之間的依賴關系共有三種情況：
V型結構也成沖撞結構，給定c的取值弯汰，a,b必不獨立艰山，但是當c的取值不知道時，a,b反而獨立咏闪。
第二種結構是同父結構曙搬，示意圖如下：
當c已知時，a和b獨立鸽嫂。
最后一種是順序結構纵装，示意如下：
如果已知C，那么a和b條件獨立据某。
基于貝葉斯網(wǎng)橡娄，可以很容易分析出各個屬性之間的條件獨立關系。我們只需生成對應的道德圖(moral graph)就行哗脖。具體的做法如下：1）找到圖中所有的V型結構瀑踢，在V型結構的兩個父節(jié)點之間加上一條無向邊；2）然后將所有的有向邊改為無向邊才避。假設在道德圖中橱夭，有變量x，y和變量集合z = {zi}桑逝，如果將z從變量集合中去除后棘劣，x和y分屬兩個連通分支，那么成變量x和y被z有向分離楞遏，記為x⊥y|z成立茬暇，即已知z首昔，x和y相互獨立。
如果要使用貝葉斯網(wǎng)絡進行預測糙俗，一般包括兩個步驟：1）學習勒奇；2）推斷。即先通過學習來構建貝葉斯網(wǎng)絡巧骚，再使用構建好的貝葉斯網(wǎng)絡進行推斷赊颠。對于學習過程，如果從所有的網(wǎng)絡結構空間來搜索最優(yōu)的貝葉斯網(wǎng)絡劈彪，會是一個NP hard的問題竣蹦。通常有兩個近似解決方法：一種是使用貪心算法，即從某個網(wǎng)絡結構出發(fā)沧奴，每次調(diào)整一條邊(增加痘括，刪除或調(diào)整方向)，直到評分函數(shù)值不再下降為止滔吠。另一種是通過給網(wǎng)絡結構施加約束來削減搜索空間纲菌。對于推斷過程，如果是精確推斷屠凶，也將會是NP hard問題驰后，常用的解決方法是吉布斯采樣法(Gibbs sampling)來得到近似的答案。
這篇的理論主要介紹到這里矗愧，對于其中沒有說明的細節(jié)問題，有興趣的讀者可以查詢其他的資料郑原。
