Learning Probabilistic Sentential Decision Diagrams by Sampling
Resumo
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.
Referências
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.
