AND/OR multi-valued decision diagrams (AOMDDs) for weighted graphical models

Compiling graphical models has recently been under intense investigation, especially for prob-abilistic modeling and processing. We present here a novel data structure for compiling weighted graphical models (in particular, prob-abilistic models), called AND/OR Multi-Valued Decision Diagram (AOMDD). This is a general-ization of our previous work on constraint net-works, 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 ex-ponentially by the treewidth of the graph, rather than pathwidth as is known for OBDDs. We dis-cuss a Variable Elimination schedule for compi-lation, and present the general APPLY algorithm that combines two weighted AOMDDs, and also present a search based method for compilation method. The preliminary experimental evalua-tion is quite encouraging, showing the potential of the AOMDD data structure.