Fast Reconstruction of Mixtures of Bernoulli Product Distributions

Mixtures of Bernoulli product distributions are a simple and widely used latent-variable model, with applications in e.g.\ recommendation systems, crowdsourcing, and medical data analysis. We consider the problem of reconstructing the mixture parameters from oracle access to its probability generating polynomial (PGP), for instance represented by a probabilistic generating circuit (PGC). We show that the parameters are uniquely identifiable for almost all mixtures, and give a randomized algorithm that exactly recovers the mixture weights and component marginals for mixtures of $r$ Bernoulli product distributions over $n$ variables using only $O(nr^2)$ oracle queries. The algorithm repeatedly applies restrictions to $O(r)$ variables, extracts low-degree coefficients, and then recovers the parameters using a moment-based tensor decomposition. To the best of our knowledge, this is the {\em first} exact reconstruction algorithm in this PGP oracle model with query complexity linear in $n$ and polynomial in $r$.

A group of three athletes often race against each other and as a coach you get to witness the outcomes of these races. However, the performance of each athlete often depends on some hidden factors like how well they slept, did they have carbs before the race, etc. As a coach, you want them to figure out these parameters to have a better understanding of what makes the particular athlete perform better. However, it is often a challenging task to reconstruct the hidden factors from only the race outcomes. Now, similar problems also arise in many pressing real world situations where you need to make fast decisions, and hence not only reconstructing the factors, but also doing it quickly becomes paramount. In this work, we give a fast algorithm to do exactly this by isolating small batches of variables to perfectly reconstruct them. In our method, the workload scales linearly with the number of variables, paving the way for faster, more accurate diagnostics and recommendation systems.