Learning the Structure of Probabilistic Sentential Decision Diagrams

Yitao Liang, Jessa Bekker, Guy Van den Broeck
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:501-510, 2017.

Abstract

The probabilistic sentential decision diagram (PSDD) was recently introduced as a tractable representation of probability distributions that are subject to logical constraints. Meanwhile, efforts in tractable learning achieved great suc- cess inducing complex joint distributions from data without constraints, while guaranteeing efficient exact probabilistic inference; for in- stance by learning arithmetic circuits (ACs) or sum-product networks (SPNs). This pa- per studies the efficacy of PSDDs for the stan- dard tractable learning task without constraints and develops the first PSDD structure learn- ing algorithm, called LEARNPSDD. Experi- ments on standard benchmarks show competi- tive performance, despite the fact that PSDDs are more tractable and more restrictive than their alternatives. LEARNPSDD compares fa- vorably to SPNs, particularly in terms of model size, which is a proxy for tractability. We re- port state-of-the-art likelihood results on six datasets. Moreover, LEARNPSDD retains the ability to learn PSDD structures in probability spaces subject to logical constraints, which is beyond the reach of other representations.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-liang17a, title = {Learning the Structure of Probabilistic Sentential Decision Diagrams}, author = {Liang, Yitao and Bekker, Jessa and Broeck, Guy Van den}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {501--510}, year = {2017}, editor = {Elidan, Gal and Kersting, Kristian}, volume = {R15}, series = {Proceedings of Machine Learning Research}, month = {11--15 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r15/main/assets/liang17a/liang17a.pdf}, url = {https://proceedings.mlr.press/r15/liang17a.html}, abstract = {The probabilistic sentential decision diagram (PSDD) was recently introduced as a tractable representation of probability distributions that are subject to logical constraints. Meanwhile, efforts in tractable learning achieved great suc- cess inducing complex joint distributions from data without constraints, while guaranteeing efficient exact probabilistic inference; for in- stance by learning arithmetic circuits (ACs) or sum-product networks (SPNs). This pa- per studies the efficacy of PSDDs for the stan- dard tractable learning task without constraints and develops the first PSDD structure learn- ing algorithm, called LEARNPSDD. Experi- ments on standard benchmarks show competi- tive performance, despite the fact that PSDDs are more tractable and more restrictive than their alternatives. LEARNPSDD compares fa- vorably to SPNs, particularly in terms of model size, which is a proxy for tractability. We re- port state-of-the-art likelihood results on six datasets. Moreover, LEARNPSDD retains the ability to learn PSDD structures in probability spaces subject to logical constraints, which is beyond the reach of other representations.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Learning the Structure of Probabilistic Sentential Decision Diagrams %A Yitao Liang %A Jessa Bekker %A Guy Van den Broeck %B Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2017 %E Gal Elidan %E Kristian Kersting %F pmlr-vR15-liang17a %I PMLR %P 501--510 %U https://proceedings.mlr.press/r15/liang17a.html %V R15 %X The probabilistic sentential decision diagram (PSDD) was recently introduced as a tractable representation of probability distributions that are subject to logical constraints. Meanwhile, efforts in tractable learning achieved great suc- cess inducing complex joint distributions from data without constraints, while guaranteeing efficient exact probabilistic inference; for in- stance by learning arithmetic circuits (ACs) or sum-product networks (SPNs). This pa- per studies the efficacy of PSDDs for the stan- dard tractable learning task without constraints and develops the first PSDD structure learn- ing algorithm, called LEARNPSDD. Experi- ments on standard benchmarks show competi- tive performance, despite the fact that PSDDs are more tractable and more restrictive than their alternatives. LEARNPSDD compares fa- vorably to SPNs, particularly in terms of model size, which is a proxy for tractability. We re- port state-of-the-art likelihood results on six datasets. Moreover, LEARNPSDD retains the ability to learn PSDD structures in probability spaces subject to logical constraints, which is beyond the reach of other representations. %Z Reissued by PMLR on 04 October 2026.
APA
Liang, Y., Bekker, J. & Broeck, G.V.d.. (2017). Learning the Structure of Probabilistic Sentential Decision Diagrams. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:501-510 Available from https://proceedings.mlr.press/r15/liang17a.html. Reissued by PMLR on 04 October 2026.

Related Material