Mini-Buckets: A General Scheme for Generating Approximations in Automated Reasoning

1 Overview

Bucket elimination is a unifying algorithmic frame­ work that generalizes dynamic programming to enable many complex problem-solving and reasoning activities. Among the algorithms that can be accommodated within this framework are directional resolution for propo­ sitional satisfiability [Dechter and Rish, 1994], adap­ tive consistency for constraint satisfaction [Dechter and Pearl, 1987], Fourier and Gaussian elimination for linear inequalities [Lassez and Mahler, 1992], and dynamic pro­ gramming for combinatorial optimization [Bertele and Brioschi, 1972]. Many algorithms for probabilistic infer­ ence, such as belief updating, finding the most proba­ ble explanation, finding the maximum a posteriori hy­ pothesis, and computing the maximum expected utility, also can be expressed as bucket-elimination algorithms [Dechter, 1996].

The main virtues of this framework are simplicity and generality. By simplicity, we mean that extensive ter­ minology is unnecessary for complete specification of bucket-elimination algorithms, thus making the algo­ rithms accessible to researchers working in diverse ar­ eas. More important, their uniformity facilitates the transfer of ideas, applications, and solutions between dis­ ciplines. Indeed, all bucket-elimination algorithms are similar enough to make any improvement to a single al­ gorithm applicable to all others in its class.

·This work was partially supported by NSF grant IRI9157636 and by the Air Force Office of Scientific Research, AFOSR 900136, Rockwell International, and Amada of America.

Normally, an input to a bucket-elimination algorithm is a knowledge base specified by a collection of func­ tions or relations, over subsets of variables (e.g., clauses for propositional satisfiability, constraints and cost func­ tions for constraint optimization, conditional probability matrices for belief networks) . Bucket-elimination algo­ rithms process variables one by one in a given order. In its first step, given a variable ordering, the algorithm partitions these functions into buckets, where the bucket of a particular variable contains the functions defined on that variable, provided the function is not defined on variables higher in that ordering. The next step is to pro­ cess the buckets from top to bottom. When the bucket of variable X is processed, an "elimination procedure" is performed over the functions in its bucket, yielding a new function defined over all the variables mentioned in the bucket, excluding X. This function summarizes the "effect" of X on the remainder of the problem. The new function is placed in a lower bucket. For illustration we include directional resolution, a bucket-elimination algorithm similar to the original Davis-Putnam proce­ dure for satisfiability (Figure 1) and elim-bel, a bucket­ elimination algorithm for belief updating in probabilistic networks (Figure 2).

An important property of variable-elimination algo­ rithms is that their performance can be predicted using a graph parameter, w·, called the induced width [Dechter and Pearl, 1987], also known as tree-width [Arnborg, 1985], which is the largest cluster in an optimal tree­ embedding of a graph. In general, a given theory and its query can be associated with an interaction graph. The complexity of a bucket-elimination algorithm is time and space exponential in the induced width of the problem's interaction graph. The size of the induced width varies with various variable orderings, so each ordering has a different performance guarantee. Although finding the optimal ordering is hard [Arnborg, 1985], heuristics and approximation algorithms are available [Robertson and

Algorithm directional resolution

Input: A cnf theory <p over Q1, .. . , Qn; an ordering d. Output: A decision of whether <p is satisfiable. If it is, a theory Ed( <p ), equivalent to <p; else, an empty di­ rectional extension.

1. Initialize: Generate an ordered partition of the clauses, bucket1, ... , bucketn, where bucket; contains all the clauses whose highest literal is Q;.
2. Backward: For p = n to 1, do:
3. If bucketp contains a unit clause, perform unit reso­ lution. Put each resolvent in its bucket.
4. Else, resolve each pair {(a V Qp), (/3 V ·Qp)} ~ bucketp. If "Y =a V /3 is empty, return Ed('f') = 0, the theory is not sati\fiable; else, determine the index of "Y and add -y to the appropriate bucket.
5. Return: Ed('f') ~ U; bucket;.

Figure 1: Algorithm directional resolution

Algorithm elim-bel

Input: A belief network BN = (G, P), P { P1 , ... , P n}; an ordering of the variables, o X}, ... ,Xn.

Output: The belief of X1 given evidence e.

