疑似乱数に状態なんていらない - あどけない話
State モナドと疑似乱数で書いたように、遅延評価が利用できる言語では、無限数列が扱えるので、疑似乱数を使う際に状態を持たなくてもよい。その一例として、モンテカルロ法による円周率の近似を挙げてみる。 XY 平面に単位円を考える。 radius :: Double radius = 1.0この円がぴったり収まる大きさ1の正方形を描く。ここで、第一象限のみを考える。正方形のうち、第一象限にある部分の面積は、1/4。第一象限にある円の面積は、全体の 1/4 だから π/4。 モンテカルロ法では、第一象限の正方形の中に、ランダムに点(x,y)を打つ。たくさんのランダムな点を、疑似乱数から生成しよう。そのとき、状態を持つのではなく、乱数の無限数列を生成する。 import Random randomSeq :: Int -> [Double] randomSeq seed = randomRs (
モンテカルロ法を試す―円周率の評価―
確率法則を用いて問題を解くモンテカルロ法（Monte Carlo meyhod）では、質のよい乱数が必要である。 C言語で用意されている関数randと、高品質で高速に乱数を生成できるとして知られるメルセンヌ・ツイスタを利用して、円周率を評価してみる。 また、その際のアルゴリズムとして「あたりはずれ法」と「粗いモンテカルロ法」を用いて計算する。 図１のような単位円の第１象限領域の面積をモンテカルロ法にて求め、 解析的に求められる面積$\pi/4$と比較することによって、円周率の評価を行うことにする。 図１．単位円の第１象限領域 あたりはずれ法 あたりはずれ法とは、面積を評価したい領域$S_A$を面積が既知の領域$S$で囲み、 領域$S$上に分布が一様になるように$N$個の点を降らせる。 領域$S_A$上に落ちた点の数が$N_A$であれば、$S_A$の面積は、 で評価することができる。 図１の
Algorithm for generating Poisson random values
The most direct way of generating random samples from a Poisson distribution is efficient for some parameters and inefficient for others. Wikipedia attributes the following algorithm to Donald Knuth: init: Let L ← exp(−λ), k ← 0 and p ← 1. do: k ← k + 1. Generate uniform random number u in [0,1] and let p ← p × u. while p > L. return k − 1. Here’s the idea behind the algorithm. The time between ar
ベイズの定理と３囚人問題、モンティ・ホール問題を言葉だけで納得してもらう方法を募集。
占い師がこう言った。 「AB型を一言でいうと「変人」となります。より正確にいうなら「ＡＢ型の常識、世間の非常識」ということです。AB型は知的活動に適応した人間です。頭で考えて生きる人たちです。怠け者で、執着心があまりありません。」 さて、これは正しいだろうか？ http://www.catv296.ne.jp/~butakusa-no-niwa/kannjyou.htm こちらのページからの引用トリックなのだが、AB型を「AB型は社会の中では少数派です。」としている。 もし、貴方が血液型占いが大好きだったら、これが真であると思うかもしれない。だが、この占いは、巧妙なトリックがある。 それは、事前確率を織り込んでいる、という点だ。 http://www.fukushima-bc.jp/new_page_70.htm こちらのページで、日本人の血液型分布が見れるが、AB型の日本人は、全体の１０
さいころを使った１〜Ｎまでの完全な乱数の作り方 ２≦Ｎ≦２０ - chokudaiのブログ
人生ゲームとかやる時用に 手軽になるように作ってみました。振る回数の期待値は全て３以下です。 振る必要のある回数の期待値も併記しています。これより減らせる場合はコメントによろしくお願いします。回数はおそらくΣ[k=1..∞](6^(k-1)%n)/6^(k-1)になるだろう、という予測が経ちましたが、全ての明記はちょっと複雑になるので止めておきます。n=13,14,16,17,19,20が最善でないです。 N=2 (1回) 方法１ さいころを１回振り、偶数の場合１、奇数の場合２ 方法２ ３以下なら１、４以上なら２ N=3 (1回） 方法１ さいころを１回振り、３で割った余りに１を足す 方法２ １〜２が１、３〜４が２、５〜６が３とする N=4 (1.5回) ５以上が出たら振りなおす 別解法 N=2を２回利用する(2回) 追記 omeometoさん提供(1.333333回） １〜４が出たらその
本の虫: 確率分布の使い方
C++0xのstd::randomには、様々な分布クラスが存在する。一体どうやって使い分ければいいのか。ここでは、ゲームにたとえて考えてみる。 もっとも簡単な分布は、一様分布（Uniform distributions）である。これは、a ≦ i ≦ b, の範囲の値iを、それぞれ等しい確率で返す分布である。 ゲームでいえば、サイコロやルーレットなどの実装に使えるだろう。 // 六面サイコロの実装 int main() { std::mt19937 rng ; // 一様分布 // 0から5までの数字を等しい確率で返す分布 std::uniform_int_distribution<> dice(0, 5) ; int a[6] = { } ; // 六面サイコロの出た目の回数を記録する配列 // 600回サイコロを振る for ( int i = 0 ; i != 600 ; ++i )
数学ガール／乱択アルゴリズム - Mae向きなブログ
『数学ガール 乱択アルゴリズム (数学ガールシリーズ 4)』を読んでます。数学ガールシリーズも本書で4冊目ですが，乱択アルゴリズムでは擬似コードでアルゴリズムが紹介されています。読者の多くの方はプログラミング言語に親しまれている方だと思いますが，ひょっとして，本書を通して初めてプログラムに触れるという方もいらっしゃるかもしれないということで，何個かプログラムにしてみました。Rubyで書いています。 Rubyがインストールされていないという方は，Googleなどで「Ruby インストール」と検索してインストールしてください。 番兵付きリニアサーチ・アルゴリズム(p48) 本では，2行目が n+1，3行目が1となっていますが，多くのプログラミング言語は配列の添字を0から数え始めますので，それぞれ，nと0に変更しています。 あと，本では手続きの名前を`-'で区切っていますが，これでは引き算の意味
Probability and Computing - makisyuの日記
Twitter連携とmixi連携を付けてみた。 はてなブログの使い方を練習しつつ連投する。 例によってこの本 確率と計算 ―乱択アルゴリズムと確率的解析― 作者: Michael Mitzenmacher,Eli Upfal,小柴健史,河内亮周出版社/メーカー: 共立出版発売日: 2009/04/24メディア: 単行本購入: 2人 クリック: 31回この商品を含むブログ (11件) を見る の話の続き。 そういえば。 この本に、バケツソートはある条件下で平均のソートができる、ということが書いてあって面白かった。ソートの下界はなのだが、条件を付ければ線形まで落とせるようだ。詳細はググればすぐに出そうなので書かないけれど、この内容で分割統治の力を再認識した。 分散も分割が基本戦略になると思うのだけれど、分割はいいとしてその統合（MapReduceで言うところのReduce）の実装って実はとても
第7回 代表的な離散型確率分布 | gihyo.jp
今回は、前回導入したNumpy、そしてグラフを描画するmatplotlibを使って、いくつかの代表的な分布を紹介していきます。 第5回「「よく使う分布」はどうしてよく使う？」の項でも代表的な分布が紹介されていました。そこでは、“この状況（モデル）では、この分布を使う”というパターンを想定する、それが“よく使う分布”がいくつも存在する理由と言及されていましたが、どのような状況でどのような分布を使えばいいのでしょうか？ 実際、どのような状況のときに、どのような分布を使うと説明しやすいかを考えながら、みていきましょう。 matplotlibのインストール matplotlibはpythonとNumpyのための高機能なグラフ描画ライブラリです。今後もグラフを描画することがあるかと思いますので、ここでインストールしておきましょう。 公式サイトのダウンロードから各OS向けのパッケージを入手して
Rediscover the Monte Carlo - 西尾泰和のはてなダイアリー
僕個人はゲームの思考ルーチンを作ることなどには興味があるので、みんな知っていることだと思っていたのですが、意外と「現在世界最強の囲碁の思考ルーチンはモンテカルロ」ってのは知られてないみたいですね。うっかりすると「そんなわけないだろー」とか言われてしまう。その根底には「モンテカルロはとても収束が遅くて使いものにならない」という過去の記憶があるのかなー。ちょうどJavaScriptが使いものにならないおもちゃ言語だと思われていたように。 囲碁の思考ルーチンを著しく進化させた新しいモンテカルロが昔の単純なモンテカルロとどう違うかというと、UCB1という評価関数で「もっと探索するとヨサゲな局面」を判断して、ヨサゲな局面から優先的に探索するという点なんだけど、そういう定性的な話をしてもピンと来ないよね。同じ発想をモンテカルロで円周率を求めるプログラムに適用したら収束の速さが定量的にはっきり見えて面白
プログラミングのための確率統計 in Haskell
こんな表のことを確率分布といいます。サイコロをふったときに起こるイベントの確率、たとえば「偶数の目が出る」確率を調べることは、この確率分布からこんな別の確率分布への変換だと考えられます。 この変換は、具体的にはこんな対応です。P(偶数) = P(2) + P(4) + P(6) P(奇数) = P(1) + P(3) + P(5)P(X)がイベントXに対する確率を表しているわけですが、Pを「イベントの集合から[0,1]区間の実数への関数」だとみなすこともできます。確率分布から確率分布への変換は、関数に対する演算でもあるわけです。確率分布を連想リストで表せば、高階関数や代数型を使って、この変換をモデル化できそうです。 以前、このアイデアをSchemeで試してみたことがありました。当時は、そもそも確率についての理解が今よりもいっそうあやしかったし、実装もちゃちでしたが、このアイデアが特別なもの
第3回 ベイジアンフィルタを実装してみよう | gihyo.jp
さらに詳細な利用方法が知りたい方は、Yahoo!デベロッパーズネットワークのマニュアルを参照してください。 ベイジアンフィルタの実装 ここから本格的にベイジアンフィルタの実装に入っていきます。 その前に、まずは先程のリスト1のコードを利用して入力された文章をわかち書きし、単語の集合を返す関数を作成しnaivebayes.pyとして保存しましょう。こちらも先程のmorphological.pyと同様にutf-8で保存してください。 リスト2 文章の分割をする関数（naivebayes.py） # -*- coding: utf-8 -*- import math import sys #yahoo!形態素解析 import morphological def getwords(doc): words = [s.lower() for s in morphological.split(doc)
第2回 確率の初歩 | gihyo.jp
今回は、機械学習で使う「確率」のお話です。 確率は、統計的な機械学習のもっとも重要な基礎知識です。とはいえ、確率についてゼロから説明するというのは紙数的にも厳しいため、高校の確率を少し憶えているくらい（期待値や標準偏差など）を前提とし、「高校の確率」と「機械学習の確率」の本質的な相違点について、少し丁寧に見ていく、という形で進めていきます。 機械学習と確率 最初に、機械学習にとって確率はどういう役割なのかを確認しておきましょう。 実のところ、機械学習に確率が必須というわけではありません。ニューラルネットワークやサポートベクターマシンなどの有名な手法も「確率を用いない機械学習」ですし、その他にも数多くの手法があります。しかし、「確率を用いない機械学習」の多くは、「結果のランキングを作りづらい（評価値の大小に意味がない）」「条件が異なる場合の結果を比較できない」などの欠点がありま
マルコフ連鎖で日本語をもっともらしく要約する - ザリガニが見ていた...。
そもそも、マルコフ連鎖とは何なのか？全く聞いたこともなかった。そして、文章を要約するのはとっても高度なことだと思っていて、自分のレベルではその方法を、今まで思い付きもしなかった。 しかし、以下のようなシンプルなRubyコードでそれが出来てしまうと知った時、目から鱗である...。一体、何がどうなっているのだ？コードを追いながら、マルコフ連鎖を利用するという発想の素晴らしさを知った！ 作業環境 MacBook OSX 10.5.7 ruby 1.8.6 (2008-08-11 patchlevel 287) [universal-darwin9.0] mecab utf8環境でインストール済み マルコフ連鎖に出逢う rssを流し読みしていると、以下の日記に目が止まった。（素晴らしい情報に感謝です！） MeCabを使ってマルコフ連鎖 一体何が出来るコードなのか、日記を読んだだけではピンと来なかっ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Group: トレーニング講座（3/06 (日)) | アルゴリズム プログラミング
確率・統計 (5) 正規分布
微分積分
乱択アルゴリズム紹介(Bloom Filter) - Preferred Networks Research & Development
Probability and Computing - makisyuの日記
実践的アルゴリズム