情報システム基礎論2：第3回(担当：古賀 2014年4月22日: ランダム

情報システム基礎論 2：第 3 回 (担当：古賀)
2014 年 4 月 22 日: ランダムサンプリングを使用した数値データの選択
レジュメ URL: http://sd.is.uec.ac.jp/koga/lecture/IF2/
ランダムサンプリング
1
n 個の要素からなる統計データ S がある。S の性質を調べたい。しかし、n が大きい時、すべてのデータ
を使うと計算時間が膨大になる。
そこで S の部分集合 R をランダムに取り出す。要素数は |R| < |S|。S の性質は R の性質により近似
的に計算する。
例：10000 個の実数データ S がある。S の各要素を Si (1 ≤ i ≤ 10000) とする。S の平均値は、
P10000
Si
Save = i=1
.
10000
ランダムサンプリングでは S から 1000 個の要素 Ri (1 ≤ i ≤ 1000) を取り出してその平均値を
P1000
Ri
Rave = i=1
1000
を計算する。Rave は Save の近似値として使える。また、Rave の計算時間は Save の計算時間の
1
10
程度。
数値選択アルゴリズム
2
問題： n 個のデータ S から k 番目に小さい要素を探す。
単純な解法：quicksort などを用いて完全に整列すればこの操作は自明にできる。しかし、O(n log n) の計
算量（=要素比較の回数）がかかる。ここでは、ランダムサンプリングを利用したより高速な確率的アル
ゴリズムを紹介する。
Definition 1 Si : S の中で i 番目に小さい要素
2.1
基本アイデア
ソーティングはすべての要素に対して順位付けを行うのが無駄。仮に、S の中で Sk より小さいデータ a
と大きいデータ b が与えられていれば、次のやり方で解ける。
1. a と b を S の全要素と比較。S の中で a 以上、b 未満のデータ集合を P とする。同時に S 内での a,
b の順位を求める。a の順位を ra 、b の順位を rb とすると ra < k < rb 。
2. P をソート。Sk は P の中で k − ra + 1 番目に小さいデータ。
計算量 = O(2n + |P | log |P |).
従って、
• a と b を効率的に見つけられる
• |P | |S|
であれば計算量小さい。
1
(1)
ra-1
sorted
S
k-ra+1
P
a
b
Sk
small
large
Figure 1: 整列された S に対する集合 P の位置
R
n3/4
-1/4
n
x
S
n
Figure 2: ランダムサンプリング
2.2
ランダムサンプリング
a と b をランダムサンプリングにより定める。S からランダムに少数のデータ集合 R を取りだす (Fig. 2)。
例: S(データ数 n = 10000) から k = 4000 番目に小さいデータを探す場合、P の要素数を 2000 程度にす
るには？
• R の要素数を 1000 に定める。
• a は R 中で 300 番目に小さいデータ, b は R の中で 500 番目に小さいデータとする。
• a は S 中で 3000 番目くらいに小さい, b は S の中で 5000 番目くらいに小さいだろう。
3
これを一般的に記述する。S からランダムに n 4 個のデータ R を取りだす (Fig. 2)。R を整列して a
と b を以下のように定める (Fig. 3)。
• a: R の中で kn− 4 −
1
• b: R の中で kn− 4 +
1
√
√
n 番目のデータ。つまり、a = R
n 番目のデータ。つまり、b = R
1 √ 。
kn− 4 − n
1 √ 。
kn− 4 + n
sqrt(n) sqrt(n)
sorted
R
a
b
-1/4
R(kn)
Figure 3: R における a と b の位置
2
• S 上での a の順位 ra は (kn− 4 −
1
• S 上での b の順位 rb は (kn− 4 −
1
√
√
1
3
n) ∗ n 4 = k − n 4 と近くなるだろう。
1
3
n) ∗ n 4 = k + n 4 と近くなるだろう。
3
3
3
3
従って、|P | の値は 2n 4 程度。O(|P | log |P |) = O(n 4 log n 4 ) = O(n 4 log n) = o(n) < O(n).
2.3
アルゴリズム Lazyselect
3
1. S からランダムに n 4 個のデータを取り出す。同じデータを複数回取り出してもよい。この集合を R
とする。
2. R をソートする。a = R
1 √ 、b
kn− 4 − n
=R
1 √ 。ただし，
kn− 4 + n
3
• k が非常に小さい: if k < n 4 , a = R1 .
3
• k が非常に大きい: if k > n − n 4 , b = R
3
n4
.
3. a, b を S の全要素と比較し、それぞれの S における順位 ra と rb を決定する。この際、k の値により、
集合 P を以下のように決定。
3
3
(a) 標準ケース: If n 4 ≤ k ≤ n − n 4 , P = {y ∈ S|a ≤ y ≤ b}.
3
(b) k が非常に小さい: if k < n 4 , P = {y ∈ S|y ≤ b}.
3
(c) k が非常に大きい: if k > n − n 4 , P = {y ∈ S|y ≥ a}.
4. P が前提条件を満足するかを確認する。確率的ゆらぎにより P が前提条件を満足しないケースもあ
るため。
• a < Sk < b を判定する。ra < k < rb を判定すればよい。 3
• P の要素数が多すぎないかをチェックする。具体的には |P | ≤ 4n 4 かどうかを判定する。
上記 2 条件が成立しない場合 → step 1 に戻ってランダムサンプリングやり直し。
5. P をソート。Pk−ra +1 を答として出力する。
2.4
Lazyselect における比較回数
3
• step 1 は O(n 4 ) = o(n)
3
• step 2 は O(n 4 log n) = o(n)
• step 3 は 2n
• step 4 は O(1) = o(n)
3
• step 5 は O(n 4 log n) = o(n)
従って、Lazyselect が Step 4 で一度もやりなおしをしなかった場合の比較回数は 2n + o(n). 以下で
は、Lazyselect が高確率でやり直しをしないことを Chebychev の不等式を使って示す。
Theorem 2 Lazyselect は 1 −
2n + o(n) に収まる。
4
1
√
n
の確率でやりなおしをしない。従って、1 −
3
4
1
√
n
の確率で比較回数は
• これまで知られている一番速い決定的アルゴリズムでの比較回数は 3n。Lazyselect はそれより速い。
しかも実装簡単。
• n が小さくなるに連れてやり直し確率が増加する。よって、step 5 を再帰呼出で実装するのは駄目。
確率的アルゴリズムを再帰呼出で実装する時は、データサイズが小さくなった
ら決定的アルゴリズムを用いて正しい解を返す必要がある。
Theorem 2 の証明: Lazyselect が Step 4 でやり直すのは以下の 2 ケース。それぞれ低確率でしか発生し
ないことを示す。
ケース 1: Sk < a or Sk > b。
3
ケース 2: P のサイズが大きい場合。つまり、|P | > 4n 4 。
2.4.1
ケース 1 が発生する確率
2sqrt(n)
sorted
R
a
b
-1/4
R(kn)
Sk
2sqrt(n)
sorted
R
a
b
-1/4
R(kn)
Sk
Figure 4: ケース 1
R 内で Sk 以下である要素数を X とする。Fig. 4 より、
• Sk < a ↔ X < kn− 4 −
1
• Sk > b ↔ X ≥ kn− 4 +
1
√
√
n.
n
よって、ケース 1 が発生する確率は
P [Sk < a] + P [Sk > b] = P [X < kn− 4 −
√
n] + P [X ≥ kn− 4 +
√
1
≤ P [|X − kn− 4 | ≥ n]
1
1
√
n]
実はこれは Chebyshev の不等式が適用できる形になっている。
X の期待値:
1 個ランダムに S からデータを取りだした時、それが Sk 以下である確率は nk . よって、R 内の Sk 以下と
なる要素数 X の期待値 µX は
3
1
k
µX = ∗ n 4 = kn− 4 .
n
4
X の分散: 分散の加法性を利用して計算する
3
3
3
k
k
k
k
k
k
n4
2
σX
= n 4 · { (1 − )2 + (1 − )(0 − )2 } = n 4 · (1 − ) ≤
.
n
n
n
n
n
n
4
以上から，ケース 1 が発生する確率は
P (|X − µX | ≥
2.4.2
√
1
n) ≤ P (|X − µX | ≥ 2n 8 σX ) ≤
1
√ .
44 n
ケース 2 が発生する確率
3
|P | > 4n 4 となる事象は論理的に
3
(A) Sk ∈
/ P かつ |P | > 4n 4
3
(B) Sk ∈ P かつ |P | > 4n 4
3
があるが、(A) が発生する確率はケース 1 で考慮済み。従って，(B) の Sk ∈ P かつ |P | > 4n 4 となるケー
スを考えればよい。
Sk-2n
P
4n-3/4
Sk Sk+2n
3/4
3/4
Sorted S
a
b
>4n-3/4
Figure 5: ケース 2
3
Sk ∈ P という条件で |P | > 4n 4 ならば、a < S
3
k−2n 4
または b > S
3
の少なくともどちらかが成立
3
].
k+2n 4
する (Fig. 5)。従って、
3
P [|P | > 4n 4 ] ≤ P [a < S
P [a < S
Z ≥ kn
− 41
3
k−2n 4
−
√
] について考える。R 内で S
3
k−2n 4
3
k−2n 4
] + P [b > S
k+2n 4
以下である要素数を Z とする。a < S
3
k−2n 4
ならば、
n (Fig. 6)。従って
a
Sorted R
b
Sk-2n
3/4
Figure 6: 変数 Z
P [a < S
] = P [Z ≥ kn− 4 −
1
3
k−2n 4
√
n].
式 (2) を Chebyshev の不等式を使って評価するために Z の期待値と分散を求める。
5
(2)
• 期待値 µZ =
3
√
3
1
× n 4 = kn− 4 − 2 n.
3
k−2n 4
n
• 分散 σZ2 = n 4 ×
3
k−2n 4
n
(1 −
3
k−2n 4
n
)≤
3
n4
4
. 従って，σZ ≤
3
n8
2
Chebyshev の不等式より
P [Z ≥ kn− 4 −
1
似た手順で、P [b > S
√
3
k+2n 4
n] = P [Z − µZ ≥
√
n]
√
1
≤ P [|Z − µZ | ≥ n] ≤ P [|Z − µZ | ≥ 2n 8 σZ ] ≤
]≤
1
√
44 n
44
1
√ .
n
も示せる。
Appendix: Chebyshev の不等式
X を確率変数 (期待値 µX , 標準偏差 σX ) とする。t を正実数とする。この時、以下が成立する。
P [|X − µX | ≥ tσX ] ≤
6
1
.
t2

Download Report