2012/08/21

超一様分布列をBoost.Randomを用いて実装する

ご存知の通り、C++のライブラリには高性能な擬似乱数生成エンジンBoost.Randomが存在している。Boost.Randomは擬似乱数を生成するエンジン部分と、一様分布、ガウス分布、ベルーヌーイ分布など好みの分布を生成する出力部分の2つで構成されている。

しかし、ことモンテカルロ法においては主に収束速度を早める目的として、擬似乱数ではなく低食い違い量列(Low-Discrepancy Sequence, LDS)と呼ばれる数列が用いられる場合がある。これを用いると低次元での積分計算の際に収束速度を大きく改善することができ、具体的には従来のモンテカルロ法で(1/√N)だった収束速度が約(1/N)くらいにまで落とすことができる。

さて、このような低食い違い量列をBoost.Randomで用いるためにはエンジン部分を製作すればいいだけで、実際には以下のような形で実装すれば良い。今回は簡単なHalton列を用いて実装を行った:

具体的には、対象のファンクタがUniform Random Number Generatorのコンセプトを満たすためには以下の記述が必要となる:
  • X::result_typeoperator()が返す型を指定
  • operator()にエンジン部分を記述
  • min(), max()にエンジンが生成する分布の最小値、最大値を指定
さらに、対象のファンクタが上述の内容に加えPseudo-Random Number Generatorのコンセプトを満たすためには:

  • X()にデフォルトの状態で生成されるようなコンストラクタを指定
  • X(...)にユーザ指定の状態で生成されるコンストラクタを指定
  • seed(...)にエンジンの状態を変更するためのメンバ関数を指定
するだけで良い。後はBoost側が良きに計らってくれる。非常に便利だと思う。

余談
C++0xには同等のstd::randomが付属しているため、これを利用すればいいのではという声もあるとは思うが、std::uniform_real_distribution<>にこのLDSを食わせたところ、どうみてもLDSではない値が出力される結果となった。恐らくresult_typeがdoubleという一般の擬似乱数ではない型を指定しているために起こる現象だと思うが、ソースを見ていないので一先ずは従来のBoost.Randomの手法を用いることにする。

3 件のコメント:

匿名 さんのコメント...

昔のエントリーで大変恐縮なのですが、2008/06/07付の『ランダムフォレスト(Random Forest)法を用いて株価予測を行ってみた。-03 』にて、「でも結局『なんだかんだやっても予測はできない』で終わらせるのは正直微妙なので、ちょっとあるデータを加工して再び解析を行ってみたら、今度はけっこうおもしろい結果が出るようになりました。でももうこれ以上書いてしまうと長くなってくるので、続きは次回」とおっしゃておりましたが、その後のエントリーをツブサに見ても、当該のエントリーが見つかりませんでした。もの凄く気になるのでいつのエントリーに続きが書いてあるか教えていただけますでしょうか?

rezoo さんのコメント...

コメントが遅くなってしまい申し訳ありません。
該当の記事ですが、もう少し温めてからきちんとした形で公開しようとしていたらいつの間にか時間が立ってしまいました。気になるような書き方をしてしまい、その点についてもお詫び申し上げます。

しかしながら、自分が言う「面白い結果」というのは非常に些細なもので、一介の理系の大学生が気づいたという程度のことは恐らく他の方々も容易に気づいているものです。
結局は既に現在の価格の中に織り込まれているものと予想されますし、
正直なところ今からきちんとした研究をしてそれなりの結果が出たとしても、
現状の自分としてのメリットはあまりないので書く気にはならないのです。すみません。

匿名 さんのコメント...

わざわざご丁寧な返信をいただきまして、どうもありがとうございます。気が付かなかったため、1か月近くもお礼が遅れてしまいました。申し訳ありません。