Optimal Time-Space Tradeoff in Probabilistic Inference

1 Introduction

Recursive Conditioning, RC, was recently proposed as an any-space algorithm for exact inference in Bayesian net­ works [Darwiche, 2001]. The algorithm works by using con­ ditioning to decompose a network into smaller subnetworks that are then solved independently and recursively using RC. It turns out that many of the subnetworks generated by this decomposition process need to be solved multiple times re­ dundantly, allowing the results to be stored in a cache after the first computation and then subsequently fetched during further computations. This gives the algorithm its any-space behavior since any number of results may be cached. This also leads to an important question, which is the subject of this paper: "Given a limited amount of memory, which re­ sults should be cached in order to minimize the running time of the recursive conditioning algorithm?"

We approach this problem by formulating it as a system­ atic search problem. We then use the developed method to construct time-space tradeoff curves for some real-world Bayesian networks, and put these curves in perspective by comparing them to the memory requirements of state-of­ the-art methods based on join trees [Jensen et al., 1990; Shafer and Shenoy, 1990]. The curves produced illustrate that a significant amount of memory can be reduced with only a minimal cost in time. In fact, for much of their domains, the time-space curves we produce appear close to linear, with ex­ ponential behavior appearing only near the extreme case of no caching. This dramatic space reduction, without a significant time penalty, allows one to practically reason with Bayesian networks that would otherwise be impractical to handle.

This paper is structured as follows. We start in Section 2 by providing some background on recursive conditioning and the cache allocation problem. We then formulate this prob­ lem in Section 3 as a systematic search problem. Time-space tradeoff curves for several published Bayesian networks are then presented in Section 4. Finally, in Section 5, we provide some concluding remarks and discuss some future work.

2 Any-Space Inference

The RC algorithm for exact inference in Bayesian networks works by using conditioning and case analysis to decompose a network into smaller subnetworks that are solved indepen­ dently and recursively. The algorithm is driven by a structure known as a decomposition tree (dtree), which controls the de­ composition process at each level of the recursion. We will first review the dtree structure and then discuss RC.

2.1 Dtrees

Definition 1 [Darwiche, 200 I} A dtree for a Bayesian net­ work is a full binary tree, the leaves of which correspond to the network conditional probability tables (CPTs). If a leaf node t corresponds to a CPT¢. then vars(t) is defined as the variables appearing in CPT¢.

Figure 1 depicts a simple dtree. The root node t of the dtree represents the entire network. To decompose this network, the dtree instructs us to condition on variable B, called the cutset of root node t. Conditioning on a set of variables leads to removing edges outgoing from these variables, which for a cutset is guaranteed to disconnect the network into two sub­ networks, one corresponding to the left child of node t and another corresponding to the right child of node t; see Fig­ ure 1. This decomposition process continues until a boundary condition is reached, which is a subnetwork that has a single variable.

We will now present some notation needed to define ad­ ditional concepts with regard to a dtree. The notation t1 and tr will be used for the left child and right child of node t, and the function vars will be extended to internal nodes t: vars(t) ~ vars( tt) Uvars(tr ). Each node in a dtree has three more sets of variables associated with it. The first two ofthese sets are used by the RC algorithm, while the third set is used to analyze the complexity of the algorithm.

Definition 2 The cutset of internal node t in a dtree is: cutset( t) d:f vars( t1) n vars( tr) - a cutset( t ), where a cutset( t) is the union of cutsets associated with ancestors of node t in the dtree. The context of node t in a dtree is: context(t) d:f vars(t) n acutset(t). The cluster of node tin a dtree is: cutset(t) U context(t) ift is a non-leaf, and as vars(t) ift is a leaf

The width of a dtree is the size of its maximal cluster -1.

The cutset of a dtree node t is used to decompose the net­ work associated with node t into the smaller networks asso­ ciated with the children oft. That is, by conditioning on vari­ ables in cutset(t), one is guaranteed to disconnect the net­ work associated with node t. The context of dtree node t is used to cache results: Any two computations on the net­ work associated with node twill yield the same result if these computations occur under the same instantiation of variables in context(t). Hence, a cache is associated with each dtree node t, which stores the results of such computations (proba­ bilities) indexed by instantiations of context(t). This means that the size of a cache associated with dtree node t can grow as large as the number of instantiations of context( t).

