好きなアルゴリズム:モンテカルロ法

今週前半、小飼弾さんの「404 Blog not found」が「プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10」という記事を載せていたが、仕事も一段落間近かなので、その記事を見て以来、書きたいと思っていたことを書いてみようと思う。
nobilog2復活へのリハビリエントリーだ。

小飼さんの記事は、Hatena Questionの「あなたが一番好きなアルゴリズムを教えてください。また、その理由やどんな点が好きなのかも教えてください」がきっかけになった記事のようだ。

 私はプログラマーではないが、まだパソコンが8ビットで「マイコン」と呼ばれていた時代に出会って衝撃を覚えたアルゴリズムがある。

 もしかしたら一般に言うアルゴリズムとは別なのかもしれないが、Wikipediaでも"algorhythm"と書かれていたので許して欲しい(広義のアルゴリズムにはぎりぎり入るのではないだろうか?)。

 それは当時の月刊アスキーだか、図書館で借りた本で読んで知った
モンテカルロ法」と言うものだ。

日本語版のWikipediaによれば、「乱択アルゴリズムと一般に定義される」らしい。

この日本語のWikipediaの内容は、数学を離れて久しい私には難しすぎるが、
私が中学の時に読んだ本には、モンテカルロ法を使った簡単な円周率の求め方が載っていた。

Montecarlo

半径2cmの円を考える。
と、書こうとしたが、検索してみたら、おそらく私よりもずっとわかりやすく解説しているサイトがあったので、解説はそちらに譲ることにしよう:


 ようするに架空の円を囲む正方形(あるいはその弧)の中に、乱数で点を打っていって、その点が円の外側に何個、内側に何個打たかをカウントし続けて、統計的に円周率を割り出す、というものだ。

 いわゆる、数学的アルゴリズムの様に、パラメーターの数字を当てはめると、スパっと答えが出るものではなく、乱数を使ってじわじわと解答に近づいていくわけだ。

 この乱数を使う、という点が斬新で、目からウロコが落ちる思いがした。
(Life is randomーー人生ランダムな私になんとピッタリな考え方だろう)

ところで、上のモンテカルロ法の図は、実は最近、あるイベントのために用意したものだ。
そう小飼さんと一緒にパネルディスカッションに参加させてもらったtechstyle社主催の「群衆の叡智サミット2007」のときだ。
実は当日、パネルディスカッションが、どんな風に進むのがわからず(life is randon的には、楽しいシチュエーションだ)、「万が一、自己紹介のプレゼンが必要だった場合」に備えて、控え室で一生懸命スライドをつくっていた。

 でも、司会の岡田さんに聞いたら、特にスライドは必要そうでなかったし、他のパネリストの方々の話しがおもしろかったので、(一応、マシンにVGAケーブルを指してはいたものの)結局スライドは使わなかった。

 せっかくなので、ここで何枚か紹介しよう。
 最初の自己紹介のスライドは無視するとして、その次に来たのは、「群衆の叡智」という概念を知って私の頭に浮かんだ、さまざまなキーワードを並べたものだ。


Gunshu005001

真っ先に浮かんだキーワードがモンテカルロ法だった。
いわば、人間を使ったモンテカルロ法、というわけだ。

そのモンテカルロ法のスライドには2枚目があって、
なんか、これもモンテカルロ法的、ということで、今年のFooCampで見てきたMicrosoft社のPhotoSynthを紹介。


他にも簡単に解説しておくと、
腸内細菌では、「The New Context Conference 2007」の北野宏明さんのお話
bootstrap allianceはdouglas engelbart博士
path of evolutionは、このブログでも何度か紹介しているScott Berkunの「Myth of Innovation」の話しを盛り込んでいました。

この「Myth of Innovation」、Mac Fan最新号の書評ページで知ったのですが、日本語訳が出たんですね。
「イノベーションの神話」というタイトルだそうです。



