Scalable Learning of Probabilistic Circuits
Resumo
Probabilistic circuits (PCs) are a family of tractable probabilistic models capable of answering a wide range of queries exactly and in polytime. While inference is usually straightforward, learning PCs that both obey the needed restrictions for inference tractability and exploit their expressive power has proven to be a challenge. This dissertation aims to propose fast and scalable structure learning algorithms for PCs from two different standpoints: from a logical point of view, we efficiently construct a PC that takes certain knowledge in the form of logical constraints and scalably translate them into a probabilistic circuit; from the viewpoint of data guided structure search, we propose hierarchically building PCs from random hyperplanes. We empirically show that either approach is competitive against state-of-the-art methods of the same class in both performance and scalability.
Referências
Bova, S. (2016). Sdds are exponentially more succinct than obdds. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence.
Choi, A. and Darwiche, A. (2013). Dynamic minimization of sentential decision diagrams. In Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence.
Choi, A., den Broeck, G. V., and Darwiche, A. (2015). 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.
Correia, A. H. C., Peharz, R., and de Campos, C. (2020). Joints in random forests. In Advances in Neural Information Processing Systems 33 (NeurIPS).
Dang, M., Vergari, A., and den Broeck, G. V. (2020). Strudel: Learning structured-decomposable probabilistic circuits. In Proceedings of the 10th International Conference on Probabilistic Graphical Models.
Dasgupta, S. and Freund, Y. (2008). Random projection trees and low dimensional manifolds. In Proceedings of the fortieth annual ACM symposium on Theory of computing.
Dempster, A. P., Laird, N. M., and Rubin, D. B. (1977). Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society. Series B (Methodological).
Freund, Y., Dasgupta, S., Kabra, M., and Verma, N. (2008). Learning the structure of manifolds using random projections. In Advances in Neural Information Processing Systems.
Geh, R., Mauá, D., and Antonucci, A. (2020). Learning probabilistic sentential decision diagrams by sampling. In Proceedings of the VIII Symposium on Knowledge Discovery, Mining and Learning.
Geh, R. L. and Mauá, D. D. (2021). Fast and accurate learning of probabilistic circuits by random projections. In The 4th Tractable Probabilistic Modeling Workshop.
Geh, R. L. and Mauá, D. D. (2021). Learning probabilistic sentential decision diagrams under logic constraints by sampling and averaging. In Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence.
Gens, R. and Domingos, P. (2013). Learning the structure of sum-product networks. In Proceedings of the 30th International Conference on Machine Learning.
Jaini, P., Ghose, A., and Poupart, P. (2018). Prometheus: Directly learning acyclic directed graph structures for sum-product networks. In International Conference on Probabilistic Graphical Models.
Kisa, D., den Broeck, G. V., Choi, A., and Darwiche, A. (2014). Probabilistic sentential decision diagrams. Knowledge Representation and Reasoning Conference.
Liang, Y., Bekker, J., and den Broeck, G. V. (2017). Learning the structure of probabilistic sentential decision diagrams. In Proceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence.
Lowd, D. and Davis, J. (2010). Learning markov network structure with decision trees. In 2010 IEEE International Conference on Data Mining.
Mauro, N. D., Gala, G., Iannotta, M., and Basile, T. M. A. (2021). Random probabilistic circuits. In Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence.
Monteith, K., Carroll, J. L., Seppi, K., and Martinez, T. (2011). Turning bayesian model averaging into bayesian model combination. In The 2011 International Joint Conference on Neural Networks.
Oztok, U. and Darwiche, A. (2015). A top-down compiler for sentential decision diagrams. In Proceedings of the 24th International Conference on Artificial Intelligence.
Shen, Y., Choi, A., and Darwiche, A. (2017). A tractable probabilistic model for subset selection. In Proceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence.
Smyth, P. and Wolpert, D. (1998). Stacked density estimation. In Advances in Neural Information Processing Systems.
Van Haaren, J. and Davis, J. (2012). Markov network structure learning: A randomized feature generation approach. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence.
Choi, A. and Darwiche, A. (2013). Dynamic minimization of sentential decision diagrams. In Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence.
Choi, A., den Broeck, G. V., and Darwiche, A. (2015). 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.
Correia, A. H. C., Peharz, R., and de Campos, C. (2020). Joints in random forests. In Advances in Neural Information Processing Systems 33 (NeurIPS).
Dang, M., Vergari, A., and den Broeck, G. V. (2020). Strudel: Learning structured-decomposable probabilistic circuits. In Proceedings of the 10th International Conference on Probabilistic Graphical Models.
Dasgupta, S. and Freund, Y. (2008). Random projection trees and low dimensional manifolds. In Proceedings of the fortieth annual ACM symposium on Theory of computing.
Dempster, A. P., Laird, N. M., and Rubin, D. B. (1977). Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society. Series B (Methodological).
Freund, Y., Dasgupta, S., Kabra, M., and Verma, N. (2008). Learning the structure of manifolds using random projections. In Advances in Neural Information Processing Systems.
Geh, R., Mauá, D., and Antonucci, A. (2020). Learning probabilistic sentential decision diagrams by sampling. In Proceedings of the VIII Symposium on Knowledge Discovery, Mining and Learning.
Geh, R. L. and Mauá, D. D. (2021). Fast and accurate learning of probabilistic circuits by random projections. In The 4th Tractable Probabilistic Modeling Workshop.
Geh, R. L. and Mauá, D. D. (2021). Learning probabilistic sentential decision diagrams under logic constraints by sampling and averaging. In Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence.
Gens, R. and Domingos, P. (2013). Learning the structure of sum-product networks. In Proceedings of the 30th International Conference on Machine Learning.
Jaini, P., Ghose, A., and Poupart, P. (2018). Prometheus: Directly learning acyclic directed graph structures for sum-product networks. In International Conference on Probabilistic Graphical Models.
Kisa, D., den Broeck, G. V., Choi, A., and Darwiche, A. (2014). Probabilistic sentential decision diagrams. Knowledge Representation and Reasoning Conference.
Liang, Y., Bekker, J., and den Broeck, G. V. (2017). Learning the structure of probabilistic sentential decision diagrams. In Proceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence.
Lowd, D. and Davis, J. (2010). Learning markov network structure with decision trees. In 2010 IEEE International Conference on Data Mining.
Mauro, N. D., Gala, G., Iannotta, M., and Basile, T. M. A. (2021). Random probabilistic circuits. In Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence.
Monteith, K., Carroll, J. L., Seppi, K., and Martinez, T. (2011). Turning bayesian model averaging into bayesian model combination. In The 2011 International Joint Conference on Neural Networks.
Oztok, U. and Darwiche, A. (2015). A top-down compiler for sentential decision diagrams. In Proceedings of the 24th International Conference on Artificial Intelligence.
Shen, Y., Choi, A., and Darwiche, A. (2017). A tractable probabilistic model for subset selection. In Proceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence.
Smyth, P. and Wolpert, D. (1998). Stacked density estimation. In Advances in Neural Information Processing Systems.
Van Haaren, J. and Davis, J. (2012). Markov network structure learning: A randomized feature generation approach. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence.
Publicado
06/08/2023
Como Citar
GEH, Renato Lui; MAUÁ, Denis Deratani.
Scalable Learning of Probabilistic Circuits. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 36. , 2023, João Pessoa/PB.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 138-147.
ISSN 2763-8820.
DOI: https://doi.org/10.5753/ctd.2023.229457.
