PaperlayerView exact revision on arXiv

Source-linked AI summary

Trajectory Anomaly Detection with Language Models

Jonathan Mbuya, Dieter Pfoser, Antonios Anastasopoulos

arXiv:2409.15366v1cs.LGcs.AI

TL;DR

Trajectory anomaly detection needs to identify deviations without labels while accounting for location-level and user-specific behavior. LM-TAD uses autoregressive causal attention over tokenized trajectories, and experiments report stronger user-contextual detection on PoL, competitive GPS-based performance on Porto, and lower online latency.

  • Problem

    Trajectory anomaly detection seeks to distinguish normal and anomalous trajectories without explicit labels, while prior methods struggle with user context and precise anomaly localization.

  • Method

    LM-TAD uses autoregressive causal attention to predict tokenized locations, optionally conditioning on user-specific tokens, with perplexity and surprisal rate for detection and localization.

  • Results

    LM-TAD vastly outperforms existing methods on user-contextual PoL anomalies, remains competitive on GPS-based Porto outliers, and reduces online latency through cached attention states.

  • Takeaways & Limitations

    The framework supports diverse trajectory representations and online anomaly detection across user-contextual and GPS-based settings.

  • Takeaways & Limitations

    On Porto-style anomalies, detecting trajectories with few anomalous locations remains challenging for whole-trajectory summary metrics, motivating local surprisal rate.

Abstract

from arXiv · show

This paper presents a novel approach for trajectory anomaly detection using an autoregressive causal-attention model, termed LM-TAD. This method leverages the similarities between language statements and trajectories, both of which consist of ordered elements requiring coherence through external rules and contextual variations. By treating trajectories as sequences of tokens, our model learns the probability distributions over trajectories, enabling the identification of anomalous locations with high precision. We incorporate user-specific tokens to account for individual behavior patterns, enhancing anomaly detection tailored to user context. Our experiments demonstrate the effectiveness of LM-TAD on both synthetic and real-world datasets. In particular, the model outperforms existing methods on the Pattern of Life (PoL) dataset by detecting user-contextual anomalies and achieves competitive results on the Porto taxi dataset, highlighting its adaptability and robustness. Additionally, we introduce the use of perplexity and surprisal rate metrics for detecting outliers and pinpointing specific anomalous locations within trajectories. The LM-TAD framework supports various trajectory representations, including GPS coordinates, staypoints, and activity types, proving its versatility in handling diverse trajectory data. Moreover, our approach is well-suited for online trajectory anomaly detection, significantly reducing computational latency by caching key-value states of the attention mechanism, thereby avoiding repeated computations.

1 INTRODUCTION

LM-TAD reframes trajectories as language-like sequences to detect anomalous locations and user-contextual deviations. It uses autoregressive prediction, perplexity, and surprisal rate across multiple trajectory representations.

  • The approach addresses prior difficulty pinpointing anomaly locations, inadequate user-context modeling, and limited support for qualitative or activity-based trajectories.The motivation includes anomalies involving visited place types, timing, and dwell duration, not only spatial deviation.
  • LM-TAD models trajectories with an autoregressive causal-attention model that predicts locations from historical context and flags low-probability locations as anomalies.A user token conditions generation on individual behavior, enabling user-specific anomaly detection.
  • Perplexity identifies outlier trajectories, while location-level surprisal rate localizes potential anomalies within trajectories.
  • The method performs exceptionally well on user-contextual anomalies in the Pattern of Life dataset and is on par with state-of-the-art methods on Porto GPS trajectories.
  • LM-TAD supports online detection by caching attention key-value states, avoiding repeated computations required by autoencoder-based scoring.

2 RELATED WORK