For a given Bayesian network, many different dtrees exist and the quality of the dtree significantly affects the resource requirements of RC. The width is one important measure of this, as RC's time complexity is exponential in this value. The construction of dtrees is beyond the scope of this paper, but in [Darwiche, 2001; Darwiche and Hopkins, 2001] it was shown how to create them from elimination orders, jointrees,

Algorithm 1 RC(t): Returns the probability of evidence e recorded on the dtree rooted at t. I: if t is a leaf node then 2: return LOOKUP(t) 3: else 4: y +--recorded instantiation of context(t) 5: if cache?(t) and cachet[y] # nil then 6: return cachet [y] 7: else 8: p +-- 0 9: for instantiations c ofuninstantiated vars in cutset(t) do I 0: record instantiation c II: p +-- p + RC(tz)RC(lr) 12: un- record instantiation c 13: when cache?(t), cachet[y] +-- p 14: return p Algorithm 2 LOOKUP(t). ¢> +-- CPT of variable X associated with leaf t if X is instantiated then x +-- recorded instantiation of X u +--recorded instantiation of X's parents return ¢>(xfu) II ¢>(xfu) = Pr(xfu) else return 1

or directly by using the hMeTiS [Karypis and Kumar, 1998] hypergraph partitioning program.

2.2 Recursive Conditioning

Given a Bayesian network and a corresponding dtree with root t, the RC algorithm given in Algorithms 1 and 2 can be used to compute the probability of evidence e by first "record­ ing" the instantiation e and then calling RC(t), which returns the probability of e.

Our main concern here is with Line 5 and Line 13 of the algorithm. On Line 5, the algorithm checks whether it has performed and cached this computation with respect to the subnetwork associated with node t. A computation is charac­ terized by the instantiation oft's context, which also serves as an index into the cache attached to node t. If the com­ putation has been performed and cached before, its result is simply fetched. Otherwise, the computation is performed and its result is possibly cached on Line 13.

When every computation is cached, RC uses 0( n exp( w)) space and O(nexp(w)) time, where n is the number of nodes in the network and w is the width of the dtree. This cor­ responds to the complexity of jointree algorithm, assuming that the dtree is generated from a jointree [Darwiche, 2001 ]. When no computations are cached, the memory requirement ofRC is reduced to O(n), in which case the time requirement increases to O(nexp(w logn)). Any amount of memory be­ tween these two extremes can also be used in increments of the size of a floating point number, a cache value.

Suppose now that the available memory is limited and we can only cache a subset of the computations performed by RC. The specific subset that we cache can have a dramatic ef­ fect on the algorithm's running time. A key question is then to choose that subset which minimizes the running time, which is the main objective of this paper. We refer to this as the secondary optimization problem, with the first optimization problem being that of constructing an optimal dtree.

Most of our results in this paper are based on a version of RC which not only computes the probability of evidence e, but also posterior marginals over families and, hence, poste­ rior marginals over individual variables. This version of RC uses a decomposition graph (dgraph), which is basically a set of dtrees that share structure.

An example dgraph for a network with four variables can be seen in Figure 2. It should be noted that each of the four root nodes corresponds to a valid dtree, so this dgraph ac­ tually contains four dtrees which share a significant portion of their structure. Creation of dgraphs is discussed in [Dar­ wiche, 2002].

The code in Algorithms 1 and 2 is also used in this ver­ sion of RC, where RC(t) is called once on each root t of the dgraph (the posterior marginal of each family is computed as a side effect of each of these calls). This version of RC uses more memory as it maintains more caches. But it is more meaningful when it comes to comparing our time-space tradeoff curves with the memory requirements of join tree al­ gorithms, as this version of RC is equally powerful to these algorithms.

3 The Cache Allocation Problem

The total number of computations that a dgraph (or dtree) node t needs to cache equals the number of instantiations of context(t) . Given a memory constraint, however, one may not be able to cache all these computations, and we need a way to specify which results in particular to cache. A cache factor cf for a dgraph is a function which maps each internal node t in the dgraph into a number cf ( t) between 0 and 1. Hence, if cf(t) = .75, then node t can only cache 75% of these total computations. A discrete cache factor is one which maps every internal dgraph node into either 1 or 0: all of the node's computations are cached, or none are cached. The RC code in Algorithms 1 and 2 assumes a discrete cache factor, which is captured by the flag cache?(t), indicating whether caching will take place at dgraph node t.

One can count the number of recursive calls made by RC (and, hence, compute its running time) given any discrete cache factor. Specifically, if tP denotes a parent of node t in a dgraph, and S# denotes the number of instantiations of variables S, the number of recursive calls made to node t is [Darwiche, 2001 ; 2002]:

