Hatena::Grouprekken

murawaki の雑記

2013-11-04

Slice Sampling for Pruning

Markov chain Monte Carlo による sampling 時に pruning したい。そのために slice sampling を使う手法。何年遅れて人のあと追いかけてるんだって話だが、細かい話題がいろいろあるので書き出してみる。

slice sampling

slice sampling 自体は (Neal, 2003) で提案された手法。当初の目的は普通に sampling すること。アイデアは単純だけど、連続分布に対して実装しようとすると途端に面倒になる。doubling とか shrinking とか。情弱には厳しい。

実物をはじめて見たのは Mark Johnson の adaptor grammar の実装。Pitman-Yor 過程の2個のパラメータを slice sampling で求めていた。ちなみに、今だったらこうはしない。Yee Whye Teh の方式で、パラメータに事前分布を置いて事後分布を sampling する方が簡単。式の導出は、というかどうしてこんな方法を思いつくのか意味不明だけど。

iHMM

slice sampling を pruning に応用したのは (Van Gael+, 2008) が最初だと思う。Teh と Ghahramani が共著者に入っていて恐ろしい。この論文は提案手法を beam sampling と呼んでいる。でも、なぜか以後の論文は追従していない。

iHMM は hidden Markov model で、Dirichlet 過程を使って隠れ状態のタイプを無限に拡張している。提案手法以前は、隠れ状態の変数を1つずつ Gibbs sampling していた。1 個だけを対象とするなら、既存のタイプか、未観測のタイプかで場合分けすれば良い。しかしこの手法は mixing が遅い。

効率を上げるために文単位で block sampling したい。しかし、状態のタイプが無限にあるので、動的計画法が使えない。そこで slice sampling が登場する。このあたりから中身を見ていく。

そもそも slice sampling は補助変数を追加するという trick を使っている。sampling したい元の分布を p(z) とすると、補助変数 u を追加して、同時確率 p(z,u) を考える。補助変数 u は好きに設計すれば良い。とにかく p(z,u) は、これはこれで立派な分布だから、 Gibbs sampling が行える。p(z)=\sum_u p(z,u) だから、p(z,u) からの集めた sample から単に u を落とせば、p(z) からの sample になる。

Gibbs sampling では、p(u|z)p(z|u) を交互に sampling する。通常通り。問題は p(u|z)設計だが、注目している値が小さい、つまり pruning したいときに、0 をとるようにする。そうすると p(z|u)=0 となって候補から外れる。

iHMM の場合は、遷移確率 \pi_{s_{t-1},s_t} を pruning の対象とする (s_tは隠れ状態)。p(u_t|s_{t-1},s_t,\pi)=\frac{\mathrm{I}(0<u_t<\pi_{s_{{t-1},s_t}})}{\pi_{s_{t-1},s_t}} とする。この分布は u_t積分するとちゃんと 1 になる。手続き的には u_t \sim \mathrm{Uniform}(0,\pi_{s_{t-1},s_t}) に従って sampling する。

p(z|u) を sampling するとき、隠れ状態 s_t に着目すると、u_t は固定。\pi_{s_{t-1},s_t} \leq u_t となる \pi_{s_{t-1},s_t} については、p(z|u)=0 となるから考えなくて良い。pruning される。u_t < \pi_{s_{t-1},s_t} を満たす \pi_{s_{t-1},s_t} のみを考える。そうした候補は有限なので forward-backward が使える。

言い忘れていたし、だから上記の式は不正確なのだが、\pi_{s_{t-1},s_t}積分消去していない。従来の Gibbs sampling の場合は積分消去していたけど。slice sampling を使うときには、\pi も sampling する。Teh の黒魔術を使って。だから p(u|z,\pi), p(u|z,\pi) と書いた方が正確。

p(z|u) の導出が論文の式 (4)。\pi_{s_{t-1},s_t} は打ち消し合って最後の式から消える。何だか不思議な感じ。

p(u|z,\pi)p(z|u,\pi)\pi は共通の値。*1だから、p(z|u,\pi) からの sampling 時、各状態遷移について、少なくとも 1 個の \pi_{s_{t-1},s_t} は必ず pruning から生き残る。sampling 前の z の値をそのまま使えば良い。だからすべての候補が pruning されて HMM の path が通らないということはない。どうしてパラメータ積分消去をやめてしまったのかと最初は思ったけど、恐ろしい人たちが共著者に入っていることだし、よくよく考えてのことだろう。

