Linear Time Generative Inference in Neural Probabilistic Circuits

Neural Probabilistic Circuits (NPCs) are neuro-symbolic models that combine both the recognition capacity of modern neural networks and the tractable reasoning of probabilistic circuits. In NPCs, a neural network predicts human-interpretable attributes from the input, and a follow-up probabilistic circuit models the joint distribution of those attributes and the class label. To connect the two modules, the existing inference procedure in NPCs averages the circuit’s class conditional probabilities over all attribute configurations, both during training and at test time. In the worst case, the average operation costs time exponential in the number of attributes, which limits the scalability of NPCs to applications with at most tens of attributes. To overcome the above limitation, we propose a new inference procedure, which we term as the generative inference, that averages each class by the joint probability, rather than the class conditional probability, over the network’s attribute predictions. We show that under factorized attribute predictions from the neural network module, each smooth and decomposable circuit can instead compute the overall prediction exactly in one forward pass of the circuit, which reduces the inference time complexity from exponential in the number of attributes to linear in the circuit size. Our key insight that enables the exponential reduction lies in the observation that factorized functions over the leaf nodes in a smooth and decomposable circuit can be absorbed into the leaf factors, hence effectively exploiting the tractability of circuits. Empirically, the generative inference helps lift NPCs to datasets with hundreds of attributes, which the original discriminative inference cannot scale to. In terms of statistical performance, by reusing the generative inference during learning, we demonstrate that the learned NPCs are at least comparable to, and sometimes better than the original NPCs.