Syoyo Fujita's Blog

raytracing monte carlo

Month: January, 2007

謎 IBL サンプラー(mythterious IBL sampler)

myth_sampler_thumb.png
Importance-sampled 128 points from HDRI map.

nyaxt さんと実装を競い合っている? 、とある CG 教授から教えてもらった
IBL 向け謎サンプラーです。

特徴は

o 実装がとても簡単
o 高速
o サンプル点の品質もそんな悪くないんじゃね?

という感じ。

やっていることは pbrt の IALSWIS [1] や VEM [2] と同じ感じ。
というか多分やりかたがちょっと違うだけで、
本質的にはやっていることはほとんど同じでしょう。

とはいえ、実際にとりあえずえいやで実装してみると、
左上ふちに集中してサンプルが生成されたりと、
(確率密度がほとんど 0 なので、サンプルしても無駄)
細かな部分でいろいろ自分の実装がわるいのかどうか原因等を調べるのが必要だったり、
サンプル分布の品質のリファレンスとして使える EIHDRI との比較はどうかなど、
いくらか調べあげないといけないことはあります。

[1] http://www.pbrt.org/plugins.php
[2] http://www.mpi-inf.mpg.de/resources/hdr/vem/

一本一億円のソフトウェア

マネー革命3[1] より。

90 年代の金融の世界では、複雑化した金融商品やリスクの計算のために、
単純なブラックショールズ解析解などはもう時代遅れで、モンテカルロ法、
つまり乱数を用いてシミュレーション計算を行うことが必須となってきた時代でした。

そんなとき、モンテカルロ法によるシミュレーション計算を 10 – 100 倍に高速化する
乱数を生成するソフトが発表されました。値段はなんと一本一億円。
膨大に増え続ける計算量にコンピュータのパワーが追いつかなくなっていた頃であったそうなので、
乱数ソフトをかえるだけで計算時間が 1/10 – 1/100 になることは画期的でした。

とある邦銀では、この画期的な乱数ソフトを用いて金融計算やリスク計算の高速化を行うべく、
担当者がこの乱数ソフトの購入を重役会議にて稟議にかけました。

重役「で、その一億円もするソフトウェアとはいったい何なんだね?」
担当「はい、乱数、つまりでたらめな数字が収録されたソフトウェアです」
重役「そんなでたらめな数字を出すソフトウェアに一億円もだせるか

めでたく稟議は棄却されましたとさ。

というような冗談のようなやりとりがあったそうです [1]。

さて、少し考察してみたい。

このソフトがなんであるのかの詳細は [1] では結局のところ書かれていないが
(リスク計算を行うソフトウェアの見本市である「Risk ’98」で発表されたソフトらしい)、
「良い乱数で計算時間が 1/10 ~ 1/100 になる」というのは、
これは間違いなく低食い違い量列(LDS)のことであろう。

LDS の研究と、LDS の金融工学への応用で有名な手塚先生によれば、氏も関連していた、
LDS を用いて(より具体的なアルゴリズムは [2] の手法だと思う)、
MBS(Morgage Backed Securities)の計算を 100 倍高速に行う FinDer
と呼ばれるソフトウェア [7] には当時 1 本 1 億円の値段がついたとのことであるから [2]、
「マネー革命」ではこの FinDer のことをさしていたのかもしれない。

ちなみに、一本一億円の値段がついたのは、当時画期的であったからであり、
すぐに競合するソフトが多く出たため、今はもうそんな値段はつかないようです。
(ただし、LDS(LDS ならアルゴリズムは何でもいいらしい!) を用いて金融計算の
シミュレーションを行うのは FinDer の主要開発者である Traub らにより
特許が取られているので、すくなくとも彼らは今でもうはうはなことでしょう)

# 最近では、「素敵な昆虫図鑑」という本に一冊一億円の値段がついたようです。
# レンダラも一本一億円の値がつかないものかな…

マネー革命の伊藤先生へのインタビュー

