Title: HFH: HOMOLOGICALLY FUNCTIONAL HASHING FOR COMPRESSING DEEP NEURAL NETWORKS

Abstract: As the complexity of deep neural networks (DNNs) trends to grow to absorb the increasing sizes of data, memory and energy consumption has been receiving more and more attentions for industrial applications, especially on mobile devices. This paper presents a novel structure based on homologically functional hashing to compress DNNs, shortly named as HFH. For each weight entry in a deep net, HFH uses multiple low-cost hash functions to fetch values in a compression space, and then employs a small reconstruction network to recover that entry. The compression space is homological because all layers fetch hashed values from it. The reconstruction network is plugged into the whole network and trained jointly. On several benchmark datasets, HFH demonstrates high compression ratios with little loss on prediction accuracy. Particularly, HFH includes the recently proposed HashedNets (Chen et al., 2015a) as a degenerated scenario and shows significantly improved performance. Moreover, the homological hashing essence facilitates us to efficiently figure out one single desired compression ratio, instead of exhaustive searching throughout a combinatory space configured by all layers.

1. INTRODUCTION:

Deep Neural networks (DNNs) have been receiving ubiquitous success in wide applications, ranging from computer vision (Krizhevsky et al., 2012) , to speech recognition (Hinton et al., 2012) , natural language processing (Collobert et al., 2011) , and domain adaptation (Glorot et al., 2011) . As the sizes of data mount up, people usually have to increase the number of parameters in DNNs so as to absorb the vast volume of supervision. High performance computing techniques are studied to speed up training, concerning optimization algorithms, parallel synchronisations on clusters w/o GPUs, and stochastic binarization/ternarization, etc (Courbariaux et al., 2015; Dettmers, 2016; Lin et al., 2016) .

On the other hand the memory and energy consumption is usually, if not always, constrained in industrial applications (Kim et al., 2016; Yang et al., 2015) . For instance, for commercial search engines (e.g., Google and Baidu) and recommendation systems (e.g., NetFlix and YouTube), the ratio between the increased model size and the improved performance should be considered given limited online resources. Compressing the model size becomes more important for applications on mobile and embedded devices (Han et al., 2016; Kim et al., 2016) . Having DNNs running on mobile apps owns many great features such as better privacy, less network bandwidth and real time processing. However, the energy consumption of battery-constrained mobile devices is usually dominated by memory access, which would be greatly saved if a DNN model can fit in on-chip storage rather than DRAM storage (c.f. Han et al. (2016) for details).

A recent trend of studies are thus motivated to focus on compressing the size of DNNs while mostly keeping their predictive performance (Han et al., 2016; Kim et al., 2016; Yang et al., 2015) . With different intuitions, there are mainly two types of DNN compression methods, which could be used in conjunction for better parameter savings. The first type tries to revise the training target into more informative supervision using dark knowledge. In specific, Hinton et al. (2014) suggested to train a large network ahead, and distill a much smaller model on a combination of the original labels and the soft-output by the large net. The second type observes the redundancy existence in network weights (Chen et al., 2015a; Denil et al., 2013) , and exploits techniques to constrain or reduce the number of free-parameters in DNNs during learning. This paper focuses on the latter type.

To constrain the network redundancy, several efforts (Denil et al., 2013; Le et al., 2013; Yang et al., 2015) formulated an original weight matrix into either low-rank or fast-food decompositions. Moreover Han et al. (2015) and Han et al. (2016) proposed a simple-yet-effective pruning-retraining iteration during training, followed by quantization and fine-tuning. An adaptive pruning strategy was further studied recently in (Guo et al., 2016) under the name of dynamic network surgery. Chen et al. (2015a) proposed HashedNets to efficiently implement parameter sharing prior to learning, and showed notable compression with much less loss of accuracy than low-rank decomposition. More precisely, prior to training, a hash function is used to randomly group (virtual) weights into a small number of buckets, so that all weights mapped into one hash bucket directly share a same value. HashedNets was further deliberated in frequency domain for compressing convolutional NNs in Chen et al. (2015b) . It should be noted that, these approaches are not completely conflicted, and methods based on different assumptions may be used jointly for a better compression.

