Computing Trajectory Similarity in Linear Time: A Generic Seed-Guided Neural Metric Learning Approach

どんなもの？

軌跡の類似性計算を高速化するためにNEUTRAJを提案

先行研究と比べてどこがすごい?

NEUTRAJは、既存のあらゆる軌跡指標に対応する汎用性を持ち、与えられた軌跡ペアの類似性を線形時間で高速に計算する。さらに、 NEUTRAJは、空間ベースの軌跡インデックス作成手法と連携して、検索空間を縮小する

技術や手法のキモはどこ？

SAMの適用，アテンション機構により効率的に軌道データの特徴を表現

どうやって有効だと検証した？

portoと北京での軌道データでSOTA

議論はある？

マルチトラジェクトリーへの拡張

次に読むべき論文は？

マルチトラジェクトリーの軌道検索タスク

Memo

線形時間での軌跡類似度計算：一般的なシードガイド付きニューラルメトリック学習アプローチ

概要-軌跡類似度計算は、軌跡データ解析における様々なアプリケーションのための基本的な問題である。しかし、既存の軌跡類似性測定の計算コストが高いことが、大規模な軌跡解析における重要なボトルネックとなっている。複雑さを軽減するための研究は数多く行われているが、それらは1つの類似尺度に特化したものであり、限定的な高速化をもたらすことが多い。我々は、軌跡の類似性計算を高速化するためにNEUTRAJを提案する。NEUTRAJは、既存のあらゆる軌跡指標に対応する汎用性を持ち、与えられた軌跡ペアの類似性を線形時間で高速に計算する。さらに、

NEUTRAJは、空間ベースの軌跡インデックス作成手法と連携して、検索空間を縮小することができる。 NEUTRAJは、与えられたデータベースから多数の種軌跡をサンプリングし、そのペアごとの類似性をガイダンスとして用いて、ニューラル・メトリック学習フレームワークにより類似性関数を近似する。

NEUTRAJは、類似関数の正確な近似を実現するために、次の2つの新しいモジュールを備えている：（1）軌跡符号化のための既存のリカレントニューラルネットワークを補強する空間Attention記憶モジュール； (2)シードベースのガイダンスからの情報を効果的に転写する距離加重ランキング損失。これら2つのモジュールにより、NEUTRAJは、訓練データが少ない場合でも、高い精度と速い収束率を得ることができる。 2つの実データセットを用いた実験により、NEUTRAJはFrechet、´Hausdorff、ERP、DTW測定において80%以上の精度を達成し、常に最新のベースラインを大幅に上回ることが示された。また、より正確な類似関数の近似を得ることができ、ブルートフォース法に対して50x1000x、既存の近似アルゴリズムに対して3x-500xのスピードアップを実現している。索引用語-深層メトリクス学習、軌跡の類似性、線形時間

2つの軌跡の類似性を計算することは、軌跡解析のための多くの検索やマイニングタスクの基本であるプリミティブである。軌跡間の本質的な構造的類似性を捉えるために、Dynamic Time Warping(DTW) [31], Hausdorff distance [3], Frechet distance [2], Edit distance ´ with Real Penalty(ERP) [9] などの様々な尺度が提案されてきた。これらの類似性尺度は、異常検知 [18]、重複検知 [27]、軌跡クラスタリング [6] などのタスクで重要な役割を担ってきた。しかし、残念ながら、既存の軌跡類似尺度は計算コストが高いため、大規模な軌跡解析のデファクトボトルネックとなっています。2つの軌跡の類似性を計算するために、既存の手法では、2つの軌跡のポイントを整列させ、整列したすべてのペアの情報を蓄積し、最後に距離を算出する必要があります。このようなプロセスは、2次関数的、あるいは超2次関数的な時間複雑性をもたらし、多くの軌跡マイニングアルゴリズムが大規模なデータセットに対応することを制限しています。例えば、約8000個の人間のGPS軌跡のペアワイズHausdorff距離を計算するのに、ハイエンドサーバーで6.5時間以上かかっています。このように、様々な場面で膨大な軌跡データが収集される中、様々な手法で軌跡の類似性を高速に計算することが急務となってきています。

