Nonstationary Temporal Matrix Factorization for Multivariate Time Series Forecasting

Xinyu Chen, Chengyuan Zhang, Xi-Le Zhao, Nicolas Saunier, Lijun SunarXiv 2022 · arXiv · OpenReview

TL;DR

This paper introduces NoTMF, a novel model for forecasting traffic speeds in urban road networks. It tackles the challenges of high-dimensional, sparse, and nonstationary data by combining matrix factorization with a differenced Vector Autoregression (VAR) model, achieving superior accuracy compared to existing methods.

What Problem Does This Paper Address?

Urban road networks generate massive amounts of data, often from sources like ridesharing vehicles. This data, representing movement speeds, is inherently problematic for analysis and forecasting due to several key issues:

  • High-dimensionality: Road networks are vast, leading to a huge number of individual road segments (features).
  • Sparsity/Incompleteness: Ridesharing vehicles only cover a fraction of the road network at any given time, resulting in many missing speed observations. This is particularly true during off-peak hours or at night.
  • Nonstationarity: Traffic patterns are not constant; they exhibit daily, weekly, and seasonal variations (seasonality) and also change over time (trends). Traditional forecasting models often assume stationarity, which is violated here.

These challenges make it difficult to accurately estimate and predict traffic flow, which is crucial for urban planning, traffic management, and optimizing transportation systems. Existing methods struggle to effectively handle all these issues simultaneously.

Methods

The core innovation of this paper is the Nonstationary Temporal Matrix Factorization (NoTMF) model. It builds upon the idea of Temporal Matrix Factorization (TMF), which decomposes a data matrix into spatial and temporal components. Here's how NoTMF extends TMF:

  • Matrix Factorization: The sparse movement speed data matrix (Y) is approximated by the product of a spatial factor matrix (W) and a temporal factor matrix (X). This helps in reconstructing missing values by learning underlying low-dimensional patterns.
  • Nonstationary Temporal Modeling: The key novelty lies in how the temporal dynamics are modeled. Instead of assuming the temporal factors (X) are stationary, NoTMF applies seasonal differencing to them. This transforms the nonstationary temporal factors into stationary ones, making them suitable for modeling with a Vector Autoregression (VAR) process. This is crucial for capturing seasonality and trends.
  • Optimization: The model is trained using an alternating minimization framework. This means the variables (W, X, and the VAR coefficients A) are optimized iteratively. For the temporal factor matrix (X), a conjugate gradient method is employed, which is efficient for solving the complex subproblem involving both matrix factorization and the differenced VAR.

Datasets

The proposed NoTMF model was evaluated on two large-scale, real-world datasets:

  • NYC Uber Movement Speed Dataset: This dataset comprises hourly movement speed data from approximately 98,210 road segments over ten weeks in 2019. It exhibits a significant missing rate of around 66.56%.
  • Seattle Uber Movement Speed Dataset: This dataset includes hourly movement speed data from about 63,490 road segments over ten weeks in 2019, with an even higher missing rate of approximately 87.35%.

These datasets are characterized by their high dimensionality and sparsity, making them ideal for testing the robustness of the NoTMF model.

Key Insights and Ideas

  • Seasonality is Key: The paper strongly emphasizes that ignoring nonstationarity (especially seasonality) in traffic data leads to suboptimal forecasting. Applying seasonal differencing to the latent temporal factors is critical for accurate predictions.
  • Matrix Factorization + Differenced VAR = Power: Combining the ability of matrix factorization to handle sparsity with a differenced VAR model for temporal dynamics creates a powerful framework for complex spatiotemporal data.
  • Efficient Solvability: The development of an alternating minimization framework with conjugate gradient for optimization makes the NoTMF model scalable and applicable to large real-world datasets.
  • Data Bias Mitigation: The differencing approach helps mitigate biases introduced by varying missing rates across different road segments or time periods.

Key Results

The experiments demonstrated that NoTMF significantly outperforms several baseline models, including TRMF, BTMF, BTRMF, and CTNNM, across various forecasting horizons.

  • Superior Accuracy: NoTMF consistently achieved lower MAPE/RMSE values on both the NYC and Seattle datasets. For instance, on the NYC dataset with a forecasting horizon of δ=1 and order d=6, NoTMF achieved a MAPE of 13.39/2.83 (for m=168) compared to TRMF's 14.00/2.98.
  • Benefit of Differencing: The results clearly show that NoTMF with seasonal differencing significantly improves accuracy over models that do not account for nonstationarity.
  • Seasonality Matters: Both daily (m=24) and weekly (m=168) differencing were tested, with weekly differencing generally showing superior performance, highlighting the importance of capturing longer-term seasonal patterns.
  • Robustness to Sparsity: The model's ability to handle datasets with very high missing rates (up to 90% at certain times) is a key strength.

Limitations and Future Work

  • Linear Temporal Dynamics: The current NoTMF model assumes linear temporal dynamics in the latent space. The authors suggest that future work could explore integrating nonlinear functions or deep learning approaches to capture more complex temporal dynamics, potentially further enhancing forecasting accuracy.
  • Computational Cost: While the conjugate gradient method improves efficiency, applying NoTMF to extremely large datasets might still be computationally intensive.
  • Hyperparameter Tuning: While the paper outlines a method for setting hyperparameters, finding optimal values can still be a challenge.

The paper concludes by highlighting the potential for future research in incorporating nonlinear temporal dependencies, which could lead to even more powerful forecasting models for urban traffic data and other spatiotemporal time series.

Summary updated

Abstract

Modern time series datasets are often high-dimensional, incomplete/sparse, and nonstationary. These properties hinder the development of scalable and efficient solutions for time series forecasting and analysis. To address these challenges, we propose a Nonstationary Temporal Matrix Factorization (NoTMF) model, in which matrix factorization is used to reconstruct the whole time series matrix and vector autoregressive (VAR) process is imposed on a properly differenced copy of the temporal factor matrix. This approach not only preserves the low-rank property of the data but also offers consistent temporal dynamics. The learning process of NoTMF involves the optimization of two factor matrices and a collection of VAR coefficient matrices. To efficiently solve the optimization problem, we derive an alternating minimization framework, in which subproblems are solved using conjugate gradient and least squares methods. In particular, the use of conjugate gradient method offers an efficient routine and allows us to apply NoTMF on large-scale problems. Through extensive experiments on Uber movement speed dataset, we demonstrate the superior accuracy and effectiveness of NoTMF over other baseline models. Our results also confirm the importance of addressing the nonstationarity of real-world time series data such as spatiotemporal traffic flow/speed.
BibTeX
@misc{chen2022nonstationary,
  author = {Xinyu Chen and Chengyuan Zhang and Xi-Le Zhao and Nicolas Saunier and Lijun Sun},
  title = {{Nonstationary Temporal Matrix Factorization for Multivariate Time Series Forecasting}},
  year = {2022},
  eprint = {2203.10651},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2203.10651},
}

Loading related content...

Figure