目錄：[ - ]

      最近學(xué)習(xí)了LDA Topic聚類算法，里面涉及到許多概率論的知識(shí)，需要回過(guò)頭去學(xué)習(xí)，這里做個(gè)小結(jié)，方便記憶，同時(shí)也希望能把它講明白。

LDA模型算法簡(jiǎn)介：

      算法 的輸入是一個(gè)文檔的集合D={d1, d2, d3, ... , dn}，同時(shí)還需要聚類的類別數(shù)量m；然后會(huì)算法會(huì)將每一篇文檔 di 在 所有Topic上的一個(gè)概率值p；這樣每篇文檔都會(huì)得到一個(gè)概率的集合di=（dp1，dp2，..., dpm）；同樣的文檔中的所有詞也會(huì)求出 它對(duì)應(yīng)每個(gè)Topic的概率，wi = （wp1，wp2，wp3，...，wpm）；這樣就得到了兩個(gè)矩陣，一個(gè)文檔到Topic，一個(gè)詞到Topic。

      這樣LDA算法，就將文檔和詞，投射到了一組Topic上，試圖通過(guò)Topic找出文檔與詞間，文檔與文檔間，詞于詞之間潛在的關(guān)系；由于LDA屬于無(wú)監(jiān)督算法，每個(gè)Topic并不會(huì)要求指定條件，但聚類后，通過(guò)統(tǒng)計(jì)出各個(gè)Topic上詞的概率分布，那些在該Topic上概率高的詞，能非常好的描述該Topic的意義。

LDA模型構(gòu)建原理：

      在講LDA模型之前，會(huì)先介紹下 Unigram Model （詞袋模型）、Bayes Unigram Model（貝葉斯詞袋模型），以及PLSA 概率潛在語(yǔ)義分析，之所以先介紹這些模型，首先它們是LDA模型的基礎(chǔ)，LDA是將它們組合和演變的結(jié)果；其次這些模型比簡(jiǎn)單，了解起來(lái)會(huì)容易些。

Unigram Model（詞袋模型）：

     LDA既然是聚類算法，而聚類算法大多數(shù)時(shí)候，都在尋找兩個(gè)東西的相似度。

     最開(kāi)始，大家想要判斷兩篇文檔是否相似，最簡(jiǎn)單直接的方法就是看文檔里出現(xiàn)的詞是否一樣，其個(gè)數(shù)是否相近。于Unigram Model（詞袋模型）就是實(shí)現(xiàn)這樣的思路設(shè)計(jì)的。所以為了得到文檔集合中，所有文檔的共性的規(guī)律，詞袋模型，假設(shè)：一篇文檔生成的過(guò)程就是 獨(dú)立的拋一個(gè)具有M面的骰子（M是所有詞的個(gè)數(shù)），N次（N是該文檔里詞的個(gè)數(shù)），這樣文檔的生成，剛好可以看作是個(gè)多項(xiàng)式分布：

      文檔集合中，每個(gè)詞出現(xiàn)的概率就是要求的參數(shù)，通過(guò)EM算法可以確定下來(lái)，這樣就得到了模型。