高速な軌跡類似性計算の難しさは、2つあります。第一は、軌跡類似性計算の複雑な性質である。入力された軌跡のペアは全く異なる長さを持っている可能性があり、2つの軌跡の最良のアライメントは、頭から尻尾までの正確なマッチングではなく、柔軟なシフトとスケーリングに左右されます。そのため、既存の技術の多くは、最適なマッチングを決定するためにスキャンアンドアライン機構を採用しなければならず、マッチングプロセスを分離して時間コストを削減することは困難である。2つ目は、異なる類似性尺度による差異です。一般的な軌跡測定法（DTW、Hausdorff、Frechetなど）は、その定義や計算メカニズムに大きな違いがあります´。既存のすべての軌跡測定に対応する汎用的な高速化戦略を設計することは困難である。

これまでにも、様々なタスクで軌跡の類似性計算を高速化するための研究が行われてきました。このような取り組みは、一般的に2つの系統に分類することができる。まず、[10]、[14]、[15]、[30]は、グローバルなレベルでの計算回数を減らすことです。しかし、この系統の技術は、専らトップk類似性検索タスクのために設計されたものである。これらの技術は、その場限りの軌跡のペアに対する計算量を減らすのではなく、与えられた軌跡データベースに対する索引付けと刈り込み戦略を設計し、top-k類似性検索の計算量を減らすことに焦点を合わせている。そのため、軌跡のクラスタリングや異常検知など、すべての軌跡ペアの距離を必要とするタスクに適用することはできない。第二の方法は、近似アルゴリズムを用いて軌跡の類似性計算の時間複雑性を直接的に低減することを目的とするものである。Frechet距離やDTW距離のローカライズハッシュ（LSH）[12]など、異なる尺度に対して異なる戦略が提案されている。残念ながら、これらの手法はある特定の距離尺度のために設計されたものであり、他の尺度には適用できない。我々は、どのような尺度に対しても軌跡の類似性計算を劇的に高速化するモデルを提案する。提案するモデルはNEUTRAJと名付けられ、ニューラルメトリック学習に基づく近似的なアプローチである。NEUTRAJは、データベースから種となる軌跡のプールをサンプリングし、それらのペアワイズ類似度をガイダンスとして利用する。具体的には、NEUTRAJは、入力軌跡を埋め込み、距離関数を近似するニューラルネットワークを共同で学習する。NEUTRAJは、以下のような魅力的な特徴を持つ：

汎用的であること： NEUTRAJは、ある軌跡の類似性指標に特化した従来の手法とは異なり、既存のあらゆる指標をサポートする汎用性を持っている。そのため、ほとんどの軌跡マイニングタスクの高速化に利用できる。
高速である： NEUTRAJは、アドホックな軌跡のペアが与えられた場合、その類似性をO(L)時間で計算することができます（Lはペアの長さの合計）。実際には、正確なブルートフォース計算よりも少なくとも50倍速いことが確認された。
正確である： NEUTRAJは、実際に優れた近似性能を達成した。2つの実際の軌跡データセットにおいて、NEUTRAJは、Frechet、Hausdorff、DTW、ERPのトップ10類似軌跡探索タスクにおいて、80%以上のヒット率と50m未満の平均エラー距離を達成した。一方、最先端の軌跡類似性近似手法と比較して、2倍以上のヒット率を獲得している[12]。
弾力性：NEUTRAJは空間情報を失うことなく軌跡を埋め込むため、他の索引付けや刈り込み戦略による拡張に弾力的である。すべてのペアの類似性が必須ではないタスクでは、NEUTRAJは既存のインデックス作成方法[10], [15], [30]と連携して計算空間を削減することができる。

