講演資料

杉山麿人（大阪大学）
• 主な研究テーマ：統計的に有意に現れるパターン
（部分グラフなど）を効率的に発見する
Positive
– 多重検定補正によって偽陽性の割合を適切に制御する
– SDM 15, KDD 15, ISMB/ECCB 15
Discriminative
Subgraph
Negative
Support: (4, 0)
Support: (0, 2)
1/2
ランダムウォークグラフカーネルの
停止に関する解析
M. Sugiyama. (Osaka Univ.), K. Borgwardt. (ETH Zürich):
Halting in Random Walk Kernels, NIPS 2015.
′
グラフ G と G の間の k ステップランダムウォークカーネル
k
∣V× ∣
′
k
l
K× (G, G ) = ∑ [∑ λ l A× ]
i , j=1 l =0
(λ l > 0)
ij
は幾何ランダムウォークカーネル
′
∣V× ∣
∞
K GR (G, G ) = ∑ [∑ λ
i , j=1 l =0
l
∣V× ∣
l
A× ]
−1
= ∑ [(I − λA× ) ] i j
ij
i , j=1
よりもベースラインに適している
2/2
Regret-Minimizing
Representative Paths
in Multi-Criteria Networks
秋葉拓哉 (NII)，吉⽥悠⼀ (NII)
1
Multi-CriteriaNetwork とは？
Single-CriteriaNetwork(普通の重み付きグラフ)
▶ コストが 1次元
Multi-CriteriaNetwork(本研究で扱うグラフ)
'
▶ コストが 𝑑 次元ベクトル 𝑐 𝑒 ∈ 𝑅&
'
▶ 各個⼈の好みもベクトル 𝑤 ∈ 𝑅&
▶ 各個⼈にとってのコストは内積 𝑤 ⋅ 𝑐 𝑒
例：コスト＝(時間，⾦額，距離，景⾊ )
「最短経路」が⼈によって違う！
2
Multi-CriteriaNetworkの最短経路研究
既存①：CustomizableRoutePlanning
好みベクトルを知っている仮定
→しかし，好みはどうやって知るのか？
既存②：SkylinePathEnumeration
最適になり得るパスを全列挙
→指数的な個数，多すぎ
提案：Regret-minimizingRepresentativePaths
好み知らない状況下
少数を提⽰し多くの⼈を満⾜させる
3
Top-𝒌 ShortestPaths& SkylinePaths
1.Top-KShortestPaths
(k=4)
2.SkylinePaths
(144本)
4
Regret-MinimizingPaths(提案⼿法)
(k=4)
5
Regret-MinimizingPaths(提案⼿法)
モデル
MaximumRegretRatio[Nanongkai+,VLDB’10]を
Multi-CriteriaNetwork上の経路に持ってくる
▶ Regret ≔ min 𝑤 ⋅ 𝑐 𝑝 − min 𝑤 ⋅ 𝑐(𝑞)
/∈0
3∈4
▶ RegretRatio≔ =>?89:;9<
B⋅C /
@∈A
=>? B⋅C(3)
= 1 − G∈H
=>? B⋅C /
@∈H
▶ MaximumRegretRatio:= maxM
B∈KL
1−
=>? B⋅C 3
G∈H
=>? B⋅C /
@∈A
アルゴリズム
▶ Ramer-Douglas-Peucker Algorithmに基づく貪欲法
▶ 幾何的構造を活⽤した FPTアルゴリズム
▶ A*探索との組み合わせによる⾼速化
6

Download Report