章節(jié)目錄

• 貝葉斯決策論

• 極大似然估計

• 樸素貝葉斯分類器

• 半樸素貝葉斯分類器

• 貝葉斯網(wǎng)

• EM算法

7.1 貝葉斯決策論

貝葉斯決策論是概率框架下的基本方法。

該理論假設(shè)有N種可能的類別標記，即y={c1，c2，...，cN}，λij是一個將真實標記為cj的樣本誤分類為ci產(chǎn)生的期望損失，即在樣本x上的“條件風險”。

image.png

我們的任務(wù)是尋找一個判斷準則h:X→ y以最小化總體風險。對每個樣本最小化條件風險，則總體分線也被最小化。

當我們在適用貝葉斯判定準則來最小化決策風險時，我們首先要獲得后驗概率P(c|x)，但是在現(xiàn)現(xiàn)實任務(wù)中這通常難以直接獲得，機器學(xué)習(xí)所要實現(xiàn)的是基于有限的訓(xùn)練樣本集盡可能準確地估計出后驗概率P(c|x)。

主要有兩種策略：

給定x，可通過直接建模P(c|x)來預(yù)測c，這樣得到的是“判別式模型”。

先對聯(lián)合概率分布P（x，c）建模，然后再由此獲得P（c|x），這樣得到的是“生成式模型”。 顯然，前面介紹的決策樹、BP神經(jīng)網(wǎng)絡(luò)、支持向量機等，都可歸入判別式模型的范疇。

image.png

基于貝葉斯定理可寫成，P(c|x)可寫為

image.png

P(c)是類“先驗”概率，P(x | c)是樣本x相對于c地類條件概率，或稱為“似然”；P（x）是用于歸一化地“證據(jù)”因子。

7.2 極大似然估計

估計類條件概率的一種常見策略是先假定其具有某種確定的概率分布形式，再基于訓(xùn)練樣本對概率分布的參數(shù)進行估計。 課本里介紹的是頻率主義學(xué)派的極大似然估計：

令Dc表示訓(xùn)練集D中第c類樣本組成的集合，假設(shè)這些樣本是獨立同分布的，則參數(shù)θc對于數(shù)據(jù)集Dc的似然是

image.png

7.3 樸素貝葉斯分類器

樸素貝葉斯分類器采取了“屬性條件獨立性假設(shè)：對已知類別，假設(shè)所有屬性相互獨立，換言之，假設(shè)每個屬性獨立地對分類結(jié)果發(fā)生影響，則有

image.png

其中d為屬性數(shù)目，Xi為X在第i個屬性上的取值。

由于對所有類別來說P(x)相同，則貝葉斯判斷準則有

image.png

樸素貝葉斯分類器的訓(xùn)練過程就是基于訓(xùn)練集D來估計類先驗概率P(c)，并為每個屬性估計條件概率P(Xi | c)。

令Dc表示訓(xùn)練集D中第c類樣本組成的集合，若有充足的獨立同分布樣本，則可容易地估計類先驗概率

image.png

對離散屬性而言，令Dc,xi表示Dc中在第i個屬性為xi為樣本組成的集合，則條件概率P(xi|c)可估計為

image.png

對連續(xù)屬性可考慮概率密度函數(shù)，假定p(xi|c)~N(μc,i,σc,i2)，其實μc,i和σc,i2分別是第c類樣本在第i個屬性上取值的均值和方差，則有

image.png

若某個屬性值在訓(xùn)練集中沒有于某個類同時出現(xiàn)過，直接算的話就為0了。為了避免這個情況，我們可以用拉普拉斯修正：令N表示訓(xùn)練集D中可能的類別數(shù)，Ni表示第i個屬性可能的取值數(shù)

image.png

image.png

7.4 半樸素貝葉斯分類器

半樸素貝葉斯分類器的基本想法是適當考慮一部分屬性間的相互依賴信息，從而既不需要進行完全聯(lián)合概率計算，又不至于徹底忽略了比較強的屬性依賴關(guān)系。“獨依賴”就是假設(shè)每個屬性在類別之外最多僅依賴于一個其他屬性，即

image.png

其中pai為屬性xi所依賴的屬性，稱為xi的父屬性。

最直接的做法是假設(shè)所有屬性都依賴于同一個屬性，稱為“超父”，然后通過交叉驗證等模型選擇方法來確定超父屬性，由此形成了SPODE（Super-Parent ODE）方法。

image.png

TAN則是在最大帶權(quán)生成樹算法的基礎(chǔ)上，有以下步驟：

1.計算任意兩個屬性之間的條件互信息

2.以屬性為結(jié)點構(gòu)建完全圖，任意兩個結(jié)點之間邊的權(quán)重設(shè)為I(xi,xj|y)

3.構(gòu)建次完全圖的最大帶權(quán)生成樹，挑選根變量，將邊置為有向

