Novel Upper Bounds for the Constrained Most Probable Explanation Task
Authors: Tahrima Rahman
Sara Rouhani
Vibhav Giridhar Gogate
Venue: NeurIPS 2021 Poster (2021)
Keywords: Discrete Optimization
Probabilistic Graphical Models
Constrained Most Probable Explanation
Explainable AI

Abstract:  We propose several schemes for upper bounding the optimal value of the constrained most probable explanation (CMPE) problem. Given a set of discrete random variables, two probabilistic graphical models defined over them and a real number $q$, this problem involves finding an assignment of values to all the variables such that the probability of the assignment is maximized according to the first model and is bounded by $q$ w.r.t. the second model. In prior work, it was shown that CMPE is a unifying problem with several applications and special cases including the nearest assignment problem, the decision preserving most probable explanation task and robust estimation. It was also shown that CMPE is NP-hard even on tractable models such as bounded treewidth networks and is hard for integer linear programming methods because it includes a dense global constraint. The main idea in our approach is to simplify the problem via Lagrange relaxation and decomposition to yield either a knapsack problem or the unconstrained most probable explanation (MPE) problem, and then solving the two problems, respectively using specialized knapsack algorithms and mini-buckets based upper bounding schemes. We evaluate our proposed scheme along several dimensions including quality of the bounds and computation time required on various benchmark graphical models and how it can be used to find heuristic, near-optimal feasible solutions in an example application pertaining to robust estimation and adversarial attacks on classifiers.

