P4-21 ネットワーク上の経路に対する 回帰問題について 井手 剛 IBM東京基礎研究所 本研究の一部は、総務省の地球温暖化対策ICTイノベーション推進事業(PREDICT)の助成により行われました．
問題設定: ネットワーク上の任意の経路について「コスト」を予測すること 入力: ネットワーク上の任意の経路 ネットワーク上の隣接するリンク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
想定するアプリケーションは交通関係 各リンクのコストは観測困難である GPSでは各リンクのコスト（所要時間など）を計測するのは難しい つねにとびとびの点でしか計測できないため Brakatsoulas et al., "On map-matching vehicle tracking data," Proc. VLDB '05, pp.853--864 2010/11/04
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
個々のリンクのコストが推定できれば、経路のコストは容易に求まる 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
「渋滞の伝播」を念頭に、損失関数に制約を加えて最小化することにする 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
（参考） リンク同士の類似度の定義の例 d = (# of hops between edges) In this case, d(e.e’)=2 e e’ 2010/11/04
これはラプラシアン正則化項を持つ一種のリッジ回帰になる 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
（参考）カーネル回帰の場合、経路同士のカーネルが定義されれば回帰式を書き下せる カーネルリッジ回帰の公式 どうカーネル関数 k を選ぶかがキモ 2010/11/04
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
交通シミュレーションデータでの旅行時間予測の実験 実験の設定 ネットワークのデータ grid25x25 (25x25 square grid) 京都市街地図 経路-コストデータ Nagel-Schreckenberg モデルという交通流のモデルで生成 渋滞の発生を再現できるもっとも基本的なモデル 比較した手法 Legal: 法定速度を完全に守る Simple: （略） GPR: 文字列カーネルを使った正規過程回帰 Ours: 今回の手法 2010/11/04
交通シミュレーションデータでの旅行時間予測の実験 提案法がもっともよい結果 Simple GPR Ours Legal Grid25x25 Prediction actual travel-time Kyoto 2010/11/04