Splay Tree
研究上必要があって, 前々からずっと気になっていた, SleatorとTarjanの スプレー木(Splay Tree) [LINK] を実装した。 スプレー木は「自己調整(自己組織化)二分木」ともいわれる通り, 頻度の高いアイテムをアクセスの際に木の上の方に自動的に持ってくることで, 高頻度なアイテムへの高速なアクセスを実現する順序木。 自然言語の文字列や単語列の頻度は偏りや Power law の固まりなので, 非常に適している と思う。 かつ, 最悪の場合でもスプレー木は 全体を通して, O(log n) のアクセスを提供することがわかっている。 トライを表現するデータ構造としては, 松本研的には Double Array や その実装である Darts がすぐ思い浮かぶと思いますが, Double Array は既に固定されたトライには高速にアクセス できるものの, 新しいノードの
lwlm, The Latent Words Language Model. - mots quotidiens.
というわけで, 公開しました。 "lwlm, The Latent Words Language Model". http://chasen.org/~daiti-m/dist/lwlm/ 潜在語言語モデル(LWLM)は, 各単語の裏に隠れた「潜在語」を教師なしで推定すること のできる言語モデルです。 ソシュールの一般言語学講義を読んでいる方は, (論文の著者はそう書いていませんが) これは, ソシュールの「範列」の計算的な表現だということがすぐにわかるかと思います。その意味でも, 非常に面白い(&恐らく, NLPの他のタスクにも役立つ)モデルです。 詳しくは, 先日のMCMC研究会のスライド をご覧下さい。 EMNLP 2009の原論文 *1 では SRILM を使って近似的にやっているらしい(全ての可能な単語を考慮していないらしい) ですが, ここでは本当に全て真面目にベイズ推定してい
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