1. Initialize: Generate an ordered partition of the conditional probability matrices into buckets. bucket; contains all matrices whose highest variable is X;. Put each observation in its bucket. Let S1, ... , Si be the subset of variables in the processed bucket on which matrices (new or old) are defined.
2. Backward: For p +- n downto 1, do: For >.1, >.2, ... , >.j in bucketp, do:
3. (bucket with observed variable) If Xp = Xp appears in the bucket, then substitute Xp = Xp in each matrix >.; and put the results in the appropriate bucket .
4. Else, Up +- UL 1 S; - {Xp}· For all Up = u, >.p(u) = I:.,p IT{=1>.;(xp,us.). Add >.p to the largest index variable in Up.
5. Return: Bel(x1) = aP(x!) ·IT;>.;( xi). (Where the >.; are in bucket1, a is a normalizing con­ stant.)

Figure 2: Algorithm elim-bel

Seymour, 1995).

When a problem has a large induced width, bucket elimination is unsuitable because of its extensive mem­ ory demand. In such cases, approximation algorithms should be attempted. In this paper, we present a col­ lection of parameterized algorithms that have varying degrees of accuracy and efficiency. We demonstrate the general scheme for combinatorial optimization and for the probabilistic task of belief assessment.

2 Preliminaries

Definition 2.1 (graph concepts) A directed graph is a pair, G = {V, E}, where V = {Xt, ... ,X,.} is a set of elements and E = {(X,, Xj )IX,, Xj E V} is the set of edges. For each variable X,, pa(X,) or pa,, is the set of variables pointing to X, in G. A directed graph is acyclic if it has no directed cycles. In an undirected graph, the directions of the arcs are ignored: (X;, Xj) and (X3, X;) are identical. An ordered graph is a pair ( G, d) where G is an undirected graph and d = X 1, ... , Xn is an ordering of the nodes. The width of a node in an ordered graph is the number of the node's neighbors that precede it in the ordering. The width of an ordering d, denoted w(d), is the maximum width over all nodes. The induced width of an ordered graph, w*(d), is the width of the induced ordered graph obtained by processing the nodes from last to first; when node X is processed, all its earlier neighbors in the ordering are connected. The induced width of a graph, W*, is the minimal induced width over all its orderings; it is also known as the tree­ width [Arnborg, 1985]. The moral graph of a directed graph G is the undirected graph obtained by connecting the parents of all the nodes in G and then removing the arrows.

Definition 2.2 (belief network, cost network) Let X = {Xt, ... ,X,.} be a set of random variable! over multivalued domains D1 , ... , D,.. A belief network is a pair (G, P), where · G is a directed acyclic graph and P = {P,}. P; = {P(X,Ipa(X;))} are the condi­ tional probability matrices associated with X,. An a!­ signment (X1 = :Z:t, ... ,X,. = :z:,.) can be abbreviated to :z: = (:z:1, ... , :z:,.). The belief network represents a probability distribution over X having the product form P(:z:l! .... , :z:,.) = Tif=1P(:z:,l:z:pa(x,)), where :z:s denote! the projection of a tuple :z: over a subset of variables S. A cost network is a triplet (X, D, C), where X is a set of discrete variables, X = {X1 , ··. ,X,.}, over domain! D = {D1 , ... , D,.}, and Cis a set of real-valued cost functions Ct, ... , C,. Each function C, is defined over a subset ofvariables, S, = {X, 10 ··· ,X,~}, C, :1>4j=1 Dij-+ R+ . The cost graph of a cost network has a node for each variable and connects nodes denoting variables appear­ ing in the same cost function.

A = a denotes a partial assignment to a subset of vari­ ables, A. An evidence set e is an instantiated subset of . variables. We use (us, :Z:p) to denote the tuple us ap­ pended by a value :Z:p of Xp. We define Xi= (:z:1, ... ,x;) and x{ = (:z:i, Xi+!, ... , Xj)·

Definition 2.3 (elimination function) Given a function h defined over subset of variables, S, where X E S, the functions (minxh), (maxxh), (meanxh), and CL:x h) are defined over U = S - {X} as fol­ lows. For every U = u, (minxh)(u) = min.: h(u,x), (maxxh)(u) =max., h(u,x), (:Ex h)(u) =I:., h(u,x), and (meanxh)(u) = I:., h~:;cj>, where lXI is the cardi­ nality of X 's domain. Given a set of functions h11 ... , h; defined over the subsets S1 , ... , Sj, the functions (ITJh;) and L:J h3 are defined over U = UjSj. For every U = u, (IT3h3)(u) = lljhj(usi) and (2: 3 h3)(u) = 2: 3 h3(usi).

Algorithm elim-opt

Input: A cost network (X, D, C), C {Cl, ... , c,}; an ordering of the variables, Oj as­ signments e.