To obtain a desired compression in applications, one key question of most existing compression approaches is how to appropriately choose the compression ratios. Usually, people have to search within finite choices either heuristically or in a Bayesian manner. The searching procedure becomes more and more exhaustive as the network depth increases, since usually compression ratios are various for different (kinds of) layers (Han et al., 2015; Guo et al., 2016) . Moreover, we observe HashedNets compresses model sizes greatly at marginal loss of accuracy for many situations, whereas significantly loses accuracy for others. After revisiting its mechanism, we conjecture this instability comes from at least three factors. First, hashing and training are disjoint in a two-phase manner, i.e., once inappropriate collisions exist, there may be no much optimization room left for training. Second, one single hash function is used to fetch a single value in the compression space, whose collision risk is larger than multiple hashes (Broder & Karlin, 1990) . Third, parameter sharing within a buckets implicitly uses identity mapping from the hashed value to the virtual entry in HashedNets.

This paper proposes the homologically functional hashing (HFH) to relieve these problems. Specifically, we use multiple hash functions to map per virtual entry into multiple values in the compression space. Inspired from the "homology" in biology (Williams & Forey, 2004) , the compression space is a homological space, meaning that it is accessed by all entries from all (kinds of) layers in a DNN. Then an additional network plays in a mapping function role from these hashed values to the virtual entry (before hashing), which can be also regarded as "reconstructing" the virtual entry from its multiple hashed values. Plugged into and jointly trained within the original network, the reconstruction network is of a comparably ignorable size, i.e., at low memory cost.

The homologically functional hashing structure includes HashedNets as a degenerated special case, and facilitates less value collisions and better value reconstruction. Moreover, the homology essence favors high efficiency during searching appropriate compression ratios, because the only value we have to determine is a scalar, i.e., the size of the homological compression space. Since HFH imposes no restriction on other network design choices (e.g. dropout and weight sparsification), it can be considered as a standard tool for DNN compression, and provably used jointly with other compression techniques for a even better compression. Experiments on several datasets demonstrate significantly larger reduction of model sizes and/or less loss on prediction accuracy, compared with HashedNets.

2. BACKGROUND:

Notations. Throughout this paper we express scalars in regular (A or b), vectors in bold (x), and matrices in capital bold (X). Furthermore, we use x i to represent the i-th dimension of vector x, and use X ij to represent the (i, j)-th entry of matrix X. Occasionally, [x] i is also used to represent the i-th dimension of vector x for specification clarity . Notation E[•] stands for the expectation operator.

Feed Forward Neural Networks. We define the forward propagation of the -th layer as

a +1 i = f (z +1 i ), with z +1 i = b +1 i + d j=1 V ij a j , for ∀i ∈ [1, d +1 ].

(1)

For each -th layer, d is the output dimensionality, b is the bias vector, and V is the (virtual) weight matrix in the -th layer. Vectors z , a ∈ R d denote the units before and after the activation function f (•). Typical choices of f (•) include rectified linear unit (ReLU) (Nair & Hinton, 2010) , sigmoid and tanh (Bishop, 1995) .

Feature Hashing has been studied as a dimension reduction method for reducing model storage size without maintaining the mapping matrices like random projection (Shi et al., 2009; Weinberger et al., 2009) . Briefly, it maps an input vector x ∈ R n to a much smaller feature space via φ : R n → R K with K n. Following the definition in Weinberger et al. (2009) , the mapping φ is a composite of two approximate uniform hash functions h : N → {1, . . . , K} and ξ : N → {-1, +1}. The j-th element of φ(x) is defined as:

[φ(x)] j = i:h(i)=j ξ(i)x i .

(2)

As shown in (Weinberger et al., 2009) , a key property is its inner product preservation, which we quote and restate below.

Lemma [Inner Product Preservation of Original Feature Hashing] With the hash defined by Eq. ( 2), the hash kernel is unbiased, i.e., E φ [φ(x) φ(y)] = x y. Moreover, the variance is var x,y =

