統計的システム論サンプリング法

統計的システム論
サンプリング法
林和則
京都大学大学院情報学研究科
E-mail: [email protected]
講義資料： http://www.msys.sys.i.kyoto-u.ac.jp/~kazunori/sst.html
1
2
AGENDA
! モンテカルロ法
! 一様乱数（擬似乱数）
! 逆関数法
! Marsaglia法
! 棄却サンプリング
! 重点サンプリング
! SIR (sampling/importance-resampling)
! 参考文献
3
モンテカルロ法の簡単な例
! 円周率の計算（ヒットミス法）：
1.  [-1,1]の値をとる二つの乱数を
発生させる
2.  座標が円の中にあるかない
かの判定をする
a. 
ならば円内
b. 
ならば円外
3.  1.と2.を繰り返して最後に 円内の点の数
円の面積
全ての点の数
正方形の面積
から円周率を推定する
4
モンテカルロ法の簡単な例(続)
! 積分値の計算（荒いモンテカルロ法）：
[a,b]の一様乱数
a∼bにおける
の平均の
高さ：
積分区間の幅：
a
x
a
x
5
モンテカルロ法とは
! 大数の法則を利用して積分を数値的に求める手法
! 所望の確率分布からのサンプルを得る（乱数を生成
する）ことが中心的な問題
! 静的なモンテカルロ法と動的なモンテカルロ法
6
一様乱数
! 線形合同法：
•  UNIX系OSの標準ライブラリ rand()
•  漸化式： •  精度が必要な場面で使ってはいけない（とされている）
7
一様乱数（続）
! メルセンヌ・ツイスタ：
•  1996年にmatsumoto, nishimuraによって提案
•  漸化式：
はGF(2)の元が要素のw×w行列はの上位(w-r)ビットとの下位rビットを並べたもの
•  http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/mt.html
• 
のとき，周期，623次
元均等分布 8
単純な分布からのサンプル生成：逆関数法
・区間で一様に分布する乱数の発生源がある
z
・ある関数を用いてと変換する
y
・変換後のが所望の分布に従うようにを選ぶ
y
・の確率密度関数：
y の分布関数の逆関数に一様乱数を代入すればよい
z
分布関数が求まるか？
逆関数が求まるか？
9
逆関数法の例：指数分布の場合
y
・の確率密度関数：
y
・の累積分布関数：
・逆関数（変換式）：
10
逆関数法の例：コーシー分布の場合
y
・の確率密度関数：
y
・の累積分布関数：
z = h(y) =
�
y
−∞
y
�
p(y � )dy �
1
1
�
=
·
dy
�2
−∞ π 1 + y
�y
�
1
tan−1 y �
=
π
−∞
1
1
−1
= tan y +
π
2
・逆関数（変換式）：
11
逆関数法：多変数への拡張
・変換前後の結合密度関数の関係：
12
Marsaglia法
ガウス分布からのサンプルの生成法
・一様分布する乱数のペアを生成
・でないものは破棄
・それぞれのペアに対して
有名なBox-Muller法では，一様乱
数のペアに対して
を計算する
このときの同時分布は
13
一般のガウス分布からのサンプル生成
・平均，分散のガウス分布からのサンプルの生成：
x は平均0, 分散1のガウスランダム変数
・平均，共分散行列のガウス分布からのサンプルの生成：
：コレスキー分解
は各要素が独立で平均0, 分散1の
ガウスに従うベクトル値の確率変数
14
棄却サンプリング：準備
・からサンプリングしたいが，直接は困難
z
・任意のについて，の値はある正規化定数を除いて容易
に分かる（では分かるけどは分からない）
・容易にサンプルを抽出できる分布を用意（提案分布）
z
・定数を導入し，の全ての値に対してとなるよう
にする
比較関数
z
15
棄却サンプリング：手順
・乱数をから生成する
・乱数を区間の一様分布から生成
・ならばサンプルは棄却，そうでなければを保持
z
・保持されたに対応するの値はに従って分布
z
16
棄却サンプリング：原理
z
・サンプルの累積分布関数：
：特性関数
の累積分布関数
17
k
棄却サンプリング：の決め方と問題
・サンプルが受理される確率：
・サンプルが棄却される確率：
は，全てのに対して
z
を満たす範囲で
出来るだけ小さくすべき
z
適切な包絡分布が決まるか？
適切なが決まるか？
18
重点サンプリング：考え方
・サンプリングを行う目的は多くの場合，ある関数の確率分布の下での期待値計算
・重点サンプリングは期待値を直接近似する手法（からのサン
プル生成ではない）
・空間を均一なグリッドで離散化すると
z
と近似できるが，一様サンプリングは効率が悪い
が大きな領域から
サンプル点を取りたい
19
重点サンプリング：手順
・容易にサンプルを抽出できる分布を用意（提案分布）
・からのサンプルをとする
・重点サンプリングによる期待値の近似：
：重要度重み
20
重点サンプリング：手順(続)
・の正規化定数が分からない場合
21
SIR (sampling/importance-resampling)
棄却サンプリング同様，提案分布を用いるが定数を決定する
ことなく，に（近似的に）従うサンプルを生成する手法
・から個のサンプルを抽出
・によって重みを決定
・離散分布から重みで与えられる
確率にしたがって個のサンプルを抽出する
再サンプリング
22
SIR：原理
・再サンプリングされた値の
累積分布関数：
の累積分布関数
：特性関数
23
SIR：注意点
・有限のの場合は近似的なサンプルでしかない
・がに近づくにつれて近似は改善
・のとき，初期サンプルも再サンプリングされた値もに従うので，となる
・の期待値は，もとのサンプルと重みから求まる
24
参考文献
1. 
C. M. Bishop, Pattern Recognition and Machine Leaning, Springer, 2006
2. 
A. F. M. Smith and A. E. Gelfand, “Bayesian statistics without tears: a samplingresampling perspective,” Amer. Stat., vol. 46, no. 2, pp. 84-88, May, 1992.
3. 
伊庭幸人ほか, 統計科学のフロンティア12 計算統計II, 岩波書店, 2005.
4. 
W. H. Press etc., Numerical Recipes, 3rd Edition, Cambridge University Press, 2007.

Download Report