Venue: ICLR 2017 conference

Reviews:

final_score: rating: null
review_content: As far as I can tell, this paper is proposing to apply multiple hashes and take the union, as opposed to taking a single hash of input or output values. While the intuition about bloom filters is nice, at the end of the day, this technique is just producing a smaller, but more dense, binary vector, is that correct? 

Also, what is the computational complexity of decoding the output? The bloom filter can tell you quickly if a given element is in the set. But for producing a sparse output it looks like the suggested procedure is just to iterate over all possible outputs...which defeats the purpose of a fast sparse coding of the output.

Can you discuss in more detail also how this will affect neural models that learn embeddings of the input? A straightforward application of your method would suggest that you represent each input as a sum of embeddings indexed by random hashes. Is that correct?  Is there anything further going on here?
review_title: Can you discuss the implications for representation learning?

final_score: rating: null
review_content: Thank you for this very interesting paper. While Bloom filters have already been used to encode outputs in multilabel classification, the paper makes a more general contribution by using it for inputs and outputs, and in particular gives a method to apply bloom filters for ranking tasks.

Some questions regarding the experiments:

1) As far as I understood the "dimensionality ratio" is the compression applied to both inputs and outputs, as far as this is applicable (e.g., I suppose input compression is not performed for PTB). In case compression was applied to both (e.g., recommendation), did you try different compression ratios in the input ?

2) regarding the use of bloom filters for input encoding: bloom filters do not encode counts of objets, but some extensions do. In particular for recommendation tasks with count data, to what extent the suppression of the counts affects performance ? 

3) Some Deep Learning libraries have layers specialized for sparse inputs (e.g., SparseLinear in torch, which behaves exactly like a Linear layer). When timings are reported, do they use such implementations ? In particular, the Bloom filter approach for the inputs leads to inputs that are *less* sparse (but in smaller dimension), so I think it is important on the exact implementation when reporting timings.

4) When using bloom filters on the output, I suppose the baseline uses a sofmax activation layer. However, since all your evaluations are in terms of ranking and not in terms of perplexity/log-likelihood, a pairwise ranking loss could be used instead of softmax+cross-entropy, making it possible to severely subsample the negative classes during training (each epoch would essentially cost about the number of positive labels, even though this doesn't say anything about the overall training time nor on the final accuracy). Did you experiment with such losses ?
review_title: questions on experiments and baselines

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper presents the idea of using Bloom filter encodings on the input features and the output layer of deep network to reduce the size of the network. Bloom-filter like encodings were proposed in Shi et al. (JMLR 2009) "Hash Kernels for Structured Data" (see Theorem 2 and its proof), whereas it was proposed to encode the outputs in the context of multilabel classification in Cisse et al. (NIPS 2013) "Robust Bloom Filters for Large MultiLabel Classification Tasks". The paper still joins both ideas together, applies it to ranking problems, and presents extensive experiments in the context of deep neural networks and language modelling.

The main motivation of the paper is the reduction of model size for deep neural networks. There is a whole body of literature on this topic,  that is not mentioned at all in the paper, where the baselines are based on weight quantization (with an available implementation in TensorFlow https://github.com/tensorflow/tensorflow/tree/master/tensorflow/contrib/quantization). More recent methods are e.g.,

1) the model compression approach of https://arxiv.org/abs/1510.00149
2) training with integer/binary weights https://arxiv.org/abs/1511.00363

Overall, the advantage of the Bloom filter approach is its simplicity and its wide applicability -- it could, as well, be used in conjunction with weight quantization and other compression methods. The main merits of the paper is to present extensive experiments on how well the vanilla Bloom filter approach can perform, but overall the novelty is fairly limited.
review_title: a lot of interesting experiments but limited novelty

final_score: rating: 3: Clear rejection
review_content: Description:

This paper aims at compressing binary inputs and outputs of neural network models with unsupervised "Bloom embeddings".

The embedding is based on Bloom filters: projecting an element of a set to different positions of a binary array by several independent hash functions, which allows membership checking with no missed but with possibly some false positives.

Inputs and outputs are assumed to be sparse. The nonzero elements of an input are then simply encoded by Bloom filters onto the same binary array. The neural network is run with the embedded inputs.

Desired outputs are assumed to be a softmax-type ranking of different alternatives. a sort of back-projection step is needed to recover a probability ranking of the desired ground truth alternatives from the lower-dimensional output. For each ground-truth class, this is simply approximated as a product of the output values at the Bloom-filtered hash positions of that class.

The paper simply applies this idea, testing it on seven data sets. Scores and training times are compared to the baseline networks without embeddings. Comparison embedding methods are mostly very traditional (hashing trick, error-correcting output codes, linear projection by canonical correlation analysis) but include one recent pairwise mutual information based approach.


Evaluation:

It is hard to see a lot of novelty in this paper. The Bloom filters are an existing technique, which is applied very straightforwardly here. The back-projection step of equation 2 is also a straightforward continuous-valued variant of the Bloom-filter membership test.

The way of recovering outputs is heuristic, since the neural network inbetween the embedded inputs and outputs is not really aware that the outputs will be run through a further back-projection step.

In the comparisons of Table 3, only two embedding dimensionalities are used for each data set. This is insufficient, since it leaves open the question whether other methods could get improved performance for higher/lower embeddings, relative to the proposed method. (In appendix B, Figure 4, authors do compare their method to a variant of it for many different embedding dimensionalities; why not do this for all comparison methods too?)

Overall, this seems for the most part too close to off-the-shelf existing embedding to be acceptable.


Minor points:

As the paper notes, dimensionality reduction of inputs by various techniques is common. The paper lists some simple embeddings such as SVD based ones, CCA etc. but a more thorough review of other approaches including the vast array of nonlinear dimensionality reduction solutions should be mentioned.

The experiments in the paper seem to have an underlying assumption that inputs and outputs need to have the same type of embedding dimension. This seems unnecessary.

review_title: Straightforward application of Bloom filter embedding and membership checking, not a lot of novelty; experiments should test more dimensionalities

final_score: rating: 6: Marginally above acceptance threshold
review_content: The authors propose a simple scheme based on Bloom filters to generate embeddings for inputs and outputs.  This reduces memory while introducing limited computational overhead, and it is simple enough to implement that it can easily be added to any practitioner's toolbox.

Pros:

- Can be applied to practically any model, either at the input or hte output.
- Method is very straightforward: apply multiple hashes, instead of single one. The algorithm for decoding is nice too. 

Cons:

- The paper is a bit difficult to read; the idea is really simple so it doesn't seem like it warrants such a complex description.
- The novelty of the approach is a bit limited since, as other reviewers have mentioned, Bloom filters are in use in a lot of areas including multi-label classification.

This seems like it would be a good short paper. There's a lot of well fleshed out experiments, but the core of the paper is a bit incremental.
review_title: Straightforward but marginal impact

Meta-review: The authors present a simple scheme based on Bloom filters to generate embeddings for inputs and outputs. On the one hand, the scheme is simple, it reduces memory while introducing limited computational overhead. On the other hand, reviewers were concerned with the limited novelty of the approach, which diminishes quite a bit its impact. Overall, this paper is just a pinch too borderline.
Decision: Reject