Streaming, Distributed Variational Inference for Bayesian Nonparametrics
This paper presents a methodology for creating streaming, distributed inference algorithms for Bayesian nonparametric (BNP) models. In the proposed framework, processing nodes receive a sequence of data minibatches, compute a variational posterior for each, and make asynchronous streaming updates to a central model. In contrast to previous algorithms, the proposed framework is truly streaming, distributed, asynchronous, learning-rate-free, and truncation-free. The key challenge in developing the framework, arising from the fact that BNP models do not impose an inherent ordering on their components, is finding the correspondence between minibatch and central BNP posterior components before performing each update. To address this, the paper develops a combinatorial optimization problem over component correspondences, and provides an efficient solution technique. The paper concludes with an application of the methodology to the DP mixture model, with experimental results demonstrating its practical scalability and performance.
Review Summary ============== Score: 6, Marginally above the acceptance thresholdThe proposed method for streaming, distributed inference of DP mixture models presents a nice solution to the cluster identification problem, backed by experiments that are convincing though not rock solid. I'm hesitant to recommend unconditional acceptance, because basic information about how new clusters are created at each minibatch are totally absent, hurting reproducibility.Summary of Paper ================This paper develops a new algorithm for streaming, distributed variational inference for the DP mixture model, with some supplementary material suggesting how to use these insights for many other BNP models. Using a mean-field approximation, the authors consider how to allow multiple worker nodes to process data batches in parallel and then aggregate these results asynchronously. In particular, the authors offer a new solution to the "component identification" problem: how to find correspondence between new clusters created independently by two separate worker nodes. This solution finds an optimal assignment for each new cluster from the current minibatch, merging it with another new cluster if advantageous but keeping it separate otherwise. The optimization objective for this assignment is derived via applying Jensen's inequality to the exchangeable partition probability function (EPPF), which works out nicely for the DP case and applies to some other BNP models.Experiments compare the proposed algorithm in detail to several other methods for DP mixture models.Toy data experiments show that with the proposed component identification scheme, they see big speedup using many workers (up to 48) without loss in predictive performance.Furthermore, the authors report computation time and test log likelihood on 3 "real-world" datasets, showing their method achieves among the best testLL scores in much less time, often with 10x-100x speedup over other methods.Technical Comments on Method ============================My biggest concern here is that the paper lacks details about what exactly happens at each minibatch, and especially how exactly new clusters are created for that minibatch.Line 356 says the proposed approach is coupled with "standard variational inference" (Blei & Jordan 2006), but this is a well-known fixed truncation method and does not create new clusters at all.It seems the proposed component identification method applies regardless of the specific creation procedure used, but not specifying any details about creation is serious cause for concern. In my experience, the single most important feature of a BNP inference method is how successfully it creates high-quality new clusters that are missing from the current model.A related concern is that the presented merge scheme in Sec. 3.2 only applies to merging *new* clusters with other new clusters (created by different nodes). Many existing papers highlight ways to merge or remove existing clusters in approximate inference [eg Lin's ref 7, Bryant & Sudderth ref 11]. Without these moves, in my experience junky new clusters can overwhelm good ones. The proposed method does not handle this at all, and so likely underperforms.A final concern is that the current exposition does not compare and contrast the proposed DP mixture regularization bound (Eq 9) with existing mean-field variational objectives (e.g. from Blei and Jordan 2006 or Hughes & Sudderth 2013). Adding some of these bounds to Fig 2 would be interesting. It's unclear whether the proposed bound leads to a coherent overall bound on the marginal likelihood... I think so but it should be stated more obviously. It's also unclear even what objective function is used within a minibatch for SDA-DP: the proposed one? or the one from Blei and Jordan 2006?.Technical Comments on Experiments =================================The toy data results (Fig 3) are pretty convincing, though if you have 2D data showing plots of learned cluster parameters overlaid with data is nice. My big question here is that from Fig 3e it seems most runs do not recover all K=100 true clusters, instead usually about 90 or 95. This screams local optima to me, and I'm curious whether this might go away with a longer run (if so, how long would you need to run?), or whether the algorithm does really gets stuck if even run for a while and fails to create these missing clusters. Finally, figure 3b shows no visible speedup from 24 to 48 workers... is this because the problem is too small for effective parallelization? Or due to overhead from locking/unlocking?I'm less convinced by the experiments in Fig. 4. First, please plot traces of algorithm performance, rather than using a table, to communicate more information in the same amount of space. Second, lots of experimental details are missing: how was prior set? how were competitor methods initialized? what final number of clusters is reached for each dataset? was just one run used, or the best of multiple runs of each method? did you do many passes through the dataset, or just one pass? Third, some of the Airplane testLL numbers are so low (esp. for SVA and SC) that it's hard to know whether to blame local optima, buggy code, or what, but I'd expect both of these to perform better.Overall, the lack of detail makes these experiments hard to evaluate and hard to reproduce. It's also unclear how performance is sensitive to batch size, and whether competitor algorithms were allowed to vary the truncation... did the SVA runs use that paper's merge/prune moves? did the moVB runs include that paper's birth and merge moves? did SVI and Batch just use fixed truncation?Novelty ======= Other work provides the basic framework for mean-field inference [ref 24, etc.] and streaming/asynchronous Bayesian computation [ref 5, etc] used here. The real contribution is the new framing of the "component identification" problem, which I have not seen adequately addressed in prior work, and especially the concrete bound for the DP mixture case.Significance ============ The problem of general-purpose scalable inference for BNP models is definitely worth studying. The proposed approach could likely be adopted by others considering that it is based on the EPPF.Clarity =======I could follow the main arguments without too much trouble, but in many places (like around Eq 10) the authors relied too heavily on math notation and lacked motivating narrative. Around Eq. 10, I'd recommend adding text offering interpretations of the statistics s and t used for computing the regularization bound.Another possible improvement: In figure 1, remove the nodes for y_t illustrating data batches (which dont add much) and instead make the focus on the cluster parameters. Perhaps show two different cycles of a,b,c,d, so the reader better understands how the number of cluster parameters grows over time and what the "component identification" problem is ... maybe highlight the edges that need to be optimized in c from those that are known in advance.Line-by-line Comments ===================== (not necessary to respond to these in rebuttal)Lines 51-52: ref 13 does not seem to require a learning rateFig 2a: The "U"-shaped bend with large alpha is real but not very intuitive. Could use some commentary. Also, labeling some specific alpha values would help interpret the plot.Line 289: Saying "the bound increases as K -> 0" might suggest to non-experts that for any N, the DP's preferred number of clusters is very small, which is definitely not true.