LDA及Gibbs Sampling

心不留意外塵 2016-03-30

展開全文

from http://blog./?p=1265

本系列博文介紹常見概率語言模型及其變形模型，主要總結(jié)PLSA、LDA及LDA的變形模型及參數(shù)Inference方法。初步計劃內(nèi)容如下

第二篇 LDA及Gibbs Sampling

1 LDA概要

LDA 是由Blei,Ng, Jordan 2002年發(fā)表于JMLR的概率語言模型，應(yīng)用到文本建模范疇，就是對文本進行“隱性語義分析”（LSA），目的是要以無指導學習的方法從文本中發(fā)現(xiàn)隱含的語義維度-即“Topic”或者“Concept”。隱性語義分析的實質(zhì)是要利用文本中詞項(term)的共現(xiàn)特征來發(fā)現(xiàn)文本的Topic結(jié)構(gòu)，這種方法不需要任何關(guān)于文本的背景知識。文本的隱性語義表示可以對“一詞多義”和“一義多詞”的語言現(xiàn)象進行建模，這使得搜索引擎系統(tǒng)得到的搜索結(jié)果與用戶的 query在語義層次上match，而不是僅僅只是在詞匯層次上出現(xiàn)交集。

2 概率基礎(chǔ)

2.1 隨機生成過程及共軛分布

要理解LDA首先要理解隨機生成過程。用隨機生成過程的觀點來看，文本是一系列服從一定概率分布的詞項的樣本集合。最常用的分布就是 Multinomial分布，即多項分布，這個分布是二項分布拓展到K維的情況，比如投擲骰子實驗，N次實驗結(jié)果服從K=6的多項分布。相應(yīng)的，二項分布的先驗Beta分布也拓展到K維，稱為Dirichlet分布。在概率語言模型中，通常為Multinomial分布選取的先驗分布是Dirichlet 分布，因為它們是共軛分布，可以帶來計算上的方便性。什么是共軛分布呢？在文本語言模型的參數(shù)估計-最大似然估計、MAP及貝葉斯估計一文中我們可以看到，當我們?yōu)槎椃植嫉膮?shù)p選取的先驗分布是Beta分布時，以p為參數(shù)的二項分布用貝葉斯估計得到的后驗概率仍然服從Beta分布，由此我們說二項分布和Beta分布是共軛分布。這就是共軛分布要滿足的性質(zhì)。在LDA中，每個文檔中詞的Topic分布服從Multinomial分布，其先驗選取共軛先驗即Dirichlet分布；每個Topic下詞的分布服從Multinomial分布，其先驗也同樣選取共軛先驗即Dirichlet分布。

2.2 Multinomial分布和 Dirichlet分布

上面從二項分布和Beta分布出發(fā)引出了Multinomial分布和Dirichlet分布。這兩個分布在概率語言模型中很常用，讓我們深入理解這兩個分布。Multinomial分布的分布律如下

多項分布來自N次獨立重復實驗，每次實驗結(jié)果可能有K種，式子中 $\vec{n}$ 為實驗結(jié)果向量，N為實驗次數(shù)， $\vec{p}$ 為出現(xiàn)每種實驗結(jié)果的概率組成的向量，這個公式給出了出現(xiàn)所有實驗結(jié)果的概率計算方法。當K=2時就是二項分布，K=6時就是投擲骰子實驗。很好理解，前面的系數(shù)其實是枚舉實驗結(jié)果的不同出現(xiàn)順序，即

$\frac{N!}{\prod_{i=1}^K n^{(k)}!}$

后面表示第K種實驗結(jié)果出現(xiàn)了 $n^{(k)}$ 次，所以是概率的相應(yīng)次冪再求乘積。但是如果我們不考慮文本中詞出現(xiàn)的順序性，這個系數(shù)就是1。本文后面的部分可以看出這一點。顯然有 $\vec{p}$ 各維之和為1，所有 $n^{(k)}$ 之和為N。

Dirichlet分布可以看做是“分布之上的分布”，從Dirichlet分布上Draw出來的每個樣本就是多項分布的參數(shù)向量 $\vec{p}$ 。其分布律為

