Fast Recursive Low-rank Tensor Learning for Regression

Ming Hou, Brahim Chaib-draaIJCAI 2017 · DOI

TL;DR

This paper introduces RHOPLS, a novel recursive framework for low-rank tensor regression that efficiently handles large, dynamic tensor sequences. By updating regression coefficients at a feature level rather than raw data level, RHOPLS achieves significant speedups over existing methods while maintaining comparable accuracy, making it suitable for real-time applications.

What Problem Does This Paper Address?

Machine learning is increasingly dealing with high-order, large-scale data, often in the form of dynamic sequences (e.g., video, sensor data). Traditional batch methods struggle with the computational and storage demands of such data, especially in real-time scenarios where new data arrives continuously. Existing sequential methods, like RNPLS, often sacrifice accuracy or convergence speed. Higher-order Partial Least Squares (HOPLS) offers good accuracy but is computationally prohibitive for large, dynamic datasets. This paper addresses the need for a sequential tensor regression method that is both fast and accurate, capable of handling large-scale, high-speed general tensor sequences in dynamic environments.

Methods

The core innovation is the Recursive Higher-Order Partial Least Squares (RHOPLS) framework. It builds upon the idea of recursive updates but significantly improves efficiency by:

  • Low-rank Tucker Modification: Integrates a low-rank modification strategy of Tucker decomposition into a PLS framework.
  • Feature-Level Updates: Crucially, RHOPLS updates regression coefficients (factors) at a small-scale feature level, rather than processing the entire raw data (observation) level. This is achieved by efficiently merging new data into the previous low-rank approximation of the model.
  • Blockwise Recursive Calculation: Employs a blockwise recursive scheme, meaning only a small set of factors needs to be stored, drastically reducing memory requirements.

The RHOPLS framework operates in four main steps for each new mini-batch of data:

  1. Incremental Approximation (Yellow Arrow): Partially decomposes the new mini-batch input and output tensors using Tucker decomposition to extract incremental factors. This step significantly reduces dimensionality complexity.
  2. Expansion (Blue Arrow): Appends the incremental factors to the existing factors representing the model's current state, creating an augmented set of factors. This is done for loadings and the cross-covariance core tensor.
  3. Compression (Purple Arrow): Truncates the augmented factors back to the original d-rank sizes by finding the most dominant principal components. This step efficiently updates the loading factors and the cross-covariance core tensor.
  4. Projection (Green Arrow): Updates the individual core tensors for input and output by projecting them using the newly obtained loadings. This step efficiently updates the core tensors, further reducing sample complexity.

Datasets

The paper evaluates RHOPLS on two real-world datasets:

  • Utrecht Multi-Person Motion Database (UMPM): This dataset provides synchronized video sequences and 3D ground truth positions of human motion. The input is an intensity image sequence (3rd-order tensor), and the output is 3D positions of markers (3rd-order tensor).
  • Neurotycho Electrocorticography (ECoG) Dataset: This benchmark involves decoding limb movements from monkey brain signals. The input is transformed ECoG signals (4th-order tensor), and the output is 3D movement distances (3rd-order tensor).

Key Insights and Ideas

  • Feature-Level Updates are Key: The most significant insight is that updating regression coefficients at the feature (factor) level, rather than the raw data level, is the primary driver of RHOPLS's speedup. This avoids processing large amounts of raw data repeatedly.
  • Recursive Framework for Dynamic Data: RHOPLS provides a robust solution for handling continuously arriving data streams, which is crucial for many real-world applications where data cannot be stored entirely.
  • Scalability Beyond Dimensionality: The method demonstrates excellent scalability not only with respect to data dimensionality but also with increasing numbers of latent vectors (d-ranks) and initial samples, outperforming existing methods significantly in these aspects.
  • Balancing Accuracy and Speed: RHOPLS achieves a remarkable balance, offering prediction accuracy comparable to state-of-the-art batch methods (like HOPLS) while being orders of magnitude faster than other sequential methods.

Key Results

  • Speedup: RHOPLS is significantly faster than existing sequential methods (RNPLS, NPLS) and batch methods (HOPLS). For instance, it achieves speedups of over 30x against RNPLS and 3000x against NPLS in the "table" scenario of the UMPM dataset. The acceleration rates increase with larger numbers of latent vectors.
  • Accuracy: RHOPLS maintains highly comparable accuracy to the best batch methods (HOPLS). In the UMPM dataset, it achieves similar RMSEP and Q index values. In the ECoG dataset, it shows nearly the same predictability as HOPLS across different settings.
  • Scalability: RHOPLS is much less sensitive to increasing input loading sizes (d-ranks) compared to HOPLS, reflecting its efficient feature-based updating strategy. It also requires fewer initial samples to achieve good results.

Limitations and Future Work

  • Hyper-parameter Tuning: While RHOPLS is efficient, it still requires tuning of hyper-parameters such as the initial number of latent vectors (F) and initial loadings (L, K). The paper mentions assuming L=ΔL and K=ΔK for simplicity and conducting grid searches for optimal values.
  • Future Work: The paper's success on challenging real-life tasks like human pose estimation from videos suggests RHOPLS has great potential for various applications. Future work could explore its application to other complex tensor-based problems and potentially further optimize the hyper-parameter selection process.

Summary updated

BibTeX
@inproceedings{hou2017fast,
  author = {Ming Hou and Brahim Chaib-draa},
  title = {{Fast Recursive Low-rank Tensor Learning for Regression}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/257},
}
Figure