A quasi-Monte Carlo Metropolis algorithm

by syoyo

乱列化準モンテカルロ(RQMC)で有名な Art B. Owen
氏による、
メトロポリス(・ヘイスティング)サンプリングへの RQMC
の応用についての論文です。

Owen, A.B. and Tribble, S.D “A
quasi-Monte Carlo Metropolis
algorithm”

http://www.pnas.org/cgi/reprint/102/25/8844


http://www-stat.stanford.edu/~owen/reports/

論文は結構小難しく書かれていますが(というか予備知識がないと全然わかんないべ?)、

言わんとすることは、 RQMC をメトロポリス法のような MCMC
系(マルコフ連鎖モンテカルロ法)
に適用しても問題ないよね、ということの数学的裏づけが述べられています。

(いままでは QMC や RQMC を MCMC
に使ってちゃんと収束すると言えるかが数学的に疑わしかった。
と思う)

RQMC を用いることにより、通常の MC(モンテカルロ法)に比べて、

10 – 100 倍ほど収束が早くなっています。
(論文のテスト対象は単純なガウス分布関数などなので、
実際のレンダリング処理に適用した場合は
そこまで収束の効率はよくならないかと思います)

論文がやっていることは単純で、
メトロポリス法で通常擬似乱数を使う部分を
RQMC のサンプルで置き換えるだけです。
本論文では、サンプルの生成には Entacher et al の
LCG(Linear Congruential Generators)
[1] を使っています。
各サンプルには、Strictly Deterministic
Sampling [2] にもあるように、
Cranley-Patterson
回転を使ってランダムネスを付加しています。

つまり、 LCG で得られた i 番目のサンプルが x_i としたとき、
 

x’_i = frac(x_i + u)

として実際に用いるサンプル点 x’_i を生成します。
u は [0, 1) の一様分布乱数(Mersenne
Twister や WELL などの
擬似乱数
 でよい)、
frac(x) は x の小数部を取り出す関数(つまり結果は [0,
1) の範囲になる)です。

サンプルは二つのペアにまとめ、最初のほうを関数の評価に使い、
二つ目のほうを
accept/reject のために使っています。

ちなみに、双方向パストレに RQMC を使うのは Alexander
Keller 博士がもうやっていますね。

http://lucille.sourceforge.net/blog/archives/000142.html

RQMC は vray も導入しているようですし(Owen’s
scrambling らしい。 [3] が参考文献)、


http://www.oakcorp.net/chaos/sigg15.shtml

maxwell
もレンダリングのプロセスを見ているとランダムさがありつつも規則的なパターンが出ていることから
QMC(RQMC ではなさそう?) を使っているようです。

レンダラも、もう MC ではなく QMC or
RQMC を使うように着実に遷移しつつあるようです。

References

[1] K. Entacher, P. Hellekalek, and
P. L’Ecuyer, “Quasi-Monte Carlo
Node Sets from Linear Congruential
Generators”, Monte Carlo and
Quasi-Monte Carlo methods 1998, H.
Niederreiter and J. Spanier Eds.,
Springer, Berlin, 2000,
188–198.

http://www.iro.umontreal.ca/~lecuyer/papers.html

[2] Strictly Deterministic Sampling
Methods in Computer Graphics
(mental images technical report,
2001) in “Monte Carlo Ray Tracing”,
SIGGRAPH’2003 Course #44, San
Diego, July 2003.
http://graphics.uni-ulm.de/

[3] Owen, A.B. “Quasi-Monte Carlo
Sampling” PDF A Chapter on QMC for
a SIGGRAPH 2003 course

http://www-stat.stanford.edu/~owen/reports/

Advertisements