轉(zhuǎn)載自： http://bbs./#!article/PR_AI/2530?p=1

原文的主要內(nèi)容

有兩種方法設(shè)計(jì)分類器：
1. discriminative model，就是由樣本直接設(shè)計(jì)判別函數(shù)，例如SVM；
2. generative model，就是先從樣本恢復(fù)概率模型——例如我們熟悉的參數(shù)方法：混合高斯模型GMM;非參數(shù)方法Parzen窗。然后再充分挖掘模型，用以分類。例如Bayes最大后驗(yàn)概率準(zhǔn)則；或者將模型中的參數(shù)當(dāng)作提取的特征（參數(shù)一般都比較少，所以這么做實(shí)際上是在降維），在這些新特征上設(shè)計(jì)分類器（例如又用SVM）。
恢復(fù)的模型可生成新的樣本，所以得名generative。

原文就是講了一種建立generative model的方法，用于文本處理。
對(duì)文本（document）中各單詞（word）的出現(xiàn)頻率（簡稱詞頻）建立概率模型通常是文本處理的第一步。

開始討論前，先做如下約定：
- 僅考慮文本的詞頻，而不考慮單詞在文本中出現(xiàn)的先后順序及其約束關(guān)系
- 文本中的單詞來自大小為|V|的詞匯表。例如： V = {FILM, MUSIC, TAX, MILLION, STUDENT, TEACHER, SCHOOL}. |V| = 7
- 每篇文本有N個(gè)單詞
- 文本來自k個(gè)主題（topic）。例如: T = {Arts, Budgets, Education}. k = 3

一種簡單直觀的詞頻概率模型——unigram model（原文Figure 3(a)）這樣描述某一文本中單詞的“發(fā)生方式”：
For each of the N words w_n:
Choose a word w_n ～ p(w);
其中，w是離散隨機(jī)變量，在詞匯表V中取|V|個(gè)離散的值。p(w)是w的分布，可由訓(xùn)練樣本通過機(jī)器學(xué)習(xí)或其它方法獲得。這個(gè)模型就是每個(gè)單詞的詞頻，沒有考慮文本的主題，過于簡單。于是我們引出考慮了文本主題的模型——

Mixture of unigram(原文中Figure 3(b)). 它這樣描述某一文本中單詞的“發(fā)生方式”：
Choose a topic z ～ p(z);
For each of the N words w_n:
Choose a word w_n ～ p(w|z);
其中，z是離散隨機(jī)變量，在主題T中取k個(gè)離散值，p(z)是z的分布；w_n是離散隨機(jī)變量,在詞匯表V中取|V|個(gè)離散值，p(w|z)是給定z時(shí)w的條件分布。z可取k個(gè)值，w可取|V|個(gè)值，p(w|z)可看作一個(gè)k×|V|的矩陣，可由訓(xùn)練樣本通過機(jī)器學(xué)習(xí)或其它方法獲得。
對(duì)照我們?cè)谇懊娴募s定中給出的V和T的具體示例，p(w|z)是3×7矩陣。若p(w|z)的第1行表示主題{Education}——可以想象這個(gè)主題的文本中{STUDENT, TEACHER, SCHOOL}的詞頻會(huì)高些，其它單詞的詞頻會(huì)低些——因此該行的行向量所表示的分布p(w|z)會(huì)在{STUDENT, TEACHER, SCHOOL}附近出現(xiàn)峰值；若第2行表示主題{Budgets}，p(w|z)就會(huì)在{TAX,MILLION}附近出現(xiàn)峰值…
在“發(fā)生”一篇文本前先隨機(jī)選出p(w|z)的第z行（根據(jù)分布p(z)）；再依次隨機(jī)選出第z行的w_1,w_2,…,w_N列（每次選取都根據(jù)分布p(w|z)）,這就“發(fā)生”出了文本中的所有單詞。
但是這個(gè)模型只允許一篇文本有一個(gè)主題，這是不夠妥當(dāng)?shù)?。一篇關(guān)于北郵科研經(jīng)費(fèi)的文本，可能{STUDENT, TEACHER, SCHOOL, TAX, MILLION}的詞頻都很高——這個(gè)文本同時(shí)具有兩個(gè)主題{Education,Budgets}。如何模擬一篇文本多個(gè)主題的情形呢？在此，我們跳過pLSI模型，直接引入原文探討的——