4.加入類別結(jié)點y，增加從y到每個屬性的有向邊

AODE是一種基于集成學(xué)習(xí)機制、更為強大的獨依賴分類器。

image.png

其中Dxi是在第i個屬性上取值為xi的樣本的集合，m'為閾值常數(shù)。顯然，AODE需估計P(c,xi)和P(xj|c,xi)

image.png

image.png

其中N是D中可能的類別數(shù)，Ni是第i個屬性可能的取值數(shù)，Dc,xi是類別為c且在第i個屬性上取值為xi的樣本集合，Dc,xi,xj是類別為c且在第i和第j個屬性上取值分別為xi和xj的樣本集合。

7.5貝葉斯網(wǎng)

貝葉斯網(wǎng)亦稱“信念網(wǎng)”，借助有向無環(huán)圖來刻畫屬性之間的依賴關(guān)系。，并使用條件概率表來描述屬性的聯(lián)合概率分布。

image.png

從圖中可以看出，“色澤”直接依賴于“好瓜”和“甜度”，而“根蒂”則直接依賴于“甜度”：進一步從條件概率表能得到“根蒂”對“甜度”量化依賴關(guān)系。

7.5.1 結(jié)構(gòu)

貝葉斯網(wǎng)結(jié)構(gòu)有效地表達了屬性間的條件獨立性，給定結(jié)點集，貝葉斯網(wǎng)假設(shè)每個屬性與他的非后裔屬性獨立，于是

image.png

以上圖為例，聯(lián)合概率分布為：

image.png

貝葉斯網(wǎng)中三個變量之間的典型依賴關(guān)系：

image.png

7.5.2 學(xué)習(xí)

評分函數(shù)：給定訓(xùn)練集D={x1,x2,...,xm}，貝葉斯網(wǎng)B={G,Θ}在D上的評分函數(shù)可寫為

image.png

其中，|B|是貝葉斯網(wǎng)的參數(shù)個數(shù)；f(θ)表示描述每個參數(shù)θ所需的字節(jié)數(shù)；而

image.png

是貝葉斯網(wǎng)B的對數(shù)似然。評分函數(shù)的第一項是計算編碼貝葉斯網(wǎng)B所需的字節(jié)數(shù)，第二項是計算B所對應(yīng)的概率分布PB對D描述得有多好。我們要做的是尋找一個貝葉斯網(wǎng)B使評分函數(shù)s(B|D)最小。

-若f(θ)=1，即每個參數(shù)用1字節(jié)描述，則得到AIC評分函數(shù)

image.png

-若f(θ)=(1/2)log(m)，即每個參數(shù)用(1/2)log(m)字節(jié)描述，則得到BIC（Bayesian Information Criterion）評分函數(shù)

image.png

-若f(θ)=0，則學(xué)習(xí)任務(wù)退化為極大似然估計。

7.5.3 推斷

貝葉斯網(wǎng)訓(xùn)練好之后就能用來回答”查詢“，即通過一些屬性變量的觀測值來推測其他屬性變量的取值，最理想的是直接根據(jù)貝葉斯網(wǎng)定義的聯(lián)合概率分布來精確計算后驗概率，但是這樣的”精確推斷“已被證明是NP難的，所以我們通過降低精度要求，在有限時間內(nèi)求得近似解，在現(xiàn)實應(yīng)用中，貝葉斯網(wǎng)的近似推斷常采用吉布斯采樣來完成。

7.6 EM算法

未觀測變量的學(xué)名是”隱變量“。令X表示已觀測變量集，Z表示隱變量集，Θ表示模型函數(shù)。若欲對Θ做極大似然估計，則應(yīng)最大化對數(shù)似然

image.png

然而由于Z是隱變量，上式無法直接求解。此時我們可通過對Z計算期望，來最大化已觀測數(shù)據(jù)的對數(shù)“邊際似然”

image.png

EM算法是常用的估計參數(shù)隱變量的利器，它是一種迭代式的方法，其基本想法是：若參數(shù)Θ已知，則可根據(jù)訓(xùn)練數(shù)據(jù)推斷出最優(yōu)隱形變量Z的值（E步）；反之，若Z的值已知，則可方便地對參數(shù)Θ做極大似然估計（M步）。

以初始值Θ0為起點，對上式可迭代執(zhí)行以下步驟直至收斂：

-基于Θt推斷隱變量Z的期望，記為Z^t；

-基于已觀測變量X和Zt對參數(shù)Θ做極大似然估計，記為Θ^t+1。

這就是EM算法的原型。

若我們不是取Z的概率分布P(Z|X,Θt)，則EM算法的兩個步驟是：

-E步（Expectation）：以當前參數(shù)Θt推斷變量分布P(Z|X,Θt)，并計算對數(shù)似然LL(Θ|X,Z)關(guān)于Z的期望

image.png

-M步（Maximization）：尋找參數(shù)最大化期望似然，即

image.png