TL;DR
This paper introduces a novel approach to supervised learning for non-sequential data by representing model parameters as a tensor decomposed using the Canonical Polyadic (CP) decomposition. This method offers improved invariance to feature ordering and outperforms existing Tensor Network (TN) methods, particularly on sparse datasets, while also achieving competitive results on dense datasets with enhanced feature mapping.
What Problem Does This Paper Address?
Supervised learning tasks often involve data where features have no inherent order (e.g., house price prediction based on number of bedrooms, location, etc.). Modeling all possible interactions between these features leads to an exponential increase in computational cost and memory requirements, known as the "curse of dimensionality." Existing Tensor Network (TN) approaches, like Tensor Train (TT), attempt to mitigate this by factorizing the model parameters into a tensor. However, these methods are sensitive to the ordering of features, which is problematic for non-sequential data. The paper addresses the need for a method that can efficiently model feature interactions in non-sequential data while being invariant to feature ordering and scalable to large datasets.
Methods
The core contribution is the use of Canonical Polyadic (CP) Decomposition to represent the weight tensor of the model. Unlike Tensor Train (TT) or other Tensor Networks (TNs) that impose an ordering on their components, CP decomposition is inherently invariant to the permutation of its factors, making it suitable for non-sequential data. The authors develop efficient algorithms for both prediction and learning (inference and training) that scale linearly with the number of features and the local dimension of feature mappings. They also introduce:
- Generalized Local Feature Mappings: Moving beyond the standard 2-dimensional mappings, they propose polynomial mappings that can be extended to arbitrary dimensions.
- Normalized Polynomial Mapping: To address instability and overfitting with high-dimensional feature mappings, they introduce a unit normalization technique that significantly improves performance and stability.
- Order Regularization: A novel regularization scheme that penalizes higher-order feature interactions more heavily, improving generalization.
- Linear Model Initialization: A method to initialize the model's parameters based on a linear model solution, leading to faster convergence and better performance.
Datasets
The paper evaluates its proposed CP-based predictor on the following datasets:
- Synthetic Polynomial Regression Task: Used to illustrate the effects of initialization and order regularization.
- MovieLens 100K: A benchmark dataset for recommender systems, characterized by very sparse categorical data.
- California Housing Dataset: A standard dataset for regression on dense data, used to demonstrate the benefits of high-dimensional normalized feature mappings.
The authors also implemented and compared their approach against other TN-based predictors using code from Google's TensorNetwork library and their own implementations for Tucker, Tensor Ring, and Hierarchical Tucker formats.
Key Insights and Ideas
- CP Decomposition for Feature Order Invariance: The key insight is that CP decomposition's inherent invariance to factor permutation makes it a natural fit for non-sequential data, overcoming a major limitation of TT-based methods.
- High-Dimensional Normalized Feature Mappings: Increasing the local dimension of feature mappings can dramatically improve model expressiveness. Normalizing these high-dimensional mappings is crucial for stability and preventing overfitting, leading to performance competitive with fully-connected neural networks.
- Order Regularization for Sparse Data: For sparse categorical data, penalizing higher-order interaction coefficients more strongly (via order regularization) is beneficial for generalization.
- Linear Initialization as a Strong Baseline: Initializing the CP model based on a linear model solution provides a strong starting point, leading to faster convergence and often better final performance, especially on challenging tasks.
- CP vs. Other TNs: While other TNs like TT can represent CP tensors, the optimization process for TT can alter the structure, leading to different performance characteristics. The paper suggests that for non-sequential data, CP's direct representation is often more advantageous.
Key Results
- Outperformance on Sparse Data: The proposed CP-based predictor significantly outperformed other TN-based predictors on the MovieLens 100K dataset (sparse categorical data).
- Competitive Performance on Dense Data: On the California Housing dataset (dense data), the CP-based predictor with high-dimensional normalized feature mappings achieved performance comparable to fully-connected neural networks.
- Efficiency: The developed algorithms scale linearly with the number of features and local dimension, making them computationally efficient.
- Stability with High Dimensions: The normalized polynomial mapping allowed for stable training with local dimensions as high as d > 100, a feat not achievable with unnormalized mappings.
- Order Regularization Benefits: Order regularization was shown to help achieve lower validation error on certain tasks, particularly when using higher local dimensions.
Limitations and Future Work
- Limitations:
- The paper notes that for very small CP ranks, performance might be sensitive.
- While the CP model can approximate any function with sufficient rank, the optimal rank is not always obvious.
- For extremely high-dimensional datasets (e.g., 784 features), further research is needed to achieve state-of-the-art results, though linear initialization helps alleviate some issues.
- The Tucker-based predictor encountered "out of memory" errors on larger datasets due to its tensor structure.
- Future Work:
- Explore Riemannian optimization approaches for handling high local dimensions.
- Investigate other local feature mapping functions.
- Generalize the approach by employing different Tensor Networks for weight tensor representation, tailored to specific data structures (e.g., TT for sequential data, PEPS for images).
Summary updated