Novel Upper Bounds for the Constrained Most Probable Explanation Task
Year: 2021

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.

heading: 1 Introduction
text: We develop upper bounding algorithms for the constrained most probable explanation (CMPE) task [32], a 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 a global capacity constraint to the classic optimization problem in PGMs called most probable explanation (MPE). Given a set of log-potentials F , namely a log-linear model, the MPE task seeks to find an assignment of values to all variables (i.e., an explanation) such that the sum over the projection of the assignment on the log-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 G and a real number q. 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-potentials in G is smaller than or equal to q. Our interest in CMPE stems from the fact that several tasks in Explainable AI [16] can be reduced to CMPE. For example, the nearest assignment problem [31] and the decision preserving explanation problem [7, 32] are instances of CMPE; the former seeks to find an assignment whose probability is as close as possible to a given assignment, namely, its nearest neighbor while the latter seeks to find the most probable extension of a given partial assignment according to a generative model such that the same (classification) decision is made according to a discriminative model. Other applications of CMPE include various queries in robust estimation [10] and detecting adversarial attacks.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
In terms of computational complexity, Rouhani et al. [31, 32] showed that CMPE is much harder than MPE. In particular, via a reduction from the multi-choice knapsack problem (MCKP) [19], 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 is 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-based technique for approximating CMPE. The key idea is to condition on variables, namely remove them from the primal graph G until no more than k nodes remain in each connected component. The removed nodes form a 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 an anytime algorithm.
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 a mixed integer linear program (MILP) and solved using MILP solvers such as Gurobi [17] and SCIP [1, 2]. 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 is based on Lagrangian relaxation (cf. [35]) and relaxes the global constraint using a Lagrange multiplier λ ≥ 0 to yield an (unconstrained) MPE task. Given a value for λ, 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-bucket elimination [11], dual decomposition [14] and join graph based cost shifting schemes [18] and further tighten the upper bound by searching for the best possible value for λ, 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 an 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 a 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, our 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.

heading: 2 Notation and Background
text: 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 ⊆X , then xS is the projection of x onto S. We use letters f , g and h to denote log-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 byM is a pair 〈X,F〉 where X is a set of variables and F is a set of log-potentials or features such that each feature fi ∈ F is defined over a subset of variables S(fi) ⊆X . S(fi) is called the scope of fi. A log-potential maps each assignment in its scope to a real number (R). A primal graph ofM is an undirected graph G(V,E) where V and E is the set of vertices and edges respectively such that each vertex Vi ∈ V represents the random variable Xi ∈X and there is an edge between vertices Vi and Vj in G iff the corresponding variables appear together in the scope of some function in F . Given an assignment x, the weight of x w.r.t.M, denoted by ωM(x) equals ∑ f∈F f(xS(f)). For brevity, we will abuse notation and use f(x) instead of f(xS(f)).
Definition 1 (CMPE ). Given two log-linear modelsM1 = 〈X,F〉 andM2 = 〈X,G〉 defined over the same set of variables X and a real value q, the constrained most-probable explanation (CMPE) task is to find an assignment x∗ such that wM1(x ∗) is maximized and wM2(x ∗) ≤ q. Mathematically, the problem of computing the optimal weight is given by
max x ∑ f∈F f(x) s.t. ∑ g∈G g(x) ≤ q (1)
x∗ is the optimal solution to the CMPE problem. Let c∗ = ωM1(x ∗) denote the optimal value or weight. A feasible solution of CMPE is an assignment x s.t. ∑ g∈G g(x) ≤ q.
The combined primal graph of CMPE is the graph obtained by taking the union of the edges of the primal graphs associated withM1 andM2 respectively. Formally, let G1(V,E1) and G2(V,E2) be the primal graphs associated withM1 andM2 respectively. Then the combined primal graph is G(V,E1 ∪ E2). Without loss of generality and for simplicity of exposition we assume that bothM1 andM2 have the same number of functions and for each function f ∈ F there is a corresponding function g ∈ G such that S(f) = S(g) and vice versa. Thus, under this assumption, G1 = G2 = G. Example 1. Fig. 1 shows two log-linear models that define a CMPE problem given q = 40.

