AND/OR Multi-Valued Decision Diagrams (AOMDDs) for Weighted Graphical
  Models
  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.
