Sentential decision diagram
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.[1]
Properties
[edit]SDDs are defined with respect to a generalization of variable ordering known as a variable tree (vtree).[2]
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.[2]
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.[2] They also allow for polynomial-time model counting.[3][4]
SDDs are known to be exponentially more succinct than OBDDs.[5]
Applications
[edit]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.[3] SDDs have also been extended to model probability distributions, in which context they are known as probabilistic sentential decision diagrams (PSDD).[6]
References
[edit]- ^ Darwiche, Adnan; Marquis, Pierre; Suciu, Dan; Szeider, Stefan (2018). Recent trends in knowledge compilation (Report). Schloss Dagstuhl.
- ^ a b c Darwiche, Adnan (2011). "SDD: A New Canonical Representation of Propositional Knowledge Bases". International Joint Conference on Artificial Intelligence.
- ^ a b Riguzzi, Fabrizio (2023). Foundations of probabilistic logic programming: Languages, semantics, inference and learning (2nd ed.). Gistrup, Denmark: River Publishers. p. 214. ISBN 978-87-7022-719-3.
- ^ 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). [1]
- ^ Bova, Simone (2016). SDDs are exponentially more succinct than OBDDs. AAAI Conference on Artificial Intelligence.
- ^ Kisa, Doga; Van den Broeck, Guy; Choi, Arthur; Darwiche, Adnan (2014). Probabilistic Sentential Decision Diagrams. International Conference on the Principles of Knowledge Representation and Reasoning (KR).
 | This artificial intelligence-related article is a stub. You can help Wikipedia by expanding it. |
