anobiidae's blog


4.1 Upper Bounds for Z(2/2)


H¨older’s inequality describes a class of bounds, for any valid choice of (p, q, r); these values are a design choice of the algorithm. A critical aspect in the choice of bounds is that it must be computationally efficient to maintain. In particular we want to be able to calculate Z0 and update ... in constant time.



We focus our attention on two natural choices of values which lead to computationally efficient implementations: (p, q, r) = (2, 2,∞) and (3, 3, 3).



For p, q, r < ∞, the norms can be updated in constant time, while for r = ∞, we have k~cl+1:Kkr = mink Nk which is also relatively efficient to maintain.

p,q,r < ∞に対して、normsは定数時間で交信がなされる。r=∞の間、我々は | c _l+1_k | = min Nl が管理的に効果的である。


Section 4.4 provides more detail on how these values are maintained. Empirically, we found that the first choice typically results in a better bound (see Figure 10 in Section 6.4).


section 4.4ではこれらの値の管理方法について更に詳細を言及する。経験的に我々は最初の選択が典型的に良いboundとなる結果であることを発見している(Section 6.4, 図10を参照)



FastLDA maintains the norms k~akp, k~bkq, k~ckr separately and then uses their product to bound Z. One might consider maintaining the norm k~a~bk, k~b~ck or even Z instead, improving on or eliminating the bound for Z.

FastLDAでは、norms ... を分割して管理する。そして、それらの積をbound zとして使う。norm ... を管理することが1つ考えられる。あるいは、それぞれのZを代わりにZのためにboundを減らすか削減する。


The problem with maintaining any combination of the vectors ~a,~b or ~c is that the update of one zij will cause many separate norms to change because they depend on the counts of zij variables, Nwkj .

vector a,b,cの集合をメンテナンスする問題は、一つのzijがアップデートされると分離したnormに対する変更が発生する事である、これはこれらがzij変数のカウントに依存しているためである。


For example, if we maintain dwk = bwkck, then a change of the value of zij from k to k′ requires changes to dwk, dwk′∀w resulting in O(2W) operations. However without

~d, only bwk, bwk′ , ck, ck′ change.

例えば、dwk = bwkckと管理していて、zijの値がkからk'に変わった場合に、dwkの健康が必要となる。dwk'∀wを求めるには、O(2W)が必要になる。しかし、dがなければ、たったbwk, bwk' ck, ck'を変更すればよい。



4.1 Upper Bounds for Z(1/2)

FastLDA depends on finding a sequence of improving bounds on the normalization constant, Z1 ≥ Z2 ≥ . . . ≥ ZK = Z. We first define Z in terms of component vectors ~a,~b,~c:

FastLDAではZ1 ≥ Z2 ≥ . . . ≥ ZK = Zとなるような正規化定数において、より高いboundを検索する必要があります。我々はtermにおけるcomponent vector a,b,cのZを以下のように定義します。






Then, the normalization constant is given by


Z= ...


To construct an initial upper bound Z0 on Z, we turn to the generalized version of H¨older’s inequality [7], which states

Zにおける、初期のupper bound Z0を構築するために、H olderの不等式の生成バージョンを用います。



Notice that, as we examine topics in order, we learn the actual value of the product ~ak~bk~ck. We can use these calculations to improve the bound at each step. We then have a bound at step l given by:

ここで注意すべき点として、順列に並んだtopicにおいては経験的に、我々はak bk ckの積の実質的な値を知っています。我々はそれぞれのステップで境界を増加する計算を用いる事が出来ます。そのとき、step lにおけるboundは以下の通りです。

Zl = ...


This sequence of bounds satisfies our requirements: it is decreasing, and if l = K we recover the exact value of Z. In this way the bound improves incrementally at each iteration

until we obtain the correct normalization factor.

boundのシーケンスでは我々の要求が守られる。これは減衰していく。そしてもしl=kであればZの値によってリカバリする。これによって、bound improveはそれぞれの繰り返しの中で増加をしていく、最終的に我々が正しい正規化factorを得る間に。

Fast LDA(3/3)

By organizing the segments in this way, we can obtain a substantial advantage:



we can check each segments in order, knowing only p1 . . . pk and Zk, and if we find that u falls within a particular segment sk l , the remaining segments are irrelevant.

我々はそれぞれのp1,...pkとして並んでいるsegmentとZkをチェックする。そしてもしsegment s_k_l部分でuが決定できれば、残りのsegmentについては見当違いとできる。


Importantly, if for our sequence of bounds Z1 . . .ZK, an intermediate bound Zl depends only on the values of ajk and bjk for k ≤ l, then we may be able to draw the sample after only examining topics 1 . . . l.

重要なことは、もしbounds Z1, ZKの我々のシーケンスに対しては、bound Zlはajk, bjkの値だけを必要としている場合、我々はきっとtopic 1...lだけからsampleを選出する事が出来るだろう。


