--- title: "Branch and Bound with Mini-Bucket Heuristics" authors: - "Kalev Kask" - "Rina Dechter" doi: "" url: "https://ijcai.org/proceedings/1999/62" pdf: "https://ijcai.org/proceedings/1999/0062.pdf" venue: "Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence" year: 1999 pages: "426-434" track: "Constraint Satisfaction" keywords: --- # Branch and Bound with Mini-Bucket Heuristics Kalev Kask, Rina Dechter *Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence*, pages 426-434. ## Abstract The paper describes a branch and bound scheme that uses heuristics generated mechanically by the mini-bucket approximation . This scheme is presented and evaluated for optimization tasks such as finding the Most Probable Explanation ( MP E ) in Bayesian networks. The mini-bucket scheme yields monotonic heuristics of varying strengths which cause different amounts of pruning, allowing a controlled tradeoff between preprocessing and search. The resulting Branch and Bound with Mini-Bucket heuristic (BBMB), is evaluated using random networks, probabilistic decoding and medical diagnosis networks. Results show that the BBMB scheme overcomes the memory explosion of bucket-elimination allowing a gradual tradeoff of space for time, and of time for accuracy. ## Full text ## 1 Introduction This paper proposes a new scheme for augmenting branch-and-bound search with heuristics generated auto­ matically by the Mini-Bucket algorithms. Mini-bucket is a class of parameterized approximation algorithms based on the recently proposed bucket-elimination frame­ work. The approximation uses a controlling parame­ ter which allows adjustable levels of accuracy and effi­ ciency [Dechter and Rish, 1997]. The algorithms were presented and analyzed for deterministic optimization tasks and probabilistic tasks, such as finding the most probable explanation ( M P E), belief updating, and find­ ing the maximum a posteriori hypothesis. Encouraging empirical results were reported for M P E on randomly generated noisy-or networks, on medical-diagnosis CPCS networks, and on coding problems [Rish et al., 1998]. In some cases, however, the approximation was largely sub­ optimal, even when using the highest feasible accuracy level. One way of improving the mini-bucket scheme is by embedding it in a general search algorithm. The in­ termediate functions created by the mini-bucket scheme can be interpreted as a heuristic evaluation function and used by any heuristic search algorithm. For instance, an upper bound on the probability of the best possible ex­ tension of any partial assignment in an MPE task can be derived. The tightness of these bounds can be controlled by the accuracy parameter of the mini-bucket scheme. In this paper we evaluate this idea using Branch-and­ Bound search which searches the space of partial assign­ ments in a depth-first manner. It expands a partial as­ signment only if its upper-bounding heuristic estimate is larger than the currently known best lower bound. The virtue of branch-and-bound compared to best-first search, is that it requires a limited amount of mem­ ory and can be used as an anytime scheme - when in­ terrupted, Branch-and-Bound outputs the best solution found so far . In [Kask and Dechter, 1999a] we apply this approach to Best-First search and compare the two schemes. The resulting search algorithm, BBMB (Branch and Bound with Mini-Bucket heuristics) is evaluated and compared against other algorithms (such as bucket elimi­ nation, the mini-bucket scheme and iterative belief prop­ agation), on a number of test problems, including cod­ ing networks, random networks, and CPCS networks. We show that the BBMB scheme is effective for a larger range of problems because of its gradual trade-off be­ tween preprocessing and search, and time and accuracy. Unlike bucket elimination, BBMB does not suffer from memory explosion and is often quicker to find an opti­ mal solution. We investigated this approach for the op­ timization task of finding the Most Probable Explanation (MPE). Section 3 presents an overview of the relevant algo­ rithms. In Section 4 we describe our branch-and-bound scheme and its guiding heuristic function . Section 5 presents empirical evaluations, while Section 6 provides discussion and conclusions. For space reasons we omit all proofs. For more details see [Kask and Dechter, 1999a]. ## 1.1 Related work MPE appears in applications such as medical diagnosis, circuit diagnosis, natural language understanding and probabilistic decoding. For example, given data on clin­ ical findings, MPE can postulate on a patient's probable affliction. In decoding, the task is to identify the most likely input message transmitted over a noisy channel given the observed output. Researchers in natural lan­ guage consider the understanding of text to consist of finding the most likely facts (in internal representation) that explains the existence of the given text. In com­ puter vision and image understanding, researchers for­ mulate the problem in terms of finding the most likely set of objects that explains the image. Scientific theories are models that attempt to fit the given observations , and so on. Figure 1: belief network P(f,d,c, b, a) P(flc, b)P(dlb, a) P(bla)P(cia) ![Image](https://ijcai.org/proceedings/1999/fulltext/62/image_000000_3de1f2a294a5b7398cec7de58d5aa580e9ad17d2e6edfb6e12d8b3444131be59.png) It is known that solving the MPE task is NP-hard. Complete algorithms for MPE use either the cycle cut­ set technique or the join-tree-clustering [Pearl, 1988] and the bucket-elimination scheme [Dechter, 1996]. However, these methods work well only if the network is sparse enough to allow small cutsets or small clusters. Fol­ lowing Pearl 's stochastic simulation algorithms for the MPE task [Pearl , 1988], the suitability of Stochastic Lo­ cal Search (SLS) algorithms for MPE was studied in the context of Medical diagnosis applications [Peng and Reg­ gia, 1986], [Peng and Reggia, 1989] and more recently in [Kask and Dechter , 1999b]. Best first search algo­ rithms were also proposed [Shimony and Charniak, 1991] as well as algorithms based on linear programming [San­ tos, 1991] . ## 2 Background ## 2.1 Notation and definitions Belief Networks provide a formalism for reasoning about partial beliefs under conditions of uncertainty. They are defined by a directed acyclic graph over nodes represent­ ing random variables of interest . DEFINITION 2.1 (Belief Networks) Given a set, X = {X1 , .. . , Xn} of random variables over multivalued do­ mains D1 , ... , Dn , a belief network is a pair ( G, P) where G is a directed acyclic graph and P = { P;}. P; = { P (X; f pa (X;) ) } are conditional probability ma­ trices associated with X;. The set pa(X;) is called the parent set of X;. An assignment (X1 = x1, ... ,Xn = Xn) can be abbreviated to x = (x1 , ... ,xn). The BN 1·epresents a probability distribution P(x1 , .... , Xn) = ITi=1P(x; lxpa(X;)) , where, xs is the projection ofx over a subsetS. An evidence set e is an instantiated subset of variables . The argument set of a fun ction h is denoted S(h ). DEFINITION 2.2 (Most Probable Explanation) Given a belief network and evidence e, the Most Prob­ able Explanation (MPE) task is to find an assignment (xr, . . . , x~) such that DEFINITION 2.3 (graph concepts) An ordered graph is a pair ( G , d) where G is an undirected graph and d = X1 , ... , Xn is an ordering of the nodes. The width of a node in an ordered graph is the number of its ear­ lier neighbors. The width w( d) of an ordering d, is the maximum width over all nodes. The induced width of an ordered graph, w* (d), is the width of the induced or­ dered graph obtained by processing the nodes recursively, from last to first; when node X is processed, all its earlier neighbors are connected. 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. An example of a belief network is given in Figure la, and its moral graph in Figure lb. ## 2.2 Bucket and mini-bucket algorithms Bucket elimination is a unifying algorithmic frame­ work for dynamic-programming algorithms applicable to probabilistic and deterministic reasoning [Dechter , 1996]. The input to a bucket-elimination algorithm con­ sists of a collection of functions or relations (e.g., clauses for propositional satisfiability, constraints, or conditional probability matrices for belief networks) . Given a vari­ able ordering, the algorithm partitions the functions into buckets, each placed in the bucket of its latest argument in the ordering. The algorithm has two phases. During the first , top-down phase, it processes each bucket, from the last variable to the first by a variable elimination pro­ cedure that computes a new function, placed in a lower bucket . For MPE, this procedure computes a product of all probability matrices in the bucket and maximizes over the bucket 's variable. During the second, bottom­ up phase, the algorithm constructs a solution by assign­ ing a value to each variable along the ordering, consult­ ing the functions created during the top-down phase. THEOREM 2.1 [Dechter, 1996] The time and space com­ plexity of Elim-MPE, the bucket elimination algorithm fo r MPE, are exponential in the induced width w*(d) of the network's ordered moral graph along ordering d . 0 The Mini-bucket elimination is an approximation scheme designed to avoid the space and time problems of full bucket elimination. In each bucket, all the func­ tions are first partitioned into smaller subsets called mini-buckets which are then processed independently. Here is the rationale. Let h1 , ... , hj be the functions in bucketp. When Elim-MPE processes bucketp, it computes the function hP: hP = maxxpiT{=1h;. The mini­ bucket alg0rithm, on the other hand, creates a partition­ ing Ql = { Q1 , ... , Qr} where the mini-bucket Ql contains the functions h1, , ... , ht.. The approximation will com­ pute gP = rrr=l maxxpiil; ht; . Clearly, hP ::; gP . Thus, ## Algot·ithm Approx-MPE(i) ( MB(i)) Input: A belief network BN = {?1 , ... , Pn}; ordering d; Output: An upper bound on the MPE, an assignment and the set of ordered augmented buckets. 1. Initialize: Partition matrices into buckets. Let S1 , ... , SJ be the subset of variables in bucketp on which matrices (old or new) are defined. 2. (Backward) For p f- n downto 1, do - If bucket p contains Xp = Xp, assign Xp = Xp to each h; and put each in appropriate bucket. - else, for h 1 , h2, ... , h J in bucketp, generate an ( i)- partitioning, Q' = { Q1, ... , Qr }. For each Q1 E Q' containing h1 1 , ··· h1, generate function h 1 , h 1 = maxxpiTl= 1 h1,. Add h 1 to the bucket of the largest-index variable in U1 f- U;= 1 S(h1,)- {Xp}· 3. (Forward) Fori= 1 ton do, given x1, ... ,Xp-1 choose a value Xp of Xp that maximizes the product of all the functions in X P 's bucket . 4. Output the ordered set of augmented buckets, an upper bound and a lower bound assignment. Figure 2: algorithm Approx-MPE(i) the algorithm computes an upper bound on the prob­ ability of the MPE assignment. Subsequently, in its second phase, the algorithm computes an assignment that provides a lower bound. The quality of the up­ per bound depends on the degree of the partitioning into mini-buckets. Given a bound parameter i, the algo­ rithm creates an i-partitioning, where each mini-bucket includes no more than i variables. Algorithm Approx­ MPE(i) (sometimes called MB(i)) is described in Figure 2. The algorithm outputs not only an upper bound on the M P E and an assignment (whose probability yields a lower bound) , but also the collection of augmented buck­ ets. By comparing the upper bound to the lower bound we can always have a bound on the error for the given instance. THEOREM 2.2 [Dechter and Rish, 1997} Algorithm Approx-MPE(i) generates an upper bound on the exact MP E and its time and space complexity is 0( exp( i)). When the bound i is large enough (i.e. when i 2:: w·) , the algorithm coincides with full bucket elimination. Example 2.3 Figure 3(b) illustrates how algorithms Elim-MPE and Approx-MPE(i) for i = 3 process the network in Figure l(a) along the ordering (A , E , D , C,B). Elim-MPE records new functions hB(a , d, c, e) , hc (a,d,e) , hD(a ,e), and hE(a) during its backwards phase. Then, in the bucket of A, it computes MPE = maxa P(a)hE(a) . Subsequently, an MPE assignment (A = a' B = b' C = c' D = d' E = 0) ( E = 0 is an ' ' ' ' evidence) is computed by maximizing the product functions in each bucket. Namely, a'= argmaxa P(a)hE(a) , e' = 0, d' = argmaxdhc (a', d, e = 0), and so on. The approximation Approx-MPE(3) splits bucket B into two mini-buckets each containing no more than 3 vari­ ables, and generates hB(e, c) and hB(d, a). An upper bound U on the MPE value is computed in A 's bucket, U = maxaP(a) ·hE(a) ·hD(a). A suboptimal MPE tuple is computed by assigning a value to each variable that maximizes the product of functions in the corresponding bucket, given the values of preceding variables. Figure 3: (a) Algorithm approx-mpe(i,m) and (b) a trace of the algorithm's execution. ![Image](https://ijcai.org/proceedings/1999/fulltext/62/image_000001_4305ea8b5aa7789ae557ae8289e5e80ceb5ecb29c55103efb4919f010aaa9a3e.png) ## 3 Heuristic Search with Mini-Bucket ## 3.1 Notation Given an ordered set of augmented buckets generated by the mini-bucket algorithm along d = X 1 , ... , Xn, we use the following convention - PPi denotes an input conditional probability matri­ ces placed in bucket p, (namely, its highest-ordered variable is Xp). - hPi denotes an arbitrary function in bucket p gen­ erated by the mini-bucket algorithm. - hj denotes a function created by the j-th mini­ bucket in bucket p . - )..Pi denotes an arbitrary function in bucket p. We denote by buckets(l..p) the union of all functions in the bucket of X 1 through the bucket of X P. Remember that S(f) denotes the set of arguments of function f. ## 3.2 The idea We will now show that the new functions recorded by the mini-bucket algorithm can be used to express upper bounds on the most probable extension of any partial assignment. Therefore , they can serve as heuristics in an evaluation function which guides either a best-first search or a branch-and-bound search. ## DEFINITION 3.1 (Exact Evaluation Function) Let x = xP = (x1 , ... , xp). The probability of the most probable extension of i;P I denoted r (xP) is: The above product defining J* can be divided into two smaller products expressed by the functions in the ordered augmented buckets. In the first product all the arguments are instantiated , and therefore the maximiza­ tion operation is applied to the second product only. De­ noting and we get During search, the g function can be evaluated over the partial assignment :fP, while H* can be estimated by a heurist ic function . Our first proposal is to estimate H*(xP) by a function H1 = f1j hPi which is the product of all h functions generated by the mini-bucket algorithm which reside in bucket p. It can be shown, using prop­ erties of mini-bucket scheme, that this product indeed provides an upper bound on H* , yielding an admissible heuristic. However, the heuristic function H1 is non-monotonic. In fact, even if provided with augmented buckets that are generated by exact full bucket elimination, this heuris­ tic may still be nonmonotonic. A heuristic function is monotonic if the evaluation function along any path in the search . tree is not increasing. We next modify H 1 to make it monotone and more accurate. The modified heuristic function H2 adds to the product of H 1 all those h functions in buckets(l..p-1) that were generated in buckets processed before bucket p. The rationale is that some conditional probability matrices in H* are approximated by h functions that are placed below bucket p (because they are not defined over Xp)· DEFINITION 3.2 Given an ordered set of augmented buckets, the heuristic function H 2 ( xP) ' is the product of all the h functions that satisfy the following two prop­ erties: 1} They are generated in buckets (p + 1, ... , n), and 2} They reside in buckets 1 through p. Namely, H2(xP) = ITf=l IThkEbucket; hj, where k > p, (i .e. hj J is gener-ated by a bucket processed before bucket p.) THEOREM 3.1 (Mini-Bucket Heuristic) For every partial assignment x = :fP = (x1 , ... , xp), of the first p variables, the evaluation function f( xP) = g( xP) · H2(xP) is: 1) Admissible - it never underestimates the probabil­ ity of the best extension of :fP. 2) Monotonic, namely f(xP+l )/ J( xP) :S 1. o The following proposition shows how g(xP+ 1 ) and H(xP+l) can be updated recursively based on g( xP) and H(xP) and functions residing in bucket p+ 1. (From now on we will use H to mean H2.) Proposition 1 Given a partial assignment xP (x1 , .. . xp), both g(xP) and H( xP) can be computed re­ cursively by ## Algorithm BBMB(i) Input: A belief network EN= {P1 , ··· ,Pn}; ordering d. Output: An MPE assignment, or a lower bound and an upper-bound on the MPE. 1. Initialize: Run MB(i) algori thm which generates a set of ordered augmented buckets and an upper-bound on MPE. Set lower bound L to 0. Set current variable index p to 0. 2. Search: Execute the following procedure until variable X1 has no legal values left. - Expand: Given a partial instantiation xP, compute all partial assignments xP+ 1 = ( xP, v) for each value v of X P+ 1 . For each node xP+ 1 compute its heuristic value f(xP+ 1) = g(xP+1). H(xP+1) using Prune those assignments xP+ 1 for which f ( xP+ 1 ) is smaller than the lower bound L. - Forward: If Xp+l has no legal values left , goto Back­ track. Otherwise let xP+ I = ( xP, v) be the best extension to xP according to f. If p + 1 = n , then set L = f (xP+ 1 ) and goto Backtrack. Otherwise remove v from the list of legal values. Set p = p + 1 and goto Expand. - Backtrack: If p = 1, Exit. Otherwise set p = p- 1 and repeat the Forward step. ## 3.3 Search with Mini-Bucket Heuristics The tightness of the upper bound generated by the mini­ bucket approximat ion depends on its i-bound. Larger values of i yield better upper-bounds, but require more computation. Therefore, Branch-and-Bound search, if parameterized by i , allows a controllable tradeoff be­ tween preprocessing and search , or between heuristic strength and its overhead. In Figure 4 we present algorithm BBMB(i). This al­ gorithm is initialized by running the mini-bucket algo­ rithm, producing the set of ordered augmented buckets . It then traverses the search space in a depth-first man­ ner , instantiating variables from first to last . Through­ out the search, the algorithm maintains a lower bound on the probability of the MPE assignment, which corre­ sponds to the probability of the best full variable instan­ t iation found thus far. It uses the heuristic evaluation function f( xP ) to prune the search space. Search ter­ minates when it reaches a time-bound or when the first variable has no values left. In the latter case , the algo­ rithm has found an optimal solution. The heuristic function generated by the mini-bucket approximation can also be used to guide any A* type algorithm. For a description of Best-First search with mini-bucket heuristics see [Kask and Dechter, 1999a]. ## 4 Experimental Methodology We tested the performance of our scheme on severa! types of networks. On each problem instance we ran bucket elimination (Elim-MPE), mini-bucket ap­ proximation with various i-bounds (MB(i)) and branch and bound with some levels of mini-bucket heuristics (BBMB(i)). Table 1: Random MPE. Time bound 30 sec. 100 samples. | N C,P,l< | Elim MPE #[ t i?"e] w | opt | MB / BBMB i=2 #[time] | MB I BBMB i=4 #[time] | MB/ BBMB i=6 #[t ime] | MB / BBMB i=B #[timej | MB / BBMB i=lO #[time] | MB / BBMB i=12 #[time] | MB / BBMB i=14 #[time] | |----------------|-------------------------|--------|-------------------------|-------------------------|-------------------------|-------------------------|--------------------------|--------------------------|--------------------------| | 256 100 ,2 ,2 | 9 114 .9 1) 14 .6 | >0 .95 | 14l0 03j 89[6 .30] | 301? 03J_ 100[104) | HJ? 0~1) 100[0 21 | 50J~-07dl 100 0.13 | 63J? ·15J, 100[0 . 18] | 68J? 40), 100[0.45] | 81),120), 100[128] | | 256 105,2,2 | 69[7. 11) 15.8 | >0 .95 | 6_1? -03] 83[8 .86] | 20l0.03] 99[1 .38] | 29_1?-04J_ 100[0. 69) | 42_l?-08J_ 100[0.lll) | 47J~ 17] 100 0 .26) | 67 [0.491, 100[0 .5:2) | 75[154 100[163 | | 256 11 0,2, 2 | 41[9. 06] 17.5 | >0.95 | 8J? 04] 77[14.1] | 15_1? o(i] 100[3 .68 | 23l0 O~j 99[1.07] | 33_1? 08J_ 100[0.4 i) | 47_l?·18J_ wo[o.a5J | 55[? 57)_ 100[0 .70) | 67[1.85_1_ 100[1.98) | | 256 11 5 ,2 ,2 | l7_[ l2 .3j 19 . 1 | >0 .95 | 6[? -03J. 71[17 .5] | 1 ~ l o 03j 98[5. 74] | 16_1? 05J. 100[178] | 22_1? ·09J. 100[0 .85] | 43_L?-21J. 100[0.71] | 37_1? ·66J, 100[0 .84] | 5 1_1? -17J. 100[2.34] | | 256 120,2,2 | 11J9 99j 20. 3 | >0 .95 | 4_1? 04J, 57[20 .4] | 10 O . O~j 95 6 .50] | 1~lo o~j 97[2.60] | 2:Jr08Jl 100 1.96 | 3~~.2~il 100 0.97 | 39_1?·66J. 100[1.00] | 53_1? -10 100[2 .35 | | 256 125 ,2 ,2 | 2[211] 22 .4 | >0 .95 | 2[0.03] 49[21 .5] | 8 0 .04]. 86 9 .44] | 9[? 05] 95[4 79] | 2~[00~! 96[2 . 17] | 28_[? 25), 100[162] | 35J?·78Jl 100[1.52 | 35_1? -50 100[3.34 | The main measure of performance of the approxima­ tion algorithm given a fixed time bound , is the accuracy ratio opt = Palg / PM p E between the probability of the solution found by the test algorithm (Patg) and the prob­ ability of the optimal solution (PM PE ) , whenever PM PE is available. We also record the running time of each algori thm. We report the distribution of problems with respect to 5 predefined ranges of accuracy : opt ;::: 0.95 , opt ;::: 0.5 , opt ;::: 0.2, opt ;::: 0.01 and opt < 0.01. We recorded the number of problems that Elim-MPE solved as well as the average induced width w· of the test problems. Be­ cause of space restrictions in most cases we report only the number of problems that fall in the highest accu­ racy range opt ;::: 0.95. However , since most problems were solved by BBMB optimally, we lose only minimal information. In addition, during the execution of BBMB we also stored the current lower bound L at regular time inter­ vals. Comparing the lower bound against the optimal solution , allows reporting the accuracy of BBMB as a function of time. ## 4.1 Random Bayesian Networks and Noisy-OR Networks Random Bayesian networks and Noisy-OR networks were randomly generated using parameters (N, K, C, P), where N is the number of variables, K is their domain size, C is the number of conditional probability matri­ ces and P is the number of parents in each conditional probability matrix. The structure of each test problem is created by ran­ domly picking C variables out of N and for each, ran­ domly selecting P parents from preceding variables, rel­ ative to some ordering. For random Bayesian networks, each probability table is generated randomly. For Noisy­ OR networks , each probability table represents an OR­ function with a given noise and leak probabilities P(X = OJY1 , ... , Yp) = Pteak X ITY,=l Pnoise · Tables 1 and 2 present results of experiments with ran­ dom Bayesian networks and Noisy-OR networks respec­ tively. In each table, parameters N, K and P are fixed , while C, controlling network's sparseness , is changing. For each C, we generate 100 problem instances. Each entry in the table reports the number of instances that fall in a specific range of accuracy, as well as the average running time of each algorithm (note that BBMB time includes the preprocessing time by MB). For example, Table 1 reports the results with random problems having N=256, K=2, P=2. There are 5 hori­ zontal blocks, each corresponding to a different value of C. Each block has two rows, one for MB and one for BBMB, reporting the number of problems in accuracy range of 0.95 and the average running time. The second column reports the results of Elim-MPE, namely the number of instances it solved, their average w· and running time. The rest of the columns report results of MB and BBMB for various levels of i. Look­ ing at the first line in Table 1 we see that in the best accuracy range, opt ;::: 0.95, MB with i = 2 solved only 14 problems using 0.03 seconds on the average. BBMB with i = 2 solved 89 instances in this range while us­ ing 6.30 seconds on the average. Note that Elim-MPE on the other hand solved 91 instances using much more time than BBMB with any i-bound. Each row demonstrates a tradeoff between preprocess­ ing by MB and subsequent search by BBMB. As ex­ pected, MB can solve more instances as i increases while its average time increases. At the same time, the search time of BBMB decreases as i increases. We observe that the total BBMB time improves when i increases until a threshold point and then worsens. We have high­ lighted the best performance point in each row. Below this threshold, the heuristic function is weak , resulting in long search. Above the threshold, the extra prepro­ cessing is not cost effective. As problems become harder BBMB achieves its best performance at higher thresh­ olds. For example, when C is 100 and 105, the threshold is i = 8, when C is 110, 115 and 120, it is i = 10, and when C is 125, it is i = 12. Table 2 reporting on Noisy-OR shows similar results (based on opt;::: 0.95 range). On this class BBMB is very effective and solved all problems exactly, while Elim- MPE solved almost none. For i 2: 6 BBMB can solve all 100 instances, with threshold i = 6. Table 2: Noisy-OR MPE. Noise 0.2 , Leak 0.01. Time bound 30 sec. 100 samples. 10 evidence. | N C,P | Elim MPE #(time] w ' | opt | B~~~ i::::: 2 #(time] | B~~~ i::::: 6 #(time] | ~~~ i=1 0 #(time] | ~~~ i:::::l 4 #(time] | |-----------|------------------------|-------|-------------------------|-------------------------|----------------------|-------------------------| | 128 90,2 | 6 ~10 9J 20.4 | >0.95 | 3 1_l? 04J, 100(0.54] | 42~?-0SJ. 100[0.11] | 49_l? 22J_ 100(0.25] | 71_l?-22J_ 100(2 .22] | | 128 95,2 | 1~7 .67] 21.5 | >0.95 | 2~ ~0 O~J 99(0 . 78] | 36J[:·04J. 100 0.11] | 44 0 .22J. 100 0.27] | 59J~45J. 100 246] | | 128 100,2 | Oj-J 23.6 | >0.95 | 10(0.05] 98[1.0 Ij | 26J[:·o~Jl 100 0 .25 | 44 0.27), 100 0.33] | 57(2. 77] IOo'[2.ni] | | 128 105,2 | ~H | >0.95 | I~!? o~l 99(2. 18] | 29)? 04), 100(0.45] | 38 0.26], 100[0.37] | 48_[!! 17), 100(3.20] | In Figures 5 and 6 we provide an alternative view of the performance of BBMB(i). Let FssM B(i) (t) be the fraction of the problems solved completely by BBMB(i) by time t. Each graph in Figures 5 and 6 plots FsBMB(i)(t) for some specific value i. Figure 5 shows the distribution of F88M B(i) (t) for random Bayesian networks when N=256, C=125, K=2 and P=2 (corre­ sponding to the last row in Table 1) , whereas Figure 6 shows the distribution of F88M B( i) (t) for Noisy-OR net­ works when N=128 , C=95 and P=2 (corresponding to the second row in Table 2) . Figures 5 and 6 display a trade-off between preprocess­ ing and search. Clearly, if FsBMB(i)(t) > FsBMB(j)(t), then FssM B(i ) (t) completely dominates FssM B(j) (t). For example, in Figure 5 BBMB(10) compl etely domi ­ nates BBMB(6). When FsBMB(i)(t) and FsBMB(j)(t) intersect, they display a trade-off as a function of time. For example, if we have only few seconds, BBMB(6) is better than BBMB(14) . However, when sufficient time is allowed, BBMB(14) is superior to BBMB(6). The same pattern appears in Figure 6. BBMB(6) completely dominates BBMB(2) , while there is a trade­ off between BBMB(2) and BBMB(14) depending on the amount of time allowed. ## 4. 2 Random Coding Networks Our random coding networks fall within the class of lin­ ear block codes. They can be represented as four-layer belief networks (Figure 7). The second and third layers correspond to input information bits and parity check bits respectively. Each parity check bit represents an XOR function of input bits u; . Input and parity check nodes are binary while the output nodes are real-valued . In our experiments each layer has the same number of nodes because we use code rate of R=K/N=1/2 , where K is the number of input bits and N is the number of transmitted bits. Given a number of input bits K, number of parents P for each XOR bit and channel noise variance ~ 2 , a cod­ ing network structure is generated by randomly picking parents for each XOR node. Then we simulate an in­ put signal by assuming a uniform random distribution of informat ion bits, compute the corresponding values of the parity check bits, and generate an assignment to the output nodes by add ing Gaussian noise to each in­ formation and parity check bit. The decoding algorithm takes as input the coding network and the observed real­ valued output assignment and recovers the original in­ put bitvector by computing or approximating an MPE assignment . Figure 5: Random Bayesian . N= 256 , C=l25 , 1<=2, P=2. 100 samples. ![Image](https://ijcai.org/proceedings/1999/fulltext/62/image_000002_3fabe4d75c5ae1b80b0bdba4c06bf77e24d6b8dc8821d9bd4618c49e97562f2f.png) Table 3: Random coding. Time 30 sec. 2000 samples. | N- 100 K=50 CT | opt | ~~~ i::::: 6 | B~~~ i=IO | B~~~ i ::::: 14 | IBP | |------------------|--------|--------------------------|--------------------------|-------------------------|--------------| | 0.22 | >0.95 | 172~~? - 0~! 1998[0.13] | 183?!? 4?l 2000(0 .42] | 193~!4 5~ l 2000[4.55] | 2000 [0 08] | | 0 .28 | >0.95 | 108 :!? o~l 1977(0 . 75] | 130~~?-3~! 1996[0.69] | 162~~4 . 5~! 1999[4.63] | 1996 (0 .08] | | 0.32 | >0.95 | 660.l? 0~~] 1908[1. 77 | 8 99J?-30J_ 1 9 72[1.28] | 124~~4-S~J 1990[4 .82] | 1993 (0 .08] | | 0.40 | >0 .95 | 172 (0.06] 1522(6 Hi] | 272[0 .37] 1779[4.24] | 450_[~-46] 1900[6.51] | 1741 (0.08] | | 0.51 | >0.95 | 21[? 06) , 8 11(17 .0] | 3~~0 37] 11 75(13 .4] | 8~~4-41~ 1435[11.9] | 616 (0 .08] | We tested two sets of random coding networks- 1<=50 and K=100 input bits. Table 3 reports results on ran­ dom coding networks having 1<=50. In add ition to Elim­ MPE and BBMB, we also ran Iterative Belief Propaga­ t ion (IBP) which was recently observed as the best per­ forming decoding algorithm. It is identical to iterative application of Pearl 's belief updating on tree- like net­ works [Pearl , 1988]. For each ~we generated and tested 2000 samples divided into 200 different networks each simulated with 10 different input bit vectors. In Table 3 we observe a familiar pattern of preprocessing-search tradeoff. For each level of noise ~ there is an empirical opt imal i balancing preprocessing cost and search. For ~ = 0.22 the threshold is 6. As noise increases, the threshold increases. Also, as noise increases, the role of search becomes more significant. Although IBP is superior (because it is faster) for small noise, it has a shortcoming for high noise levels since its performance cannot be improved with extra time while BBMB can. Figure 6: Noisy-OR. N=128, C=95, P=2. 100 samples. ![Image](https://ijcai.org/proceedings/1999/fulltext/62/image_000003_7f34c32ff2bc5d5ca72f94d2f9b41797183293832fe51cd68ce918341e89d204.png) Figure 7: Belief network for structured (10,5) block code with parent set size P=3 ![Image](https://ijcai.org/proceedings/1999/fulltext/62/image_000004_92512bd8f7ae2f64b6e047ad5a72006403d12a90c6b50a09566cc25b12e0d56b.png) Table 4 reports the Bit Error Rate (BER) for MB/BBMB(14) and IBP. BER is a standard measure used in the coding literature denoting the fraction of in­ put bits that were decoded incorrectly. When compared using BER, IBP is about the same as BBMB(14) when the noise is small , but slightly better when the noise is large. Figure 8 shows the distribution of FBBM B(i) (t) for Random Coding networks when K=100 and o- = 0.28. We observe that no algorithm completely dominates any other algorithm. However , we can see a trade-off depending on the time available. When the time allowed is small (less then 10 seconds), BBMB(i) with i less than 14 is better. However, when more time is allowed, BBMB(14) is clearly superior. Table 4: Random coding BER. | | MB 88MB i - 14 | IBP | |--------------------------------|--------------------------------------------------------------------------|------------------------------------| | " 0.22 0.28 0 .32 0 .40 0 .5 1 | 0.00 1:f.0 .00024 0.010/0 .0015 0.025/0.0041 0.090/0 .021 0 . 184/0. 102 | 0.00024 0.0015 0.0034 0.016 0 .084 | Figure 8: BBMB Random Coding. K=100, o500 samples. 0.28. ![Image](https://ijcai.org/proceedings/1999/fulltext/62/image_000005_c15c22ba5be8420ae3dbaf19006c05a9ece1cc2d18e5b8ef0d371f28f8fcc010.png) ## 4.3 CPCS Networks As another realistic domain, we used the CPCS networks derived from the Computer-Based Patient Care Simu­ lation system, and based on INTERNIST-1 and Quick Medical Reference expert systems [Pradhan et al. , 1994] . The nodes in CPCS networks correspond to diseases and findings. Representing it as a belief network requires some simplifying assumptions, 1) conditional indepen­ dence of findings given diseases, 2) noisy-OR dependen­ cies between diseases and findings, and 3) marginal in­ dependencies of diseases. For details see [Pradhan et al., 1994]. In Table 5 we have results of experiments with two binary CPCS networks, cpcs360b (N = 360, C = 335) and cpcs422b (N = 422, C = 348) , with 1000 and 150 instances respectively. Each instance had 10 evidence nodes picked randomly. Since cpcs360b network is solved quite effectively by MB we see that BBMB added search time is small , serv­ ing primarily to prove the optimality of the MB solution. On the other hand, on cpcs422b MB can solve a third of the instances accurately when i is small , and more as i increases. BBMB can solve all instances accurately for i > 12 when search takes little additional time. ## 5 Discussion and Conclusion Our experiments demonstrate that combining branch­ and-bound with mini-bucket heuristics (BBMB) pro­ vides a powerful method of attacking optimization prob­ lems such as the MPE. Table 5: CPCS networks. Time 30 and 45 resp. | CPCS360b 1000 samples | MBI 88MB i=4 | MB I 88MB i=8 | MB I 88MB i=l 2 | MBI 88MB i=l6 | |----------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------| | >0.95 >0.50 >0.20 >0 .0 1 <0.0 1 CPCS422b 150 samples >0.95 >0.50 >0 .20 >0.0 1 <0.0 1 | 939_L?·94J 1000[0.96] 13(0.94] 0[-] 44[0.95] 0[-] 4[0 .94] 0(-] 0[-] 0[-] 8~~~ i=4 56[?3 1) 144(25.5] 14(22.9] 1(45 .0] 12[23. 0] 0[-] 34(23 . 1] 2(4 5 .0] 34 [23. 1] 3[45.0] | 950[0 .96] 1000[0 97] 8[0 96] 0[-] 38[0 .97] 0(-] 4[0.96] 0(-] 0(-] 0(-] MB _~ 88MB i=8 67_(?31). 148[24 .5] 8[22.9] 0(-] 16[22 9] 0[-] 27(23.1] 2(45.0] 32(22 .9] 0[-] | 983[? .04] 1000(2 .04] 6(2.01 ] 0[-] 11(2.03] 0[-] 0[-] 0[-] 0[-] 0[-] 8~~~ i=12 78_[;3.2]. 150[23.4] 19(23 .4] 0[-] 23(23 .4] 0[-] 15(23.2] 0(-] 15b~~ 0] | 99 l[l6 .4J. 1000[16.4] 6[16.1] 0[-] 3[16.6] 0(-] 0[-] 0(-] 0(-] 0(-] MB_~ 88MB i=16 98_(~9 9J. 150[40 .0] 22(40 . 1] 0(-] 17(40.1] 0[-] 8[40.0] 0(-] 5[40 0] 0[-] | On the one hand it avoids the storage bottleneck offull bucket elimination while frequently solving problems op­ timally. On the other hand, it improves output quality substantially over the mini-bucket approximation , espe­ cially when the former is highly suboptimal. However, the mostimportant feature of BBMB is the ability to control the balance between preprocessing (for heuristic generation) and search, using its bounding parameter i. Pure search (low i) and pure bucket-elimination (high i) are two extremes ends of that spectrum. In all ou r experiments , including random Bayesian networks , Noisy-OR networks, coding networks and medical diagnosis CPCS networks , we observed that op­ timal performance (measured by time within a certain accuracy range) occurred at an intermediate threshold point of i . Weaker heuristics, lying below the thresh­ old, and stronger heuristics, lying above the threshold, were less cost-effect ive. We also observed that as prob­ lems grew harder, stronger heuristics became more cost­ effective. The control of the gradual change of space­ time-accuracy tradeoff of BBMB now makes a larger set of problem solvable. Although the best threshold point may not be pre­ dictable for every problem instance, a preliminary em­ pirical analysis can be informative when given a class of problems that is not too heterogeneous. We have also tested the mini-bucket heuristic func­ tion with Best-First search. We found that if we are in­ terested in the optimal solution only, BFMB(i) is often significantly faster than BBMB(i) when given sufficient time and space. However, unlike BBMB, BFMB is not an anytime algorithm [Kask and Dechter , 1999a]. ## References 1. [Dechter and Rish, 1997] R. Dechter and I. Rish. A scheme for approximat ing probabilistic inference. In Proceedings of Uncertainty in Artificial Int elligence (UA I9 7), pages 132-141 , 1997. 2. [Dechter , 1996] R. Dechter. Bucket elimina tion: A uni- fying fram ework for probabilistic inference algorithms. In Uncertainty in Artificial intelligence (U A 1-96), pages 211-219 , 1996. 3. [Kask and Dechter, 1999a] K. Kask and R . Dechter. On the power of mini-bucket heuristics for improved search. UCI Technical report, 1999. 4. [Kask and Dechter, 1999b] K. Kask and R . Dechter. Stochastic local search for bayesian networks. In Workshop on AI and Statistics (AISTAT99) , 1999. 5. [Pearl , 1988] J. Pearl. Probabilistic Reasoning in intel- ligent Systems. Morga n Ka ufm ann , 1988. 6. [Peng and Regg ia, 1986] Y. Peng and J .A. Reggia. Plausability of diagnostic hypothesis. In Natio nal Conference on Artificial Intelligence (AAAI86) , pages 140-145, 1986. 7. [Peng and Reggia , 1989] Y. Peng and J .A . Reggia. A connectionist model for di agnostic problem solving. IEEE Transa ctions on Systems, Man and Cybernet- ics, 1989. 8. [Pradhan et al. , 1994] M. Pradhan , G. Provan, B. Mid- dleton , and M. Henrion. Knowledge engineering for large belief networks . In Proc. Tenth Conf. on Uncer- tainty in Artificial i ntelligence, 1994. 9. [Rish et al. , 1998] I. 10. Rish , K. Kask, and R . Dechter. Ap- proximation a lgorithms for probabilistic decoding. In Uncertainty in Artificial Intelligence (UA 1-98 ) , 1998. 11. [Santos, 1991] E. Santos. On the generat ion of alter- native explanations with implications for belief revi- sion. In Uncertainty in Artificial Intelligence (UAI- 91), pages 339-347, 199 1. 12. [Shimony and Charniak, 1991] S.E. Shimony and E. Charniak. A new algorithm for finding map assign- ments to belief networks. In P. Bonissone, M. Hen- rion, L. I< anal, and J. Lem m er E ds. Uncertainty in Artificial Intelligence, volume 6, pages 185-193 , 1991.