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 worst-case 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.
Introduction
In probabilistic AI, representing and manipulating functions over numerous boolean variables is a fundamental challenge. Algebraic Decision Diagrams (ADDs) have long served as the standard tool for this task, utilizing a directed acyclic graph structure to merge redundant branches and save space. However, ADDs suffer from a significant limitation: they cannot efficiently represent additive and multiplicative structures. For a simple sum like $f = 4a + 2b + c$, an ADD must create a unique terminal node for every possible combination of values, leading to an exponential explosion in size. This "kryptonite" makes standard ADDs impractical for many real-world problems in Bayesian networks and Markov Decision Processes (MDPs) where such structures—like Noisy-OR gates or cumulative rewards—are prevalent.
The AADD Framework
To address these limitations, we introduce the Affine Algebraic Decision Diagram (AADD). The core innovation is the addition of an affine transformation to every edge. Instead of a node simply pointing to a child, it points to a child through a transformation of the form $c + bF$, where $c$ is an offset and $b$ is a multiplier.
Key technical components of the AADD include:
- Canonical Representation: To ensure that identical functions have a unique representation in memory (essential for caching), we enforce a normalization scheme where every internal node's range is mapped to $[0, 1]$.
- The
ApplyAlgorithm: A recursive algorithm was developed to perform binary operations—such as addition, multiplication, and min/max—directly on these affine-weighted diagrams. - Numerical Hashing: To handle floating-point precision errors that might prevent exact node matching, we implemented a bucket-based hashing scheme using Euclidean distance to group nearly-identical nodes.
Experimental Results
The AADD was evaluated against standard tabular and ADD representations across synthetic operations, Bayesian networks (e.g., Alarm, Barley, Insurance), and MDPs (SysAdmin domain).
The most striking result is the reduction from exponential to linear complexity for functions with additive or multiplicative independence. As shown in the scaling tests for the Sum function, AADDs maintain linear growth in the number of nodes while ADDs and tables explode exponentially.
In practical benchmarks:
- Noisy-Or-15: For a Bayesian network with 15 parents, the ADD required over 125,000 nodes and 50 seconds. The AADD required only 1,066 nodes and finished in 0.7 seconds.
- Barley Network: While tabular and ADD representations exceeded 1GB of memory, the AADD successfully completed inference using approximately 60,000 nodes.
- MDP Value Iteration: In the SysAdmin domain, AADDs exploited the additive nature of reward functions to solve significantly larger problem sizes than previously possible with ADDs.
Discussion and Conclusion
The AADD provides a "worst-case safe" extension to decision diagrams; in scenarios where no affine structure exists, the AADD is only a constant factor larger than a standard ADD. However, when such structure is present, the performance gains are exponential.
Future work will address the sensitivity to numerical precision in very deep diagrams and the ongoing challenge of optimal variable ordering. Nonetheless, these results suggest that the AADD is a powerful replacement for ADDs in a wide variety of probabilistic inference algorithms, offering substantial improvements in both time and space efficiency.
Summary updated