Given that in LDA, the probability mass is typically concentrated on a small subset of topics for a given word and document, in practice we may have to do far fewer operations per sample on average.



※ aとかbの説明はまだ出てきていないっす。

Fast LDA(2/3)


Instead of having a single segment for topic k, of length pk/Z = p(zij = k|z¬ij , x, α, β), we instead have several segments skl . . . sk K associated with each topic.

pk/Z の長さに基づくtopic kの1つのsegmentの代わりに、我々はそれぞれのtopicに対応づけられるsegment sk( K)を導入する。


The first segment for a topic k, sk k, describes a conservative estimate of the probability of the topic given the upper bound Zk on the true normalization factor Z. Each of the subsequent segments associated with topic k, namely sk l for l > k, are the corrections for the missing probability mass for topic k given the improved bound Zl. Mathematically, the lengths of these segments are given by 


topic kに対する最初のセグメントであるs_k_kは、正規化係数Zにおけるuppor bound Zkが与えられた場合の、topic の確率の保守的な推定値を意味する。topic kに対応付けられたsegmentの部分は、s_k_lと称する(lはkよりも大きい)。s_k_lはbound Zlが与えられた場合の、topic kに対する失敗確率の補正量である。数学的には、これらのsegmentは以下のように与えられる。


s_k_k = ...

s_k_l= ...



Since the final bound ZK = Z, the total sum of the segment lengths for topic k is equal to the true, normalized probability of that topic:

final bound ZK = Z(topic kのsegmentの長さの合計)であり、それらのtopicの確率によって正規化される。

p() = Σ s_k_l


Therefore, as in the conventional sampling method, we can draw zij from the correct distribution by first drawing u ∼ Uniform[0, 1], then determining the segment in which it falls.

利便性あるsampling 手段のために、u←一様乱数(0~1)の正規分布からzijを選び、それ以下となるsegmentによって決定する。




Fast LDA(1/3)


