Abductive Reasoning in Logical Credal Networks
Authors: Radu Marinescu
Junkyu Lee
Debarun Bhattacharjya
Fabio Cozman
Alexander G. Gray
Venue: NeurIPS 2024 poster (2024)
Keywords: probabilistic logic
imprecise probabilities
MAP inference
search
message passing
Primary area: probabilistic_methods
TL;DR: The paper presents new algorithms for MAP and Marginal MAP inference in Logical Credal Networks.

Abstract: Logical Credal Networks or LCNs were recently introduced as a powerful probabilistic logic framework for representing and reasoning with imprecise knowledge. Unlike many existing formalisms, LCNs have the ability to represent cycles and allow specifying marginal and conditional probability bounds on logic formulae which may be important in many realistic scenarios. Previous work on LCNs has focused exclusively on marginal inference, namely computing posterior lower and upper probability bounds on a query formula. In this paper, we explore abductive reasoning tasks such as solving MAP and Marginal MAP queries in LCNs given some evidence. We first formally define the MAP and Marginal MAP tasks for LCNs and subsequently show how to solve these tasks exactly using search-based approaches. We then propose several approximate schemes that allow us to scale MAP and Marginal MAP inference to larger problem instances. An extensive empirical evaluation demonstrates the effectiveness of our algorithms on both random LCN instances as well as LCNs derived from more realistic use-cases.

Abductive Reasoning in Logical Credal Networks
Radu Marinescu
Junkyu Lee IBM Research, USA junkyu. lee@i bm. com
IBM Research, Ireland aedd.mmainne. cuu ie. bim. com
Debarun Bhattacharjya
Fabio Cozman
IBM Research, USA
Universidade de São Paulo, Brazil
debarunbêus. 1bmm com
fgcozmaneusp... br
Alexander Gray
Centaur AI Institute, USA
alexander hww.aande..rsyeeetaaarraatttttoo
Abstract
Logical Credal Networks or LCNs were recently introduced as a powerful proba- bilistic logic framework for representing and reasoning with imprecise knowledge. Unlike many existing formalisms, LCNs have the ability represent cycles and allow specifying marginal and conditional probability bounds on logic formulae which may be important many realistic scenarios. Previous work LCNs has focused exclusively marginal inference, namely computing posterior lower and upper probability bounds on a query formula. In this paper, we explore abductive reasoning tasks such as solving MAP and Marginal MAP queries in LCNs given some evidence. We first formally define the MAP and Marginal MAP tasks for LCNs and subsequently show how to solve these tasks exactly using search-bar based approaches. We then propose several approximate schemes that allow us to scale MAP and Marginal MAP inference to larger problem instances. An extensive em- pirical evaluation demonstrates the effectiveness of our algorithms on both random LCN instances well as LCNs derived from more realistic use-cases.
Introduction
Probabilistic logic which combines probability and logic in principled manner has emerged the past decades as a unified representational and reasoning framework capable of dealing effectively with complex real-world applications that require efficient handling of uncertainty and compact 8
9 [O]. Logical Credal Networks or LCNs [ were introduced recently as probabilistic logic designed for representing and reasoning with imprecise knowledge. Unlike many existing probabilistic logics, LCNs have the ability to represent cycles (e.g.. feedback loops) as well allow specifying marginal and conditional probability bounds on logic formulae which may be important in many realistic usecases.
representations of domain expert knowledge 2 3 5
7
Up until now, the work LCNs has focused exclusively on marginal inference, i.e. efficiently computing posterior lower and upper probability bounds on a query formula. However, abductive reasoning tasks such explaining the evidence observed in an LCN equally important in many real-world applications. In probabilistic graphical models, these tasks are commonly known as MAP and Marginal MAP (MMAP) inference and have received extensive attention over the past decades [3]
[3] They are typically tackled efficiently with dynamic programming (c.g., variable climination) or heuristic search (e.g., depth-first -irstt branch and bound) based algorithms B
16
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Contribution. In this paper, we consider solving MAP and Marginal MAP inference queries in LCNs. Unlike in graphical models, an LCN encodes a set of probability distributions over its interpretations. Therefore, a complete or a partial explanation of the evidence which represents complete or partial truth assignment to the LCNN's propositions may correspond to more than one distribution. Our work builds on very recent work on Marginal MAP inference for credal networks, class of probabilistic graphical models that allow reasoning with imprecise probabilities [17]. We formally introduce the MAP and Marginal MAP tasks for LCNs as finding a complete partial truth assignment to the LCN's propositions with maximum lower (respectively, upper) probability, given some evidence in the LCN. We show how to evaluate such MAP assignments using exact marginal inference for LCNs and, subsequently, propose several search schemes based on depth-first first search, limited discrepancy search and simulated annealing to solve these tasks in practice. We then extend a recent message-passinng scheme for approximate marginal inference in LCNs [8] to handle effectively the MAP and MMAP inference tasks in LCNS as well as adapt the limited discrepancy search and simulated annealing methods to use an approximate evaluation of the MAP assignments during search. We experiment and evaluate proposed exact and approximate algorithms several classes of LCNs including random as well as more realistic LCN instances. Our results show that the search methods based on exact evaluation of the MAP assignments are limited to solving small size problems in practice, while the approximate message-passinng scheme and, to some extent, the approximate gearch-based methods can scale much larger problem instances. This is important because it allows us to tackle practical problems involving hundreds and possibly many thousands of propositions. The supplementary material includes additional details and experiments.
2 Background
We provide next a brief overview of basic concepts about LCNs and marginal inference in these models. Throughout the paper we will use the following notations. Logical propositions are denoted by uppercase letters (e.g., A, B, C....) while for sets of propositions we use boldfaced uppercase letters (e.g., A, B, C, ...). Truth assignments lowercase or uppercase letters, namely we use a or A to indicate that proposition A holds true, and -a -A if A is false. Sets of literals are denoted by boldfaced lowercase letters (c.g., a, b, C...).
propositions (i.e.. literals) are denoted by either
2.1 Logical Credal Networks
Logical Credal Network (LCN) is defined by a tuple -= (A,C) where A = {AI...., An) is set of propositions (or atoms), and C is set of probability labeled sentences (or constraints) having the following two forms:
a S P(o) <
a < P()le) < 8
Here, ó and x are arbitrary propositional logic invollvng propositions in A and logical connectives such negation, disjunction and conjunction, and 0 I a S 3 < 1 are lower and upper probability bounds, respectively.
An LCN is associated with primal graph which is a directed graph G' containing formula nodes and proposition nodes, as well as directed edges from each proposition node in a formula é to the formula node representing ø (for type sentences), and directed edges from each of the proposition nodes in yp to yp, a directed edge from yp to Φ), and bi-directed edges from & to the proposition nodes in d, respectively (for type 2 sentences) [T]. A parent of proposition A in G is proposition B such that there a directed path in G from B to A in which all intermediate nodes are formulae. A descendant of a proposition A in G is proposition B such that there is directed path in G from A to B in which no intermediate node is a parent of A [II].
An LCN is endowed with Local Markov Condition (LMC) where proposition node A is indepen- dent, given its parents, of all proposition nodes that are not A itself nor descendants of A nor parents of A [I]] Therefore, an LCN represents set of probability distributions over all interpretations of its formulae that satisfy the constraints represented by the type (1) and (2) sentences as well as the constraints induced by the independence relations given by the local Markov condition [
'The original definition of LCNs allows for relational structures and first-order logic formulae, but their semantics is obtained by grounding finite domains thus yieling propositional LCN (...

---

0.05 S P(B) S 0.1
BVC
0.3 & 0.4
V CIS) S 0.2
B
C
(X ①
D)
0.6 P A C) 0.7
0.7 S PX + D)IC) s 0.8
B
(a) I.CN sentences
(h) Primal graph
Figure I: A simple LCN and its primal graph.
Example 1. Figure 7 describes simple LCN whose sentences shown in Figure Ta state that: Bronchitis (B) is more likely than Smoking (S); Smoking may cause Cancer (C) or Bronchitis; Dyspnea (D) shortness of breadth is a common symptom for Cancer and Bronchitis; in case of Cancer we have either a positive X-Ray result (X) and Dyspnea, or a negative X-Ray and no Dyspnea. T the primal graph where the formula and proposition nodes are displayed as rectangles and shaded circles. respectively.
2.2 Marginal Inference in Logical Credal Networks
Given an LCN L with n propositions. the marginal inference task is compute lower (3) and upper bounds on the posterior probabil- ity P(t) of query formula 1ú, which de- (4) note by P(t) and P(v), respectively. This
m
Σ P:
Di 2 0, Vi l....,m a a 1
(5) is achieved by solving non-lineat program given by Equations 3 g and defined by a set of non-negative real real-valued variables representing the probabilities of L's inter- pretations, of linear constraints derived from L's sentences, set of non-linear con- straints corresponding the independence assumptions given by the local Markov condition, and a linear objective function encoding the query P(t) which is minimized and maximized yield the desired bounds. More specifically, let p = (p....., Pm) be the vector of real-valued variables representing the probabilities L's inter- pretations, where m 2", and let To (af..... .af.....ae ath ) be a binary vector, called an indicator vector, such that a is if formula e is true in the i-th interpretation and 0 otherwise. Since the probability of a formula Φ is the sum of the probabilities of the interpretations which & is true, we can write P()) as To 3 p where @ is the dot-product of two vectors. Therefore, Equations (3) and (4) ensure that Ø a valid probability distribution, Equations (5) and (6) encode the type (1) and (2) sentences in L while Equation encodes the conditional independencies of the form P(X, S T = P(X,IS)). where X, proposition, S; = {S,I..... S5a} and T, (T,I,..., Tx are X,'s parents and non-descendants in the primal graph of C, Io and Tonp are the indicator vectors for formulae ó and A ip involved in L's sentences, and F., T., and Ta are the indicator vectors corresponding the formulae a = ( A88 A A A A4 . and d (811 A... 85k A la ... A 15)), respectively (see also 11 for more details).
1T (Ia
minimize/maximizz 1 O
Alg)). J (811 A... .....A8p. Aj c = (xy A8j1 A A...A835)) 888),
3 MAP and Marginal MAP Inference in LCNs
Maximum A Posteriori (MAP) and Marginal MAP (MMAP) inference are well known abductive reasoning tasks probabilistic graphical models such as Bayesian networks and Markov networks 14
15 16] Specifically, the MAP task calls for finding complete assignment to all variables having maximum probability, given the evidence. Marginal MAP generalizes MAP and looks for partial variable assignment that has maximum marginal probability, given the evidence. MAP
12 13

