Source-linked AI summary
Compressing Neural Networks with the Hashing Trick
Wenlin Chen, James T. Wilson, Stephen Tyree, Kilian Q. Weinberger, Yixin Chen
TL;DR
Large deep networks are difficult to deploy on mobile devices with limited memory, motivating compression that retains predictive performance. HashedNets use random hash-based weight sharing, and experiments show substantial model-size reductions with little accuracy loss, including a nearly 50% test-error drop under 8× virtual expansion. The paper also identifies GPU memory access as a future optimization challenge.
Problem
Deep-learning models grow with data-set size, but mobile devices have limited memory and cannot store many effective models.
Method
HashedNets randomly group neural-network connections into hash buckets that share parameters, which standard backpropagation tunes without additional memory overhead.
Results
HashedNets substantially reduce model size with little prediction-accuracy impact across benchmarks; test error drops nearly 50%, from 3% to 1.61%, with 8× virtual expansion.
Takeaways & Limitations
Reusing a finite set of parameters can create virtual connections and improve performance, with best results reported for 8–16× network inflation.
Takeaways & Limitations
GPU deployment remains future work because pseudo-random hashing may cause non-coalesced memory accesses on GPU architectures.
Abstract
from arXiv · showhide
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.
1. Introduction
Deep networks are growing alongside applications that must run on memory-limited mobile devices, creating a deployment dilemma. HashedNets address this tension by sharing weights through hashing, reducing model size while largely preserving accuracy.
- Motivation: Mobile devices typically have small working memory, while effective deep-learning models increasingly grow to absorb larger data sets.The cited example is the iPhone 6, with 1GB of RAM.
- Motivation: Large models can exceed on-device memory, while server-side inference requires sufficient bandwidth and introduces network delays.Training can remain server-side, but testing on-device becomes prohibitive when models exceed available memory.
- Prior work: Prior work indicates substantial redundancy in neural-network weights and explores compression through low-rank decomposition, distillation, reduced precision, and pruning.The accumulated evidence suggests that much of the information stored within network weights may be redundant.
- HashedNets: HashedNets randomly assign connections to hash buckets so connections in each bucket share one weight, with bucket parameters learned by standard backpropagation.The procedure is designed to require no additional memory overhead.
- Results: HashedNets drastically reduce neural-network model size with little impact on prediction accuracy across several real-world benchmarks.Under the same memory constraint, they have more adjustable free parameters than the cited low-rank methods, leading to smaller drops in descriptive power.
- Results: For a finite parameter budget, reusing each parameter multiple times can improve performance, with best results reported for 8–16× network inflation.This inflation remains compatible with dropout, activation functions, and weight sparsity.
2. Feature Hashing
Feature hashing maps high-dimensional inputs into a smaller hashed space to save memory. It preserves sparsity and approximately preserves inner products, while collisions remain the principal trade-off.
- Mapping: Feature hashing maps an input x ∈ R^d into a lower-dimensional space R^k using hash functions, with k ≪ d.The mapping uses an index hash h and an independent sign hash ξ.
- Mapping: The hashed representation aggregates input terms assigned to each hash-table dimension.The supplied formal definition identifies φ_k(x) as the sum of variables hashed into bucket k.
- Memory savings: Hashing saves memory by avoiding a term-to-index dictionary and storing model parameters in the smaller R^k space instead of R^d.It can operate directly on input term strings.
- Trade-offs: Hash collisions are the cost of dimensionality reduction, but their impact is less severe for sparse data and can be reduced with multiple hashing or larger hash tables.Feature hashing is most effective when feature vectors are sparse because fewer active features collide.
- Properties: The hashing trick is sparsity preserving, fast to compute, storage-free, and approximately preserves inner products in expectation.The independent sign hash makes inner products unbiased in expectation.
- Extensions: Multiple classifiers can share one hashed space by using separate hash functions for different tasks.The cited prior work applies this construction to multitask learning.
3. Notation
The notation distinguishes vectors, scalars, matrices, and their entries, then describes feed-forward propagation using virtual weight matrices and transformed activation units.
- Notation: Vectors use bold type, scalars use regular type, and matrices use capital bold type.Entries inherit the convention of the object containing them.
- Notation: The ith vector component is written x_i, and the (i, j)th matrix entry is written V_ij.These are scalar entries following their parent vector or matrix notation.
- Feed Forward Neural Networks: The forward propagation of layer ℓ uses a virtual weight matrix V_ℓ to produce pre- and post-transformation activation vectors.The transition function f can be ReLU, sigmoid, or tanh.
4. HashedNets
HashedNets compress fully connected neural networks by assigning connections to hash buckets whose shared parameters are trained with backpropagation. The approach avoids storing explicit assignments and preserves architectural flexibility while reducing memory.
- Random weight sharing: A compression factor of 1/4 reduces 24 virtual weights to six stored values by sharing weights among randomly grouped connections.Connections in the same color group share one parameter, represented in the stored vectors w1 and w2.
- Hash-based implementation: Explicitly storing each connection’s group assignment would impose an undesirable limit on memory savings.HashedNets therefore encode assignments through hashing rather than a secondary assignment matrix.
- Hash-based implementation: HashedNets determine each shared connection weight with an approximately uniform hash function mapping connection keys to hash buckets.The example uses h1(2,1)=1, making the corresponding virtual weight equal to w1=3.2; experiments use xxHash.
- Feature-hashing interpretation: Feature-hashing equivalence computes each output by hashing prior activations into K buckets and taking an inner product with K shared parameters.Each bucket contains the sum of variables hashed into it, establishing equivalence between feature hashing and random weight sharing.
- Feature-hashing interpretation: An independent sign hash factor ξ(i,j) is used to remove bias from hashed inner products caused by collisions.The sign factor preserves the equivalence between feature hashing and weight sharing.
- Training and extensions: HashedNets training is equivalent to standard neural-network training with equality constraints on shared weights, using forward propagation, error propagation, and shared-weight gradients.ReLU transition functions encourage sparsity, which can reduce hash collisions; the method can also extend to recurrent networks and combine with other compression techniques.
5. Related Work
Related work reduces neural-network complexity through architectural sharing, parameter reduction, pruning, reduced precision, low-rank decomposition, distillation, and feature hashing. These approaches provide complementary ways to reduce model size or parameter count, and several can be combined with HashedNets.
- Architectural compression: Convolutional filters and pooling reduce model complexity through shared receptive-field weights and fewer connections where input locality exists.Autoencoders likewise use tied encoder and decoder weights.
- Weight reduction: Soft weight sharing clusters weights with similar values for regularization, whereas optimal brain damage removes unimportant weights but requires auxiliary sparse-storage parameters and retraining.Random connection removal has also shown superior empirical performance in cited experiments.
- Precision reduction: Reduced numerical precision lowers storage requirements with little reported accuracy reduction and can be combined with HashedNets for further model-size reduction.The cited example uses 16-bit fixed-point representation with a compression factor of 1/4 relative to double precision.
- Low-rank compression: Low-rank decomposition exploits redundancy in full weight matrices, producing networks that are only slightly less accurate than networks with unrestricted weights.The cited evidence indicates substantial overparameterization in full weight matrices.
- Distillation: Distillation trains a compact network to reproduce the outputs of a larger network, using original labels together with softened output distributions.The larger network is trained first, followed by the smaller model.
- Feature hashing: Feature hashing reduces the number of features and parameters through random hash-based feature mixing for memory-constrained mobile and large-scale learning.The cited systems use hashing to avoid memory-consuming dictionaries and scale large-scale learning.
6. Experimental Results
Experiments across eight benchmark datasets evaluate HashedNets against compressed and size-matched neural-network baselines. HashedNets generally preserves accuracy better at strong compression, while virtual expansion improves fixed-storage models up to a sweet spot.
- Experimental setting: Experiments evaluate HashedNets and several size-constrained baselines across eight benchmark datasets.The comparisons include Random Edge Removal, Low-Rank Decomposition, equivalent-size neural networks, and Dark Knowledge variants.
- Results with varying compression: At small compression factors, HashNet and HashNetDK outperform the other baselines and are the only methods that maintain performance.The size-matched neural network is the strongest baseline but has substantially higher test error at small compression rates.
- Results with fixed storage: With fixed storage, expansion factors above 1 improve all methods over the fixed-sized neural network, but further expansion eventually increases test error.The experiments vary virtual hidden-node counts while keeping the number of real weights fixed.
- Results with fixed storage: HashedNet performance improves substantially through virtual expansion without adding parameters, with the 5-layer network benefiting through an expansion factor of 16×.At 16× expansion, the 5-layer network has 800 virtual nodes; excessive hashing can eventually produce increasingly similar gradient updates.
- Results with fixed storage: Best results occur when networks are inflated by 8–16×, after which additional expansion tends to hurt.The expansion benefit is bounded for HashedNets and the other compression methods.
7. Conclusion
HashedNets exploit redundant weights to create virtual connections, and expanding these connections can improve test error while retaining a compact stored model. The approach’s GPU deployment remains constrained by memory-access challenges from pseudo-random hashing.
- 7. Conclusion: Nearly 50%: test error drops from 3% to 1.61% when virtual weights expand by 8×.The networks with and without expansion both used dropout and Bayesian hyper-parameter optimization.
- 7. Conclusion: Virtual connections can increase neural-network expressiveness when additional nodes reuse existing weights.The paper frames this as one explanation for why additional virtual layers help.
- 7. Conclusion: GPU optimization is future work because pseudo-random hash functions can cause non-coalesced memory accesses.This is identified as a sensitive issue for GPU architectures with finite on-board memory.