Online Forecasting Matrix Factorization

San Gultekin, John W. PaisleyIEEE TSP 2017 · OpenReview

TL;DR

This paper introduces a novel online matrix factorization approach for forecasting high-dimensional time series with missing values. By learning low-dimensional embeddings and an autoregressive model in a single pass, the method effectively predicts future values, outperforming existing techniques on large-scale real-world datasets.

What Problem Does This Paper Address?

Forecasting high-dimensional time series, especially those with many missing values, is a significant challenge. Traditional time series methods often struggle with the scale and sparsity of modern data, and many require the entire dataset to be available at once (batch processing). This paper tackles the problem of forecasting in an online setting, where data arrives sequentially as a stream, and the model must learn and predict using only a single pass through the data, without storing it all. This is crucial for applications where data is continuous and storage is limited, such as real-time sensor networks or financial markets. The authors specifically focus on using low-rank matrix factorization as a powerful tool for this task, building upon its success in areas like collaborative filtering.

Methods

The core of the paper lies in developing online matrix factorization techniques that can learn low-dimensional embeddings from streaming data. They propose three main methods:

  • Fixed Penalty (FP) Matrix Factorization: This approach adapts a probabilistic matrix factorization method to the online setting. It uses a fixed penalty term to regularize the latent factors, encouraging them to remain close to their previous values.
  • Fixed Tolerance (FT) Matrix Factorization: This method introduces a fixed tolerance parameter that bounds the approximation error. This allows for adaptive regularization, where the penalty strength can vary across time steps, potentially leading to better performance.
  • Zero Tolerance (ZT) Matrix Factorization: This is a special case of FT where the tolerance is set to zero. This aims for perfect reconstruction of observed data, effectively making it a parameter-free method, which is advantageous for large datasets where cross-validation is difficult.

Once these low-dimensional embeddings (represented by the matrix $V$) are learned, the paper derives a recursive Minimum Mean Square Error (MMSE) estimator to learn an autoregressive (AR) model on these embeddings. This AR model is then used to forecast future values of the time series. The derivation of the MMSE estimator makes minimal assumptions about the noise distribution, relying only on first and second-order statistics.

Datasets

The authors evaluate their proposed methods on two real-world datasets:

  • Electricity: Hourly power consumption data from 370 customers in Portugal, spanning over three years. This dataset contains approximately 9.7 million measurements.
  • Traffic: Hourly occupancy rates from 963 roads in the Bay Area, California, recorded over approximately three months. This dataset contains over 10 million measurements.

These datasets were used in both their original form and with artificially introduced sparsity (unstructured and structured) to simulate realistic missing data scenarios.

Key Insights and Ideas

  • Online Matrix Factorization for Time Series Forecasting: The paper demonstrates that matrix factorization, traditionally used for static data, can be effectively adapted for online time series forecasting, even with significant missing data.
  • Adaptive Regularization is Key: The FT and ZT methods, which allow for adaptive regularization (either through a tolerance bound or zero tolerance), generally outperform the fixed penalty approach (FP). This suggests that dynamically adjusting how much the latent factors are constrained is crucial for handling varying data characteristics.
  • Low-Rank Embeddings Capture Temporal Structure: By learning low-dimensional embeddings of the time series, the methods can capture underlying temporal patterns that are then modeled by an AR process. This is more effective than simply applying an AR model to the raw, high-dimensional, and sparse data.
  • Parameter-Free ZT Method is Promising: The ZT method, by eliminating the need for tuning regularization parameters, offers a significant advantage for large-scale streaming data where cross-validation is computationally prohibitive.
  • Importance of Generating Latent Sequences: The paper highlights that how the latent sequences ($V$) are generated is critical. A naive approach without temporal regularization can lead to poor forecasting performance, underscoring the value of the proposed methods.

Key Results

  • Superior Forecasting Accuracy: The proposed methods (FP, FT, and ZT) consistently outperform baseline methods (Base, AR, PMF, CKF) on both the Electricity and Traffic datasets, especially under high sparsity conditions.
  • FT and ZT Lead Performance: FT and ZT generally achieve the best prediction accuracy, with FT often showing a slight edge over ZT when low dimensionality is a concern.
  • Robustness to Sparsity: The proposed methods are significantly more robust to increasing sparsity compared to simpler AR models or non-regularized matrix factorization. For instance, on the Electricity dataset with unstructured sparsity, the proposed methods maintain much lower Mean Absolute Error (MAE) as the percentage of observed data decreases.
  • Impact of AR Order: For both datasets, setting the AR order ($P$) to 24 (corresponding to daily periodicity) yields optimal results for the proposed methods, indicating that the learned latent sequences capture daily patterns.
  • Dimensionality Matters: The performance is sensitive to the latent dimensionality ($d$). While a dimension of 1 is insufficient, increasing $d$ generally improves performance, with $d=10$ or $d=20$ often providing a good balance between accuracy and compression.

Limitations and Future Work

  • Computational Cost of FT: While FT offers adaptive regularization, its optimization problem can be computationally intensive, requiring solvers for quadratic programs. The paper addresses this by deriving closed-form updates for the FT constraint.
  • ZT's Restrictiveness: The ZT method's zero tolerance constraint can be too restrictive in some cases, potentially leading to poorer performance if the underlying data cannot be perfectly reconstructed. This might necessitate a higher factorization rank ($d$).
  • Future Work: The authors suggest investigating scenarios where entire columns of data are missing (e.g., system-wide blackouts). They also plan to explore alternative factorization approaches that might not require explicit regularization.

Summary updated

Abstract

In this paper the problem of forecasting high dimensional time series is considered. Such time series can be modeled as matrices where each column denotes a measurement. In addition, when missing values are present, low rank matrix factorization approaches are suitable for predicting future values. This paper formally defines and analyzes the forecasting problem in the online setting, i.e. where the data arrives as a stream and only a single pass is allowed. We present and analyze novel matrix factorization techniques which can learn low-dimensional embeddings effectively in an online manner. Based on these embeddings a recursive minimum mean square error estimator is derived, which learns an autoregressive model on them. Experiments with two real datasets with tens of millions of measurements show the benefits of the proposed approach.
BibTeX
@article{gultekin2017online,
  author = {San Gultekin and John W. Paisley},
  title = {{Online Forecasting Matrix Factorization}},
  journal = {IEEE Trans. Signal Process.},
  year = {2017},
  url = {https://openreview.net/forum?id=kKXE8dm6bU},
}
Figure