Large-scale Distributed Dependent Nonparametric Trees

Practical applications of Bayesian nonparamet-ric (BNP) models have been limited, due to their high computational complexity and poor scal-ing on large data. In this paper, we consider dependent nonparametric trees (DNTs), a pow-erful infinite model that captures time-evolving hierarchies, and develop a large-scale distribut-ed training system. Our major contributions in-clude: (1) an effective memoized variational in-ference for DNTs, with a novel birth-merge s-trategy for exploring the unbounded tree space; (2) a model-parallel scheme for concurrent tree growing/pruning and efficient model alignmen-t, through conflict-free model partitioning and lightweight synchronization; (3) a data-parallel scheme for variational parameter updates that al-lows distributed processing of massive data. Us-ing 64 cores in 36 hours, our system learns a 10K-node DNT topic model on 8M documents that captures both high-frequency and long-tail topics. Our data and model scales are orders-of-magnitude larger than recent results on the hier-archical Dirichlet process, and the near-linear s-calability indicates great potential for even bigger problem sizes. 1