If the cache factor is not discrete, the above formula gives the average number of recursive calls, since the actual number of calls will depend on the specific computations cached. This equation is significant as it can be used to predict the expected time requirement ofRC under a given caching scheme.

We focus in this paper on searching for an optimal dis­ crete cache factor, given a limited amount of memory, where optimality is with respect to minimizing the number of recur­ sive calls. To this end, we will first define a search problem for finding an optimal discrete cache factor and then develop a depth-first branch-and-bound search algorithm. We will also use the developed algorithm to construct the time-space tradeoff curves for some published Bayesian networks from various domains, and compare these curves to the memory demands and running times of jointree algorithms.

3.1 Cache Allocation as a Search Problem

The cache allocation problem can be phrased as a search problem in which states in the search space correspond to partial cache factors that do not violate the given memory constraint, and where an operator extends a partial cache fac­ tor by making a caching decision on one more dgraph node. The initial state in this problem is the empty cache factor, in which no caching decisions have been made for any nodes in the dgraph. The goal states correspond to complete cache factors, where a caching decision has been made for every dgraph node, without violating the given memory constraint. Suppose for example that we have a dgraph with three inter­ nal nodes h , t2 , t3 . This will then lead to the search tree in Figure 3. In this figure, each node n in the search tree repre­ sents a partial cache factor cf. For example, the node in bold corresponds to the partial cache factor cf(h) = 0, cj(t2) = 1 and cf(t 3 ) = ?. Moreover, if node n is labeled with a dgraph node t i , then the children of n represent two possible exten­ sions of the cache factor cf: one in which dgraph node t i will cache all computations (1- child), and another in which dgraph node ti will cache no computations (0-child).

According to the search tree in Figure 3, one always makes a decision on dgraph node t 1 , followed by a decision on dgraph node t2, and then node t3 . A fixed ordering of dgraph nodes is not necessary, however, as long as the following con­ dition is met: A decision should be made on a dgraph node ti only after decisions have been made on all its ancestors in the dgraph. We will explain the reason for this constraint later on when we discuss cost functions.

In the search tree depicted in Figure 3, the leftmost leaf represents no caching, while the rightmost leaf represents full caching. The search trees for this problem have a maximum depth of d, where d is the number of internal nodes in the dgraph. Given this property, depth-first branch-and-bound search is a good choice given its optimality and linear space complexity [Papadimitriou and Steiglitz, 1998]. It is also an anytime algorithm, meaning that it can always return its best result so far if interrupted, and if run to completion will return the optimal solution. Hence, we will focus on developing a depth-first branch-and-bound search algorithm.

3.2 Cost Functions

The depth-first branch-and-bound (DFBnB) algorithm re­ quires a cost function f which assigns a cost f ( n) to every node n in the search tree. The function f(n) estimates the cost of an optimal solution that passes through n. The key here is that f ( n) must not overestimate that cost; otherwise, one loses the optimality guarantee offered by the search algo­ rithm. We will now develop such a cost function f ( n) based on the following observations. Since each node n represents a partial cache factor cf, function f ( n) must estimate the num­ ber of recursive calls made to RC based on an optimal com­ pletion of cache factor cf. Consider now the completion cf' of cf in which we decide to cache at each dgraph node that cf did not make a decision on. This cache factor cf' is the best completion of cf from the viewpoint of running time, but it may violate the constraint given on total memory. Yet, we will use it to compute f(n) as it guarantees that f(n) will never overestimate the cost of an optimal completion of cf .

One important observation in this regard is that once the caching decision is made on the ancestors of dgraph node t, we can compute exactly the number of recursive calls that will be made to dgraph node t (see Equation 1). Therefore, when extending a partial cache factor, we will always insist on making a decision regarding a dgraph node t for which decisions have been made on all its ancestors. This improves the quality of the estimate f ( n) as n gets deeper in the tree. It also allows us to incrementally compute this estimate based on the estimate of n 's parent in the search tree.

3.3 Pruning

As depicted by the search tree in Figure 3, there is potentially an exponential number of goal nodes in the search tree and the combinatorial explosion of exhaustive search can become unmanageable very quickly. Hence the search algorithm must eliminate portions of the search space while still being able to guarantee an optimal result. One of the key methods of doing this is by pruning parts of the search tree which are known to contain non-optimal results. The DFBnB algorithm does this by pruning search tree nodes when the cost function f ( n) is larger than or equal to the current best solution. Hence, more accurate cost functions will allow more pruning. Another ma­ jor source of pruning is the given constraint on total memory. This is accomplished by pruning a search tree node and all its descendants once it attempts to assign more memory to caches than is permitted by the memory constraint.