いろいろな人の情報が集まってきて、そこからビジョンが形成されるって、こういうことじゃないかと感じたのだ(よりたくさんの人の意見/写真を集めた方が、ディテール部分まで考慮/写されているか可能性が高い)。

 で、この際に重要なのが、均質な人を増やすのではなくって、やっぱり、多様な人々を増やしていくこと。

 そこで伊藤穣一さんもよく紹介しているScott E. Pageの「the Difference」を紹介。

Gunshu008002


実はScott E. PageのWebページでつい先日まで、彼のプレゼンのスライドが配布されていた(現在はない模様):
http://www.cscs.umich.edu/~spage/michigania1.ppt
http://www.cscs.umich.edu/~spage/michigania2.ppt

このスライドで紹介していた実験結果によれば:
Crowd Error = Average Error - Diversity
という式が成り立ったようで、

群衆の予想による誤答率は、平均の誤答率 ー 多様性の度合い

つまり、多様な人が集まれば集まるほど、誤答が減ったようだ。

これって、さきほどのモンテカルロ法に当てはめると、diversityというのが例えばy軸の変化で、それがないと、一箇所だけに集中してしまって、烏合の衆化、イナゴ化が進んでしまうというイメージなんだろうか、と思っているのだが、果たしてどうなんだろう。

いずれにしても、「群衆の叡智」は本当におもしろいし、先日のイベントも、とても注目度が高かったようで気がつけば、関連記事をまとめたブログ記事まで登場していたようだ:

群衆の叡智サミット2007関連の記事まとめ

これからも、もっといろいろ勉強してみようと思います。

さっそく、総合予測市場サイトの「predictions.jp」も登録させてもらっている。

岡田さん、誘ってくださってありがとうございます!

P.S.参加パネリストの間では、前回、次に不祥事を起こすのはどこだと、来場者に問いかけたところ「マクドナルド」が「小飼弾」さんに負けず劣らず大きかったので、「これはもしかして当たったのか?」と話題になっている。

「みんなの意見」は案外正しい「みんなの意見」は案外正しい
ジェームズ・スロウィッキー 小高 尚子

角川書店 2006-01-31
売り上げランキング : 2820

Amazonで詳しく見る
by G-Tools


The Difference: How the Power of Diversity Creates Better Groups, Firms, Schools, And Societies
The Difference: How the Power of Diversity Creates Better Groups, Firms, Schools, And SocietiesScott E. Page


Amazonで詳しく見る
by G-Tools


イノベーションの神話
イノベーションの神話Scott Berkun 村上 雅章


Amazonで詳しく見る
by G-Tools



ウィキノミクス マスコラボレーションによる開発・生産の世紀へウィキノミクス マスコラボレーションによる開発・生産の世紀へ
ドン・タプスコット/アンソニー・D・ウィリアムズ 井口 耕二

日経BP社 2007-06-07
売り上げランキング : 2268

Amazonで詳しく見る
by G-Tools


投稿者名 Nobuyuki Hayashi 林信行 投稿日時 2007年12月01日 | Permalink

  • Re: 好きなアルゴリズム:モンテカルロ法


    なかなか、眠れないので、AppleScriptで簡単に(ちょっと雑に)
    モンテカルロ方で円周率を求めるスクリプトを書いてみました。

    set a to (display dialog "何個の点を打ちますか?" default answer "1")
    set b to (text returned of a) as number
    set c to 0
    repeat with i from 1 to b
    set x to (random number) * 2 - 1
    set y to (random number) * 2 - 1
    if x ^ 2 + y ^ 2 ≤ 1 then set c to c + 1
    end repeat
    set pai to 4 * c / b
    display dialog "円周率は" & pai as string

    投稿者名 nobi

  • Re:好きなアルゴリズム:モンテカルロ法

    、眠れないので、AppleScriptで簡単に(ちょっと雑に)

    投稿者名 replica handbags WEB

  • Re:好きなアルゴリズム:モンテカルロ法

    金儲けの為に金を使い儲けた金を金儲けに使う以下永久ループ

    投稿者名 fake chanel handbags WEB