TL;DR
This paper introduces Kronecker CP (KCP) decomposition as a novel method to compress Recurrent Neural Networks (RNNs), particularly LSTMs. By proposing efficient multiplication algorithms and leveraging KCP's unique structure, they achieve significant compression ratios while maintaining competitive accuracy and offering better parallelization potential compared to existing tensor decomposition methods.
What Problem Does This Paper Address?
Modern Recurrent Neural Networks (RNNs), especially Long Short-Term Memory (LSTM) and Gated Recurrent Unit (GRU) networks, are highly effective for sequential data tasks like natural language processing and video recognition. However, their complex architectures lead to substantial computational and memory demands, making them difficult to deploy on resource-constrained devices. While tensor decomposition methods like Tensor Train (TT), Block Term (BT), Tensor Ring (TR), and Hierarchical Tucker (HT) offer high compression ratios, they often struggle to balance both space and computational efficiency. This paper aims to address this trade-off by introducing a new tensor decomposition approach, Kronecker CP (KCP), designed to achieve both high compression and efficient computation for RNNs.
Methods
The core of this paper is the Kronecker CP (KCP) decomposition. KCP is derived from Kronecker Tensor (KT) decomposition. The authors first establish a KT decomposition for RNN weight matrices and then show how this can be transformed into a KCP format. The key innovation lies in the KCP structure, which results in sparse and partitioned factor matrices.
To leverage this structure for efficient computation, the authors propose two fast multiplication algorithms:
- Algorithm 1 (Strict Fast Multiplication): This algorithm directly computes the product of the input and the KCP-decomposed weight, contracting tensors sequentially.
- Algorithm 2 (Relaxed Fast Multiplication): This algorithm offers a more relaxed strategy, breaking down the computation to potentially improve efficiency, especially for parallel processing.
The paper also delves into theoretical aspects, proving theorems related to KCP's properties and deriving bounds for its rank.
Datasets
The authors evaluate their KCP-RNNs on the following datasets:
- UCF11: A dataset for action recognition in videos.
- Youtube Celebrities Face: A dataset for face recognition.
- UCF50: A more complex action recognition dataset, considered an extension of UCF11.
Key Insights and Ideas
- KCP offers a better balance: Unlike previous tensor decomposition methods that often sacrifice either space or computation efficiency, KCP aims to optimize both.
- Sparse and partitioned factors are key: The KCP decomposition naturally leads to factor matrices that are sparse and partitioned, which is crucial for efficient computation.
- Parallelism potential: The KCP structure is identified as having significant potential for parallel computing, which can further accelerate RNN computations.
- KT rank matters more than parameter count: The paper suggests that the KT rank (K) plays a more critical role in KCP's expressive ability and computational efficiency than the number of parameters alone.
- Weights sharing can be adapted: While previous methods adapted weights sharing for TT-LSTM, the authors show how to adapt it for KCP-LSTM, leading to even higher compression ratios.
Key Results
- Competitive Accuracy: KCP-RNNs achieve comparable accuracy to other tensor-decomposed RNNs and even the original models on UCF11, Youtube Celebrities Face, and UCF50 datasets.
- High Compression Ratios: The paper reports compression ratios as high as 278,219x on the UCF50 dataset with KCP-RNNs.
- Improved Efficiency: KCP-RNNs demonstrate superior space and computation complexity compared to other tensor-decomposed methods, especially at higher ranks.
- Faster Calculation: Experiments show that KCP-LSTMs achieve faster calculations, particularly when compared to TT-LSTM.
- Parallel Computing Advantage: Figure 12 demonstrates that parallel multiplication in KCP significantly outperforms serial multiplication, with the advantage growing with rank size.
Limitations and Future Work
- Algorithm 2's practical performance: While theoretically faster, Algorithm 2's practical performance can be inconsistent, especially in Python frameworks, suggesting the need to choose algorithms based on specific hardware and software environments.
- Parallel computing implementation: The authors note that to fully realize the potential of parallel computing with KCP, further work is needed to optimize multi-process or multi-thread management, potentially by leveraging specific hardware architectures.
- Pre-training dependency: Some of the comparisons on the UCF50 dataset required pre-training, which might not always be ideal for evaluating end-to-end performance.
Summary updated