言語処理学会2011 の原稿「条件付確率場とベイズ階層言語モデルの統合による 半教師あり形態素解析」の原稿を置いておきました。 [PDF]
例によって?公式版は重要な図が入っていなかったりするので, ご興味のある方は 上をお取り下さい。

僕の発表は3/10の B-5 です。
このセッションでは, タイトルが地味なので一見わかりにくいと思いますが, CS研の新人の進藤君の「ベイズ学習による木接合文法獲得」が新しい本質的な研究で, かなりお薦めです。
木接合文法(Tree-Adjoining Grammar)は, 構文木に割り込み(言語学で言う変形操作 みたいなもの)を許すような, TSG(木代入文法)の拡張ですが *1 , 進藤君の話はこれを確率的にした確率的木接合文法の構文フラグメントを Pitman-Yor過程に従って生成されるとした上で, あらゆる接合の可能性を動的計画法で 考えて学習する, という新しい話です。

他にCS研からは, 目黒さんの B4-1 「POMDPを用いた聞き役対話システムの対話制御」 が内部のTalkを聞いたところ, 非常に筋のよい, 良い話だと思いました。 初日に強化学習のチュートリアルがあったはずなので, 関係も深いと思います。

---

日曜日だが, 坪坂君の実験 で Google sparsehash はやはり結構速かったことが わかったのに影響されて(?), 自製のHPYLMのコードを Google sparsehash で書き直してみることに。
というのは, もうすぐ公開する予定のプログラムで確率の計算がボトルネックに なっているらしいことが分かったからですが..。 *1

実際のプログラムはうまく抽象化して書いてあったことが幸いして, 少し直すだけで対応完了。

• ngramの各ノードから子供へのポインタを探す部分
• 予測するngramのノードから, 予測したい語(CRPオブジェクト)へのポインタを探す 部分

の両方を sparse_hash/dense_hash にしてみました。
例えば, p(cake|mary eats a)の確率を予測したい場合, 木の根から a→eats→mary の順にノードをたどり, たどり着いた 'mary eats a' のノードで cake が何回出てきているか&そのテーブルの数は何個か, を知る必要がありますが, どの検索もスパースなので, 何らかの形で効率的なデータ構造が必要になります。

というのが前置きで, 以下がその結果。

Algorithm	Time	Memory
dense_hash_map	33.48min	209M
sparse_hash_map	55.28min	111M
splay tree	57.13min	76M

上はかなり小さいデータ(京大コーパスから5000文)のもので, 毎日新聞2000年度全文 (約150万文)を突っ込んだメモリ使用量は, dense_hash_map で7.5G, splay tree で 4.0Gでした。ちなみに, ナイーブに ext/hash_map を使うと20G超えのようです。
ということで,

• メモリ効率ではスプレー木はやはり優秀 *2
• sparse_hash_map の速度はスプレー木と同程度
• dense_hash_map はスプレー木に比べてメモリを2倍弱使うが, 速度が2倍弱になる

というのがひとまずの結論のようです。
スプレー木は二分木なので O(logn) ですが, 意外と速かったなというか..。
今回は densehash を使うことにしましたが, ちなみにスプレー木は自己組織化二分木 なので, 計算が進むほど, 各ノードの持つ二分木の構造が最適化されて, どんどん計算 が速くなるという素敵仕様があったりします。

---