$\vec{\alpha}$ 為Dirichlet分布的參數(shù)，在概率語言模型中通常會根據(jù)經(jīng)驗給定，由于是參數(shù)向量 $\vec{p}$ 服從分布的參數(shù)，因此稱為“hyperparamer”。 $\Delta(\vec{\alpha})$ 是Dirichlet delta函數(shù)，可以看做是Beta函數(shù)拓展到K維的情況，但是在有的文獻中也直接寫成 $B(\vec{\alpha})$ 。根據(jù)Dirichlet分布在 $\vec{p}$ 上的積分為1（概率的基本性質(zhì)），我們可以得到一個重要的公式

$\int_{\vec{p}}\prod_{k=1}^Kp_k^{\alpha_k - 1}d\vec{p} = \Delta(\vec{\alpha})$

這個公式在后面LDA的參數(shù)Inference中經(jīng)常使用。下圖給出了一個Dirichlet分布的實例

在許多應(yīng)用場合，我們使用對稱Dirichlet分布，其參數(shù)是兩個標量：維數(shù)K和參數(shù)向量各維均值 $\alpha = \frac{\sum\alpha_k}{K}$ . 其分布律如下

關(guān)于Dirichlet分布，維基百科上有一張很有意思的圖如下

File:LogDirichletDensity-alpha 0.3 to alpha 2.0.gif

這個圖將Dirichlet分布的概率密度函數(shù)取對數(shù)

$\log (f(x_1,\dots, x_{K-1}; \alpha_1,\dots, \alpha_K)) = \log\left(\frac{1}{\mathrm{B}(\alpha)} \prod_{i=1}^K x_i^{\alpha_i - 1}\right)= + \sum_{i=1}^K \alpha_i \log(x_i) - \sum_{i=1}^K \log(x_i) - \sum_{i=1}^K \log(\Gamma(\alpha_i)) + \log(\Gamma(\sum_{i=1}^K \alpha_i))$

并且使用對稱Dirichlet分布，取K=3，也就是有兩個獨立參數(shù) x_1, x_2 ，分別對應(yīng)圖中的兩個坐標軸，第三個參數(shù)始終滿足 x_3 = 1-x_1-x_2 且 $\alpha_1=\alpha_2=\alpha_3=\alpha$ ，圖中反映的是 $\alpha$ 從0.3變化到2.0的概率對數(shù)值的變化情況。

3 unigram model

我們先介紹比較簡單的unigram model。其概率圖模型圖示如下

關(guān)于概率圖模型尤其是貝葉斯網(wǎng)絡(luò)的介紹可以參見 Stanford概率圖模型（Probabilistic Graphical Model）— 第一講貝葉斯網(wǎng)絡(luò)基礎(chǔ)一文。簡單的說，貝葉斯網(wǎng)絡(luò)是一個有向無環(huán)圖，圖中的結(jié)點是隨機變量，圖中的有向邊代表了隨機變量的條件依賴關(guān)系。unigram model假設(shè)文本中的詞服從Multinomial分布，而Multinomial分布的先驗分布為Dirichlet分布。圖中雙線圓圈表示我們在文本中觀察到的第n個詞， $n\in [1,N]$ 表示文本中一共有N個詞。加上方框表示重復，就是說一共有N個這樣的隨機變量。 $\vec{p}$ 和 $\vec{\alpha}$ 是隱含未知變量，分別是詞服從的Multinomial分布的參數(shù)和該Multinomial分布的先驗Dirichlet分布的參數(shù)。一般 $\vec{\alpha}$ 由經(jīng)驗事先給定， $\vec{p}$ 由觀察到的文本中出現(xiàn)的詞學習得到，表示文本中出現(xiàn)每個詞的概率。

4 LDA

理解了unigram model之后，我們來看LDA。我們可以假想有一位大作家，比如莫言，他現(xiàn)在要寫m篇文章，一共涉及了K個Topic，每個Topic下的詞分布為一個從參數(shù)為 $\vec{\beta}$ 的Dirichlet先驗分布中sample出來的Multinomial分布（注意詞典由term構(gòu)成，每篇文章由word構(gòu)成，前者不能重復，后者可以重復）。對于每篇文章，他首先會從一個泊松分布中sample一個值作為文章長度，再從一個參數(shù)為 $\vec{\alpha}$ 的Dirichlet先驗分布中sample出一個Multinomial分布作為該文章里面出現(xiàn)每個Topic下詞的概率；當他想寫某篇文章中的第n個詞的時候，首先從該文章中出現(xiàn)每個Topic的Multinomial分布中sample一個Topic，然后再在這個Topic對應(yīng)的詞的Multinomial分布中sample一個詞作為他要寫的詞。不斷重復這個隨機生成過程，直到他把m篇文章全部寫完。這就是LDA的一個形象通俗的解釋。用數(shù)學的語言描述就是如下過程