1 K i =j x 2 i y 2 j + x i y i x j y j , and thus var x,y = O( 1 K ) if ||x|| 2 = ||y|| 2 = const.

HashedNets in (Chen et al., 2015a) . As illustrated in Figure 1 (a), HashedNets randomly maps network weights into a smaller number of groups prior to learning, and the weights in a same group share a same value thereafter. A naive implementation could be trivially achieved by maintaining a secondary matrix that records the group assignment, at the expense of additional memory cost however. HashedNets instead adopts a hash function that requires no storage cost with the model. Assume there is a finite memory budge K per layer to represent V , with K (d + 1)d +1 . We only need to store a weight vector w ∈ R K , and assign V ij an element in w indexed by a hash function h (i, j), namely

EQUATION

where hash function h (i, j) outputs an integer within [1, K ]. Another independent hash function ξ (i, j) : (d +1 × d ) → ±1 outputs a sign factor, aiming to reduce the bias due to hash collisions (Weinberger et al., 2009) . The resulting matrix V is virtual, since d could be increased without increasing the actual number of parameters in w once the compression space size K is determined and fixed.

Substituting Eq. (3) into Eq. ( 1), we have

z +1 i = b +1 i + d j=1 ξ (i, j)w h (i,j) a j .

During training, w is updated by back propagating the gradient via z +1 (and the virtual V ). Besides, the activation function f (•) in Eq. ( 1) was kept as ReLU in (Chen et al., 2015a) to further relieve the hash collision effect through a sparse feature space. In both (Chen et al., 2015a) and this paper, the open source xxHash1 is adopted as an approximately uniform hash implementation with low cost.

3. HOMOLOGICALLY FUNCTIONAL HASHING:



3.1. STRUCTURE FORMULATION:

The key differences between our homologically functional hashing and HashedNets (Chen et al., 2015a ) are three folded: (i) how to maintain the compression space, (ii) how to employ hash functions, and (iii) how to map from hashed values to a virtual entry. Precisely,

• Reminder in HashedNets the compression space are split into pieces, with one piece w for one layer. In contrast, the compression space w ∈ R K in HFH is taken as a whole, so that any entry in all layers fetches hashed values from a same space, namely the homology.

• Instead of adopting one pair of hash function (h, ξ) in Eq. ( 3), we use a set of multiple pairs of independent random hash functions. Let's say there are U pairs of mappings {h u , ξ u } U u=1 , each h u (i, j) outputs an integer within [1, K], and each ξ u (i, j) selects a sign factor. • Eq. ( 3) of HashedNets assigns an equality between one virtual element and one hashed value, i.e., an implicit identity mapping. In contrast, this paper uses a multivariate function g(•) to map from multiple hashed values {ξ u (i, j)w hu(i,j) } U u=1 to V ij . Specifically,

EQUATION

Therein, α is referred to as the parameters in g(•). Note that the input ξ u (i, j)w hu(i,j) is order sensitive from u = 1 to U . For optimization convenience, we choose g(•) to be a multi-layer feed forward neural network, and other multivariate functions can be considered as alternatives.

Figure 1 (b) illustrates our HFH structure on one layer, which can be easily plugged in any matrices of DNNs. Note that α in the reconstruction network g(•) is of a much smaller size compared to w.

For instance, a setting with U = 4 and a 1-layer g(•; α) of α ∈ R 4 performs already well enough in experiments. In other words, Eq. ( 4) just uses an ignorable amount of additional memory to describe a functional w-to-V mapping, whose properties will be further explained in the sequel. Figure 1(c ) further shows the HFH structure on multiple layers, taking AlexNet (Krizhevsky et al., 2012) for instance. Therein, no matter convolutional or fully-connected, all layers fetch hashed values from one single homological compression space.

3.2. TRAINING PROCEDURE:

The parameters in need of updating include w in the compression and α in g(•). Training HFH is equivalent to training a standard neural network, except that we need to forward/backward-propagate values related to w through g(•) and the virtual entries.