3.4 Search Decisions

Now that we have chosen a cost function, we are still left with two important choices in our search algorithm: ( 1) which child of a search tree node to expanded first, and (2) in what order to visit dgraph nodes during search. Expanding the 1child first is a greedy approach, as it attempts to fully cache at a dgraph node whenever possible. Results on many dif­ ferent networks have shown that in many cases, expanding the 1-child before the 0-child appears to be equal to or bet­ ter than the opposite, and it is this choice that we adopt in our experiments. The specific order in which we visit dgraph nodes in the search tree turns out to have an even more dra­ matic effect on the efficiency of search. Even though we make caching decisions on parent dgraph nodes before their chil­ dren, there is still a lot of flexibility. Our experimentation on many networks has shown that choosing the dgraph node t with the largest context(t)# is orders of magnitude more ef­ ficient than some other basic ordering heuristics [Allen and Darwiche, 2002]. This choice corresponds to choosing the dgraph node with the largest cache, and it is the one we use in our search algorithm.

4 Time-Space Tradeoff

The main goal of this section is to present time-space tradeoff curves for a number of benchmark Bayesian networks, some of which are obtained from [Bayesian Network Repository, URL] and others are included in the distributions of [Hugin Expert, URL; GeNie, URL]. The main points to observe with respect to each curve is the slope of the curve, which pro­ vides information on the time penalty one pays when reduc­ ing space in probabilistic inference. The second main point is to compare the produced curves with the time and space requirement of jointree methods, as the version of RC we are using provides the same functionality as these algorithms (that is, probability of evidence and posterior marginals over families and variables). This baseline comparison is impor­ tant as it places our results in the context of state-of-the- art inference systems.

Time-space tradeoff curves. Figures 4, 5, and 6 depict optimal discrete time-space tradeoff curves for three net­ works. These curves were generated as follows. A join­ tree was first generated for the network using Hugin. 1 The

1 We used Hugin's default setting: the minimum fill-in weight heuristic in conjunction with prime component analysis.

0 "

Figure 4: Time-space tradeoff on Alarm.

B.net OGraph · RC Calls (All) vs Cache

jointree was then converted into a dtree as described in [Dar­ wiche, 2001] . The dtree was finally converted into a dgraph as described in the full paper. Two sets of results were then generated:

• We computed the space requirements for jointree algo­ rithms, using both the Hugin [Jensen eta/., 1990] and Shenoy-Shafer [Shafer and Shenoy, 1990] architectures. For the first architecture, we assumed one table for each clique and one table for each separator. For the sec­ ond, we assumed two tables for each separator (no ta­ bles for cliques). We also performed propagation on the jointree using Netica [Norsys Software Corp., URL] and recorded the running time.
• We then ran our search algorithm to find an optimal cache factor under different memory constraints, where we generated 100 data points for each curve. For each caching factor that we identified, we computed the num­ ber of recursive calls that will be made by RC under that factor and converted the calls to seconds. 2

2 0ur Java implementation of RC on a Sun Ultra 10, 440 MHz

A number of observations are in order here. First, these time­ space tradeoff curves show that the amount of memory used by RC under full caching is very close to that required by the Shenoy-Shafer architecture (the Hugin architecture takes much more space). Second, the curves show that a signifi­ cant amount of memory can sometimes be reduced from full caching with only a limited increase in the time required; in fact, the exponential growth appears to be occurring only near the lower extreme of no caching. The space requirement for Water (Figure 6), for example, can be reduced to 30% while only increasing the running time by a factor of 6. Moreover, the space requirements for B (Figure 5) can be reduced to about 2.5% while increasing the running time by a factor of 20. Finally, we note that each optimal search for the Water and B networks took less than two seconds, and each opti­ mal search for Alarm took less than two minutes. We stress though that such searches need to be done only once for a network, and their results can then be used for many further queries.