NEUTRAJの中核は、リカレントニューラルネットワーク（RNN）を使用して軌跡の埋め込みを生成するDeepメトリクス学習フレームワークである。データベースから種となる軌跡のプールをサンプリングし、それらのペアワイズ類似性を計算する。計算された種子の類似性を指針として、種子の類似性に適合するようにネットワークを最適化するために、ペアワイズロスを設計する。NEUTRAJは、ネットワークが類似性関数を正確に近似するように促す、次の2つの新規モジュールを備えています：（1）空間的注意メモリ（SAM）。バニラRNNとその既存の亜種（GRU、LSTM）は、配列間の相関を考慮せずに1つの配列だけをモデル化することができます。私たちの設計したSAMユニットは、アテンションメカニズムによって過去に処理した軌跡の情報を記憶し、より良い軌跡埋め込みを生成するために、トレーニング軌跡間の相関を捕捉します。(2) 距離重み付けによる順位損失種軌跡を利用することの難しさの一つに、効率と効果のジレンマがある。一方、ネットワークを十分に訓練するためには、すべての軌跡のペアに対して反復処理を行うことが望ましい。しかし、すべての軌跡のペアを列挙することは、計算時間がかかる。このジレンマに対処するため、我々は、より識別性の高い訓練ペアに焦点を当てる、距離加重サンプリング戦略を提案する。重み付きサンプリング戦略とともに、距離重み付きランキングロスは、種からのガイダンスに適合するようにネットワークのパラメータを学習するランキングロスである。これら2つの新規モジュールにより、NEUTRAJは、訓練データが少ない場合でも、高い精度と速い収束率を得ることができる。

異なる尺度の下での軌跡類似度計算を高速化するためのニューラルメトリック学習法を提案する。我々の知る限り、NEUTRAJは汎用的な軌跡類似性尺度の高速化をサポートする最初の手法であり、多くのアプリケーションに広く適用可能である。
空間的に近い軌跡間の相関を、Attentionネットワークと外部メモリテンソルに基づきモデル化する空間Attentionメモリユニットを提案する。
種の軌跡の力を十分に引き出す、重み付けサンプリングと学習モジュールを設計する。既存のアーキテクチャと比較して、本学習モジュールは、より速い収束率と高い精度を実現する。
2つの実軌跡データセットと4つの一般的な軌跡類似性尺度で大規模な実験を行った。その結果、提案モデルは、精度と効率の両方において、常に最先端のベースラインを上回ることが実証された。

A. 実験設定

データセット：我々の実験は、2つの都市の2つの公開された軌跡データセットに基づいている：北京とポルトである。最初のデータセット[33]は、Geolifeと呼ばれ、2007年から2010年までの人間の移動の17,621の軌跡で構成されている。2つ目のデータセット[23]は、2013年から2014年までの170万件以上のタクシーの軌跡から構成されている。Mの次元を緩やかにするために、都市の中心エリアの軌跡を選び、そのエリアを50m×50mのグリッドセルに離散化する。そして、10件未満の軌跡を削除する。このようにして、Geolifeでは8203件、Porto1では601,071件の軌跡を得ることができた。
実験プロトコル NEUTRAJの性能を評価するために、GeolifeとPortoの両データセットでトップk類似性検索問題を行い、Frechet距離、Hausdorff´距離、Edit distance with Real Plenty（ERP）、Dynamic Time Warping（DTW）という4つの距離尺度でNEUTRAJを評価した。最初の3つはメトリクス、すなわち距離が対称で三角形の不等式を満たすものである。したがって、我々はメトリクスを直接近似するモデルを学習する。しかし、DTW距離はメトリクスではありません。DTWに関する実験では、非メトリクスの類似性尺度に対するNEUTRAJの性能を探る。

この問題のグランドトゥルースは、正確な類似度に基づく正確なトップk結果である。Geolifeでは、すべての軌跡ペアの正確な類似度を計算し、NEUTRAJを訓練するための種として20%の軌跡をランダムに選択する。さらに、10%の軌跡はパラメータのチューニングに、70%の軌跡はテストに使用されます。Protoの場合、軌跡が膨大であるため、すべての軌跡ペアの正確な類似度を直接計算することは非現実的である。そこで、10k個の軌跡をランダムに選んで類似度を計算し、Geolifeと同じように実験プロトコルに従います。トップk類似度検索の性能比較、効率調査、パラメータ感度調査をVII-B VII-CとVII-Dに示す。さらに、10k Proto軌跡に対するよく訓練されたモデルに基づいて、大規模データセットに対するNEUTRAJの効率と精度を示すために、Protoデータセット全体のケーススタディ（VII-Eに報告）を実施する。