Output: The minimal cost assignment.

1. Initialize: Partition the cost components into bucketl> ... , bucket.,.. Let S1 , ... , S; be the subset of variables in the processed bucket on which the functions are defined.
2. Backward: For p ~ n downto 1, do:

For hi> h2 , ··· , h; in bucket 11 , do:

• If bucket 11 contains X 11 = :z: 11 , assign X 11 = :z: 11 to each h, and put each h. in its appropriate bucket.
• Else, _generate the functions hP: hP minx, z=:=l h1· :z:'j;t = argminx,hP. Add hP to the bucket of the largest-index variable in U 11 ~ U{= 1 S, - {X11}.
• Forward: Assign values in the ordering o using the recorded functions :z:opt in each bucket.

Figure 3: Algorithm elim-opt

Definition 2.4 (optimization, belief assessment) Given a cost network (X, D, C), the discrete optimiza­ tion problem is to find an assignment :z: 0 = (:z:!, ... , :z:~), :z:f ED,, such that :Z: 0 = argmini!,. Z:!=l C,. Given a be­ lief network ( G, P), the belief assessment task for X = :z: is to determine bel(:z:) = P(:z:je).

3 Approximating optimization

In [Bertele and Brioschi, 1972], the non serial dynamic programming algorithm for the discrete optimization problem is presented. This algorithm can be rephrased within the bucket-elimination scheme, as shown in Fig­ ure 3. Given a partitioning of. the cost functions into their respective buckets, algorithm elim-opt processes buckets from top to bottom. When processing X 11 , it generates a new function by taking the minimum rela­ tive to X 11 , over the sum of the functions in that bucket. The time and space complexity of elim-opt is exponen­ tial in the induced width w* of the cost graph. Thus, when its induced width is not small, we must resort to approximations.

Since the complexity of processing a bucket is tied to the arity of the functions being recorded, we propose to approximate these functions by a collection of smaller ar­ ity functions. Let h1 , ... , h; be the functions in the bucket of X 11 , and let S1, ... , S; be the subsets of variables on which those functions are defined. When elim-opt pro­ cesses the bucket of X 11 , it computes the function hP: hP =minx, Z:f=t hJ. Instead, we can use a brute-force approximation method to generate another function gP by migrating the minimization operator inside the summation. That is, gP = Z:f=l minx,.h1· Clearly, hP and gP are defined on the same arguments, and since each function h1 in the sum of hP is replaced by minx, h. in the sum defining gP, gP ::; hP. In gP the minimizing elimination operator minx,hi is applied separately to each function, (so gP will never increase dimensionality) and can be moved, separately, to a lower bucket. Thus, once elim-opt reaches the first variable, it has computed a lower bound on the minimal cost.

This idea can be generalized to yield a collection of parameterized approximation algorithms having vary­ ing degrees of accuracy and efficiency. Instead of the elimination operator (i.e., minimization) being applied to each singleton function in a bucket, it can be ap­ plied to a coerced partitioning of buckets into mini­ buckets. Let Qt = { Q1 , ... , Q .. } be a partitioning into mini-buckets of the functions h1 , ... , h; in X 11 's bucket. The mini-bucket Q1 contains the functions h1 1 , ··· , h1~· Algorithm elim-opt computes hP: (l indexes the minibuckets) hP = minx, Z:f=l h. = minx, z=;=l 2:1, h,,. By migrating the minimization operator into each mini­ bucket we get g~, = z=;=l minx, E1, h,,. As the parti­ tionings are more coerced, complexity as well as accuracy mcreases.

Definition 3.1 Partitioning Q' is a refinement of Q" iff for every set A E Q' there exists a set B E Q" such that A c B.

Proposition 3.2 If in the bucket of X 11 , Q' is a refine­ ment partitioning of Q", then hP 2: g~, 2: g~, . 0

Algorithm approx-opt is described in Figure 4. It is pa­ rameterized by two indexes that control the partition­ ings.

Definition 3.3 Let H be a collection of functions h1 , ... , h; on subsets Sl> ... , S;. A partitioning of H is canonical if any function whose arguments are sub­ sumed by another belongs to a mini-bucket with one of its subsuming functions. A partitioning Q is an ( i, m) - partitioning iff the following three conditions are met: the partitioning is canonical, at most m non­ subsumed functions participate in each mini-bucket, and the total number of variables mentioned in each mmz­ bucket does not exceed i.

