anobiidae's blog

個人的に自然言語処理とかに関して、調べ物したもののメモとかを残す場所。

4.1 Upper Bounds for Z(2/2)

自然言語処理 LDA

 

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.

Holder不等式はboundのクラスを意味している、それらは(p,q,r)に対する有効な選択である。これらの値はアルゴリズムによって設計された選択に基づく。boundを選択する中心的な考えは、管理のための計算効果である。特に我々はZ0の計算とアップデートを定数時間でできるようにした。

 

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).

我々は計算的に効率的な実装を導くための、２つの自然的な選択における導入に注目した。(p,q,e)=...

 

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 ... を管理することが１つ考えられる。あるいは、それぞれの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)

自然言語処理 LDA

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を以下のように定義します。

 

a=...

b=...

c=...

 

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の不等式の生成バージョンを用います。

Z0=...

 

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)

自然言語処理 LDA

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 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.

LDAにとってはこれによって、確率が、既知のwordとdocumentに対するtopicの小さな部分集合に集中する事が出来、実運用上、平均的に１サンプル当たりの処理を減らせた。

 

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

Fast LDA(2/3)

自然言語処理 LDA

 

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の代わりに、我々はそれぞれのtopicに対応づけられるsegment sk(sl1...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)

自然言語処理 LDA

 

大体、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処理を図示することができる（図３参照）

 

 

 

ほそく、ほそく

LDA 自然言語処理 
 new_z = numpy.random.multinomial(1, p_z / p_z.sum()).argmax()

 

multinomialは（第１引数）回だけ、（第二引数）確率の試行を繰り返し行って、その時の回数を求めるかな？で、その引数に対して最大値を求めれば「一番選択されうるもの」になると。

LDAの実装その２

自然言語処理 LDA 
    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[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

inferenceの意味は演繹、ね。

 

foreach(self.docs 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.。

で、p_z[i]/p_z_sumの確率で選んで最大になるものを選びます……

 

Cで組むのめんどくさい（；ω；）

Fast LDAの論文からすると

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

 

 

 

 

 

しーかたがないのでCGBのコードを解読解読

LDA 自然言語処理

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 = beta # parameter of words prior

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

 

 def set_corpus(self, corpus, stopwords): """コーパスの読み込みとカウンタの初期化""" voca = vocabulary.Vocabulary(stopwords==0) self.docs = [voca.doc_to_ids(doc) for doc in corpus] M = len(self.docs) 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

 

vocaはvocabraryファイルを読み込みます、かな？

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

 

Mは文書数、Vは全語彙数（つまりvocabularyに含まれるwordの種別数)

self_z_m_n は一次元配列（ただしまだ空）

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

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

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

 

 self.N = 0 for m, doc in enumerate(self.docs): 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(self.docs) は……？

http://d.hatena.ne.jp/meganii/20111121/1321884656

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

enumerate()は「この引数にindex付ける」という意味です、と。

 

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

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

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

docの各要素をkeyに、z_nの各要素をvalueにした配列を作って、t,zでそれぞれ回す、かな？

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の出現数」

と。

wikipediaのタイトルを辞書登録するか（車輪の再発明）

自然言語処理 MeCab

http://d.hatena.ne.jp/aidiary/20101230/1293691668

http://fukushimu.blog.shinobi.jp/Entry/76/

 

ここらへんを参考に、ipadicからもうちょっとだけ賢い（というか都合のよい）辞書を作ろうか思案中だったけど、ライセンス条項がめんどくさいから、なしかなあ……

MeCabの謎……メニューの「辞書リコンパイル」は無効？

MeCab 自然言語処理

Windows版MeCabの場合、

①インストール時に文字コード指定

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

の二か所で文字コード指定ができそうだけど……

 

実質上、①インストール時、のみが有効っぽい。

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

 

とりあえずWindowsユーザは気をつけてね、と。

（あれ？となると、ユーザー辞書作れない？）

 

 

4. Relationship with other latent variable models

自然言語処理 LDA

4. Relationship with other latent variable models

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

 

3.2 A continuous mixture of unigrams

自然言語処理 LDA

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 (θ | α) は混在加重になります。

 

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

 

3.1 LDA and exchangeability

自然言語処理 LDA

 

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

に基づけば、wordsとtopicsの順列の確率は以下の形式を取らねばならない。

 

p(w; z) = ...

 

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

 

MeCabるか…… Windowsな場合

自然言語処理

MeCabのライセンスは

  • GPL(the GNU General Public License)
  • LGPL(Lesser GNU General Public License)
  • BSD ライセンス　に従って本ソフトウェアを使用,再配布することができます。
ということなので、BSDライセンスに従えば、LGPLのために動的リンク対応をしなくてもいい……はず。
 
使うときは、MeCabのWindows版をダウンロード→exampleフォルダからライブラリとヘッダをコピー、って感じかな？