Learning Probabilistic Sentential Decision Diagrams by Sampling

  • Renato Geh University of São Paulo
  • Denis Mauá University of São Paulo
  • Alessandro Antonucci Istituto Dalle Molle di Studi sull'Intelligenza Artificiale


Probabilistic circuits are deep probabilistic models with neural-network-like semantics capable of accurately and efficiently answering probabilistic queries without sacrificing expressiveness. Probabilistic Sentential Decision Diagrams (PSDDs) are a subclass of probabilistic circuits able to embed logical constraints to the circuit’s structure. In doing so, they obtain extra expressiveness with empirical optimal performance. Despite achieving competitive performance compared to other state-of-the-art competitors, there have been very few attempts at learning PSDDs from a combination of both data and knowledge in the form of logical formulae. Our work investigates sampling random PSDDs consistent with domain knowledge and evaluating against state-of-the-art probabilistic models. We propose a method of sampling that retains important structural constraints on the circuit’s graph that guarantee query tractability. Finally, we show that these samples are able to achieve competitive performance even on larger domains.

Palavras-chave: artificial intelligence, machine learning, probabilistic circuits, probabilistic sentential decision diagrams, propositional logic


Akers, S. B. Binary decision diagrams. IEEE Trans. Comput. 27 (6): 509–516, June, 1978.

Bentley, J. and Floyd, B. Programming pearls: A sample of brilliance. Commun. ACM 30 (9): 754–757, Sept., 1987.

Bryant, R. E. Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput. 35 (8): 677–691, Aug., 1986.

Choi, A., den Broeck, G. V., and Darwiche, A. Tractable learning for structured probability spaces: A case study in learning preference distributions. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, Q. Yang and M. J. Wooldridge (Eds.). AAAI Press, pp. 2861–2868, 2015.

Dang, M., Vergari, A., and den Broeck, G. V. Strudel: Learning structured-decomposable probabilistic circuits (to appear). Proceedings of the Tenth International Conference on Probabilistic Graphical Models , 2020.

Darwiche, A. Sdd: A new canonical representation of propositional knowledge bases. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence - Volume Volume Two. IJCAI’11. AAAI Press, Barcelona, Catalonia, Spain, pp. 819–826, 2011.

Gens, R. and Pedro, D. Learning the structure of sum-product networks. In Proceedings of the 30th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 28. PMLR, Atlanta, Georgia, USA, pp. 873–880, 2013.

Kisa, D., den Broeck, G. V., Choi, A., and Darwiche, A. Probabilistic sentential decision diagrams. Knowledge Representation and Reasoning Conference, 2014.

Lee, C. Y. Representation of switching circuits by binary-decision programs. The Bell System Technical Journal 38 (4): 985–999, 1959.

Liang, Y., Bekker, J., and den Broeck, G. V. Learning the structure of probabilistic sentential decision diagrams. In Proceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence, UAI 2017, Sydney, Australia, August 11-15, 2017, G. Elidan, K. Kersting, and A. T. Ihler (Eds.). AUAI Press, 2017.

Mattei, L., Antonucci, A., Mauá, D. D., Facchini, A., and Villanueva Llerena, J. Tractable inference in credal sentential decision diagrams. International Journal of Approximate Reasoning vol. 125, pp. 26 – 48, 2020.

Mattei, L., Soares, D. L., Antonucci, A., Mauá, D. D., and Facchini, A. Exploring the space of probabilistic sentential decision diagrams. In 3rd Workshop of Tractable Probabilistic Modeling. PMLR, 2019.

Poon, H. and Domingos, P. Sum-product networks: A new deep architecture. In Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence. UAI’11. AUAI Press, Arlington, Virginia, USA, pp. 337–346, 2011.

Rahman, T., Kothalkar, P., and Gogate, V. Cutset networks: A simple, tractable, and scalable approach for improving the accuracy of chow-liu trees. In Proceedings of the 2014th European Conference on Machine Learning and Knowledge Discovery in Databases - Volume Part II. ECMLPKDD’14. Springer-Verlag, Berlin, Heidelberg, pp.630–645, 2014.

Shen, Y., Goyanka, A., Darwiche, A., and Choi, A. Structured bayesian networks: From inference to learning with routes. Proceedings of the AAAI Conference on Artificial Intelligence vol. 33, pp. 7957–7965, 07, 2019.
Como Citar

Selecione um Formato
GEH, Renato; MAUÁ, Denis; ANTONUCCI, Alessandro. Learning Probabilistic Sentential Decision Diagrams by Sampling. In: SYMPOSIUM ON KNOWLEDGE DISCOVERY, MINING AND LEARNING (KDMILE), 8. , 2020, Evento Online. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2020 . p. 129-136. DOI: https://doi.org/10.5753/kdmile.2020.11968.