[B! LDA] sleepy_yoshiのブックマーク

A clever way to derive the collapsed Gibbs sampling for LDA

sleepy_yoshi 2012/08/15

LDA

リンク

Mining Contrastive Opinions on Political Texts using Cross-Perspective Topic Model(WSDM 2012) 読んだ & 実装して試した - 糞糞糞ネット弁慶

Mining contrastive opinions on political texts using cross-perspective topic model 概要複数の立場(perspective)から書かれた文章があった時，論点(topic)ごとに立場の主張をまとめ，それらの主張の違いを定量的に出力する．例えば，自民党と民主党のマニフェストが与えられた時，「年金に対する自民/民主の主張」「安全保障に関する自民/民主の主張」をそれぞれまとめ，かつ，あるクエリに対する意見の違いを数値で出力する．モデル documentが名詞などのtopic word(LDAなどのword)と形容詞や動詞，副詞などのopinion wordで構成されるとする．生成モデルは次のような過程を辿るとする．まずトピックを選ぶトピックに従って単語(topic word)を選ぶ次に，意見(opinio

sleepy_yoshi 2012/07/22

LDA

リンク

Interactive Topic Modeling を読む (Hu, Boyd-Graber and Satinoff ACL2011) - 木曜不足

9/3 の ACL 読み会で読む [Hu+ ACL11] Interactive Topic Modeling(ITM) の資料です(途中ですが力尽きましたすいません……)。【追記】ディリクレ木と Interactive Adding Constraints and Unassigning(←これがこの論文のキモ！) についての説明を追加しました。【／追記】 Interactive Topic Modeling(ITM) とは通常の LDA は教師無しであり、結果の制御は基本的にできない baseball と football が同じトピックに入って欲しいと思っても、うまく分類されない場合はパラメータを変えて試行錯誤するとか、分類後にトピックをクラスタリングするか ITM は LDA に「単語ＡとＢは同じトピックに入って欲しい」という制約を「後から」入れられるモデル Notatio

sleepy_yoshi 2011/09/04

リンク

Regularized Latent Semantic Indexing - tsubosakaの日記

最近勉強会で発表する予定のものと仕事関係の論文しか読んでなかったのでこのブログにはあんまり書けなかったんだけど、久々に書いてみる。紹介する論文はSIGIR 2011のLSIを語彙数が大きい時にも効率的に並列化できるようにしたという論文[1]。論文概要 PLSIやLDAみたいなトピックモデルは情報検索においても性能向上で重要であるが、語彙数が多い時スケールしないという問題点がある(文章数に関しては効率的な実装が知られている。例えば[2])。このためよく行われるのが語彙数を1万とかに制限する方法ですが、情報検索への応用を考えるとこのアプローチは問題がある(文章分類やクラスタリングへの応用であればこれで問題ない)。このため著者らはRLSIという方法を提案した。これにより160万文章、語彙数700万のデータセットに対して16台のマシンでトピック数500のとき1時間半で処理できた(おそらく1イ

sleepy_yoshi 2011/08/27

リンク

Vector Space, Probabilistic LSI, and LDA

Thoughts on Information Retrieval, Search Engines, Data Mining, Science, Engineering, and Programming source: http://www.cs.princeton.edu/~blei/papers/BleiNgJordan2003.pdf There is a kind of buzz about Probabilistic Latent Semantics Indexing, so this post goes. From VSM to LSI Prior to 1988 the prevalent IR model was Salton’s Vector Space Model (VSM). This model treats documents and queries as vec

sleepy_yoshi 2011/06/22

LDA

リンク

LDA で実験その１:stop words の扱い方でどう変わる？ - 木曜不足

LDA Python 実装編 LDA 解説編というわけで連載じゃあないけど第3回。わざわざ自前で実装したんだから、LDA で細かい設定で実験してみる。 NLTK のブラウンコーパスの 0〜99 までの 100 個のドキュメントをコーパスとし、トピック数は K=20、ハイパーパラメータはα=0.5, β=0.5、イテレーションは 100 回、というのが基本条件。*1 そして stop words の扱いを「除外(-s 0)」、「除外しないで他の単語と同様に扱う(-s 1)」、そして「初期化時にストップワードを１つのトピック(k=0)に集中させる。その他の単語は残りのトピック(k>0)に分散させる (-s 2)」と変えてみて、それぞれ 10回推論を行わせて、perplexity やトピック-単語分布について確認する。ただし -s 0 のときは -s 2 との対比でトピック数 K=19 にして

sleepy_yoshi 2011/03/11

LDA

リンク

Latent Dirichlet Allocations(LDA) の実装について - 木曜不足

昨日の "Latent Dirichlet Allocations in Python" の続きで実験結果を載せようかと思ったけど、先にやっぱりもうちょっと LDA を説明しておこう。 LDA の初出は [Blei+ 2003] Latent Dirichlet Allocation 。ただし [Blei+ 2003] で "LDA" としているのはトピック-単語分布がただの多項分布(事前分布無し)のもの。"LDA" としてよく目にするトピック-単語多項分布にディリクレ事前分布が入ったものは "Smoothed LDA" として記載されている(確かにβでスムージングしているのと等価)。今回実装した LDA も後者の "Smoothed LDA"。その LDA はこんな感じ。αとβはハイパーパラメータだから、チビ黒丸で書いて欲しいんだけどね。 (図は Wikipedia-en の LD

sleepy_yoshi 2011/03/11

LDA

リンク

Latent Dirichlet Allocations の Python 実装 - 木曜不足

LDA とは "Latent Dirichlet Allocation"。文書中の単語の「トピック」を確率的に求める言語モデル。「潜在的ディリクレ配分法」と訳されていることもあるが、その名前だと「それってなんだっけ？」という人のほうが多そうｗ。各単語が「隠れトピック」(話題、カテゴリー)から生成されている、と想定して、そのトピックを文書集合から教師無しで推定することができる。特徴は、果物の apple と音楽の apple とコンピュータ関連の apple を区別することが出来る(ことが期待される)という点。そのために、どのトピックを生成しやすいかという分布を各文章も持つ。細かい話は略。結果の見方としては、定量的にはパープレキシティを見るし(一般に小さいほどいい)、定性的には各トピックがどのような単語を生成するか、その確率上位のものを見てふむふむする。この「各トピックが生成する単語」

sleepy_yoshi 2011/03/11

LDA

リンク

LDA で実験その２:初期値を逐次サンプリングにしてみた - 木曜不足

Collapsed Variational Bayesian での LDA 推論も実装してみたのだが、そのときに「パープレキシティが下がりきるのは非常に早いのに、その時点ではトピック-単語分布がストップワードだらけ」「イテレーションの最初のうちはパープレキシティがほとんど動かない」という現象にぶちあたってしまった。で、その解決方法を考えているうちに、一つひらめいたことがあったので、また Collapsed Gibbs LDA に戻ってちょいと試してみた。といっても大層なことではなく、推論の初期値に各 term のトピックをランダムに割り振るのだが、それを完全にランダム( K 個のトピックが一様分布)にするのではなく、Gibbs サンプリングに用いる事後分布を逐次更新しつつ、その分布からトピックをサンプリングするようにしてみたのだ。つまり p( z_mn | z_mn より一つ前までの

sleepy_yoshi 2011/03/11

LDA

リンク

[機械学習] LDAのコードを書いてみた - tsubosakaの日記

昔書いたことがあったけど、どこかにいってしまったのでもう一度書いてみた。推論方法にはギブスサンプリングと変分ベイズの2つがあるけど、導出も実装もより楽なcollapsed gibbs sampling(Griffiths and Steyvers, PNAS, 2004)の方を採用。 Token.java package lda; public class Token { public int docId; public int wordId; public Token(int d , int w){ docId = d; wordId = w; } } LDA.java package lda; import java.util.*; public class LDA { int D; // number of document int K; // number of topic int

sleepy_yoshi 2011/01/29

LDA

リンク

PythonでLDAを実装してみる

Latent Dirichlet Allocationはテキストのような不連続データのための生成的確率モデル。入力はドキュメント。出力はドキュメントを特徴づける何か（tf-idfみたいなもん）。基本的なアイディアは、あるドキュメントは潜在的ないくつかのトピックが混合していて、それぞれのトピックは語の分布で特徴づけられている、ということ。論文[1]ではαとβというパラメータを用いてドキュメントが以下のように生成されると仮定している。ドキュメントのトピックの分布θがディリクレ分布Dir(α)に基づいて選ばれる。ドキュメントの語数N個になるまで以下を繰り返す。トピックznが多項分布Mult(θ)に基づいて選ばれる。単語wnが確率p(wn|zn,β)で選ばれる。ただし、トピックzの数をk個、単語wの種類をV個とすると、パラメータαはk次元のベクトル、βはk x V次元の行列でβij=

sleepy_yoshi 2011/01/29

LDA

リンク

「オーマｘクックパッド勉強会」で発表してきました - mroriiの日記

去る12月16日、クックパッドさんのオフィスで行われたオーマｘクックパッド勉強会にて「SPYSEEの新検索機能の裏側」というタイトルで発表してきました。クックパッドの皆様＆見に来ていただいた皆様、どうもありがとうございました。発表スライドはこちらになります：Ohmapadslideshareを見られない方は下記のPDFをご参照くださいhttp://dl.dropbox.com/u/9436074/ohmapad.pdfSPYSEEの検索ログを見ると、「さかなクン」や「ウィルスミス」など、検索全体のほぼ99%を人名が占めています。今回の発表では「人名に限らず、『Ruby』や『料理家』などの『キーワード』でも検索できますよ」ということを伝えようとしました。肝心の検索の計算に関しては厳密性にこだわらず、分かりやすさを優先させたつもりですが、「難しかった」との声もあったようですね、すみません。。。

sleepy_yoshi 2010/12/20

search
LDA

リンク

[機械学習] スライスサンプリング - tsubosakaの日記

持橋さんのlwlmに関する記事を読んで、スライスサンプリング[1,2]というのが有用そうということで調べてみたのでメモ。スライスサンプリング概要今確率分布f(x)がの形で与えられており、このf(x)からxをサンプリングすることを考える。ここでl(x)は非負の関数、\pi(x)は確率密度関数とする。サンプリングを以下の手順で行なう初期値x_0を適当に決定する u_t = Uniform(0 , l(x_t))で一様分布からサンプリング X_t = { x | u_t < l(x)}とする x_{t+1}をX_tに含まれるxから\pi(x)に従ってサンプリングする 2へ戻るここでu_tの値は捨てて、{x_t}だけ取り出すとf(x)に従うxをサンプリングできる。何が嬉しいのかスライスサンプリングの話は以前から聞いたことがあったのですが、連続の場合だと4の部分が簡単にできそうではな

sleepy_yoshi 2010/03/29

ML
LDA

リンク

[機械学習] PRML Hackathon #2 - tsubosakaの日記

PRML Hackathonに行ってきました。今回のHackathonでは昨日書いたスライスサンプリングという手法をLDAの推論に使ってみて通常のGibbs samplerと比較してみました。結果としてはサンプリング速度が2-3倍程度高速になり、手法の有効性を確かめることができました。また、perplexityの値は Gibbs samplerよりも少し悪い結果となりました。(誤解を招く表現でした、詳しくは下に追記しました) Prml HackathonView more presentations from tsubosaka. 追記: perplexityの値が悪くなったというと変分ベイズのように近似が入って性能が悪くなる印象を与えますがそうではないです。 slice samplerはgibbs samplerと同様に十分な回数反復すれば正しい確率分布からのサンプルを取ることができ

sleepy_yoshi 2010/03/29

PRML
LDA

リンク

[論文] Parallel Inference for Latent Dirichlet Allocation on Graphics Processing Units - tsubosakaの日記

NIPS 2009のonline papersがすでにダウンロードできるように*1なってたのでタイトルを眺めていたらGPUでLDAを並列化するという論文があって読んだので少し紹介してみる。まず、彼らの論文[1]ではLDAの推論アルゴリズムのうち、Collapsed Gibbs sampling(CGS)とCollapsed Variational Bayes(CVB)の2つに関して並列化を試みているがCollapsed Gibbs samplingの方に関してのみ紹介する。また、彼らの論文ではGPGPUの統合開発環境としてCUDAを用いている。 LDAについて LDAは論文[2]で提案された、文章生成モデルでトピック分析などに広く用いられている。モデルの推論アルゴリズムとしては変分ベイズ[1]、ギブスサンプリング[4]、EP、collapsed 変分ベイズ[5]などが知られている。こ