infinite mixture model に slice sampling を適用した例も iHMM と似た感じ。*2stick-breaking representation で明示的に Dirichlet 過程からの sample を考えて、棒の高さで slice する。

PCFG

(武井+, 2009) という論文を最近みつけた。国内だけど、IBIS という恐ろしい集まりの発表。

PCFG (ただし Chomsky 標準形に限る) に slice sampling を適用している。何が困るかというと、HMM の場合と違って、補助変数の設定が難しい。p(u|z) から sampling しようと思っても、z は CKY の chart の一部の cell しか埋めない。残り cell の扱いに困る。提案手法は split position というのを考えて、tricky に数合わせを行っている。何しろ tricky なので、例えば semi-Markov な単語分割には適用できない。

引っかかるのは、iHMM の場合と違って、パラメータ積分消去をしたまま slice sampling を行っていること。PCFG なので導出確率 \theta_{A \rightarrow B C} があるが、共役性を利用して積分消去してしまう。z 中のカウントと hyperparameter で擬似的に \theta^\prime を考えている。とすると uz 全体に依存していることになる。まじめに graphical model を考えると恐ろしいことになる。u設計は何でもありなので、これ自体は問題ないだろう。

問題なのは、擬似的なパラメータ \theta^\prime の扱い。普通に Gibbs sampling すると、以下の手順に従う。

  • p(u|Z) から u を sampling
  • z のカウントを decrement
  • p(z|u,Z^{-}) から sampling
  • z のカウントを increment

Step 2でカウントを decrement するから、\theta^\prime の値が Step 1 で u を sampling したときから変わってしまう。運が悪いとすべての候補が pruning される気がする。

SCFG

(Blunsom+, NAACL2010) は SCFG に slice sampling を適用している。SCFG は機械翻訳に使う PCFG の拡張で、2 言語を同時に導出する。機械翻訳の常だが組み合わせ爆発地獄。普通に動的計画法で parsing しようとしても、遅いどころか、現実的な時間内に終わらない。そこで slice sampling で pruning しようというもの。

short paper なので全然 self-contained ではない。あたかも \theta という導出確率を持っているような書きっぷり。でも、(Cohn+, ACL2009) で提案した collapsed Gibbs sampler のモデルから変更したとは書いていない。積分消去して得られる擬似的なパラメータを使っているのだろう。そうすると、PCFG の場合と同じく候補全滅のおそれがありそう。

SCFG は PCFG の拡張なので、PCFG と同じく、zcell を埋め切らないという問題がある。Blunsom らは、z が未使用の cell も含めて、すべての cell に補助変数を設定している。z が未使用の場合は u_s \sim \mathrm{Beta}(a,b) と、ベータ分布を使っている。\theta の確率をまったく無視して u_s を決めているから、全滅する cell が続出する。これは Blunsom らの意図通り。そもそもすべての cell を見て回るだけでも大変だから、cell をまるごと pruning していくらしい。

p(z|u)、あるいはこの論文記法に従うと p(d|u) は、式 (2-4) で求められている。CFG で木の確率を求めるというのに、導出確率 \theta が打ち消されて最後の式には出てこない。しかしこの式変形は間違っているのではないかと思う。p(u|d) から sampling するときに使った、前の状態の d と、今まさに sampling しようとしている d を混同している。本当は \theta は打ち消されないはず。識者の意見を乞う。

雑感

iHMM, PCFG, SCFG と見てきたが、いずれも pruning 対象は 1 個のパラメータ。iHMM なら遷移確率、PCFG/SCFG なら導出確率。1 個のパラメータだから、生き残って欲しい候補は (0, 1) のなかで適当な範囲に収まっている。だから適当に u_s \sim \mathrm{Beta}(a,b) で足切りするといった乱暴なことが可能となる。

普通の beam search だと、ある時点での one-best を基準に pruning を行う。上位 K 個とか、one-best の10^{-10} までとか。これはパラメータの組み合わせなので、生き残って欲しい候補であっても極端に小さな値になる。そうなると、決め打ちパラメータベータ分布で足切りなんてできない。意外と使い勝手が悪い。

*1p(u|z,\pi) からの sampling と p(z|u,\pi) からの sampling の間に、p(\pi|z,u)=p(\pi|z) からの sampling をするといった妙なことを行わなければ。

*2:実はもともとこちらのほうが (Van Gael+, 2008) より早い。