NEUTRAJのペアワイズ類似度計算の有効性を評価するために、両データセットで軌跡のクラスタリング実験を行い、正確な類似度と埋め込みベースの類似度とのクラスタ結果の違いを比較する。Portoからランダムに10k個の軌跡をサンプリングし、グランドトゥルースとして正確なペアワイズ類似度を計算する。空間データに対して最も広く使われている密度ベースのクラスタリングアルゴリズムであるDBSCANを利用してクラスタリング結果を得、4つのクラスタリングメトリクスの下でその違いを評価する：均質性、完全性、V-measure、Adjusted Random Indexの4つのクラスタリング指標でその違いを評価する。軌跡のクラスタリング結果をVII-Fに示す。また、利用可能な軌跡がなく、道路ネットワークしかない都市で、NEUTRAJがうまく機能するかどうかをテストするために、ゼロショット学習タスクを実施した。北京の道路網[32]に基づいて、6000個の合成軌跡を訓練用の種としてシミュレートし、Geolifeの実際の軌跡を使ってNEUTRAJをテストした。ゼロショート学習の結果は、VII-Gに示す。

比較した方法 NEUTRAJと4つのベースラインとの比較を行ったが、これらは大きく3つのカテゴリーに分けられる：

近似アルゴリズム：近似アルゴリズム：近似アルゴリズムを持たないERPを除き、3つの尺度はそれぞれ高速に計算するためのいくつかの近似アルゴリズムを持っている。我々は、Frechet距離とDTW´距離の計算に使用される[12]と、Hausdorff距離に使用される[4]の最新鋭の近似アルゴリズムと比較している。我々は、これらのアルゴリズムを、すべての距離尺度で一般的にAPと呼ぶ。- シャムネットワーク[24]：このカテゴリは、シャムネットワークに基づくメトリクス学習アプローチである。LSTMをバックボーンに持つシャムネットワークをインスタンス化し、Siameseと表記する。

アブレッション (1)NEUTRAJのウェイトサンプリングをランダムサンプリングに置き換え、距離重み付けランキングロスの有効性を検証する。この変法をそれぞれNT-NO-WSと表記する。(2) 提案する空間的なAttentionの記憶メカニズムの効果を検証するために、SAMユニットを標準的なLSTMに置き換え、NT-NO-SAMと表記する。

4）評価のメトリクス

性能評価には、3種類のメトリクスを用いる。1つ目はトップクラスのヒット率であり、トップクラスの結果とグランドトゥルースの重なり率を調べるものである。上位10件(HR@10)と上位50件(HR@50)の検索ヒット率を報告する。2つ目は、トップ10のグランドトゥルースに対するトップ50のリコール（R10@50）です。これは、異なる手法で作成されたトップ50リストによって、トップ10のグランドトゥルースの軌跡がどれだけ回収されたかを評価するものである。第3のメトリクスは、上位10位までの平均距離の歪みであり、δH10とδR10と表記される。δH10は結果の上位10個の軌跡に基づいて計算され、δR10は上位50個の結果の上位10個の最も類似した軌跡に基づいて計算される。これらは、クエリの軌跡と検索結果のトップ10との間の平均正確距離の歪みを測定する。距離が小さいほど、その手法の性能が高いことを意味する。

パラメーターの設定 NEUTRAJの主要なパラメータは以下の通りである： (1) 埋め込み次元 d； (2) Attention Memory Readerのスキャン幅w。我々は、dを{16, 32, 64, 128, 256}の範囲でグリッドサーチによりチューニングした。一般に、dが大きくなるにつれて性能は向上し、十分な大きさになると徐々に安定する。wについては、{0, 1, 2, 3, 4}の範囲で調整し、両方のデータセットでw = 2として最適値を持つことを発見した。さらに，バッチサイズを20，サンプリングサイズnを10とした．比較した手法については、我々のデータセットで最高の性能を得るためにパラメータを調整した。また，セクションVII-Dでパラメータ調査の結果も報告する．

