Gibbs sampling -- batch LDA

  詳細的推導我就不記錄了，畢竟各種文章中都有講到LDA的各種實作算法。用variational inference的，用gibbs sampling的。Gibbs sampling又有batch的，online的，incremental的等等。這裡隻提一種常用的batch gibbs sampling算法，即由Griffiths和Steyers提出的collapsed Gibbs sampler。

  其中batch gibbs sampling 也就是傳統的靜态資料集上運作的LDA算法，這也是我們這一篇文章所涉及到的，動态的o-LDA和iLDA在以後的文章中講。結合上一篇文章中提到的Gibbs抽樣基本思想來了解，這個抽樣器的狀态空間是主題在每一篇文章中的詞上的分布。該算法被稱為“collapsed”是由于它把變量 θ 和 ϕ 都積掉了，隻留下隐含主題變量 zN 需要被抽樣。這種思想也是統計推斷中常用到的，即将不關心的變量都盡量積掉，這樣能大大降低算法的時空複雜度。

  對于算法collapsed Gibbs sampler，它的核心就是對單詞 j 基于以下條件機率進行抽樣：

P(zj|zN∖j,wN)∝n(wj)zj,N∖j+βn(dj)zj,N∖j+αn(∙)zj,N∖j+Wβn(dj)∙,N∖j+Tα

  其中 ZN∖j 表示 (z1,...,zj−1,zj+1,...,zN) ， W 是vocabulary的大小，也就是不同單詞的個數。n(wj)zj,N∖j表示目前iteration時，單詞 wj 被配置設定為主題 zj 的次數， n(∙)zj,N∖j 是所有詞被配置設定為主題 zj 的個數，等等。

經過算法

1: initialize zN randomly from 1,...,TN

2: loop

3:  choose j from {1,…,N}

4:  sample zj from P(zj|zN∖j,wN)

收斂到後驗機率分布 P(zN|wN) 。也就得到了我們所希望求得的每個詞所屬主題。