Mateescu, Robert and Dechter, Rina and Marinescu, Radu (2008) AND/OR Multi-Valued Decision Diagrams (AOMDDs) for Graphical Models. Journal of Artificial Intelligence Research, 33 (2605). pp. 465-519. ISSN 1076-9757 http://resolver.caltech.edu/CaltechAUTHORS:MATjair08
Restricted to Caltech community only
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:MATjair08
Inspired by the recently introduced framework of AND/OR search spaces for graphical models, we propose to augment Multi-Valued Decision Diagrams (MDD) with AND nodes, in order to capture function decomposition structure and to extend these compiled data structures to general weighted graphical models (e.g., probabilistic models). We present the AND/OR Multi-Valued Decision Diagram (AOMDD) which compiles a graphical model into a canonical form that supports polynomial (e.g., solution counting, belief updating) or constant time (e.g. equivalence of graphical models) queries. We provide two algorithms for compiling the AOMDD of a graphical model. The first is search-based, and works by applying reduction rules to the trace of the memory intensive AND/OR search algorithm. The second is inference-based and uses a Bucket Elimination schedule to combine the AOMDDs of the input functions via the the APPLY operator. For both algorithms, the compilation time and the size of the AOMDD are, in the worst case, exponential in the treewidth of the graphical model, rather than pathwidth as is known for ordered binary decision diagrams (OBDDs). We introduce the concept of semantic treewidth, which helps explain why the size of a decision diagram is often much smaller than the worst case bound. We provide an experimental evaluation that demonstrates the potential of AOMDDs.
|Additional Information:||© 2008 AI Access Foundation. Submitted 05/08; published 12/08. This work was done while Robert Mateescu and Radu Marinescu were at the University of California, Irvine. The authors would like to thank the anonymous reviewers for their constructive suggestions to improve the paper, David Eppstein for a useful discussion of complexity issues, and Lars Otten and Natasha Flerova for comments on the final version of the manuscript. This work was supported by the NSF grants IIS-0412854 and IIS-0713118, and the initial part by the Radcliffe fellowship 2005-2006 (through the partner program), with Harvard undergraduate student John Cobb.|
|Subject Keywords:||KNOWLEDGE COMPILATION; CONSTRAINT NETWORKS; REPRESENTATION; INFERENCE|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Jason Perez|
|Deposited On:||10 Feb 2009 00:08|
|Last Modified:||26 Dec 2012 10:48|
Repository Staff Only: item control page