B. 性能比較

表IIは、トップk類似性検索タスクに対する異なる手法の性能を示している。示されるように、両データセットにおいて、NEUTRAJはほとんどのメトリクスにおいて、すべてのベースライン手法を大幅に上回る。Frechet距離を例とする。NEUTRAJは、最新の近似アルゴリズム（AP）と比較して、ヒット率が2倍以上、R10@50が約70%、平均距離が約69%減少していることがわかります。このような大きな改善は、NEUTRAJが手作業のヒューリスティックに頼らず、種の軌跡から類似性関数を自動的に学習していることを考えると、印象的である。シャムネットワークに対するNEUTRAJの優位性は、4つのメトリクスすべてにおいて明らかである。両手法とも類似関数を近似するためにニューラルメトリック学習を採用しているが、NEUTRAJはシャムネットワークに対して2つの利点がある。第一に、加重サンプリングとランキングロスは、シャムネットワークと比較して、より区別できる軌跡と訓練ロスを得ることができる。第二に、空間Attentionメモリモジュールは、空間的に近い軌跡間の相関をモデル化し、高品質の軌跡埋め込みを生成するために非常に有益である。を生成するのに非常に有効です。 4つの距離のうち、DTWの性能は他の3つの距離より劣っている。

その理由は、学習済み埋込みの距離がメトリクスであるのに対し、DTWはそうでないからである。この系統的な誤差により、NEUTRAJはDTWの性能を効果的に発揮することができない。

Frechet距離、Hausdorff距離、ERP距離、DTW距離に対する各手法の性能比較。注：HRはヒット率、R10@50はトップ10のグランドトゥルースに対するトップ50のリコール、δH10はトップ10の結果における平均距離の歪み、δR10はトップ50の結果におけるトップ10のリコールである。Frechet距離とHausdorff距離の平均距離のトップ10のグランドトゥルースは以下の通りである：平均距離の歪みは1044mと730m(Geolife)、935mと679m(Porto)、δH10/δR10の要素単位はメートルである。

アブレーション実験の結果を表IIIに示す。NEUTRAJとそのアブレーションを比較すると、NEUTRAJの2大モジュールの有効性をさらに確認することができます。引き続き、Geolifeデータセット´のFrechet距離を例として使用する。(1)SAMモジュールを搭載することで、NEUTRAJはNT-NO-WSのHR@10を0.46から0.47に改善、(2)重み付けサンプリングと最適化モジュールを搭載することで、NEUTRAJはNTNO-WSのHR@10を0.47から0.49に改善、という観測結果が出ています。この傾向は、Portoデータセットと他の3つの類似性尺度でも同様である。HR@10とHR@50の絶対値は、両データセットともあまり高くないようだ。その理由は、両データセットの軌跡には重複に近いインスタンスが多く存在するためである。このことは、グランドトゥルースと生成されたトップ10リストの両方について、空間的な近さを測定するδH10から観察することができる。

C. 効率性の研究このサブセクションでは、NEUTRAJの効率性を研究する。まず、オンライン類似性検索にかかる時間コストを報告し、次にNEUTRAJモデルの訓練にかかるオフライン時間コストを報告する。実験は、Inter Xeon E5 @2.20GHz CPUと1つのNvidia P100 GPUを搭載したマシンで実施した。

1）オンライン類似検索の時間コスト：インデックスを用いない類似性検索。表IVは、NEUTRAJが異なるサイズのトップk類似性検索を行う際の時間コストを示している。具体的には、Portoのテストセットから、それぞれ1K、5K、10K、200Kのサイズを持つ4つのサブコーパをランダムに抽出する。そして、NEUTRAJを用いて各軌跡のトップ50類似度検索を行い、50個の軌跡の正確な距離を計算することで再ランク付けを行う。表IVは、1つのクエリを処理するための平均時間コストを報告している。定義に従って正確な距離を直接計算するBruteForce法、最先端の近似アルゴリズム（AP）、およびニューラルネットワークに基づく方法（NTNO-SAM）と比較している。NT-NO-WS法、siamese法の結果は、オンライン検索手順において、NEUTRAJ法、NT-NO-SAM法と同様の時間コストがかかるため、省略した。表IVに示すように、4つの指標すべてにおいて、NEUTRAJはBruteForceに対して50倍〜1500倍、既存の近似アルゴリズムに対して2倍〜500倍のスピードアップを達成した。この高速化比率は、特に大規模データセットにおいて顕著である。アブレーション法NT-NOSAMの時間コストは、1つの探索軌道の埋め込み時間差が小さいため、NEUTRAJに非常に近い。