Theorem 3.4 Algorithm approx-opt{i,m} computes a lower bound to the minimal cost in time 0( m · e:z:p(2i)) and space 0( m · e:z:p( i)) where i ::; n and m ::; 2 1 . 0

In general, as m and i increase we get more accurate ap­ proximations. The two parameters, although dependent, allow flexibility in bounding performance.

Example 3.5 Consider the network in Figure 5. We use ordering (A, B, C, D, E, F, G, H, I) to which we apply both elim-opt and appro:z:-opt{m = 1} with unbounded i.

Algorithm approx-opt(i,m)

Input: A cost network (X, D, C), {C1 , ... , C1}; or­ dering o.

Output: A lower bound on the optimal cost.

1. Initialize: Partition the functions into bucket1, ... , bucketn. Let 51 , ..· , Si be the sub­ set of variables in bu.cketp on which the functions are defined.
2. Backward: For p t- n downto 1, do:
3. If bucketp contains Xp = Xp, assign Xp = Xp to each hi and put each hi in the appropriate bucket.
4. Else, for h1, h2, ... , hj in bucketp, gener­ ate an ( i, m)-mini-bucket-partitioning, Q' {Q1, ... ,Qr}. For each Q, E Q' containing h1,, ··· , h1., do:

Generate function h 1 , h 1 = minx,. E:=l hti. Add h 1 to the largest-index bucket in u, t- LJ{=l s,i - {Xp}·

1. Forward: For i = 1 to n, do:

Given Xp-1, choose the Xp that minimize the sum functions in Xp 's bucket.

Figure 5: A cost network C C1(I, H, G) + C2(G,E,D) + C3(H,F,E) + C4 (F,B)+C5(E,B,C) + C6(D, C) + C1(B, A) + C8 (C, A) + C9 (A)

(We omit the cost subscripts for simplicity.) The initial partitioning into buckets is

bucket(!)= C(I, H, G), bucket(H) = C(H, E, F),

bucket( G) = C(G, E, D), bucket(F) = C(F, B),

bucket(E) = C(E,C,B), bucket(D) = C(D,C),

bucket( C) = C(C, A), bucket(B) = C(B, A),

bucket(A) = C(A).

Processing the buckets from top to bottom by elim-opt will generate what we denote as ). functions:

bucket(!) = C(I, H, G) bucket(H) = C(H, E, F), >.1(H, G) bucket( G)= C(G, E, D), >.H(E, F, G) bucket(F) = C(F, B), >.a(E, F, D) bucket(E) = C(E, C, B), >.p(E, B, D) bucket(D) = C(D, C), >.E(C, B, D) bucket(C) = C(C,A),>.D(C,B) bucket(B) = C(B, A), >.c(A, B)

bucket( A)= C(A), >.B(A)

where >.1(H, G) = min1C(I, H, G), >.H(E, F, G) = minH(C(H, E, F)+ >.1(H, G)), and so on. The optimal cost minA(C(A) + >.B(A)) is computed in bucket( A).

Processing by approx-opt(m = 1}, and denoting func­ tions that differ from those recorded by elim-opt by 1 1 8, we get

bucket(!) = C(I, H, G)

bucket(H) = C(H, E, F), >.1(H, G)

bucket( G) = C(G, E, D), /H(G)

bucket(F) = C(F, B), /H(E, F)

bucket(E) = C(E, C, B), IF( E), "fa(E, D)

bucket(D) = C(D, C), 'YE(D)

bucket(C) = C(C,A),"fE(C,B),"fD(C)

bucket(B) = C(B,A),"fc(B),"fp(B)

bucket(A) = C(A),"fc(A),"fB(A).

Bucket(H) contains two functions, each placed in a separate mini-bucket and each processed indepen­ dently, yielding 'YH(G) = minH>.I(H, G) placed in bucket( G) and 'YH(E, F) = minHC(H, E, F) placed in bu.cket(F); then, in bucket(G) we generate "ta(E, D) = mina(C(G, E, D)+ /H(G)); and so on. Finally, in bucket( A) we minimize ·over A the sum functions in that bucket, which provides a lower bound on the optimal cost. The first difference in elim-opt and approx-opt(m=l) occurs in bucket(H) and is visible in bu.cket(G), where elim-opt records a function on three variables, >.H(E, F, G), but approx-opt(m=l) records two functions, one on G ,"fH(G), and one on E and F, /H(E, F).

