A. Becker, R. Bar-Yehuda and D. Geiger

Volume 12, 2000

**Links to Full Text:**

We show how to find a minimum weight loop cutset in a Bayesian network with high probability. Finding such a loop cutset is the first step in the method of conditioning for inference. Our randomized algorithm for finding a loop cutset outputs a minimum loop cutset after O(c 6^k kn) steps with probability at least 1 - (1 - 1/(6^k))^c6^k, where c > 1 is a constant specified by the user, k is the minimal size of a minimum weight loop cutset, and n is the number of vertices. We also show empirically that a variant of this algorithm often finds a loop cutset that is closer to the minimum weight loop cutset than the ones found by the best deterministic algorithms known.

Journal of Artificial Intelligence Research 12 (2000) 219-234 Submitted 5/99; published 5/00 Randomized Algorithms for the Loop Cutset Problem Ann Becker anyuta@cs.technion.ac.il Reuven Bar-Yehuda reuven@cs.technion.ac.il Dan Geiger dang@cs.technion.ac.il Computer Science Department Technion, Haifa, 32000, Israel Abstract We show how to find a minimum weight loop cutset in a Bayesian network with high probability. Finding such a loop cutset is the first step in the method of conditioning for inference. Our randomized algorithm for finding a loop cutset outputs a minimum loop cutset after O(c 6kkn) steps with probability at least 1 Gamma (1 Gamma 16k )c6 k, where c ? 1 is a constant specified by the user, k is the minimal size of a minimum weight loop cutset, and n is the number of vertices. We also show empirically that a variant of this algorithm often finds a loop cutset that is closer to the minimum weight loop cutset than the ones found by the best deterministic algorithms known. 1. Introduction The method of conditioning is a well known inference method for the computation of posterior probabilities in general Bayesian networks (Pearl, 1986, 1988; Suermondt & Cooper, 1990; Peot & Shachter, 1991) as well as for finding MAP values and solving constraint satisfaction problems (Dechter, 1999). This method has two conceptual phases. First to find an optimal or close to optimal loop cutset and then to perform a likelihood computation for each instance of the variables in the loop cutset. This method is routinely used by geneticists via several genetic linkage programs (Ott, 1991; Lang, 1997; Becker, Geiger, & Schaffer, 1998). A variant of this method was developed by Lange and Elston (1975). Finding a minimum weight loop cutset is NP-complete and thus heuristic methods have often been applied to find a reasonable loop cutset (Suermondt & Cooper, 1990). Most methods in the past had no guarantee of performance and performed very badly when presented with an appropriate example. Becker and Geiger (1994, 1996) offered an algorithm that finds a loop cutset for which the logarithm of the state space is guaranteed to be at most a constant factor off the optimal value. An adaptation of these approximation algorithms has been included in version 4.0 of FASTLINK, a popular software for analyzing large pedigrees with small number of genetic markers (Becker et al., 1998). Similar algorithms in the context of undirected graphs are described by Bafna, Berman, and Fujito (1995) and Fujito (1996). While approximation algorithms for the loop cutset problem are quite useful, it is still worthwhile to invest in finding a minimum loop cutset rather than an approximation because the cost of finding such a loop cutset is amortized over the many iterations of the conditioning method. In fact, one may invest an effort of complexity exponential in the size of the loop cutset in finding a minimum weight loop cutset because the second phase of the conditioning algorithm, which is repeated for many iterations, uses a procedure of such cfl2000 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved. Becker, Bar-Yehuda, & Geiger complexity. The same considerations apply also to constraint satisfaction problems as well as other problems in which the method of conditioning is useful (Dechter, 1990, 1999). In this paper we describe several randomized algorithms that compute a loop cutset. As done by Bar-Yehuda, Geiger, Naor, and Roth (1994), our solution is based on a reduction to the weighted feedback vertex set problem. A feedback vertex set (FVS) F is a set of vertices of an undirected graph G = (V; E) such that by removing F from G, along with all the edges incident with F , a set of trees is obtained. The Weighted Feedback Vertex Set (WFVS) problem is to find a feedback vertex set F of a vertex-weighted graph with a weight function w : V ! IR+, such that Pv2F w(v) is minimized. When w(v) j 1, this problem is called the FVS problem. The decision version associated with the FVS problem is known to be NP-Complete (Garey & Johnson, 1979, pp. 191-192). Our randomized algorithm for finding a WFVS, called RepeatedWGuessI, outputs a minimum weight FVS after O(c 6kkn) steps with probability at least 1 Gamma (1 Gamma 16k )c6 k, where c ? 1 is a constant specified by the user, k is the minimal size of a minimum weight FVS, and n is the number of vertices. For unweighted graphs we present an algorithm that finds a minimum FVS of a graph G after O(c 4kkn) steps with probability at least 1 Gamma (1 Gamma 14k )c4 k. In comparison, several deterministic algorithms for finding a minimum FVS are described in the literature. One has a complexity O((2k + 1)kn2) (Downey & Fellows, 1995b) and others have a complexity O((17k4)!n) (Bodlaender, 1990; Downey & Fellows, 1995a). A final variant of our randomized algorithms, called WRA, has the best performance because it utilizes information from previous runs. This algorithm is harder to analyze and its investigation is mostly experimental. We show empirically that the actual run time of WRA is comparable to a Modified Greedy Algorithm (MGA), described by Becker and Geiger (1996), which is the best available deterministic algorithm for finding close to optimal loop cutsets, and yet, the output of WRA is often closer to the minimum weight loop cutest than the output of MGA. The rest of the paper is organized as follows. In Section 2 we outline the method of conditioning, explain the related loop cutset problem and describe the reduction from the loop cutset problem to the WFVS Problem. In Section 3 we present three randomized algorithms for the WFVS problem and their analysis. In Section 4 we compare experimentally WRA and MGA with respect to output quality and run time. 2. Background: The Loop Cutset Problem A short overview of the method of conditioning and definitions related to Bayesian networks are given below. See the book by Pearl (1988) for more details. We then define the loop cutset problem. Let P (u1; : : : ; un) be a probability distribution where each variable ui has a finite set of possible values called the domain of ui. A directed graph D with no directed cycles is called a Bayesian network of P if there is a 1-1 mapping between fu1; : : : ; ung and vertices in D, such that ui is associated with vertex i and P can be written as follows: P (u1; : : : ; un) = nY i=1 P (ui j ui1; : : : ; uij(i)) (1) where i1; : : : ; ij(i) are the source vertices of the incoming edges to vertex i in D. 220 Randomized Algorithms for the Loop Cutset Problem Suppose now that some variables fv1; : : : ; vlg among fu1; : : : ; ung are assigned specific values fv1; : : : ; vlg respectively. The updating problem is to compute the probability P (ui j v1 = v1; : : : ; vl = vl) for i = 1; : : :; n. A trail in a Bayesian network is a subgraph whose underlying graph is a simple path. A vertex b is called a sink with respect to a trail t if there exist two consecutive edges a ! b and b c on t. A trail t is active by a set of vertices Z if (1) every sink with respect to t either is in Z or has a descendant in Z and (2) every other vertex along t is outside Z. Otherwise, the trail is said to be blocked (d-separated) by Z. Verma and Pearl proved that if D is a Bayesian network of P (u1; : : :; un) and all trails between a vertex in fr1; : : : ; rlg and a vertex in fs1; : : : ; skg are blocked by ft1; : : :; tmg, then the corresponding sets of variables fur1; : : : ; urlg and fus1; : : : ; uskg are independent conditioned on fut1; : : : ; utmg (Verma & Pearl, 1988). Furthermore, Geiger and Pearl proved that this result cannot be enhanced (Geiger & Pearl, 1990). Both results were presented and extended by Geiger, Verma, and Pearl (1990). Using the close relationship between blocked trails and conditional independence, Kim and Pearl developed an algorithm update-tree that solves the updating problem on Bayesian networks in which every two vertices are connected with at most one trail (Kim & Pearl, 1983). Pearl then solved the updating problem on any Bayesian network as follows (Pearl, 1986). First, a set of vertices S is selected such that any two vertices in the network are connected by at most one active trail in S [ Z, where Z is any subset of vertices. Then, update-tree is applied once for each combination of value assignments to the variables corresponding to S, and, finally, the results are combined. This algorithm is called the method of conditioning and its complexity grows exponentially with the size of S. The set S is called a loop cutset. Note that when the domain size of the variables varies, then update-tree is called a number of times equal to the product of the domain sizes of the variables whose corresponding vertices participate in the loop cutset. If we take the logarithm of the domain size (number of values) as the weight of a vertex, then finding a loop cutset such that the sum of its vertices weights is minimum optimizes Pearl's updating algorithm in the case where the domain sizes may vary. We now give an alternative definition for a loop cutset S and then provide a probabilistic algorithm for finding it. This definition is borrowed from a paper by Bar-Yehuda et al. (1994). The underlying graph G of a directed graph D is the undirected graph formed by ignoring the directions of the edges in D. A cycle in G is a path whose two terminal vertices coincide. A loop in D is a subgraph of D whose underlying graph is a cycle. A vertex v is a sink with respect to a loop Gamma if the two edges adjacent to v in Gamma are directed into v. Every loop must contain at least one vertex that is not a sink with respect to that loop. Each vertex that is not a sink with respect to a loop Gamma is called an allowed vertex with respect to Gamma . A loop cutset of a directed graph D is a set of vertices that contains at least one allowed vertex with respect to each loop in D. The weight of a set of vertices X is denoted by w(X) and is equal to Pv2X w(v) where w(x) = log(jxj) and jxj is the size of the domain associated with vertex x. A minimum weight loop cutset of a weighted directed graph D is a loop cutset F Lambda of D for which w(F Lambda ) is minimum over all loop cutsets of G. The Loop Cutset Problem is defined as finding a minimum weight loop cutset of a given weighted directed graph D. 221 Becker, Bar-Yehuda, & Geiger The approach we take is to reduce the loop cutset problem to the weighted feedback vertex set problem, as done by Bar-Yehuda et al. (1994). We now define the weighted feedback vertex set problem and then the reduction. Let G = (V; E) be an undirected graph, and let w : V ! IR+ be a weight function on the vertices of G. A feedback vertex set of G is a subset of vertices F ` V such that each cycle in G passes through at least one vertex in F . In other words, a feedback vertex set F is a set of vertices of G such that by removing F from G, along with all the edges incident with F , we obtain a set of trees (i.e., a forest). The weight of a set of vertices X is denoted (as before) by w(X) and is equal to Pv2X w(v). A minimum feedback vertex set of a weighted graph G with a weight function w is a feedback vertex set F Lambda of G for which w(F Lambda ) is minimum over all feedback vertex sets of G. The Weighted Feedback Vertex Set (WFVS) Problem is defined as finding a minimum feedback vertex set of a given weighted graph G having a weight function w. The reduction is as follows. Given a weighted directed graph (D; w) (e.g., a Bayesian network), we define the splitting weighted undirected graph Ds with a weight function ws as follows. Split each vertex v in D into two vertices vin and vout in Ds such that all incoming edges to v in D become undirected incident edges with vin in Ds, and all outgoing edges from v in D become undirected incident edges with vout in Ds. In addition, connect vin and vout in Ds by an undirected edge. Now set ws(vin) = 1 and ws(vout) = w(v). For a set of vertices X in Ds, we define (X) as the set obtained by replacing each vertex vin or vout in X by the respective vertex v in D from which these vertices originated. Note that if X is a cycle in Ds, then (X) is a loop in D, and if Y is a loop in D, then Gamma 1(Y ) = Sv2Y Gamma 1(v) is a cycle in Ds where Gamma 1(v) = 8?!?: vin v is a sink on Y vout v is a source on Y fvin; voutg otherwise (A vertex v is a source with respect to a loop Y if the two edges adjacent to v in Y originate from v). This mapping between loops in D and cycles in Ds is one-to-one and onto. Our algorithm can now be easily stated. ALGORITHM LoopCutset Input: A Bayesian network D Output: A loop cutset of D 1. Construct the splitting graph Ds with weight function ws 2. Find a feedback vertex set F for (Ds; ws) using the Weighted Randomized Algorithm (WRA) 3. Output (F ). It is immediately seen that if WRA (developed in later sections) outputs a feedback vertex set F of Ds whose weight is minimum with high probability, then (F ) is a loop cutset of D with minimum weight with the same probability. This observation holds due to the one-to-one and onto correspondence between loops in D and cycles in Ds and because WRA never chooses a vertex that has an infinite weight. 222 Randomized Algorithms for the Loop Cutset Problem 3. Algorithms for the WFVS Problem Recall that a feedback vertex set of G is a subset of vertices F ` V such that each cycle in G passes through at least one vertex in F . In Section 3.1 we address the problem of finding a FVS with a minimum number of vertices and in Sections 3.2 and 3.3 we address the problem of finding a FVS with a minimum weight. Throughout, we allow G to have parallel edges. If two vertices u and v have parallel edges between them, then every FVS of G includes either u, v, or both. 3.1 The Basic Algorithms In this section we present a randomized algorithm for the FVS problem. First we introduce some additional terminology and notation. Let G = (V; E) be an undirected graph. The degree of a vertex v in G, denoted by d(v), is the number of vertices adjacent to v. A self-loop is an edge with two endpoints at the same vertex. A leaf is a vertex with degree less or equal 1, a linkpoint is a vertex with degree 2 and a branchpoint is a vertex with degree strictly higher than 2. The cardinality of a set X is denoted by jXj. A graph is called rich if every vertex is a branchpoint and it has no self-loops. Given a graph G, by repeatedly removing all leaves, and bypassing with an edge every linkpoint, a graph G0 is obtained such that the size of a minimum FVS in G0 and in G are equal and every minimum FVS of G0 is a minimum FVS of G. Since every vertex involved in a self-loop belongs to every FVS, we can transform G0 to a rich graph Gr by adding the vertices involved in self loops to the output of the algorithm. Our algorithm is based on the observation that if we pick an edge at random from a rich graph there is a probability of at least 1=2 that at least one endpoint of the edge belongs to any given FVS F . A precise formulation of this claim is given by Lemma 1 whose proof is given implicitly by Voss (1968, Lemma 4). Lemma 1 Let G = (V; E) be a rich graph, F be a feedback vertex set of G and X = V n F . Let EX denote the set of edges in E whose endpoints are all vertices in X and EF;X denote the set of edges in G that connect vertices in F with vertices in X. Then, jEXj ^ jEF;Xj. Proof. The graph obtained by deleting a feedback vertex set F of a graph G(V; E) is a forest with vertices X = V n F . Hence, jEXj ! jXj. However, each vertex in X is a branchpoint in G, and so, 3 jXj ^ X v2X d(v) = jEF;Xj + 2 jEXj: Thus, jEXj ^ jEF;Xj. 2 Lemma 1 implies that when picking an edge at random from a rich graph, it is at least as likely to pick an edge in EF;X than an edge in EX . Consequently, selecting a vertex at random from a randomly selected edge has a probability of at least 1=4 to belong to a minimum FVS. This idea yields a simple algorithm to find a FVS. 223 Becker, Bar-Yehuda, & Geiger ALGORITHM SingleGuess(G,j) Input: An undirected graph G0 and an integer j ? 0. Output: A feedback vertex set F of size ^ j, or "Fail" otherwise. For i = 1; : : :; j 1. Reduce GiGamma 1 to a rich graph Gi while placing self loop vertices in F . 2. If Gi is the empty graph Return F 3. Pick an edge e = (u; v) at random from Ei 4. Pick a vertex vi at random from (u; v) 5. F F [ fvig 6. V V n fvig Return "Fail" Due to Lemma 1, when SingleGuess(G; j) terminates with a FVS of size j, there is a probability of at least 1=4j that the output is a minimum FVS. Note that steps 3 and 4 in SingleGuess determine a vertex v by first selecting an arbitrary edge and then selecting an arbitrary endpoint of this edge. An equivalent way of achieving the same selection rule is to choose a vertex with probability proportional to its degree: p(v) = d(v)P u2V d(u) = d(v) 2 Delta jEj To see the equivalence of these two selection methods, define Gamma (v) to be a set of edges whose one endpoint is v, and note that for graphs without self-loops, p(v) = X e2Gamma (v) p(vje) Delta p(e) = 12 X e2Gamma (v) p(e) = d(v)2 Delta jEj This equivalent phrasing of the selection criterion is easier to extend to the weighted case and will be used in the following sections. An algorithm for finding a minimum FVS with high probability, which we call RepeatedGuess, can now be described as follows: Start with j = 1. Repeat SingleGuess c 4j times where c ? 1 is a parameter defined by the user. If in one of the iterations a FVS of size ^ j is found, then output this FVS, otherwise, increase j by one and continue. ALGORITHM RepeatedGuess(G,c) Input: An undirected graph G and a constant c ? 1. Output: A feedback vertex set F . For j = 1; : : : ; jV j Repeat c 4j times 1. F SingleGuess(G; j) 2. If F is not "Fail" then Return F End fRepeatg End fForg 224 Randomized Algorithms for the Loop Cutset Problem The main claims about these algorithms are given by the following theorem. Theorem 2 Let G be an undirected graph and c * 1 be a constant. Then, SingleGuess(G; k) outputs a FVS whose expected size is no more than 4k, and RepeatedGuess(G; c) outputs, after O(c 4kkn) steps, a minimum FVS with probability at least 1 Gamma (1 Gamma 14k )c4 k, where k is the size of a minimum FVS and n is the number of vertices. The claims about the probability of success and number of steps follow immediately from the fact that the probability of success of SingleGuess(G; j) is at least (1=4)j and that, in case of success, O(c 4j) iterations are performed each taking O(jn) steps. The result follows from the fact that Pkj=1 j4j is of order O(k4k). The proof about the expected size of a single guess is presented in the next section. Theorem 2 shows that each guess produces a FVS which, on the average, is not too far from the minimum, and that after enough iterations, the algorithm converges to the minimum with high probability. In the weighted case, discussed next, we managed to achieve each of these two guarantees in separate algorithms, but we were unable to achieve both guarantees in a single algorithm. 3.2 The Weighted Algorithms We now turn to the weighted FVS problem (WFVS) of size k which is to find a feedback vertex set F of a vertex-weighted graph (G; w), w : V ! IR+, of size less or equal k such that w(F ) is minimized. Note that for the weighted FVS problem we cannot replace each linkpoint v with an edge because if v has weight lighter than its branchpoint neighbors then v can participate in a minimum weight FVS of size k. A graph is called branchy if it has no endpoints, no self loops, and, in addition, each linkpoint is connected only to branchpoints (Bar-Yehuda, Geiger, Naor, & Roth, 1994). Given a graph G, by repeatedly removing all leaves, and bypassing with an edge every linkpoint that has a neighbor with equal or lighter weight, a graph G0 is obtained such that the weight of a minimum weight FVS (of size k) in G0 and in G are equal and every minimum WFVS of G0 is a minimum WFVS of G. Since every vertex with a self-loop belongs to every FVS, we can transform G0 to a branchy graph without self-loops by adding the vertices involved in self loops to the output of the algorithm. To address the WFVS problem we offer two slight modifications to the algorithm SingleGuess presented in the previous section. The first algorithm, which we call SingleWGuessI, is identical to SingleGuess except that in each iteration we make a reduction to a branchy graph instead of a reduction to a rich graph. It chooses a vertex with probability proportional to the degree using p(v) = d(v)= Pu2V d(u). Note that this probability does not take the weight of a vertex into account. A second algorithm, which we call SingleWGuessII, chooses a vertex with probability proportional to the ratio of its degree over its weight, p(v) = d(v)w(v)= X u2V d(u) w(u): (2) 225 Becker, Bar-Yehuda, & Geiger ALGORITHM SingleWGuessI(G,j) Input: An undirected weighted graph G0 and an integer j ? 0. Output: A feedback vertex set F of size ^ j, or "Fail" otherwise. For i = 1; : : :; j 1. Reduce GiGamma 1 to a branchy graph Gi(Vi; Ei) while placing self loop vertices in F . 2. If Gi is the empty graph Return F 3. Pick a vertex vi 2 Vi at random with probability pi(v) = di(v)= Pu2Vi di(u) 4. F F [ fvig 5. V V n fvig Return "Fail" The second algorithm uses Eq. 2 for computing p(v) in Line 3. These two algorithms have remarkably different guarantees of performance. Version I guarantees that choosing a vertex that belongs to any given FVS is larger than 1=6, however, the expected weight of a FVS produced by version I cannot be bounded by a constant times the weight of a minimum WFVS. Version II guarantees that the expected weight of its output is bounded by 6 times the weight of a minimum WFVS, however, the probability of converging to a minimum after any fixed number of iterations can be arbitrarily small. We first demonstrate via an example the negative claims. The positive claims are phrased more precisely in Theorem 3 and proven thereafter. Consider the graph shown in Figure 1 with three vertices a,b and c, and corresponding weights w(a) = 6, w(b) = 3ffl and w(c) = 3m, with three parallel edges between a and b, and three parallel edges between a and c. The minimum WFVS F Lambda with size 1 consists of vertex a. According to Version II, the probability of choosing vertex a is (Eq. 2): p(a) = ffl(1 + 1=m) Delta ffl + 1 So if ffl is arbitrarily small and m is sufficiently large, then the probability of choosing vertex a is arbitrarily small. Thus, the probability of choosing a vertex from some F Lambda by the criterion d(v)=w(v), as done by Version II, can be arbitrarily small. If, on the other hand, Version I is used, then the probability of choosing a; b, or c is 1=2; 1=4; 1=4, respectively. Thus, the expected weight of the first vertex to be chosen is 3=4 Delta (ffl + m + 4), while the weight of a minimum WFVS is 6. Consequently, if m is sufficiently large, the expected weight of a WFVS found by Version I can be arbitrarily larger than a minimum WFVS. The algorithm for repeated guesses, which we call RepeatedWGuessI(G; c; j) is as follows: repeat SingleWGuessI(G; j) c 6j times, where j is the minimal number of vertices of a minimum weight FVS we seek. If no FVS is found of size ^ j, the algorithm outputs that the size of a minimum WFVS is larger than j with high probability, otherwise, it outputs the lightest FVS of size less or equal j among those explored. The following theorem summarizes the main claims. 226 Randomized Algorithms for the Loop Cutset Problem c a b w(c) = 3ffl w(a) = 6 w(b) = 3m Figure 1: The minimum WFVS F Lambda = fag. Theorem 3 Let G be a weighted undirected graph and c * 1 be a constant. a) The algorithm RepeatedWGuessI(G; c; k) outputs after O(c 6kkn) steps a minimum WFVS with probability at least 1 Gamma (1 Gamma 16k )c6 k, where k is the minimal size of a minimum weight FVS of G and n is the number of vertices. b) The algorithm SingleWGuessII(G,k) outputs a feedback vertex set whose expected weight is no more than six times the weight of a minimum weight FVS. The proof of each part requires a preliminary lemma. Lemma 4 Let G = (V; E) be a branchy graph, F be a feedback vertex set of G and X = V n F . Let EX denote the set of edges in E whose endpoints are all vertices in X and EF;X denote the set of edges in G that connect vertices in F with vertices in X. Then, jEXj ^ 2 Delta jEF;Xj. Proof. Let Xb be the set of branchpoints in X. We replace every linkpoint in X by an edge between its neighbors, and denote the resulting set of edges between vertices in Xb by EbXb and between vertices in Xb and F by EbF;Xb. The proof of Lemma 1 shows that jEbXbj ^ jEbF;Xbj: Since every linkpoint in X has both neighbors in the set Xb [ F , the following holds: jEXj ^ 2 Delta jEbXbj and jEF;Xj = jEbF;Xbj: Hence, jEXj ^ 2 Delta jEF;Xj. 2 An immediate consequence of Lemma 4 is that the probability of randomly choosing an edge that has at least one endpoint that belongs to a FVS is greater or equal 1=3. Thus, selecting a vertex at random from a randomly selected edge has a probability of at least 1=6 to belong to a FVS. Consequently, if the algorithm terminates after c 6k iterations, with a WFVS of size k, there is a probability of at least 1 Gamma (1 Gamma 16k )c6 k that the output is a minimum WFVS of size at most k. This proves part (a) of Theorem 3. Note that since k is not known in advance, we use RepeatedWGuessI(G; c; j) with increasing values of j until a FVS is found, say when j=J. When such a set is found it is still possible that there exists a WFVS with more than J vertices that has a smaller weight than the one found. This happens when k ? J. However, among the WFVSs of size at most J, the algorithm finds one with minimum weight with high probability. The second part requires the following lemma. 227 Becker, Bar-Yehuda, & Geiger Lemma 5 Let G be a branchy graph and F be a FVS of G. Then,X v2V d(v) ^ 6 X v2F d(v): Proof. Denote by dY (v) the number of edges between a vertex v and a set of vertices Y . Then, X v2V d(v) = X v2X d(v) + X v2F d(v) =X v2X dX(v) + X v2X dF (v) + X v2F d(v): Due to Lemma 4, X v2X dX(v) = 2jEXj ^ 4jEF;Xj = 4 X v2X dF (v): (3) Consequently, X v2V d(v) ^ 4 X v2X dF (v)+X v2X dF (v) + X v2F d(v) ^ 6 X v2F d(v) as claimed. 2 We can now prove part (b) of Theorem 3 analyzing SingleWGuessII(G,k). Recall that Vi is the set of vertices in graph Gi in iteration i, di(v) is the degree of vertex v in Gi, and vi is the vertex chosen in iteration i. Furthermore, recall that pi(v) is the probability to choose vertex v in iteration i. The expected weight Ei(w(v)) = Pv2Vi w(v) Delta pi(v) of a chosen vertex in iteration i is denoted with ai. Thus, due to the linearity of the expectation operator, E(w(F )) = Pki=1 ai, assuming jF j = k. We define a normalization constant for iteration i as follows: fli = " X u2Vi di(u) w(u) # Gamma 1 Then, pi(v) = fli Delta di(v)w(v) and ai = X v2Vi w(v) Delta di(v)w(v) Delta fli = fli Delta X v2Vi di(v) Let F Lambda be a minimum FVS of G and F Lambda i be minimum weight FVS of the graph Gi. The expected weight Ei(w(v)jv 2 F Lambda i )) of a vertex chosen from F Lambda i in iteration i is denoted with bi. We have, bi = X v2FLambda i w(v) Delta pi(v) = fli Delta X v2FLambda i di(v) By Lemma 5, ai=bi ^ 6 for every i. 228 Randomized Algorithms for the Loop Cutset Problem Recall that by definition F Lambda 2 is the minimum FVS in the branchy graph G2 obtained from G1 n fv1g. We get, E(w(F Lambda )) * E1(w(v)jv 2 F Lambda 1 )) + E(w(F Lambda 2 )) because the right hand side is the expected weight of the output F assuming the algorithm finds a minimum FVS on G2 and just needs to select one additional vertex, while the left hand side is the unrestricted expectation. By repeating this argument we get, E(w(F Lambda )) * b1 + E(w(F Lambda 2 )) * Delta Delta Delta * kX i=1 bi Using Pi ai= Pi bi ^ maxi ai=bi ^ 6, we obtain E(w(F )) ^ 6 Delta E(w(F Lambda )): Hence, E(w(F )) ^ 6 Delta w(F Lambda ) as claimed. 2 The proof that SingleGuess(G; k) outputs a FVS whose expected size is no more than 4k (Theorem 2) where k is the size of a minimum FVS is analogous to the proof of Theorem 3 in the following sense. We assign a weight 1 to all vertices and replace the reference to Lemma 5 by a reference to the following claim: If F is a FVS of a rich graph G, then Pv2V d(v) ^ 4 Pv2F d(v). The proof of this claim is identical to the proof of Lemma 5 except that instead of using Lemma 4 we use Lemma 1. 3.3 The Practical Algorithm In previous sections we presented several algorithms for finding minimum FVS with high probability. The description of these algorithms was geared towards analysis, rather than as a prescription to a programmer. In particular, the number of iterations used within RepeatedWGuessI(G; c; k) is not changed as the algorithm is run with j ! k. This feature allowed us to regard each call to SingleWGuessI(G; j) made by RepeatedWGuessI as an independent process. Furthermore, there is a small probability for a very long run even when the size of the minimum FVS is small. We now slightly modify RepeatedWGuessI to obtain an algorithm, termed WRA, which does not suffer from these deficiencies. The new algorithm works as follows. Repeat SingleWGuessI(G; jV j) for min(Max; c 6w(F)) iterations, where w(F ) is the weight of the lightest WFVS found so far and Max is some specified constant determining the maximum number of iterations of SingleWGuessI. ALGORITHM WRA(G; c; Max) Input: An undirected weighted graph G(V; E) and constants Max and c ? 1 Output: A feedback vertex set F F SingleWGuessI (G; jV j) M min(Max; c 6w(F)); i 1; While i ^ M do 1. F 0 SingleWGuessI(G; jV j) 2. If w(F 0) ^ w(F ) then 229 Becker, Bar-Yehuda, & Geiger jV j jEj values size MGA WRA Eq. 15 25 2-6 3-6 12 81 7 15 25 2-8 3-6 7 89 4 15 25 2-10 3-6 6 90 4 25 55 2-6 7-12 3 95 2 25 55 2-8 7-12 3 97 0 25 55 2-10 7-12 0 100 0 55 125 2-10 17-22 0 100 0 31 652 17 Figure 2: Number of graphs in which MGA or WRA yield a smaller loop cutset. The last column records the number of graphs for which the two algorithms produced loop cutsets of the same weight. Each line in the table is based on 100 graphs. F F 0; M min(Max; c 6w(F)) 3. i i + 1; End fWhileg Return F Theorem 6 If Max * c6k, where k is the minimal size of a minimum WFVS of an undirected weighted graph G, then WRA(G; c; Max) outputs a minimum WFVS of G with probability at least 1 Gamma (1 Gamma 16k )c6 k. The proof is an immediate corollary of Theorem 3. The choice of Max and c depend on the application. A decision-theoretic approach for selecting such values for any-time algorithms is discussed by Breese and Horvitz (1990). 4. Experimental Results The experiments compared the outputs of WRA vis-`a-vis a greedy algorithm GA and a modified greedy algorithm MGA (Becker & Geiger, 1996) based on randomly generated graphs and on some real graphs contributed by the Hugin group (www.hugin.com). The random graphs are divided into three sets. Graphs with 15 vertices and 25 edges where the number of values associated with each vertex is randomly chosen between 2 and 6, 2 and 8, and between 2 and 10. Graphs with 25 vertices and 55 edges where the number of values associated with each vertex is randomly chosen between 2 and 6, 2 and 8, and between 2 and 10. Graphs with 55 vertices and 125 edges where the number of values associated with each vertex is randomly chosen between 2 and 10. Each instance of the three classes is based on 100 random graphs generated as described by Suermondt and Cooper (1990). The total number of random graphs we used is 700. The results are summarized in the table of Figure 2. WRA is run with Max = 300 and c = 1. The two algorithms, MGA and WRA, output loop cutsets of the same size in only 230 Randomized Algorithms for the Loop Cutset Problem Name jV j jEj jF Lambda j GA MGA WRA Water 32 123 16 40.7 42.7 29.5 Mildew 35 80 14 48.1 40.5 39.3 Barley 48 126 20 72.1 76.3 57.3 Munin1 189 366 59 159.4 167.5 122.6 Figure 3: Log size (base 2) of the loop cutsets found by GA, MGA, and WRA. 17 graphs and when the algorithms disagree, then in 95% of these graphs WRA performed better than MGA. The actual run time of W RA(G; 1; 300) is about 300 times slower than GA (or MGA) on G. On the largest random graph we used, it took 4.5 minutes. Most of the time is spend in the last improvement of WRA. Considerable run time can be saved by letting Max = 5. For all 700 graphs, WRA(G,1,5) has already obtained a better loop cutset than MGA. The largest improvement, with Max = 300, was from a weight of 58.0 (log2 scale) to a weight of 35.9. The improvements in this case were obtained in iterations 1, 2, 36, 83, 189 with respective weights of 46.7, 38.8, 37.5, 37.3, 35.9 and respective sizes of 22, 18, 17, 18, and 17 nodes. On the average, after 300 iterations, the improvement for the larger 100 graphs was from a weight of 52 to 39 and from size 22 to 20. The improvement for the smaller 600 graphs was from a weight of 15 to 12.2 and from size 9 to 6.7. The second experiment compared between GA, MGA and WRA on four real Bayesian networks showing that WRA outperformed both GA and MGA after a single call to SingleWGuessI. The weight of the output continued to decrease logarithmically with the number of iterations. We report the results with Max = 1000 and c = 1. Run time was between 3 minutes for Water and 15 minutes for Munin1 on a Pentium 133 with 32M RAM. 5. Discussion Our randomized algorithm, WRA, has been incorporated into the popular genetic software FASTLINK 4.1 by Alejandro Sch"affer who develops and maintains this software at the National Institute of Health. WRA replaced previous approximation algorithms for finding FVS because with a small Max value it already matched or improved FASTLINK 4.0 on most datasets examined. The datasets used for comparison are described by Becker et al. (1998). The main characteristics of these datasets is that they were all collected by geneticists, they have a small number of loops, and a large number of values at each node (tens to hundreds depending on the genetic analysis). For such networks the method of conditioning is widely used by geneticists. The leading inference algorithm, however, for Bayesian networks is the clique-tree algorithm (Lauritzen & Spiegelhalter, 1988) which has been further developed in several papers (Jensen, Lauritzen, & Olsen, 1990a; Jensen, Olsen, & Andersen, 1990b). For the networks presented in Table 3 conditioning is not a feasible method while the clique tree algorithm can and is being used to compute posterior probabilities in these networks. Furthermore, it has been shown that the weight of the largest clique is bounded by the weight of the loop cutset union the largest parent set of a vertex in a Bayesian network implying that the 231 Becker, Bar-Yehuda, & Geiger clique tree algorithm is always superior in time performance over the conditioning algorithm (Shachter, Andersen, & Szolovits, 1994). The two methods, however, can be combined to strike a balance between time and space requirements as done within the bucket elimination framework (Dechter, 1999). The algorithmic ideas behind the randomized algorithms presented herein can also be applied for constructing good clique trees and initial experiments confirm that an improvement over deterministic algorithms is often obtained. The idea is that instead of greedily selecting the smallest clique when constructing a clique tree, one would randomly select the next clique according to the relative weights of the candidate cliques. It remains to develop the theory behind random choices of clique trees before a solid assessment can be presented. Currently, there is no algorithm for finding a clique tree such that its size is guaranteed to be close to optimal with high probability. Horvitz et al. (1989) show that the method of conditioning can be useful for approximate inference. In particular, they show how to rank the instances of a loop cutset according to their prior probabilities assuming all variables in the cutset are marginally independent. The conditioning algorithm can then be run according to this ranking and the answer to a query be given as an interval that shrinks towards the exact solution as more instances of the loop cutset are considered (Horvitz, Suermondt, & Cooper, 1989; Horvitz, 1990). Applying this idea without making independence assumptions is described by Darwiche (1994). So if the maximal clique is too large to store one can still perform approximate inferences using the conditioning algorithm. Acknowledgment We thank Seffi Naor for fruitful discussions. Part of this work was done while the third author was on sabbatical at Microsoft Research. A variant of this work has been presented at the fifteenth conference on uncertainty in artificial intelligence, July 1999, Sweden. References Bafna, V., Berman, P., & Fujito, T. (1995). Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs. In Proceedings of the Sixth Annual Symposium on Algorithms and Computation (ISAAC95), pp. 142-151. Bar-Yehuda, R., Geiger, D., Naor, J., & Roth, R. (1994). Approximation algorithms for the feedback vertex set problems with applications to constraint satisfaction and Bayesian inference. In Proceedings of the 5th Annual ACM-Siam Symposium On Discrete Algorithms, pp. 344-354. Becker, A., & Geiger, D. (1994). Approximation algorithms for the loop cutset problem. In Proceedings of the 10th conference on Uncertainty in Artificial Intelligence, pp. 60-68. Becker, A., & Geiger, D. (1996). Optimization of pearl's method of conditioning and greedylike approximation algorithms for the feedback vertex set problem. Artificial Intelligence, 83, 167-188. 232 Randomized Algorithms for the Loop Cutset Problem Becker, A., Geiger, D., & Schaffer, A. (1998). Automatic selection of loop breakers for genetic linkage analysis. Human Heredity, 48, 47-60. Bodlaender, H. (1990). On disjoint cycles. International Journal of Foundations of Computer Science (IJFCS), 5, 59-68. Breese, J., & Horvitz, E. (1990). Ideal reformulation of belief netwroks. In Proceedings of the 6th conference on Uncertainty in Artificial Intelligence, pp. 64-72. Darwiche, A. (1994). ffl-bounded conditioning: A method for the approximate updating of causal networks. Research note, Rockwell Science Center. Dechter, R. (1990). Enhancement schemes for constraint processing: backjumping, learning, and cutset decomposition. Artificial Intelligence, 41, 273-312. Dechter, R. (1999). Bucket elimination: A unifying framework for structure-driven inference. Artificial Intelligence, To appear. Downey, R., & Fellows, M. (1995a). Fixed-parameter tractability and completeness I: Basic results. SIAM Journal on Computing, 24 (4), 873-921. Downey, R., & Fellows, M. (1995b). Parameterized computational feasibility. In P. Clote, . J. R. (Ed.), Feasible Mathematics II, pp. 219-244. Birkhauser, Boston. Fujito, T. (1996). A note on approximation of the vertex cover and feedback vertex set problems - unified approach. Information Processing Letters, 59, 59-63. Garey, M., & Johnson, D. (1979). Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman, San Francisco, California. Geiger, D., & Pearl, J. (1990). On the logic of causal models. In Uncertainty in Artificial Intelligence 4, pp. 3-14 New York. North-Holland. Geiger, D., Verma, T., & Pearl, J. (1990). Identifying independence in bayesian networks. Networks, 20, 507-534. Horvitz, E. J. (1990). Computation and action under bounded resources. Ph.D dissertation, Stanford university. Horvitz, E. J., Suermondt, H. J., & Cooper, G. H. (1989). Bounded conditioning: Flexible inference for decisions under scarce resources. In Proceedings of 5th conference on Uncertainty in Artificial Intelligence, pp. 182-193. Morgan Kaufmann. Jensen, F., Lauritzen, S. L., & Olsen, K. (1990a). Bayesian updating in causal probabilisitic networks by local computations. Computational Statistics Quarterly, 4, 269-282. Jensen, F., Olsen, K., & Andersen, S. (1990b). An algebra of bayesian belief universes for knowledge-based systems. Networks, 20, 637-659. Kim, H., & Pearl, J. (1983). A computational model for combined causal and diagnostic reasoning in inference systems. In Proceedings of the Eighth International Joint Conference on Artificial Intelligence (IJCAI83), pp. 190-193. 233 Becker, Bar-Yehuda, & Geiger Lang, K. (1997). Mathematical and statistical methods for genetic analysis. Springer. Lange, K., & Elston, R. (1975). Extensions to pedigree analysis. I. likelihood calculation for simple and complex pedigrees. Human Heredity, 25, 95-105. Lauritzen, S., & Spiegelhalter, D. (1988). Local computations with probabilities on graphical structures and their application to expert systems (with discussion). Journal Royal Statistical Society, B, 50, 157-224. Ott, J. (1991). Analysis of human genetic linkage (revised edition). The Johns Hopkins University Press. Pearl, J. (1986). Fusion, propagation and structuring in belief networks. Artificial Intelligence, 29, 241-288. Pearl, J. (1988). Probabilistic reasoning in intelligent systems: Networks of plausible inference. Morgan Kaufmann, San Mateo, California. Peot, M., & Shachter, R. (1991). Fusion and propagation with multiple observations in belief networks. Artificial Intelligence, 48, 299-318. Shachter, R., Andersen, S., & Szolovits, P. (1994). Global conditioning for probabilistic inference in belief networks. In Proceedings of the tenth conference on Uncertainty in Artificial Intelligence, pp. 514-522. Morgan Kaufmann. Suermondt, H., & Cooper, G. (1990). Probabilistic inference in multiply connected belief networks using loop cutsets. International Journal of Approximate Reasoning, 4, 283- 306. Verma, T., & Pearl, J. (1988). Causal networks: Semantics and expressiveness. In Proceedings of 4th Workshop on Uncertainty in Artificial Intelligence, pp. 352-359. Voss, H. (1968). Some properties of graphs containing k independent circuits. In Proceedings of Colloquium Tihany, pp. 321-334 New York. Academic Press. 234