轉(zhuǎn)化成概率圖模型表示就是

圖中K為主題個數(shù)，M為文檔總數(shù)，是第m個文檔的單詞總數(shù)。 $\vec{\beta}$ 是每個Topic下詞的多項分布的Dirichlet先驗參數(shù)， $\vec{\alpha}$ 是每個文檔下Topic的多項分布的Dirichlet先驗參數(shù)。 $z_{m,n}$ 是第m個文檔中第n個詞的主題， $w_{m,n}$ 是m個文檔中的第n個詞。剩下來的兩個隱含變量 $\vec{\theta}_m$ 和 $\vec{\phi}_k$ 分別表示第m個文檔下的Topic分布和第k個Topic下詞的分布，前者是k維(k為Topic總數(shù))向量，后者是v維向量（v為詞典中term總數(shù)）。

給定一個文檔集合， $w_{m,n}$ 是可以觀察到的已知變量， $\vec{\alpha}$ 和 $\vec{\beta}$ 是根據(jù)經(jīng)驗給定的先驗參數(shù)，其他的變量 $z_{m,n}$ ， $\vec{\theta}_m$ 和 $\vec{\phi}_k$ 都是未知的隱含變量，也是我們需要根據(jù)觀察到的變量來學習估計的。根據(jù)LDA的圖模型，我們可以寫出所有變量的聯(lián)合分布

那么一個詞 $w_{m,n}$ 初始化為一個term t的概率是

也就是每個文檔中出現(xiàn)topic k的概率乘以topic k下出現(xiàn)term t的概率，然后枚舉所有topic求和得到。整個文檔集合的似然函數(shù)就是

5 用Gibbs Sampling學習LDA

5.1 Gibbs Sampling的流程

從第4部分的分析我們知道，LDA中的變量 $z_{m,n}$ ， $\vec{\theta}_m$ 和 $\vec{\phi}_k$ 都是未知的隱含變量，也是我們需要根據(jù)觀察到的文檔集合中的詞來學習估計的，那么如何來學習估計呢？這就是概率圖模型的Inference問題。主要的算法分為exact inference和approximate inference兩類。盡管LDA是最簡單的Topic Model，但是其用exact inference還是很困難的，一般我們采用approximate inference算法來學習LDA中的隱含變量。比如LDA原始論文Blei02中使用的mean-field variational expectation maximisation 算法和Griffiths02中使用的Gibbs Sampling，其中Gibbs Sampling 更為簡單易懂。

Gibbs Sampling 是Markov-Chain Monte Carlo算法的一個特例。這個算法的運行方式是每次選取概率向量的一個維度，給定其他維度的變量值Sample當前維度的值。不斷迭代，直到收斂輸出待估計的參數(shù)?？梢詧D示如下

初始時隨機給文本中的每個單詞分配主題 $z^{(0)}$ ,然后統(tǒng)計每個主題z下出現(xiàn)term t的數(shù)量以及每個文檔m下出現(xiàn)主題z中的詞的數(shù)量，每一輪計算，即排除當前詞的主題分配，根據(jù)其他所有詞的主題分配估計當前詞分配各個主題的概率。當?shù)玫疆斍霸~屬于所有主題z的概率分布后，根據(jù)這個概率分布為該詞sample一個新的主題 $z^{(1)}$ 。然后用同樣的方法不斷更新下一個詞的主題，直到發(fā)現(xiàn)每個文檔下Topic分布 $\vec{\theta}_m$ 和每個Topic下詞的分布 $\vec{\phi}_k$ 收斂，算法停止，輸出待估計的參數(shù) $\vec{\theta}_m$ 和 $\vec{\phi}_k$ ，最終每個單詞的主題 $z_{m,n}$ 也同時得出。實際應(yīng)用中會設(shè)置最大迭代次數(shù)。每一次計算的公式稱為Gibbs updating rule.下面我們來推導LDA的聯(lián)合分布和Gibbs updating rule。