heading: 2.1 Prior Work on Upper Bounding the Most Probable Explanation Task
text: Removing the constraint in Eq. (1) encoded byM2 and q yields the most probable explanation (MPE) task. MPE is known to be NP-hard in general but can be solved efficiently in practice when the primal graph has low treewidth or when the partition-based [11] upper bounding schemes yield close to optimal estimates within an AND/OR branch and bound framework [24]. In this paper and specifically in our experiments, we use mini-buckets based upper bounding schemes presented in Ihler et al. [18]. These schemes operate by first converting the primal graph of M to a join graph where each node called a cluster and each edge called a separator is associated and labeled with a subset of variables from M. The join graph can be thought of as a relaxation of inference architectures called tree-decompositions (cf. [20]), on which MPE inference is exact, in that it satisfies all properties that the latter satisfies including the running intersection property except
that it is a graph of clusters instead of a tree of clusters. Then these algorithms perform messagepassing 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 a 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.
Ihler et al. propose three different classes of message-passing schemes on join graphs. The first scheme which yields the classic mini-buckets (MB) algorithm [11] performs message-passing along a given order o of variables processing the clusters one by one. For each variable X along o, the algorithm maxes out X from each unprocessed cluster that it appears in and sends a message to all unprocessed clusters that are connected to the cluster but do not mention X . The second scheme called mini-bucket with max-marginal matching (MM) enhances the MB algorithm by performing LP-tightening updates on all clusters that are processed when maxing-out X . These update equations are inspired by work on a family of LP-based methods including reweighted max-product [34], max-product linear programming (MPLP) [14], dual decomposition [21], and soft arc consistency [4, 33]. At a high level, these tightening approaches shift cost/weight from one cluster to another 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 as 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. 1 having log-potentials f1, f2 and f3. MB is a one-pass algorithm and computes the messages denoted by h while MM also passes the marginal matching messages denoted by c (red).

heading: 2.2 Multi-Choice Knapsack Problem
text: The knapsack problem is a classic problem in combinatorial optimization which is often stated as follows. Given n items where each item i has a cost ci and a profit pi, and a knapsack with capacity q, select a subset of items such that the total profit is maximized and the total cost does not exceed q. For each item i, we can associate a Boolean variable xi which takes value 1 if the item is selected and 0 if it is not and state it as the following optimization problem: maxx ∑n i=1 pixi s.t. ∑n i=1 cixi ≤ q.
The multiple-choice knapsack problem (MCKP) is a 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 Ni items and each item j in bin i has a cost cij and a profit pij , and a 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 q. For each item j in bin i, we can associate a Boolean variable xij that takes value 1 if the item is selected and 0 if the item is not and express the problem mathematically as:
max x m∑ i=1 ∑ j∈Ni pijxij s.t. m∑ i=1 ∑ j∈Ni cijxij ≤ q and ∑ j∈Nj xij = 1, i = 1, . . . ,m (2)
In recent work, Rouhani et al. [32] showed that when the combined primal graph ofM1 andM2 is disconnected into multiple components and the number of variables in 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 is bounded by dk. Fig. 3 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 O(nq) time and O(mq) space where n is the number of items, m is the number of bins and q is the capacity using a dynamic programming algorithm [26, 27, 28]. When the profits and costs are not integers, a LP upper bound can be computed in O(n) time using the Dyer-Zemel algorithm [12, 36].

heading: 3 Upper Bounding Techniques for CMPE
text: 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 a 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 is weakly polynomial. To this end, we seek to 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.

