CaltechAUTHORS
  A Caltech Library Service

AND/OR Multi-Valued Decision Diagrams (AOMDDs) for Graphical Models

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. https://resolver.caltech.edu/CaltechAUTHORS:MATjair08

[img] PDF
Restricted to Caltech community only
See Usage Policy.

804Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:MATjair08

Abstract

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://www.jair.org/papers/paper2605.htmlPublisherUNSPECIFIED
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.
Funders:
Funding AgencyGrant Number
National Science FoundationIIS-0412854
National Science FoundationIIS-0713118
Radcliffe fellowship, Harvard UniversityUNSPECIFIED
Subject Keywords:KNOWLEDGE COMPILATION; CONSTRAINT NETWORKS; REPRESENTATION; INFERENCE
Issue or Number:2605
Record Number:CaltechAUTHORS:MATjair08
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:MATjair08
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:13324
Collection:CaltechAUTHORS
Deposited By: Jason Perez
Deposited On:10 Feb 2009 00:08
Last Modified:03 Oct 2019 00:36

Repository Staff Only: item control page