5.2 LDA的聯(lián)合分布

由LDA的概率圖模型，我們可以把LDA的聯(lián)合分布寫成

第一項和第二項因子分別可以寫成

可以發(fā)現(xiàn)兩個因子的展開形式很相似，第一項因子是給定主題Sample詞的過程，可以拆分成從Dirichlet先驗中SampleTopic Z下詞的分布 $\vec{\phi}_z$ 和從參數(shù)為 $\vec{\phi}_z$ 的多元分布中Sample詞這兩個步驟，因此是Dirichlet分布和Multinomial分布的概率密度函數(shù)相乘，然后在 $\vec{\phi}_z$ 上積分。注意這里用到的多元分布沒有考慮詞的順序性，因此沒有前面的系數(shù)項。 $n_z^{(t)}$ 表示term t被觀察到分配topic z的次數(shù)， $n_m^{(k)}$ 表示topic k分配給文檔m中的word的次數(shù).此為這里面還用到了2.2部分中導出的一個公式

$\int_{\vec{p}}\prod_{k=1}^Kp_k^{\alpha_k - 1}d\vec{p} = \Delta(\vec{\alpha})$

因此這些積分都可以轉(zhuǎn)化成Dirichlet delta函數(shù)，并不需要算積分。第二個因子是給定文檔，sample當前詞的主題的過程。由此LDA的聯(lián)合分布就可以轉(zhuǎn)化成全部由Dirichlet delta函數(shù)組成的表達式

這個式子在后面推導Gibbs updating rule時需要使用。

5.3 Gibbs updating rule

得到LDA的聯(lián)合分布后，我們就可以推導Gibbs updating rule，即排除當前詞的主題分配，根據(jù)其他詞的主題分配和觀察到的單詞來計算當前詞主題的概率公式

里面用到了伽馬函數(shù)的性質(zhì)

$\Gamma(z+1)=z \, \Gamma(z).$

同時需要注意到

這一項與當前詞的主題分配無關(guān)，因為無論分配那個主題，對所有k求和的結(jié)果都是一樣的，區(qū)別只在于拿掉的是哪個主題下的一個詞。因此可以當成常量，最后我們只需要得到一個成正比的計算式來作為Gibbs updating rule即可。

5.4 Gibbs sampling algorithm

當Gibbs sampling 收斂后，我們需要根據(jù)最后文檔集中所有單詞的主題分配來計算 $\vec{\theta}_m$ 和 $\vec{\phi}_k$ ，作為我們估計出來的概率圖模型中的隱含變量。每個文檔上Topic的后驗分布和每個Topic下的term后驗分布如下

可以看出這兩個后驗分布和對應(yīng)的先驗分布一樣，仍然為Dirichlet分布，這也是共軛分布的性質(zhì)決定的。

使用Dirichlet分布的期望計算公式

我們可以得到兩個Multinomial分布的參數(shù) $\vec{\theta}_m$ 和 $\vec{\phi}_k$ 的計算公式如下

綜上所述，用Gibbs Sampling 學習LDA參數(shù)的算法偽代碼如下

6 參考文獻及推薦Notes

本文部分公式及圖片來自 Parameter estimation for text analysis，感謝Gregor Heinrich詳實細致的Technical report。看過的一些關(guān)于LDA和Gibbs Sampling 的Notes，這個是最準確細致的，內(nèi)容最為全面系統(tǒng)。下面幾個Notes對Topic Model感興趣的朋友也推薦看一看。

[1] Christopher M. Bishop. Pattern Recognition and Machine Learning (Information Science and Statistics). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2006.
[2] Gregor Heinrich. Parameter estimation for text analysis. Technical report, 2004.
[3] Wang Yi. Distributed Gibbs Sampling of Latent Topic Models: The Gritty Details Technical report, 2005.

[4] Wayne Xin Zhao, Note for pLSA and LDA, Technical report, 2011.

[5] Freddy Chong Tat Chua. Dimensionality reduction and clustering of text documents.Technical report, 2009.

[6] Wikipedia, Dirichlet distribution , http://en./wiki/Dirichlet_distribution

轉(zhuǎn)自 http://blog.csdn.net/yangliuy/article/details/8302599