---

and MMAP inference tasks appear in many real-world applications such as diagnosis, abduction and explanation and are typically tackled with dynamic programming (e.g.. variable elimination) or
heuristic search (e.g., depth-first branch and bound) based algorithms 13
14
15 16.
In this section, we present our novel approach for solving the MAP and Marginal MAP inference tasks in Logical Credal Networks. Unlike in graphical models, (partial) variable assignment (or interpretation) in an LCN may correspond more than one distribution. Therefore, we begin by formally defining two MAP and MMAP inference tasks for LCNs, called maximin MAP (resp. maximin MMAP) and maximax MAP (resp. maximax MMAP). Subsequently, we develop several exact and approximation schemes for solving these tasks efficiently in practice.
3.1 The MAP and Marginal MAP Tasks in L.CNs
Let L = () be an LCN with n propositions and let E (Fi...., Fi C A be a subset of k propositions, called evidence, for which the truth values e {eI...., Ek] are known. Let Y = (Yi,..., Ym S A E be a subset of m propositions called MAP propositions. A truth assignment to Y is is called MAP assignment and is denoted by y {111.... Vm J. respectively. Clearly, , if Y = A \ E (i.e., m = n k) then we have a MAP task, otherwise we have MMAP task (i.e., n k). The maximin and maximax MAP/MMAP tasks are defined follows:
Definition (maximin). Given an LCN L with n propositions, evidence e, and MAP propositions Y. the maximin MAP (or maximin MMAP if m < n - k) task is finding truth assignment y" to Y having maximum lower probability, given evidence e, namely:
argmax P(tbysa) yEQ(Y)
(9)
where Q(Y is the set of all truth assignments to the MAP propositions, and Uyse = 1/1 A .... A Aym Um e1 A ... Cg is the conjunction of the literals in y and e, respectively.
A
Definition 2 (maximax). Given an LCN L with n propositions. evidence e, and MAP propositions Y, the maximax MAP (or maximax MMAP if m < n k) task is finding truth assignment y" to
Y having maximun upper probability, given evidence e, namely:
y" argmax P(éyne) yEn(Y)
(10)
where ()) is the set of all truth assignments to the MAP propositions, and tyye V1 A - pm A
e1 .... eg is the conjunction of the literals in y and e, respectively.
3.2 Search Algorithms Using Exact MAP Assignment Evaluations
We present next three search-based schemes for solving the MAP and MMAP tasks in LCNs. These methods employ different search strategies for exploring the search space defined by the MAP propositions while evaluating exactly each complete or partial MAP assignment.
Exact Evaluation of MAP Assignment. Clearly, computing the lower and upper probabilities P(tyye) and P())yne) of MAP assignment y given evidence can be done easily by minimizing
and, respectively maximizing the non-linear program defined by Equations ( ( where the query
formula is the conjunetion of positive or negative literals y and e, namely &/ yhy y1 A-.. A ym A e1 A... A cg. Therefore, evaluating MAP assignment in case of both MAP and Marginal MAP inference in LCNs is quite difficult as involves solving maginal inference problem for LCNs which is know to be Na-hard [Л]. This is in contrast with graphical models where, least for MAP inference, the evaluation of a MAP assignment is linear in the number of variables [13.
Example 2. For illustration, consider the LCN example from Figure 7 and assume that we have evidence {x, -s), namely patient has positive X-Ray result (X I:) and is not smoking (S -s) The MAP propositions in this case are Y [B,C, D} and the MAP assignment y (b, -c, -d) corresponds to the query formula tyyne = P - -d x -s. The lower and upper probabilities P(wyye) and P( P(yyne) of the MAP assignment are 9, 0.9e-09 and O.I, respectively.

---

Algorithm Depth-First Search for MAP and Marginal MAP Inference in LCNs
1: procedure DFS(C (), E Y)
10: scorely) &- P(
2: initialize y f- 0, best + -00
11:
if score(y) best then
3: SEARCI(0, Y)
12:
y" + y, best score(y)
4: return y
13:
else
5: procedure SEARCH(Y, Y)
14:
select unassigned proposition Y; E
6: if size(y) = size Y) then
15:
for all values y {yr, my: do
7: if' maximiin then
16:
+ U {Y, =
8: score(y) L(vyyn)
17: SEARCH(y, Y)
9: else
Algorithm 2 Limited Discrepancy Search for MAP and Marginal MAP Inference in LCNs
1: procedure LDS(C (A, C)2 E == e, Y, 8)
12: scorely) P(bbyne)
2: initialize Yo randomly and let y +- Yo
13: if score(y) > best then
3: best t- sc"re(y")
14:
y" y, best score(y)
4: for all 0 = 1..... do
15:
else
5: SEARCH(Y", Y. 1)
16:
for all values {yr, -Vi do if y = then
6: return y", best
17:
7: procedure SEARCH(y, Y, i)
18:
f SEARCH(y, Y, i 1,
8: i = or Y then
19:
else
9: if maximin then
20:
y' y.y'l + y
score(y) P(Vyna)
21:
2 f- SEARCH(y', Y, i 1, 1)
11: else
22: return Z
Depth-First Search. Our first approach for solving the MAP and MMAP tasks, called DFS, is described by Algorithm 1
takes as input an LCN L (A, C), evidence MAP propositions Y A E and outputs the optimal MAP assignment y* The method conducts a depth-first search over the space of partial assignments to the MAP propositions, and, for each complete MAP assignment y computes its score the exact lower probability P(yyne) for maximin tasks, and respectively, the upper probability P()yye) for maximax tasks, given the evidence This way, the optimal solution y" corresponds to the MAP assignment with the highest score.
e and a set of
Theorem 1 (complexity). Given an LCN (A.C) with propositions, evidence propositions Y C A E, algorithm DFS is sound and complete. The time and space complexity of the algorithm is 0(2m+2") and (22)), respectively, where m is the number of MAP propositions.
and MAP
Example 3. Consider again the LCN from Figure | with evidence e = {ar, -s}. In this case, the exact maximin MAP assignment found by algorithm DFS y = =(-b, c, d] with value 9.99e-09, while the exact maximax MAP assignment
{-b, -c, d} with value 0.7, respectively.
Limited Diserepancy Search. Our second approach for MAP and MMAP inference in LCNS
uses Limited Discrepancy Search (LDS) 19 20 explore the search space and is described by Algorithm Specifically, LDS is a depth-first search strategy that searches for new solutions by iteratively increasing the number of discrepancy values, where discrepancy value indicates the maximum number of allowed variable- value assignment changes to an initial solution [19]. Function SEARCH (lines 7-22) performs the actual exploration of the search space limited by discrepancy 0. If the selected truth value {y:. T is different from the one corresponding to proposition Y, E Y at position in the assignment y, decremented to reduce the number of changes allowed to the remaining MAP propositions. Otherwise, the truth value for proposition Y; remains unchanged and the / value preserved. As before, complete MAP assignments are evaluated exactly (lines 9-12) and the best solution found far is maintained (lines 13-14).
5

---

Algorithm 3 Simulated Annealing for MAP and Marginal MAP Inference in LCNs
1: procedure SA(C= (A, C), E c, Y)
10:
if A > 0 then t- y'
2: initialize Yo randomly and let y + Yo
11:
else
3: best f- score(y")
12:
sample randomly p (0, 1) p e² then y y' scoreeyy > best then y y, best + scorely)
4: for all iterations i 1... .....N N do
13:
5: set y-"",
T Tinit
14:
6: for all flips j = 11..... M do
15:
7: W be y''s neighbors
8: select random neighbor y' E A
16:
+ x
9: A
log scorely') log score(y)
17:
return y*
Algorithm 4 Approximate MAP and Marginal MAP Inference in LCNs
1: procedure AMAP(C (), E Y)
9:
else y + y" U [ty}
2: Create factor graph F of L
10:
else
3: Apply the ARIEL scheme from 18 F
11:
P(y) m Us-Y
4: for all MAP propositions Y E Y do
12:
P(-y)
P(y)
5: if' maximin then
6:
P(y) = max 4-+
13:
P(y) > P(-y) then y + y" (v)
14:
else y" + y" U{
7:
P(-y) = P(y)
8:
if P(y) ((-w) then y + (2)
15:
return y*
Theorem 2 (complexity). Given an LCN C (A.C) C) with n propositions, evidence E = e and MAP propositions Y A algorithm LDS is sound and complete. The time and space complexity of the algorithm is 0(2m+2") and ((2)). respectively, where is the number of MAP propositions.
Simulated Annealing. The third approach for solving MAP and MMAP tasks in LCNs is described by Eagorithmaaani employs a form of stochastic local search known as Simulated Annealing (SA) [21 to explore the search space defined by the MAP propositions. The algorithm starts from an initial guess y as a truth assignment to the MAP propositions Y, and iteratively tries to improve by moving to better neighbor y' that has higher score. A neightbr y' of is defined assignment y' which results from changing the truth value of a single proposition Y in Y. At each step, the transition from the current state y neighboring state y' is decided probabilistically using an acceptance probability function Ply', P(y',y,7 T)) that depends on the scores of the two states as well as global time-varying parameter T called temperature which is decreased using a cooling schedule ē where A log score(y') log score acore(y).
new
(21] We chose P(y Jyy.
Theorem 3 (complexity). Given an LCN - (A,C) with propositions, evidence E and MAP propositions Y C A E, the time and space complexity of algorithm SA is O(N M M222" 2²") and O(2"), respectively, where N is the number of iterations and M is the number of flips per iterations.
3.3 Approximate MAP and Marginal MAP Inference
The main bottleneck in the proposed search algorithms the exact evaluation of the MAP assignments which is computationally very expensive [TI. This limits the applicability of these methods to relatively small LCNs. Therefore, in order to be able to tackle larger LCNs, we extend recent messagc-passing approximation scheme for marginal inference in LCNs [8] to solve the MAP and MMAP tasks in LCNs. Subsequently, we also adapt the limited discrepancy search and simulated annealing methods to use approximate evaluation of the MAP assignments during search.
Algorithm 4 describes our message-passing based approximation scheme for MAP and MMAP inference in LCNs which we denote hereafter by AMAP. We build upon recent scheme for approximate marginal inference I.CNs, called ARIEL 18, which propagates messages along the edges of a factor graph associated with the input LCN until convergence. The factor graph F of an

---

LCN L is a bi bi-partite graph the connects proposition nodes labeled by the propositions in L with factor nodes associated with sentences that involve the same set of propositions [18]. The messages propagated between the nodes of F are intervals representing lower and upper bounds on the marginal probabilities of L's propositions and are computed as follows: the message sent from a proposition to factor node tightens these bounds based on the incoming messages from the factor nodes connected to it; the message sent from a factor to a proposition node computes new bounds by solving a local non-linear program defined by the factor's 's sentences and the constraints encoding the assumption that the factor's propositions are independent of each other and the marginal probabilities of the factor's 's propositions are within the bounds given by the incoming cropsstioontoo-fcttor messages (see also [18] for more details). Upon convergence, the maximin MAP assignment y" can be obtained as follows: for each MAP proposition Y E Y compute the tightest lower probability bound P(y) by maximizing the lower bound of all incoming factor-to-proee -opropostooooiiioonnnnn messages to Y, and, subsequently, select y as the most likely value assignment to Y if P(y) > P(-y) and my otherwise the upper probability bounds P(y) and P(-y), respectively).
(for the maximax tasks
Theorem 4 (complexity). Given an LCN C (A.C) with n propositions, evidence E = e and MAP propositions Y C A E, the time and space complexity of algorithm AMAP is O(N M 22") and ((2"). where N is the number of iterations, M bounds the number of factor-to-node messages per iteration and bounds the number of propositions in the factor nodes, respectively.
3.4 Search Algorithms Based on Approximate MAP Evaluations
The main assumption behind algorithm AMAP is that all MAP propositions are independent of each other and therefore the solution y* returned by AMAP is likely to correspond to a local maxima. One way to escape such a local optima and obtain a potentially better solution is to employ a search scheme based on either limited discrepancy search simulated annealing that continues the exploration of the search space starting from y". However, in order to scale to larger LCNs, we would like the search schemes rely on an approximate rather than an exact evaluation of the MAP assignments.
Approximate Evaluation of a MAP Assignment. Estimating the lower and upper probabilities of a MAP assignment y can be done by approximate marginal inference an augmented LCN as follows. Let L = (A, C) be the input LCN and let y = (./..... .ym) ) be a MAP assignment to propositions Y (Yi, ..... -....... Yn. } (for simplicity, we include the evidence in y). The augmented
LCN L' = (A',C* is constructed by adding a set of auxiliary propositions W = (WI..... W. J. one for each MAP proposition, and additional constraints of the following two forms: P(W and P(W, (W-,)W,,,Y,))... for all 2 < j < m, such that ((wi (81) = 1, P(wil ( = 0, ((w::(oo---iiu = 1, P(Wy/ujj- A 4 O, wyy -wj- A 45) = 0 and P(wyl -1-1 A -w;) = 0, respectively.
Then, we can estimate (((y)) and P(wy), where bhy = 1/1 A ... ym. by computing the posterior
marginals P(wm) and (wm) in the augmented LCN L' using the method from 18
Limited Discrepancy Search and Simulated Annealing. Our approximate LDS and SA based algorithms denoted by ALDS and ASA can be obtained from Algorithms 2 3 replacing the score(y) function with the approximate MAP evaluation scheme described above. These algorithms can start the search either from a random MAP assignment from the solution found by algorithm AMAP. Finally, the time complexity of algorithms ALDS and ASA can be bounded by O(2m+t?") and O(N M 22"" ). respectively, where is the number of MAP propositions, N is the number of iterations used by ASA, M is the maximum number of flips per iteration, and r bounds the number of propositions in the factor nodes of the factor graph associated with the input LCN [18).
4 Experiments
In this section, we empirically evaluate the proposed exact and approximate schemes for MAP and MMAP inference in LCNs. All competing algorithms were implemented in Python 3.10 and used the i popt 3.14 solver (22) with default settings to handle the non-linear constraint programs. We ran all experiments on a 3.0GHz Intel Core processor with 128GB of RAM.
The open-source implementation of LCNs is available https://giie cow.
7

---

Table Results for MAP tasks obtained on small/large scale polytree, dag, and random LCNs. Average CPU time in seconds and number of problem instances solved. Time limit is hours.
size
exact MAP
арprox MAP eval ALDS(3)
DFS
LDS(3)
SA
AMAP
ASA
polytres
5
15.30 (I0)
26.07 (10)
20.18 (10)
2.87 (10)
174.17 (10)
188.27 (10)
3246.28 (4)
3072.18 (4)
1199.51 (10)
8,05 (10)
1054.53 (10)
518.18 (10)
10
11.81 (10)
2273.16(10)
813.30 (10)
30
31.55 (10)
3091.74 (10)
50
52.30 (10)
5324.71 (10)
79.28 (10)
7279.56 (10)
dag
5
21.09 (I0)
15.66 (10)
24.04 (IO)
5.54
163.02 (10)
156.34 (10)
8
1633.38
1958.16 (9)
633.77 (10)
13.05 (10)
1339.71 (10)
571.55 (10)
15.55 (10)
2903.05 (10)
944.17 (10)
30
49.94 (10)
3593.71 (10)
50
89.13 (10)
5639.90 (10)
70
132.34 (10)
6093.28 (10)
randon.
5
19.51 (10)
17.56 (10)
20.37 (10)
5.26 (10)
152.99 (10)
143.60 (10)
8
3152.57 (1)
3209.54 (5)
1226.88 (10)
10.29 (10)
954.46 (10)
444.17 (10)
12.21 (10)
2150.27 (10)
717.75 (10)
30
40.54 (10)
3335. 14 (10)
50
76.83 (10)
5276.93 (10)
70
105.70 (10)
6059.57 (7)
Random LCNs. We generated three classes of random LCNs with propositions {XI,... X, and sentences of the following types: (a) S P(x;) S u, (b) S P(æ,(z;) S u, + and (c) I S [X A Xx) I i + j o ki such that the corresponding primal graph is polytree, dag or a random graph. The type (c) sentences were generated for all truth values of propositions X, and Xg, namely ((z,(ı,), [x,), P(x))~w,), P(zlzz A z&), P(z|/zz A -. P(z ((zy-zz, A x&) and P(z A ~Zx), respectively. The probability bounds / and u were selected uniformly at random between and such that I 0.6, and ensured that all instances with 10 consistent.
Table summarizes the results obtained for maximax MAP queries on the random LCNs. For each problem class we consider both smaller (5 S 10) and larger (30 S n S 70) scale instances, respectively. We report the average CPU time in seconds and num- ber of problem instance solved (out of 10) for each problem size. '-' indicates that the respective algorithm exceeded the 2 hour time limit. The maximum discrepancy value by algorithms LDS and ALDS was to 8 = 3, while algorithms SA and ASA used up to 30 flips over single iteration. We can see that the algorithms using exact MAP assignment evaluations (i.e., DFS, LDS and SA) are limited to small scale problem in- stances with up to 8 propositions and they run out of time on the larger instances. This is caused by the prohibitively large computational overhead associated with the exact evaluation of the MAP assignments during search. In contrast, the approximate search algorithms ALDS and specially ASA can scale to much larger problem instances due to the less expensive approximate MAP assignment evaluations. A.MAP. the best performing algorithm in terms of running time and number of problems solved for all reported problem sizes. However, since the solution found by AMAP is only a local maxima, the solution quality found by algorithms AMAP, ALDS and ASA on LCN instances of size 10. Specifically, we show the number of wins as the number of times (out of 10) each algorithm found the best solution. In this case, algorithms ALDS and ASA were initialized with the MAP assignment
Nodin
Figure 2: Wins for LCNs with 10.
Figure we report on

---

Figure 3: Average CPU time in seconds and standard deviation vs discrepancy 8 for AL)
Table 2: Results for MMAP tasks realistic LCNs. CPU time in seconds. Time limit is 2 hours.
LCN
exact MAP
approx MAP
DFS
LDS(3)
SA
AMAP
ALDS(3)
ASA
Toy
2.20
3.18
1.85
0.85
134.83
141.17
Earth
9.19
7.67
2.75
1.28
150.99
162.35
Cancer
16.34
14.09
8.52
2.64
157.92
159.66
Asia
811.82
800.18
312.10
4.07
187.44
201.76
Credit
6719.30
2976.55
5.09
204.77
222.52
Engine
4786.12 12
4502.34
2033.77
6.57
212.61
235.70
Suicide
5.99
220.31
203.68
Tank
8.04
263.65
281.73
Alarm
4.28
216.19
186.67
Hepatitis
8.22
260.38
250.45
found by AMAP. We that almost always the search-based approaches ALDS and ASA able to find better solutions than AMAP. This is important in practice, particularly on larger scale problems where solution using a search-base algorithm like ALDS or ASA if the time budget allows it. Finally, in Figure we show the impact of the maximum discrepancy value ō on the running time of algorithm ALDS(O). It is easy to see that as the discrepancy value increases, the search space explored by ALDS(0) becomes larger, and therefore its corresponding running time increases as well.
can use AMAP to find a MAP solution quickly, and subsequently refine that
Realistic LCNs. We experimented with set of more realistic LCNs which were first introduced in [8]. These LCNs were derived from real-world Bayesian networks (3] and contain up to 10 propositions as well up to 24 sentences of the form / < P(x;) u and respectively, where v; the positive literal of proposition X; and m; = Yi A A... Yiu is the conjunction of the positive parents (Ya,... } X; in the Bayesian network. The specification of these LCNs is included in the supplementary material. Table 2 reports the results obtained on 10 LCN instances for the maximax MMAP task with 4 MAP propositions selected randomly. As before, algorithmss DFS, LDS(3) and SA which rely on exact evaluations of the MAP assignments during search can only solve the smallest problem instances within the 2 hour time limit. In contrast, algorithms A ALDS(() and ASA solve all problem instances due to much reduced overhead associated with the approximate MAP assignment evaluations. In this case, the search spaces explored by ALDS(3) and ASA approximately the same in size and therefore the corresponding running times are comparable. AMAP is the fastest algorithm in this case as well.
P(z)(T)) S
negative literals corresponding to particular configuration of the
Application to Factuality in Large Language Models. We consider an application of MMAP inference in LCNs to assess the factuality of the output A generated by a large language model (LLM) in response may contain contradicting factual information (e.g., Wikipedia) 224.. The goal is to compute factuality score for response A, denoted by fc) in the context of the information from C. In the following, we assume that A can be decomposed into a set of n atomic facts (or just atoms) = (Ai,-- A.)) (e.g., one way to that is to split into sentences) and, for each atom A,, up to k relevant passages (Ca,..., Ca.) called contexts can be retrieved from C. A natural language inference (NI.I) classifier such as SBERT 25 can be used to infer the entailment, contradiction and neutrality relationships between the texts corresponding to the atoms and contexts together
user query Q with respect to an external source of knowledge C' that

---

Table 3: Results for factuality LCNs. Average CPU time in seconds and number of problem instances solved. Time limit is 2 hours.
size
exact MAP eval
approx MAP eval ALDS(2)
T1, k = 2
DFS
LDS(2)
SA
AMAP
ASA
2
56.95
(10)
57.37 (10)
60.09 (TO)
0.31 (10)
5.25 (10)
4.13(10)
4
0.98 (10)
80.07 (10)
54.15(10)
6
1.97 (10)
453.88 (10)
219.57 (10)
7.33 (10)
2713.90 (10)
928.28 (10)
20
28.42 (10)
3809.23 (10)
50
379.18 (10)
100
1807. (10)
with their corresponding probabilities (or scores). Specifically, we consider relationships between an atom and context r(A,, Ci²). and between two contexts r(Cij. Cpg), respectively. where e fentailment, contradiction). We define an LCN L containing n + n x l propositions for each of the atoms and contexts, and two types of sentences corresponding to the entailment and contradiction relationships as follows: < X(Y]X) S u if X entails Y, and S P(-YIX) S u if X contradicts Y, where X and Y are the propositions corresponding to a context and an atom, or to two different contexts, respectively. The lower and upper bounds / and can be calculated easily from the probabilities obtained by running multiple NLI classifiers. Finally, the factuality score fc(A) is the proportion of true atoms in the MAP assignment obtained by solving maximax MMAP task over where the MAP propositions are those corresponding to A's atoms.
Table displays the results obtained on randomly generated factuality LCNs. More specifically, for each reported problem size n E {2, 4, 6, 10, 20, 50, 100). we generated 10 random instances with atoms and k = 2 contexts per atom such that 10% of all possible pairwise relationships between atoms and contexts were selected to be either entailment or contradiction with probability 0.5 while the remaining relationships were labeled neutral and thus ignored. The lower and upper probability bounds and u in the corresponding LCN sentences were also generated randomly between O and I such that / < 0.6. In this case, the maximum discrepancy value was set to 2 and simulated annealing was allowed single iteration and 30 flips. We observe again that algorithms DFS, (2) and SA can only solve the smallest instances due to large computational overhead associated with exact evaluation of the MAP assignments. In contrast, algorithms ALDS(2) and ASA which rely on less expensive approximate evaluations of the MAP assignments can scale to larger problems with up to 20 atoms. Algorithm AMAP outperforms its competitors and solves all problem instances.
In summary, our empirical evaluation showed that the exact search-based MAP/MMAP algorithms are limited to solving relatively small problem instances. contrast, the approximate MAP/MMAP schemes based on either message-passing or search can scale to much larger L.CN instances.
Conclusions
In this paper, we address abductive reasoning tasks such generating MAP and Marginal MAP (MMAP) explanations in Logical Credal Networks (LCNs), a recently introduced probabilistic logic framework for reasoning with imprecise knowledge. Since an LCN encodes set of distributions over its interpretations, a complete or partial explanation of the evidence (i.e., a MAP assignment) may correspond to more than one distribution. Therefore, we define the maximin/maximal MAP and MMAP tasks for LCNS as finding complete or partial MAP assignments that have maximum lower/upper probability given the evidence. We propose several search algorithms that combine depth- first search, Limited-discrepane assignments using marginal inference for LCNs. We also develop an approximate message-passinng scheme as well as extend limited discrepancy search and simulated annealing to use an approximate evaluation of the MAP assignments during search. Our experiments with random LCNs and LCNs derived from realistic use-cases demonstrate conclusively that the search methods based on exact evaluations the MAP assignments are limited to small size problems, while the approximation schemes can scale to much larger problems. For future work we plan to investigate more advanced depth-first branch-and-bouut and best-first search techniques. However, these kinds of methods require developing novel heuristic bounding schemes to guide the search more effectively (16).
search or simulated annealing with exact evaluations of the MAP
10

---

Acknowledgements
Fabio Cozman thanks CNPq (grant 305753/2022-3) and the Center for Al Universidade de São Paulo, funded by FAPESP (grant 2019/07665 and IBM.
References
[1] Nils Nilsson. Probabilistic logic. Artificial Intelligence, 28(1):71-87, 1986.
[2] Ronald Fagin, Joseph Halpern, and Nimrod Megiddo. A logic for reasoning about probabilities. Information and Computation, 87(1-2):78-128, 1990.
[3] Jochen Heinsohn. Probabilistic description logics. Proceedings of the International Confer- Uncertainty in Artificial Intelligence, pages 311-318, 1994.
[4] Manfred Jaeger. Probabilistic reasoning in terminological logics. In Principles of Knowledge Representation and Reasoning, pages 305-316. Elsevier, 1994.
[5] Kent Andersen and John Hooker. Bayesian logic. Decision Support Systems, 11(2):191-210, 1994.
[6] Vijay Chandru and John Hooker. Optimization Methods for Logical Inference. John Wiley & Sons, 1999.
[7] Michael Dürig and Thomas Studer. Probabilistic abox reasoning: Preliminary results, In Description Logics, pages
[8] Matthew Richardson and Pedro Domingos. Markov logic networks. Machine Learning, 62(1- 2):107-, 2006.
[9] Lise Getoor and Ben Taskar. Introduction to Statistical Relational Learning (Adaptive Compu- tation and Machine Learning). MIT Press, 2007.
[10] Lue De Raedt, Paolo Frasconi, Kristian Kersting, and Stephen Muggleton. Probabilistic Inductive Logic Programming Theory and Applications. Springer, 2008
[11] Radu Marinescu, Haifeng Qian, Alexander Gray, Debarun Bhattachariya, Francisco Barahona, Tian Gao, Ryan Riegel, and Pravinda Sahu. Logical credal networks. 36th Conference on Neural Information Processing Systems (NeurIPS), 2022.
[12] Judea Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, 1988.
[13] Daphne Koller and Nir Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT Press, 2009.
[14] Radu Marinescu and Rina Dechter. AND/OR branch-and-boume search for combinatorial optimization in graphical models. Artificial Intelligence, 173(11-11)11457-149,, 2009.
[15] Radu Marinescu and Rina Dechter. Memory intensive AND/OR search for combinatorial optimization in graphical models. Artificial Intelligence,
2009.
[16] Radu Marinescu, Junkyu Lee, Rina Dechter, and Alexander Ihler. AND/OR search for marginal MAP. Journal or Artificial Intelligence Research (JAIR), 63(1):875 921, 2018.
[17] Radu Marinescu, Debarun Bhattachariya, Junkyu Lee, Alexander Gray, and Fabio Cozman. Credal marginal map. In 37th Conference on Neural Information Processing Systems (NeurIPS), 2023.
[18] Radu Marinescu, Haifeng Qian, Alexander Gray, Debarun Bhattacharjya, Francisco Barahona. Tian Gao, and Ryan Riegel. Approximate inference in logical credal networks. In 32nd International Joint Conference Artificial Intelligence (IJCAI), 2023.
[19] William Harvey and Matthew Ginsberg. Limited discrepancy search. International Joint Conference Artificial Intelligence (IJCAI), pages 607-613, 1995.

---

[20] Richard Korf. Improved limited discrepancy search. In AAAI Conference on Artificial Intelli- gence (AAAI), pages 286-291, 1996.
[21] Scott Kirkpatrick, Daniel Gelatt, and Mario Vecchi. Optimization by simulated annealing. Science, 220:671-680 1983.
[22] Andreas Wächter and Lorenz Biegler. On the implementation of interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming, 106(1):25-57, 2006.
[23] Anthony Constantinou, Yang Liu, Kiattikun Chobtham, Zhigao Guo, and Neville Kitson. The bayesys data and bayesian network repository. Technical report, Bayesian Artificial Intelligence research lab, Queen Mary University of London, London, UK, 2020.
[24] Sewon Min, Kalpesh Krishna, Xinxi Lyu, Mike Lewis, Wen-tau Yih, Pang Koh, Mohit lyyer, Luke Zettlemoyer, and Hannaneh Hajishirzi. FActScore: Fine-grained atomic evaluation of factual precision in long form text generation. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 12076-12100, 2023.
[25] Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert- networks. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing, pages 3973-3983. 2019.
12

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] [NA]-
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked use checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No] is perfectly acceptable to answer "[No] providee proper justification is given (c.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA] is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
.
Do not modify the questions and only use the provided macros for your answers.
1.
Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: Sections 3 and 4
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
13

---

Justification: Section 3, 4 and 5. Essentially the exact inference methods proposed in this paper are limited small size problems with up 8 propositions/variabl while the proposed approximate inference methods can scale to much larger problems with tens and even hundreds of variables.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well vell-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
Section
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Section 4 and supplementary material
14

---

Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel urchitecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
Section 4 and supplementary material
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https:/nipss.c//publcc guiides/CodeSubmissioooooo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https) httpps.c/public/uuude/CCCC Sowpiiddeeeooeebbbbmioooooloel for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
15

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Section 4 and the supplementary material
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Section and the supplementary material
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Section 4
Guidelines:
The answer NA means that the paper does not include experiments.
16

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:://beriiss.cccppph//ttiiiie
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
17

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Section
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If asseets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode, wtt.:wwwwwoo...w/atteeeeeeeeeeee com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
Section
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
18

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
19


Reviews:
[{"review_id": "589K5Bkafy", "reviewer": "Reviewer_NnQo", "summary": "Logical Credal Networks (LCNs) are a probabilistic logic framework designed for representing and reasoning with imprecise knowledge. While previous research on LCNs has focused on marginal inference, there has been a lack of exploration in abductive reasoning within this context. This paper addresses this gap by investigating abductive reasoning in LCNs using Maximum A Posteriori (MAP) and Marginal MAP (MMAP) queries. To solve MAP and MMAP tasks, the authors propose techniques based on Depth-First Search (DFS), Limited Discrepancy Search (LDS), and Simulated Annealing (SA). Additionally, to improve time complexity, they introduce a method that utilizes a message-passing approximation scheme, allowing for more efficient and scalable solutions.", "questions": "- Could you provide more detailed descriptions of the algorithm implementation? Additionally, could you include a clear analysis of the time and space complexity of the algorithms to help evaluate their efficiency? I recommend this paper should answer these questions in the Appendix. (Could be in the supplementary material)\n- Could you include baselines comparing the performance of the proposed algorithms with those of existing studies? Without such baselines, it is challenging to determine whether your algorithms are superior to existing research.\n- Could you clarify the specific advantages of ALDS and ASA over AMAP, and provide additional justification for their inclusion? How do these algorithms contribute to this paper?", "limitations": "- As the authors mentioned, the method still relies on heuristic approaches for finding MAP, indicating a need for further development. The proposed method is not yet practical for real-world applications without additional improvements, as evidenced by the computational overhead and limited scalability shown in the experiments.\n- Arbitrary Setting of Hyperparameter Values: \n   * Size of problem (n): Figure 3 shows a trend where CPU time increases as the discrepancy increases for n = 7. However, Table 1 shows experiments conducted for n = 5, 8, 10, 30, 50, 70 for the same datasets. It is unclear why only Figure 3 uses other values, indicating an arbitrary setting of hyperparameters without a specific criterion. \n   * Discrepancy (delta): Table 1 and Table 2 use a discrepancy value of 3, whereas Table 3 uses a discrepancy value of 2 for the experiments. The rationale behind these hyperparameter settings needs to be clarified. Setting discrepancy values without a consistent criterion undermines the study's consistency and can confuse interpreting the results. Furthermore, a discrepancy of 2 appears to be an elbow point, suggesting it is an optimal parameter value for ALDS(2). Maybe, results for the large data(n = 30, 50, 70) could have been obtained using ALDS(2).\n   * Contexts per atom (k): In Table 3, since k is fixed to 2, you don't have to indicate repeatedly it in the table. Also, it would be better to append the results of experiments with various k.\n- Uncertain Contribution: While this paper proposes various algorithms based on LCN, it is questionable whether the introduction of LCN is necessary for solving Marginal MAP. I summarize the points previously mentioned from this perspective. Firstly, in the performance of the approximation algorithms, it is evident that AMAP, which relatively fails to find the optimal LCN, performs better. This result weakens the necessity of LCN to solve the marginal MAP problem. Additionally, it is difficult to prove the superiority of LCN without a theoretical comparison (e.g., time complexity, space complexity) or experimental comparison (i.e., experimental results) between LCN-based algorithms and existing algorithms. To prove the contributions of this paper, it seems necessary to supplement these aspects.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper introduces a novel method for computing MAP and MMAP in Logical Credal Networks (LCNs), which were not previously addressed in this context. It proposes a more efficient search method compared to the brute force approach for MAP calculation.\n- Unlike previous studies, this research reduces complexity by using an approximation method to address time complexity.\n- This approach is theoretically well-proven and demonstrated through experimental results.\n- By adding a simple method called Message Parsing Approximation to LDS and SA, performance was effectively enhanced.\n- The practical application of the algorithm is shown, proving its usefulness and suggesting future development directions.\n- Since this paper shows that LCN's knowledge expression is better than other existing research, many follow-up studies using LCN could be conducted.", "weaknesses": "Comparison with prior work & Experiments\n- Mention how you build upon from the previous works by Radu Marinescu et al. The introduction mentions that existing approaches use heuristic algorithms or DP algorithms for MAP and MMAP inference, and this paper does not employ a significantly different method.\n- If this is a follow-up to the aforementioned research, wouldn't it have been better to demonstrate the performance of the previous research with the addition of Message Passing Approximation? The current paper compares the method added to LDS and SA. The advantages of using SA and LDS compared to previous research are not clearly demonstrated.\n- While I agree that there may not be existing studies that have introduced LCNs, there are certainly prior studies that have tackled MAP and Marginal MAP tasks. It would be beneficial to include baselines comparing the performance of the proposed algorithms with those of existing studies. Without such baselines, the current experimental results only allow for comparisons among the proposed algorithms themselves, making it difficult to ascertain whether these algorithms are superior to those from other research. The absence of baseline comparisons hampers a complete understanding of the contribution of the proposed methods.\n- A comparison and introduction of MAP estimation methods in Credal Networks (CN) and Bayesian Networks (BN) would have been beneficial to understand the practical advantages over these existing methods. (Probably author thought this was the scope of the prior work - Logical Credal Network)\n- It is unclear whether ALDS and ASA are needed instead of AMAP. Experimental results show that AMAP consistently outperforms in terms of CPU time(in Tables 1, 2, 3), and the auxiliary measure of solved problem instances(in Tables 1, 3) is always 10/10 with AMAP. These results raise questions about the necessity of ALDS and ASA. Although the paper attempts to address these concerns with Figure 2, but it demonstrates that sufficient problem-solving can be achieved without the optimal LCN, suggesting that the approximation methods of ALDS and ASA may be inefficient.\n\nPresentation\n- There is insufficient evidence for the statement in LINE 24: \"Logical Credal Networks (LCNs) have focused exclusively on marginal inference, i.e., efficiently computing posterior lower and upper probability bounds on a query formula.\"\n- The main contribution seems to be Algorithm 4, but its emphasis is not different from Algorithms 1-3, which perform inference through DFS, making it difficult to identify the core of the paper.\n- Line 36: Is the term \"probability bound\" more accurate than \"imprecise probability.\"?\n- Section 3 lack sufficient explanation of the proposed methodology, making it difficult for readers to fully understand. Additionally, the paper lacks a clear analysis of the time complexity and space complexity of the algorithms, which is crucial for evaluating their efficiency.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback. We provide responses to your questions and concerns below.\n\nThe MAP and MMAP inference tasks have been extensively studied over the past decades in the context of classical graphical models such as Bayesian networks or Markov networks. However, algorithms developed for those models such as variable elimination or depth-first AND/OR branch and bound are not directly applicable to LCNs and therefore a direct comparison with those kinds of methods is not possible. For example, the AND/OR search algorithms for MMAP in Bayes nets presented in [Marinescu et al, JAIR-2018] are guided by a heuristic function derived from a variational bound on MMAP in Bayes nets. That bound cannot be computed in an LCN and therefore the AND/OR search algorithms mentioned simply do not work on LCNs.\n\nPrevious papers on LCN have only focused on exact and approximate algorithms for computing upper and lower probability bounds on a query formula (also known as marginal inference). Virtually nothing is known about MAP and MMAP inference in LCNs. Therefore, the contribution of our paper is to bridge this gap and present the first ever exact and approximate algorithms for solving MAP and MMAP queries in LCNs.\n\nRegarding the experiments, in Tables 1, 2 and 3 we chose a discrepancy value such that the search space explored by LDS/ALDS would have a comparable size to that of SA/ASA. However, we experimented with many more discrepancy values (up to 7) but observed that a larger discrepancy value has a negative impact on running time and we illustrate this behavior with Figure 3.\n\nQ1: We included the actual Python implementation of the proposed algorithms in the supplementary material (see the exact_map.py and approx_map.py scripts) and we are currently in the process of open sourcing our code. Theorems 1, 2, 3 and 4 in the main paper provide the time and space complexity bounds of the proposed algorithms. Their proofs are included in the supplementary material.\n\nQ2: To the best of our knowledge, our paper provides the first study on MAP and MMAP inference in LCNs and therefore there are no other baseline algorithms to compare with on these two tasks.\n\nQ3: Algorithms ALDS and ASA could potentially improve the solution found by AMAP. More specifically, the initial solution found by AMAP is most likely a local optima, but if more time is available then we can use ALDS/ASA to search for a better solution. Figure 2 in the main paper is meant to illustrate the benefit of using ALDS/ASA on top of AMAP. In this case, both ALDS and ASA were initialized with the solution found by AMAP and the plot shows how many times ALDS/ASA found a better solution compared with the initial one upon exceeding the time limit. We will expand the discussion in the paper to emphasize the benefits of ALDS/ASA over AMAP.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rHcHnhPQsn", "reviewer": "Reviewer_AMr2", "summary": "The paper presents an approach for MAP and marginal MAP in logical credal networks using search based algorithms. Compared to PGMs, MAP and marginal MAP is harder in LCNs since a MAP assignment could correspond to one of several distributions and therefore, to even evaluate the MAP, we need to perform marginalization which is a hard task. The exact algorithms are developed using DFS, limited discrepancy search and simulated annealing. However, since these are infeasible in practice, approximate methods are developed based on a marginal inference method for LCNs. The main idea is to compute lower and upper MAP (or marginal MAP) probabilities \n\nExperiments are performed on synthetic LCNs and those generated from Bayesian nets. Further, an application related to testing LLMs is presented. Specifically, the idea is to connect atoms from the generated text to a source such as wikipedia and compute facility as a the MAP score. Scalability results are shown for the LCNs used in this task for different variants of the proposed methods.", "questions": "Are there specific use cases where the MAP or MMAP solutions for LCNs can be compared with other competing methods? In general, what would be the advantages of MAP/MMAP queries for LCNs as compared to other probabilistic approaches.", "limitations": "Limitations are not explicitly mentioned.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- A novel class of inference queries added to LCNs can improve the applicability of LCNs in different applications. \n- The paper develops a comprehensive suite of MAP and MMAP exact and approximate inference algorithms for LCNs\n- Results show that the proposed algorithms can scale up and find approximate MAP/MMAP solutions", "weaknesses": "In terms of significance of the proposed approaches, the results mainly show scalability of the approximate methods and their ability to find MAP/MMAP solutions. However, the actual application of MAP/MMAP seems missing. For example, in the LLM application the results do not really tell us how useful the MAP/MMAP solution was compared to other methods other than that the MAP/MMAP solution could be found as the LCN becomes larger. In general, I feel the proposed approaches would be much more significant if the results showed that if the proposed solution improved over other approaches that could be used to solve the same problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback. We provide responses to your questions below.\n\nTo the best of our knowledge, this paper provides the first study dedicated to MAP and MMAP inference in LCNs and therefore, there are no other baseline algorithms for solving MAP/MMAP queries in LCNs to compare with. In general, LCNs offer several advantages over existing models, namely they allow specifying probability bounds on logic formulae, do not require acyclicity, and are far more flexible to specify logic formulae compared with existing logic programming approaches. \n\nMAP/MMAP queries for LCNs provide a principled way to generate most probable (partial) explanations for these kinds of models. For example, inferring the code in the uncertain Mastermind puzzles introduced in a previous paper on LCNs can be solved as a MMAP query and as shown previously the most effective way to solve it is by modelling the problem as an LCN rather than using existing approaches based on Bayes nets, Problog or MLN.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QSojqVBqXp", "reviewer": "Reviewer_Pbqt", "summary": "This is a paper about inference on logical credal networks, a class of graphical models that cope with interval-valued probabilistic statements on propositional logic formulae. The novelty of the paper is that it focuses on marginal MAP inference (and hence also MAP as a special case). Exact and approximate algorithms based on search strategies are proposed and empirically tested.", "questions": "- The authors do not report results on the hardness of their inference tasks. This is probably obvious, right? Yet, some comments about that would help. It would be also interesting to compare a brute-force wrt the exact methods.\n- With credal models, there is a difference between the \"conditional\" and the \"joint\" versions of an inference task for the simple reason that the two models are proportional through the probability of the evidence, which is not constant in a credal setup. I believe that the authors consider a \"joint\" version, but this point should be made clearer.\n- I don't understand how the ground-truth values in the experiments are obtained.\n- The results show that the topology of the networks seems not to affect the execution time too much. Some comments about that would be valuable, as the situation is very different in other graphical models.", "limitations": "-", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main contribution is an approximate procedure based on recent work on marginal inference in the same class of models. This procedure seems to perform well on models for which exact algorithms are too slow. The extension from marginal inference to marginal MAP is non-trivial. \n\nThe experiments are extensive and the results convincing.", "weaknesses": "LCNs are not very popular models, at least for the moment, and their potential for applications to real problems is not very clear.\nSomething similar could be said, more specifically, to the need for tools for abductive reasoning in such models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback. We provide responses to your questions below.\n\nQ1: The hardness of MAP/MMAP inference in LCN isn’t actually known yet. We suspect it is an NP^NP^PP-hard task but proving this result formally is an open problem. We will include a discussion of this issue. The DFS algorithm described in the paper (Algorithm 1) is a brute-force algorithm (i.e., the MAP assignments are enumerated exhaustively and each one is evaluated exactly) so we do include results with such a brute-force approach.\n\nQ2: Yes, the MAP/MMAP tasks defined in this paper can be viewed as “joint” inference tasks. They find a truth assignment to the MAP propositions and the evidence propositions can be viewed as part of that assignment. We will clarify this in the paper.\n\nQ3: We are not clear what the reviewer means by “ground-truth values”. If they refer to the exact MAP/MMAP solutions, we do obtain them with the DFS algorithm which is an exact algorithm but only on the smallest problem instances due to the scalability issues discussed in the paper. However, if they refer to the probability values in the problem instances considered, we actually generated those values randomly as described in the experimental section (and also in the supplementary material).\n\nQ4: That is correct. The algorithms proposed in this paper do not exploit the graph structure as commonly done in variational inference in graphical models. Understanding the factorization of the LCN is an open research problem. Recently, [Cozman et al, 2024] investigated Markov conditions and factorization in LCNs which could be used in principle to develop more efficient algorithms for LCNs. This ambitious endeavour is also part of our research agenda.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "M5WXVFjD6z", "reviewer": "Reviewer_56vh", "summary": "This paper proposes how to solve MAP and Marginal MAP queries for Logical Credal Networks (LCNs). LCNs are a class of graphical probabilistic logic models with the expressiveness to represent cycles as well as marginal and conditional probability bounds on logical formulae. The authors first present three search algorithms for exactly computing MAP/MMAP bounds on queries to LCNs. Then, because the MAP/MMAP problem for LCNs is NP-Hard, the authors present three approximation methods that offer considerable speedup at only a small cost to accuracy. The supplemental material contains formal proofs and extensive experiment details.", "questions": "* The space complexities appear quite extreme. Could the authors please comment on whether this is a fundamental drawback, and if so, how much better might one (in practice) reasonably expect to do?\n* Figure 3 in the paper looks different from Figure 6 in the supplemental material. Could the authors please address why this might be the case?\n\n\nI have saved my harshest critiques for last. I am an outsider to the graphical models community, so please forgive my ignorance. I am willing to revise my assessment if the authors could please expand on the following points that a general ML audience might have:\n* Why care about LCNs?\n* What are real-world cases of people using LCNs or similar models?\n* What's an example of something that LCNs can capture that other graphical models can't?\n* In fact, why care about graphical models at all when deep learning is everywhere? (Some comments about explainability + interpretability should be well-received)\n* If the existing algorithms for LCNs are so expensive, what would be some \"realistic\" scenarios for which they're relevant?", "limitations": "The authors sufficiently discuss the limitations of their work.", "rating": 5, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "The authors do a good job of comprehensively studying the problem of MAP/MMAP inference for LCNs. Consequently, this paper is relevant and useful for researchers and practitioners interested in graphical probabilistic logic models. In particular:\n* The authors present a variety of different algorithms for MAP/MMAP on LCNs and theoretically prove their correctness and complexity.\n* The approximation algorithms presented offer considerable speedup while achieving competitive performance with the exact solutions.\n* The six algorithms (three exact + three approximate) offer good coverage of what a user of LCNs may consider.", "weaknesses": "My primary critique is on the exposition and motivation.\n* It would help to better motivate the strengths of LCNs by providing examples/references of why cycles and marginal+conditional probabilities show up. This would be stronger than claiming \"... which may be important in many realistic use cases\".\n* Having more examples and figures of LCNs would be helpful, especially in Section 2.1.\n* Emphasizing the NP-Hardness of MAP/MMAP for LCNs would help better motivate the need for search techniques and approximation algorithms.\n* Section 2.2 is a bit dense. Moreover, it appears that Equation (8) is a vector-valued objective, which does not make sense to me. Overall, this section would benefit from a more relaxed exposition pace --- possibly in a future manuscript version.\n\nThe experiments would also benefit from having the main takeaways more explicitly stated.\n* It would help to have captions that succinctly explain the main points, e.g., for Table 1: that AMAP does very well compared to DFS, LDS(3), and SA.\n* It would be useful to supplement Figure 2 with a plot of the optimality gaps of the approximations, rather than simply the \"wins\".\n\nOthers comments:\n* At present, it appears that the practical algorithms are restricted to fairly small LCNs.\n* Three exact algorithms and three approximation schemes in one paper are quite a lot. It would help the reader to see the author's recommendations and discussions of their various trade-offs.\n* The part on \"Application to Facuality in Large Language Models\" is a bit dense and sudden. If the authors deem it within the scope of the paper, it would help to supplement this with some experiments.\n\nMinor Comments:\n* Section 3.2: It would be helpful to explicitly list Algorithm 1, 2, and 3 in the paragraph headers, e.g., \"Algorithm 1: Depth-first Search\"\n* More descriptive names for theorem labels would be helpful, e.g. \"Theorem 1 (Complexity of Depth-first Search)\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback. We provide responses to your questions and concerns below.\n\nWe will expand the background section to include more examples of LCNs. For now, we refer the reader to the previous work on LCNs which we cite in the paper. We agree that Section 2.2 is quite dense at the moment and we will use additional space to add more details as well as a small running example. The hardness of inference in LCNs is not actually known yet. We suspect it belongs to the NP^NP^PP-hard class but proving the result formally is an open problem. We will include a short discussion to emphasize this issue. Finally, we will follow up on your suggestion and summarize the findings of our empirical evaluation in a separate subsection.\n\nQ1: Regarding space complexity, yes, in the worst case we need to represent in memory a probability distribution over an exponentially large number of interpretations. This is a serious limitation, especially for exact algorithms. For example, in practice, our approximate scheme AMAP can handle LCN instances whose factor graph contains factor nodes involving up to 10-12 propositions.\n\nQ2: Figure 3 in the main paper plots results with algorithm ALDS and is the same as Figure 5 in supplementary material (although there is a typo in its caption), while Figure 6 in supplementary material contains results with algorithm LDS.\n\nQ4: Previous work on LCNs has already showcased several potential applications of LCNs including one from the chemistry domain. In this paper, we illustrate a potential application to factuality assessment for LLMs. Furthermore, [Cozman et al, 2024] has shown recently that LCNs can be used to model and solve causal reasoning tasks such as estimating the causal effect of an intervention under partial identifiability conditions.\n\nQ3&Q5: LCNs allow specifying conditional probability bounds on logic formulae and allow directed cycles. Previous work on LCNs demonstrated that this is very useful especially when we need to combine multiple sources of imprecise knowledge in a single model. In contrast, graphical models like Bayes nets do not allow cycles nor bounds on probability values, credal networks allow probability bounds but require acyclicity. Probabilistic logics like Problog and MLNs allow undirected cycles but require point probability values. Therefore, LCNs can be viewed as a generalization of these previous models.\n\nQ6: Graphical models are inherently interpretable models and can be used to provide explanations in a principled manner. They have been studied extensively over the past decades and there is substantial literature illustrating non-trivial applications to real-world situations.\n\nQ7: We show that exact inference for LCNs is expensive while approximation schemes are far more scalable. These approximate algorithms are clearly applicable to the potential realistic applications presented in previous papers on LCNs (please see also our answer to Q4).\n\nWe thank the reviewer again for their detailed feedback and thoughts. If the reviewer believes we have addressed some of their concerns, we request them to consider increasing their score.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OkfTKdtv1D", "reviewer": "Reviewer_ZTSx", "summary": "This paper addresses abductive reasoning tasks such as generating MAP and Marginal MAP (MMAP) explanations in Logical Credal Networks (LCNs). Given that LCNs encode sets of distributions over their interpretations, a complete or partial explanation of the evidence may correspond to multiple distributions. Thus, the authors define the maximin/maximax MAP and MMAP tasks for LCNs as finding complete or partial MAP assignments with maximum lower/upper probability given the evidence. They propose several search algorithms that combine depth-first search, limited-discrepancy search, or simulated annealing with exact evaluations of MAP assignments using marginal inference for LCNs. Additionally, they develop an approximate message-passing scheme and extend limited discrepancy search and simulated annealing to use approximate evaluations of MAP assignments during the search. Experiments show that the approximation schemes which they have proposed can scale to much larger problems compared to search methods.", "questions": "1. In the initial LCN papers, the authors compared LCN with ProbLog and MLN. Can your method be compared with these? For example, ProbLog is a direct derivative of logic programming, which can perform basic reasoning, including deductive reasoning as well as abductive reasoning.\n2. In the experiments, different approximate algorithms show significant differences in solving time, despite having almost equivalent time complexity. How can this be explained?\n3. In line 80, should it be \"less likely\"?", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The research is very detailed, providing an excellent formalization of abductive reasoning in LCNs. This formalization addresses a significant gap in previous LCN research, where solving MAP was challenging, and developing corresponding algorithms is not a trivial extension. The authors list several algorithms for solving this and successfully implement and compare them in detail.\n2. The approximate algorithms proposed by the authors significantly improve both the solving time and the scale of solvable problems compared to previous search-based methods.", "weaknesses": "The experimental setup is relatively simple, lacking more practical industrial examples and relying more on basic toy experiments. Additionally, there is no comparison with other methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback. We provide responses to your questions and concerns below.\n\nWe would like to emphasize that our paper provides the first study dedicated to MAP and MMAP inference in LCNs and to the best of our knowledge there are no other baseline algorithms for solving these tasks in LCNs.\n\nQ1: Previous work on LCNs showed that the Problog/MLN formalisms cannot really be used to model the same benchmark problems that LCNs can model (for instance, Problog/MLN do not allow conditional probability bounds). Therefore, a direct comparison with these methods is not really possible on the benchmark problems we consider in our work.\n\nQ2: The discrepancies between LDS/SA and ALDS/ASA in terms of running times can be explained by the slightly different search spaces explored by the two classes of algorithms. LDS/ALDS explore up to 2^d nodes, where d is the discrepancy value, and every single assignment is evaluated from scratch. In contrast SA/ASA are limited to M=30 flips (i.e., assignments) in our experiments, but some of these assignments may be generated multiple times and, in this case, SA and ASA use caching, namely if the current MAP assignment was solved before, they retrieve its value from the cache, thus avoiding its re-evaluation. Therefore, SA/ASA are more efficient than LDS/ALDS and we demonstrate this in our experiments. Furthermore, the underlying ipopt solver we use to solve the non-linear programs corresponding to the conditioned subproblems often suffers from numerical precision issues and for some subproblems it may take longer to solve than for others, and consequently the order in which these conditioned subproblems are considers may impact the overall running time. We will discuss these aspects in more detail in the paper.\n\nQ3: Yes, it was supposed to be “less likely” – we will correct the typo, thanks for the catch.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all reviewers for their valuable feedback and thoughtful suggestions.

Since several reviewers have asked for more justification for the formalism, we would like to emphasize that LCNs offer a language to deal with many AI settings where probabilities and constraints interact and that they are meant to go beyond classical graphical models such as Bayesian networks and the like. For instance, LCNs offer a path to dealing with non-identifiability in causal reasoning as was recently shown by [Cozman et al, 2024]. Furthermore, LCNs can offer a path to uncertainty quantification where it is important to differentiate between epistemic and aleatoric uncertainties, something that is done often with probability bounds [Hullermeier et al, 2022]. Unlike existing graphical models (e.g, Bayes nets) and probabilistic logics (e.g., Problog, MLN), LCNs are more expressive allowing conditional probability bounds on logic formulae, do not require acyclicity restrictions, and in general are more flexible to specify logic formulae compared with existing formalisms. Previous work on LCNs has already showcased several applications that can be solved more efficiently when modeled as LCNs and where existing approaches based on graphical models like Bayes nets or on probabilistic logics like Problog and MLN fail. These applications include uncertain Mastermind puzzles, credit card fraud detection with imprecise domain expert knowledge, as well as an application from the chemistry domain involving a prediction task using imprecise domain expert knowledge and molecular fingerprinting data [Marinescu et al, 2022, 2023]. Clearly, identifying additional real-world applications for LCNs is an open problem and is also part of our ongoing research agenda.

References:

[Cozman et al, 2024] F. Cozman, R. Marinescu, J. Lee, A. Gray, R. Riegel, D. Bhattacharjya. Markov Conditions and Factorications in Logical Credal Networks. In International Journal of Approximate Reasoning (IJAR), vol. 172, 2024.

[Hullermeier et al, 2022] E. Hullermeier, S. Destercke, and M. Shaker. Quantification of Credal Uncertainty in Machine Learning: A Critical Analysis and Empirical Comparison. Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence (UAI), 2022.

Meta-review: In the family of probabilistic graphical models, logical credal networks (LCNs) have recently garnered attention for their ability to represent imprecise probabilities in a compact and intuitive way. Up to now, there has been limited exploration of queries for this model class. This paper aims to broaden the practical applications of LCNs by focusing on the widely used maximum a posteriori (MAP) and marginal MAP queries. After providing an overview of LCNs and their queries, the authors propose exact and approximate algorithms for MAP and marginal MAP inference. These algorithms are evaluated using both synthetic and real-world benchmarks.

All reviews for this paper are positive, ranging from borderline accept to accept. As acknowledged by reviewers, this paper provides the first approach to handle abductive reasoning (with MAP and marginal MAP) on logical credal networks. As the runtime (and space) complexity of exact inference algorithms is prohibitive, an important contribution of this paper is to focus on the empirical analysis of various approximation algorithms, including message-passing, limited discrepancy search, and simulated annealing. In summary, this paper paves the way for future research on abductive reasoning with imprecise graphical models.

While the main concerns of reviewers have been addressed in the fruitful discussions with authors, I highly recommend providing a light revision of the current manuscript to consider all reviewers' comments. Notably:
* Applicability: as several reviewers were skeptical about the practical interest of LCNs, the insightful global response provided by the authors should be incorporated into the paper.
* Complexity: the paper should include a discussion on the computational complexity of MAP (and marginal MAP) for LCNs in order to justify the use of approximation algorithms. I would suggest providing an NP^PP hardness result (even if, as suspected by the authors, the complexity class is even higher). By first taking a class of undirected or directed graphical models for which MAP is NP^PP hard and then explaining that this class can be transformed (in polynomial time and space) into an LCN, the hardness result should follow.
* Presentation: The paper, in its current state, is targeted to specialists in probabilistic graphical models. The too short introduction should be revised to motivate this study for a larger NeurIPS audience. Furthermore, in order to deal with the density of the paper, the authors’ suggestion to provide additional examples and use additional space would be welcome. Finally, even if the state-of-the-art methods for (M)MAP inference are dedicated to probabilistic models and cannot be trivially extended to credal models, this should be emphasized at the beginning of the experimental section.
Decision: Accept (poster)