AND/OR Multi-Valued Decision Diagrams (AOMDDs) for Weighted Graphical Models
This work addresses the challenge of efficient compilation for probabilistic and weighted graphical models, which is incremental as it builds on existing frameworks like AND/OR search spaces and OBDDs.
The authors tackled the problem of compiling weighted graphical models by introducing AND/OR Multi-Valued Decision Diagrams (AOMDDs), a novel data structure that generalizes previous work on constraint networks and is based on AND/OR search spaces and Ordered Binary Decision Diagrams. The result is a canonical representation with size and compilation time bounded exponentially by the treewidth of the graph, rather than pathwidth as in OBDDs, and preliminary experiments show encouraging potential.
Compiling graphical models has recently been under intense investigation, especially for probabilistic modeling and processing. We present here a novel data structure for compiling weighted graphical models (in particular, probabilistic models), called AND/OR Multi-Valued Decision Diagram (AOMDD). This is a generalization of our previous work on constraint networks, to weighted models. The AOMDD is based on the frameworks of AND/OR search spaces for graphical models, and Ordered Binary Decision Diagrams (OBDD). The AOMDD is a canonical representation of a graphical model, and its size and compilation time are bounded exponentially by the treewidth of the graph, rather than pathwidth as is known for OBDDs. We discuss a Variable Elimination schedule for compilation, and present the general APPLY algorithm that combines two weighted AOMDDs, and also present a search based method for compilation method. The preliminary experimental evaluation is quite encouraging, showing the potential of the AOMDD data structure.