Credal Marginal MAP
Authors: Radu Marinescu
Debarun Bhattacharjya
Junkyu Lee
Fabio Cozman
Alexander G. Gray
Venue: NeurIPS 2023 poster (2023)
Keywords: graphical models
credal networks
probabilistic inference
TL;DR: The paper presents new exact and approximate algorithms for Marginal MAP inference in credal networks.

Abstract: Credal networks extend Bayesian networks to allow for imprecision in probability values. Marginal MAP is a widely applicable mixed inference task that identifies the most likely assignment for a subset of variables (called MAP variables). However, the  task is extremely difficult to solve in credal networks particularly because the evaluation of each complete MAP assignment involves exact likelihood computations (combinatorial sums) over the vertices of a complex joint credal set representing the space of all possible marginal distributions of the MAP variables. In this paper, we explore Credal Marginal MAP inference and develop new exact methods based on variable elimination and depth-first search as well as several approximation schemes based on the mini-bucket partitioning and stochastic local search. An extensive empirical evaluation demonstrates the effectiveness of our new methods on random as well as real-world benchmark problems.

Credal Marginal MAP
Radu Marinescu IBM Research, Ireland radu. www.mmarinsccuuiee i.m. com
Debarun Bhattacharjya
IBM Research, USA debarunb@us, iimm com
Junkyu Lee
Alexander Gray
IBM Research, USA Junkyu. lee@ ibm. com
IBM Research, USA
alexander araa gray@iamaym..aa com
Fabio Cozman
Universidade de São Paulo, Brazil fgcozman@usp.br
Abstract
Credal networks extend Bayesian networks to allow for imprecision in probability values. Marginal MAP is widely applicable mixed inference task that identi- fies the most likely assignment for a subset of variables (called MAP variables). However, the task is extremely difficult solve credal networks particularly because the evaluation of each complete MAP assignment involves exact likelihood computations (combinatorial sums) over the vertices of complex joint credal set representing the space of all possible marginal distributions of the MAP variables. this paper, we explore Credal Marginal MAP inference and develop new exact methods based on variable elimination and depth-first search as well as several approximation schemes based on the buni-bucket partitioning and stochastic local search. An extensive empirical evaluation demonstrates the effectiveness of our new methods on random as well as real-world benchmark problems.
Introduction
Probabilistic graphical models such as Bayesian networks [1] provide a powerful framework for reasoning about conditional (in) denddeneyyyy structures over many variables. Marginal MAP (MMAP) is the task that identifies the most likely instantiation for a subset of variables given some evidence in a Bayesian network. Since MMAP inference distinguishes between maximization variables (called MAP variables) and summation variables, it is computationally more difficult than either max- sum- inference tasks alone, primarily because summation and maximization operations do not commute; this forces processing along constrained variable orderings that may have significantly higher induced widths 2 3 4. MMAP is NP -complete, but despite its complcxity, it is often the appropriate task for problems that involve hidden variables such conformant planning [5], image segmentation with hidden fields (6, or probabilistic diagnosis in healthcare 77
In many practical situations it may not always be possible to provide the precise specification of Bayesian network's parameters (i.e., probability values). Credal networks (8] provide an elegant extension to Bayesian networks that retain the graphical appeal of the latter while allowing for more flexible quantification of the probability values via credal sets. This ability to represent and reason with imprecision in probability values allows credal networks to often reach more conservative and robust conclusions than Bayesian networks. Over the past three decades, the bulk of research has
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

focused on developing marginal inference algorithms that are concerned with computing efficiently the marginal probability of query variable given some evidence in the credal network (
Abductive reasoning tasks such as explaining the evidence in a credal network with or without hidden (unobserved) variables (i.e., Marginal MAP inference) are equally important to consider in practice. For example, in a hypothetical medical diagnosis situation modeled as a credal network, one may be interested in identifying the most likely combination of underlying medical conditions that determine a negative CT scan result and the presence of severe memory loss [T0 M.. Furthermore, since probabilistic structural causal models can be mapped exactly into equivalent credal networks, credal Marginal MAP inference could also be used to enable effective counterfactual analysis [12
Contributions In this paper. we address the Marginal MAP inference task in credal networks. Specifically, we define the Credal Marginal MAP (CMMAP) task as finding an assignment to subset of variables that has maximum upper (respectively, lower) marginal probability. We focus first on exact inference and propose variable elimination as well as a depth-first search scheme for CMMAP. The complexity analysis of these exact methods indicates that they are likely to be limited to very easy problems. Therefore, we subsequently propose a mini-bucket partitioning based approximation of variable elimination for CMMAP as well as a family of approximate search based schemes that combine stochastic local search a algorithms such as hill climbing, taboo search and simulated annealing with approximate maginal inference for credal networks. We evaluate empirically the new CMMAP inference algorithms random credal networks with different graph topologies as well as a collection credal networks derived from weal-world applications. Our experimental results show that the exact approaches are limited to solving relatively small scale problems, while the approximation schemes can scale to much larger and practical problems.
The supplementary material includes additional details, experimental results, code and benchmarks.
2 Background
2.1 Bayesian Networks
A Bayesian network (BN) D is defined by tuple (X, D. P. G). where (X is set of variables over multi-valued domains D = .i..... Dn G is a directed acyclic graph (DAG) over X as nodes where each X; has set of parents II, and P is set of conditional probubility tables (CPT's where each P:- = P(X,III)). A Bayesian network represents a joint probability distribution over X, namely P(X) IT== PIX,
be subset of X called MAP variables and Xs X XM be the complement of XMM called sum variables. The Marginal MAP (MMAP) task seeks an assignment xM to variables XM having maximum probability. This requires access to the marginal distribution over XM, which is obtained by summing out variables Xs:
Let XM- (Xi....,
XMM = argmax
EIIP(X,m X 1=1
XM
MMAP is mixed inference task (max-sum) and its complexity is known to be NPPP -complete
3 Over the past decades, several algorithmic schemes have been developed for solving MMAP efficiently. We later overview the most relevant exact and approximate algorithms for MMAP.
2.2 Credal Networks
A set of probability distributions for variable X is called a credal set and is denoted by K(X) L3 Similarly. a conditional credal set is a set of conditional distributions, obtained by applying Bayes rule to each distribution in a credal set of joint distributions [4]. We consider credal sets that are closed and convex with finite number of vertices. Two credal sets ( = y1) and K K(XYY y2). where y1 and y/2 are two distinct values of variable Y, are called separately specified if there is no constraint the first set that is based on the properties of the second set.
credal network (CN) 8 is defined by a tuple (X, D, K, G), where X X= (X,,..... discrete variables with finite domains D {Di, D.). , G is a directed acyclic graph (DAG) over
X,, is a set of
2

---

A
A
1
0.7
JoUs 0.8
PIATA
C
PICIAL
B
KICIA)
0
10.1003
(0.7.0.))
0.6
0.5
1
0.7)
(0.4, 0.6)
MD|RCC
KID
0.4
0.5)
PIEDD)
0.8
KEEDD
[07,0.3]
10.6, 0.81
1
102, 0.4]
0.2
0.7
10.1 0.31
[0., 0.8)
(a) Bayesian network
(b) Credal network
Figure 1: Examples of Bayesian and credal networks with bi-valued variables.
X as nodes, and (X, II, {3s}} each variable X; and each configuration of its parents IT; in G. The strong extension K (X) ) of credal network is the convex hull (denoted CH) of all joint distributions that satisfy the following Markov property: every variable is strongly independent of its non-descendants conditional on its parents (8] (see also [8 for more details on strong conditional independence).
separately specified conditional credal sets for
n
((X) (P() P(X)= II P(X, i=1
TTak) is vertex of KII mTkk))
(2)
Example 1. Figure la shows a simple Bayesian network with 5 bi-valued variables {A, B, C, D, E}. The conditional probability tables shown next to the nodes. For example, we have that P(B 1|A 0) = 0.2 and P(B =
= = 0.6, respectively. In Figurel Tb we show a credal network variables. In this case, the conditional credal sets associated with the variables are given by closed probability intervals such as, for example, 0.1 S P(B = 0) 0.3 and 0.5 P(B 1|A 1) s 0.7, respectively.
1|A =
defined over the same
Unlike in Bayesian networks, a MAP assignment in a credal network may correspond to more than one marginal distribution. Therefore, define the following two Credal Marginal MAP (CMMAP)
tasks:
G) be a credal network whose variables are partitioned into MAP variables XM and sum variables Xs X XM. The maximin Credal Marginal MAP task is finding the assignment X²1 to XM with the maximum lower marginal probability, namely:
Definition (maximin). Lei C=
ΣII P(X,LL) XM P(X) X 1=1
X = argmnax min
(3)
Definition 2 (maximax). Cet K, G) be credal network whose variables partitioned into MAP variables XM and sum variables X X X The maximax Credal Marginal MAP task finding the assignment X²y to XM with the maximum upper marginal probability, namely:
ΣI P(..1.)
X5s argmax X
max P(X) X.s 1=1
Solving CMMAP can be shown to be NpNPT -hard 15 11. Despite being much harder than MMAP, CMMAP is applicable for explaining evidence imprecise probabilistic models [2] [6].
3
Related Work
exact solution to the Bayesian MMAP task given by Equation 1 can be obtained by using the variable elimination (VE) algorithm, form of dynamic programming which climinates the variables

---

Algorithm Variable Elimination for Credal Marginal MAP
1: procedure CVB(C, XM. Xs))
12:
1 = max (Ex IIf E Tx,3)
2: initialize +
13:
else
3: for all variable X; X do
14:
max (maxx, I[f
4: & = {p= : - E (x
15:
let Y vars(E) be the closest X;
5: update I ru
16:
update I' Ty U {τ}
6: create constrained elimination ordering o
17:
initialize xi,
7: for all variable X; E do
18:
for all variable X; E reversed(o) do
8: Fx. f Φ E ET, X; E (arr(())
19:
if X; E M then
9: update I = ['
20:
x = argmaxx, x, [x) E Fx,]
for all variable X; do
21:
XM x U [X; xf}
11: if X; E Xs then
22: return XjM
along constrained elimination order such that all sum variables are eliminated before the MAP variables [2]. The optimal configuration X is obtained by backward pass that proceeds from the last to the first MAP variable in the constrained elimination ordering and processes each MAP variable by an argmax operator conditioned on the previously instantiated MAP variables.
Alternatively, a depth-first branch and bound search can also be conducted to solve the MMAP exactly, guided by an unconstrained join-tree based upper bound which can be re-evaluated fully [17] or incrementally [18) at each step during search. More recently, a collection of exact schemes sensitive the problem structure have emerged including depth-fire first branch and bound search, best-first search, memory efficient recursive best- first search as well as anytime weighted best- best-first search algorithms
that traverse an AND/OR search space associated with the MMAP task 44 20 21]. These
algorithms are guided by an effective weighted mini-bucked partitioning based heuristic function and are currently the state-of-the-ard for exact MMAP inference.
Several approximation schemes for Bayesian MMAP inference, including mini-bucket partitioning, message-passing and variational methods, have been introduced the years (2 23
24
25
26).
These methods, however, do not guarantee eventual optimality of their solutions without significantly increasing their memory requirements.
Stochastic local search algorithms have also been developed to approximate MMAP efficiently B while the algorithm introduced by [27] that propagates sets of messages between the clusters of join-tree and the hybrid schemes combining depth-first and best-first AND/OR search [20] provide lower and upper bounds the optimal MMAP value in anytime manner.
4 Exact Credal Marginal MAP
In this section, we describe two exact algorithms for solving the Credal Marginal MAP tasks defined by Equations (2) and (3). respectively. Due to space limitation, we discuss only the maximax case (the maximin analogous). Specifically, we present variable elimination scheme that eliminates the variables either by summation or by maximization, well as depth-first search scheme that finds the optimal MAP assignment by traversing the search space defined by the MAP variables.
4.1 Variable Elimination
Algorithm I describes variable elimination procedure for CMMAP which extends the exact method developed previously for marginal inference tasks 9 and operates on potentials.
Definition 3 (potential). Given set of variables Y. a potential Φ(Y) ) is a set of non-negative real-valued functions p( (Y) on Y. The product of two potentials di (Y) and (Z)) defined by
((Y). (2) {p- g E d.y v). The sum-murginal Ez (Y) and the max-marginal maxz o0 (Y) of potential (YY with respect to a subset of variables Z S Y are defined by Ez (Y) (ZzP(Y) e Φ) and maxz d(Y) {maxz p( (YY )): E ø), respectively.

---

Since the multiplication operator may grow the size of potentials dramatically, we introduce an additional pruning operation that can reduces the cardinality a potential. Specifically, the operator max (Y) returns the set of non-zero maximal elements of (YY), under the partial order 2 defined component- wise as p 2 q iff Vyy E D(y)())) 2 g(yc), where Dy is the cartesian product of the domains of the variables in Y: max ({Y) = {p (Y)) By E o, 2 p)-
K, G) input together with a partitioning of its variables into disjoint subsets XM (as MAP variables) and X5 (as sum variables), algorithm CVE transforms each conditional credal set K [I,) into a corresponding potential that contains the set of all conditional probability distributions in the strong extension of (I, (lines 3-5). Subsequently, given an ordering of the variables in which all the MAP variables come after the sum variables. the potentials are partitioned into buckets. A bucket is associated with single variable X; and contains every unallocated potential & that has X; in scope var)(() (lines 6-9). The algorithm then processes each bucket, from first to last in the constrained elimination ordering o, by multiplying all potentials in the current bucket and eliminating the bucket's s variable (by summation for sum variables, and by maximization for MAP variables), resulting in a new potential which is first pruned by its non-maximal elements and then placed in a subsequent bucket, depending on its scope (lines 10-16). Following the top-down elimination phase, a bottom-up pass over the MAP buckets, from the last to the first MAP variable in the ordering, assembles the solution xi, by selecting the value zy of variable X, that maximizes the combination of potentials in its bucket, conditioned on the already assigned MAP variables in the ordering (lines 18-21). Note that the bucket X, 's combined potential may contain more than one components. In this case, we choose the value x; that maximizes the largest number of components in that potential (breaking ties arbitrarily). Clearly, we have the following complexity result:
Given a credal network C
Theorem (complexity). Given a credal network C, the complexity of algorithm CVE is time and space O(n C' k")), where is the number of variables, k bounds the domain sizes, w is the induced width of the constrained elimination order and C bounds the cardinality of the potentials.
4.2 Depth-First Search
An alternative approach to solving CMMAP exactly is to conduct a depth-first search over the space of partial assignments to the MAP variables, and, for each complete MAP assignment XM compute its score as the exact upper probability P(xM) This way, the optimal solution Xi, corresponds to the configuration with the highest score. Evaluating P(xM) can be done by using simple modification of the CVE algorithm described in the previous section. Specifically, given a complete assignment X to the MAP variables, the modified CVE, denoted by CVE+, computes unconstrained elimination ordering of all the variables regardless of whether they are MAP or summation variables. Then, for each MAP variable X, and corresponding value 2; E XM, CVE+ adds to the bucket of X; deterministic potential <(X)) = {6,.) where 8z, returns one if X; = I; and zero otherwise. Finally, CVE+ eliminates all variables by summation and obtains the desired upper probability bound after processing the bucket of the last variable in the ordering.
Theorem 2 (complexity). Given a credal network C, the complexity of the depth-first search algorithm time Onn-C M..-C-.mmmt km+ and space On Kin-C-k"h C-kw.), where n is the number of variables, m the number of MAP variables, k is the maximum domain size, w is the induced width of the unconstrained elimination ordering u and bounds the cardinality of the potentials.
Approximate Credal Marginal MAP
Solving the CMMAP task exactly is computationally hard and does not scale to large problems. There- fore, in this section, we present several approximation schemes using the bucket partitioning as well as stochastic local search combined with approximate credal marginal inference.
5.1 Mini-Buckets Approximation
The first approximation scheme is described by Algorithm 2 and adapts the mini-bucket partitioning scheme developed for graphical models (28) to the CMMAP task. Specifically, algorithm CMBE() parameterized by an i-bound and works by partitioning large buckets into smaller subsets, called mini-bucked each containing at most i distinct variables (line 5). The mini-buckets are processed
5

---

Algorithm 2 Mini-Buckets for Credal Marginal MAP
1: procedure CMBE(C. X x i-bound)
8:
+ max Ex. Ill e 92}
2: create constrained climination ordering o
9:
else
3: initialize buckets I' x, in Algorithm
10:
v max maxx, ll Q₂}
4: for all variable X; o (Q1,.... Q1) Tx; 6: for all mini- bucket Qj. E (I.....I] do
11:
let E var)( be the closest to X;
5: create mini-bucked
12:
update Ty = Ty {1)}
13:
generate xi, as in Algorithm
7: if X2 E Xs then
14:
return X
separately, follows: MAP mini-bucked (in XM)) are eliminated by maximization, while variables in Xs are climinated by summation. In practice, however, for variables in Xs. one (arbitrarily selected) is eliminated by summation, while the rest of the mini-buckets Clearly, CMBE(i) outputs an upper bound on the optimal maximax CMMAP value from Equation
processed by maximization.
Theorem (complexity). Given a credal network C, the complexity of algorithm CMBE(1) is time and space Onn C k'), where n is the number of variables, & is the maximum domain size, i is the mini-bucket i-bound and C bounds the cardinality of the potentials.
5.2 Local Search
The second approximation scheme is described by Algorithm 3 and combines stochastic local search with approximate marginal inference for credal networks (2] More specifically, the basic idea behind the method is to start from an initial guess XM as a solution, and iteratively try to improve it by moving better neighbor Xay that has a higher score. A neighbor x'y of instantiation XM is defined as an instantiation X'y, which results from changing the value of a single variable X in XM- For example, the neighbors of X (B 0, C. 1. D 0) for the credal network from Figure Ib are (B = 1,C D 0), (B = 0, C 0, D = 0) and (B 0, = D. = 1), respectively. In this case, computing the score score score(x'x)) of neighbor x requires estimating the upper probability of the evidence P(x'M) represented by the assignment x'y-- This can be done efficiently using any of the approximation schemes developed for marginal inference in credal networks such as L2U (29), GL2U [30] or ApproxLP [31] However, since these schemes were originally designed to compute the lower and upper marginal probabilities of query variable Z z conditioned on evidence Y = y, we use a simple transformation of the credal network to evaluate the probability of evidence P(Y y) (see the supplementary material for more details). We present next three strategies for conducting the local search for CMMAP.
Stochastic Hill Climbing. Firstly, procedure SHC in Algorithm describes our Stochastic Hill Climbing based approach for CMMAP. Specifically, SHC proceeds by repeatedly either changing the state of the variable that creates the maximum score change (line 13), or changing variable at random (lines and 15). The quality of the solution returned by the method depends to a large extent on which part of the search space it is given explore. Therefore, our scheme restarts the search from a different initial solution which is initialized uniformly at random (lines 3-4).
Taboo Search. Secondly, procedure TS in Algorithm implements the Taboo Search approach for CMMAP. Taboo search is similar to stochastic hill climbing except that the next neighbor of the current solution is chosen the best neighbor that hasn't 't been visited recently. A taboo list maintains a portion of the previously visited solutions so that at the next step a unique point is selected. Our TS algorithm implements random restarts strategy.
Simulated Annealing. Finally, procedure SA in Algorithm 3 describes our Simulated Anncaling based scheme for CMMAP. The basic principle behind this approach is to consider some neighboring state XMM of the current state XM. and probabilistically decides between moving to state Xyr or staying in the current state. The probability of making the transition from xM to x'y, is specified by an acceptance probability function P(x),; XMs T) that depends on the scores of the two states
well as global time-varying parameter T called temperature. We chose P(x's xM,T) T) è

---

Algorithm 3 Local Search for Credal Marginal MAP
1: procedure SHC(C. X S X. Pftip)
35:
b +- score(XMM)
2: initialize x1y +- best f- -00
36:
xxx @ then
3: for all iterations i .... N do
37:
select random neighbor X'M E E.
4: initialize XM randomly
38:
else
5: for all flips j = 1... M do
39:
X'M < XMM
6: sample randomly E (0, 1)
40:
score(x(11 (xx11) (/)) > best then
7: N be XM 's neighbors
41:
X²M t XM
8:
if (p S pstpp) then
42:
best t- score(X(M)
9: select random neighbor xss E
10: else
43:
+ -X's 44: if size 2 S then
11: for all neighbor Xyy E do
12:
compute score(x(s)
45:
prune T until size(T) < S
13:
select highest score neighbor xMM E A
46:
return x
14:
score(x S score(xM) then select random neighbor XMM E N else
47: procedure SA(C, XM S. Tinits σ)
15:
48: initialize xi, randomly
16:
49: best t- score(x]]) M
select X/1 x"M
50: for all iterations
1 1...N do
18:
if score(x'x) > best then
51: set XM + x T + T Timi
19:
XM XM
52:
for all flips j =
M do
20:
best + score(x's)
53:
let V be Xas neighbors
54:
select random neighbor x's e N A < log score(x'M) log score(XM)
21:
XM + X'M
55:
22:
return X
56:
A 0 then
23: procedure TS(C, XM XX initialize XM 0, best x- -00
57:
XM + XxM
58: else
25: for all iterations i 1... do
59:
sample randomly (0,
26: initialize XM randomly
60:
if e then
27:
T - 0
61:
XM f- X'M
28:
for all flips j= M do
62:
if score(xM)) > best then
29:
T +- TU {x
63:
X + XM
30:
let / be XM 's neighbors initialize x"r + 0, b -o0
64:
best t SCOTE(XM))
31:
32:
for all neighbor X'M E N do
65:
+ T
33:
if x's & T and score(x()) b then
66:
return XMM
34:
x < XxM
where A = log P(x'x log p( At each iteration, the temperature is decreased using cooling schedule a < 1. Like SHC and TS, algorithm SA implements random restarts strategy.
Theorem 4 (complexity). Given a credal network C, the complexity of algorithms SHC, TS and SA is time O(N M PP) and space O(n), where n is the number of variables, N is the number of iterations, M the maximum number of flips allowed per iteration, and P bounds the complexity of approximating the probability of evidence in C.
6 Experiments
We evaluate the proposed algorithms for CMMAP on random credal networks and credal networks derived from real-world applications. All competing algorithms were implemented in C++ and the experiments were run on a 32-core machine with 128GB of RAM running Ubuntu Linux 20.04.
We consider the two exact algorithms denoted by CVE and DFS, as well as the four approximation schemes denoted by SHC, TS, S SA and CMBB((), respectively. The local search algorithms used N 10 iterations and M 10, 000 maximum flips per iteration, and they all used the approximate I.2 algorithm with 10 iterations (29 to evaluate the MAP assignments during search. Furthermore, for SHC we set the flip probability prui to 0.2, TS used taboo list of size 100, while for SA set
7

---

w0
SHC
TS
SA
CMBE(2)
time (#)
W
time (#)
W
time
W
time (#)
W
random
20
25
32.69
100
23.08
100
6.47
100
225.28 (70)
100
163.05
100
79.11
100
14.78
327.67 (43)
60
23
421.93
100
185.41
100
29.99
100
224.93 (7)
30
39
254.32
100
141.03
100
24.08
100
294.48 (43)
150
60
57
1143.78
100
531.45
100
70.06
100
555.98 (14)
2811.47
100
1259.79
100
139.78
75
925.41 (2)
50
58
I044.79
100
490,38
100
72.09
100
276.98 (38)
200
100
86
3496.77
(32)
32
2143.79
100
211.47
14
927.31 (1)
0
150
69
3601.67
(16)
16
3550.99 (17)
17
339.34
72
(0)
grid
20
25
31.35
100
22.77
100
4,66
100
0.07
100
155.34
100
79.83
100
10.51
3.85
60
23
358.81
100
168.79
100
19.18
100
28.76
30
36
219.49
100
121.86
100
21.02
100
0.34
144
60
53
878.63
100
426.70
100
54.77
100
1.03
2109.47
100
958.13
100
102.93
73
27.79
50
55
817.52
100
382.46
100
58.13
100
0.68
196
100
56
3045.54 (94)
94
14S3.39
100
147.11
13
51.01
(98)
150
22
3601.25
(23)
23
301 1.47 (93)
93
190.26
41.27 (99)
k-tree
20
25
68.25
100
44.25
100
10.48
100
221.18 (55)
100
307.91
100
151.97
100
23.19
163.59 (8)
60
23
650,72
100
306.26
100
40.19
100
(0)
30
28
443.33
100
245.71
100
44.58
100
492.55 (26)
150
60
47
1647.29
100
724.01
100
106.71
100
14.68 (1)
2917.01 (84)
1541.91
100
192.76
82
(0)
50
45
1306.43
100
660.59
100
108.36
100
1199.83
200
100
64
3376.59 (54)
54
1917.95
100
266.24
21
(0)
1500
48
3602.98 (4)
3334.49 (59)
59
344.96
38
(0)
Table 1:
Results on random, grid and k-tree credal networks. Mean CPU times in seconds,
number of instance solved (#) and number of wins (W). Time limit 1 hour, 8GB of RAM.
the initial temperature and cooling schedule to Timst 100 and o 0.9, respectively. For CMBE() we set the i-bound i to 2 and used the same L2U algorithm to evaluate the solution found. All competing algorithms were allocated 1 hour time limit and 8GB of memory per problem instance.
In all our experiments, we report the CPU time in seconds, the number of problems solved within the time/memory limit and the number of times an algorithm converged to the best possible solution. The latter is called the number of wins and is meant be measure solution quality for the respective algorithm. We also record the number of variables (n), the number (or percentage) of MAP variables (Q) and the constrained induced widths (w*). The best performance points are highlighted.
6.1 Random Credal Networks
For our purpose, we generated random credal networks, m-by-m grid networks as well k-tree net- works. Specifically, for the random networks, we varied the number of variables n E {100, 150, 200}. for grids, choose m {10, 14, 16), and for k-trees selected & = 2 and the number of variables n E {100, 150, 200}, respectively. In all cases, the maximum domain size was set to and the conditional credal sets were generated uniformly random probability intervals such that the difference between the lower and upper probability bounds was at most 0.3.
First, we note that the exact algorithms CVEE and DFS could only solve very small problems with up to variables and MAP variables. The main reason for poor performance of these algorithms is the extremely large size of the intermediate potentials generated during the variable elimination procedure which causes the algorithms to run out of memory or time on larger problems. Therefore, omit their evaluation hereafter.

---

problem
SHC
TS
SA
CMBF(2)
time (#)
W
time (#)
W
time (#)
W
time
alarm
12
27.32 (10)
21.31 (10)
10
4.89 (10)
10
324.23 (10)
child
3.51 (10)
3.69 (10)
10
1.19 (10)
0.64 (10)
link
239
3655.67 (2)
2
3628.15
1300.14 (10)
8
(0)
insurance
12
64.22 (10)
10
45.77 (10)
10
17.11 (10)
10
97.16 (9)
hepar2
25
1734.11 (10)
10
833.82 (10)
10
163.16 (10)
10
pathfinder
33
2509.89 (10)
79.78 (10)
10
93.98 (10)
10
hailfinder
126.60 (10)
72.73 (10)
10
12.53 (10)
531.52 (10)
largefam
402
(0)
0
(0)
2903.55 (10)
10
-(0)
mastermind!
389
(0)
0
(0)
0
3600.85 (10)
10
-00)
mastermind2
726
0
(0)
3617.17 (5)
5
(0)
mastermind3
1193
(0)
0
(0)
3650.54 (3)
-00)
mildew
12
22.49 (10)
15.22 (10)
10
3.15 (10)
10
0.16
(10)
munin
175
3615.45 (5)
4
3639.57 (3)
652.72 (10)
5
-0)
pedigree
74
3603.87 87700 (7)
7
3609.44 (8)
410.61 (10)
0
1269.45 (8)
pedigree7
147
3620.74
1
3625.51 (2)
1689.89 (10)
9
pedigree9
(0)
0
(0)
1719.92 (10)
1128.50 (4)
win95pts
28
3612.38 (6)
6
3610.94 (6)
821.20 (10)
10
(0)
xandes
75
3619.00 (6)
6
3611.76 (6)
6
3565.62 (10)
3
(0)
xdiabetes
75
3605.08 (9)
9
3603.76 (10)
10
175.76 (10)
0
182.38 (6)
zbarley
140.93 (10)
82.36 (10)
10
18.47 (10)
863.64 (1)
zpigs
105
3606.83 (4)
4
3603.8 (5)
234.84 (10)
5
100.47 (2)
zwater
16
207.07 (10)
10
126.87 (10)
10
44.68 (10)
10
(0)
Table Results on real-world credal networks with Q
50%
MAP variables. Mean CPU time in
seconds, number of instances solved (#) and number of wins (W). Time limit hour, 8 GB of RAM.
Table summarizes the results obtained on random, grid and k-tree networks. Each data point represents average over 100 random problem instances generated for each problem size (n) and number of MAP variables (Q), respectively. Next to the running time we show the number of instances solved within the time/memory limit (if the number is omitted then all 100 instances solved). We can see that in terms of running time, CMBE(2) performs best on the grid networks. This is because the intermediate potentials generated during elimination are relatively small size and therefore are processed quickly. However, the algorithm is not able converge to good quality solutions compared with its competitors. The picture is reversed on the random and k-tree networks where CMBB(2) is the worst performing algorithm both in terms of running time and solution quality, In this case, the relatively large intermediate potentials cause the algorithm exceed the time and memory limits on many problem instances and thus impact negatively its performance.
The local search algorithms SHC, TS and SA yield the best performance in terms of solution quality with all three algorithms almost always converging to the best possible solutions on these problem instances. In terms of running time, SA is the fastest algorithm achieving almost order of magnitude speedup over its competitors, especially for larger numbers of MAP variables (e.g., h-trees with n 100 variables and Q 60 MAP variables). Algorithms SHC and TS have comparable running times (with SHC being slightly slower than TS) but they are significantly slower than SA. This is due the significantly larger computational overhead required for evaluating the scores of all the neighbors of the current state, especially when there are many MAP variables.
6.2 Real- World Credal Networks
Table shows the results obtained on set of credal networks derived from 22 real-world Bayesian networks by converting the probability values in the CPTs into probability intervals such that the difference between the corresponding lower and upper probability bounds was at most 0.3. Furthermore, since the local search algorithms rely on the L2U approximation to evaluate the MAP configurations, restricted the domains of the multi-valued variables to the first two values in the domain while shrinking and re-normalizing the corresponding CPTs. For each network we selected uniformly random Q 50% of the variables to act MAP variable and generated 10 random instances. As before, we indicate next to the average running times the number of instances solved
Available http::/wwww.bllee..comm//rrrrggp

---

MC
PD
PAIR
RxE
KLOG
K408
ISC
onn PASE
At
KGoM
(a) Brain Tumour diagnosis
(b) Attack Intelligence report
Figure 2: Applications of Credal Marginal MAP inference.
by the respective algorithms within the time and memory limits. We can see again that CMBE(2) is competitive only on the easiest instances (e.g., child, mildew) while SA yields the best performance in terms of both running time and solution quality on the majority of the problem instances. In summary, the relatively large potentials hinder CMBE's performance, while the computational overhead incurred during the evaluation of relatively large neighborhoods of the current state slows down significantly SHC and TS compared with SA.
6.3 Applications
Figure 2a shows the credal network for the brain tumour diagnosis case derived from the Bayesian network described in [IT]. The variables are: MC metastatic cancer, PD Paget disease, B brain tumour, ISC increased serum calcium, H headaches, M memory loss, CT scan result.
Considering the query variables B and TSC, the exact solution for both maximax and maximin CMMAP is (B- 0, TSC 0) (obtained by both the CVE and DFS algorithms). In this case, the maximax and maximin scores are 0.837 and 0.42, respectively. Algorithms SHC, TS and SA also find the optimal configuration (B 0, ISC = 0) which is evaluated by L2U to 0.8316 for maximax CMMAP and to 0.37296 for maximin CMMAP, respectively.
Figure 2b shows the credal network for the intelligence report analysis described in 9 The variables are: As assassination, C- coup/revolt, R regime change, D decision to invade, At attack, B build-up, P propaganda, I- invasion.
Considering the query variables D. At and I, the exact solution for both maximax and maximin CMMAP is (D = 0, At = 0, 7 = 0) and is obtained by both algorithms CVE and DFS. The in this
0.765 and 0. 0.4588066, respectively. The approximation schemes SHC, TS and SA also find the same optimal CMMAP configuration (D = 0, At = 0, I = 0) which evaluated by L2U to 0.69651 for maximax CMMAP and to 0.305486 for maximin CMMAP, respectively.
corresponding scores
We note that in both cases, the constrained induced width is 2 and therefore CMBE(2) coincides with the exact CVE. Therefore, all our approximation schemes found the optimal solutions.
7 Conclusions
The paper explores the Marginal MAP inference task in credal networks. We formally define the Credal Marginal MAP task and present new exact algorithms based on variable elimination and depth- first search. Subsequently, we introduce approximate algorithms using the mini-bucket partitioning or a combination of stochastic local search and approximate credal marginal inference. Our experiments on random and real-world credal networks demonstrate the effectiveness of our CMMAP algorithms. potential direction for future work is to investigate branch-and-boung and best-first search strategies guided by credal version of weighted mini-buckets [32]
10

---

Acknowledgements
Fabio Cozman was supported in part by C4AI funding (FAPESP and IBM Corporation, grant 2019/07665-4) and CNPq (grant 305753/2022-3),
References
[1] Judea Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, 1988.
[2] Rina Dechter. Bucket elimination: unifying framework for reasoning. Artificial Intelligence, 113:41-88 85, 1999.
[3] James Park. MAP complexity results and approximation methods. In Uncertainty in Artificial Intelligence (UAI), pages 388-396 2002.
[4] Radu Marinescu, Rina Dechter, and Alexander Ihler. AND/OR search for marginal MAP. In Uncertainty in Artificial Intelligence (UAI), pages 563-572, 2014.
[5] Junkyu Lee, Radu Marinescu, and Rina Dechter. Applying search based probabilistic inference algorithms to probabilistic conformant planning: Preliminary results. In Proceedings of the International Symposium on Artificial Intelligence and Mathematics (ISAIM), 2016.
[6] Jose M. BBiouca-DDial -asu and Mario A. T. Figueiredo. Bayesian image segmentation using hidden fields: Supervised, unsupervised, and semi-supervised formulations. In Proceedings of the European Signal Processing Conference (EUSIPCO), pages 523-527, 2016.
[7] Evangelia Kyrimi, Scott McLachlan, Kudakwashe Dube, Mariana R. Neves, Ali Fahmi, and Norman Fenton. A comprehensive scoping review of bayesian networks in healtheare: Past, present and future. Artificial Intelligence in Medicine, 117, 2021.
[8] Fabio Cozman. Generalizing crimiile-limmination in Bayesian networks. In Workshop Probabilistic Reasoning in Bayesian Networks at SBIA/lberamia 2000, pages 21 21-26, 2000,
[9] Denis Maua and Fabio Cozman. Thirty years of credal networks: Specifications, algorithms and complexity. International Journal of Approximate Reasoning, ((126):13-113) 2020.
[10] Gregory Cooper. Nestor: A computer-based medical diagnosis aid that integrates causal and probabilistic knowledge. Technical report, Computer Science department, Stanford University, Palo-Alto, California, 1984.
[11] Johan Kwisthout. Most probable explanations in Bayesian networks: Complexity and tractability, International Journal of Approximate Reasoning, 52(1): 2011.
[12] Marco Zaffalon, Alessandro Antonucci, and Rafael Cabañas. Structural causal models are (solvable by) credal networks. In European Workshop Probabilistic Graphical Models, 2020.
[13] Isaac Levi. The Enterprise of Knowledge. MIT Press, 1980.
[14] Peter Walley, Statistical Reasoning with Imprecise Probabilities. Chapman and Hall, London, UK, 1991.
[15] Cassio Campos and Fabio Cozman. The inferential complexity of Bayesian and credal networks. In International Joint Conference on Artificial Intelligence (IJAAI) pages 1313-1318, 2005.
[16] Eyke Hüllermeier, Sébastien Destercke, and Mohammad Hossein Shaker. Quantification of credal uncertainty machine learning: critical analysis and empirical comparison. James Cussens and Kun Zhang, editors, Proceddings of the Thirly-Eighth Conference Uncertainty Artificial Intelligence, volume 180 of Proceedings of Machine Learning Research, pages 548-557, PMLR, 01-05 Aug 2022.
[17] James Park and Adnan Darwiche. Solving MAP exactly using systematic search. In Uncertainty in Artificial Intelligence (UAI), pages 459-468, 2003.

---

[18] Changhe Yuan and Eric Hansen. Efficient computation of jointree bounds for systematic MAP search. In International Joint Conference on Artificial Intelligence (IJCAI), pages 1982-1989, 2009.
[19] Junkyu Lee, Radu Marinescu, Rina Dechter, and Alexander Ihler. From exact to anytime solutions for marginal MAP. In 30th AAAI Conference on Artificial Intelligence, pages 1749- 1755, 2016.
[20] Radu Marinescu, Junkyu Lee, Rina Dechter, and Alexander lhler. Anytime best+depth-fing search for bounding marginal MAP. In 31st AAAI Conference on Artificial Intelligence, pages 1749-1755, 2017.
[21] Radu Marinescu, Junkyu Lee, Rina Dechter, and Alexander Ihler. AND/OR search for marginal MAP. Journal of Artificial Intelligence Research, 63:875-9211 921, 2018.
[22] Rina Dechter and Irina Rish. Mini-buckets: A general scheme of approximating inference. Journal of ACM, 50(2):107-153, 2003.
[23] Jiarong Jiang, Piyush Rai, and Hal Daume. Message-passing for approximate MAP inference with latent variables. In Advances in Neural Information Processing Systems (NIPS), pages 1197-1205. 2011.
[24] Qiang Cheng, Feng Chen, Jianwu Dong, Wenli Xu, and Alexander Ihler. Approximating the sum operation for marginal-MAP inference. In 26th AAAI Conference on Artificial Intelligence, AAAI, pages 1882-1887, 2012.
[25] Qiang Liu and Alexander Ihler. Variational algorithms for marginal MAP. Journal of Machine Learning Research, 14:1155-3000) 2013.
[26] Wei Ping, Qiang Liu, and Alexander Ihler. Decomposition bounds for marginal MAP. In Advances in Neural Information Processing Systems 28, pages 3267-3275, 2015.
[27] Denis Maua and Cassio Campos. Anytime marginal MAP inference. In International Conference on Machine Learning (ICML), pages 1471-1478, 2012.
[28] Rina Dechter. Mini-buckets: A general scheme of generating approximations in automated reasoning. In International Joint Conference Artificial Intelligence (IJCAI), pages 1297-1302, 1997.
[29] Jaime Shinsuke Ide and Fabio Gagliardi Cozman. Approximate algorithms for credal networks with binary variables. International Journal of Approximate Reasoning, 48(1):275-299 2008
[30] Alessandro Antonucci, Sun, Cassio P De Campos, and Marco Zaffalon. Generalized loopy 2u A new algorithm for approximate inference in credal networks. International Journal of Approximate Reasoning, 51(5):474 484, 2010.
[31] Alessandro Antonucei, Cassio Campos, David Huber, and Marco Zaffalon. Approximate credal network updating by linear programming with applications to decision making. International Journal of Approximate Reasoning, 58(3):25-38, 2015.
[32] R. Marinescu and R. Dechter. AND/OR tranch-and-bound search for combinatorial optimization 2009.
in graphical models. Artificial Intelligence,
12


Reviews:
[{"review_id": "ZyDNgVSkgK", "reviewer": "Reviewer_9XGw", "summary": "The paper proposes inference algorithms for credal networks for the marginal MAP inference task. The idea is to use variable elimination methods for this task. An exact inference algorithm is proposed as well as approximations using mini-bucket partitioning. Further, stochastic local search procedures combined with existing approximate marginal inference methods are proposed to solve the MMAP task. Experiments are performed on randomly generated credal networks as well as real-world Bayesian networks converted to credal networks.\n", "questions": "What strategies could we use to control/trade-off accuracy vs complexity in the algorithms where the results show best performance (e.g. SA)?", "limitations": "There are no limitations explicitly mentioned.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This looks to be the first work on MMAP for credal networks which seems significant since MMAP is a hard but important task for PGMs. The use of existing inference algorithms with the local search methods gives a general family of MMAP algorithms. The evaluation considers a large number of benchmarks. The paper is generally well-written with clear contributions.", "weaknesses": "The relatively poor performance of CMBE may indicate it is hard to get more reliable performance for MMAP (e.g. by increasing i-bound of CMBE) for credal networks compared to approximations for other PGMs. The stochastic local search algorithms which seem to work much better in the experiments may be harder to trade-off w.r.t accuracy vs complexity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and suggestions.\n\nOne way to address the tradeoff accuracy vs complexity in the case of algorithm CMBE for example is to also bound the size of the sets of potentials that are propagated during elimination (or approximate somehow these sets of potentials). This way we may be able to increase the i-bound (thus hoping to improve accuracy) while lowering to some extent the computational complexity of the elimination process. Clearly, we will need to expand the empirical evaluation of this proposed scheme; we hope our paper will open an interesting line of research exploring better bounds for this provably hard problem. \n\nFor the local search based algorithm we may be able to lower the computational effort  by developing a faster, incremental scheme to compute the scores of all neighbours using the score of the current solution. At the moment, each neighbour’s score is computed from scratch using an approximate marginal inference algorithm and this negatively impacts the running time especially on larger problem instances. The comments by the reviewer do suggest exciting paths to be pursued.\n"}, {"review_id": "YVFyOPDvEA", "reviewer": "Reviewer_3qEE", "summary": "This work presents novel algorithms for performing exact and approximate marginal MAP inference in credal networks with discrete-valued factors, and evaluates the computational and inferential effectiveness of these algorithms on a number of benchmarks.", "questions": "Is the case where the credal network has arbitrary real-valued distributed variables, rather than all discrete-valued variables, important for any of the applications discussed?", "limitations": "Method seems only to apply to Bayesian Networks in the narrow sense of the term with discrete factors. ", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "Firstly, I enjoyed reading the paper and think it’s fantastic how basic research into PGM inference is still being done. A strength of the paper is the technical depth demonstrated to devise these novel inference algorithms. I thought the design of the ablation study was solid and plenty of real-world experiments given.", "weaknesses": "One weakness is that the explanation of the algorithms proposed is difficult to follow, but perhaps this is unavoidable with a heavily technical topic. I think it would strengthen the paper to explain the significance of marginal MAP in credal networks in particular, and performing experiments on counterfactual analysis. More discussion/experiments on counterfactual inference may strengthen the apparent contribution/impact of solving MMAP in credal networks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and suggestions.\n\nWe will revise the presentation and will try to expand the discussion of the algorithms in order to address the concerns identified during the review. Certainly the content is very technical but we will do our best to make it more didactic. \n\nWe appreciate your suggestion to perform experiments on counterfactual analysis. We will definitely take it into consideration and try to formalize the connection between the CMMAP task and counterfactual analysis. We emphasize that causal reasoning is a clear application of credal networks (as explained in our Ref. [12]), a point that, we think, adds to the relevance of the paper to NeurIPS. More specifically, the estimation of distributions for exogenous variables from the observation of endogenous variables directly leads to credal networks, so our techniques can be directly applied to counterfactual reasoning given endogenous distributions and associated directed graphs that capture causal mechanisms (as in fact shown by the paper by Zaffalon et al).\n\nRegarding your questions about real-valued variables, yes, we believe that it is almost always the case that in real-world applications many variables of interest are real-valued. Therefore, we will adopt the broad definition of Bayesian/credal networks as the focus on discrete factors is a feature of this paper but a larger perspective including continuous variables can be very important in applied work and may be a path for future research.\n\nFurthermore, real-valued variables typically require developing different kinds of algorithms compared with the variable elimination and search based ones we proposed in this paper. Handling real-valued variables is also an important direction of our future work.\n"}, {"review_id": "jZWidPJEzb", "reviewer": "Reviewer_VJAx", "summary": "This paper is about a generalisation of marginal MAP (MMAP) for Bayesian networks (BNs). The authors allow the BN parameters to vary in (credal ) sets. The goal is, therefore, to find the configuration with the maximum upper (wrt the credal sets) probability. The authors first consider exact inference. A number of schemes based on mini-buckets are then obtained to address approximate inference and empirically validated.", "questions": "The ApproxLP scheme based on linearisation is used to address MAR in CNs. Can we extend it to MMAP and then perform a comparison against the methods proposed here? This point is partially addressed in Section 5.2, but the answer seems to be a bit inconclusive.\n\nCMBE is giving an upper bound. Do the search methods give a lower bound? If so, is it never the case that the two results coincide, this meaning that the solution is exact? ", "limitations": "I don't see significant sociated impacts for the present work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem is important and very general (in a sense, most of the classical inferences in PGMs can be intended as a subcase of CMMMAP). This seems to be the first serious attempt to address the problem in the credal case and the experiments show how the proposed approximate schemes allows to solve a large number of non-trivial instances.", "weaknesses": "The authors only consider maxi-max and maxi-min versions of the problem. Credal networks are often used to model a condition of indecision between multiple options, and considering other decision criteria possibly leading to multiple options (e.g., maximality or interval dominance) would be interesting. This is also related to the ideas sketched by De Bock et al. (Neurips 2014).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and suggestions.\n\nWe are already exploring several ideas around interval dominance as well as alternative criteria such as maximality and/or E-admissibility. Therefore, we are very thankful for your suggestions and we plan to address these issues in our future work.\n\nExtending ApproxLP to CMMAP is indeed an interesting idea. We believe that in principle it is possible to do so. Therefore, it is an excellent suggestion of future work together with developing new, more efficient approximation schemes for CMMAP.\n\nAt the moment, the search based schemes can give a lower bound only if the approximate marginal inference algorithm used to evaluate the current solution is guaranteed to provide a lower bound on the probability of evidence (either the lower probability or the upper probability). And yes, in principle, if we have that the upper bound produced by CMBE is the same as the lower bound produced by another scheme then they both found the exact solution. Therefore, one direction of future work is to develop a scheme that computes in an anytime manner both lower and upper bounds on the CMMAP values.\n"}, {"review_id": "pIU4Ofxggt", "reviewer": "Reviewer_8qY7", "summary": "The paper studies algorithms for the marginal MAP (MMAP) problem in Credal networks that generalize Bayesian networks. The paper gives an overview of the problem, existing algorithms for Bayesian networks and generalizes the algorithms to credal networks. Overall, two exact and multiple heuristic approaches are presented. As the exact approaches were unable to deal with larger problems, the experiments are restricted to heuristic approaches. ", "questions": "Could you elaborate on the relationship between CN and BN algorithms (see weaknesses)?", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is very well written and gives a good overview of the problem and related work. While Bayesian networks are an old topic, they remain relevant for probabilistic reasoning tasks that require analytical guarantees. However, one problem of Bayesian networks is that specifying the CPDs can be difficult. Credal networks are an interesting generalization that allows using probability intervals rather than point probabilities in order to capture the uncertainty about the encoded knowledge. To the best of my knowledge, there is not much literature on algorithms for Credal networks. The authors generalize state-of-the-art ideas for Bayesian networks to Credal networks and give an empirical evaluation. The paper is therefore an interesting contribution to the probabilistic reasoning literature. The code is attached in the supplementary material to reproduce the experimental results and is a useful resource for the probabilistic reasoning community.", "weaknesses": "It could be discussed in more detail what the exact relationship between the proposed algorithms and the corresponding algorithms for BNs is. Are they generalizations in the sense that if the intervals in the Credal network are tight, then the Credal network algorithms correspond to the BN algorithms? Are there challenges in generalizing the algorithms to credal nets or is the generalization straightforward? And how do the runtime guarantees for Credal networks compare to those for Bayesian networks? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and suggestions.\n\nRegarding the relationship between the CN and BN algorithms, in principle, if the probability intervals in a CN are tight, namely they collapse to point probabilities, then the CMMAP task we defined for CNs collapses to the MMAP task for BNs. In this case, the CMBE algorithm, for example, will be identical to the MBE algorithm for MMAP in BNs because CMBE will no longer have to propagate sets of potentials. \n\nHowever, in the more general case when we introduce probability intervals and/or more complex credal sets, the two tasks are different from a computational complexity point of view: MMAP for BNs is NP^PP-complete, whereas MMAP for CNs is NP^NP^PP-complete. Therefore, the corresponding MMAP algorithms will be significantly different (i.e., those for CNs vs those for BNs).\n"}]

Author rebuttal:

Meta-review: This paper studies marginal MAP inference, which is already notoriously hard on graphical models. It does so on credal graphical models, where accounting for the parameter uncertaintly makes the problem even more challenging. The paper is novel in studying this problem and the empirical evaluation is thorough.
Decision: Accept (poster)