マネー革命 [1, 3, 4] は本でしか読みませんでしたが、当時の放送の再放送をぜひみてみたいです。
とくに確率解析の大家であり、金融工学にも多大な貢献をした伊藤先生 [5] の在りし日の
インタビューが記録されていますので、今としては非常に貴重な映像だと思います。

マネー革命2では、その伊藤先生へのインタビューが載っています。

伊藤先生は、公務員時代は給料から自費をはたいて海外から論文を取り寄せ、
仕事が終わると論文を読みふけっていたいたそうです。
戦時中海外から論文を取り寄せるのが難しくなってくると、
当時の同盟国であるドイツから、潜水艦に論文を載せてもらってまで取り寄せたそうです。

(T_T)

なんかもう、学問に対する意気込みが違います。

「web でお手軽に論文 get だぜ!」 なんてお気軽にやっている自分が恥ずかしいです。
精進せねば。

[1] NHKスペシャル マネー革命〈第3巻〉リスクが地球を駆けめぐる
http://www.amazon.co.jp/dp/4140804173/
[2] http://lucille.sourceforge.net/blog/archives/000144.html
[3] ウォール街を動かすソフトウェア, 手塚 集
http://www.iwanami.co.jp/.BOOKS/00/X/0065840.html
[4] NHKスペシャル マネー革命〈第2巻〉金融工学の旗手たち (単行本)
http://www.amazon.co.jp/dp/4140804165
[5] マネー革命—NHKスペシャル (1) (単行本)
http://www.amazon.co.jp/dp/4140842164/

[6] http://ja.wikipedia.org/wiki/伊藤清
[7] http://www1.cs.columbia.edu/~traub/html/body_finder.html

Sort Benchmark

Sort Benchmark homepage
http://research.microsoft.com/barc/SortBenchmark/

ソート野郎が世界最高速のソートアルゴリズムを競い合う場所。
世の中すごい野郎がいるものです。

ギガバイト単位やテラバイト単位のデータに対するソートアルゴリズム(Nsort など)はもう、
CPU のキャッシュやメモリのキャッシュやらディスクのキャッシュまで考えたソートプログラムとなっており、
純粋に最速ソートアルゴリズムというよりは最速のソートシステムという感じです。

というわけで、Bytes-Split-Index Sort (BSIS) が最速のソートアルゴリズム
(アルゴリズムのオーダは O(N) らしい)のような感じがしますが、
BSIS が基本としている Self-Indexed Sort(SIS) [1] は、そのアルゴリズムはすでにあるものであり、
またテスト結果には疑問があるという意見 [2] もありますので、少し怪しい感じがします。

Flash sort [3] も O(N) のアルゴリズムらしいですが、それと比較するとどうなのかな?

[1] A New Sort Algorithm: Self-Indexed Sort
[2] Comment on Self-Indexed Sort
[3] http://lucille.atso-net.jp/blog/?p=135

ハードウェア•レイトレーサーの研究開発

tueda_wolf さんの日記より。

日本の会社でハードウェアレイトレチップを開発中らしい。

http://www.euphonic-tech.com
http://www.euphonic-tech.com/raytracer.html

へー、どれくらいのレイトレができるんだろう。

SIGGRAPH 2005 ではレイトレプロセッサ RPU の論文が発表されていましたが、
そろそろレイトレチップがコモディティとして日の目をみる日が出てきそう?…

ハードウェアレイトレでは交差判定やシェーダ云々よりも、
空間データ構造をどう持つかが重要であると思うので、
そこがどうなっているのか気になります。

テクニカルショウ ヨコハマ2007 に出展するらしいとこのことなので、
そこで詳しく聞けるかも。

効率的市場仮説 2

ユージン•ファーマの効率的市場仮説(Efficient Market Hypothesis) [1] に関係するお話を
DS lite で表現すると、、、

(ニュース) DS lite は大人気、どこも品切れです!

だが、あるおもちゃ屋で DS lite が売っていました。
そこに通りすがったのが、、、

o 「ゲーマー」だったら、、、
「とりあえず買っとけ!」
(DS lite 買えてラッキー!)

