Credal Sentential Decision Diagrams

Alessandro Antonucci, Alessandro Facchini, Lilith Mattei
Proceedings of the Eleventh International Symposium on Imprecise Probabilities: Theories and Applications, PMLR 103:14-22, 2019.

Abstract

Probabilistic sentential decision diagrams are logical circuits annotated by probability mass functions on the disjunctive gates. This allows for a compact representation of joint mass functions consistent with logical constraints. We propose a credal generalisation of the probabilistic quantification of these models, that allows to replace the local probabilities with (credal) sets of mass functions specified by linear constraints. This induces a joint credal set, that sharply assigns probability zero to states inconsistent with the constraints. These models can support cautious estimates of the local parameters when only small amounts of training data are available. Algorithmic strategies to compute lower and upper bounds of marginal and conditional queries are provided. The task can be achieved in linear time with respect to the diagram size for marginal queries. The same can be done for conditional queries if the topology of the circuit is singly connected.

Cite this Paper


BibTeX
@InProceedings{pmlr-v103-antonucci19a, title = {Credal Sentential Decision Diagrams}, author = {Antonucci, Alessandro and Facchini, Alessandro and Mattei, Lilith}, booktitle = {Proceedings of the Eleventh International Symposium on Imprecise Probabilities: Theories and Applications}, pages = {14--22}, year = {2019}, editor = {De Bock, Jasper and de Campos, Cassio P. and de Cooman, Gert and Quaeghebeur, Erik and Wheeler, Gregory}, volume = {103}, series = {Proceedings of Machine Learning Research}, month = {03--06 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v103/antonucci19a/antonucci19a.pdf}, url = {https://proceedings.mlr.press/v103/antonucci19a.html}, abstract = {Probabilistic sentential decision diagrams are logical circuits annotated by probability mass functions on the disjunctive gates. This allows for a compact representation of joint mass functions consistent with logical constraints. We propose a credal generalisation of the probabilistic quantification of these models, that allows to replace the local probabilities with (credal) sets of mass functions specified by linear constraints. This induces a joint credal set, that sharply assigns probability zero to states inconsistent with the constraints. These models can support cautious estimates of the local parameters when only small amounts of training data are available. Algorithmic strategies to compute lower and upper bounds of marginal and conditional queries are provided. The task can be achieved in linear time with respect to the diagram size for marginal queries. The same can be done for conditional queries if the topology of the circuit is singly connected.} }
Endnote
%0 Conference Paper %T Credal Sentential Decision Diagrams %A Alessandro Antonucci %A Alessandro Facchini %A Lilith Mattei %B Proceedings of the Eleventh International Symposium on Imprecise Probabilities: Theories and Applications %C Proceedings of Machine Learning Research %D 2019 %E Jasper De Bock %E Cassio P. de Campos %E Gert de Cooman %E Erik Quaeghebeur %E Gregory Wheeler %F pmlr-v103-antonucci19a %I PMLR %P 14--22 %U https://proceedings.mlr.press/v103/antonucci19a.html %V 103 %X Probabilistic sentential decision diagrams are logical circuits annotated by probability mass functions on the disjunctive gates. This allows for a compact representation of joint mass functions consistent with logical constraints. We propose a credal generalisation of the probabilistic quantification of these models, that allows to replace the local probabilities with (credal) sets of mass functions specified by linear constraints. This induces a joint credal set, that sharply assigns probability zero to states inconsistent with the constraints. These models can support cautious estimates of the local parameters when only small amounts of training data are available. Algorithmic strategies to compute lower and upper bounds of marginal and conditional queries are provided. The task can be achieved in linear time with respect to the diagram size for marginal queries. The same can be done for conditional queries if the topology of the circuit is singly connected.
APA
Antonucci, A., Facchini, A. & Mattei, L.. (2019). Credal Sentential Decision Diagrams. Proceedings of the Eleventh International Symposium on Imprecise Probabilities: Theories and Applications, in Proceedings of Machine Learning Research 103:14-22 Available from https://proceedings.mlr.press/v103/antonucci19a.html.

Related Material