Percy Liang の "Type-Based MCMC" (NAACL 2010) [PDF] を何回かに分けて読んでいて, ようやくほぼ理解できた。
これはすごい論文です。非常に基礎的な話で, 統計の専門ジャーナルにも余裕で 通る話だと思いましたが, NAACLという。Michael Jordanが第2(第3でなく)著者なので, 恐らく Jordan のテイストが結構入っているのだと思います。

よくこれだけの内容を8ページに書いたなぁ..というのが最初の感想で, ちなみに, かなりベイズ的な議論に慣れていないと, 普通の自然言語処理の人だとそもそも何を 言っているのかさっぱりわからないかも知れないと思いました。 少し前に情処論文誌でトンデモ査読をされて唖然としたので, 余計にそう思うのかもしれませんが..。 *1
内部のベイズ勉強会では別の話 ("Painless Unsupervised Learning with Features") を紹介したので, ここで自分用メモを含めてまとめ。

この論文は一言で言うと,「同じ環境の変数をまとめてサンプリングする」MCMCを提案しています。
いわゆる Direct Gibbs (Scott 2000)では, 例えば教師なし品詞推定ならば, 各単語の持つ隠れ状態(〜品詞)を一単語ずつサンプリングして変えていきますが, これは非常に収束が遅い場合があります。
他には, PCFGでたまたま全ての文が S->NP (文->名詞句) と解析されてしまった場合, EMだと絶対に S->NP VP (文→名詞句 動詞句) となることはありませんが, MCMCでは 確率的にどれかの文の解析が NP VP になり, それに応じてまた別の文が NP VP に なり..が繰り返されて, 解釈が引っくり返ることがありえます(これがMCMCのいい所)。
ただし, これには非常に長い計算時間が必要で, データが大きくなればなるほど, 全体の解釈が大きく変わるような変化は起きにくくなります。

しかしよく見ると, データの中では同じような「部分」が沢山あり, それらをまとめて 動かせば, 効率的にサンプリングできる可能性があります。 *2
例としてHMMで隠れ状態が0と1の二状態だった場合,

0→[1]→1,  0→[1]→1,  0→[1]→1, ...
   ↓          ↓          ↓
   flower      flower      flower

のように, []で囲まれたサンプルすべき隠れ状態について, データの中で同じような 部分が沢山ある可能性があります。この場合, 状態[1]が1であるか0に変わるかの 確率はどの部分でも同じなので,

• まず, n個の同じ部分のうち, 何個が変わるか(mとする)をサンプルする
• n個のうち, ちょうどm個をランダムに変える

という操作をする, というのがキモ。これは一種の Blocked Gibbs で, ただしBlockが 1文のように予め決まっているのではなく, 変数を変える環境が同じもの(これをTypeと 呼んでいる)を集めて Block とする, ということ。

具体的には, n個のうちm個が変わる確率は nCm・g(m) になります。 g(m)はm個が変わった一つの潜在変数の組み合わせの確率(当然これがnCm個ある)で, 論文の(9)式ですが, これは当然 m によって異なる値で, 離散分布の事前分布に ディリクレ過程(またはディリクレ分布)を仮定すると(3)式と(4)式から求まります。
ここで多分, (3)式を一瞬見ると(?)ですが, よく見ると, これは実は, 単純なPolya分布の式であることがわかります。

Polya分布(詳しくは 2005/10/28の日記 参照)では, カウントの整数nについて Γ(α+n)/Γ(α) という形がよく出てきますが, ガンマ関数の標準的な性質 Γ(x+1)=xΓ(x) を使うと, これは

Γ(α+n)/Γ(α)
=(α+n-1)Γ(α+n-1)/Γ(α)=..=(α+n-1)(α+n-2)..αΓ(α)/Γ(α)
=(α+n-1)(α+n-2)..α= α⁽ⁿ⁾

です。
すると, 論文の(3)式の

p(z) = Π_r(Π_o(α_roμ_ro)^(n_ro)) /α_r^(n_r)

は実は, 有限次元の場合だと

p(z) = Π_rΓ(α_r)/Γ(α_r+n_r)Π_oΓ(α_roμ_ro+n_ro)/Γ(α_roμ_ro)

という, よく見慣れたPolya分布です。(4)(9)式も形式としては同じ。 自分で導出はしていないですが, (4)(9)はここから割と自然に求まりそうです。
論文ではさらに, どうやってType blockを決めるか, そのためのデータ構造はどうす べきか, 頻出する品詞や単語(theや冠詞など)を全部考慮すると効率が悪いので どう近似するか, ..などが詰め込まれ, さらに実験ではHMM,USM(ユニグラムの超簡単な 単語分割問題), PTSGの学習などに適用して..まで書かれています。内容濃すぎる。

ちなみに, この方法は基本的に隠れ変数が二値の場合に特に役立つ問題で (なぜなら,「隠れ変数をいくつflipするか」をサンプリングするため), 分割問題への 適用は自然ですが, HMMで隠れ状態が2より大きい場合は

• 現在サンプル対象の状態(例えば4とする)を, 次に何に変えるかを 1..K からUniform に選び,
• フリップすると決めたランダムなm個をその状態に変える

という操作をすると, K×Kの遷移行列をスライスサンプリング的に均一になめる ことになるためok, のようです。
ただ, 著者は書いていないですが, これはKが比較的小さい時には有効ですが, 隠れ状態数が大きい時にはかなり非効率な可能性があるので, もう少し効率的なMCMCが この場合に拡張で作れるのかも, という気がします。

---

三月の年度末に, 予算が少し余ったということで, Linux版の Mathematicaを代理店の 日本電子計算 から購入して創知グループの計算機にインストールしました。 MathematicaにはNotebookインターフェースという標準のインターフェースが あって, 非常によくできているものの,

• 編集した内容を再利用できない電卓のようなもの
• 自動でインデントしてくれない(重要)
• Emacsバインドが使えない

など, 実際にプログラムを書くには使いにくい点が多い。(ので, 家のMac上の Mathematicaもこの使いにくさのため, あまり使っていなかった。)
Emacsから使えばこの問題は解消しますが, math.el やmma.elは単にmathコマンドを シェルと同じように動かすだけか, *.m ファイルを編集するためのモードで, cmuscheme.el のようにプログラムを書きながら式を順次評価する, というような ことができない。

ないなら作れ, というX68ユーザの精神で(というほどではないですが), Nakaiさんが2003年に改良された math.el にさらに追加して, "inferior Mathematica"モードを提供する math++.el というelispを簡単に書いてみた。
上の画像のように, コードを書きながら C-cC-e (or C-cC-s)で今の式をMathematicaに 送り, C-cC-r でリージョンを丸ごと送れます。 MathematicaはLispと違って式の境界が曖昧なので, 空行で区切られた部分が 一つの式だとしています。

これは scheme をemacsで使うのとほとんど同じで(というか, Mathematicaは本質的に Lispですが), かなりプログラムが書きやすくなりました。
公開しないとどうも直す気がしないので, 簡単に 公開して おきます。

-