[機械学習] スライスサンプリング

持橋さんのlwlmに関する記事を読んで、スライスサンプリング[1,2]というのが有用そうということで調べてみたのでメモ。

スライスサンプリング概要

今確率分布f(x)が
$f(x) \propto l(x) \pi(x)$
の形で与えられており、このf(x)からxをサンプリングすることを考える。ここでl(x)は非負の関数、\pi(x)は確率密度関数とする。

サンプリングを以下の手順で行なう

初期値x_0を適当に決定する
u_t = Uniform(0 , l(x_t))で一様分布からサンプリング
X_t = { x | u_t < l(x)}とする
x_{t+1}をX_tに含まれるxから\pi(x)に従ってサンプリングする
2へ戻る

ここでu_tの値は捨てて、{x_t}だけ取り出すとf(x)に従うxをサンプリングできる。

何が嬉しいのか

スライスサンプリングの話は以前から聞いたことがあったのですが、連続の場合だと4の部分が簡単にできそうではなくあんまりありがたみが分からなかったのですが、離散の場合ですと結構使える方法となっている。

例えばlwlmの実装では隠れ変数h_iを
$p(h_i |o_i, H) \propto p(h_i|H) p(h_{i+1}|h_i,H) ... p(h_{i+n}|h_i,H) p(o_i | h_i)$
に従ってサンプリングしている。ここで便宜上h_i以外の隠れ変数の集合をHと書いた。lwlmにおいてはh_iの取りうる値が単語数と同じだけあり、上の値を計算してそれに従ってサンプリングするのは非常に効率が良くない。

そこで
$l(h_i) = p(h_i|H) , \pi(h_i)=p(h_{i+1}|h_i,H) ... p(h_{i+n}|h_i,H) p(o_i | h_i)$
とすると上のスライスサンプリングが使えて、u = Uniform(0 , l(h_i))以上の潜在変数のみに関して\pi(h_i)を計算して、その確率に従いサンプリングすると候補数を少なくすることができる。u以上の値を列挙するには文脈上での潜在変数の頻度順*1にデータをソートしておくことにより効率的に行なうことができる。

離散分布においてこの手法は他にも文献[3]などで用いられている。

参考文献

[1] Damien, P. and Wakefield, J. and Walker, S., Gibbs sampling for Bayesian non-conjugate and hierarchical models by using auxiliary variables, Journal of the Royal Statistical Society. Series B, Statistical Methodology, pp. 331--344, 1999
[2] Neal, R.M., Slice sampling, Annals of Statistics, vol 31, pp. 705--741, 2003
[3] Van Gael, J. and Saatci, Y. and Teh, Y.W. and Ghahramani, Z., Beam sampling for the infinite hidden Markov model, In Proceedings of the 25th international conference on Machine learning, pp. 1088--1095, 2008

*1:実際にはもう少し工夫をしているようです