準モンテカルロ法

モンテカルロ法(Monte Carlo method, MC)では擬似乱数を用いるが、準モンテカルロ法(qusi-Monte Carlo method, QMC)では、数論の分野で用いられている、低食い違い量列(low-discrepancy sequence, LDS)と呼ばれるあらかじめ並びが決まっている数列を用いる。

準モンテカルロという名前だと、モンテカルロっぽい手法だと想像しがちだが、本質的にはモンテカルロ法は確率論を基礎とし、準モンテカルロ法は数論を基礎としたものであって両者はまったく異なる理論である(と思う)。そのため誤差の測定などは、モンテカルロ法と準モンテカルロ法で異なる。

レンダリングを含め、多くのサンプリング問題では、一様であるが、かつ不規則性がある数列が望まれる。

擬似乱数は、不規則性があるが、効率的に一様に分布しないことが知られている(つまり分布に無駄が多い)。

それに対して、低食い違い量列は、不規則性を持ちつつも一様に分布する。そのため低食い違い量列は超一様分布列とも呼ばれる。これは無駄なく分布が生じることを意味している。

準モンテカルロ法は、低次元の問題においてモンテカルロ法に比べて収束が早いことが知られている。つまり少ないサンプル数で品質の高い結果を得ることが可能になっている。

準モンテカルロ法は、今までは高次元の問題においてはモンテカルロ法よりも悪くなることが知られてきた。しかし、90 年代における準モンテカルロ法の発展により、高次元の問題においてもモンテカルロ法よりも優れた結果が得られることが報告されている。

準モンテカルロ法は金融工学、レンダリングへの応用が主である。

金融の分野での例を挙げよう。本質的に金融の問題は千数次元と高次元である。

準モンテカルロ法を利用することで、今までモンテカルロ法では 2 日半かかっていた計算を、わずか 1 分で処理できたことが報告されている^[1]。

レンダリングの場合、レンダリングの問題も高次元である。しかし、次元の問題よりも、レンダリングで扱う関数群がそもそも非常に病的な関数ばかりであるという事実のほうが問題である。病的な関数が相手であっては、そもそもモンテカルロ法であろうと準モンテカルロ法であろうと、問題の解決は困難である。

またレンダリングでは、レイトレーシングが主に用いられるが、レイトレーシングのコストがはるかにサンプリングの数列の生成コストよりもかかるので、準モンテカルロ法で金融のように数千倍高速に処理するのは困難であると見られる。

それでも、レンダリングで用いられる関数をよく解析して注意深く準モンテカルロ法を適用したレンダラでは、モンテカルロ法に比べて、少ないレンダリング時間でより高品質な結果画像を得ることが可能なことがいくつもの準モンテカルロ法によるレンダリングの論文で報告されている。

準モンテカルロ法のレンダリングへの応用は、 Alexander Keller 博士

• http://graphics.uni-ulm.de/

が多大な貢献をしている。

また、最近では、準モンテカルロ法にモンテカルロ法のランダム性を取り入れた乱列化準モンテカルロ法(Randomized quasi-Monte Carlo method, RQMC)というのも提案されている。

この分野は数論を基礎としているために非常が奥深く、また毎年のように新しい手法がと発展がある。非常に興味深い分野である。

• [1]NINOMYA SYOITI. AND TEZUKA SHU. Towards real-time procing of complex financial derivatives. Applied Mathematical Finance 3 (1996). pp. 1-20. 1996

[カテゴリ:レンダリングアルゴリズム]