P4-21 ネットワーク上の経路に対する 回帰問題について

Presentation on theme: "P4-21 ネットワーク上の経路に対する 回帰問題について"— Presentation transcript:

1 P4-21 ネットワーク上の経路に対する 回帰問題について
井手 剛 IBM東京基礎研究所 本研究の一部は、総務省の地球温暖化対策ICTイノベーション推進事業(PREDICT)の助成により行われました．

2 問題設定: ネットワーク上の任意の経路について「コスト」を予測すること
入力: ネットワーク上の任意の経路 ネットワーク上の隣接するリンクIDの系列 出力: その経路のコスト スカラー値。所要時間などを想定。 訓練データ: x(n) : n-th trajectory (or path) y(n) : n-th cost origin destination arbitrary path Cost regression function link ID defined in digital maps 2010/11/04

3 想定するアプリケーションは交通関係 各リンクのコストは観測困難である GPSでは各リンクのコスト（所要時間など）を計測するのは難しい
つねにとびとびの点でしか計測できないため Brakatsoulas et al., "On map-matching vehicle tracking data," Proc. VLDB '05, pp 2010/11/04

4 2つの可能な定式化がある。 ここでは特徴ベクトルベースのアプローチを採用
Kernel-based [Idé-Kato 09] Use kernel matrix No need to use data matrix Feature-based Use data matrix No need to use kernel matrix 2010/11/04

5 個々のリンクのコストが推定できれば、経路のコストは容易に求まる
origin destination for all links included input path x cost of link e We use a particular parameterization like this: Default unit cost (known from e.g. legal speed limit) link length (known) cost deviation per unit length from the default (unknown) 2010/11/04

6 「渋滞の伝播」を念頭に、損失関数に制約を加えて最小化することにする
The objective function to be minimized “Predicted cost should be close to observed values” “Neighboring links should take similar values” S is the similarity matrix between links 2010/11/04

7 （参考） リンク同士の類似度の定義の例 d = (# of hops between edges)
In this case, d(e.e’)=2 e e’ 2010/11/04

8 これはラプラシアン正則化項を持つ一種のリッジ回帰になる
Graph Laplacian induced by the similarity Matrix Q can be interpreted as the “data matrix” Therefore, q-vectors can be interpreted as feature vectors これを解けばよい 2010/11/04

9 （参考）カーネル回帰の場合、経路同士のカーネルが定義されれば回帰式を書き下せる
カーネルリッジ回帰の公式 どうカーネル関数 k を選ぶかがキモ 2010/11/04

10 2つのアプローチの間の関係 カーネル関数の選択に非常に有用な知見が得られた
Kernel-based [Idé et al., SDM 09] Proposition [Idé-Yanagisawa, 10]: These two approaches are equivalent if the kernel matrix is chosen as Feature-based 2010/11/04

11 交通シミュレーションデータでの旅行時間予測の実験 実験の設定
ネットワークのデータ grid25x25 (25x25 square grid) 京都市街地図 経路-コストデータ Nagel-Schreckenberg モデルという交通流のモデルで生成 渋滞の発生を再現できるもっとも基本的なモデル 比較した手法 Legal: 法定速度を完全に守る Simple: （略） GPR: 文字列カーネルを使った正規過程回帰 Ours: 今回の手法 2010/11/04

12 交通シミュレーションデータでの旅行時間予測の実験 提案法がもっともよい結果
Simple GPR Ours Legal Grid25x25 Prediction actual travel-time Kyoto 2010/11/04