TL;DR
This paper introduces a novel approach to compress deep neural networks by exploiting their inherent structural invariances, specifically permutation invariance in feedforward layers. They develop universal lossless compression algorithms that achieve near-entropy bounds and allow for inference directly from the compressed representation, significantly reducing storage and enabling on-device intelligence.
What Problem Does This Paper Address?
The explosive growth in the size and complexity of deep neural networks (DNNs) presents a significant challenge for deployment, especially on resource-constrained devices or for scaling cloud-based services (DLaaS). Storing millions of unique DNNs for personalized services is infeasible. While existing compression techniques often focus on lossy methods like pruning or quantization, this paper tackles the problem of universal lossless compression of DNNs, aiming to achieve representations that are as compact as theoretically possible while still allowing for efficient inference without full decompression. The core issue is how to represent the vast number of synaptic weights in a way that minimizes redundancy, especially considering the structural properties of DNNs.
Methods
The authors' key innovation lies in recognizing and exploiting the permutation invariance present in the layers of feedforward neural networks. Specifically, they observe that the output of a neuron is a function of the weighted sum of its inputs, and this sum is invariant to the order (labeling) of the input nodes. This property allows them to treat layers as unlabeled bipartite graphs or partially labeled bipartite graphs.
Their approach involves:
- Identifying and Dissipating Invariance: They develop algorithms to remove the "irrelevant uncertainty" arising from this permutation invariance. This is achieved by defining canonical representations for these graph structures.
- Universal Source Coding: They employ arithmetic coding, a standard technique for achieving near-entropy bounds, to compress the representations of these graph structures.
- Succinct Structures: The goal is to create "succinct structures" – representations that are close to the information-theoretic minimum number of bits and allow for relevant operations (like inference) on the compressed data.
- Inference without Full Decompression: A crucial aspect is their development of inference algorithms that can operate directly on the compressed representation, avoiding the need to decompress the entire network. This is achieved through a breadth-first search traversal of the compressed tree structures representing the network layers.
They propose algorithms for two substructures:
- Partially-labeled bipartite graphs: Used for the first and last layers.
- Unlabeled bipartite graphs: Used for intermediate layers.
These are then combined to compress K-layer feedforward networks.
Datasets
The authors evaluated their compression and inference algorithms on three standard datasets:
- MNIST: A dataset of handwritten digits.
- IMDB: A dataset for movie reviews sentiment classification.
- Reuters-21578: A dataset for text categorization.
They trained feedforward neural networks on these datasets and quantized the weights using different levels (17, 33, and 65) before applying their compression scheme.
Key Insights and Ideas
- Permutation Invariance as a Compression Opportunity: The most significant insight is that the permutation invariance of node labels in feedforward layers is not just a theoretical curiosity but a direct avenue for lossless compression. By recognizing this, they can remove redundant information that arises from arbitrary labeling.
- Bridging Information Theory and DNNs: The paper effectively bridges concepts from information theory (source coding, entropy bounds) with the practical problem of DNN compression, providing a theoretically grounded approach.
- Inference on Compressed Data: The ability to perform inference directly on the compressed representation is a major practical advantage, enabling efficient deployment without the overhead of decompression.
- Universal Compression: The algorithms are designed to be universal, meaning they do not require prior knowledge of the specific weight distributions, making them applicable to a wide range of DNNs.
Key Results
- Near-Entropy Bound Compression: The proposed algorithms achieve compression rates that are asymptotically close to the theoretical entropy bounds for the represented graph structures.
- Succinct Representations: The compressed representations are shown to be succinct, meaning they require only a small overhead beyond the theoretical minimum bits.
- Efficient Inference: The inference algorithm operating on compressed data is efficient, with an additional dynamic space requirement of O(N) for a layer with N nodes.
- Experimental Validation: Experiments on MNIST, IMDB, and Reuters datasets demonstrated that the compressed networks performed identically to the original quantized networks, with negligible extra memory for inference.
- Time Complexity: The inference time for compressed networks was higher than for uncompressed networks (e.g., 2.30 sec vs. 0.06 sec for MNIST17), but the authors argue it's not impractical and can be improved with efficient arithmetic coding implementations. The primary time cost in inference comes from arithmetic encoding/decoding and probability matrix computation.
Limitations and Future Work
- Inference Time Overhead: While compression is lossless and inference is possible without full decompression, the inference time for compressed networks is higher than for uncompressed ones. This is largely due to the arithmetic coding/decoding process.
- Future Work: The authors plan to investigate optimal quantization of real-valued synaptic weights, integrating ideas from functional quantization with their novel entropy coding approach. They also suggest that their compression algorithms can be applied to other neural network architectures like convolutional and recurrent neural networks.
Summary updated