Latent dirichlet allocation note -- Prepare
轉自莘莘學子blog ：?http://ljm426.blog.163.com/blog/static/120003220098110425415/
By: Zhou, Blog:?http://foreveralbum.yo2.cn
1 基礎知識
1.1 貝葉斯統計
假設有兩個箱子，每個箱子裝了8個球，A箱子3個紅球5個白球，B箱子6個紅球2個白球。如果問從A箱子摸出一個紅球的概率，那么答案是3/8，如果問從B箱子摸出一個白球的概率，那么為2/8。這樣的正向推理很簡單。但是如果問摸出一個紅球，它是從A箱子中摸出的概率是多少，這又如何求呢？貝葉斯方法正是用來求這種”逆”概率。
P(X,Y)表示X,Y的聯合概率，有如下公式P(X,Y)=P(Y|X)P(X)，由于P(X,Y)=P(Y,X)，于是我們得到P(Y|X)P(X)=P(X|Y)P(Y)，將左邊P(X)移到右邊得到：
這就是貝葉斯公式，其中P(Y|X)稱為后驗分布，P(X)稱為先驗分布，P(X|Y)稱為似然函數。貝葉斯問題的詳細描述可以參考Pattern Recognition and Machine Learning[1].該書第一章對貝葉斯方法做了詳細的解釋。
下面討論一個概率問題，一對夫婦有兩個孩子，已知其中一個是男孩，問另一個也是男孩的概率？
令A=另一個也是男孩 B=已知其中一個是男孩
由貝葉斯：P(A|B) = P(B|A)P(A)/P(B)
其中 P(B|A) = 1 ，因為另一個也是男孩，表示兩個都是男孩。
P(A) = 0.25 即如果有兩個孩子，兩個都是男孩的概率0.25
P(B) = 0.75 即如果有兩個孩子，那么其中一個是男孩的概率為0.75
因此P(A|B) = 1*0.25/0.75=1/3
1.2 Dirichlet distribution
假設我們在和一個不老實的人玩擲骰子游戲。按常理我們覺得骰子每一面出現的幾率都是1/6，但是擲骰子的人連續擲出6，這讓我們覺得骰子被做了手腳，而這個骰子出現6的幾率更高。而我們又不確定這個骰子出現6的概率到底是多少，所以我們猜測有50%的概率是：6出現的概率2/7，其它各面1/7；有25%的概率是：6出現的概率3/8，其它各面1/8；還有25%的概率是：每個面出現的概率都為1/6，也就是那個人沒有作弊，走運而已。用圖表表示如下：
我們所猜測的值，如果設為X的話，則表示X的最自然的分布便是Dirichlet distribution。設隨機變量X服從Dirichlet分布，簡寫為Dir(α)，即X~Dir(α)。Α是一個向量，表示的是某個事件出現的次數。比如對于上例，骰子的可能輸出為{1,2,3,4,5,6}，假設我們分別觀察到了5次1~5，10次6，那么α = {5,5,5,5,5,10}。X則表示上例中的各種概率組合，比如{1/7,1/7,1/7, 1/7,1/7,2/7}；{1/8, 1/8, 1/8, 1/8, 1/8, 3/8}；{1/6, 1/6, 1/6, 1/6, 1/6, 1/6}，那么P(X)則表示了該概率組合出現的概率，也就是概率的概率。
以下是公式：
下圖來自WIKI[2]，圖像化了當K=3時的dirichlet分布。
Dirichlet分布的重要性質：
Dirichlet分布是多項分布的共軛分布，也就是說，先驗分布為Dirichlet分布，似然函數為多項分布，那么后驗分布仍為Dirichlet分布。
在LDA中，Dirichlet分布是為了描述文檔—主題層面的概率分布，一個文檔由多個主題組成，而Dirichlet分布描述了主題集合的分布。具體將在后面討論。
之所以選擇Dirichlet分布是因為其共軛特性大大減小了計算量。
1.3 Expectation-Maximization (EM) Algorithm[3][4]
EM算法是用來計算極大似然估計。EM有兩個主要應用環境，第一個是觀測到的數據不完整或其它原因導致數據丟失，第二個是似然函數無法直接計算但可以用隱含變量表示。LDA中的參數估計屬于后者。
概括的說，EM算法首先隨機給每個參數賦值，然后迭代的執行兩個步驟，分別叫做E-STEP和M-STEP。在E-STEP，EM算法計算出期望的似然函數，由于這時已經為所有參數賦值，所以似然函數是可以計算的。在M-STEP，EM算法重新估計參數值，按照最大化似然函數的標準。這樣多次迭代直到收斂為止。
本文大致討論下EM的推理，更具體的分析參考Further Reading中EM相關資料。
假設某次迭代中我們估計的參數是θ(n)，而我們的目的是希望找到θ(n+1)使得P(X|θ(n+1))盡可能的大于P(X|θ(n))。將lnP(X|θ)表示成L(θ|X)，則我們的目標是使使下式盡可能的大：
(1)
現在考慮隱含變量Z：
于是(1)式改寫成：
(2)
下面是The Expectation Maximization Algorithm A short tutorial[3]關于(2)式的推導：
因此：
(3)
現在令：
(4)
前面已經提高過，我們的目的是找到θ，使得L(θ)最大。而從(3)，(4)中我們可以看到l(θ|θn)就是L(θ)的下界，所以我們的目標就成了找到一個下界逼近L(θ):
E-STEP:
計算條件數學期望
M-STEP：
最大化這個數學期望，得出此時的θ。
1.4 Variational Inference[5]
Variational Inference是用來估計后驗分布的方法。該方法無法直接計算后驗分布的情況。在Variational Message Passing and its Applications[5]的1.8節有該方法的非常詳細的推理，我這里只大致介紹該方法的思想。
當我們遇到無法計算后驗分布的情況，會希望使用一個函數來近似它，設為Q：
我們自然希望P,Q的差最小。這里的差用 Kullback-Leibler (KL) divergence表示：
經過下式的變換：
可以從上面看到，右邊的logP(D)不依賴于Q，所以我們的工作相當于使右式加號左邊的表達式最小。另該項為L(Q)：
經過推導（具體見論文[5]）可得下式：
右邊第一項為似然函數，第二項L(Q)相當于一個下界。要使KL盡量下，就要使右邊兩項盡可能的接近。所以L(Q)相當于logP(D|H)的下界。我們現在要做的，就是用L(Q)下屆逼近logP(D|H)。還要記住我們是要用Q(H)來近似后驗分布，因此我們需要找一個可解的Q。最簡單的方法是認為Q的n個參數都是獨立的，于是：
根據這個前提，就可以迭代來求L(Q)，直到收斂。具體過程參見Variational Message Passing and its Applications
1.5 Bayesian Network
在LDA原始paper[6]中有幅貝葉斯網絡圖，想看懂這幅圖只需要一點貝葉斯網絡的基礎知識就可以了，所以這里把需要理解的地方列出來，貝葉斯網絡的深入討論可以參考Pattern Recognition and Machine Learning[1]一書第8章。
先舉一個例子：聯合概率P(a,b,c)=P(c|a,b)P(b|a)P(a)可以表示為如下圖
箭頭表示條件概率，圓圈表意一個隨機變量。這樣我們就可以很容易的畫出一個條件概率對于的貝葉斯網絡。
對于更復雜的概率模型，比如
由于有N個條件概率，當N很大時，在圖中畫出每一個隨機變量顯然不現實，這是就要把隨機變量畫到方框里：
這就表示重復N個tn.
在一個概率模型中，有些是我們觀察到的隨機變量，而有些是需要我們估計的隨機變量，這兩種變量有必要在圖中區分開：
如上圖，被填充的圓圈表明該隨機變量被觀察到并已經設為了被觀察到的值。
了解上面三個定理就能輕松的讀懂LDA原始paper中的貝葉斯網絡圖了。
總結
以上是生活随笔為你收集整理的Latent dirichlet allocation note -- Prepare的全部內容，希望文章能夠幫你解決所遇到的問題。