インデックスを用いた類似性探索この実験では、広く使われている2つのインデックス技術を採用している： 1) bounding box r-tree、2) grid based inverted indexの2つのインデックス技術を用い、NEUTRAJの弾性特性を調べるために200のクエリー軌跡をランダムに選択した。Frechet距離の下で、様々なサブコーパスを対象に、index-´拡張NEUTRAJと2つのベースライン（総当たり法、近似アルゴリズム）を比較した。平均時間コストは表Vに報告されている。NEUTRAJは2つのインデックス構造においてベースラインを上回り、近似アルゴリズムと比較して30倍以上のスピードアップを達成することがわかった。同様の傾向は他の指標でも観察される。

オフライントレーニングとエンベッディングの時間コスト：オフラインでのトレーニング時間。表VIは、Portoデータセットにおいて、他の類似性尺度に対するFrechet距離´の下でのオフライントレーニング時間の比較を示している。2,000の訓練軌道に対して、NEUTRAJは20エポック以内に収束する。NEUTRAJの1エポックの学習時間は約5分であり、したがってNEUTRAJの全学習時間は2時間未満である。一方、シャムネットワークは収束に60エポック以上かかり、NEUTRAJの約3倍の速度で収束する。また、図5でNEUTRAJとNT-NO-SAMの収束率を比較すると、NEUTRAJはNT-NO-SAMよりも収束率が高いが、これはSAMモジュールが処理した軌跡から有用な情報を取得するからである。

オフラインでのエンベッディング時間オフライン学習では、訓練されたモデルを用いて軌跡の埋め込みを行う埋め込み処理も行われる。本実験では、埋め込みバッチサイズを2000とし、200k個の軌跡を埋め込むのにかかる時間コストを報告します。すべての中立ネットワークベースの手法の結果を表VIに示す。SAMユニットベースの手法（NEUTRAJ、NT-NOWS）は、標準ユニットベースの手法（NTNO-SAM、siamese）より少し遅いことが容易に分かる。これは、SAMユニットがメモリテンソルの有用な情報を見つけるために、より多くの計算を必要とするためである。

D. パラメータ感度の検討本節では、NEUTRAJの感度を、学習データサイズ、スキャン幅w、埋め込み次元dの3つのパラメータで評価する。容量の都合上、Portoデータセットでの実験結果のみを示す。1) 訓練データサイズの感度まず、種軌跡の数がNEUTRAJの性能に与える影響を調査する。図6は、Portoの学習データサイズを500から8,000まで変化させたときの、NEUTRAJとそのアブレーションNT-NO-SAMの結果を4つの指標で示したものである。このように、NEUTRAJの性能は、2,000以上の訓練軌跡があるときに比較的安定するようになる。また、SAMベースのモデルがNT-NOSAMモデルよりも優れていることも確認された。もう一つの興味深い事実は、NEUTRAJは訓練データが疎な場合にNT-NO-SAMよりも頑健であることである。このように、訓練軌道の数が500しかない場合、NEUTRAJとNT-NO-SAMの性能差は特に大きくなる。これは、SAMがメモリテンソルを用いて、処理された軌跡から有用な情報を記憶しているためである。

