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 | edit source]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 | edit source]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 | edit source]- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ a b c Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ a b Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ 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]
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
