On Inference and Learning With Probabilistic Generating Circuits

Juha Harviainen, Vaidyanathan Peruvemba Ramaswamy, Mikko Koivisto

Tutkimustuotos: ArtikkelijulkaisuKonferenssiartikkeliTieteellinenvertaisarvioitu

Abstrakti

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.

Alkuperäiskielienglanti
LehtiProceedings of Machine Learning Research
Vuosikerta216
Sivut829-838
Sivumäärä10
ISSN2640-3498
TilaJulkaistu - 2023
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaConference on Uncertainty in Artificial Intelligence - Carnegie Mellon University, Pittsburgh, PA, Yhdysvallat (USA)
Kesto: 31 heinäk. 20234 elok. 2023
Konferenssinumero: 39
https://www.auai.org/uai2023/

Lisätietoja

Publisher Copyright:
© UAI 2023. All rights reserved.

Tieteenalat

  • 113 Tietojenkäsittely- ja informaatiotieteet

Siteeraa tätä