heading: 3.1 MPE based upper bounds by relaxing the global constraint
text: 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 a parameter λ ≥ 0 called the Lagrange multiplier, we consider the following Lagrangian relaxation of CMPE:
max x ∑ f∈F f(x)− λ ∑ g∈G g(x) + λq s.t. λ ≥ 0 (3)
Let u∗λ 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 ∈ G such that S(f) = S(g) we add a function h = f − λg toH. The MPE value of the log-linear model 〈X,H〉 plus λq equals u∗λ. From the theory of Lagrangian relaxations, it is easy to show that u∗λ is an upper bound on c
∗: 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 or equal to the relaxed problem because ∑ g∈G g(x) − q ≤ 0. The optimal, namely the smallest upper bound via Lagrangian relaxation is obtained by searching for a value for λ s.t. u∗λ is minimized. This minimization problem is called the Lagrangian dual problem. Formally, we can show that
Proposition 1. minλ:λ≥0 u∗λ ≥ c∗ where u∗λ and c∗ are optimal values of problems given in Eqs. (3) and (1) respectively.
Let u∗LR = minλ:λ≥0 u ∗ λ denote the optimal upper bound. u ∗ LR can be computed using standard sub-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 consider the following update rule for λ. We start with a heuristic value λ0 and generate a sequence [λ0, . . . , λk, λk+1, . . .] using: λk+1 = λk + αk Ä∑ g∈G g(x ∗,k)− q ä
where αk is the learning rate and x∗,k is the optimal solution to Eq. (3) with λ = λk.
The discussion above yields Algorithm 1 for computing an upper bound on CMPE. After initializing the variables, specifically the Lagrangian multiplier λ and the step-size α to a random positive number and the best answer u∗LR to∞, steps 3 to 10 iteratively solve the Lagrangian dual problem by performing sub-gradient descent over λ. At each iteration, we construct the log-linear modelMλ (step 3), solve the MPE problem overMλ to yield an optimal assignment x∗λ (step 4), use x∗λ to
Algorithm 1: UB-MPE (M1,M2,q) Input: Log-linear modelsM1 = 〈X,F〉 andM2 = 〈X,G〉; and a real value q ∈ R Output: An upper bound on CMPE Begin: 1: Initialize: (1) λ = random number > 0; (2) u∗LR =∞, α = a random number > 0 2: repeat 3: ConstructMλ = 〈X,H〉 whereH = {h = f − λg|f ∈ Fand g ∈ G} 4: Use an MPE algorithm overMλ to compute the MPE solution x∗λ.
{If MPE is not tractable, we can use algorithms such as MB, MM and JG to upper bound it.} 5: uλ = wMλ(x ∗ λ) + λq 6: if uλ < u∗LR then u∗LR = uλ 7: λ = λ+ α Ä∑ g∈G g(x ∗ λ)− q ä 8: Update α using a suitable step-size update procedure (cf. [5]) 9: until convergence
10: return u∗LR End.
compute the upper bound uλ (step 5), update the answer u∗LR if the current bound is better (step 6), perform a sub-gradient step to update λ (step 7) and update the learning rate using a suitable update procedure (cf. [5]). In our experiments, we used diminishing step size which reduces α by periodically dividing it by a positive constant.
To use Algorithm 1 in practice, we need access to 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 a cutset network [29] or an arithmetic circuit [8] and the sub-gradient optimization converges in t iterations, we can show that the bound returned by Algorithm 1 can never be worse than the linear programming relaxation. Formally (proof in the supplement),
Theorem 1. If the MPE overMλ is tractable for all λ ≥ 0 then u∗LR ≤ u∗LP , where u∗LP is the LP-bound of CMPE (Eq. (1)) and u∗LR is the upper bound returned by Algorithm 1.
WhenMλ is not tractable, we propose to use polynomial time approximations whose complexity can be controlled using an integer parameter called the i-bound; specifically MB, MM and JG methods (see section 2.1) to yield an upper bound on uλ at each iteration. This yields an upper bound that may be worse (higher) than u∗LR; however using only polynomial time and space complexity.

