UAI 2023 Oral Session 6: On Inference and Learning With Probabilistic Generating Circuits скачать в хорошем качестве

UAI 2023 Oral Session 6: On Inference and Learning With Probabilistic Generating Circuits

"On Inference and Learning With Probabilistic Generating Circuits" Juha Harviainen, Vaidyanathan Peruvemba Ramaswamy, Mikko Koivisto (https://proceedings.mlr.press/v216/ha...) Abstract Probabilistic generating circuits (PGCs) are economical representations of multivariate probability generating polynomials (PGPs). They unify and extend decomposable probabilistic circuits and determinantal point processes, admitting tractable computation of marginal probabilities. However, the need for addition and multiplication of high-degree polynomials incurs a significant additional factor in the complexity of inference. Here, we give a new inference algorithm that eliminates this extra factor. Specifically, we show that it suffices to keep track of the highest degree coefficients of the computed polynomials, rendering the algorithm linear in the circuit size. In addition, we show that determinant-based circuits need not be expanded to division-free circuits, but can be handled by division-based fast algorithms. While these advances enhance the appeal of PGCs, we also discover an obstacle to learning them from data: it is NP-hard to recognize whether a given PGC encodes a PGP. We discuss the implications of our ambivalent findings and sketch a method, in which learning is restricted to PGCs that are composed of moderate-size subcircuits. Slides: https://www.auai.org/uai2023/oral_sli...