Non-optimal tradeoffs. On some networks, the search space is too large to solve optimally using our search algo­ rithm, but the anytime nature of the algorithm allows us to interrupt the search at any point and ask for the best result obtained thus far. Figures 7 and 8 were generated by allow­ ing the search to run for an hour. Even though these curves are not optimal, they are useful practically. For example, ac­ cording to these curves, the memory requirement of Barley can be reduced from about 22 MB to about 6.5 MB while only increasing the running time from about 1 to 4 minutes. Moreover, the space requirement of Munin I can be reduced from about 370MB to 150MB, while increasing the running time from about 22 minutes to about 6 hours. Encouraged by such results, we are planning to investigate other (non­ optimal) search methods, such as local search.

Dtrees vs dgraphs. Running RC on a dtree takes less space than running it on a dgraph, but produces much less information (probability of evidence instead of posterior marginals). To illustrate this difference concretely, we present in Figure 9 two tradeoff curves for the Water network, assum­ ing a dtree version of RC, which require much less memory compared to the curves in Figure 6. Suppose now that we only have 1 MB of memory, instead of the 7.6 MB or 30.2 MB required by jointree algorithms, and we want to compute the posterior marginals for all variables. According to Fig­ ure 6, we can do this in 669 seconds using the dgraph version of RC. The dtree version takes 16.7 seconds to compute the probability of evidence under this amount of memory, and we would have to run it 85 times to produce all posterior marginals for the Water network (given variable cardinalities in Water).

computer with 256MB of RAM, makes an average number of three million recursive calls per second.

Effect of dtree/dgraph on tradeoff. Our notion of op­ timality for tradeoff is based on a given dtree/dgraph; hence, generating different dtrees/dgraphs could possibly lead to bet­ ter time-space tradeoff curves. To illustrate this point, we generated tradeoff curves for the Water network based on multiple dtrees/graphs, as shown in Figures 6 and 9. One ob­ servation that we came across is that dtrees/graphs that are based on jointrees tend to require less memory under full caching, but are not necessarily best for tradeoff towards the no caching region; see Figures 6 for an example. Yet, we used such dtrees/graphs in this paper in an effort to provide a clear baseline for comparison with jointree methods. If we relax this constraint, however, we can obtain better trade­ off curves than is generally reported here, as illustrated by Figures 6 and 9. The specific way in which properties of a dtree/dgraph influence the quality of corresponding time­ space tradeoff curves is not very well understood, however, and we hope to shed more light on this in future work.

Size of search space. It should be noted that the difficulty of obtaining an optimal time- space tradeoff curve on some networks is not due to a large space requirement, but is due mostly to the number of nodes in the Bayesian network as that is what decides the size of search space. To further illustrate this point, we generated a network randomly with 40 nodes (many of them non-binary), 86 edges, and a width of 14. This network requires extensive memory but has a relatively small number of variables. In fact, both Netica and Hugin were un­ able to compile the network requiring about 6 GB and 11 GB respectively. We were able, however, to produce an optimal time-space tradeoff curve for this network. The curve for the dtree version of RC is shown in Figure 10. According to this curve, we can compute the probability of any evidence on this network in about 2 hours using only about 75 MB.

Related work. We close this section by a note on re­ lated work for time-space tradeoff in probabilistic reasoning, which takes a different approach [Dechter and Fattah, 2001]. In this work, large separators in a jointree are removed by combining their adjacent clusters, which has the effect of re­ ducing the space requirements of the Shenoy-Shafer architec­ ture (as we now have fewer separators), but also increasing its running time (as we now have larger clusters). The tradeoffs permitted by this approach, however, are coarser than those permitted by RC as discussed in [Darwiche, 2001]. Further­ more, the secondary optimization problem of which separa­ tors to remove in order to minimize running time is not ad­ dressed in [Dechter and Fattah, 2001] for the proposed ap­ proach, as we do in this paper for the RC approach.

5 Conclusions and Future Work

The main contribution of this paper is a formal framework, and a corresponding working system, for trading space for time when designing probabilistic reasoning systems based on Bayesian networks. The proposal is based on the algo­ rithm of recursive conditioning, and is accompanied with a set of experimental results showing that a significant amount of memory can sometimes be reduced while only incurring a reasonable penalty in running time. The proposed frame­ work is then beneficial for designing reasoning systems with limited memory, as in embedded systems, and for reasoning with challenging networks on which jointree algorithms can exhaust the system memory.

Recursive conditioning and the described time-space tradeoff system have been implemented in JAVA in the SAMIAM tool, which is available publically [UCLA Auto­ mated Reasoning Group, URL].

Acknowledgments

This work has been partially supported by NSF grant IIS9988543 and MURI grant NOOO 14-00-1-0617.