埋め込み次元dの感度次に、埋め込み次元dがNEUTRAJの性能に与える影響について検討する。図7は、dを8から256まで変化させたときのHR@10を示したものである。このように、NEUTRAJとその亜種の性能は、まず上昇し、その後わずかに低下する。その理由は、パラメータdがNEUTRAJの複雑さを制御しているからである。dが大きくなると、モデルは軌跡の本質的な構造を捕らえるために、より多くの表現力を享受する。しかし、dが大きすぎると、学習データのサイズが限られているため、モデルはオーバーフィッティングに悩まされる。
スキャン幅wの感度：最後に、SAMモジュールのスキャン幅wは、過去の軌跡の探索の広がりを制御する重要なパラメータである。図8に示すように、wの増加に伴い、すべての手法のHR@10は、まず増加し、その後わずかに低下する。この現象は、(1)wが大きくなると、より多くの情報がSAMリーダーによってアクセスされる傾向があり、初期段階で現在の軌跡を符号化するのに有効である、(2)wが大きすぎると、いくつかの非関連軌跡の情報が必然的に組み込まれることになる、という二つの理由に起因していると思われる。NEUTRAJのAttentionメカニズムがこの影響を軽減するのに役立つとしても、モデルの性能は損なわれてしまう可能性がある。

III A. 問題定義軌跡データベースTと軌跡類似性関数f(-, -)を考慮する。各軌跡T∈Tは、移動する物体の軌跡を記録した点列である。軌跡の各サンプル点にはサンプリング時間があるが、我々は時間情報に関係なく、類似した形状を持つ軌跡を見つけることだけに焦点を当てる。一般性を損なうことなく、ここでは2次元の軌跡を考える。すなわち、各軌跡T = [Xc 1, ..., Xc t , ...] は、Xc t (xt, yt) がオブジェクトのt - th番目の位置であるタプルの列である。任意の2つの軌跡Ti, Tj∈T に対して、関数f(Ti, Tj )はTiとTjの間の類似性を測定する．ここで、f(-, -)はDTW類似度、Hausdorff距離、Frechet距離、´または他の軌跡類似度尺度となりうる。紙面の都合上、これらの尺度の詳細な定義については省略する。我々の問題は、Tからの軌跡のアドホックなペアについて、類似性関数f(-, -)の下で類似性を計算することである。しかし、一般的な類似性尺度では、一対の軌跡の類似性を計算するのに2次関数的な時間的複雑さが発生する。したがって、研究課題は、差｜f(T i, T j) - g(T i, T j)｜を最小化しながら、g(Ti, Tj )を計算するのにO(n)時間かかるように、近似類似関数g(-, -)をどのようにして学習できるのかということである。

NEUTRAJはニューラルネットワークによるメトリクス学習のフレームワークを採用している。NEUTRAJは、TからN個の軌跡を種Sとしてランダムにサンプリングし、Sに対して対称なN×Nの距離行列Dを計算する。そして、元の距離行列を正規化した類似性行列Sに変換する。行列Sをガイドとして活用し、さらに、任意の長の軌跡を低次元空間にマッピングしてそれらの類似性を捕らえるニューラルネットワークを学習する。より正式には、任意の2つの入力軌跡TiとTj (i, j∈[1, ..., N])に対して、NEUTRAJはそれらをそれぞれ2つのd次元ベクトルEiとEjに投影する。学習されたマッピングは類似性保持でなければならない。すなわち、f(Ti, Tj ) ≈ g(Ti, Tj ) ここで、g(-, -)は埋め込み空間におけるEiとEj間の類似性である。図1はNEUTRAJのアーキテクチャを示したものである。空間的アテンションメモリ（SAM）増強型RNNエンコーダとシードガイド付きメトリクス学習法の2つの主要部分から構成されている。

SAM増強型RNNエンコーダー。 NEUTRAJは、軌跡をモデル化するためにリカレントニューラルネットワーク（RNN）に依存し、RNNの最後のHidden Stateを埋め込みベクトルとする。しかし、前述のように、バニラRNNとその亜種（GRU、LSTM）は、各シーケンスの情報を独立して捕捉する。軌跡の類似性を計算するためには、軌跡間の相関が重要です。空間的に近い軌跡の情報を活用し、メトリクス学習プロセスを導くことが重要である。そこで、NEUTRAJでは、空間Attentionメモリモジュールを設計した。これは空間メモリテンソルを用いて、以前に処理された軌跡の空間情報を記憶するものである。このメモリテンソルは、ソフトアテンションメカニズムに基づく空間全体の読み書きを支え、以前に見た軌跡の情報を必要に応じて符号化したり取り出したりすることができる。

