ランダムウォークの最適化

自己ループ確率の除去による
メトロポリスウォークの高速化
西関研究室９５２４
近藤啓介
2015/10/1
1
はじめに
インターネット,センサネットワークが発展
• 記憶しきれない程大規模
• 動的に変化する
全体を記憶しきれない
端から見ていくと上手くいかない
“ランダム”な探索
2015/10/1
2
ランダムウォーク
v Vから出発する．
2.　v の隣接頂点 v  N v をランダムに選択し , v に推移する．
3.　v に対しても 2.と同様の操作を行い，以下同様に繰り返す．
1.　ある頂点
0
0
0
0
1
1
探索時間は速いほうが良い
0.2
0.3
1
2
0.3 0.5
0.7
0.5
3
0.4
0.6
2015/10/1
0.5
G
4
 0 0.3 0 0.7 


 0.2 0 0.3 0.5 
P
0 0.4 0.6 0 


 0.5 0.5 0

0


3
ランダムウォークの速さ
到達時間（hitting time）
𝐻𝐺 𝑃; 𝑢, 𝑣 :頂点𝑢から始まるランダムウォークが
初めて頂点𝑣に到達するために必要な遷移数の期待値
𝐻𝐺 𝑃 = max 𝐻𝐺 (𝑃; 𝑢, 𝑣)
𝑢,𝑣∈𝑉
全訪問時間（cover time）
𝐶𝐺 𝑃; 𝑢 :頂点𝑢から始まるランダムウォークが
𝐺のすべての頂点を訪れるために必要な遷移数の期待値
𝐶𝐺 𝑃 = max 𝐶𝐺 (𝑃; 𝑢)
𝑢∈𝑉
2015/10/1
4
単純ランダムウォーク
1/3
½
1
2
1/3
1/3
½
½
3
1
½ 4
 0 1/ 2 0 1/ 2


1 / 3 0 1 / 3 1 / 3 
P
0
1
0
0 


1 / 2 1 / 2 0

0


G
𝐻𝐺 𝑃 = 𝑂 𝑛3 , 𝐶𝐺 𝑃 = 𝑂(𝑛3 )
2015/10/1
※nは頂点数
5
定常分布
遷移行列𝑃に対して
𝜋𝑃 = 𝜋
を満たす頂点上の確率分布
𝜋 = (𝜋1 , 𝜋2 , … , 𝜋𝑛 )を𝑃の
定常分布という
2015/10/1
6
メトロポリスウォーク
• Metropolis-Hastings法に基づく
-Markov Chain Monte Carlo(MCMC)の手法
-𝜋（定常分布）を任意に設定可能
-隣接頂点の情報を利用
1
𝑑𝑢 𝜋 𝑣
min
,1
𝑑𝑢
𝑑𝑣 𝜋 𝑢
𝑝𝑢𝑣 =
1−
𝑝𝑢𝑤
𝑣∈𝑁 𝑢 ,
𝑑𝑢 : 𝑢の次数
𝑁 𝑢 : 𝑢の隣接頂点の集合
𝑣 = 𝑢,
𝑤∈𝑁(𝑢)
0
2015/10/1
otherwise.
[W.K Hastings, 1970]
7
メトロポリスウォークの速さ
2
到達時間 : 𝑂 𝑓𝑛
2
全訪問時間 : 𝑂 𝑓𝑛 log 𝑛
ただし,
𝑓 = max 𝜋𝑢 / 𝜋𝑣
𝑢,𝑣∈𝑉
[Y.Nonaka, 2009]
※nは頂点数
• 単純ランダムウォークは
𝐻𝐺 𝑃 = 𝑂(𝑛3 ), 𝐶𝐺 𝑃 = 𝑂(𝑛3 )
2015/10/1
8
今後の課題
1
𝑑𝑢 𝜋𝑣
min
,1
𝑑𝑢
𝑑𝑣 𝜋𝑢
𝑝𝑢𝑣 =
1−
𝑝𝑢𝑤
𝑣∈𝑁 𝑢 ,
𝑣 = 𝑢,
𝑤∈𝑁(𝑢)
0
otherwise.
• 自己ループを取り除いた新しいランダム
ウォークを提案し,既存のメトロポリスウォーク
に比べてどの程度速くなるか明らかにする
2015/10/1
9
単純ランダムウォークのタイトな例
Lollipopグラフ
2015/10/1
10
メトロ解析ポリスウォークのタイトな例
Glitter starグラフ
2015/10/1
11

Download Report