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が この場合に拡張で作れるのかも, という気がします。

---

IBISML の第1回研究会が無事に終了。 参加者は何と200人を超えたとのことで, 運営側も結構驚いていました。
初回のためとにかく発表件数が多く, 招待講演も一般講演も(一般講演は15分とか) 時間が足りない感じでしたが, 最初なのである程度は仕方ない部分もあったかも 知れません。 個人的には, 東京だけでなくかなり遠い所からも聞きに来られた方が色々 あったようで, 若い人も多く, そこの所が素晴らしいなというのが感想でした。
講演スライドが 第1回研究会のページ で続々公開されていますので (ibisml@twitter), ご興味のある方はぜひどうぞ。

牧野君のノンパラメトリックベイズの講演はすごい力作で, しかもわかりやすく, 講演をお願いして良かったなと思いました。 あの内容を50分で話すというのがそもそもかなり無茶なので, スライドを見直すと 結構わかるのではないかという気がします。

ベイズ学習の説明の所で, 一般にベイズ学習は事前分布を仮定して.. と言うと, 結果がその事前分布に依存してしまうじゃないか!という批判が 当然ありますが, 実際には, これまでの経験では事前分布はできる限り「無情報」にすることが多いので, そういう批判はかなりかわせるような気がします。例えば, DPはデータがPower Lawに 従うという仮説の事前分布ですが, 実際にはハイパーパラメータのαは学習できるので, Power law が現れないようにもなるはずですが, データがそれを支持している..という 理屈になっているかと思います。

終わった後, 帰りに愛する銀杏(安田講堂前)でお茶をして帰りました。 ケーキとコーヒーで310円とか, ありえない...。

佐藤君のトピックモデルの話(「階層Pitman-Yorトピックモデル」, KDD 2010)について 少し気付いたことがあったので, まとめ。15分しかないあの話で普通全部は わからないだろうと思うので..。

この話は最初, LDAのディリクレ分布をPitman-Yor過程(ポアソン=ディリクレ分布) にしただけかと思ったのですが, そうではないことに聞いていて気付きました。
佐藤君が Twitterで喋っている ように, この話はLDAにDM的なキャッシュ(Pitman-Yor adaptor)を入れたもの なのだと思います。 これまで, LDAには単語のバースト性 (同じ単語が複数回現れやすいというキャッシュモデル) が表現できないという問題があり, その点で Dirichlet Mixtures (DM)の方が パープレキシティの低いモデルとなっていました。が, この話でLDAにもキャッシュが 入ったので, DMはもしかすると不要になったかも知れません。 *1

佐藤君の論文は全部CRPで書かれているので, 何をやっているかわかりにくいのですが, 少し考えるとわかったので, 以下に整理。

一般に, LDAの生成モデルでは文書に含まれる単語が

• 文書のトピック分布 θ ~ Dir(α) をサンプル
• For n = 1 .. N,
  • 潜在トピック k_n ~ Mult(θ) をサンプル
  • 単語 w_n ~ p(w|k_n) をサンプル

という過程で生成されるとしますが, これは実は,

1. θ ~ Dir(α) をサンプル
2. 単語分布 p = Σ_k θ_k p(w|k) を混合分布として作成
3. w_1 .. w_N ~ p を i.i.d. にサンプル

というのと同じです。上の 1,2 をまとめて, 以下 p ~ LDA(α) と書くことにします。
一方, DM等の単純なキャッシュモデル(Polya分布)では,

• p ~ Dir(α) をサンプル (このαは単語次元.)
• w_1 .. w_N ~ p, i.i.d.

で, 中間の p を積分消去するとΓ関数の形が出てきます。

上の佐藤君の話は, この Polya 分布でαに当たる単語の事前確率が一定ではなく, 文書のトピックを考慮して LDA(α) になっている, と理解できます。 それに加えて, ディリクレ分布にパラメータが1つ増えてポアソン=ディリクレ分布 (Pitman-Yor過程)になっている, ということ。つまり,

1. p ~ LDA(α) をサンプル
2. q ~ PY(η,d,p) をサンプル (ηは集中率, dはディスカウントを表すパラメータ)
3. w_1 .. w_N ~ q, i.i.d.

で, 中間のqを積分消去。 言葉で言うと, p ~ LDA(α) は普通のLDAの単語分布ですが, 実際にはpを中心として 少しずれた, 特定の単語が何回も出やすい q があり, そこから最終的に単語が生成 されていると考えるモデルだ, ということ(この辺はDMと同じ)。

というわけで, この話でLDAの欠点も克服されたので, 一つ一つは特別なことをして いる訳ではないと思いますが, 実際上は結構役立つモデルになっているのではないか, という気がします。

---