Algorithms for the Nearest Assignment Problem

1 Introduction

We focus on the following problem in probabilistic graphical models (PGMs): given a real number q such that 0 ≤ q ≤ 1 and a PGM B, find a configuration ω of variables in B such that ∣∣∣log ( q PB(ω) )∣∣∣ is minimized where PB(ω) is the probability of ω according to B. We call this problem the nearest assignment problem or NAP in short. NAP includes several well-known tasks such as finding the most likely configuration, also called the most probable explanation (MPE) or maximum-a-posteriori (MAP) estimate, as a special case (when q = 1) and is thus intractable or NP-hard in general.

A solution to NAP is desired in several real-world applications. For example, it is possible to construct a piece-wise approximation of the CDF of a PGM, possibly conditioned on evidence, by answering a few NAP queries (e.g., after finding the min and max assignments, we can recursively set q to midway between the probability of two known assignments). This approximation is useful in interactive applications [Kulesza et al., 2015], in particular, for explaining the shape of the distribution to the user. CDFs can also be used to check whether two probability distributions are similar subject to a known renaming of their variables, a key sub-task in learning lifted probabilistic models such as Markov logic [Richardson and Domingos, 2006]. Other applications of NAP include (i) finding nearest neighbors when the distance distribution is compactly stored as a PGM for very large datasets; (ii) hardware test case generation [Fournier et al., 1999; Dechter et al., 2002]; and (iii) generating explanations that are close to a given explanation in terms of probability (cf. the DARPA Explainable AI program).

NAP is closely related to the order statistics problem [Smith et al., 2017] and similar to the latter is NP-hard even on so-called independent PGMs - PGMs having only univariate potentials/CPTs. Therefore, in order to facilitate the development of non-trivial algorithms for NAP, we show how to encode NAP on independent PGMs as a two-way number partitioning problem. This encoding enables us to leverage well-researched algorithms from the number partitioning literature and develop a greedy algorithm with guarantees on approximation error for solving NAP on independent PGMs. We call it Algorithm INAP.

We then use the 0-cutset [Bidyuk and Dechter, 2004] concept, which is defined as a subset of variables such that when the subset is removed, the remaining PGM has no edges (and thus has zero treewidth) to yield an algorithm with guarantees on complexity and accuracy for arbitrary, high treewidth PGMs. Similar to cutset conditioning [Dechter, 1990], the key idea in this algorithm is to enumerate all configurations to the 0-cutset variables and then solve the sub-problem on each independent PGM using INAP. To make the technique practical, we propose generating configurations of the 0-cutset variables via random sampling and local search. This yields a stochastic anytime version of our 0-cutset algorithm, similar to previously proposed cutset sampling and local search algorithms [Bidyuk and Dechter, 2007; Kask and Dechter, 1996].

We empirically evaluate 0-cutset based sampling and local search algorithms on various benchmark networks from the 2014 UAI competition [Gogate, 2014], comparing their performance with conventional local search and random sampling algorithms (that do not exploit cutsets). Our experiments show that our new algorithms converge faster and are often orders of magnitude better in terms of approximation error than random sampling and local search, especially when q is closer to either the min or the max probability in the model.

2 Preliminaries and Notation

We focus on Bayesian networks [Pearl, 1988] having binary variables noting that results presented in this paper can be easily extended to Markov networks and multi-valued variables. Let X = {X1, . . . ,Xn} denote a set of n Boolean random variables, namely each variable Xi takes values from the set {0, 1}. We denote the variable assignments Xi = 1 and Xi = 0 by xi and xi respectively.

A discrete Bayesian network B is a triple 〈X, P, G〉 where P is a set of conditional probability tables (CPTs) and G is a directed acyclic graph which has one node for each variable. Edges in G define scopes of CPTs. In particular, each CPT Pi ∈ P = {P1, . . . , Pn} has the form Pi(Xi|pa(Xi)) where Xi ∈ X and pa(Xi) is the set of parents of Xi in G. Given a CPT Pi, we will use the notation S(Pi) to denote the scope of Pi, namely S(Pi) = {Xi} ∪ pa(Xi). B represents the probability distribution: PB(ω) = ∏ni=1 Pi(ωS(Pi)) where ω is an assignment of values to all variables in X and ωS(Pi) denotes the projection of ω on the scope of Pi. We will use ω to denote the assignment in which all variable assignments in ω are flipped. For example, if ω = (x1, x2, x3) then ω = (x1, x2, x3).

