Temporal Regularized Matrix Factorization for High-dimensional Time Series Prediction

Hsiang-Fu Yu, Nikhil Rao, Inderjit S. DhillonNeurIPS 2016 · OpenReview

Overview

Temporal Regularized Matrix Factorization (TRMF) is a novel framework that combines the scalability of matrix factorization with the predictive power of classical time-series models. By learning autoregressive dependencies within a latent feature space, TRMF enables high-dimensional forecasting and missing-value imputation that is up to two orders of magnitude faster than traditional methods.

The Challenge of High-Dimensional Time Series

In fields like climatology and e-commerce, researchers often deal with "high-dimensional" time series—thousands of interdependent variables (like sensor readings or product demands) tracked over long periods. This presents two major hurdles:

  1. Scalability: Classical models like Autoregressive (AR) models or Kalman filters have computational costs that explode as the number of variables ($n$) increases. Their complexity is often $O(n^4)$ or $O(n^6)$, making them unusable for datasets with tens of thousands of items.
  2. Missing Data: Real-world data is inherently messy. Sensors fail, and products go out of stock. Traditional models struggle to handle these "holes" in the data without complex, potentially biasing preprocessing steps.

While existing Matrix Factorization (MF) techniques are excellent at handling missing data and scaling to large $n$, they typically ignore the temporal ordering of data or rely on rigid, pre-defined structures that fail to capture complex, data-driven dependencies.

The TRMF Framework

To bridge this gap, the authors introduce Temporal Regularized Matrix Factorization (TRMF). The core idea is to factorize the large, potentially sparse data matrix $Y$ into two smaller matrices: $F$ (spatial features of the items) and $X$ (latent temporal embeddings).

TRMF Matrix Factorization Setup

The primary innovation of TRMF is its Temporal Regularizer:

  • Latent AR Modeling: Instead of assuming a fixed relationship between time points, TRMF incorporates an Autoregressive (AR) model directly into the regularization of the temporal matrix $X$. It enforces that the latent state at time $t$ should be a linear combination of previous latent states.
  • Data-Driven Learning: Unlike previous methods that use fixed graphs to represent time, TRMF learns the dependency weights ($W$) automatically from the data.
  • Alternating Minimization: The model solves for $F$, $X$, and the temporal weights $W$ by cycling through them—optimizing one while holding the others fixed. This allows the use of highly efficient, off-the-shelf solvers.

Key Innovations

  • Forecasting via Latent Space: Because TRMF learns an AR model on the latent embeddings ($x_t$), it can project these embeddings into the future ($X_{new}$). By multiplying these future embeddings by the feature matrix $F$, the model produces non-trivial forecasts for all $n$ dimensions simultaneously ($Y_{new}$).
  • Beyond Graph Laplacians: The authors prove that their AR regularizer is a generalization of graph-based regularization. Crucially, it can account for negative correlations between time points, which standard graph-based methods (requiring non-negative edge weights) cannot handle.
  • Handling Seasonality: The framework allows for custom "lag sets." For example, to capture weekly seasonality in daily data, the model can be configured to look at lag 1 (yesterday) and lag 7 (the same day last week). These discontinuous lags can be tailored to specific domain knowledge.

Experimental Evaluation

The authors evaluated TRMF on a mix of synthetic and real-world high-dimensional datasets, including publicly available UCI datasets tracking electricity consumption (370 series) and road occupancy (963 series). They also tested on two proprietary Walmart e-commerce datasets containing weekly sales for ~1,500 items, which were particularly challenging due to having over 50% missing values from stock-outs.

Performance and Results

  • Speed and Scalability: TRMF is remarkably scalable. As shown in the scalability comparison, on a problem with 50,000 dimensions, TRMF was two orders of magnitude faster than competing AR or Dynamic Linear Models (DLM).
Scalability Comparison of TRMF vs. Baselines
  • Accuracy: In forecasting tasks, TRMF consistently outperformed standard Matrix Factorization, Temporal Collaborative Filtering (TCF), and classical AR models.
  • Robustness to Missingness: On the highly sparse Walmart datasets, TRMF provided significantly better forecasts and imputations than other methods. Learning the temporal structure simultaneously with the latent features helps "fill in" missing history much more accurately.

Limitations and Future Directions

While highly effective, the current AR regularizer assumes linear dependencies in the latent space, which might miss highly non-linear temporal patterns. Furthermore, while the authors provide theoretical guarantees for the model when the temporal weights ($W$) are fixed, establishing a full theoretical guarantee for the joint learning of $W$ and the embeddings remains an open challenge. Future extensions could adapt the framework to tensors for multi-way data or incorporate additional side information (like product descriptions or weather data) to further improve predictive accuracy.

Summary updated

Abstract

Time series prediction problems are becoming increasingly high-dimensional in modern applications, such as climatology and demand forecasting. For example, in the latter problem, the number of items for which demand needs to be forecast might be as large as 50,000. In addition, the data is generally noisy and full of missing values. Thus, modern applications require methods that are highly scalable, and can deal with noisy data in terms of corruptions or missing values. However, classical time series methods usually fall short of handling these issues. In this paper, we present a temporal regularized matrix factorization (TRMF) framework which supports data-driven temporal learning and forecasting. We develop novel regularization schemes and use scalable matrix factorization methods that are eminently suited for high-dimensional time series data that has many missing values. Our proposed TRMF is highly general, and subsumes many existing approaches for time series analysis. We make interesting connections to graph regularization methods in the context of learning the dependencies in an autoregressive framework. Experimental results show the superiority of TRMF in terms of scalability and prediction quality. In particular, TRMF is two orders of magnitude faster than other methods on a problem of dimension 50,000, and generates better forecasts on real-world datasets such as Wal-mart E-commerce datasets.
BibTeX
@inproceedings{yu2016temporal,
  author = {Hsiang-Fu Yu and Nikhil Rao and Inderjit S. Dhillon},
  title = {{Temporal Regularized Matrix Factorization for High-dimensional Time Series Prediction}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2016},
  url = {https://openreview.net/forum?id=Hy-YI_ZuWH},
}
Figure