Forward Propagation. Substituting Eq. ( 4) into Eq. ( 1), we omit the super-script and get

z i = b i + d j=1 a j V ij = b i + d j=1

a j • g ξ 1 (i, j)w h1(i,j) , . . . , ξ U (i, j)w h U (i,j) ; α .

(5)

Backward Propagation. Denote L as the final loss function, e.g., cross entropy or squared loss, and suppose δ i = ∂L ∂zi is already available by back-propagation from layers above. The derivatives of L with respect to w and α are computed by

EQUATION

where, since we choose g(•) as a multilayer neural network, derivatives ∂Vij ∂w and ∂Vij ∂α can be calculated through the small network g(•) in a standard back-propagation manner.

Complexity. Concerning time and memory cost, HFH roughly has the same complexity as Hashed-Nets, since the additional small network g(•) is quite light-weighted (e.g., 4 hashed inputs and 2 layers). One key varying factor is the way to implement multiple hash functions. On one hand, if they are calculated online, HFH requires little additional time if tackling them in parallel. On the other, if they are pre-computed and stored in dicts to avoid hashing time cost, the multiple hash functions of HFH demand more storage space. In application, we suggest to pre-compute hashes during offline training for speedup, and to compute hashing in parallel during online prediction for saving memory under limited hardware budget.

3.3. PROPERTY ANALYSIS:

In this part, we try to depict the properties of our HFH from several aspects to help understanding it, especially in comparison with HashedNets (Chen et al., 2015a) .

Value Collision. It should be noted, both HashedNets and HFH conduct hashing prior to training, i.e., in a two-phase manner. Consequently, it would be unsatisfactory if hashing collisions happen among important values. For instance in natural language processing tasks, one may observe wired results if there are many hashing collisions among embeddings (which form a matrix) of frequent words, especially when they are not related at all. In the literature, multiple hash functions are known to perform better than one single function (Azar et al., 1994; Broder & Karlin, 1990; Broder & Mitzenmacher, 2001) . In intuition, when we have multiple hash functions, the items colliding in one function are hashed differently by other hash functions.

Value Reconstruction. In both HashedNets and HFH, the hashing trick can be viewed as a reconstruction of the original parameter V from w ∈ R K . In this sense, the approach with a lower reconstruction error is preferred2 . Then we have at least the following two observations:

• The maximum number of possible distinct values output by hashing intuitively explains the modelling capability (Shi et al., 2009) . For HashedNets, considering the sign hashing function ξ(•), we have at most 2K possible distinct values of Eq. ( 3) to represent elements in V. In contrast, since there are multiple ordered hashed inputs, HFH has at most (2K) U possible distinct values of Eq. ( 4). Note that the memory size K is the same for both.

• The reconstruction error may be difficult to analyzed directly, since the hashing mechanism is trained jointly within the whole network. However, we observe g ξ 1 (i, j)w h1(i,j) , . . . , ξ U (i, j)w h U (i,j) ; α degenerates to g(ξ 1 (i, j)w h1(i,j) ) if we assign zeros to all entries in α unrelated to the 1st input dimension. Since g(ξ 1 (i, j)w h1(i,j) ) depends only on one single pair of hash functions, it is conceptually equivalent to Hashed-Nets. Consequently, including HashedNets as a special case, HFH with freely adjustable α is able to reach a lower reconstruction error to fit the final accuracy better.

Feature Hashing. In line with previous work (Shi et al., 2009; Weinberger et al., 2009) , we compare HashedNets and HFH in terms of feature hashing. For specification clarity, we drop the sign hashing functions ξ(•) below for both methods, the analysis with which is straightforward by replacing K hereafter with 2K.

• For HashedNets, one first defines a hash mapping function φ

(1)

EQUATION

Thus z i by HashedNets can be computed as the inner product (details c.f. Section 4.3 in (Chen et al., 2015a) )

EQUATION

• For HFH, we first define a hash mapping function φ

(2) i (a). Different from a K-dim output in Eq. ( 7), it is of a much larger size K U , with

