Kronecker CP Decomposition with Fast Multiplication for Compressing RNNs

Dingheng Wang, Bijiao Wu, Guangshe Zhao, Hengnu Chen, Lei Deng, Tianyi Yan, Guoqi LiIEEE TNNLS 2020 · DOI · OpenReview

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:

  1. Algorithm 1 (Strict Fast Multiplication): This algorithm directly computes the product of the input and the KCP-decomposed weight, contracting tensors sequentially.
  2. 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

Abstract

Recurrent neural networks (RNNs) are powerful in the tasks oriented to sequential data, such as natural language processing and video recognition. However, since the modern RNNs, including long-short term memory (LSTM) and gated recurrent unit (GRU) networks, have complex topologies and expensive space/computation complexity, compressing them becomes a hot and promising topic in recent years. Among plenty of compression methods, tensor decomposition, e.g., tensor train (TT), block term (BT), tensor ring (TR) and hierarchical Tucker (HT), appears to be the most amazing approach since a very high compression ratio might be obtained. Nevertheless, none of these tensor decomposition formats can provide both the space and computation efficiency. In this paper, we consider to compress RNNs based on a novel Kronecker CANDECOMP/PARAFAC (KCP) decomposition, which is derived from Kronecker tensor (KT) decomposition, by proposing two fast algorithms of multiplication between the input and the tensor-decomposed weight. According to our experiments based on UCF11, Youtube Celebrities Face and UCF50 datasets, it can be verified that the proposed KCP-RNNs have comparable performance of accuracy with those in other tensor-decomposed formats, and even 278,219x compression ratio could be obtained by the low rank KCP. More importantly, KCP-RNNs are efficient in both space and computation complexity compared with other tensor-decomposed ones under similar ranks. Besides, we find KCP has the best potential for parallel computing to accelerate the calculations in neural networks.
BibTeX
@article{wang2020kronecker,
  author = {Dingheng Wang and Bijiao Wu and Guangshe Zhao and Hengnu Chen and Lei Deng and Tianyi Yan and Guoqi Li},
  title = {{Kronecker CP Decomposition with Fast Multiplication for Compressing RNNs}},
  journal = {IEEE Trans. Neural Networks Learn. Syst.},
  year = {2020},
  doi = {10.1109/tnnls.2021.3105961},
}
Figure