Slice Sampling for Pruning - murawaki の雑記

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$ は隠れ状態)。[tex:p(u_t|s_{t-1},s_t,\pi)=\frac{\mathrm{I}(0*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$ を考えている。とすると $u$ は $z$ 全体に依存していることになる。まじめに 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 と同じく、 $z$ が cell を埋め切らないという問題がある。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}$ までとか。これはパラメータの組み合わせなので、生き残って欲しい候補であっても極端に小さな値になる。そうなると、決め打ちパラメータのベータ分布で足切りなんてできない。意外と使い勝手が悪い。

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

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