After approx-opt(m=l} processes all the buckets, we can generate a tuple in a greedy fashion as in elim-opt: we choose a value a of A that minimizes the sum in A's bucket, a value b of B minimizing the sum in bucket(B) given A = a, and so on. Although we have no guaran­ tee on the quality of the tuple generated, we can bound its error a posteriori by evaluating its cost against the derived lower bound.

3.1 Mini-bucket heuristics and search

The mini-bucket approximations compute lower bounds of the exact quantities, and these lower bounds can be viewed as under-estimating heuristic functions in a mini­ mization problem. We can associate with each partial as­ signment ip an evaluation function f(ip) = (g + h)(ip), where g(ip) = L{iiSi~{X,, ... ,x,_,}} ci and h(ip) = LjEbucket,. hj.

Proposition 3.6 The evaluation function f, generated by approx-opt, provides a lower bound on the optimal cost. D

We can conduct a best-first search using this heuristic evaluation function. When expanding the search tree, the best-first algorithm has a collection of tip nodes de­ noting a partial value assignment and their estimated evaluation function. At each step, the algorithm will expand a node with a minimal value of the evaluation function, f. From the theory of best-first search, we know the following: when the algorithm terminates with a complete assignment , it has found an optimal solu­ tion; as the heuristic function becomes more accurate, fewer nodes are expanded; and if we use the full bucket­ elimination algorithm, best-first search will reduce to a greedy-like algorithm for this optimization task [Pearl, 1984]. Thus, mini-bucket approximations can be used to generate mechanically heuristics for best-first or branch­ and-bound search.

4 Approximation of belief updating

The algorithm for belief assessment, elim-bel (for de­ tails see [Dechter, 1996]), is identical to elim-opt with two changes: minimization is replaced by summation, and summation by multiplication. Let x1 = X1 be an atomic proposition. Given a belief network (G, P) and evidence e, the problem is to compute P(x1\e) = P(x1, e)/ P(e). We can thus compute P(xb e) = I:z=:l!;' IIf=1 P(xi, e\xpa,) and normalize at the end. Con­ sider an ordering of the variables (X1, ... , X,.) and a corresponding partition of the probability matrices into buckets. The procedure has only a backward phase (Figure 2) . When processing a bucket, we multiply all the bucket's matrices, A1, .. . , Aj, defined over subsets S1, ... , s1, and then eliminate the bucket's variable by summation. The computed function is AP : Up --+ R, ).,P = Ex II{=1).,i, where Up = uisi- Xp . Once all the buc"kets are processed, the answer is available in the first bucket of X 1· Like all bucket-elimination algo­ rithms this algorithm's complexity (time and space) is O(exp(w·(d)) , where w·(d) is the induced width along d of the moral graph.

We will now apply the mini-bucket approximation to belief assessment. Let Qt = {Q1, ... ,Q,.} be a parti­ tioning into mini-buckets of the functions A1, ... , Aj in Xp 's bucket. Algorithm elim-bel computes AP: (l indexes the mini-buckets) Ap =Ex,. II{=1Ai =Ex,. IIl=1II,,A,,. If we, following the analog to approx-opt precisely, mi­ grate the summation operator into each mini-bucket, we get !~, = IIl=1 Ex,. II,,A,,. This, however, amounts to computing an unnecessarily bad upper bound of AP, since the products II,, AI, for i > 1 are replaced by their sums Ex II,, AI,. Instead, we can bound the product by its ~aximizing function. Separating the processing of the first mini-bucket from the rest, we get AP = Ex,. ((II, , A1,) · (II1=2II,, A1.) ), which yields g~, =Ex,. ((II, , AI,). IIl=2maxx,.II,,A,.). Clearly,

Proposition 4.1 For every partitioning Q, AP :S g~ :S f~ , and if in Xp 's bucket, Q' is a refinement partitioning of Q", then AP :S ~, :S ~, . D

Algorithm approx-bel-max(i,m)

Input: A belief network BN = (G, P) , P = {P1, ... , P,.}; an ordering of the variables, o; evi­ dence e.

Output: An upper bound on P(x11 e) .

1. Initialize: Partition the functions into buck­ ets. Let S1, ... , S1 be the subset of variables m bucketp on which matrices are defined.
2. Backward: For p +- n downto 1, do:
3. If bucketp contains Xp = Xp, assign Xp = Xp to each Ai and put each Ai in the appropriate bucket. · Else, for A1, )..2 , .. . , Aj in bucketp, do:

Generate Q' { Q11 ... , Q,. }, an (i, m)-partitioning.

• (First bucket) For Q1 = { A1 1 , ... , A1;} first in Q', do:

