anobiidae's blog

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

CodeIQ

[完了] 9 1742(同心円上の分割) 2016/1/4 8 2428 (くねくね) 2016/1/4 7 2528 (Markdown修正) 2016/1/3 6. 1678 (BIT反転) 2016/1/3 5. 1715 (柱問題) 2016/1/2 4. 2351 (誤字判定) 2016/1/2 3. 2546 (BIT逆転) 2016/1/2 2. 2210 (ルイージ問題) 2…

すてにゃんとは何かを冷静になって考えてみる

www.adventar.org です!! つまりどういうことだってばよ! こういうのみ興味ある人は、がち勢であるすてにゃん https://twitter.com/stefafafan をフォローするといいっぽい! 音げーが好き。 アニメが嫌いじゃない。 Web系な技術的話も好き すてにゃん ( …

友利奈緒の「他人に認知されない能力」をコンピュータビジョンは実現できるか?

www.adventar.org こちらの10日目の記事でございます。 はじめに 友利奈緒には魅力があふれているが、あえて!!今回は消す方向で考える。 すなわち、友利奈緒の特殊能力である「任意の一人の視覚から消える能力」を、コンピュータビジョンによって疑似的に…

ECGSまとめ。

Standard-CGS ・全ドキュメント、全単語の「出現回数」分処理をするので重たい。 ECGS-Shortcut ・全ドキュメントの単語は同じtopicに属するものと、ざっくり決める。 ・100回出現していても1回で決めれる。 ECGS-Dynamic ・全ドキュメントの単語は異なるtop…

4.2 ECGS-Dynamic (4/4)

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…

4.2 ECGS-Dynamic (3/4)

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, γ ]で初期化す…

4.2 ECGS-Dynamic (2/3)

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 (1/3)

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

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

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で、と。

FastLDAまとめ

文書ごとにtopicはどうせ最後は集中するでしょ? だったら、0~K全部のtopicを順番に見なくてもいいじゃない。どうせ大体外れると。 だったら、indx[Document][seq] にtopic参照すべき順番を入れておきましょう。例えば、t=3になる文章ならば、indx[] = { 3,…

FastLDA つまり……どういうことだってばよ!?

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

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

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を評…

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…

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となるような正規化定数において…

Fast LDA(3/3)

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…

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の代わりに、我々はそれぞれのt…

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 o…

ほそく、ほそく

new_z = numpy.random.multinomial(1, p_z / p_z.sum()).argmax() multinomialは(第1引数)回だけ、(第二引数)確率の試行を繰り返し行って、その時の回数を求めるかな?で、その引数に対して最大値を求めれば「一番選択されうるもの」になると。

LDAの実装その2

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[…

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

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…

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

http://d.hatena.ne.jp/aidiary/20101230/1293691668 http://fukushimu.blog.shinobi.jp/Entry/76/ ここらへんを参考に、ipadicからもうちょっとだけ賢い(というか都合のよい)辞書を作ろうか思案中だったけど、ライセンス条項がめんどくさいから、なしかな…

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

Windows版MeCabの場合、 ①インストール時に文字コード指定 ②インストール後のメニューで、Recompile XXXX dictionary の二か所で文字コード指定ができそうだけど…… 実質上、①インストール時、のみが有効っぽい。 こまったもんだなあ? x64環境特有の問題?と…

4.1 Unigram model

4.1 Unigram model unigram model下では、全てのdocumentのwordは1つの周辺確率から独立して存在しています。 p(w)= ... これを図3aにグラフィックモデルとして図示します。

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…

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)) もし全ての有…

MeCabるか…… Windowsな場合

MeCabのライセンスは GPL(the GNU General Public License) LGPL(Lesser GNU General Public License) BSD ライセンス に従って本ソフトウェアを使用,再配布することができます。 ということなので、BSDライセンスに従えば、LGPLのために動的リンク対応をし…

3. Latent Dirichlet allocation(3/3)

θで積分し、zで総和をとると、我々はdocumentの周辺分布を得られる: p(w | α, β ) = ... 最後に、1documentに対する周辺確率の積によって、corpusの確率が得られる。 p(D | α, β ) = ... LDA modelを図1に確率グラフィックモデルとして表した。この図が明…

3. Latent Dirichlet allocation(2/3)

k次元のディレクレ任意変数θが(k-1) simplexの値をとるとする。(θiは0よりも大きく、かつΣθi=1であるとき、k次元ベクトルθはk-1 simplexである)そして、θがこのsimplex上においては以下の確率分布を持つ。 p(θ|α) = Γ(Σα) / Π (Γ α) θ_1 ^ {α_1 - 1)} ..…

補講:条件付確率

http://ja.wikipedia.org/wiki/%E6%9D%A1%E4%BB%B6%E4%BB%98%E3%81%8D%E7%A2%BA%E7%8E%87 P(A|B) :ある事象B が起こるという条件の下で別の事象A の確率 P(A,B) :ある事象Aとある事象B が同時に起こる確率 p(w_n | z_n , β) だと、 「あるz_nとβの条件下に…

3. Latent Dirichlet allocation(1/3)

3. Latent Dirichlet allocation 潜在ディレクト配分法(LDA)は、corpusの生成確率モデルです。基本的な考えは、文章は潜在的topicの任意の混在で表現され、更にtopicはワードの分布で特徴づけられている。1 LDAは、courpus Dの中の各document wに対して、次…

2. Notation and terminology(2/2)

形式的に、私たちは次の用語を定義します: wordは、{1...V}でインデックスを付けられた vocabulary からのitemであると定義されて、不連続データの基本単位です。我々はwordsを単位基準ベクトルを使用して表現します、これはある要素が1と等しく、それ以外は…

2. Notation and terminology(1/2)

それではまずLDAの御本尊たる、 http://www.cs.princeton.edu/~blei/papers/BleiNgJordan2003.pdf を読みましょうと。 Exciteの翻訳がほとんと使えるレベルだなあ…… 2. 注釈と単語 我々はこの論文においてここでは「words」「documents」と「corpora」のよう…

さて、最新近いものは?

うーん、ICML2011で報告があったというこれが面白そうなんだけどなあ。 http://www.slideshare.net/tsubosaka/icml2011-readingsage

TF-IDFからLDAまでの軌跡(らしきもの)

LDA(Latent Dirichlet Allocation)の論文 (David M.Blei, et al , 2003)にあった、ここら辺のドキュメント解析技術について纏めてみると Information retrieval(IR) (Baeza-Yates and Ribeiro-Nto, 1999) tf-idf scheme (Salton and McGill, 1983) latent sc…

今後の計画?

LDA(Latent Ditichlet Allocation)ってなーに?(~8/15) Gibbs samplingってなーに?(~9/1) HPC(Hierarchical Poisson Convolution)ってなーに?(~9/15) ぐらいかなー、今のところは。