Alexandre Bouchard-Côté et al. Randomized Pruning: Efficiently Calculating Expectations in Large Dynamic Programs. NIPS 2009. (pdf)
時間があいてしまったが、前回と同じ話題。sampling 時に pruning を行う手法。前回はいずれも slice sampling に基づいていたが、今回はかなり違う発想。そこが面白い。
あらかじめ断っておくと、使い勝手は悪い。sampling 対象とは別個に、簡単に計算できる別のモデルを用意しておく必要がある。論文の実験では、bitext parsing をするのに、Berkeley Aligner を使っている。機械翻訳の人は、簡単なモデルからはじめて徐々に複雑にしていくのに慣れているかもしれない。でも他の分野はそうでもない。
第一著者は、以前紹介した言語系統樹を与えて祖語の語形を推定する話の人。ちゃんと統計がわかっている人。MCMC sampling の使い方も王道的。表題にあるように、期待値計算の近似に用いる。私を含む他の言語処理関係者が、sampling を randomized search としてしか使っていないのとは大違い。
trick は大きく2つ。ひとつは pruning mask を分解していること。もう一つは MCMC にメタな MCMC を設けていること。論文はこの順番に説明しているが、ここでは後者を先に見る。
今回は blocked Gibbs sampling になっていて提案が常に受理されるが、Metropolis-Hasting の提案分布を考えた方がわかりやすい。MH の提案分布はパラメータを持っている。例えば、ガウス分布で random walk するなら分散をパラメータとして持つ。普通はこのパラメータは固定しておいて MCMC を走らせる。でも、パラメータの値の集合を用意しておいて、適当に交代させても MCMC としては問題ない。例えば、ガウス分布なら、大きな分散と小さな分散を用意しておけば、ドツボにはまって動けなくなるのを防げそう。これをさらに一般化すると、パラメータ自体が MCMC で遷移しても大丈夫ということになる。
注意が必要なのは、このメタな MCMC は、sampling 対象の MCMC (e.g., bitext parsing) の状態とは別個に構成していること。言い換えると、元の MCMC の状態を見ながら遷移の仕方を変えているわけではない。これが理由で、本来の sampling 対象とは別個に、簡単に計算できる別のモデルが必要となる。このモデルの出力を適当に加工して遷移パラメータを決める。
MCMC の状態を見ながら遷移の仕方を変える手法を adaptive MCMC というらしい。adaptive MCMC の論文を眺めると、たかが Gaussian の提案分布を adaptive にするだけでも、ちょっと間違えれば不正確になってしまう。正しく構成するために大変な議論が必要になっている。adaptive にできないと決まったわけではないが、無理ゲー感が漂っている。
話を元に戻す。やりたいことは、候補数の爆発を抑えるための pruning。確率の高そうな候補群だけを考えたい。しかし、同時に sampling として正しく構成したい。例えば、常に pruning されるセルがあるとまずい。確率が低いセルにも低い確率で訪れる必要がある。
論文では CKY を例に説明している。pruning によりセル単位で枝刈りしていくことになる。簡単な別モデルを使うと、確率の高そうなセルの集合が得られる。こうして得られる新しい集合を直接 pruning に使う、つまり、残りのセルを pruning してしまうと、正しい sampling にならない。
ではどうするかというと、もう一つの trick の出番。mask (セルが keep か prune かを決める) を selection と assignment という2つに分解して構成している。selection はメタな MCMC で得られるもの。各セルに selected か excluded かいずれかの値を付与する。次の状態への遷移をどうするかというと、現在 selected なセルの一部を取り除いて、代わりに別モデルから得られるセル集合の一部を加える。
assignment は現在採用されているセル集合。sampling 対象の MCMC の状態では、いくつかのセルが採用されて構文木が作られている。
selection と assignment から決定的に mask が作られる。mask は selected なセルに関して発動する。あるセルが selected でかつ assigned (論文の用語で positive) なら、それと競合するセルを prune する。セルが selected でかつ unassigned (negative) なら、そのセルを prune する。残りは keep。
何が起きるかというと、いま採用されているセルは必ず keep される。残りが pruning の候補となるわけだが、selection の状態の変化によって、pruning の対象がちょっとずつ変わっていく。そのため、確率の低いセルもその確率に応じて採用できる。
あとは細かい話。結局 slice sampling と同じく、補助変数を導入していることになる。決定的な処理をいろいろやっているけど、それを確率の形で表しているから理解しにくい。
最初に言ったように使い勝手は悪い。前回見たように、slice sampling による pruning も微妙な点がある。何が大変かというと、対象の分布からの正しい sample を得る部分。でも、そもそも sampling を randomized search としてしか使っていないなら、本当にそこを頑張る必要があるのか怪しい。不正確なのを承知のうえで beam search しても良いんじゃないかと思えてくる。
