Compressing Neural Networks with the Hashing Trick

Wenlin Chen, James T. Wilson, Stephen Tyree, Kilian Q. Weinberger, Yixin Chen

Abstract

As deep nets are increasingly used in applications suited for mobile devices, a fundamental dilemma becomes apparent: the trend in deep learning is to grow models to absorb ever-increasing data set sizes; however mobile devices are designed with very little memory and cannot store such large models. We present a novel network architecture, HashedNets, that exploits inherent redundancy in neural networks to achieve drastic reductions in model sizes. HashedNets uses a low-cost hash function to randomly group connection weights into hash buckets, and all connections within the same hash bucket share a single parameter value. These parameters are tuned to adjust to the HashedNets weight sharing architecture with standard backprop during training. Our hashing procedure introduces no additional memory overhead, and we demonstrate on several benchmark data sets that HashedNets shrink the storage requirements of neural networks substantially while mostly preserving generalization performance.

Introduction

Deep learning models are scaling rapidly to accommodate massive datasets, but this growth conflicts with the limited memory of mobile and embedded devices. While a server might possess hundreds of gigabytes of RAM, consumer devices like the iPhone 6 (at the time of this research) are constrained to 1GB. Standard approaches to model size reduction, such as training smaller networks, often result in significant accuracy loss. Other techniques like low-rank decomposition or pruning introduce complexity and require additional metadata for bookkeeping.

HashedNets addresses this "fundamental dilemma" by leveraging the "hashing trick" to force random weight sharing. This approach achieves massive compression (up to 64x) while maintaining, and occasionally improving, predictive performance without the need for auxiliary storage.

Methods: The Hashing Trick for Neural Networks

HashedNets exploit the inherent redundancy in neural network weights through a simple yet effective mechanism:

  1. Random Weight Sharing: Instead of unique weights for every connection, multiple connections share the same parameter value.
  2. Hashing Mechanism: A low-cost hash function $h(i, j)$ maps the indices of a connection (from node $i$ to node $j$) to an index in a small, compressed weight vector $w$. This eliminates the need to store a mapping table.
  3. Sign Factor: To prevent biased accumulation during hashing, a second hash function $\xi(i, j)$ assigns a random $+1$ or $-1$ to the weight. The virtual weight is defined as $V_{i,j} = w_{h(i,j)} \cdot \xi(i,j)$.
  4. Training via Backpropagation: The model is trained using standard backprop. The gradient for a physical weight in the compressed vector is the sum of the gradients of all virtual connections mapped to it.
HashedNets architecture illustrating the mapping from a small set of real weights to a large virtual weight matrix via a hash function.

A significant advantage of this architecture is "inflation": one can keep the number of physical parameters fixed while increasing the number of virtual hidden units, creating a large virtual network stored in a tiny physical footprint.

Experimental Evaluation

The authors evaluated HashedNets on eight benchmark image classification datasets, including MNIST and its challenging variants (ROT, BG-RAND, BG-IMG, BG-IMG-ROT), as well as binary image tasks (CONVEX, RECT).

Key Results

HashedNets consistently outperformed alternative compression techniques such as Low-Rank Decomposition (LRD) and Random Edge Removal (RER).

  • Extreme Efficiency: At a 1/64 compression ratio (retaining only 1.5% of original parameters), HashedNets maintained significantly higher accuracy than standard networks of equivalent size. On the MNIST-ROT dataset, HashedNets achieved roughly half the error rate of a size-equivalent standard network.
  • Optimal Inflation: Expanding the number of virtual hidden units by 8x to 16x while maintaining a constant physical parameter count yielded the best performance.
  • Information Density: Even with 1/64 compression, where the model effectively stores only 0.5 bits per virtual parameter, the network remains highly functional.
Test error vs. compression factor for MNIST and ROT datasets. HashedNets (red lines) consistently outperform other compression techniques like Low-Rank Decomposition (LRD) and Random Edge Removal (RER).

Discussion and Insights

The success of HashedNets confirms that neural network weights are highly redundant. By using storage-free indexing via hash functions, the architecture avoids the memory overhead associated with sparse matrix indices in pruning methods. Furthermore, random weight sharing appears to act as a form of regularization, potentially improving generalization similarly to Dropout.

Limitations and Future Work

Despite the memory savings, the pseudo-random nature of hashing can lead to non-coalesced memory access on GPUs, potentially slowing down execution compared to dense matrices. Future research could focus on optimizing GPU implementations and combining HashedNets with other techniques like 8-bit quantization or knowledge distillation (Dark Knowledge) for further efficiency gains.

Summary updated

Abstract

As deep nets are increasingly used in applications suited for mobile devices, a fundamental dilemma becomes apparent: the trend in deep learning is to grow models to absorb ever-increasing data set sizes; however mobile devices are designed with very little memory and cannot store such large models. We present a novel network architecture, HashedNets, that exploits inherent redundancy in neural networks to achieve drastic reductions in model sizes. HashedNets uses a low-cost hash function to randomly group connection weights into hash buckets, and all connections within the same hash bucket share a single parameter value. These parameters are tuned to adjust to the HashedNets weight sharing architecture with standard backprop during training. Our hashing procedure introduces no additional memory overhead, and we demonstrate on several benchmark data sets that HashedNets shrink the storage requirements of neural networks substantially while mostly preserving generalization performance.
BibTeX
@inproceedings{chen2015compressing,
  author = {Wenlin Chen and James T. Wilson and Stephen Tyree and Kilian Q. Weinberger and Yixin Chen},
  title = {{Compressing Neural Networks with the Hashing Trick}},
  booktitle = {International Conference on Machine Learning},
  year = {2015},
  url = {https://openreview.net/forum?id=SJEBcsZubr},
}
Figure