Bayes Unigram Model（貝葉斯詞袋模型）

      在詞袋模型中，我們簡(jiǎn)單的認(rèn)為文檔里每個(gè)詞出現(xiàn)的概率是個(gè)定數(shù)（即骰子的每個(gè)面的概率），但Bayes學(xué)派不這么認(rèn)為，他們認(rèn)為這些概率應(yīng)該是一個(gè)隨機(jī)過(guò)程產(chǎn)生的，于是生成一篇文檔的過(guò)程可以描述為：先隨機(jī)抽取一個(gè)M面的骰子， 再用這個(gè)骰子獨(dú)立拋N次。那么這個(gè)模型的分布如下：

      其中后邊部分，是多項(xiàng)式分布，我們已經(jīng)知道，為了方便計(jì)算我們假設(shè) 為Dirichlet分布，它是多項(xiàng)式分布的共軸分布

      簡(jiǎn)單介紹下 Dirichlet 分布：比如 拋了100詞骰子，得到6個(gè)面的一個(gè)概率，記為一個(gè)實(shí)驗(yàn)，重復(fù)這個(gè)實(shí)驗(yàn)100次，那么這100次的實(shí)驗(yàn)中，這6個(gè)面的概率的概率分布，就是Dirichlet分布，它是分布之上的分布。

      例如：1點(diǎn)（骰子六個(gè)面之一） 在這100次實(shí)驗(yàn)（每個(gè)實(shí)驗(yàn)拋100次） 是 0.15的概率為 0.12，實(shí)際我們這么想，100次實(shí)驗(yàn)中，有12次，1點(diǎn)在一個(gè)實(shí)驗(yàn)內(nèi)出現(xiàn)了15次，可以看作是總共拋10000次，1點(diǎn)出現(xiàn)15×12=180次。這10000次實(shí)驗(yàn)，視為一個(gè)大的多項(xiàng)式分布，于是可以得出他們有相同的概率分布公式，這就是前面所提到的共軸分布，且有如下性質(zhì)：

                            先驗(yàn)的Dirichlet分布+多項(xiàng)式分布 = 后驗(yàn)的Dirichlet分布

     上述的例子中，你會(huì)發(fā)現(xiàn)，它與我們的Bayes Unigram Model（貝葉斯詞袋模型）已經(jīng)很相似了。一個(gè)實(shí)驗(yàn)里的100次拋骰子，可以看作是先驗(yàn)的Dirichlet分布，也就是模型中確定骰子各個(gè)面概率的那個(gè)隨機(jī)過(guò)程，而重復(fù)這個(gè)這個(gè)實(shí)驗(yàn)100次，可以看作是后面的根據(jù)這個(gè)骰子確定文檔的一個(gè)過(guò)程。

     Dirichlet分布還有一個(gè)重要的性質(zhì)，它的最大似然估計(jì)可以通過(guò)如下公式，證明過(guò)程有些復(fù)雜，暫不推導(dǎo)了：

PLSA潛在語(yǔ)義分析

      在文本聚類的時(shí)候，常常會(huì)遇到這樣一種問(wèn)題：例如在NBA的相關(guān)新聞中提到“石佛”，和提到“鄧肯”它們應(yīng)該是指的同一個(gè)人，確實(shí)兩個(gè)不同的詞；而另一篇關(guān)于教育的新聞里也提到了“鄧肯”，但此“鄧肯”非彼“鄧肯”，它可能指的是美國(guó)教育部部長(zhǎng)“阿恩·鄧肯”；而這兩篇NBA新聞和一篇教育新聞，很可能就被錯(cuò)誤的聚類了。

      于是，可以發(fā)現(xiàn)詞在不同的語(yǔ)義環(huán)境下，同一個(gè)詞可能表達(dá)不同意思，而同一個(gè)意思可能產(chǎn)生不同的詞。PLSA潛在語(yǔ)義分析，就是為了解決這樣的問(wèn)題。它在文檔和詞之間加了一層主題（Topic），先讓文檔和主題產(chǎn)生關(guān)聯(lián)，再在主題中尋找詞的概率分布。

      PLSA模型將文檔的生成這樣設(shè)計(jì)：第一步，我們拋一個(gè)有H面的骰子，每個(gè)面代表一個(gè)主題，各個(gè)面概率不一，得到一個(gè)主題；第二步，這個(gè)主題又對(duì)應(yīng)了一個(gè)有T個(gè)面的骰子，每個(gè)面代表一個(gè)詞，拋這骰子N次，得到一篇文章。其實(shí)我覺(jué)得這個(gè)模型可以看作是兩個(gè)詞袋模型的組合，第一個(gè)做一次，確定主題，第二個(gè)重復(fù)獨(dú)立做N詞，確定文章。下面是一個(gè)直觀圖（借用LDA數(shù)學(xué)八卦的圖了）：

      這樣概率分布公式如下：