o 「統計学者」だったら、、、
「記録しろ!」
本当に DS lite か?もしかしたらおもちゃ屋は
ワンダースワンを DS lite と偽って売りつけようとしていないか?
100 個購入し、99 個がワンダースワンであったら、
”あのおもちゃ屋は偽物を売っている”と主張する
(統計を取るだけで、あとは満足する)

o 一方「経済学者」だったら、、、
「買うな!」
DS lite は大人気でどこも品切れであるので、
DS lite が売っているはずがない。
もし本当にこのおもちゃ屋が DS lite を売っているのだとしたら、
DS lite は大人気なので既に売れているはずであるからである。
きっと偽物の DS lite を売っているに違いない。
(DS lite は大人気でどこも品切れ!と心の中で思ったならッ!
そのときスデに DS lite は売り切れているんだッ!)

この「経済学者」の行動が、効率的市場仮説に基づく行動ということですね。
(「経済学者」が効率的市場仮説を信じているとする)

さて、あなたならどう行動する?

ちなみに、効率的市場仮説は発表当時は異端とされていたようですが、
現在では広く認知されており、
年金運用など安定した運用を行いたい機関では効率的市場仮説に従って、
インデックスファンドなどの平均株価指数へ投資する資金運用が盛んになっています。

[1] Fama, E. F., 1970, Efficient capital markets: A review of theory and empirical work, Journal of Finance, pp383-417.

シャノンの悪魔 vs 効率的市場仮説

天才数学者はこう賭ける—誰も語らなかった株とギャンブルの話
http://www.amazon.co.jp/dp/479176305X/

話の内容は主に、
情報理論の創始者である天才シャノン、
最適な賭けの金額を与えるケリー基準、
そのケリー基準を利用してラスベガスで勝ちまくった常勝青山ソープという人物に
関する物語である。

常勝ソープ [1] もさりとて、シャノンがいかなる天才的人物であったかを知るためだけでも、
本書は一読の価値がある。

シャノンの悪魔

本書ではひとつ面白い事例として、「シャノンの悪魔」という投資手法について述べられている。

情報理論で有名なシャノンは、株式市場にも興味を持っていた。
彼は、株価の動きはノイズであるととらえ、そこから確実に収益を得る
手法を見つけ出したという。それが「シャノンの悪魔」である。
(これは「マックスウェルの悪魔」とかけている)

シャノンの悪魔とは、以下のモデルのことである。

手持ちの資本のうち、半分を株式に、半分を現金に割り当てる。
毎日正午に値洗いを行い、常に株と現金の比率が 1:1 になるように調整する。

たとえば、1,000 ドルの資本があるとすれば、
500 ドルを株式に、500 ドルを現金とする。

もし次の日、株価が二倍になったとしよう。

資本は、1,000 ドルの株式と、500 ドルの現金となっている。
ここで、配分が半分になるように調節する。
750 ドルを株式に割当て、750 ドルを現金とする。

逆に、株価が半減したとしよう。
資本は、250 ドルの株式と、500 ドルの現金となっている。
配分が半分になるように調節する。
375 ドルを株式に割当て、375 ドルを現金とする。

これを日々くりかえしていく。

株価は毎日、二倍になるか、半額になるかが
半分の確率でおこるランダムウォークモデルとする。

以下の図は、これを 360 日間シミュレーションさせた結果である。
緑が株価で、赤がシャノンの悪魔に従って投資したリターンである。
株価は最初は 1 ドルと設定した。

最初、株価は 100 ドル近くまで上昇するものの、最終的には 0.01 ドル以下となってしまった。

対して、シャノンの魔物によるリターンはいかほどかというと、
最初 1 ドルから初まり(つまり初日は 0.5 ドルを株式に、0.5 ドルを現金に配分)、
最後はなんと 1 億ドル!である。
(プロット図は Y 軸が対数スケールであることに注意)
shannon_devil.png

はて、このモデルは本当だろうか?