Novel Upper Bounds for the Constrained Most Probable Explanation Task
Tahrima Rahman
Sara Rouhani
Vibhav Gogate
The University of Texas at Dallas
[tahrima, rahman, sara. rouhani, vibhav. laahaa..ogateeuudllla...... edu)
Abstract
We propose several schemes for upper bounding the optimal value of the con- strained most probable explanation (CMPE) problem. Given a set of discrete random variables, two probabilistic graphical models defined over them and real number q. this problem involves finding assignment of values to all the variables such that the probability of the assignment is maximized according to the first model and is bounded by g w.r.t. the second model. In prior work, it was shown that CMPE a unifying problem with several applications and special cases including the nearest assignment problem, the decision preserving task and robust estimation. It was also shown that CMPR is NP-hard even on tractable models such bounded treewidth networks and is hard for integer linear programming methods because it includes a dense global constraint. The main idea in our approach position to yield either knapsack problem or the unconstrained most probable explanation (MPE) problem, and then solving the two problems, respectively using specialized knapsack algorithms and mini-buckets based upper bounding schemes. We evaluate our proposed scheme along several dimensions including quality of the bounds and computation time required on various benchmark graphical models and how it can be used to find heuristic, near-optimal feasible solutions in an example application pertaining to robust estimation and adversarial attacks on classifiers.
probable explanation
simplify the problem via Lagrange relaxation and decom-
Introduction
We develop upper bounding algorithms for the constrained most probable explanation (CMPE) task 33]. recently defined unifying (discrete) optimization task over probabilistic graphical models (PGMs) 9 20 25 or log-linear models. At a high level, the CMPE task adds global capacity constraint to the classic optimization problem in PGMs called most probuble explanution (MPE). Given set of log-potentials F, namely a log-linear model, the MPE task seeks to find an assignment of values to all variables (i.c., an explanation) such that the sum over the projection the assignment on the log-potcun pog-potentials is maximized, namely it has the maximum probability. The CMPE task adds a global constraint to MPE using a possibly different set of log-potentials & and a real number g. Specifically, it seeks to find the most probable assignment w.r.t. F under the constraint that the sum over the projection of the assignment on the log pogentttssalss 9 smaller than or equal to q.
Our interest in CMPE stems from the fact that several tasks in Explainable AI [66] can be reduced to CMPE. For example, the nearest assignment problem 31 and the decision preserving explanation problem 7 (2) are instances of CMPE; the former seeks to find an assignment whose probability is as close as possible a given assignment, namely, its nearest neighbor while the latter seeks to find the most probable extension of given partial assignment according to generative model such that the same (classification) decision is made according to discriminative model. Other applications of CMPE include various queries in robust estimation [10] and detecting adversarial attacks.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In terms of computational complexity. Rouhani et al. B1 showed that CMPE is much harder than MPE. In particular, via a reduction from the multi-choice knapsack problem (MCKP) [99] Rouhani et al. showed that while MPE is linear time on graphical models having empty primal graphs, CMPE is NP-hard. However, despite these worst-case results, the good news is that MCKP an instance of easy NP-hard problems [19] and can be well-approximated using advanced methods from the knapsack problems literature. The MCKP reduction also yields a graph-basee technique for variables, namely remove them from the primal graph G until no more than & nodes remain in each connected component. The removed nodes form k-separator [3] and each assignment to them yields an MCKP. When the k-separator is bounded, this method yields a fully polynomial time approximation scheme (FPTAS). When the k-separator is not bounded, Rouhani et al. propose to perform local search yielding anytime algorithm.
approximating CMPE. The key idea is to condition
While the algorithms described above yield a lower bound, no non-trivial upper bounding algorithms are available for CMPE. Such algorithms serve two important purposes (24] : (1) generating heuristic near-optimal solutions; and (2) pruning the search space of branch and bound methods and thus improving their efficiency. In principle, CMPE can be encoded as mixed integer linear program (MILP) and solved using MILP solvers such as Gurobi (17) and SCIP ( However, CMPE and other related tasks such as MPE and MCKP are particularly difficult for MILP solvers because the global constraint in CMPE simultaneously restricts all the variables while MILP solvers are adept at handling sparse constraints. This motivates the development of specialized methods for CMPE.
In this paper, we propose two approaches for efficiently computing qualitative upper bounds for the CMPE task. These approaches relax either the objective or the constraint or both. Our first approach based on Lagrangian relaxation (cf. 355) and relaxes the global constraint using a Lagrange multiplier X 2 0 to yield an (unconstrained) MPE task. Given a value for X, an upper bound on the MPE task yields an upper bound on CMPE. We propose to solve the MPE task using either exact or upper bounding approaches described in literature such as mini-bucke elimination M1I dual decomposition [4] and join graph based cost shifting schemes [8]] and further tighten the upper bound by searching for the best possible value for X, namely a value that minimizes the upper bound on MPE. Our second approach is based on Lagrangian decomposition. The key idea is to decompose the problem by duplicating variables [6] via equality constraints and then relaxing the latter using Lagrange multipliers such that the resulting problem reduces to MCKP. Solving the MCKP for a given assignment of values to the multipliers yields upper bound on CMPE. We propose to further improve the bound by searching for the best possible value assignment to the multipliers via an iterative algorithm.
Empirically, we investigate the quality and computational efficiency of our proposed bounding techniques on variety of CMPE tasks formulated on cutset networks [30] and graphical models used in the UAI competitions 13 15). We also explore a novel application of CMPE: making classifiers (expressed as log-linear models) change their decision by minimally changing the test example. We found that when there is a relatively small limit on the amount of storage space an algorithm can use, approach based on Lagrange decomposition via MCKP yields the best upper bounds. However, it also requires significantly longer to converge. Conversely, when the space limit is relatively large, the approach based on Lagrangian relaxation that utilizes MPE solvers is superior.
2 Notation and Background
We denote binary discrete random variables using upper case letters (e.g., X, Y, etc), their sets using bold uppercase letters (e.g.. X, Y, etc.) and assignment of values to them using bold lowercase letters (e.g., x, y. etc). If S C X, then gg is the projection of z onto S. We use letters f. g and h to denote tog-potentials or features and the calligraphic capital letters such as F. G. etc. to denote sets of log-potentials. A log-linear model or a Markov network, denoted by A is pair (X,F) where X is a set of variables and F is a set of log-potentials or features such that each feature Sú E F is defined over a subset of variables S(J))
X. S(..) is called the scope of ft- A log-potentia maps each assignment in its scope to a real number (RR). A primal graph of M is an undirected graph G(V, E') where and E the set of vertices and edges respectively such that each vertex V; E V represents the random variable X; E X and there is an edge between vertices VÚ and V3 in G iff the corresponding variables appear together in the scope of some function in F. Given an assignment x, the weight of æ w.r.t. M, denoted by (x)(x) equals ΣJEF f(ES())) For brevity, we will abuse notation and use f(x) instead of f (((ss))
2

---

X1
X2
fi
X2
X3
f2
X1
fs
X1
f((X1, X2)
Ja(Ki, Nax) ga((ii,
0
0
15
13
0
0
6
17
0
0
14
11
gi(Xi,
0
3
10
0
7
19
0
19
25
10
18
1
2
24
1
20
30
20
1
12
30
11
X2
X3
MPE 41, 40,
CMPE = 28
J2(X2.Xa)
92
Figure 1: Combined primal graph of two log-linear models having log-potentials {f1, f2. fa} and {g1, 92, (a) respectively. Let q 40, then the optimal solution a² to the CMPE problem is (X1 = 1, X2 = 0, X3 = 1) (highlighted in green and yellow) and the optimal weight is 28. The MPE assignment having weight 41 is (X1 0, X2 0, X3 =) (highlighted in red and yellow).
Definition 1 (CMPE) Given two log-linear models M1 (X,F) and M₂ (X defined over the same set of variables X and a real value the constrained most-probable explanation (CMPE) task is to find an assignment x² such that wM, (x") is maximized and (x²) S q.
Mathematically, the problem of computing the optimal weight is given by
max Σf(x) s.t. JEF
Σ g()) S
(I)
9EG
xx is the optimal solution the CMPE problem. Let c* Wi (xx) denote the optimal value or weight. A feusible solution of CMPE is assignment æ s.t. Egec g(x) S
The combined primal graph of CMPE is the graph obtained by taking the union of the edges of the primal graphs associated with Mj and MM respectively. Formally, let G1 (V, F1) and G2(V, F2)) be the primal graphs associated with Mj and M2 respectively. Then the combined primal graph is G(V, Ej J E2). Without loss of generality and for simplicity of exposition
assume that both Mi
and M2 have the same number of functions and for each function f E F there is a corresponding function g such that S(f) =S(g) and vice versa. Thus, under this assumption, Gi G2 G. Example 1. Fig. shows two log-linear models that define a CMPE problem given q = 40.
2.1 Prior Work on Upper Bounding the Most Probable Explanation Task
Removing the constraint in Eq. (1) encoded by M₂ and q yields the most probable explanation (MPE) task. MPE known to be NP-hard in general but can be solved effi- ciently in practice when the primal graph has low treewidth when the partition-based [II upper bounding schemes yield close to optimal estimates within an AND/OR branch and bound framework (24). In this paper and specifi- cally in our experiments, we use buni-bbckeets based upper bounding schemes presented in Ihler al. (18). These schemes operate by first converting the primal graph of M join graph where each node called a cluster and each edge called a separator is associated and labeled with subset of variables from M. The join graph can be thought of as relaxation of inference architectures called tree-eccopoostions (cf. (20), on which MPE inference is exact, in that it satisfies all properties that the latter sat- isfies including the running intersection property except that it is graph of clusters instead of a tree of clusters. Then these algorithms perform message- passing on the edges of the join graph where the computational complexity of message-passing is exponential in the maximum cluster size. To control the complexity and yield bounded polynomial time approximation, these schemes use an integer parameter i known as the i-bound which bounds the number of variables in each cluster in the join graph by i.
B(x)): (x(1
Xx(X1,
((x))
c(Xi)
B(X2): fa(X2, X3) ) + (X2)
B(Xs):
ha(Xs) + An (XG)
ub
Figure 2: cessage-passing in MB and
MM on the log-linear model given in Fig. having log potentials fi, fz and fa-
3

---

X1
X1
X2
R
91
X2
X3
12
92
P1
C12
P2
Oz
0
15
13
0
17
211
15
13
221
17
1
2
10
0
8
19
212
2
10
3/22
19
1
0
15.01
18
1
0
3
24
15.01
18
2223
3
24
1
16.01
20
1
14
30
214
16.01
20
2024
14
30
X2
X3
X1
X3
f3
93
Ca3
0
0
14
11
14
11
X2
Bir sa)
X3
1
18
25
T33
18
25
adl
14.99
30
333
14.99
30
4.99
3
23
4.99
3
Mi and M2
40
capacity
40
(a)
(b)
(c)
(a) combined primal graph over variables {X1, X2. X3, Xi, X3} and two log-linear models, each having three fog-potentials. The functions fi, ln and f' form the objective while the functions 9t. 92 and fts form the constraint. (b) defines the CMPE task and (c) shows an equivalent MCKP to the CMPE task given in (b). Solution to the MCKP and the corresponding solution to CMPE is highlighted in red. The weight of the optimal solution is 15.01 + 8 + 4.99 = 28.
Figure 3:
Ihler et al. propose three different classes of dessage-passing schemes on join graphs. The first scheme which yields the classic mini-buckets (MB) algorithm [1]] performs message-passing along a given order o of variables processing the clusters one by one. For each variable along o, the algorithm maxes oul X from each unprocessed cluster that it appears in and sends message to all unprocessed clusters that are connected to the cluster but do not mention called mini-bucket with max max-marginal matching (MM) enhances the MB algorithm by performing L--tightening updates on all clusters that are processed when maxing-ou X. These update equations inspired by work on faailly of LP-based methods including reweighted max- -rx-pprouuct [34), max- max-produs product linear programming (MPLP) [14), dual decomposition [21], and soft are consistency At high level, these tightening approaches shift cost/weight from one cluster another
X. The second scheme
4 (3). without changing the original weight and thus try to re-parameterize the model in order to reduce and thus improve the upper bound. The third scheme, which we refer to JG, is a fully iterative approach which performs message-passing or LP-tightening updates until convergence or until a bound on the number of iterations is reached. In practice, it was observed that in terms of the upper bound quality, JG is superior to MM which in turn is superior to MB. However, since MM and MB are single pass approaches while JG is iterative, JG requires significantly more time.
Fig. 2 demonstrates the MB and MM algorithms using the log-linear model given in Fig. Thaving log-potentials fi, f2 and fa. MB is one-pass algorithm and computes the messages denoted by while MM also passes the marginal matching messages denoted by c (red).
2.2 Multi-Choice Knapsack Problem
The knapsack problem is a classic problem in combinatorial optimization which is often stated as follows. Given n items where each item has cost C; and profit pt, and a knapsack with capacity q, select subset of items such that the total profit is maximized and the total cost does not exceed g. For each item i, we can associate Boolean variable x; which takes value the item is selected and O if it is not and state it as the following optimization problem: max D -== Piz;; s.t. Σ CaT; g.
The maltiple-choice knapsack problem (MCKP) is generalization of the knapsack problem in which items are partitioned into groups/bins and the constraint is that exactly one item must be chosen from each group. Specifically, given m bins where each bin i has N, items and each item j in bin has a cost cty and a profit Pij. and knapsack with capacity q. the MCKP task is to select one item from each bin such that the total profit is maximized and the total cost does not exceed g. For each item in bin i, we can associate a Boolean variable 2ij that takes value if the item is selected and 0 if the item is not and express the problem mathematically as:
Σ
Σ JEN,
Cjfaij & and Σ Fij 1, i= 1.... m JEN,
max
Pijoij
JEN.

---

In recent work, Rouhani et al. B2 showed that when the combined primal graph of M₁ and M2 is disconnected into multiple components and the number of variables each component is bounded by k then the CMPE task can be encoded as MCKP where the number of items in each bin is exponential in k. Thus, if the maximum domain size of the variables is d, then the number of items in each bin bounded by d². Fig. demonstrates the MCKP encoding for an example CMPE task.
If the profits and costs of the items are integers, the MCKP problem can be solved in ((ng) time and ((mq) space where n is the number of items, m is the number of bins and q is the capacity using When the profits and costs are not integers, a LP upper bound can be computed in (n) time using the Dyer-Zemel algorithm [2 36).
a dynamic programming algorithm [26 27 28
3 Upper Bounding Techniques for CMPE
A straight forward upper bound (LP-Bound) for CMPE can be derived by converting it to an integer linear program, relaxing the integrality constraint to yield linear program and solving the latter using standard methods and solvers such as the simplex, ellipsoid and interior-point methods. However, the computational complexity of these algorithms weakly polynomial. To this end, we seek develop algorithms that are non-trivial and have strong polynomial time guarantees.
We derive two classes of upper bounding algorithms for CMPE. The first class relaxes the global constraint yielding an MPE task while the second duplicates variables by adding equality constraints yielding an MCKP problem. We describe the two approaches in the next two subsections.
3.1 MPE based upper bounds by relaxing the global constraint
The Lagrangian relaxation of a constrained optimization problem is obtained by incorporating all or some of the constraints into the objective function using appropriate coefficients called the Lagrange multipliers. This relaxation provides a simple and efficient approach to compute upper bounds on the maximization problem known as the primal problem. Given parameter multiplier, we consider the following Lagrangian relaxation of CMPE:
called the Lagrange
E(()) - A >Σ g(x)) S. A20
nIXX OF
FEF
gEG
Let ut denote the optimal value of the problem given in Eq. 3 Computing u² can be easily reduced to the MPE task. We construct a set of functions H. as follows. We begin with an empty H. Then, for each f F and its corresponding function g 9 such that S(f) S(g) add function == Àg to H. The MPE value of the log-lineat model (X, H.) plus Ag equals ut.
From the theory of Lagrangian relaxations, it is easy to show that u² is an upper bound on e": all feasible solutions of CMPE are also feasible solutions of the Lagrangian relaxed problem and the objective value of the feasible solutions of CMPE is smaller than equal to the relaxed problem because Enec g(x)
S O. The optimal, namely the smallest upper bound via Lagrangian relaxation is obtained by searching for value for À s.t. u² is minimized. This minimization problem is called the Lagrangian dual problem. Formally, we can show that
Proposition 1. minxA20 2 2 c¹ where u² and c² are optimal values of problems given in Eqs. and ① respectively.
Let uin = minx:220 "², denote the optimal upper bound. wi,n can be computed using standard cub-gradient optimization methods. In particular, u as a function of À has several nice properties such as concavity but is non-differentiable in presence of multiple optima. To this end, we con- sider the following update rule for X. We start with a heuristic value X and generate a sequence [A?.....X x², k- ....] using: k+1 = x + +ax (Egec ((x**A)- - where ag is the learning rate and *h
. is the optimal solution to Eq. \
The discussion above yields Algorithm I for computing an upper bound on CMPE. After initializing the variables, specifically the Lagrangian multiplier > and the step-size a to a random positive number and the best answer vi,n to co, steps 3 to 10 iteratively solve the Lagrangian dual problem by performing sub- gradient descent over X. At each iteration, we construct the log-linear model Mx (step 3), solve the MPE problem over Mx to yield an optimal assignment σ; (step 4), use x; to
5

---

Algorithm 1: UB-MPE (Mi..M..)
Input:
Log-linear models MM F) and Mr (X, 9); and real value q E
Output: An upper bound on CMPE
Begin:
1:
Initialize: (1) X = random number > (2) ui 00. random number >> 0
2: repeat
Construct MA (X, H) where = f >g E Fand g 9}
4: Use an MPE algorithm over MA to compute the MPE solution zz}- (If MPE is not tractable, we can use algorithms such as MB, MM and JG to upper bound it.)
5:
WM, (ax) Aq
6: u, < u7. then WZ. =
7: À = x Ee ( -
8:
Update a using suitable step-size update procedure (cf. 5
9:
until convergence
10:
return ULR
End.
compute the upper bound иλ (step 5), update the answer uin if the current bound is better (step 6), perform a sub-gradient step to update À (step 7) and update the learning rate using suitable update procedure (ef. (5).. In our experiments, we used diminishing step size which reduces by periodically dividing it by positive constant.
To use Algorithm I in practice, need access an MPE solver. In particular, if MPE is tractable, for example the treewidth of the combined primal graph is small or the model admits a tractable probabilistic circuit such as cutset network (29 an arithmetic circuit [8] and the sub- sub-grade gradient optimization converges in iterations, we can show that the bound returned by Algorithm Caan never be worse than the linear programming relaxation. Formally (proof in the supplement).
Theorem 1. If the MPE over Mx is tractable for all X 2 O then "In S "'.p. where uir is the L.-bound of CMPE (Eq. (T)) and uin is the upper bound returned by Algorithm
When MM is not tractable, we propose to use polynomial time approximations whose complexity can be controlled using integer parameter called the i-bound; specifically MB, MM and JG methods (see section 2.T to yield an upper bound on 4y at each iteration. This yields an upper bound that may be worse (higher) than u7.Ri however using only polynomial time and space complexity.
3.2 MCKP based upper bounds using the Lagrange decomposition method
The main idea in our proposed scheme is to decompose the structures of both Mi and MM by duplicating variables such that the CMPE task reduces to MCKP and then solving the latter using specialized algorithms to yield upper bound. We describe our idea using the following CMPE problem:
max fi I2) + f2(22, + fa(z1, 23) s.t. gi (II, + g2 (22, va) + +g(aa,, 13) S
(4)
Here, we assume that all variables are binary and take values from the set (0. 1) and a = (x1, 22 0z).
Duplicating each variable two times since each variable appears in two functions and adding equality constraints account for the duplication, we can express the problem given in Eq. 4 as:
max (2), + fz(zz, m3) + fa(21, x'/)) s.t. gi (2 x2) + 92(2'2, x3) + gz(21. x41) S
(5)
and T =' x2 = Zzz and 23 a's
(6)
Relaxing the constraints using Lagrange multipliers μ = (μ //, u3). where 14 u2; 11 we get:
max f1 (2),)22) + fa(2', xs) + (5) + (r - =1) + (2(2 m + // (1 x4g ffl2)+ff(aasa.oa
s.t. 91 (4), x2) g2 (2 23) + ga (z1, x/y 5
(8)
Note that by theory of Lagrange relaxations, a solution to the problem described by Eqs. and will yield upper bound on the problem described by Eqs. (5) and ( Let fl fi 1 p242.

---

Algorithm 2: UB-KP (Mi, M2.q.i)
Input:
Log-linear models MM F) and Mr = (X, 9); real value q E R; i-bounde N An upper bound on CMPE
Output:
Begin:
1:
Merge (via summation) functions in F (and corresponding ones in () such that the number of variables in
the scope of the new functions is bounded by to yield new of functions H. (and 8 for 9).
2: Given X, E X, let 1, {a/ha H, 8a E ES and X, E S(ha) S(sa)) and (Y,a) where I
denote the set of duplicated variables of X,. Let Y = {Y X, E X and a E T,}
3: Express H and S using duplicated variables Y
4: Initialize: (1) all members of vector μ = (M Xy E X, a, b 1, and a < bj to random number; (2)
wi.n oc, and (3) a random number > 0
repeat
6: Construct a MCKP from H. S, μ and g
7: Solve the MCKP to yield an optimal value "n and an assignment of values y to Y. solve it approximately using linear time upper bounding schemes 19]
(If MCKK is intractable,
8:
if ui "iD then ui Ui
9:
Update each Hj,a.b using Mj.a.6 a(yj v5
10:
Update using a suitable step-size update procedure (cf. 5
11:
until convergence
12:
return ui.D
End.
f3g f2 ugz2y + M323 and f'g fa -M3a's + M1 Then we can express the problem described
by Eqs. (7) and (8) as:
max fi (111, x2) + (2 v3) + (2 x'/)) s.t. (1 22) + 92(22,, .s) + gs(211, x2)) S q 0,
The problem described by Eq. is an instance of MCKP having 3 bins and 4 items in each bin since the combined primal graph associated with the CMPE problem has three connected components corresponding the three functions (see Fig. 3). Thus, it can be solved using MCKP methods to yield an upper bound on our example CMPE problem. Let 4 denote the optimal value of the problem described by Eq. (9). then solving the Lagrangian dual wiD min, "A via sub-gradient optimization methods yields the best possible upper bound.
The combined primal graph given in Fig. ils obtained by duplicating each variable in the combined primal graph of the log-linear models given in Fig. [ and relaxing the equality constraint (via Lagrangian decomposition) between the duplicated variables such that the number of nodes in each connected component is bounded by 2. Given μn = -5.01, μ22 = -1.0 and
Example 2.
#s = 1.0. the functions f'. and f's given in Fig. 3) are obtained the functions fI, fz and fa. respectively given in Fig. [ Jusing the expressions = f1 111 + 22 f/2 = f2 H22222 + 1323 and f/3 fs u3zzy/ + 11 The functions g1. 92 and g3 are copied from Fig. [ Thus, from Eq. (Ρ). theory of Lagrange relaxations and MCKP encoding described in Rouhani et al. [32]. solving the MCKP task Fig. (c) will yield an upper bound on the optimal value of the CMPE problem. The value of the optimal solution to MCKP given in Fig. ((c is 28. Thus, for this toy example, the MCKP based upper bound is equal to the optimal value of the CMPE problem.
We generalize the method prescribed in the aforementioned example to yield a polynomial time upper bounding scheme. In particular, in order to control both the computational time and space complexity of our proposed algorithm, we use an integer parameter (similar to the i-bound used for join graphs). This parameter exponentially bounds the number of items in each bin of MCKP and under the assumption that the log-potentials have integer values that are bounded above by an integer B, the MCKP generated by our relaxation can be solved in time that scales linearly in exp(i), B and the number of functions using a dynamic programming algorithm. Before we present our algorithm, we introduce some required notation. Given a set of functions H. that defines the objective, corresponding functions S that define the constraint and a variable X, E X, let I, {a E H, Sa E S and X, E S(ha)) = S(sa)) denote an index over functions that mention X,. Let (Yj.a} where a E I, denote the set of duplicated variables of Xj. Let {Hj,a.b} denote the set of Lagrange multipliers associated with each variable X, X where a, b E I, and b. Without loss of generality, we can now state the Lagrangian relaxed problem as:
max
h(y) +
Σ
(i U5.b) s.t.
Σ s( <q 8ES
NEA
J.a.ba,,bEI,as I
7

---

Table 1: Table showing results on cutset networks for 4 datasets AD, BBC, Book and Reuters. The line under each network reports the number of random variables and their maximum domain size. Alg: Algorithm, q20 and q50: q values are chosen from the 20-th and 50-th percentile respectively, and Tm: time in seconds.
AD
BBC
Book
Reuters
(1556,2)
(1058,2)
(500,2)
(889,2)
Alg
420
'mm q50
Tm
420
Tm q50
Tm
920
Tm
q50
Tm
420
Tm q50
Tm
MB
-3308.3
0
-3228.4
0
-953,9
1
-906.7
-670.4
0
-629.9
0
-1572.3
0
-1443.5
0
KP
-3307.8
59
-3225.8
70
-953.4
42
-906.1
49
-669.9
15
-629.7
20
-1564.8
63
-1431.6
149
where Y is the set of duplicated variables. To solve the Lagrangian dual, we can use the sub- uub-graddent method with the following update rule for each Mj.a,b- We start with 1 22,,, and generate a sequence US, Pja....... ... using: u = 12a. au(V3, - M).b)) where or is the learning rate.
Algorithm finhhm@ffrmmat formally describes our approach. In step 1, it merges functions in MM (and M2) creating new functions having potentially higher scope sizes under the constraint that the maximum scope size bounded by i. This yields two new sets of functions H. and S which represent the objective and the constraint respectively. Then the algorithm duplicates the variables so that the resulting problem can be converted to MCKP (step 2-3). In steps 4-12 the algorithm solves the Lagrangian dual problem via sub- -obadridient descent over the Lagrange multipliers μ.. A key sub-step in optimizing the dual is solving the MCKP (step 7). For this, the algorithm either uses an exact MCKP algorithm if feasible or linear time upper bounding scheme [12 [36].
In general, when the combined primal graph has large number of disconnected components, the quality of bounds returned by Algorithm is likely to be better than the quality of bounds returned by Algorithm For instance, in the extreme case when the primal graph has no edges, Algorithm 2 will either yield an exact answer or superior srapsack-baseer upper bounds while Algorithm will yield inferior bounds that are equal the LP-relaxation of the knapsack problem (see 19
4 Experiments
We compared the upper bounding schemes proposed in this paper three types of CMPE problems having different levels of complexity. The first type uses tractable probabilistic circuits, specifically cutset networks 29 30 learned well known benchmarks used by the tractable models community
[23] The second type uses intractable, high treewidth models from the UAI competitions [13 [5]. The third type uses models developed for performing adversarial attacks on classifiers in order to measure their robustness. We also evaluated the impact of increasing the i-bound on the quality of upper bound and the time required to compute the upper bound.
We evaluated three algorithms within our MPE-based bounding approach: (1) Mini-Bucket climi- with max- marginal matching (MM); and (3) join graph based linear programming (JG). We implemented the Dyer-Zeme algorithm [12 36) to compute upper bounds on MCKP (we will call it KP for brevity). We ran JG for maximum of 40 iterations or until convergence. We ran the outer-loop of the MPEEbased as well as MCKP- bounding algorithms for maximum of 100 iterations until convergence. Details are described in the supplement.
nation (MB); (2)
Results on MPE Tractable Models. We learned cutset networks on four high-dimensional datasets AD, BBC, Book and Reuters. We used these networks as M1. To construct M2, we modified the parameters of Mi using a noise parameter ~ (O0, o² = 0.1). For each network, experimented with 5 values of g such that the chosen values lie roughly in the 10-th, 20-th, 50-th, 80-th and 90-th percentile respectively. This helps evaluate the impact of q on the bounds.
Table I shows the results for two values g (20-th and 50-th percentile). Results for other values of g are included in the supplement. Note that on these networks, the mini-buckets algorithm yields exact MPE values the inner loop of our algorithm and as a result max-marginal as well as join-graph based propagation will not improve the bounds (we have therefore not reported them). As expected, we see that when MPE is tractable, MPE based bounds are superior in terms of time as well as quality than MCKP based bounds.
8

---

Table Table showing results on four networks from the UAI competitions: Segmentation. Grids, Promedas and Pedigree. The line under each network reports the number of random variables, the maximum domain size of the variables, the number of functions and the treewidth. Alg: Algorithm, iB; i- i-bunn, q20 and q50: are chosen from the 20th and 50th percentile respectively, and Tm: time in seconds.
values
Segmentation (232,2,863.
Grids
Promedas
Pedigree
18)
(1600,2,4800)
113)
(1953,2,
1953,148))
(1152,5,1152.35
Aig
iB
920
Tm
q50
Tm
q20
Tm
950
Tm
920
Tm
950
Tm
920
Tm
950
Tm
MB
2
-381.7
0
-366.0
0
1370.4
1
1587.4
0
-1491.7
1
-1431.5
-123.4
0
-111.2
0
MM
2
-427.3
0
-116.9
0
1040.8
1
1235.8
-1964.8
1
-1881.8
-235.6
-222.0
JG
-459.9
5
447.8
821.9
35
1017.8
12466.1
45
-2362.5
-31.22
-307.4
KP
2
-459.9
37
446.8
36
821.4
430
1020.4
406
-2765.3
139
-2677.6
138
-323.6
214
-310.9
204
MB
5
-425.0
-09..8
0
1078.4
2
1289.6
2
-2661.6
1
2578.1
0
-268.9
-260.2
MM
5
-452.2
440.0
857.3
2
1045.9
-2748.8
-666.77
-315.3
-302.6
JG
5 -461.5
5
8
449.1
819.9
51
1016.0
-2764.6
37
2676.2
-330.8
-318.2
KP
-459.8
37
446.8
31
819.9
214
1016.3
164
-2770.8
116
2681.2
150
-324.8
139
-312.6
134
MB
8
-48..0
434.4
0
995.8
3
1178.7
-2692.0
2
2599..
-92.33
-285.9
MM
8
-46022
448.5
830.3
6
1024.8
6
-2762.7
3
-2670.1
-327.6
-313.9
JG
8
-461.1
22
449.2
820.3
190
1016.0
160
-2760.8
98
-2670.7
126
-327.8
91
-317.1
KP
8
-459.8
29
148.1
37
819.6
202
1016.0
167
-27714
134
-2681.7
130
-325.8
171
-313.6
170
MB
10 -452.7
2
-38.77
2
951.7
8
1143.4
8
-2688.4
4
-2601.5
-300.9
-284.9
4
MM
10
-460.7
2
-48.55
3
824.1
12
1021.2
13 -2763.1
8
-2673.2
-330.1
-316.4
JG
10
-461.4
65
-48.9
823.9
396
1018.9
501
-2756.4
322
26669.9
381
-33.22
288
-316.4
319
KP
10
-600.0
33
448.4
36
819.5
215
1016.0
170
-2770.8
115
2680.3
101
211 324.9
-313.8
193
Results on Networks from the UAI Competition. We also experimented with several high treewidth networks used in the UAI competitions [13 [5]. We varied the i-bound of all algo- rithms from to 10. We used the technique described above for MPE tractable models to construct the CMPE problems. For brevity, in Table we present results the largest network from four domains: image segmentation, Grids, medical diagnosis (Promedas) and pedigrees for genetic linkage analysis for two values of q which are roughly equal to the 20-th and 50-th percentile respectively.
We see that KP and JG yield smaller (better) upper bounds than MB and MM. However, their time complexity is much higher. For smaller i-bounds (= 2, 5), there is an order of magnitude difference between the upper bounds output by JG and KP, and the other two approaches. However, the difference is much smaller for larger i-bounds (= 8, 10). The MM algorithm yields the best trade-off between time complexity and upper bound quality, especially when using higher i-bounds is feasible. However, if using higher i-bounds in not feasible, the KP algorithm should be used.
Results on Adversarial Modification on the MNIST dataset. We consider the problem of per- forming adversarial attacks discriminative classifiers in order to measure their robustness. The goal is to manipulate the predictions made by the classifier by minimally changing the test example. We show that this problem can be reduced CMPE if the classifier can be expressed model. Formally, let G be a set of features/funccions, each defined over a set of random variables X. Given assignment æ. let D be a decision variable which takes the value if Σ g(x)) > 0 and
log-linear
otherwise. Given an assignment (test example) æ, our goal rendering an adversarial attack is to modify it minimally such that the classifier decision flips, namely find an assignment w' such that the decision flips from d to d and the distance between æ and x' is minimized. Given an assignment x. we can model the complement of the Hamming distance using the of univariate functions F= (i, Sn) where [4(2)) = 1f of E æ and 0 otherwise. Notice that if the hamming distance between x and x' is then E = n k. Given an assignment such that Egeg (xx) now express the adversarial attack task as the following CMPE problem: maxæ' ΣfEF f(x') s.t. Enes g(x') < O.
and set of functions F and as described above,
We can also use more sophisticated distance functions that take into account the spatial urrungement of pixels. For example, if we want pixels that are spatially close to take the same value, we can add the following set of pairwise functions to F: fez (x,, = 1.0 if X; a neighboring pixel of X; and x; Zj. and 0 otherwise. This will yield graphical model whose primal graph is grid.

---

Table Table showing average upper bound over 21000 test examples and time required by the four algorithms MB, MM, JG and KP with i-bounds varying between 2 and 4 on the MNIST dataset using the Grid model for measuring distance and lincar SVM as the classifier. Under the univariate distance model, the average upper bounds for MB and KP with i-bound set were 781.05 781.0552.66 662 and 780.8+2.926 respectively. Avg.
UB: average upper bound, Std. UB: standard deviation of upper bound and Avg.
Time: average time seconds.
i-bound=2
i-bound=3
i-bound=4
MB
MM
JG
KP
MBB
MM
JG
KP
MB
MM
JG
KP
Avg. UB 291.42
290.91
290.11
290.85
291.0
290.38
290.11
290.69
290.79
290.38
290.11
290.66
Std. UB
2.12
2.14
2.44
2.32
2.15
2.35
2.42
2.33
2.2
2.36
2.42
2.38
Avg. Time
0.0
0.0
2.8
0.6
0.0
0.0
3.0
0.4
0.0
0.0
3.3
0.3
3
3
3
Qualitative results on MNIST. Row shows the original test images. Row 2 shows the images changed using the univariate model so that the decision changes from the original classification to any of the other 9 digits. Row 3 shows the images changed using the grid model.
Figure 4:
We conducted experiments on the MNIST dataset (22 using the univariate and grid distance functions described above and linear support vector machine as the classifier. The dataset has 70,000 examples. We used 70% of the examples for training and 30% for testing. The accuracy of our classifier on the dataset was 97%. Note that a limitation our approach in its current form is that we can only multi-lineaa classifiers (aka graphical models without latent variables) and cannot non-linear classifiers such as deep neural networks (however, we can use their linear or high treewidth approximations and this is subject of future research).
Table 3 shows quantitative results comparing the quality of the upper bounds and time required for the univariate and grid distance functions. We see that on the univariate model, the KP based bounds yield exact answers (since the univariate problem is an instance of the knapsack problem) while the MPE based bounds are only slightly worse than the KP based bounds. On the grid models however, MPE bounds are more accurate.
Fig. shows qualitative results. The qualitative results verify our intuition that the grid model yields smoother deceptions than the univariate model. More qualitative results on the MNIST dataset are included in the supplement.
5 Conclusion
We proposed novel upper bounding methods for solving the CMPE task. The schemes are based on relaxing the original constrained maximization problem into either an MPE or MCKP problem which can then be solved using state-of the-hartt techniques. Our empirical findings on a large variety of models including both tractable and intractable models suggest that our proposed relaxations can produce effective upper bounds. We also presented the application of CMPE in solving an important task in robust estimation: measuring the robustness of discriminative classifiers. On the MNIST dataset we showed that CMPE equipped with our proposed upper bounding methods can efficiently find the most important pixels to change the prediction of the classifier. In future, we will explore other interesting applications of CMPE involving multiple constraints and over non-lincar models.
10

---

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.
References
[1] Tobias Achterberg. SCIP: solving constraint integer programs. Mathematical Programming Computation, 1(1):144,, July 2009.
[2] Tobias Achterberg, Timo Berthold, Thorsten Koch, and Kati Wolter. Constraint integer pro- gramming: A new approach to integrate cp and mip. In International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Program- ming, pages 6-20. Springer, 2008.
[3] Walid Ben-Ameur, Mohamed-Ahmed Mohamed-Sidi, and José Neto. The k-separator problem. In International Computing and Combinatorics Conference, pages 337-348. Springer, 2013.
[4] Stefano Bistarelli, Rosella Gennari, and Francesca Rossi. Constraint propagation for soft con- straints: Generalization and termination conditions. In International Conference on Principles and Practice of Constraint Programming, pages 83-97. Springer, 2000.
[5] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, March 2004.
[6] Arthur Choi and Adnan Darwiche. Relax, Compensate and Then Recover. Takashi Onada, Daisuke Bekki, and Eric McCready, editors, New Frontiers in Artificial Intelligence, pages 167-180. Springer Berlin Heidelberg, 2011.
[7] Arthur Choi, Yexiang Xue, and Adnan Darwiche. Same-decision probability: A confidence measure for threshold-based decisions. International Journal of Approximate Reasoning,
53(9):1415-1428, 2012.
[8] Adnan Darwiche. A Differential Approach to Inference in Bayesian Networks. Journal of the
ACM, 50:280-305, 2003.
[9] Adnan Darwiche. Modeling and Reasoning with Bayesian Networks. Cambridge University Press, 2009.
[10] Adnan Darwiche and Auguste Hirth. On the reasons behind decisions. In Twenty Fourth European Conference on Artificial Intelligence, volume 325 of Frontiers in Artificial Intelligence and Applications, pages 712-720. IOS Press, 2020.
[11] Rina Dechter and Irina Rish. Mini-buckets: A general scheme for bounded inference. Journal of the ACM (JACM), 50(2):007-153, 2003.
[12] Martin E Dyer. An o (n) algorithm for the multiple-choice knapsack linear program. Mathemat- ical programming. 29(1):57-63, 1984.
[13] Gal Elidan and Amir Globerson. The 2010 UAI approximate inference challenge. Available online at: http: www. www.hhhii.... ac pttpro/ect/tua.....eeeeeeep/ watpaaiii//i/.../e/ phpp) 2010.
[14] Amir Globerson and Tommi Jaakkola. Fixing max-product: Convergent message passing algorithms for map Ip-relaxations. Advances in neural information processing systems, 20:553- 560. 2007.
[15] Vibhav Gogate. Results of the 2014 UAI competition.
httpp://ww.hlt..ut wetiitiooninnnieee html 2014.
[16] David Gunning and David Aha. DARPA's Explainable Artificial Intelligence (XAI) Program.
Al Magazine, 40(2):44-58, June 2019.
[17] LLC Gurobi Optimization. Gurobi Optimizer Reference Manual. 2021.
[18] Alexander T Ihler, Natalia Flerova, Rina Dechter, and Lars Otten. Join-graph based cost-shifting schemes. arXiv preprint arXiv: 10l::1210.8877 18.88 2012.
[19] Hans Kellerer, Ulrich Pferschy, and David Pisinger. Knapsack problems. Springer, 2004.
[20] Daphne Koller and Nir Friedman. Probabilistic Graphical Models; Principles and Techniques.
MIT Press, 2009.

---

[21]
Nikos Komodakis, Nikos Paragios, and Georgios Tziritas. Mrf optimization via dual decompo- sition: Message-passing revisited. In 2007 IEEE 1 11th International Conference on Computer Vision, pages 1-8. IEFE, 2007.
[22]
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010.
[23] Daniel Lowd and Jesse Davis. Learning Markov network structure with decision trees. In Proceedings of the 10th International Conference Data Mining, pages 334-343, 2010.
[24] Radu Marinescu and Rina Dechter. Best-First ANDIOR Search for Most Probable Explanations. CoRR,
2012.
[25] Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, 1988.
[26] David Pisinger. Linear time algorithms for knapsack problems with bounded weights. Journal of Algorithmss, 33(1):1-14, 1999.
[27] David Pisinger. Dynamic programming on the word ram. Algorithmica, 35(2):128-144 2003.
[28] David Pisinger. Where are the hard knapsack problems? Computers & Operations Research, 32(9):2271 -2284, 2005.
[29] Tahrima Rahman, Shasha Jin, and Vibhav Gogate. Cutset Bayesian Networks: A New Represen- tation for Learning Rao-Blackwer Blackwellised Graphical Models. In Proceedings of the Twenty-Eight Eiigh International Joint Conference Artificial Intelligence, pages 5751-5757, 2019.
[30] Tahrima Rahman, Prasanna Kothalkar, and Vibhav Gogate. Cutset Networks: A Simple, Tractable, and Scalable Approach for Improving the Accuracy of Chow-Liu Trees. In Machine Learning and Knowledge Discovery in Databuses European Conference, ECML PKDD. Proceedings, Purt II, pages (33-645,72 2014.
[31] Sara Rouhani. Tahrima Rahman, and Vibhav Gogate. Algorithms for the Nearest Assignment Problem. In Proceedings of the Twenty-Sevents International Joint Conference on Artificial Intelligence, pages 5096-5102, 2018.
[32] Sara Rouhani, Tahrima Rahman, and Vibhav Gogate. A novel approach for constrained optimization in graphical models. In Advances in Neural Information Processing Systems, volume 33, pages 11949-11960, 2020.
[33] Thomas Schiex. Arc consistency for soft constraints. In International Conference on Principles and Practice of Constraint Programming, pages 41 1-425. Springer, 2000.
[34] Martin Wainwright, Tommi S Jaakkola, and Alan S Willsky. Map estimation via agreement on trees: message-passieee and linear programming. IEEE transactions on information theory, 51(11):3697-3711 2005.
[35] Laurence A. Wolsey. Integer programming. Wiley-Interscience series in discrete mathematics and optimization. J. Wiley, New York, 1998.
[36] Eitan Zemel. An Onn) algorithm for the linear multiple choice knapsack problem and related problems. Information Processing Letters, 18(3):123-128, 1984.
12


Reviews:
[{"review_id": "vRUUI87WB3-", "reviewer": "Reviewer_NaDK", "summary": "This paper proposes tractable strategies for upper bounding the value of constrained MPE problems. Two strategies are developed based on Lagrangian relaxation. One is to completely eliminate the constraint, converting the problem to a straight MPE problem. The second one involves the strategic application of dual decomposition to convert the problem instance to one of a multiple choice knapsack problem. The approaches are evaluated on datasets from the UAI inference challenge as well as adversarial input modification tasks.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is a very well written paper that addresses an reasonably important tasks through non-trivial means. The ideas are clearly communicated and easy to follow. Regarding novelty --- I found the MCKP bound to be rather clever and this thankfully translates to interesting computational results as well. \n\nI have a few points of criticism. \nFirst, the final paragraph on page 4 (lines 170 - 174) imply somehow that LP-based bounds are unworthy of consideration because of the weak polynomial complexity of linear programming. I find this point extremely contrived given that the first bound simply assumes that the unconstrained MPE problem will be tractable or otherwise the recourse are approximation algorithms with running time proportional to 2^i  If one is comfortable accepting MPE tractability, accepting LP tractability should be a much easier pill to swallow. This is actually not a minor point, since the domination of the LP bound by the first Lagrangian bound holds only if the MPE is solved exactly. Otherwise, no straightforward claims can be made. The LP bound should not only not be discarded so lightly but is probably the most natural baseline for the evaluations of this paper. \n\nSecond, one thing that is actually confusing on first read is the way that the way that the algorithms under evaluation are introduced on page 7, section 4. At first I thought that MG/MM/JG are existing bounding approaches, since they were discussed in the prior art section  (which might leave a confusing impression as the reader might have forgotten exactly what the situation is at that point), then I wondered where are the evaluations of the first bound, so it took some back and forth until things clicked. I think it's worth calling this out explicitly in a single sentence that MG/MM/JG are evaluations of the bound in eq. 3.\n\nFinally, I think it's worth considering to move all the tabular data to the appendix and instead having plots to illustrate the specific points that are made in section 4. I think going through all these tables multiple times makes for a rather tedious reading experience, yet there are rather interesting observations here that shouldn't be missed, so having a more condensed representation might make sense. \n\nOverall, I would say this is a solid paper. It can be further strengthened by the addition of an LP baseline. The other issues are cosmetic.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No concerns.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "999"}, "extra_text": {}}, {"review_id": "qSNsOQYS_E0", "reviewer": "Reviewer_9jTV", "summary": "The authors present two novel approaches for upper bounding the constrained most probable explanation (CMPE) task in graphical models.  The CMPE is a variation of the MPE or MAP estimation problem in discrete graphical models, where one must find the most likely configuration of the graphical model subject to a constraint on the chosen configuration.  The authors make use of lagrangian relaxation to introduce two new methods.  One works by relaxing the CMPE to an MPE, which can be solved exactly or approximately, using the solution to compute the upper bound, tightening the bound via subgradient descent and repeating.  The other works in a similar fashion by relaxing the CMPE to a multi choice knapsack problem.  \n\nAs far as I can tell, these contributions are both novel and significant. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I thought this was a very well written paper.  The problem was tightly described, the contributions (and limitations) were clearly presented, the technical results were clear and concise and the results conveyed the efficacy and limitations of the proposed approaches. And to the best of my knowledge, these appear to be the first generally tractable methods to upper bound the CMPE problem.\n\nA few comments/questions:\n-Is the assumption that the log linear models F (MPE) and G (constraint) have the same primal graph limiting? And does it obscure the real trade-off between the two methods?  If the graphs weren't the same, would you choose the MCKP approximation when the model G has higher treewidth and the MPE-based approximation when F has higher treewidth?   \n-It was not obvious to me that \\sum_{g \\in G} g(x) <= q in the MPE based approximation when the MPE model is not tractable and must be approximated. Can you provide some additional color on this claim.\n-Did you run into any convergence issues in the case where the MPE approximation was not tractable?  \n-What is the relationship between i and k on lines 162 and 163, or is that a typo?\n-Line 227 I don't think you mean \"duplicating each variable two times\". \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This doesn't seem relevant.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "e3TkU9g8b9", "reviewer": "Reviewer_av4V", "summary": "This paper presents two novel schemes for upper bounding the CMPE problem. The first relaxes the global constraint via Lagrangian relaxation and the second reduces the CMPE to an MCKP problem. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and contributions are solid. I personally like the paper but I have several minor concerns:\n\n(1) How tight are the two new bounds? It is unclear to me how much these two new bounds are better than the naive upper bound obtained by removing the constraint in Eq (`1). \n\n(2) The paper claims the usages of the new upper bounds are  (1) generating heuristic\nnear-optimal solutions; and (2) pruning the search space of branch and bound methods and thus improving their efficiency. However, there are no experiments provided about these two usage cases in the paper. Therefore, I am not sure how much these two new bounds can help in practices. \n\n(3) The time and space complexities of the second scheme seem rather high, it looks to me that it will significantly hinder the use of such scheme in the usage of pruning search space in a complete search engine like branch and bound.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See my comments in \"Main review\"", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "WHCR35Nogae", "reviewer": "Reviewer_MHAL", "summary": "The paper considers the constrained most probable explanation task in probabilistic graphical models and develops new upper bounding schemes for it. Unlike MPE, the CMPE task is NP-hard even for tree-shaped graphical models and therefore finding good upper bounds for it is definitely called for. Specifically, the idea is to use the Lagrangian relaxation to generate either a standard MPE problem or a knapsack problem. Experimental results of several CMPE benchmark domains demonstrate the effectiveness of the proposed upper bounding schemes.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written and organised. The quality of the presentation is overall very good. The two proposed upper bounding schemes are presented very clearly and examples provided help to get a better understanding. In the experimental section it may be worthwhile to include some plots of the computed upper bounds (as functions of the mini-bucket I-bounds for example).\n\nLagrangian relaxation is a well known technique that is widely used in operations research to deal efficiently with complicated constraints. Therefore, applying it to the CMPE task is quite natural. Although the extension is fairly straightforward it appears to be the first time it is done in this context. The experimental results demonstrate that the technique is quite effective in practice.\n\nOne thing the is perhaps missing is a discussion on the usefulness of these upper bounds. Although it is mentioned in the introduction that in principle they can be used to guide a heuristic search algorithm, it would be interesting to see how one would do it in practice (ie, precompile the heuristics in some way, generate them dynamically at each node in the search space, etc.).\n\nMinor comment:\n- In section 3.2 you also use a parameter \"i\" to bound the number of items in a partition. It's not exactly equivalent to the mini-bucket I-bound, so may be use a different letter for the parameter.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations of the proposed method are well addressed and there's no potential societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical concerns", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present two approaches for bounding "constrained" most probable explanation (CMPE) tasks in graphical models, in which we seek an MPE solution to one model, constrained to a subset of configurations by another model.  Both methods are simple (in a good way), relaxing the CMPE to an unconstrained MPE problem, or to a multi-choice knapsack problem, then using Lagrangian optimization to tighten the resulting bounds.  Reviewers were unanimously positive, highlighting the novelty of the work as a strength.  Several reviewers did bring up points that should be addressed in a final version, however, including comparison to LP-based techniques, and some issues with the presentation (see individual reviews for details).
Decision: Accept (Poster)