Fast LDA(1/3)

大体、CGSのLDAは挙動が解ってきたので、Fast LDAの理解に入る。

http://www.ics.uci.edu/~welling/publications/papers/rtp378-porteous.pdf

4. FAST LDA

For most real data sets after several iterations of the Gibbs sampler, the probability mass of the distribution p(zij = k|z¬ij , x, α, β) becomes concentrated on only a small set of the topics as in Figure 4.

Gibbs samplerの何度か繰り返し処理を実施した、多くの実データセットでが、分布確率(probability mass of the distribution ) p が図4に示すようにトピックの小さなセットに集約される。

FastLDA takes advantage of this concentration of probability mass by only checking a

subset of topics before drawing a correct sample. After calculating the unnormalized probability in (1) of a subset of topics, FastLDA determines that the sampled value

does not depend on the probability of the remaining topics.

Fast LDAは、正しいサンプルを選び足す前にtopicのサブセットを一回だけチェックすることで、このprobability massの集約に対するadvantageを活用する。topicのサブセットの(1)で示す非正規化確率を計算した後で、Fast LDAは残りのtopicでの確率においてsampled valueが必要ないかを決定する。

To describe how FastLDA works, it is useful to introduce a graphical depiction of how a sample for zij is conventionally drawn. We begin by segmenting a line of unit length into K sections, with the kth section having length equal to p(zij = k|z¬ij , x, α, β). We then draw a

sample for zij by drawing a value uniformly from the interval, u ∼ Uniform[0,1], and selecting the value of zij based on the segment into which u falls; see Figure 2.

FastLDAがどのように挙動するかを記載するには、それは図によってzijのsampleが利便性高く選択されることを説明する事が良い。我々はまず、K sectionsに分割された単位長さを導入する。それぞれのk番目のsectionはp()だけの長さを持つ。我々はそのあとで、u←一様乱数(0～1)に従ってzijをsampleする、そしてuよりも小さいsegmentが位置するzijの値を選択する（図２参照）

As an alternative, suppose that we have a sequence of bounds on the normalization constant Z, denoted Z1 . . .ZK, such that Z1 ≥ Z2 ≥ . . . ≥ ZK = Z. Then, we can graphically depict the sampling procedure for FastLDA in a similar way, seen in Figure 3.

更に、定数Zによｔって正規化された境界の順列を考える。ここで、Z1≧Z2≧...≧Zk=Zである。同じようにしてFastLDAで行われるsampling処理を図示することができる（図３参照）