A primal graph or a moral graph of a Bayesian network B is an undirected graph D ≡ (V, E) which has one node Vi ∈ V for each variable Xi in B and an edge between any two variables that are in the scope of a CPT, namely E = {(Vi, Vj)|∃Pk such that {Vi, Vj} ⊆ S(Pk)}.

An independent Bayesian Network (IBN) is a Bayesian network having no edges. Thus, in an IBN the scope of each CPT Pi equals {Xi} and its primal graph is empty. A 0-cutset of an undirected graph is a subset of nodes C such that when all nodes in C are removed, the remaining graph is empty. This paper addresses the following inference task

Definition 1 (Nearest Assignment Problem (NAP)). Given a Bayesian network B and a real number 0 ≤ q ≤ 1, find an assignment ω of values to all variables of B such that ∣∣∣log ( q PB(ω) )∣∣∣ is minimized. 2.1 2-way Number Partitioning

Given a multi-set S of positive real numbers, the 2-way number partitioning problem is defined as finding a partition S1, S2 of S, namely S1 ∪ S2 = S and S1 ∩ S2 = ∅, such that

| ∑α∈S1 α- ∑β∈S2 β| is minimized. Popular approaches for solving number partitioning include the greedy method, Karmarkar-Karp heuristic [Karmarkar and Karp, 1983] and branch and bound algorithms [Korf, 1998]. In this paper, we use the KarmarkarKarp heuristic because of its associated guarantees to yield an algorithm for solving NAP, noting that sophisticated algorithms from the number partitioning literature can be easily employed to further improve our proposed method.

3 NAP on IBNs

In this section, we develop an algorithm with guarantees for solving NAP over IBNs. As mentioned earlier, NAP is closely related to the order-statistics problem [Smith et al., 2017]. In particular, Smith et al. showed that finding an assignment having the median rank in IBNs is NP-hard via a reduction from the 2-way number partitioning problem. Setting q = PB(ωm) where ωm is the assignment having the median rank in B yields the following proposition:

Proposition 1. NAP on IBNs is NP-hard in general.

A key use of this NP-hardness reduction is that it enables us to encode NAP on IBNs as a number partitioning problem and thus leverage algorithms developed in the literature on number partitioning [Vazirani, 2001; Korf, 1998; Karmarkar and Karp, 1983]. We describe a possible encoding next. Without loss of generality, for each variable Xi, let Pi(xi) ≥ Pi(xi) and q2 ≥ µ where µ = ∏i Pi(xi)Pi(xi). We claim that an assignment ω that minimizes | log(q) - log(PB(ω))| can be recovered by solving the following 2-way number partitioning problem:

Definition 2 (2-way Number Partitioning Encoding). Given an independent Bayesian network B ≡ 〈X, P, G〉, we construct a set S = {log ( Pi(xi) Pi(xi) ) |Pi ∈ P} ∪ {log ( q2 µ )}. The 2-way number partitioning problem given S is to find a 2way partition S1 and S2 of S such that | ∑α∈S1 α-∑β∈S2 β| is minimized.

Proof. (Sketch)

Theorem 1. Finding an assignment ω that minimizes ∣∣∣log ( q PB(ω) )∣∣∣ is equivalent to solving the 2-way number partitioning problem described in Definition 2.

Substituting µ = PB(ω)PB(ω) in Eq. (2), we get

We will simplify log ( PB(ω) PB(ω) ) using the following notation. Let X1 and X2 denote the subsets of variables which are assigned to 1 and 0 respectively in ω.

Without loss of generality, let

Algorithm 1 INAP: Greedy Algorithm for NAP over IBNs

Input: An Independent Bayesian network B ≡ 〈X, P, G〉 and a probability q

Output: Nearest assignment ω to q Begin:

• 1: S = ∅; µ = 1
• 2: for each variable Xi in X do
• 3: µ = µ×Pi(xi)P(xi)
• 5: S = S ∪ {log ( q2 µ )}
• 4: S = S ⋃ {log ( Pi(xi) Pi(xi) )}
• 6: Find a partition S1 and S2 of S using either the greedy method or Karmarkar-Karp heuristic [Karmarkar and Karp, 1983]
• 7: Construct ω from S1 and S2 using Corollary 1
• 8: return ω

End.

Combining Equations (3), (5), (6) and (7), we get:

Given a solution to the number partitioning problem described in Definition 2, we can use Theorem 1 to construct the nearest assignment as follows.

3.1 Poly-time Approximation Algorithm for Solving NAP over IBNs