大体、CGSのLDAは挙動が解ってきたので、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の値を選択する(図2参照)



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.






 new_z = numpy.random.multinomial(1, p_z / p_z.sum()).argmax() 




    def inference(self):
        for m, doc in enumerate(
            z_n = self.z_m_n[m]
            for n, t in enumerate(doc):
                # n 番目の単語 t (トピック z)についてカウンタを減算
                z = z_n[n]
                self.n_m_z[m, z] -= 1
                self.n_z_t[z, t] -= 1
                self.n_z[z] -= 1

                # トピックの事後分布からサンプリング
                p_z = self.n_z_t[:, t] * self.n_m_z[m] / self.n_z
                new_z = numpy.random.multinomial(1, p_z / p_z.sum()).argmax()

                # サンプリングされた新トピックを設定&カウンタを増加
                z_n[n] = new_z
                self.n_m_z[m, new_z] += 1
                self.n_z_t[new_z, t] += 1
                self.n_z[new_z] += 1                



foreach( as $m => $doc){

z_n = z_m_n[m];

foreach(doc in $n => $t){

z = z_n[n];

n_m_z[m, z] --; n_z_t[z,t] --; n_z[z] --;  # n番目の単語を無所属に。

new_z = ... は後でやるとして

z_n[n] = new_z

n_m_z[m, new_z] ++;

n_z_t[new_z, t] ++;

n_z[new_z] ++; # n番目の単語をnew_z所属に変更


という感じかー。 z_m_n[m][n] はm番目の文章のn番目のキーワードはどこのtopicですか?が入っていると。


                # トピックの事後分布からサンプリング
                p_z = self.n_z_t[:, t] * self.n_m_z[m] / self.n_z
                new_z = numpy.random.multinomial(1, p_z / p_z.sum()).argmax()



で、ここはGibbs samplingの更新式だろうなー

p_z_sum = 0;

for(i=0;i<K;i++){ p_z[i] = n_z_t[i, t] * self.n_m_z[m,i] / self.n_z[i]; p_z_sum += p_z[i]; }


multinomial() はDraw samples from a multinomial distribution.。




Fast LDAの論文からすると

P[k] ← P[k -1] + ... としておいて u ← uniform[0..1], u<P[k]/P[K]で探索と。






しーかたがないのでCGBのコードを解読解読 さんのコードを眺めつつ、CGBを実装するか…

class LDA: """LDA : collapsed Gibbs で推論""" def __init__(self, K, alpha, beta): self.K = K self.alpha = alpha # parameter of topics prior self.beta = beta # parameter of words prior

これは初期化部分。coppapsed Gibbs samplingの場合、α、βはvectorではなくvariableと。


 def set_corpus(self, corpus, stopwords): """コーパスの読み込みとカウンタの初期化""" voca = vocabulary.Vocabulary(stopwords==0) = [voca.doc_to_ids(doc) for doc in corpus] M = len( self.V = voca.size() self.z_m_n =  # topics of words of documents self.n_m_z = numpy.zeros((M, self.K)) + self.alpha # word count of each document and topic self.n_z_t = numpy.zeros((self.K, self.V)) + self.beta # word count of each topic and vocabulary self.n_z = numpy.zeros(self.K) + self.V * self.beta # word count of each topic 



self.docsは、えーっと、vocaのdoc_to_ids(doc) ただし、docはcurpus内の物を順繰りに使うと。idsは頻度……かな?



self_z_m_n は一次元配列(ただしまだ空)

self.n_m_z はarray(M×K)で、初期値α、これは確か高速化でこうやってると。


self.n_z はarray(K)で、初期値 V × β


 self.N = 0 for m, doc in enumerate( self.N += len(doc) z_n = numpy.random.randint(0, self.K, len(doc)) self.z_m_n.append(z_n) for t, z in zip(doc, z_n): self.n_m_z[m, z] += 1 self.n_z_t[z, t] += 1 self.n_z[z] += 1 return voca

Nは0で初期化したけど、docのlenで加算しますよ…… len(doc)が「この文章の単語出現数」で、Nは「このcorpusの単語出現数」か。


for m, doc in enumerate( は……?

をみるとつまり、 foreach( as $m => $doc)と(謎記載)



z_n は0~Kの間の、len(doc)=この文章の単語数の乱数。

self.z_m_nに追加する、とあるけど要するにz_m_n[m] = z_n ですと。

で、for t,z in zip(doc,z_n) ???


t in doc には単語、z in z_nには乱数で適当に決めたトピック、で「単語に適当にtopic割り振り」かな?

self.n_m_z[m,z] は「ある文章mのtopic zの出現数」

self.n_z_t[z,t] は「あるtopic zの単語 tの出現数」

self.n_z[z] は「あるtopic zの出現数」








②インストール後のメニューで、Recompile XXXX dictionary




 こまったもんだなあ? x64環境特有の問題?というわけでもなさそうだし。






4. Relationship with other latent variable models

4. Relationship with other latent variable models

この章では、我々はLDAとテキストに対する単純な潜在変数モデル - unigram model, a mixture of unigrams そして pLSI model との比較を行う。さらに、我々はこれらのモデルと一体となった幾何学的解釈を、それぞれの重要な違いと類似性を強調しながら示します。


3.2 A continuous mixture of unigrams

3.2 A continuous mixture of unigrams

図1に示されるLDA model は古典的な階層的ベイズの論文の中でしばしば研究された2レベルのモデルより多少精巧です。隠しtopic変数zを除外する事で、我々はLDAを2階層modelとして理解する事が出来ます。


特にword分布 p(w | θ,β)を考えると、


p(w | θ , β) = Σ p ( w| z, β) p ( z, θ)




我々はdocument wの生成プロセスを以下のように定義します:


1. Choose q  Dir(a).

2. For each of the N words w_n:

(a) Choose a word wn from p(w_n |  θ, β).





p(w | a, b) = ...


ここで、p(w_n | θ, β) は混在要素であり、p (θ | α) は混在加重になります。


図2はLDAに対するこの解釈を図示したものです。それは、LDAモデルの特別の実例から引き起こされるp(w|q, b)の上の分配を描きます。(V-1)-simplex上のこの分布が、k+kVパラメータだけに到達している、非常に興味深いmultimodal構造を表現しています。


3.1 LDA and exchangeability


3.1 LDA and exchangeability

任意変数(z_1, ... z_N)の有限集合、結合分布が順列に依存しない場合に、「exchangeable」であるという。もし、piが1からNまでの整数の順列を持っているならば、

p(z_1, ... z_N) = p (z_pi(1), ... , z_pi(z_N))


もし全ての有限の部分シーケンスがexchangeableであるならば、任意変数の無限集合はinfinitely exchangeableであるという。


De Finetti’s representation theorem は、任意変数のinfinitely exchangeable シーケンスの結合分布がパラメータ上のコンディションである事を示した。その条件として、任意パラメーターはいくつかの分布によって導出され、そして質問に対する任意変数は分布から独立し、かつ識別できるのであれば。


LDAでは、我々はwordsはtopicsから(固定のコンディション分布から)生成され、それぞれのtopicsはdocumentに対してinfinitely exchangeableである。de Finetti’s theorem



p(w; z) = ...


ここで、θはtopicに対するmultinormalな任意パラメータである。我々は Eq(3)を、周辺化されたtopic変数と、ディレクレト分布の特性θによる、documentsにおけるLDA分布として得られる。


MeCabるか…… Windowsな場合


  • GPL(the GNU General Public License)
  • LGPL(Lesser GNU General Public License)
  • BSD ライセンス に従って本ソフトウェアを使用,再配布することができます。