LDA
Standard-CGS ・全ドキュメント、全単語の「出現回数」分処理をするので重たい。 ECGS-Shortcut ・全ドキュメントの単語は同じtopicに属するものと、ざっくり決める。 ・100回出現していても1回で決めれる。 ECGS-Dynamic ・全ドキュメントの単語は異なるtop…
Figure 5 shows the plot of E(|M|) and H(ˆk) for different values of Idi. One can observe that as the entropy increases, the expectation value increases as well for large values of Idi. Intuitively, when P(z|w) is close to an uniform distri…
To achieve a high sampling rate at the beginning, Γdi is initialized as [0, · · · , 0, γ] for every type, where γ is the damping factor and γ ∈ N+. まず最初に高いsampling rateを保持するために、全てのtypeに対してΓdiを[0,...0, γ ]で初期化す…
An illustrated comparison of different sampling procedures is provided in Figure 4. 図4に異なるsampling処理の比較図を示す。 Given for instance an 8-tokens document with 5 times “cat” and 3 times “dog”. The standard CGS samples 8 times for …
4.2 ECGS-Dynamic The intuition behind ECGS-Dynamic is to automatically adapt ¯ St over the iterations, where ¯ St ∈ [ Σd Nd/W, 1]. Loosely speaking, we start CGS with a high sampling rate (e.g. ¯ S1 = 1), such that every token is involved…
4.1 ECGS-Shortcut To introduce our optimization strategies, we first define the sampling rate in CGS iteration t for type wdi as follows: 我々の最適化戦略を導入するために、CGS iteration tにおけるwdiに対するsampling rateを以下のように定義…
4. ECGS Algorithm In this section, two optimization strategies that form the ECGS algorithm are presented. The underling philosophy of the two strategies is the same: reducing the number of iterations Ndi in the 3rd loop. For the sake of c…
http://home.in.tum.de/~xiaoh/pub/ecgs.html http://home.in.tum.de/~xiaoh/pub/ecgs_slides.pdf 次はこのあたりかなあ？ 出現回数が多いものに積極的に割り当てていく、的なものかな。 dog:5 cat:3 → だったら、dog:cat = 5:3で、と。
文書ごとにtopicはどうせ最後は集中するでしょ？ だったら、0～K全部のtopicを順番に見なくてもいいじゃない。どうせ大体外れると。 だったら、indx[Document][seq] にtopic参照すべき順番を入れておきましょう。例えば、t=3になる文章ならば、indx[] = { 3,…
U = drand(); // draw indx = indx_dp[doc]; // point indx to current sort order U = 0.0～1.0の正規乱数。 indx は文章毎の「Z参照順番」 for (t_ = 0; t_ < T; t_++) { // for each possible topic (sorted order) t=indx[t_]; // t_ refers to sort #, …
4.3 Fast LDA Algorithm The sampling step for FastLDA begins with a sorted list of topics in descending order by Njk, the most popular topic for a document to the least popular. FastLDAのsampling stepは、まずNjkを逆順にするtopicのソート済…
4.2 Refinement Sequence Finally, we must also consider the order in which the topics are evaluated. Execution time improves as the number of topics considered before we find the segment sk l containing u decreases. 最後に、我々はtopicを評…
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…
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となるような正規化定数において…
By organizing the segments in this way, we can obtain a substantial advantage: この方法でsegmentを組織化することで、以下のようなadvantageを得る事が出来る。 we can check each segments in order, knowing only p1 . . . pk and Zk, and if we fin…
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の１つのsegmentの代わりに、我々はそれぞれのt…
大体、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 o…
new_z = numpy.random.multinomial(1, p_z / p_z.sum()).argmax() multinomialは（第１引数）回だけ、（第二引数）確率の試行を繰り返し行って、その時の回数を求めるかな？で、その引数に対して最大値を求めれば「一番選択されうるもの」になると。
def inference(self): """イテレーション1回分の推論を行う""" for m, doc in enumerate(self.docs): 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[…
http://d.hatena.ne.jp/n_shuyo/20110214/lda さんのコードを眺めつつ、CGBを実装するか… class LDA: """LDA : collapsed Gibbs で推論""" def __init__(self, K, alpha, beta): self.K = K self.alpha = alpha # parameter of topics prior self.beta = bet…
4.1 Unigram model unigram model下では、全てのdocumentのwordは１つの周辺確率から独立して存在しています。 p(w)= ... これを図3aにグラフィックモデルとして図示します。
4. Relationship with other latent variable models この章では、我々はLDAとテキストに対する単純な潜在変数モデル - unigram model, a mixture of unigrams そして pLSI model との比較を行う。さらに、我々はこれらのモデルと一体となった幾何学的解釈を…
3.2 A continuous mixture of unigrams 図1に示されるLDA model は古典的な階層的ベイズの論文の中でしばしば研究された2レベルのモデルより多少精巧です。隠しtopic変数zを除外する事で、我々はLDAを2階層modelとして理解する事が出来ます。 特にword分布 p…
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)) もし全ての有…
θで積分し、zで総和をとると、我々はdocumentの周辺分布を得られる： p(w | α, β ) = ... 最後に、１documentに対する周辺確率の積によって、corpusの確率が得られる。 p(D | α, β ) = ... LDA modelを図1に確率グラフィックモデルとして表した。この図が明…
k次元のディレクレ任意変数θが(k-1) simplexの値をとるとする。（θiは0よりも大きく、かつΣθi=1であるとき、k次元ベクトルθはk-1 simplexである）そして、θがこのsimplex上においては以下の確率分布を持つ。 p(θ|α) = Γ(Σα) ／ Π (Γ α) θ_1 ^ {α_1 - 1)} ..…
3. Latent Dirichlet allocation 潜在ディレクト配分法(LDA)は、corpusの生成確率モデルです。基本的な考えは、文章は潜在的topicの任意の混在で表現され、更にtopicはワードの分布で特徴づけられている。1 LDAは、courpus Dの中の各document wに対して、次…
形式的に、私たちは次の用語を定義します: wordは、{1...V}でインデックスを付けられた vocabulary からのitemであると定義されて、不連続データの基本単位です。我々はwordsを単位基準ベクトルを使用して表現します、これはある要素が1と等しく、それ以外は…
それではまずLDAの御本尊たる、 http://www.cs.princeton.edu/~blei/papers/BleiNgJordan2003.pdf を読みましょうと。 Exciteの翻訳がほとんと使えるレベルだなあ…… 2. 注釈と単語 我々はこの論文においてここでは「words」「documents」と「corpora」のよう…