Theorem 1, Corollary 1 and the Karmarkar-Karp heuristic yields Algorithm INAP (see Algorithm 1). The algorithm first constructs the number partitioning problem using Definition 2 (lines 1-5). Then, it uses number partitioning algorithms to construct the two subsets S1 and S2 (line 6). Finally, it uses Corollary 1 to compute the nearest assignment from S1 and S2 (line 7). Note that Algorithm INAP assumes that for each variable Xi, Pi(xi) ≥ Pi(xi) and q2 ≥ µ. The two assumptions are required because the Karmarkar-Karp heuristic has guarantees on the approximation error only when all numbers are positive. When the first assumption is violated we use log ( Pi(xi) Pi(xi) ) instead of log ( Pi(xi) Pi(xi) ) and then flip the assignment to the corresponding variable (namely replace xi by xi and vice versa) while constructing ω from S1 and S2.

When the second assumption is violated, we use log ( µ q2 ) instead of log ( q2 µ ) and return ω instead of ω.

Since the Karmarkar-Karp algorithm outputs a 7/6 approximation [Matteo and Silvano, 1987], we can prove that Algorithm INAP has the following guarantees:

Theorem 2. Let ω∗ be the (optimal) nearest assignment to q, ω be the assignment returned by Algorithm INAP and T = ∑α∈S α. Then,

Proof. (Sketch) Without loss of generality, let q = PB(ω∗ ) and ∑α∈S1 α > ∑β∈S2 β. Since the greedy algorithm and Karmarkar-Karp method yield a 7/6 approximation, we have the following guarantees on the sets S1 and S2 computed in Step 6 of Algorithm INAP:

From Eqs. (8) and (9), we get:

We consider two cases.

• Case 1: log ( q2 µ ) is in set S1

Let X1 and X2 be subsets of variables such that ∀Xi ∈ X1, log ( Pi(xi) Pi(xi) ) is in S1 and ∀Xj ∈ X2, log ( Pj(xj) Pj(xj) ) is in S2. For Case 1, we can rewrite Eq. (10) as

• Case 2: log ( q2 µ ) is in set S2.

Rearranging Eq. (11) and substituting q = PB(ω∗ ), PB(ω) = ∏Xi∈X1 Pi(xi) ∏Xj∈X2 Pj(xj), and µ = ∏Xi∈X Pi(xi)Pi(xi), we get

For Case 2, performing similar analysis as above, we get:

Combining Eqs. (12) and (13), we get the following result:

From Theorem 2, we can see that Algorithm INAP is accurate when T is small. In turn, T is small when the following two conditions are satisfied: (1) the difference between q and õ is small, namely q is close to the probability of the median assignment in the network, and (2) the log odds, namely log ( Pi(xi) Pi(xi) ) of all variables are small.

4 NAP on Arbitrary Bayesian networks

Algorithm 2 0CNAP 0-cutset based algorithm for solving NAP on Arbitrary Bayesian networks

Input: Bayesian network B ≡ 〈X, P, G〉 and probability q Output: Nearest assignment ω to q Begin:

• 1: ωbest = a random assignment
• 2: C = A 0-cutset of B
• 3: for each assignment ωC to C do
• 4: Y = X \ C
• 6: Bc ≡ 〈Y,U,Gc ≡ (Y, ∅)〉
• 5: U = {Pi(ωS(Pi))|S(Pi) ̸⊂ C}
• 7: qc = q ∏i:S(Pi)⊆C Pi(ωS(Pi))
• 8: ωY = INAP(Bc, qc)
• 9: ω = (ωY, ωC)

10:

• if | log( PB(ω) 11: ωbest = ω
• 12: return ωbest

End.

In this section, we extend Algorithm INAP from independent Bayesian networks to arbitrary Bayesian networks, yielding an algorithm with guarantees on approximation error as well as time and (linear) space complexity.

The key idea in our proposed method is the following: (1) find a 0-cutset, namely remove a subset of variables from the primal graph of the Bayesian network until no edges remain, and (2) for each possible assignment to the 0-cutset variables, solve the sub-problem defined over an independent Bayesian network using Algorithm INAP and (3) return the assignment whose probability is closest to q over all sub-problems. Our proposed method is described in Algorithm 0CNAP (see Algorithm 2). The algorithm takes as input a Bayesian network B and a probability q and returns the nearest assignment to q in B (line 12). It begins by finding a zero cutset (line 2). Then, for all configurations ωC to the 0-cutset variables, it executes the following steps. First, it creates an independent Bayesian network Bc given ωC (lines 4-6). The variables of Bc are all variables in B minus the variables included in the 0-cutset. Note that once the 0-cutset variables are assigned a value, each CPT will be in one the two following states: (1) all variables of the CPT are assigned a value (fully instantiated CPTs); and (2) exactly one variable of the CPT is uninstantiated. The latter CPTs form the CPTs of Bc (line 5). Second, it computes qc, the remaining value of q that is relevant to the sub-problem over Bc. qc is obtained by dividing q by the product of CPTs that are fully instantiated (line 7). Third, it runs Algorithm INAP on the sub-problem defined

q )| < | log( PB(ωbest)

q

)| then on Bc and qc (line 8) and constructs a full assignment over all variables of B by concatenating the assignment returned by Algorithm INAP and ωC (line 9). Finally, it updates the best assignment if the full assignment defined in line 9 is better than the best assignment so far (lines 10-11).