Latent Dirichlet Allocation (LDA, 原文中Figure 1). 它這樣描述某一文本中單詞的“發(fā)生方式”：
Choose parameter θ ～ p(θ);
For each of the N words w_n:
Choose a topic z_n ～ p(z|θ);
Choose a word w_n ～ p(w|z);
其中θ是一個(gè)1×k的隨機(jī)行向量，p(θ)是θ的分布，它的具體函數(shù)形式就是Dirichlet分布，這一分布保證θ的k個(gè)分量θ_1,θ_2,…,θ_k都取連續(xù)的非負(fù)值，且θ_1 + θ_2 + … + θ_k = 1；z_n是離散隨機(jī)變量，在主題T中取k個(gè)離散值，p(z|θ)是給定θ時(shí)z的條件分布，它的具體函數(shù)形式很簡單，就是把θ直接拿來作為概率值：p(z = i|θ) = θ_i,也就是說z取第1,2,…k個(gè)主題的概率分別是θ_1,θ_2,…,θ_k；w_n是離散隨機(jī)變量,在詞匯表V中取|V|個(gè)離散值，p(w|z)是給定z_n時(shí)w的條件分布。和前面一樣，可以把它看作k×|V|的矩陣。
LDA在“發(fā)生”一篇文本前,先隨機(jī)生成一個(gè)1×k的向量θ（根據(jù)Dirichlet分布p(θ)）,生成的這個(gè)θ非負(fù)且歸一化，可以看作某個(gè)隨機(jī)變量的分布(也就是說，Dirichlet可以看作是分布的分布…)；然后隨機(jī)選取p(w|z)的第z_1行（根據(jù)分布p(z|θ)）,接著隨機(jī)選取z_1行的w_1列（根據(jù)分布p(w|z = z_1)）,同樣的方法依次選出z_2,w_2,…z_N,w_N,這就“發(fā)生”出了文本中的所有單詞。

剩下的任務(wù)就是如何根據(jù)訓(xùn)練樣本學(xué)習(xí)出LDA模型的具體形式。模型無非是含有控制參數(shù)的表達(dá)式，學(xué)習(xí)出了參數(shù)就確定了模型。我們看看LDA有哪些控制參數(shù)呢？
- 分布p(θ)的表達(dá)式需要一個(gè)1×k行向量的參數(shù)，記為α
- p(w|z)可看作k×|V|的矩陣，記該矩陣為β
把w看作觀察變量，θ和z看作隱藏變量，就可以通過著名的EM算法學(xué)習(xí)出α和β，但這一過程中后驗(yàn)概率p(θ,z|w)無法計(jì)算出解析表達(dá)式，因此需要近似解，原文中使用了基于分解（factorization）假設(shè)的變分法(Variational Methods)，其實(shí)也就是先假設(shè)θ和z在給定w時(shí)條件獨(dú)立：p(θ,z|w) ≈ p(θ|w)*p(z|w)，然后進(jìn)行后續(xù)推導(dǎo)（參考本導(dǎo)讀“預(yù)備知識(shí)” – Variational Inference）。這一套方法原文叫做variational EM，推導(dǎo)過程確實(shí)有些復(fù)雜，但最后總結(jié)出的不過是幾個(gè)可以通過迭代求解的表達(dá)式（參見原文5.3節(jié)的1.2.兩步）。

最后理一下原文的結(jié)構(gòu)
1 Introduction 綜述其它方法
2 Notation and terminology 符號(hào)約定
3 Latent Dirichlet allocation 詳細(xì)介紹
4 Relationship with other latent variable models LDA與unigram, mixture of unigram, pLSI的區(qū)別。前兩個(gè)本導(dǎo)讀已經(jīng)提到了，建議讀者再仔細(xì)比較pLSI和LDA的區(qū)別，理解為什么作者說pLSI不是well-defined graphic model
5 Inference and Parameter Estimation Inference部分介紹了variational inference，就是本導(dǎo)讀前面提到的如何近似計(jì)算隱藏變量的后驗(yàn)概率。Parameter Estimation就是用EM法估計(jì)α和β
6 Examples和7 Applications and Empirical Results 給出的具體例子、應(yīng)用和實(shí)驗(yàn)結(jié)果