シードガイデッドニューラルメトリクス学習。 SAM拡張RNNに基づき、NEUTRAJは一対の軌跡を消費するためにシードガイド付きメトリクス学習アーキテクチャを構築し、類似性行列Sを近似するネットワークを学習する。既存のメトリクス学習法は、訓練ペアを生成するためにランダムサンプリングを採用しており、すべての軌跡が等しく重み付けされていることを意味する。しかし、軌跡のメトリクス学習では、軌跡間の空間的近接性を無視するため、この仮定は成立しない。本論文では、この問題を解決するために、距離加重サンプリング手法とランキング損失目的を開発する。従来のランダムサンプリングとは異なり、距離加重サンプリングは、種軌跡からより識別性の高い訓練ペアに焦点を当てる。加重サンプリング戦略では、各シード軌道Taはプール内の1つの類似リストT s aと1つの非類似リストT d aと関連付けられる。そして、ランキング損失は、類似性をSに適合させるためのネットワークのパラメータを学習し、類似および非類似のペアの両方においてランキング順位を保持する。

IV. サム拡張RNNエンコーダこのセクションでは、軌跡エンコーディングのために既存のRNNアーキテクチャを増強する空間Attention Memory（SAM）モジュールを導入するためのものである。以下では、まず、空間的な注意のメモリ構造を導入するためのものです。次に、既存のリカレントニューラルネットワークをSAMで補強する、空想的なRNNユニット、SAM-augmented LSTMを紹介します。最後に、SAM-augmented LSTMのメモリの読み取りと書き込みの操作について詳しく説明する。

A. グリッドベース・メモリテンソル（Grid-Based Memory Tensor SAMモジュールはグリッドベースのメモリネットワークである。前段階として、空間を小さなグリッドセルに分割する。ここで、Xg t = (xg t , yg t ) は t - th 位置のグリッドセルを指定します。図2は、提案するSAMモジュールのアーキテクチャを示したものである。メモリテンソルMは、空間内のすべてのグリッドセルのベクトル表現を格納し、過去に見た軌跡の情報を符号化・検索することができる。形式的には、空間全体がP×Q個のグリッドセルに分割されていると仮定すると、メモリテンソルの次元はRP×Q×dであり、dはリカレントユニットの隠れサイズである。M の各スライス (p, q, :) はセル (p, q) の埋め込みベクトルを格納し、全てのグリッドセルの埋め込みは学習前に 0 で初期化される。NEUTRAJは訓練データ中の軌跡を連続的に処理するので、メモリテンソルMは、処理された軌跡の情報をエンコードするために、メモリ増強されたリカレントユニットにより適宜更新される。

図2. 走査帯域幅w = 2の提案する空間アテンションメモリ(SAM)の説明図。各時間ステップにおいて、SAMは入力グリッドセルXg tと中間セル状態ˆtの2つを入力とする。読み手はまずメモリMを走査して、(2 ＊ 2 + 1)2 = 25個のグリッドセル埋め込みを得る。そして、attention cell state chis t を計算し出力する。赤線は、リカレントユニットのセル状態ctでMを更新する。

B. メモリ拡張RNNユニット SAMモジュールは、処理された軌跡から情報を記憶・検索することができる。我々は、標準的なRNNユニットを改良するためにこれを活用する。このように、RNNエンコーダーは、現在の軌道だけでなく、以前に処理された類似の軌道からも情報を取得する。以下では、SAM-augmented LSTMの詳細を説明する。

図4. 空間的な読み書きを説明するための例。T1〜T3は過去に処理された軌跡、Tは現在の処理軌跡、Xtは現在の処理入力である。T1 ∼ T3 を処理した後、g1 ∼ g8 のグリッドセル埋め込みはゼロでない値に更新される。空間リーダにより、NEUTRAJはXtの空間クローズグリッドセルをスキャンし、Tを符号化するためのグリッドのアテンションウェイトを算出する。その後のグリッドセル埋め込みを更新するためにXtのセル状態を用いる。