  Noisy-OR Bayesian Networks (BNs) are a family of probabilistic graphical
models which express rich statistical dependencies in binary data. Variational
inference (VI) has been the main method proposed to learn noisy-OR BNs with
complex latent structures (Jaakkola & Jordan, 1999; Ji et al., 2020; Buhai et
al., 2020). However, the proposed VI approaches either (a) use a recognition
network with standard amortized inference that cannot induce
``explaining-away''; or (b) assume a simple mean-field (MF) posterior which is
vulnerable to bad local optima. Existing MF VI methods also update the MF
parameters sequentially which makes them inherently slow. In this paper, we
propose parallel max-product as an alternative algorithm for learning noisy-OR
BNs with complex latent structures and we derive a fast stochastic training
scheme that scales to large datasets. We evaluate both approaches on several
benchmarks where VI is the state-of-the-art and show that our method (a)
achieves better test performance than Ji et al. (2020) for learning noisy-OR
BNs with hierarchical latent structures on large sparse real datasets; (b)
recovers a higher number of ground truth parameters than Buhai et al. (2020)
from cluttered synthetic scenes; and (c) solves the 2D blind deconvolution
problem from Lazaro-Gredilla et al. (2021) and variant - including binary
matrix factorization - while VI catastrophically fails and is up to two orders
of magnitude slower.