預(yù)備知識(shí)


如果牢固掌握這些預(yù)備知識(shí)，理解原文會(huì)更容易些。

- p(X|Y)的記法。注意|右邊的Y既可以表示隨機(jī)變量（已經(jīng)取定了某具體值），也可以表示普通的非隨機(jī)變量。這樣我們可以在最大似然估計(jì)和Bayes方法間方便的“切換”，而不會(huì)讓符號(hào)記法影響我們的表述。例如，考慮具有確定但未知參數(shù)μ，Σ的高斯分布p(x),可以記為p(x|μ,Σ);若按照Bayes學(xué)派觀點(diǎn)，可以將μ和Σ也看作隨機(jī)變量，x的分布就能記為隨機(jī)變量μ，Σ取定某值后的條件分布p(x|μ,Σ)——統(tǒng)一的記法。

- k取1分布/多項(xiàng)式分布(Multinomial)?？紤]取3個(gè)離散值的隨機(jī)變量x ～ p(x)。這個(gè)看似很平庸的分布…就是所謂的k取1分布或稱多項(xiàng)式分布。一般我們習(xí)慣的把它記為p(x_i) = u_i, i = 1,2,3,且u_1 + u_2 + u_3 = 1. 但在有些數(shù)學(xué)推導(dǎo)中，將它記為指數(shù)形式會(huì)更方便些.將x看作3維的隨機(jī)向量，各分量是“互斥”的，即它只能取(1,0,0),(0,1,0),(0,0,1)三組值。于是可將分布重新記為 p(x) = (u_1^x_1)*(u_2^x_2)*(u_3^x_3).注意論文原文中Multinomial就是這兒說的k取1分布，與一些概率教科書中的定義不同。一般的k維情況依次類推。具體參[Bishop]的2.2節(jié).

- 共軛先驗(yàn)分布(Conjugate Prior)?？紤]某概率密度函數(shù)，要估計(jì)其中的參數(shù)t。按照Bayes學(xué)派的觀點(diǎn)，參數(shù)t ～ p(t).我們有p(t|X) ∝ p(X|t)p(t),這個(gè)式子說：在沒有做任何觀測時(shí)，我們對(duì)t的知識(shí)用先驗(yàn)分布p(t)表示。當(dāng)觀察到X后，就通過該式將先驗(yàn)概率p(t)更新（計(jì)算）為后驗(yàn)概率p(t|X)，使我們對(duì)t的知識(shí)增加。仔細(xì)觀察，若p(t)與p(X|t)有相同的函數(shù)形式，那么后驗(yàn)概率p(t|X)就與先驗(yàn)概率p(t)有相同的函數(shù)形式——這使得t的后驗(yàn)概率與先驗(yàn)概率具有相同的表達(dá)式，只是參數(shù)被更新了！ 更妙的是，本次后驗(yàn)概率可以作為下次觀測時(shí)的先驗(yàn)概率，于是當(dāng)繼續(xù)進(jìn)行觀測X_2,X_3…時(shí)，只是不斷的在更新先驗(yàn)概率p(t)的參數(shù),p(t)的函數(shù)形式不變。具體參見[Bishop]的2.2節(jié)。
這也是Bayes學(xué)派飽受批評(píng)的地方：先驗(yàn)概率的選取有時(shí)只是方便數(shù)學(xué)推導(dǎo)，而非準(zhǔn)確的反映我們的先驗(yàn)知識(shí)。

- Dirichlet分布?，F(xiàn)在我們可以說，Dirichlet分布就是k取1分布的Conjugate Prior。若k維隨機(jī)向量θ ～ Drichlet分布，則θ的k個(gè)分量θ_1,θ_2,…,θ_k都取連續(xù)的非負(fù)值，且θ_1 + θ_2 + … + θ_k = 1。Dirichlet分布的具體表達(dá)式參見[Bishop]的2.2節(jié)。