EQUATION

Second, we define vector g α (w) still of length K U , whose

U u=1 k u K (u-1) -th entry is [g α (w)] U u=1 kuK (u-1)

g (w k1 , w k2 , . . . , w k U ; α) , for ∀u, k u = 1, . . . , K. (10) Thus z i by HFH can be computed as the following inner product

EQUATION

The difference between Eq. ( 8) and Eq. ( 11) further explains the above discussion about "the maximum number of possible distinct values".

Homology. Efficiency during searching appropriate compression ratios is the most important benefit brought by the homological property. Particularly, people usually have to search within candidate compression ratios either heuristically or in a Bayesian manner. The searching procedure becomes more and more exhaustive as the network depth increases, since usually compression ratios are various for different (kinds of) layers. For instance, the compression ratios of convolutional and fully-connected layers in both Han et al. (2015) and Guo et al. (2016) are quite different. In contrast for HFH, we only need to vary one scalar value K concerning the compression ratio. One may argue that these methods can adopt a same pruning ratio throughout layers, while preliminary experiments (not focused on and thus omitted in this paper) indicate equally pruning leads to inferior performances.

4. RELATED WORK:

Recent studies have confirmed the redundancy existence in the parameters of deep neural networks. Denil et al. (2013) decomposed a matrix in a fully-connected layers as the product of two low-rank matrices, so that the number of parameters decreases linearly as the latent dimensionality decreases. More structured decompositions Fastfood (Le et al., 2013) and Deep Fried (Yang et al., 2015) were proposed not only to reduce the number of parameters, but also to speed up matrix multiplications. Han et al. (2015) and Han et al. (2016) proposed to iterate pruning-retraining during training DNNs, and used quantization and fine-tuning as a post-processing step. Huffman coding and hardware implementation were also considered. In order to mostly keep accuracy, the authors suggested multiple rounds of pruning-retraining. That is, for little accuracy loss, we have to prune slowly enough and thus suffer from increased training time. More recently, dynamic network surgery was proposed in (Guo et al., 2016) , which achieves state-of-the-art compressions by adopting a dynamic strategy to adapt the pruning procedure. Again, the most related work to ours is HashedNets (Chen et al., 2015a) , which was then extended in (Chen et al., 2015b) to random hashing in frequency domain for compressing convolutional neural networks. Either HashedNets or HFH could be combined in conjunction with other techniques for better compression.

Extensive studies have been made on constructing and analyzing multiple hash functions, which have shown better performances over one single hash function (Broder & Karlin, 1990) . One multi-hashing algorithm, d-random scheme (Azar et al., 1994) , uses only one hash table but d hash functions, pretty similar to our settings. One choice alternative to d-random is the d-left algorithm proposed in Broder & Mitzenmacher (2001) , used for improving IP lookups. Hashing algorithms for natural language processing are also studied in Goyal et al. (2012) . Papers (Shi et al., 2009; Weinberger et al., 2009) investigated feature hashing (a.k.a. the hashing trick), providing useful bounds and feasible results.

5. EXPERIMENTS:

We conduct extensive experiments to evaluate HFH on DNN compression, especially in comparison with HashedNets. Codes for fully reproducibility will be open source in future after necessary polishment.

5.1. ENVIRONMENT DESCRIPTIONS:

Datasets. Five benchmark datasets (Larochelle et al., 2007) are considered here, including (1) the original MNIST hand-written digit dataset, (2) dataset BG-IMG as a variant to MNIST, (3) binary image classification dataset CONVEX, (4) dataset CIFAR-10, and (5) ImageNet ILSVRC-2012. For all datasets, we use prespecified training and testing splits. In particular, the original MNIST dataset has #train=60,000 and #test=10,000, while both BG-IMG and CONVEX have #train=12,000 and #test=50,000. CIFAR-10 consists of 60k 32×32 color images of 10 object classes, i.e., 6k images per class, and there are 50k training and 10k testing images, respectively. ImageNet ILSVRC-2012 has 1.2M training images and 50k validation images. Moreover, collected from a commercial search engine, a large scale dataset with billions of samples is used to learn DNNs for pairwise semantic ranking. We randomly split out 20% samples from the training data to form the validation set.

