Sentential decision diagram
{{Short description|Data structure for Boolean functions}}
In artificial intelligence, a sentential decision diagram (SDD) is a type of knowledge representation used in knowledge compilation to represent Boolean functions. SDDs can be viewed as a generalization of the influential ordered binary decision diagram (OBDD) representation, by allowing decisions on multiple variables at once. Like OBDDs, SDDs allow for tractable Boolean operations, while being exponentially more succinct. For this reason, they have become an important representation in knowledge compilation. {{cite report |title=Recent trends in knowledge compilation |last1=Darwiche |first1=Adnan |last2=Marquis |first2=Pierre |date=2018 |publisher=Schloss Dagstuhl |last3=Suciu |first3=Dan |last4=Szeider |first4=Stefan}}
Properties
SDDs are defined with respect to a generalization of variable ordering known as a variable tree (vtree).{{cite journal |last1=Darwiche |first1=Adnan |date=2011 |title=SDD: A New Canonical Representation of Propositional Knowledge Bases |journal=International Joint Conference on Artificial Intelligence}}
Provided that they satisfy additional properties known as compression and trimming (which are analogous to ROBDDs), SDDs are a canonical representation of Boolean functions; that is, they are unique given a vtree.
Like OBDDs, they allow for operations such as conjunction, disjunction and negation to be computed directly on the representation in polynomial time, while being potentially more compact. They also allow for polynomial-time model counting.{{Cite book |last=Riguzzi |first=Fabrizio |title=Foundations of probabilistic logic programming: Languages, semantics, inference and learning |publisher=River Publishers |year=2023 |isbn=978-87-7022-719-3 |edition=2nd |location=Gistrup, Denmark |pages=214}}Vlasselaer, J., Renkens, J., Van den Broeck, G., & De Raedt, L. (2014). Compiling probabilistic logic programs into sentential decision diagrams. In Proceedings Workshop on Probabilistic Logic Programming (PLP) (pp. 1-10). [https://lirias.kuleuven.be/retrieve/275254]
SDDs are known to be exponentially more succinct than OBDDs. {{cite conference |last1=Bova |first1=Simone |title=SDDs are exponentially more succinct than OBDDs |conference=AAAI Conference on Artificial Intelligence |date=2016}}
Applications
SDDs are used as a compilation target for probabilistic logic programs by the ProbLog 2 system since they support tractable (weighted) model counting as well as tractable negation, conjunction and disjunction while being more succinct than BDDs. SDDs have also been extended to model probability distributions, in which context they are known as probabilistic sentential decision diagrams (PSDD). {{cite conference|last1=Kisa |first1=Doga |last2=Van den Broeck| first2=Guy |last3=Choi |first3=Arthur|last4=Darwiche|first4=Adnan |title=Probabilistic Sentential Decision Diagrams |conference=International Conference on the Principles of Knowledge Representation and Reasoning (KR) |date=2014}}
References
{{reflist}}
Category:Graph data structures
Category:Knowledge compilation
{{Compu-ai-stub}}
{{Diagrams in logic}}