Affine Algebraic Decision Diagrams (AADDs) and their Application to Structured Probabilistic Inference

Sanner, Scott; McAllester, David A.

Affine Algebraic Decision Diagrams (AADDs) and their Application to Structured Probabilistic Inference

Download BibTeX Cite

Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 1384-1389.

Abstract

We propose an affine extension to ADDs (AADD) capable of compactly representing context-specific, additive, and multiplicative structure. We show that the AADD has worstcase time and space performance within a multiplicative constant of that of ADDs, but that it can be linear in the number of variables in cases where ADDs are exponential in the number of variables. We provide an empirical comparison of tabular, ADD, and AADD representations used in standard Bayes net and MDP inference algorithms and conclude that the AADD performs at least as well as the other two representations, and often yields an exponential performance improvement over both when additive or multiplicative structure can be exploited. These results suggest that the AADD is likely to yield exponential time and space improvements for a variety of probabilistic inference algorithms that currently use tables or ADDs.

Scott Sanner, and David A. McAllester. 2005. Affine Algebraic Decision Diagrams (AADDs) and their Application to Structured Probabilistic Inference. In Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05. IJCAI, 1384–1389. https://ijcai.org/proceedings/2005/181

@inproceedings{ijcai2005p181,
  title     = {Affine Algebraic Decision Diagrams (AADDs) and their Application to Structured Probabilistic Inference},
  author    = {Sanner, Scott and McAllester, David A.},
  booktitle = {Proceedings of the Nineteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-05}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  pages     = {1384--1389},
  year      = {2005},
  url       = {https://ijcai.org/proceedings/2005/181},
}

TY  - CPAPER
TI  - Affine Algebraic Decision Diagrams (AADDs) and their Application to Structured Probabilistic Inference
AU  - Sanner, Scott
AU  - McAllester, David A.
T2  - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2005
SP  - 1384
EP  - 1389
UR  - https://ijcai.org/proceedings/2005/181
ER  -