Methods and Settings. Chen et al. (2015a) compared HashedNets against several DNN compression approaches, and showed HashedNets performs consistently the best, including the low-rank decomposition (Denil et al., 2013) . Under the same settings, we compare HFH with HashedNets3 and baseline DNNs without compression. If not defined, all activation functions are chosen as ReLU.

5.2. FEEDFORWARD NNS FOR CLASSIFICATION:

Focusing on classification by feedforward NNs, the performances of HFH are tested on MNIST, textttBG-IMG and CONVEX in the following two scenarios. First, we compare the effects of varying compression ratio by HFH and HashedNets. Second, we compare different configurations of HFH itself, including the number U of seeds and the layer of reconstruction network g(•). Hidden layers within g(•) keep using tanh as activation functions.

5.2.1. VARYING COMPRESSION RATIO:

To test robustness, we vary the compression ratio with (1) a fixed virtual network size, and then with (2) a fixed memory size (i.e., the size of compression space). Three-layer (1 hidden layer) and five-layer (3 hidden layers) networks are investigated. In experiments, we vary the compression ratio geometrically within {1, 1 2 , 1 4 , . . . , 1 64 }. For HFH, this comparison sticked to use 4 hash functions, 3-layer g(•), and without dual space hashing.

With Virtual Network Size Fixed. The hidden layer for 3-layer nets initializes at 1000 units, and for 5-layer nets starts at 100 units per layer. As the compression ratio ranges from 1 to 1/64 with a fixed virtual network size, the memory decreases and it becomes increasingly difficult to preserve the classification accuracy. The testing errors are shown in Figure 2 , where standard neural networks with equivalent parameter sizes are included in comparison. HFH shows robustly effective compression against the compression ratios, and persistently produces better prediction accuracy than HashedNets. It should be noted, even when the compression ratio equals to one, HFH with the reconstruction network structure is still not equivalent to HashedNets and performs better. With Memory Storage Fixed. We change to vary the compression ratio from 1 to 1/64 with a fixed memory storage size, i.e., the size of the virtual network increases while the number of free parameters remains unchanged. In this sense, we'd better call it expansion instead of compression. Both 3-layer and 5-layer nets initialize at 50 units per hidden layer. The testing errors in this scenario are shown in Figure 3 . At all compression (expansion) ratios on each dataset, HFH performs better than or at least comparably well compared to HashedNets. 

5.2.2. VARYING CONFIGURATIONS OF HFH:

On 3-layer nets with compression ratio 1/8, we vary the configuration dimensions of HFH, including the number of hash functions (U ), and the structure of layers of the reconstruction network g(•). Since it is impossible to enumerate all probable choices, U is restricted to vary in {2, 4, 8, 16}. The structure of g(•) is chosen from 2 ∼ 4 layers, with U × 1, U × 0.5U × 1, U × U × 0.5U × 1 layerwise widths, respectively. We denote Ux-Gy as x hash functions and y layers of g(•). Table 1 shows the performances of HFH with different configurations on MNIST. We summarize key observations below. First, the series from index (0) to (1.x) fixes a 3-layer g(•) and varies the number of hash functions. As listed, more hash functions do not ensure a better accuracy, and instead U4-G3 performs the best, perhaps because too many hash functions potentially brings too many partial collisions. Second, the series from (0) to (2.x) fixes the number of hash functions and varies the layer number in g(•), where three layers performs the best mainly due to its strongest representability. Fastfood 16 (AD) (Yang et al., 2015) 42.90% 16.4M 1/3.7 SVD (Denton et al., 2014) 44.02% 11.9M 1/5 pruning (Han et al., 2015) 42.77% 6.7M 1/9 dynamic surgery (Guo et al., 2016) 43.09% 3.45M 1/17.7

