トピックモデルシリーズ 4 LDA （Latent Dirichlet Allocation）
このシリーズのメインともいうべきLDA（[Blei+ 2003]）を説明します。前回のUMの不満点は、ある文書に1つのトピックだけを割り当てるのが明らかにもったいない場合や厳しい場合があります。そこでLDAでは文書を色々なトピックを混ぜあわせたものと考えましょーというのが大きな進歩です。さてこの記事の表記法は以下になります。前回のUMの場合と同一です。 右2列は定数については数値を、そうでないものについてはR内の変数名を書いています。データは前の記事参照。 グラフィカルモデルは以下になります（左: LDA, 右（参考）: 前回のUM）。 見ると四角のプレートがまで伸びてきただけです。しかしながらこれが曲者でUMからかなりのギャップがあります。以下の吹き出しの順に説明していきます。 ① ここではハイパーパラメータからディリクレ分布に従って『文書の数だけ』が生成されます。このは以下のような
Bin Packing 問題 近似アルゴリズム
Bin Packing 問題 近似アルゴリズム ■ Bin Packing 問題は次のように定義される： いろいろな大きさのコップに、その容積一杯に水が入っているとする。各コップ u の容積は正の整数 s(u) とするとき、コップの集合を U とする。 一方、容積がどれも正の整数 B であるビンが K 個あるとする。 各コップの水はどれか一つのビンに注ぐとするとき、各ビンがこぼれないように注ぐ方法はあるか？ このように、方法が存在するか否かを問う問題は、「決定問題」と呼ばれる。 ■ 一方、次の問題を「最適化問題」と呼ぶ。 コップの集合Uに対して、最小何個のビンがあれば、各ビンがこぼれないようにできるか？ 最適化問題を解いて、最小のビンの数が OPT 個と分かったならば、決定問題は OPT ≦ K ならば、方法が存在し、 K ＜ OPT ならば、方法は存在しない というように簡単に解くこと
Compressed Permuterm Index: キーワード辞書検索のための多機能＆省メモリなデータ構造 - Preferred Networks Research & Development
はじめましてこんにちわ。 4月からPFIで働いているまるまる（丸山）です。最近のマイブームはスダチです。 リサーチブログの更新が再開されたので、私も流れに乗って初ブログを書いてみようと思います。 今回は社内の情報検索輪講で少し話題にあがったCompressed Permuterm Indexを紹介したいと思います。 Paolo Ferragina and Rossano Venturini. “The compressed permuterm index”, ACM Transactions on Algorithms 7(1): 10 (2010). [pdf] これを実装したので以下のgoogle codeに晒してみることにします。 http://code.google.com/p/cpi00/ 修正BSDライセンスです。ソースコードは好きにしてもらって構いませんが、完成度はまだまだな
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