少し考えれば、この株式の動きは「賭ける側」にとって有利であることが分かる。
結局この株式の動きは、確率 0.5 で賭け金二倍、確率 0.5 で賭け金半額のギャンブルと同じである。
賭け金 1 のときの期待値は 1.25 であるから、賭けなければ「損」である。

さて、このシャノンの悪魔方式の投資モデルを実際の株式市場で検証すると
どうなるか考えてみるのは面白いかもしれない。

そこで、1950/1月から 2006/12月までダウ平均指数にシャノンの悪魔で投資することを考えてみる。
一日の始まりでダウ平均を”買い”、一日の終わりでダウ平均を”売る”。
つまり利益は 終値 – 始値 となる。
結局のところシャノンの悪魔方式は株の”差益”をみているだけであるので、このモデルは妥当だろう。

たとえば 1,000 ドルの資本があり、ダウ平均が 200.13 ドルだったとする。
(これは 1950 年 1 月 3 日の初値)

株に投資できる 500 ドルでは、ダウ平均を 2.5 株(実際は単位は株ではないが)ほど買うことができる。
整数倍しか投資できないとして、2 株だけだとしよう。
1 月 3 日の終値は 198.89 ドルである。

(198.89 – 200.84) * 2 = -2.48
利益は 2.48 ドルのマイナスとなる。

次の日は、今日の資本を昨日の終値で割ったぶんだけ、ダウ平均を購入する。
これを日々繰り返していく。

さて、指数平均は一日で二倍になったり半額にはなったりしないが、
シャノンの悪魔は結局は差益をみている訳であるので、
差益が投資額の二倍に近くなればよいことがわかる。

そこで、レバレッジをかけることを考える。
(1950 年当時に指数平均の先物があったかどうかは不明だが、ここではあったと仮定しよう)

さきほどの、500 ドルの資本で 2 株ダウ平均を購入したときの変動率は、
100.0 * -2.48 / 500 = -0.5 %
である。

レバレッジ 2 倍であれば、 4 株を買うことになり、変動率は 1 % となる。
レバレッジ 10 倍であれば、 10 株を買うことになり、変動率は 5 % となる。

どれくらいのレバレッジが適切か、であるが、
いくつかシミュレーションしたところでは 6 – 8 倍の
レバレッジで取引したときのリターンが最大となった。
10 倍以上のレバレッジにしていくと、
だんだんと投資額を全額失い始める時期が早く訪れるようになった。
(これは半分の確率で2倍、残り半分で半額の株式モデルと違い、
たとえばある日の変動率が 100% だったとき、
ダウ平均が上昇の方向であれば賭け金二倍のリターンになるが、
下落方向だと賭け金をすべて失うことになるためである)

以下は、1950 年から 2006 年まで毎日レバレッジ 8 倍でダウ平均に
シャノンの魔物方式で投資したリターンである。
(ダウ平均の日足は、[2] で入手できます)

dow_return.png

ダウ平均(赤線)は 1950 年 1 月に 200 ドルほどではじまり、2006 年 12 月には
12,000 ドルと 60 倍となった。ほぼ右肩あがり(年平均 8 %)で成長した。

シャノンの魔物方式の投資リターン(緑線)は、
1,000 ドルから初めて、最後は 1,000 万ドルほどに達した。約 1 万倍!である。
(本来であればインフレ率や税金、手数料も考慮すべきであるが、ここでは考えないことにした。
ちなみに 1950 – 2005 の間のインフレ率は約 8 倍である [3] )

しかも、もし 1987 年 10 月 19 日のブラックマンデーの日
(真ん中あたりで最も急激的に下落している部分)、わずか 1 日だけ bet していなかったら、
最終リターンはさらに 10 倍となり約 10 万倍となっていた!

さて、この結果を少し考察してみよう。

シミュレーション期間(1950 – 2006) の各取引日において、
値上がりした日と値下がりした日の比率はそれぞれ 52.006 %, 47.993 % であった。
また、各取引日の値上がり率の平均と値下がり率の平均はそれぞれ 0.321 %, -0.290 % であった。