On ImageNet ILSVRC-2012 data, the standard AlexNet model (Krizhevsky et al., 2012) is chosen as the reference model, which has 61 million parameters across 5 conv layers and 3 fc layers. The top-1 classification test error by this baseline AlexNet is 42.78%. The current state-of-the-art compression results on AlexNet are achieved by pruning in (Han et al., 2015) with overall 1/9 compression ratio, and dynamic network surgery in (Guo et al., 2016) with overall 1/17.7 compression ratio, which are obtained by carefully tuning the compression ratios in different layers.

Applying HashedNets to match the above two compression ratios, the performances are much worse, as listed in Table 2 . However, using HFH at the same compression ratios, the test errors are significantly reduced and even comparable to those by (Han et al., 2015) and (Guo et al., 2016) . Again it is noticeable that: (1) both HashedNets and HFH hold the compression ratios across all layers equal, and thus the searching time cost is low;

(2) the hashing techniques and the pruning strategies are not mutually exclusive, but provably to be used jointly for a better compression.

5.4. CONVOLUTIONAL NNS FOR PAIRWISE SEMANTIC RANKING:

Finally, we evaluate the performance of HFH on semantic learning-to-rank convolutional NNs. The data are collected from logs of a commercial search engine, with per clicked query-url being a positive sample and per non-clicked being a negative sample. There are totally around 45 billion samples. We adopt a deep convolutional structured semantic model similar to (Huang et al., 2013; Shen et al., 2014) , which is of a siamese structure to describe the semantic similarity between a query and the title of an url. Stochastically for each query, the network is trained to optimize the pairwise ranking cross entropy for each randomly sampled pair of positive and negative samples.

The performance is evaluated by correct-to-wrong pairwise ranking ratio on testing set. In Figure 5 , we plot the performance by a baseline network as training epoch proceeds. Results by HFH and HashedNets with 1/4 compression ratio are included for comparison. Still, HFH performs better than HashedNets throughout the training epochs, and even comparable to the full network baseline that requires 4 times of memory storage. The deterioration of HashedNets probably comes from many inappropriate collisions on word embeddings, especially for words of high frequencies.

6. CONCLUSION AND FUTURE WORK:

This paper presents a novel homologically functional hashing for neural network compression. Briefly, after adopting multiple low-cost hash functions to fetch values in a homological compression space, HFH employs a small reconstruction network to recover each entry in an matrix of the original network. The compression space is shared throughout all layers, and the reconstruction network is plugged into the whole network and learned jointly. HFH includes the recently proposed HashedNets (Chen et al., 2015a) as a degenerated special case. On multiple datasets, HFH demonstrates promisingly high compression ratios with little loss on prediction accuracy, especially significantly improved compared with HashedNets. As a simple and effective approach, HFH is expected to be a standard tool for DNN compression.

As future work, we aim for deeper analysis on the properties and bounds of HFH. More industrial applications are also expected, especially on mobile devices. Furthermore, HFH might be extended in a multi-hops hyper-structure. Briefly, imagining w in the compression space plays a virtual role similar to V, we may adopt the homologically functional hashing structure once again on w, so that w is still virtual and reconstructed by hashed values from another further compressed space.

:

http://cyan4973.github.io/xxHash/

One might argue that there exists redundancy in V, whereas here we could imagine V is already structured and filled by values with least redundancy.

HashedNets code downloaded from http://www.cse.wustl.edu/∼wenlinchen/project/HashedNets/index.html

Figures and Tables:

Figure 1: Illustrations of hashing approaches for neural networks compression. (a) and (b) illustrate HashedNets (Chen et al., 2015a) and our HFH on one layer's weight matrix. (c) shows HFH on AlexNet. (Best viewed in color)

Figure 2: Testing errors by varying compression ratio with a fixed virtual network size.

Figure 3: Testing errors by varying compression (expansion) ratio with a fixed memory storage.