LDA主題聚類模型

      這時(shí)Bayes學(xué)派的朋友們又出現(xiàn)，歷史是如此的相似，他們又對(duì)PLSA下手了，認(rèn)為PLSA里面的兩種骰子（產(chǎn)生主題的骰子和主題對(duì)應(yīng)詞的骰子），各個(gè)面的概率都不應(yīng)該是確定，應(yīng)該由一個(gè)隨機(jī)過(guò)程來(lái)得出。于是讓PLSA的兩個(gè)詞袋模型，變成兩個(gè)Bayes詞袋模型，就是LDA了

      前面已經(jīng)介紹了，Bayes詞袋模型的概率分布是一個(gè)Dirichlet 同軸分布，LDA 的整個(gè)物理過(guò)程實(shí)際就是兩個(gè)Dirichlet 同軸分布，而 LDA 模型的參數(shù)估計(jì)也就出來(lái)了，通過(guò)那個(gè)重要的性質(zhì)，如下：

LDA 算法設(shè)計(jì) 與Gibbs Sampling

      算法步驟：

      1. 對(duì)文檔集合中的每篇文檔d，做分詞，并過(guò)濾掉無(wú)意義詞，得到語(yǔ)料集合W = {w1, w2, …, wx}。
      2. 對(duì)這些詞做統(tǒng)計(jì)，得到 p（wi|d）。
      3. 為語(yǔ)料集合W中的每個(gè) wi ，隨機(jī)指定一個(gè)主題 t，作為初始主題。
      4. 通過(guò) Gibbs Sampling 公式， 重新采樣 每個(gè) w 的所屬 主題t， 并在語(yǔ)料中更新 直到Gibbs Sampling 收斂。
      收斂以后得到 主題-詞 的概率矩陣，這個(gè)就是LDA矩陣，而 文檔-主題的的概率矩陣也是能得到的，統(tǒng)計(jì)后，就能能得到文檔-主題的概率分布。

      Gibbs Sampling 公式：
      Gibbs Sampling 公式，可以用于計(jì)算 某x維度的空間中，兩個(gè)平行點(diǎn)之間轉(zhuǎn)移的概率。 比如在 二維空間（x, y平面），點(diǎn)a（x1，y1） 轉(zhuǎn)移到 b（x1，y2）的概率記為P，P（a ->b） = p(y2|x1 )

      于是上述中第4步，可以視為我們將一個(gè)詞對(duì)應(yīng)的 文檔和Topic的概率 看作是一個(gè)點(diǎn)在二維平面里的兩個(gè)維度，詞在不同的文檔和不同的主題里，通過(guò)Gibbs Sampling公式，不斷的轉(zhuǎn)移（即重新采樣），直至收斂。 下面是Gibbs Sampling公式收斂的一個(gè)圖，可以給大家一個(gè)直觀印象（來(lái)自LDA數(shù)學(xué)八卦）。  

LDA（Latent Dirichlet Allocation）學(xué)習(xí)筆記

最近在看LDA算法，經(jīng)過(guò)了幾天掙扎，總算大致了解了這個(gè)算法的整體框架和流程。

示例

LDA要干的事情簡(jiǎn)單來(lái)說(shuō)就是為一堆文檔進(jìn)行聚類（所以是非監(jiān)督學(xué)習(xí)），一種topic就是一類，要聚成的topic數(shù)目是事先指定的。聚類的結(jié)果是一個(gè)概率，而不是布爾型的100%屬于某個(gè)類。國(guó)外有個(gè)博客[1]上有一個(gè)清晰的例子，直接引用：

Suppose you have the following set of sentences:

• I like to eat broccoli and bananas.
• I ate a banana and spinach smoothie for breakfast.
• Chinchillas and kittens are cute.
• My sister adopted a kitten yesterday.
• Look at this cute hamster munching on a piece of broccoli.

What is latent Dirichlet allocation? It’s a way of automatically discovering topics that these sentences contain. For example, given these sentences and asked for 2 topics, LDA might produce something like

