There has been a recent trend in training neural networks to replace data structures that have been crafted by hand, with an aim for faster execution, better accuracy, or greater compression. In this setting, a neural data structure is instantiated by training a network over many epochs of its inputs until convergence. In many applications this expensive initialization is not practical, for example streaming algorithms -where inputs are ephemeral and can only be inspected a small number of times. In this paper we explore the learning of approximate set membership over a stream of data in one-shot via meta-learning. We propose a novel memory architecture, the Neural Bloom Filter, which we show can be more compressive than Bloom Filters and several existing memory-augmented neural networks.
SUMMARY
The paper proposes a neural network based architecture to solve the approximate set membership problem, in the distributional setting where the in-set and out-of-set elements come from two unknown and possibly different distributions.
COMMENTARY
The topic of the paper is interesting, and falls into the popular trend of enhancing classical data structures with learning algorithms. For the approximate set membership problem, this approach was already suggested by (Kraska et al. 2018) and studied further in (Mitzenmacher 2018a,b). The difference in the current paper is that the proposed approach relies on "meta-learning", apparently to facilitate online training and/or learning across multiple sets arising from the same distribution; this is what I gather from the introduction, even though as I write below, I feel this point is not properly explained.
My main issue with the paper is that its conceptual contribution seems limited and unclear. It suggests a specific architecture whose details seem mostly arbitrary, or at least this is the impression the reader is left with, as the paper does rather little in terms of discussing and motivating them or putting them in context. Moreover, since the solution ultimately relies on a backup Bloom Filter as in (Kraska et al. 2018), it is hard to not view it as just an instantiation of the model in (Kraska et al. 2018, Mitzenmacher 2018a) with a different plugging of learning component. It would help to flesh out and highlight what the authors claim are the main insights of the paper.
Another issue I suggest revising pertains to the writing. The problem setting is only loosely sketched but not properly defined. How exactly do different subsets coming into play? Specifically, the term "meta-learning" appears in the title and throughout the paper, but is never defined or explained. The authors should write out what exactly they mean by this notion and what role it plays in the paper. This is important since to my understanding, this is the main point of departure from the aforementioned recent works on learning-enhanced Bloom Filters.
The experiments do not seem to make a strong case for the empirical advantage of the Neural Bloom Filter. They show little to no improvement on the MNIST tasks, and some improvement on a non-standard database related task. One interesting thing to look at would be the workload partition between the learning component and the backup filter, meaning what is the rate of false negatives emitted by the former and caught by the latter, and how the space usage breaks down between them (vis-a-vis the formula in Appendix B). For example, it seems plausible that on the class familiarity task, the learning component simply learns to be a binary classifier for the chosen two MNIST classes and mostly ignores the backup filter, whereas in the uniform distribution setting, the learning component only memorizes a small number of true and false positives and defers almost the entire task to the backup filter. I am not sure what to expect on the intermediate exponential distribution task.
Other comments/questions:
1. For the classical Bloom Filter, do the results reported in the experimental plots reflect the empirical false-positive rate measured in the experiment, or just the analytic bound?
2. On that note, it is worth noting that the false positive rate of the classical Bloom Filter is different than the one you report for the neural-net based architectures. The Bloom Filter FP probability is over its internal randomness (i.e. its hash functions) and is independent of the distribution of queries, which need not be randomized at all. For the neural-net based architectures, the measured FP rate is w.r.t. a specific distribution of queries. See the discussion in (Mitzenmacher 2018a), sections B-C.
3. The works (Mitzenmacher 2018a,b) should probably at least be referenced in the related work section.
CONCLUSION
While I like the overall topic of the paper, I currently find the conceptual contribution to be too thin, raising doubts on novelty and significance. In addition, the presentation is somewhat lacking in clarity, and the practical merit is not well established. Notwithstanding the public nature of ICLR submissions, I would suggest more work on the paper prior to publication.
REFERENCES
M. Mitzenmacher, A Model for Learned Bloom Filters and Related Structures, 2018, see https://arxiv.org/pdf/1802.00884.pdf.
M. Mitzenmacher, Optimizing Learned Bloom Filters by Sandwiching, 2018, see https://arxiv.org/pdf/1803.01474.pdf.
(Update: score revised, see below.)