CONVOLUTIONAL NNS FOR IMAGE CLASSIFICATIONWe further evaluate the performances by hashing compression methods on deep convolutional NNs for image classification. Note that, we treat the convolutional layers same as fully-connected layers during hashing. A more meticulous alternative could be hashing over CNNs on CIFAR-10 (Krizhevsky & Hinton, 2009) and ImageNet ILSVRC-2012 datasets are reported here for comparison.Particularly on CIFAR-10, a traditional CNN model with 3 conv layers and 2 fc layers is trained as the baseline, which stores roughly 4.8 million parameters and achieves 11.01% top-1 classification test error. As we vary the compression ratio, again equally over all layers, the top-1 test errors by HashedNets and HFH are illustrated in Figure4. As shown, HFH can still achieve a test error at 18% with just 1 percent memory size of the baseline model, much better than HashedNets.

Figure 4: Performances by compressed convolutional NNs on CIFAR-10 data.

Figure 5: Performances for pairwise semantic ranking. Testing correct-to-wrong pairwise ranking ratios (the larger the better) are plotted versus the number of training epochs.

Performances on MNIST by various configurations of HFH.

Table content: <table><tr><td colspan="2">Index Config</td><td>Test Error(%)</td></tr><tr><td>(0)</td><td>U4-G3</td><td>1.32</td></tr><tr><td>(1.1)</td><td>U2-G3</td><td>1.42</td></tr><tr><td>(1.2)</td><td>U8-G3</td><td>1.39</td></tr><tr><td>(1.3)</td><td>U16-G3</td><td>1.40</td></tr><tr><td>(2.1)</td><td>U4-G2</td><td>1.34</td></tr><tr><td>(2.2)</td><td>U4-G3</td><td>1.28</td></tr></table>

Performances by AlexNet on ImageNet ILSVRC-2012. Note HashedNet and HFH are in a same comparable level, holding an equal compression ratio across all layers.

Table content: <table><tr><td>Method</td><td colspan="3">Top-1 Test Error(%) Parameters Compression</td></tr><tr><td>baseline</td><td>42.78%</td><td>61.0M</td><td>1</td></tr><tr><td>HashedNet (Chen et al., 2015a)</td><td>61.71%</td><td>6.7M</td><td>1/9</td></tr><tr><td>HashedNet (Chen et al., 2015a)</td><td>64.17%</td><td>3.45M</td><td>1/17.7</td></tr><tr><td>HFH (ours)</td><td>48.05%</td><td>6.7M</td><td>1/9</td></tr><tr><td>HFH (ours)</td><td>51.99%</td><td>3.45M</td><td>1/17.7</td></tr></table>

Peer review (iclr2017):
The paper presents a method to reduce the memory footprint of a neural network at some increase in the computation cost. This paper is a generalization of HashedNets by Chen et al. (ICML*15) where parameters of a neural network are mapped into smaller memory arrays using some hash functions with possible collisions. Instead of training the original parameters, given a hash function, the elements of the compressed memory arrays are trained using back-propagation. In this paper, some new tricks are proposed including: (1) the compression space is shared among the layers of the neural network (2) multiple hash functions are used to reduce the effects of collisions (3) a small network is used to combine the elements retrieved from multiple hash tables into a single parameter. Fig 1 of the paper describes the gist of the approach vs. HashedNets. On the positive side, + The proposed ideas are novel and seem useful. + Some theoretical justification is presented to describe why using multiple hash functions is a good idea. + All of the experiments suggest that the proposed MFH approach outperforms HashedNets. On the negative side, - The computation cost seems worse than HashedNets and is not discussed. - Immediate practical implication of the paper is not clear given that alternative pruning strategies perform better and should be faster at inference. That said, I believe this paper benefits the deep learning community as it sheds light into ways to share parameters across layers of a neural network potentially leading to more interesting follow-ups. I recommend accept, while asking the authors to address the comments below. More comments: - Please discuss the computation cost for both HashedNets and MFH for both fully connected and convolutional layers. - Are the experiments only run once for each configuration? Please run multiple times and report average / standard error. - For completeness, please add U1 results to Table 1. - In Table 1, U4-G3 is listed twice with two different numbers. - Some sentences are not grammatically correct. Please improve the writing.