Generalized Canonical Polyadic Tensor Decompositions for Streaming Data

Eric Phipps, Nicholas Johnson, Tamara G. Kolda2023 · DOI

TL;DR

Researchers from Sandia National Laboratories have developed OnlineGCP, a new method for performing tensor decompositions on streaming data that isn't limited to standard Gaussian distributions. By allowing for flexible loss functions (like Poisson or Bernoulli), this approach can extract interpretable, real-time patterns from diverse data types such as taxi trip counts, crime records, and research abstracts more accurately and efficiently than traditional methods.

What Problem Does This Paper Address?

In our data-drenched world, information often arrives as "multiway" arrays, or tensors—think of a dataset organized by (Source IP x Destination IP x Port x Time). Canonical Polyadic (CP) decomposition is a powerful tool used to find the "latent" patterns within this data, effectively breaking a complex multidimensional block into a few interpretable components.

However, traditional CP decomposition faces two major hurdles:

  1. Static vs. Streaming: Most algorithms assume the data is static. In reality, data streams in constantly, and we need to update our models without re-processing the entire history from scratch.
  2. The "Gaussian" Assumption: Standard methods rely on least-squares math, which assumes data follows a Normal (Gaussian) distribution. This fails miserably for "count" data (like the number of taxi rides) or "binary" data (whether a crime occurred or not), which are better described by Poisson or Bernoulli distributions.

This paper introduces a "Generalized" CP (GCP) framework specifically designed for streaming data, bridging the gap between statistical flexibility and real-time processing.

Methods

The authors introduce OnlineGCP, which extends Generalized CP decomposition to a streaming context. Key technical highlights include:

  • Flexible Loss Functions: Unlike standard streaming methods, OnlineGCP allows users to choose a loss function that matches their data type (e.g., Poisson for counts, Bernoulli for binary data, or $\beta$-divergence).
  • Online Objective Function: The model minimizes a three-part objective:
  • Current Loss: Fitting the most recent batch of data.
  • History Regularization: A penalty term that prevents the model from changing too drastically from previous time steps, ensuring temporal stability.
  • Factor Regularization: Standard techniques to encourage low-rank, interpretable models.
  • Optimization via SGD: Because non-Gaussian loss functions break the standard "Alternating Least Squares" approach, the authors use Stochastic Gradient Descent (SGD) with the ADAM optimizer.
  • Reservoir Sampling: To keep the "history" part of the model accurate without storing all old data, they use reservoir sampling to maintain a representative window of past observations.
  • High-Performance Implementation: The method is implemented in GenTen, a software package designed for extreme-scale architectures using the Kokkos library for performance portability across CPUs and GPUs.

Datasets

The authors evaluated OnlineGCP using both synthetic benchmarks and three diverse real-world datasets:

  • ArXiv Abstract Data: A 3-way tensor (Category x Word x Month) tracking word usage in scientific abstracts over 300 months.
  • NYC Taxi Dataset: A 4-way tensor (Pickup Zone x Dropoff Zone x Hour x Day) representing taxi trip counts in New York City.
  • Chicago Crime Dataset: A 4-way tensor (Hour x Crime Type x Neighborhood x Day) sourced from the FROSTT repository, treated as Bernoulli (binary) data.
  • Synthetic Data: Controlled Gaussian and Poisson tensors used to benchmark accuracy against "ground truth" models.

Key Insights and Ideas

  • Interpretability is King: The most striking aspect of these decompositions is how "human-readable" the results are. For example, in the NYC Taxi data, the model automatically identifies distinct components like "Weekend Nightlife," "Morning Commute to Rockefeller Center," and "Travel to JFK/LaGuardia Airports."
  • Matching the Distribution Matters: For sparse datasets like Chicago Crime, using a Bernoulli loss function provides a much better fit than standard least-squares. The "Generalized" part of GCP isn't just a mathematical curiosity; it's essential for extracting signal from noise in non-Gaussian data.
  • Stability through Regularization: By penalizing large changes between time steps, the authors ensure that the "patterns" discovered by the model evolve smoothly over time rather than jumping erratically with every new data batch.

Key Results

  • Accuracy: OnlineGCP achieves accuracy comparable to "static" (batch) methods that have access to the entire dataset at once, but it does so while processing data one slice at a time.
  • Computational Efficiency: The streaming approach is significantly faster than re-running a static decomposition as new data arrives.
  • Hardware Acceleration: Using the GenTen software on GPUs (NVIDIA Volta V100), the authors demonstrated substantial speedups, making the method viable for high-velocity data streams.
  • K-Tensor Score: On synthetic data, OnlineGCP maintained high "K-tensor scores" (a measure of how well the decomposition matches the true underlying factors), outperforming standard online SGD methods in non-Gaussian scenarios.

Limitations and Future Work

While promising, the authors note several challenges:

  • Hyper-parameter Tuning: OnlineGCP requires careful tuning of learning rates, sample sizes, and regularization weights. This can be difficult when balancing computational cost against model accuracy.
  • Convergence Speed: The SGD solver can sometimes converge slowly, which increases the time required to process each new batch of data.
  • Future Directions: The team plans to address these solver challenges and incorporate "distributed parallelism" (both synchronous and asynchronous) to scale the method to even larger, more complex data streams across multiple computing nodes.

Summary updated

Abstract

Vectors comprising each factor matrix are interpretable! They each contribute to model M in a simple way Thus they describe patterns in the data
BibTeX
@misc{phipps2023generalized,
  author = {Eric Phipps and Nicholas Johnson and Tamara G. Kolda},
  title = {{Generalized Canonical Polyadic Tensor Decompositions for Streaming Data}},
  year = {2023},
  doi = {10.2172/2431370},
}
Figure