Prior trajectory anomaly detectors rely on handcrafted heuristics, labels, aggregate reconstruction scores, or limited user generalization. Language modeling offers a related sequence-modeling foundation, but earlier mobility applications had not used generative language models for trajectory anomaly detection.

  • 2.1 Trajectory Anomaly Detection: Heuristic methods use handcrafted frequency, distance, density, or edit-distance features, making them domain-specific and less transferable across geographic regions.
  • 2.1 Trajectory Anomaly Detection: Learning-based methods include RNN embeddings, mixture and adversarial models, autoencoders, and reinforcement learning, but often require labels or aggregate anomaly scores.Aggregate scores make it difficult to pinpoint the anomalous location within a trajectory.
  • 2.1 Trajectory Anomaly Detection: Existing learning-based approaches also have limited generalizability for user-specific anomaly identification because normal behavior differs across users.
  • 2.2 Language Modeling on Trajectory Data: Language modeling has been applied to mobility forecasting, next-location prediction, and trajectory analysis, but prior work had not used a generative approach for trajectory anomaly detection.

3 PROBLEM FORMULATION

The paper defines trajectories as chronological sequences of time-stamped locations and formulates unlabeled anomaly detection over collections that may contain both normal and anomalous trajectories. Locations can be represented spatially or semantically, including coordinates, staypoints, and functional areas.

  • A trajectory is a finite chronological sequence of visited locations represented as space-time points with increasing timestamps.Each point pairs a location l_i with a timestamp t_i.
  • Locations may be geographic coordinates, discretized grid cells, qualitative staypoints, or functional areas such as commercial, business, and residential regions.
  • A dataset is a collection of related trajectories that may contain normal and anomalous examples, with the goal of distinguishing them without explicit labels.
  • Figure 3 illustrates four location configurations: discretized GPS coordinates, staypoints, staypoints augmented with dwell time, and activities.

4 METHOD

LM-TAD models trajectories autoregressively, predicting each location from its history to assign probabilities and identify anomalous locations. Its transformer architecture supports multiple trajectory representations, while perplexity provides trajectory-level anomaly scores with user-specific thresholds.

  • 4 METHOD: LM-TAD learns trajectory probabilities with an autoregressive generative model and identifies anomalies as low-probability locations conditioned on historical context.The model can also identify exactly which locations within a trajectory are anomalous.
  • 4.1 Model and Architecture: A transformer architecture uses token and positional embeddings, causal multi-head attention, feedforward layers, and a softmax output to predict trajectory tokens.Causal masking prevents attention from accessing future locations, preserving the autoregressive setup.
  • 4.2 Location Configurations: LM-TAD can represent trajectories as GPS coordinates, staypoints, activities, and sequences augmented with metadata such as dwell time or transportation mode.This generative formulation allows the same framework to operate across different trajectory configurations.
  • 4.3 Anomaly Score: Perplexity measures trajectory-level uncertainty, with higher values indicating less predictable trajectories and a threshold used to flag anomalies.The threshold can be application- and dataset-dependent.
  • 4.3 Anomaly Score: User-specific anomaly detection computes the perplexity threshold from the mean and standard deviation of that user’s training trajectories.This customizes abnormality detection to individual behavior patterns.

5 EXPERIMENTS

The experiments evaluate LM-TAD on simulated Pattern-of-Life and real-world Porto taxi trajectories using unsupervised baselines and anomaly-detection metrics. The setup covers user-contextual evaluation, multiple trajectory representations, artificially generated Porto anomalies, and trajectory-level as well as location-level scoring.

  • 5.1.1 Pattern-of-Life Dataset (PoL).: The PoL dataset contains 444,634 daily trajectories from 1,000 simulated agents, with agent IDs and weekday information included to model individual behavior.Trajectories use activity locations and can also use discretized GPS coordinates or one-hour stay-duration buckets.
  • 5.1.1 Pattern-of-Life Dataset (PoL).: PoL anomalies involve ten agents whose first 450 days are normal and final 14 days are anomalous, including behaviors such as omitting a usual work visit.The model was trained on the full dataset, including those anomalous days.
  • 5.1.2 Porto Dataset.: The Porto dataset contains GPS trajectories from 442 taxis, discretized into 100m×100m grid cells and grouped by common source and destination.Each model input is bounded by SOT and EOT tokens, and groups with fewer than 25 trajectories are discarded.
  • 5.1.2 Porto Dataset.: Because Porto lacks ground-truth anomaly labels, the study generates random-shift and detour anomalies by perturbing or diverting portions of trajectories.Artificial anomalies are excluded from training for Porto experiments.
  • 5.2 Baselines: LM-TAD is evaluated against SAE, VSAE, and GM-VSAE using Precision-Recall AUC and F1 scores, with surprisal rate locating anomalies within trajectories.PoL results are computed per virtual agent, whereas Porto metrics are computed across all trajectories.