つまり、賭けの対象としてみた場合、賭け金 1 を賭けたときの期待値は
0.52006 * (1+0.00321) + 0.47993 * (1-0.00290) = 1.0003

と、少なからず賭ける側にリッジ(分、優位性)がある。つまり賭けなければ損となる。

今回のシミュレーション結果はつまるところ、
「シャノンの悪魔」スタイルの投資は、

リッジのある対象に適切なレバレッジ[3]をかけ、
複利のパワーで長期的に大きなリターンを得る

ということなのかもしれない。これはケリー方式とかなり類似性がある。

余裕資金のある方はシステムトレードができる証券会社を見つけて
試してみるとよいかもしれない。

将来的にダウ平均が右肩上がりで上昇するのが不安であれば、
初期資本を二倍用意し、一方は売り立て(取引開始でダウ平均を売り、取引終了で買い取る)
とするとよいだろう。
(そしてこれを毎年、別途初期資本を用意し行っていく)

「シャノンの悪魔」方式は、長期的に上昇のトレンドもしくは下降のトレンドがあれば
成り立つはずである。

最終的にシャノンは株式投資で成功しているが、
結局のところ、これは「シャノンの悪魔」方式ではなく、
成長株を長期間保持しつづけるというスタイルでこれを成し得た。
そのスタイルに落ち着くまでは、「シャノンの悪魔」のようないろいろな
投資スタイルを試したようだが、あまりよいリターンは得られなかったらしい。

長期保有によるシャノンの株式投資のリターンは 30 年間で年間 28 %を達成している。

30 年間で年平均 28 % のリターンとは、つまり最終的に
(1+0.28)**30 = 1646 倍
のリターンである。

30 年間年利 28 % というのは、これは世界第二位の富豪で、
同じく長期保有を基本とする投資家ウォーレン•バフェットのそれとほぼ同じリターンである。
(書籍では比較している期間が違うのでなんとも言えないが、
シャノンのほうがバフェットより 1% ほど勝っていたという)

効率的市場仮説

と、ここまで書いてみて、「シャノンの悪魔」方式 or ケリー方式、
つまりリッジのあるところから複利でリターンを得る、
というシステムは、効率的市場仮説(Efficient Market Hypothesis) [5] を出し抜けるのか?
という疑問がわき上がります。

ユージン•ファーマ [6] が提唱した効率的市場仮説というのは、
簡単に言えばマーケットから他人を出し抜くようなリターンを
得ることができないというものです。
そして、もしそのような出し抜こうとする要素があれば、
いずれマーケットによって「潰される」というような感じです。

つまり、効率的市場仮説の元では、
たとえば「シャノンの悪魔」方式で bet するプレイヤーが
マーケットに存在することが伝われば、そのプレイヤーに対して逆に「罠」を
仕掛けるプレイヤーが出てくることが考えられます。
(「シャノンの悪魔」方式で bet するプレイヤーは、
マーケット開始で”買い”、マーケット終了で”売る”ことが分かっているので、
その逆を行けばそのプレイヤーからリターンを奪い取ることが出来る)

ここらへんの金融工学に関するお話は面白いものが多いですし、また、
金融工学と大域照明理論は、確率論、統計、LDS(低食い違い量列) など
数学的ツールが共通していることから、
ちょくちょくこれからも取り上げていければと思います。

[1] ディーラーをやっつけろ! ブラックジャック必勝法
http://www.tradersshop.com/bin/showprod?c=9784775970751
[2] http://finance.yahoo.com/q/hp?s=%5EDJI
[3] http://www.westegg.com/inflation/
[4] 最適な賭けの額というのは、本当はケリー基準で決定できるので、
最適なレバレッジ量というのもケリー基準で求められるのかもしれない。
ちなみにケリー基準についてはこちらが参考になります。
http://www.geocities.jp/y_infty/management/index.html
[5] http://cruel.org/econthought/schools/finance.html
http://www1.tcue.ac.jp/home1/abek/htdocs/emh.html
[6] http://cruel.org/econthought/profiles/fama.html