4.1 Theoretical Guarantees

We can use Theorem 2 to yield the following guarantees on Algorithm 0CNAP (see Theorem 3). The key idea is that only bounds for the independent sub-problems are relevant and thus 0-cutset allows us to derive stronger guarantees. More formally, in Algorithm 0CNAP, let J = {1, . . . , 2|C|} index the iterations of the for loop of Algorithm 0CNAP. Also, let ω(k) = (ω(k) C , ω(k) Y ) denote the assignment generated in the k-th iteration (line 9) and let T (k) denote the sum of elements of set S constructed by Algorithm INAP in the k-iteration (line 8). We can prove that

Theorem 3. Let ω∗ be the (optimal) nearest assignment to q, and ω be the assignment returned by Algorithm 0CNAP. Then,

Proof. (Sketch) Let i be the index such that ω(i) C = ω∗C . Using Theorem 2, we have:

Substituting Eq. (17) in Eq. (14), we get:

However, since ω is the best assignment, we have

Combining Eqs. (18) and (19), we get:

Notice that since the error maxk∈J T (k) of Algorithm 0CNAP is bounded by the sum over log odds of a subset of variables plus a constant term, it is superior to INAP, whose error is bounded by the sum over log odds of all variables.

Moreover Theorem 3 suggests that in order to improve the accuracy (bounds), it is beneficial to select 0-cutset variables in such a way that the remaining variables have small log odds. In other words, Theorem 3 helps provide heuristic guidance for selecting good 0-cutsets.

4.2 Practical Considerations

A key issue with Algorithm OCNAP is that it has exponential computational complexity. Formally,

Proposition 2. The time complexity of AlgorithmOCNAP is O(2c r log(r)) where c is the size of the 0-cutset C and r is the number of variables in the set X \ C.

To make the algorithm practical, we propose to either sample or perform local search over the assignments to the 0cutset variables. Our proposed method belongs to the class of cutset sampling algorithms [Bidyuk and Dechter, 2007] which achieve variance reduction using the Rao-Blackwell Theorem. The key idea is that combining methods that have guarantees with sampling improves the quality of estimates output by the latter.

5 Experiments

In this section, we describe results of our extensive empirical investigation on a large number of benchmark problems from the UAI 2014 probabilistic inference competition. Our hypothesis is that given a time bound, cutset based local search and random sampling algorithms are more accurate than their conventional counterparts (that do not exploit cutsets).

Algorithms. We implemented four algorithms: (a) Random Sampling (RS): We generate assignments ω uniformly at random and output the one having the smallest ∣∣∣log ( q PB(ω) )∣∣∣. (b) 0-cutset Random Sampling (CRS): Given a cutset C, we generate assignments ωC to the cutset variables uniformly at random and then use the KarmarkarKarp heuristic to compute the assignment ωY to the remaining variables given ωC. As before, we choose the assignment ω = (ωC, ωY) having the smallest ∣∣∣log ( q PB(ω) )∣∣∣. (c) Local search (LS): Starting with a random assignment ω, we evaluate all neighbors of ω (set of assignments in which exactly one variable in ω is flipped) and choose the neighbor ω′ having the smallest ∣∣∣log ( q PB(ω′ ) )∣∣∣. We randomly restart the search if the local minima is reached or 10000 moves have been made, which ever is earlier. (d) Cutset Local search (CLS): We perform local search over the cutset variables only, namely we evaluate only those assignments in which one of the cutset variables is flipped and choose the neighbor ω′C having the smallest ∣∣∣log ( q PB(ω′C ,ω′Y ) )∣∣∣ where ω′Y is computed using the Karmarkar-Karp heuristic given ω′C . As before, we randomly restart the search if the local minima is reached or 1000 moves have been made which ever is earlier. It is easy to see that each move of cutset local search (cutset random sampling) has higher computationally complexity than local search (random sampling). However, we expect the cutset algorithms to be more accurate because they explore the search space more efficiently.