6 RESULTS

LM-TAD improves trajectory anomaly detection across user-specific, global, local, multimodal, and online settings by modeling location probabilities with contextual autoregressive attention. Results show strongest gains on user-contextual PoL anomalies, competitive Porto performance, location-level surprisal detection, adaptable representations, and lower-latency partial-trajectory scoring.

  • 6.1 Agent-based Outliers - Patterns-of-Life Data: LM-TAD outperforms all competitor methods on user-contextual PoL anomalies, where trajectories are evaluated for ten agents with anomalous behavior.The method attributes higher perplexity to anomalous trajectories than to normal ones, unlike the competing approaches.
  • 6.2 Global Outliers - Porto Taxi Data: On Porto taxi data, LM-TAD outperforms SAE and VSAE, matches GM-SVAE for random shifts, and trails GM-SVAE especially for short detours.Random shifts break continuity with location history, whereas short continuous detours can be diluted by aggregate perplexity.
  • 6.3 Identifying Anomalies using Surprisal Rate: Surprisal rate identifies potentially anomalous locations that aggregate perplexity cannot pinpoint, with high rates concentrated at selected trajectory tokens.In PoL trajectories, anomalous tokens show especially high surprisal near the beginning when an agent visits an unusual first location for a weekday.
  • 6.4 Location Configurations - Ablation Study: Staypoint labels provide the best overall PoL anomaly-detection performance among the tested location configurations.The ablation compares discretized GPS coordinates, staypoint labels, and stay duration, showing that the representation suits different anomaly types.
  • 6.5 Online Anomaly Detection: LM-TAD supports online anomaly detection from partial trajectories without requiring the full trip or destination, while caching attention states to reduce repeated computation.The method computes scores whenever a new location is sampled, lowering latency relative to recomputing an entire sub-trajectory.
  • 6.5 Online Anomaly Detection: For online Porto detection, LM-TAD performs on par with the best baseline; 40% of a sub-trajectory detects most random-shift anomalies, while short detours remain difficult.Detours become evident only after observing the destination or a large portion of the trajectory.

7 CONCLUSIONS

LM-TAD combines autoregressive causal attention, user-specific tokens, and trajectory-language modeling to support context-aware anomaly detection. Experiments show strong performance on user-contextual anomalies, competitive GPS outlier detection, versatile trajectory representations, and efficient online detection.

  • User-specific tokens enhance detection of context-specific anomalies by accounting for variability in individual behavior patterns.
  • LM-TAD vastly outperforms existing state-of-the-art methods on user-contextual anomalies and remains competitive for GPS-based trajectory outliers across the PoL and Porto taxi datasets.The results support robustness and adaptability across synthetic Pattern-of-Life and real-world Porto taxi data.
  • Perplexity detects trajectory outliers, while surprisal rate localizes anomalous locations within trajectories.Together, these metrics broaden the approach from trajectory-level detection to anomaly localization.
  • LM-TAD supports diverse trajectory representations, including GPS coordinates, staypoints, and activity types.
  • Online detection reduces computational latency and avoids expensive recomputation, enabling real-time anomaly detection.
  • The framework is presented as a scalable, context-aware, and computationally efficient solution for user-centric and real-time trajectory analysis.
Loading 2409.15366v1…