Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
AND/OR Multi-Valued Decision Diagrams (AOMDDs) for Weighted Graphical Models
Robert Mateescu, Rina Dechter
Abstract:
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.
Keywords:
Pages: 276-284
PS Link:
PDF Link: /papers/07/p276-mateescu.pdf
BibTex:
@INPROCEEDINGS{Mateescu07,
AUTHOR = "Robert Mateescu and Rina Dechter",
TITLE = "AND/OR Multi-Valued Decision Diagrams (AOMDDs) for Weighted Graphical Models",
BOOKTITLE = "Proceedings of the Twenty-Third Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-07)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2007",
PAGES = "276--284"
}


hosted by DSL   •   site info   •   help