Generate function A 1 = Ex II{=1Ak Add ).. 1 to the bucket of the largest-index variable in u1 +­ U{=1 s1,- {Xp}·

• For each Q,, l > 1, in Q' = {A1 11 .. . , A1;}, do: U, +- U{=1 S,, - {Xp}· Generate the functions A 1 = maxx,. II{=1 )...,, . Add ).. 1 to the bucket of the largest-index variable in U, .
• Output: The product in bucket of X1.

Figure 6: Algorithm approx-bel-max(i,m}

In summary, an upper bound gP of AP can be obtained by processing one of Xp 's mini-buckets by summation, while the rest of the mini-buckets are processed by max­ imization. In addition to approximating by an upper bound, we can approximate by a lower bound by ap­ plying the min operator to each mini-bucket or we can approximate by computing a mean-value approximation using the mean operator in each mini-bucket. Algorithm approx-bel-max, which uses the maximizing elimination operator, is described in Figure 6. Algorithms approx­ bel-min and approx-bel-mean can be obtained by replac­ ing the operator max with min and mean, respectively.

Theorem 4.2 Algorithm approx-bel-max{i,m} computes an upper bound to the belief P(x1, e) in time O(m · exp(2i)) and space O(m · exp(i)). D

Similarly, aprox-bel-min computes a lower bound on P(xb e) and approx-elim-mean computes a mean-value of P(x11 e) .

Remark: Algorithm approx-bel-max computes an upper bound on P(x1, e) but not on P(x1\e). If an exact value of P( e) is not available, deriving a bound on P( x1\e) from a bound on P(x1 , e) may not be easy. We can use approx-bel-min to derive a lower bound on P(e) and use the resulting lower bound to derive an upper bound on P (x1 \e) .

5 Related work

The bucket-elimination framework provides a convenient and succinct language in which to express elimination al­ gorithms across many areas. Most of these algorithms are widely known. In addition to dynamic program­ ming [Bertele and Brioschi, 1972], constraint satisfac­ tion [Dechter and Pearl, 1987], and Fourier elimina­ tion [Lassez and Mahler, 1992], there are variations on these ideas and algorithms for probabilistic inference in [Canning et al., 1978; Tatman and Shachter, 1990; Shenoy, 1992; Zhang and Poole, 1996].

Mini-bucket approximation algorithms parallel consistency-enforcing algorithms for constraint processing, in particular those enforcing directional con­ sistency. Specifically, relational adaptive-consistency is a full bucket-elimination algorithm whose approximations, directional-relational-consistency(i,m) ( DRC(i,m)), en­ forces bounded levels of consistency [Dechter and van Beek, 1997]. For example, (denoting a generic mini­ bucket algorithm by elim-approx) directional relational arc-consistency, DRC1 , corresponds to elim-approx(m = 1}; directional path-consistency, DRC2, corresponds to elim-approx{m = 2}; and so on. '

Using mini-bucket approximations as heuristics for search parallels pre-processing by local consistency prior to backtrack search for constraint solving. In propositional satisfiability, where the original Davis­ Putnam algorithm [Davis and Putnam, 1960] Is a bucket-elimination algorithm, bounded-directional­ resolution with bound b [Dechter and Rish, 1994] cor­ responds to elim-approx(i =b).

Finally, a collection of approximation algorithms for sigmoid belief networks was recently presented [Jaakkola and Jordan, 1996] in the context of a recursive algo­ rithm similar to bucket elimination. Upper and lower bounds are derived by approximating sigmoid functions by Gaussian functions. This approximation can be viewed as a singleton mini-bucket algorithm where Gaus­ sian functions replace the min or max operations applied in each mini-bucket.

6 Conclusion

We present a collection of parameterized algorithms that approximate bucket-elimination algorithms. The basic idea is to partition each bucket into mini-buckets in or­ der to control complexity. Due to the generality of the bucket-elimination framework, such algorithms and their approximations will apply uniformly across areas such as constraint optimization, satisfiability, probabilistic rea­ soning, and planning. Here we introduced the algorithms in the context of deterministic and probabilistic inference tasks.

Many questions need to be investigated in the context of our proposal. For example, given that there are many

(i, m)-partitionings, and that each may result in differ­ ent accuracy, how do we determine a good partitioning? Such questions should be investigated empirically, and will, we hope, yield domain-independent and domain­ dependent heuristics.

Acknowledgements

Thanks to Irina Rish for commenting on an earlier version of the paper.