- Simplex。考慮2維的例子：以(0,1)與(1,0)為端點(diǎn)的線段就是simplex。考慮3維的例子，以(0,0,1),(0,1,0),(0,0,1)為端點(diǎn)的三角形內(nèi)部就是simplex。更高維的情況可依次類推。考慮θ ～ Drichlet分布。注意到θ的k個(gè)分量θ_1,θ_2,…,θ_k都取連續(xù)的非負(fù)值，且θ_1 + θ_2 + … + θ_k = 1，可知Dirichlet分布的定義域是一個(gè)simplex.這也就是原文中Figure 2那個(gè)三角形的含義（k = 3的示意圖，讓這個(gè)simplex三角形平躺在水平面上）。參見[Bishop]的2.2節(jié)

- Graphical Models. 就是用圖來表示隨機(jī)變量中的依賴關(guān)系。這個(gè)tutorial一google一大把。建議參考[Bishop]的8.1節(jié)，了解幾個(gè)符號(hào)（空心圓圈——隱藏(latent)變量,實(shí)心圓圈——觀察(observed)變量，方框——重復(fù)次數(shù)）就足夠看懂原文中的Figure 1和Figure 3了。最多再看看[Bishop]的8.2節(jié)

- EM.關(guān)于這個(gè)的tutorial很多，但我覺得[Bishop]的9.2節(jié)是數(shù)學(xué)處理最為簡潔，最容易看懂的(有個(gè)tutorial在關(guān)鍵的幾步中用了大量∑和∏，讓人抓狂) 。另外[Bishop]的9.4節(jié)也值得看，為理解其它內(nèi)容如variational inference有好處。

- Variational Inference. 就是計(jì)算后驗(yàn)概率的近似方法。考慮隨機(jī)變量{X,Z}，其中X是觀察變量，Z = {Z_1,Z_2}是隱藏變量。用EM法或做Bayes推理的關(guān)鍵一步,就是要求后驗(yàn)概率p(Z|X).不巧的是,在一些復(fù)雜問題中p(Z|X)沒有解析表達(dá)式,需要近似求解.相關(guān)的方法很多,一種經(jīng)常使用的是基于可分解(factorization)假設(shè)的方法：p(Z|X) ≈ p(Z_1|X)p(Z_2|X)——就是說強(qiáng)行假設(shè)Z_1和Z_2條件獨(dú)立——然后進(jìn)行后續(xù)推導(dǎo)。
這一假設(shè)當(dāng)然會(huì)產(chǎn)生誤差，考慮二維高斯分布p(Z|X) = p(Z_1,Z_2|X)，Z_1與Z_2不獨(dú)立，所以p(Z_1,Z_2|X)的等高圖是同心橢圓，橢圓可任意傾斜（例如，若Z_1與Z_2的線性相關(guān)系數(shù)是1，則橢圓傾斜45°）。現(xiàn)簡記p(Z_1|X) = q_1(Z_1), p(Z_2|X) = q_2(Z_2)，我們想改變q_1與q_2，用q_1*q_2去擬合p(Z_1,Z_2|X).但無論如何改變q_1與q_2的形式，q_1*q_2的橢圓等高線都是長軸、短軸分別與Z_1軸、Z_2軸平行！不過，合適的q_1與q_2保證q_1*q_2與p(Z|X)的峰值點(diǎn)重合，一般這就足以解決實(shí)際問題了。詳細(xì)講解可以參見[Bishop]的第10章。也可參考[Winn]的1.8節(jié)。
另外，[Winn]提出了通用的計(jì)算框架，你不必每次都先用Variational Inference推導(dǎo)出公式，再手工編寫代碼；你只用在一個(gè)GUI里編輯好Graphical Model，再點(diǎn)start…（作為類比，考慮離散的線性系統(tǒng)轉(zhuǎn)移函數(shù)H(z)，你可以由此推導(dǎo)出差分方程的表達(dá)式，然后用Matlab編程求解；也可以在Simulink中編輯好框圖，再點(diǎn)start…）


參考文獻(xiàn)


[Bishop] Pattern Recognition And Machine Learning. C.M.Bishop. Springer, 2006（cryppie在本版曾發(fā)過電子版）
[Winn] Variational Message Passing and its Applications. John M. Winn. Ph.D. dissertation, 2004(可google到)