heading: 3.2 MCKP based upper bounds using the Lagrange decomposition method
text: The main idea in our proposed scheme is to decompose the structures of both M1 and M2 by duplicating variables such that the CMPE task reduces to MCKP and then solving the latter using specialized algorithms to yield an upper bound. We describe our idea using the following CMPE problem:
max x
f1(x1, x2) + f2(x2, x3) + f3(x1, x3) s.t. g1(x1, x2) + g2(x2, x3) + g3(x1, x3) ≤ q (4)
Here, we assume that all variables are binary and take values from the set {0, 1} and x = (x1, x2, x3). Duplicating each variable two times since each variable appears in two functions and adding equality constraints to account for the duplication, we can express the problem given in Eq. (4) as:
max x,x′
f1(x ′ 1, x2) + f2(x ′ 2, x3) + f3(x1, x ′ 3) s.t. g1(x ′ 1, x2) + g2(x ′ 2, x3) + g3(x1, x ′ 3) ≤ q (5)
and x1 = x′1, x2 = x ′ 2 and x3 = x ′ 3 (6)
Relaxing the constraints using Lagrange multipliers µ = (µ1, µ2, µ3), where µ1, µ2, µ3 ∈ R we get:
max x,x′
f1(x ′ 1, x2) + f2(x ′ 2, x3) + f3(x1, x ′ 3) + µ1(x1 − x′1) + µ2(x2 − x′2) + µ3(x3 − x′3) (7)
s.t. g1(x′1, x2) + g2(x ′ 2, x3) + g3(x1, x ′ 3) ≤ q (8)
Note that by theory of Lagrange relaxations, a solution to the problem described by Eqs. (7) and (8) will yield an upper bound on the problem described by Eqs. (5) and (6). Let f ′1 = f1 − µ1x′1 + µ2x2,
Algorithm 2: UB-KP (M1,M2,q,i) Input: Log-linear modelsM1 = 〈X,F〉 andM2 = 〈X,G〉; a real value q ∈ R; i-bound∈ N Output: An upper bound on CMPE Begin: 1: Merge (via summation) functions in F (and corresponding ones in G) such that the number of variables in
the scope of the new functions is bounded by i to yield a new set of functionsH (and S for G). 2: Given Xj ∈X , let Ij = {a|ha ∈ H, sa ∈ S and Xj ∈ S(ha) = S(sa)} and {Yj,a} where a ∈ Ij
denote the set of duplicated variables of Xj . Let Y = {Yj,a|Xj ∈X and a ∈ Ij} 3: ExpressH and S using duplicated variables Y 4: Initialize: (1) all members of vector µ = {µj,a,b|Xj ∈X, a, b ∈ Ij , and a < b} to a random number; (2) u∗LD =∞, and (3) α = a random number > 0 5: repeat 6: Construct a MCKP fromH, S, µ and q 7: Solve the MCKP to yield an optimal value u∗µ and an assignment of values y∗ to Y .
{If MCKP is intractable, we solve it approximately using a linear time upper bounding schemes [19].} 8: if u∗µ < u∗LD then u∗LD = u∗µ 9: Update each µj,a,b using µj,a,b − α(y∗j,a − y∗j,b)
10: Update α using a suitable step-size update procedure (cf. [5]) 11: until convergence 12: return u∗LD End.
f ′2 = f2 − µ2x′2 + µ3x3 and f ′3 = f3 − µ3x′3 + µ1x1. Then we can express the problem described by Eqs. (7) and (8) as:
max x,x′
f ′1(x ′ 1, x2) + f ′ 2(x ′ 2, x3) + f ′ 3(x1, x ′ 3) s.t. g1(x ′ 1, x2) + g2(x ′ 2, x3) + g3(x1, x ′ 3) ≤ q (9)
The problem described by Eq. (9) 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 to 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 u∗µ denote the optimal value of the problem described by Eq. (9), then solving the Lagrangian dual u∗LD = minµ u ∗ µ via sub-gradient optimization methods yields the best possible upper bound. Example 2. The combined primal graph given in Fig. 3 is obtained by duplicating each variable in the combined primal graph of the log-linear models given in Fig. 1 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 µ1 = −5.01, µ2 = −1.0 and µ3 = 1.0, the functions f ′1, f ′ 2 and f ′ 3 given in Fig. 3(b) are obtained from the functions f1, f2 and f3 respectively given in Fig. 1 using the expressions f ′1 = f1 − µ1x′1 + µ2x2, f ′2 = f2 − µ2x′2 + µ3x3 and f ′3 = f3 − µ3x′3 + µ1x1. The functions g1, g2 and g3 are copied from Fig. 1. Thus, from Eq. (9), theory of Lagrange relaxations and MCKP encoding described in Rouhani et al. [32], solving the MCKP task in Fig. 3(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. 3(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 i (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 functionsH that defines the objective, corresponding functions S that define the constraint and a variable Xj ∈ X , let Ij = {a|ha ∈ H, sa ∈ S and Xj ∈ S(ha) = S(sa)} denote an index over functions that mention Xj . Let {Yj,a} where a ∈ Ij denote the set of duplicated variables of Xj . Let {µj,a,b} denote the set of Lagrange multipliers associated with each variable Xj ∈X where a, b ∈ Ij and a < b. Without loss of generality, we can now state the Lagrangian relaxed problem as:
max y ∑ h∈H h(y) + ∑
j,a,b|a,b∈Ij ,a<b
µj,a,b(yj,a − yj,b) s.t. ∑ s∈S s(y) ≤ q
where Y is the set of duplicated variables. To solve the Lagrangian dual, we can use the sub-gradient method with the following update rule for each µj,a,b. We start with µ0j,a,b and generate a sequence [µ0j,a,b, µ 1 j,a,b, . . .] using: µ k+1 j,a,b = µ k j,a,b − αk(yj,a − yj,b) where αk is the learning rate.
Algorithm 2 formally describes our approach. In step 1, it merges functions inM1 (andM2) creating new functions having potentially higher scope sizes under the constraint that the maximum scope size is bounded by i. This yields two new sets of functionsH 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-gradient 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 a 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 2 is likely to be better than the quality of bounds returned by Algorithm 1. For instance, in the extreme case when the primal graph has no edges, Algorithm 2 will either yield an exact answer or superior knapsack-based upper bounds while Algorithm 1 will yield inferior bounds that are equal to the LP-relaxation of the knapsack problem (see [19]).

heading: 4 Experiments
text: We compared the upper bounding schemes proposed in this paper on three types of CMPE problems having different levels of complexity. The first type uses tractable probabilistic circuits, specifically cutset networks [29, 30] learned on well known benchmarks used by the tractable models community [23]. The second type uses intractable, high treewidth models from the UAI competitions [13, 15]. 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 elimination (MB); (2) Mini-Bucket with max-marginal matching (MM); and (3) join graph based linear programming (JG). We implemented the Dyer-Zemel algorithm [12, 36] to compute upper bounds on MCKP (we will call it KP for brevity). We ran JG for a maximum of 40 iterations or until convergence. We ran the outer-loop of the MPE-based as well as MCKP-based bounding algorithms for a maximum of 100 iterations or until convergence. Details are described in the supplement.
Results on MPE Tractable Models. We learned cutset networks on four high-dimensional datasets AD, BBC, Book and Reuters. We used these networks asM1. To constructM2, we modified the parameters ofM1 using a noise parameter ∼ N(0, σ2 = 0.1). For each network, we experimented with 5 values of q such that the chosen values lie roughly in the 10-th, 20-th, 50-th, 80-th and 90-th percentile respectively. This helps us evaluate the impact of q on the bounds.
Table 1 shows the results for two values of q (20-th and 50-th percentile). Results for other values of q are included in the supplement. Note that on these networks, the mini-buckets algorithm yields exact MPE values in 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.
Results on Networks from the UAI Competition. We also experimented with several high treewidth networks used in the UAI competitions [13, 15]. We varied the i-bound of all algorithms from 2 to 10. We used the technique described above for MPE tractable models to construct the CMPE problems. For brevity, in Table 2 we present results on 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 performing adversarial attacks on 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 to CMPE if the classifier can be expressed as a log-linear model. Formally, let G be a set of features/functions, each defined over a set of random variablesX . Given an assignment x, let D be a decision variable which takes the value d if ∑ g∈G g(x) > 0 and d̄ otherwise. Given an assignment (test example) x, our goal in rendering an adversarial attack is to modify it minimally such that the classifier decision flips, namely find an assignment x′ such that the decision flips from d to d̄ and the distance between x and x′ is minimized. Given an assignment x, we can model the complement of the Hamming distance using the set of n univariate functions F = {f1, . . . , fn} where fi(x′i) = 1 if x′i ∈ x and 0 otherwise. Notice that if the hamming distance between x and x′ is k then ∑n i=1 fi(x ′ i) = n− k. Given an assignment x such that ∑ g∈G g(x) > 0 and set of functions F and G as described above, we can now express the adversarial attack task as the following CMPE problem: maxx′ ∑ f∈F f(x ′) s.t. ∑ g∈G g(x ′) ≤ 0.
We can also use more sophisticated distance functions that take into account the spatial arrangement 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 : fi,j(xi, xj) = 1.0 if Xi is a neighboring pixel of Xj and xi = xj , and 0 otherwise. This will yield a graphical model whose primal graph is a grid.
Table 3: Table showing the average upper bound over 21000 test examples and the 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 linear SVM as the classifier. Under the univariate distance model, the average upper bounds for MB and KP with i-bound set to 1 were 781.05±2.662 and 780.8±2.926 respectively. Avg. UB: average upper bound, Std. UB: standard deviation of upper bound and Avg. Time: average time in seconds.
i-bound=2 i-bound=3 i-bound=4 MB MM JG KP MB 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
Figure 4: Qualitative results on MNIST. Row 1 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 one of the other 9 digits. Row 3 shows the images changed using the grid model.
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 of our approach in its current form is that we can only use multi-linear classifiers (aka graphical models without latent variables) and cannot use non-linear classifiers such as deep neural networks (however, we can use their linear or high treewidth approximations and this is a 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, the MPE bounds are more accurate.
Fig. 4 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.

heading: 5 Conclusion
text: 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-art 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 k pixels to change the prediction of the classifier. In future, we will explore other interesting applications of CMPE involving multiple constraints and over non-linear models.

heading: Acknowledgements
text: 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 IIS1652835 and IIS-1528037.

Review summaries:
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.

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.    As far as I can tell, these contributions are both novel and significant. 

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.