• Sentences 1 and 2: 100% Topic A
• Sentences 3 and 4: 100% Topic B
• Sentence 5: 60% Topic A, 40% Topic B
• Topic A: 30% broccoli, 15% bananas, 10% breakfast, 10% munching, … (at which point, you could interpret topic A to be about food)
• Topic B: 20% chinchillas, 20% kittens, 20% cute, 15% hamster, … (at which point, you could interpret topic B to be about cute animals)

上面關(guān)于sentence 5的結(jié)果，可以看出來(lái)是一個(gè)明顯的概率類型的聚類結(jié)果（sentence 1和2正好都是100%的確定性結(jié)果）。

再看例子里的結(jié)果，除了為每句話得出了一個(gè)概率的聚類結(jié)果，而且對(duì)每個(gè)Topic，都有代表性的詞以及一個(gè)比例。以Topic A為例，就是說(shuō)所有對(duì)應(yīng)到Topic A的詞里面，有30%的詞是broccoli。在LDA算法中，會(huì)把每一個(gè)文檔中的每一個(gè)詞對(duì)應(yīng)到一個(gè)Topic，所以能算出上面這個(gè)比例。這些詞為描述這個(gè)Topic起了一個(gè)很好的指導(dǎo)意義，我想這就是LDA區(qū)別于傳統(tǒng)文本聚類的優(yōu)勢(shì)吧。

LDA整體流程

先定義一些字母的含義：

• 文檔集合D，topic集合T
• D中每個(gè)文檔d看作一個(gè)單詞序列< w1,w2,...,wn >，wi表示第i個(gè)單詞，設(shè)d有n個(gè)單詞。（LDA里面稱之為word bag，實(shí)際上每個(gè)單詞的出現(xiàn)位置對(duì)LDA算法無(wú)影響）
• D中涉及的所有不同單詞組成一個(gè)大集合VOCABULARY（簡(jiǎn)稱VOC）

LDA以文檔集合D作為輸入（會(huì)有切詞，去停用詞，取詞干等常見(jiàn)的預(yù)處理，略去不表），希望訓(xùn)練出的兩個(gè)結(jié)果向量（設(shè)聚成k個(gè)Topic，VOC中共包含m個(gè)詞）：

• 對(duì)每個(gè)D中的文檔d，對(duì)應(yīng)到不同topic的概率θd < pt1,..., ptk >，其中，pti表示d對(duì)應(yīng)T中第i個(gè)topic的概率。計(jì)算方法是直觀的，pti=nti/n，其中nti表示d中對(duì)應(yīng)第i個(gè)topic的詞的數(shù)目，n是d中所有詞的總數(shù)。
• 對(duì)每個(gè)T中的topic t，生成不同單詞的概率φt < pw1,..., pwm >，其中，pwi表示t生成VOC中第i個(gè)單詞的概率。計(jì)算方法同樣很直觀，pwi=Nwi/N，其中Nwi表示對(duì)應(yīng)到topic t的VOC中第i個(gè)單詞的數(shù)目，N表示所有對(duì)應(yīng)到topic t的單詞總數(shù)。

LDA的核心公式如下：

p(w|d) = p(w|t)*p(t|d)

直觀的看這個(gè)公式，就是以Topic作為中間層，可以通過(guò)當(dāng)前的θd和φt給出了文檔d中出現(xiàn)單詞w的概率。其中p(t|d)利用θd計(jì)算得到，p(w|t)利用φt計(jì)算得到。

實(shí)際上，利用當(dāng)前的θd和φt，我們可以為一個(gè)文檔中的一個(gè)單詞計(jì)算它對(duì)應(yīng)任意一個(gè)Topic時(shí)的p(w|d)，然后根據(jù)這些結(jié)果來(lái)更新這個(gè)詞應(yīng)該對(duì)應(yīng)的topic。然后，如果這個(gè)更新改變了這個(gè)單詞所對(duì)應(yīng)的Topic，就會(huì)反過(guò)來(lái)影響θd和φt。

LDA算法開(kāi)始時(shí)，先隨機(jī)地給θd和φt賦值（對(duì)所有的d和t）。然后上述過(guò)程不斷重復(fù)，最終收斂到的結(jié)果就是LDA的輸出。