Benchmark Networks. We compared our algorithms on the following four types of benchmark Bayesian and Markov networks: (1) Noisy OR Bayesian networks (BN20), (2) Ising Models, (3) Relational Markov Networks, and (4) Image Segmentation. These networks were used in the UAI 2014 and 2016 inference competitions (see [Gogate, 2014]).

Methodology. We randomly generated 20 q values for each network as follows. We generated 10 million random samples, sorted them according to their probability (or weight), and chose every 500 thousandth sample. We evaluated the performance using the following error measure. Let ω be the assignment output by the sampling algorithm. Then, for Bayesian networks, we use the quantity Error = ∣∣∣log ( q PB(ω) )∣∣∣ to measure performance. For Markov networks or log-linear models, we use Error = ∣∣∣log ( q exp(∑i fi(ω)θi) )∣∣∣ where fi is a feature, θi ∈ R is its weight and fi(ω) is 1 if fi is true in ω and 0 otherwise. We constructed the 0-cutset as follows. We recursively delete a variable having the highest degree until the graph is empty, breaking ties using average log odds (see Theorem 3).

5.1 Results

We compare the impact of changing q as well as increasing time on the performance of various algorithms. We ran each algorithm for 20 minutes. Figures 1-4 show the results. For each benchmark type, due to lack of space, we report results for a randomly chosen network. For each chosen network, we report three plots showing the impact of varying the time bound for a given q and of varying q for a given time bound. The first two plots show the Error as a function of time for two q values, one near the median and one close to the MAP assignment. The third plot shows Error as a function q after 1200 seconds, the time bound. In general, we found that cutset based algorithms are superior to their conventional counterparts in resource-limited settings.

BN20 networks

BN20 networks [Henrion et al., 1992] are two level Bayesian networks in which parent interactions are modeled using the noisy-or interaction model. These networks are used for medical diagnosis in which the top level (parents) has Boolean variables which model the diseases and the bottom level has variables modeling the symptoms. Exact inference using conventional algorithms such as variable elimination and cutset conditioning is known to be intractable in these networks. Figure 1 shows the results for BN20 networks. We find that CRS and CLS are the best performing algorithms and dominate both LS and RS. For values of q close to the probability of the MAP assignment, LS is slightly better than CRS. However, in such cases, CLS is better than LS by an order of magnitude (notice the log-scale on the Y-axis). Finally, we find that unlike other algorithms, RS tends to have larger error at the extremes than the median values (see Fig. 1(c)).

Ising Models

Fig. 2 shows performance of various algorithms on an Ising model having 400 variables. We see that CLS and CRS are the best performing schemes and dominate LS and RS by several orders of magnitude. LS outperforms random sampling.

Relational Markov Networks (RMNs)

Relational Markov networks are obtained by grounding the friends and smokers Markov logic networks [Domingos and Lowd, 2009]. Fig. 3 shows performance of various algorithms on a relational network for two values of q and time bound 1200 seconds. Results on these networks are similar to those obtained over Ising models in that CRS and CLS as the best performing schemes. However, unlike other networks CRS dominates CLS. This is because RMNs have tied parameters and as a result a large number of assignments have the same probability. Thus, there is a higher chance of hitting the correct answer via random sampling.

Image Segmentation

The goal of image segmentation is to extract objects from an image which allows us to separate the image into several meaningful regions. Graphical models in which variables correspond to regions and edges which model relationships between adjacent regions are often used for performing image segmentation. Results for a benchmark image segmentation network are shown in Fig. 4. We see a similar picture to other benchmark networks: CLS and CRS outperform both LS and RS.

6 Conclusion and Future Work

In this paper, we considered the nearest assignment problem (NAP) which is the problem of finding an assignment ω in a graphical model such that the difference between the probability of ω and a given value q is minimized. We introduced novel techniques that combine 0-cutset conditioning, sampling and local search algorithms with algorithms from the number partitioning literature for solving NAP. Theoretically, we showed that our new techniques have bounded approximation error and are likely to be accurate when the distribution is not skewed and q is not extreme. Via a detailed experimental evaluation, we showed that our new techniques are superior to baseline sampling and local search algorithms.

Future work includes: developing branch and bound algorithms for NAP; investigating incremental versions of Karmarkar-Karp and greedy algorithms and combining them with local search techniques; using algorithms for NAP to solve the rank estimation problem; using NAP to generate human understandable explanations; etc.

Acknowledgements

This work was supported in part by the DARPA Explainable Artificial Intelligence (XAI) Program under contract number N66001-17-2-4032, and by the National Science Foundation grants IIS-1652835 and IIS-1528037.