Logical Credal Networks
Authors: Radu Marinescu
Haifeng Qian
Alexander G. Gray
Debarun Bhattacharjya
Francisco Barahona
Tian Gao
Ryan Riegel
Pravinda Sahu
Venue: NeurIPS 2022 Accept (2022)
Keywords: graphical models
probabilistic logic
knowledge representation
bayesian networks

Abstract: We introduce Logical Credal Networks (or LCNs for short) -- an expressive probabilistic logic that generalizes prior formalisms that combine logic and probability. Given imprecise information represented by probability bounds and conditional probability bounds on logic formulas, an LCN specifies a set of probability distributions over all its interpretations. Our approach allows propositional and first-order logic formulas with few restrictions, e.g., without requiring acyclicity. We also define a generalized Markov condition that allows us to identify implicit independence relations between atomic formulas. We evaluate our method on benchmark problems such as random networks, Mastermind games with uncertainty and credit card fraud detection. Our results show that the LCN outperforms existing approaches; its advantage lies in aggregating multiple sources of imprecise information.

Logical Credal Networks
Radu Marinescu
Haifeng Qian AWS Al Labs qi anh waw.aaa.aaaaooomm com
IBM Research
radu. mettum.arnnnscuee.. i.m. com
Alexander Gray
Debarun Bhattacharjya
Francisco Barahona IBM Research barahon ibm, com
IBM Research
IBM Research
alexander, graye 1bm com
debarunbêus iim com
Tian Gao
Ryan Riegel
Pravinda Sahu
IBM Research
IBM Research
IBM Consulting
tgaoous, iim. com
ryan.
ryan.riegen riegeieeeeiee aimmmmmm........... com
pravisah@ in. ibm. com
Abstract
We introduce Logical Credal Networks (or LCNs for short) an expressive proba- bilistic logic that generalizes prior formalisms that combine logic and probability. Given imprecise information represented by probability bounds and conditional probability bounds on logic formulas, LCN specifies set of probability distribu- tions over all its interpretations. Our approach allows propositional and first-order logic formulas with few restrictions, e.g.. without requiring acyclicity. We also de- fine a generalized Markov condition that allows us to identify implicit independence relations between atomic formulas. We evaluate lems such as random networks, Mastermind games with uncertainty and credit card fraud detection. Our results show that the LCN outperforms existing approaches; its advantage lies in aggregating multiple sources of imprecise information.
method benchmark prob-
1 Introduction
Graphical models provide powerful framework for reasoning about conditional dependency struc- tures over many variables. Bayesian networks [26 19), for example, rely on precise probabilistic information and, therefore, encode single distribution over the variables of interest, while credal networks and their variants 7 3, g 9.. which encode sets of probability distributions, are able to reason effectively with imprecise information represented by sets of probability values or intervals.
Many (if not all) real-world applications require efficient handling of uncertainty and compact representation of wide variety of knowledge. Indeed, complex concepts and relationships that typically comprise expert knowledge may be difficult to express graphical models but can be represented compactly using classical logic. Consequently, probabilistic logic which combines probability and logic in principled manner has emerged over the years as a unified framework to deal effectively with these complex domains 23 [2
[6]
5 [ 29 15] 27 28). While some of [7
these formalisms (e.g., 229 15 27) associate a single real value to the logical formulas to represent
the uncertainty around their truth values, others (e.g. 23 12 24 relax this requirement and allow specifying lower and upper probability bounds on logical formulas.
In practice, knowledge is typically imprecise and it is often the case that multiple sources of knowledge need combined effectively to improve the solution quality of the problem hand. For example, in practical credit card fraud detection application, it would be desirable to combine statistical model
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

P(b)) 0.1
P(e.) 0.2
0.1 S $02
0.1 P(e)
B
E
B
Plaglas 96) 0.1 P(a,lby
0.1 s P(aglep. () 52
s (()))b,)) 4))
A
A
P(olo))
ega))br,e)) = 0.8
0.1 P(o(o)) s
0.7 s P(ggb,, e,) 0.8
P(olo;) = 0.7
Plagla, 0.9
0.6 = P(sla,) s 0.7
0.8 s P(a e1) 0.9
P(melae) = 0.2 P(mala;)
0.1 ((mp)))) s 0.2 (mm)a))
M
Bayesian network
(b) Credal network
Figure 1: Examples of simple Bayesian and credal networks.
capturing the uncertainty around historical transaction data with probabilistic logic rules expressing imprecise expert knowledge about the domain in order to predict future fraudulent transactions more accurately. Existing formalisms such as 23 12 24 allow bounds on logic formulas to model imprecise knowledge. They also impose few restrictions on logic formulas for increased expressivity but lack independence declarations which typically leads to excessively wide posterior probability intervals the inference results and that may not be very useful for the decision maker.
Contribution: In this paper, we present Logical Credal Networks (LCN), new probabilistic logic model that allows probability bounds and conditional probability bounds on arbitrary propositional and first-order logic formulas without requiring acyclicity and other strong restrictions. In addition, we define a generalized Markov condition for LCNs that allows us to make some independence assumptions between the atoms occurring in the logic formulas. Specifically, this allows atomic formulas in LCN be treated as independent unless there information saying otherwise. The independence assumptions in LCNs mirror similar assumptions present in probabilistic databases where for example tuples are considered independent of each other unless certain constraints that encode correlation are violated [14
30 20). Furthermore, we show that even though LCNs allow cyclic dependencies between variables, our proposed Markov condition matches the Markov condition in Bayesian and credal networks for acyclic graphs. Subsequently, we describe an exact inference algorithm to compute lower and upper bounds on the posterior probability of a query formula (optionally, in the presence of evidence). We experiment with random LCNs well as with benchmark problems derived from Mastermind games with uncertainty and a realistic credit card fraud detection application. Our results quite promising and show that LCNs outperform significantly existing approaches, especially in terms of solution quality. In particular, the results highlight the ability of LCNs to effectively aggregate multiple sources of imprecise information.
The supplementary material includes additional technical details and examples.
2 Background
2.1 Bayesian and Credal Networks
Bayesian network (BN) 26 defined by a tuple (X, D. P, G),,, where X x= (X },) set of variables over multi-valued domains D (D,..... Dn). G is directed acyclic graph (DAG) over X as nodes, and (P.} where P, = P(X, (pxx))) are conditional probability distributions (CPDs) associated with each variable X, and its parents pa(X,) in G. The Bayesian network represents a joint probability over X, P(.
II P P(X.)pa(X.)).
Credal networks (CN) 6 3 extend Bayesian networks to deal with imprecise probabilities. More specifically, each variable X; and each configuration Tit of its parents pa(X,) in a credal network is associated with conditional credal set K (X; (pa(pp))) (X,) Tux) which is specified separately from all others and assumed to be closed and convex (e.g., probability intervals). The strong extension of a credal network is the convex hull of all joint distributions that satisfy the property that every variable strongly independent of its non-descessants conditional on its parents (
Example 1. Figures ((a) and I(b) show simple examples of Bayesian and credal networks defined over five binary variables together with their corresponding conditional probability tables and credal

---

sets, respectively. The lowercase letters denote the domain values the variables (e.g., A E {ao. a1)). In this case, the credal sets are given by closed probability intervals (e.g.. P(bb) E [0.1,0.2]) 0.2)).
2.2 Probabilistic Logics
Propositions are denoted by lowercase letters x, y, R,... and propositional literals (i.c., 2 - stand for z being True or I being False. A term is variable, a constant, or a function applied to terms. An atom (or atomic formula) is either a proposition or predicate p(tz..... .ty) of arity & where the t; are terms. A formula is built out of atoms using logical connectives -, V, and -, respectively. For simplicity, we assume that first-order logic (FOL) formulas are universally quantified.
A probabilistic logic is defined by set of logic formulas (1, ag) such that each formula q is annotated with a probability value 0g E [0, 1] representing the probability P(g) of q being true [23]. The semantics of this logic is the set of probability distributions over all interpretations such that P(a) = at The 0g values can be replaced with intervals to deal with imprecise probabilities. Given query formula f. common inference task is to compute lower and upper probability bounds on P(f), denoted by P(f)) and P(f), respectively.
[T
A major weakness of this probabilistic logic [23] (as well as more recent work on description logic 16 17 (2)) is the lack of a Markov condition: there are no independence relations that are implied by the probabilistic logic. Consider the following simple example:
0.3 < (x) S 0.7
0.3 SP (v) S 0.7
(1)
where r, y are atomic formulas. Computing the bounds on P(æ + y results in the interval [0, 1]
23 Indeed, there exists a joint distribution over xr y such that 4 is satisfied and that x @ y is
always False, and there exists another such that @ y is always T True. The inference result of [0. 1.
however, not informative for most purposes and often not the intention when one writes down (T) for an application. A more practical approach in this case is to assume that and are independent of each other unless there is information saying otherwise. With this independence assumption, solving
the original query P(æ + y) results in the interval [0.42, 0.58].
One way to allow for a Markov condition in probabilistic logic is constrain the logic formulas to specific structure such as Bayesian network [ or credal network with probability intervals 88 9 However, this representation comes with several restrictions: (1) the only non-atomic logic formulas allowed are AND over atomic formulas and negation of atomic formulas; (2) there must not be cyclic dependencies among atomic formulas; (3) an atomic formula must be specified by either marginal probability interval or by set of conditional probability intervals, and not both; (4) the conditions in the conditional probabilities must enumerate all possible interpretations of the parent variables we will refer to the last two requirements as the aieuss-assessment assumption. In practice, there is often knowledge that cannot be expressed by a simple AND. Furthermore, there could be multiple sources of information that, when aggregated, break the acyclicity or unique-aseessment requirements.
3 Logical Credal Networks
In this section, we introduce the Logical Credal Network (LCN)- new probabilistic logic designed to allow as few restrictions as possible on logic formulas when specifying probability bounds together with set of implied independence relations similar to those present in Bayesian and credal networks.
3.1 Syntax
An LCN is defined by set of probability sentences having one of the following two forms:
1 P (q) < Uq
(2)
1/rr P (q r) S Mglr
(3)
where q and r can be arbitrary propositional or FOL. formulas and 0 < 1, S Uq 1, 4/ir <
Uglr < 1. Each sentence is further associated with a Boolean parameter T E [True, False), which indicates whether a sentence implies dependence between the atomic formulas occurring in q.
A logic formula can be either propositional formula or universally quantified first-order logic formula. We use P (q) as shorthand notation for P (q is True) and P (gg) r) for P (g is True r is True). Symbol stands for the logical XOR operator.
3

---

x
b
q
c
(a)
(b)
b
4
4
(c)
(d)
Figure 2: Stamps of the sentences in LCNs: (a) sentence with r True; (b) A sentence
where is atomic formula (r is either Truc or False); (c) A sentence (3) where is non-atomic formula and т True; (d) sentence where q is non-atomic formula and False. The nodes corresponding to the atomic formulas are shaded.
Example 2. Consider the following Smokers and Friends LCC (adapted from (29). The predi-
cates )) Sm(.) and Cal-) stand for Friends(;;) Smokes(.) and Cancer respectively. Furthermore, predicate Fr(.,) is symmetric.
0.5 < (Fr (a; (a, B) A Fr (B, 1
0 P (Sm (a:)
① Sm (3) Fr (a, B)) $ 0.2,
(5)
0.03 <P (Ca (ax) Sm (ax) S 0.04,
0 SP (Ca (a) Smm (a)) S 0.01,
The LCN sentences state the following: friends of friends are likely friends + if two people are friends, they likely either both smoke or neither does smoking likely causes cancer (6)
3.2 Semantics
An LCN represents the set of all its models. A mode of an LCN is probability distribution over all interpretations such that it satisfies a set of constraints given explicitly by (3)(3) and a set of independence constraints which are implied by the LCN. The latter involve atomic formulas only and are similar to the independence relations implied by a Markov condition in graphical models [19]. Furthermore, we say that an LCN is consistent if it has at least model. Otherwise, it is inconsistent.
6 9 we propose a generalized Markov condition that accommodates the LCN's much more relaxed requirements on logic formulas, including cyclic dependencies (i.e., specifying sentences involving P(zly) and P(y(z) is allowed in LCNs because they may come from different sources of information). We introduce next the stamp of an LCN sentence and, subsequently, define the primal graph of an LCN which is the basis of proposed Markov condition.
In contrast to previous work 1
L, the stamp G(s) of s is a directed graph whose nodes correspond to formulas s, together with all atoms occurring in formulas in The edges of G(s) are determined as follows. For T = True, (i) if is 2 such that has atoms It, , In then G(s) has directed edges from q to each wi, and from each di to q, respectively, and (ū) if is (3) such that rI,..., In (resp. ai...., am) are the atoms in (resp. r), then G(s) contains a directed edge from r to 9, a set of directed edges from each 0, to r, as well as directed edges from q each I; and from each x, to g, respectively. For False, (iii) if is ( then G(s) has no edges, and (iv) if (3) such that and r have atoms I T1.... In and di...., am then G(s) contains directed edges from each a from to q and from each F,, respectively.
Definition 1 (stamp). Given an LCN L and sentence
'The semantics is not -ehe--thheeetic because there exist implied constraints that are jointly derived from multiple sentences.

---

Fr(Tim,Tam)AFr Tom,m)))
(TTTm.TT
Fc(lm/Jom/AA<((mmTTam)
Fr(Tim,Tom)
Fr(Tom,Tam)
Fr(Tim,Tam)
Sm(Tim)@Sm(TTmm
Smm(Tom\Sm((Tam
Sm(Tim/OSm(Tam)
Sm(Tim)
[m(Tom]
Sml Tam))
Ca(Tim)
Ca(Tom)
Ca(Tam]
Figure 3: The primal graph of the LCN from Example grounded on the domain {7 im, Tom, Tomb..
Figure 2 shows the stamps corresponding to different sentences in LCNs. The intuition behind the stamps the need to capture two types of dependencies. For sentence (2) with т = True, the dependency among atomic formulas in q is similar to a clique in Markov networks (see Figure For sentence 3 where is an atomic formula, the dependency is similar to the dependencies in Bayesian networks (see Figure 2(b)). The stamp of Figure [ is composition of the two types. For a sentence where is non-atomic, the parameter t controls whether its stamp includes edges from its atoms x, y and to q, and consequently modifies the primal graph and the Markov condition.
Definition 2 (primal graph). The primal graph of an LCN L with n sentences 81,..., 8n is the directed graph G representing the union of the stamps associated with the sentences in L, namely G =G(s)) U... G(s,).
Figure 3 illustrates the primal graph of the LCN from Example 2 grounded domain of three people x E {Tim, Tam, I J. where we assume = True for all sentences. As before, the symbol + is XOR and the shaded nodes correspond to atomic formulas.
Definition 3 (parents). The parents of an atomic formula x, denoted by parents(x), is the set of atomic formulas such that there exists directed path (y - 21 -.... 2 + x) from y x in the primal graph where all intermediate nodes z; (if any) are non-atomic.
Definition 4 (descendants). The descendants of an atomic formula x, denoted by descendants(z), + ... - zμ. + y) from parents(z).
is the set of atomic formulas such that there exists a directed path (I x to y in the primal graph where none of the intermediate nodes 2; (if any)
Definition 5 (Markov condition). Let f. be LCN and M be model of L. Given M, every atomic formula conditionally independent of its non-descendant non-parent variables ndup (x) given parents (x), where ndnp (x) 2 {atomic formulas] {parents' (x: descendants (x) U [x}}.
Clearly, the generalized Markov condition allows us to make additional independence assump- tions by inspecting the primal graph of the LCN. For example, looking at Figure again, we see that Corents(Sm(Tim)) = and ndnp(( Sm(Tim))
=f {Fr(Tém, Tom), Fr(Tim, Tam), Sm(Tom). Smm) Sm([amm [Pr(Tom, T Tam), Ca(C oom), (a(T)))). Therefore, (m(Tim) is conditionally independent of Fr(Tom, T Tam), Ca(Tom) and Ca(Tam) given Pr(Tim, Tom), Fr(Tim, Tam), Sm(Tom) and Sm (T))). Similarly, we can determine that Ca(Tim) condi- tionally independent of all other variables given (Timm..
Remark Let us consider the case when an LCN is used to represent a Bayesian network B. In this case, the upper and lower bounds in sentences (3) are equal; formulas involved in (3) are propositional and atomic; and the LCN sentences specify the prior and conditional probabilities in the Bayesian network. The primal graph is constructed by stamps only in the form of Tigure2t) and identical with the DAG of Consequently, the parents (resp. descendants) of an atomic node the same as the parents (resp. descendants) of in B. Therefore, the Markov condition of the
5

---

LCN is identical to that defined for Bayesian networks [26]. The LCN has only one model, which is the same probability distribution as the one represented by the Bayesian network
Similarly, if an LCN is composed of sentences (2 only and T = True for each sentence then, by our definitions, the parents of atomic node x the same the Markov blanket of in Markov Logic Network (MLN) with the same logic formulas as the LCN; the descendants of any atomic node is always empty; ndnp (1) are simply the atomic nodes not in the Markov blanket. Therefore, our Markov condition in this case is identical to the independence relations encoded in the MLN 29
3.3 Inference
Given LCN C. query formula f and, optionally, some evidence F {e1,-.., Ct) (i.e., a subset of atomic formulas that are true), marginal inference in LCNs calls for computing lower and upper bounds on the posterior marginal probability P(f denoted by P( E)) and P)) respectively,
The task entails solving non-lineat program defined over set of variables representing the proba- bilities of L's interpretations and comprising of linear constraints derived from the LCN sentences as well as non- non-linear constraints corresponding to the independence assumptions derived from L's Markov condition, respectively. The query P(f is translated into a non-linear objective function which is subsequently minimized and maximized, thus yielding P(flE) and P() respectively.
More specifically, if L has n atomic formulas then there are = 2n possible interpretations (recall that in the case of FOL, L refers to its grounding the domains of its variables shown in the example of Figure 3 Let p = (PI,...,PN) be the vector of their probabilities and let Aa (aî, ..... ax) be binary vector, called an indicator vector, such that az is 1 if formula is true in the j-th interpretation and 0 otherwise. Firstly, P must be valid probability distribution:
Σ Pg =1 and Pj 2 1. N
=1
(8)
Since the probability of formula is the sum of the probabilities of the interpretations in which the formula true, sentences (2 and
(3) in L are encoded by constraints (9) and (10). respectively:
A and O Ug
Aghr 1p-111-- 0 and Ager 2 Uglr A, 0
(10)
where @ is the dot product of two vectors (i.e., do aj b,). A, and Agxr are the indicator vectors for the interpretations where formulas g and A are true, respectively.
The independence assumptions implied by Definition have the form:
(s::[S,, T:) = P(., or, equivalently, P(x;, S,, P(T.) P(x,, T:) P(S,,T)) (11)
where 2; is an atomic formula, S = {s.1..... S. and T, {ta1...., t are x, 's parents and non-descendants in the primal graph of L. It is important to note that Equation I1 must hold for all truth values of its atomic formulas, namely when each atomic formula y E {(z S. UT; is replaced by y or -.. Therefore, it can be encoded by 21+h+l non-linear constraints as follows:
(Aa pp (As O (Ā, 3 p) (As p) =0
(12)
where and I are the sizes of the parent and non-descendant sets, A., Āg. A. and As are the indicator vectors corresponding to the formulas a = (α, As A S At ^ A..--Ata), 8 = (t.1 ....A-..AA Ata).
7 (z; ta A ta), and 8 (sa A... sik ta A ..... ta). respectively.
The objective F(J is encoded by
TF where A_ and A, are the indicator vectors of w AF (f Ae A A... e,) and e = (e, A...... A e.), respectively. We can then obtain the bounds P( E) and
E()(E) by solving min/max A.oT subject the constraints defined by Equations 7.37
10
respectively. In our experiments, we used state-of-ther the--ar non-linear solver such as ipopt
'Some of these constraints actually redundant and be removed suggested by i

---

Example 3. For illustration, consider the LCN & given by sentences (33 17 where T is true for all sentences. The primal graph of shown below, where shaded nodes correspond to atoms.
0.6 S (a 5
(13)
0% ((a c) S.2
(14)
0 P(a
(15)
0 ((b d) d) 0.7
(16)
a.A b
0 P(6] -d) s 0.3
(17)
Since has atomic formulas {a, b, c, d} there are interpretations. For simplicity, we represent their probabilities explicitly as (po,0.0.0= Po,0,0.1. -P1.1.1,1) where Po,0,0,0 is the probability that
a, b, c, and d are all false, P0.0.0.1 the probability that a, b, are false and d is true, and so on. We enforce Piad,k to be valid probability distribution by the following constraints:
PijkkJJ 2 Vi,i [0, and
Σ
Pij.k.11
(.I.IE
Sentences 13] and 44.. for example, correspond to the following two linear inequality constraints:
Σ
PI,LA 2 0.6 and Σ PI.iiI -.2
Σ (...E(0.11
PiJ.l 0
(.E(0.1)
Looking at the primal graph, the Markov condition implies thut, and d are independent, b is conditionally independent of e given {a, d} and a is conditionally independent of d given {b, c}. respectively. The latter independence assumption means that P(alb, c, P(alb, c) which must hold for all truth values of its atoms. Following the reduction technique suggested by [ corresponds to P(alb, d) P)) P(a b, -c, = P(alb, -c, P(al-b,e, d) -b) and ((a) -b, -, d) = P(a b,, -c) which can be encoded by four quadratic equality constraints:
Σ
Σ
Σ
PLL1111
PELLI
PELL1
P1,1111 =0
1
(E(0,1)
(E(0,1)
PLLL1,11
Σ
PEI,O.1
Σ
PLLLO.1
Σ
P1,1,,1 = 0
(01)
iE(0.1)
(E(0,1)
PLO.1I11
Σ
P.O.I.I
Σ
P.O.I.
P1,0.1,1 0 [E(0.1)
Σ
(0.1)
(0(1.))
P1,0,0.1
Σ
PLO,O.1 -
Σ
P.O.O.1
Σ
P1,0,011 = 0
iE(U,1}
(E(U,1)
The query P(c) corresponds to min/max Eijre(o.)) P.j.tt and results the interval [o, 0.33). Similarly, for the query P(alb), the objective Exac(on) Pra.s. and obtain [0.85, 1}.
Complexity The non-linear programs associated with LCNs are non-convex, thus NP-hard to solve in general (25]. One difficulty comes from the large number of quadratic equations involved. The complexity of exact marginal inference in LCNs can be bounded by O(ez((N): where N is the number of interpretations. Therefore, the scalability of exact inference is limited by the size of the LCN, One way to address this issue is to employ state-of-the--n approximate non-linear programming algorithms 32] or to rely on more recent column generation techniques I However, another important direction of our future work is pursuing a belief propagation
[26 19 based scheme for
approximate inference L-Ns which will allow us to scale to much larger problems.
Experiments
We evaluate our proposed approach on random LCNs as well benchmark problems derived from Mastermind puzzles with uncertainty and realistic credit card fraud detection application. All our experiments were run 2.6GHz CPU with 32GB of RAM.

---

4.1 Random LCNs
For our purpose, we generate random LCNs with n propo- sitional variables {æi..... En. and n + sentences of the form < P(x;) I and < (()) I u, where u,u E [0, and u - 2 0.3. For each problem size we generate 10 random instances and for each instance we select 5 different pairs of variables (x; # zz)) to formulate 4 queries per pair: P(x; Ax2), P(x, -r,), P( A AT)) and P(-z; A - respectively. Table | reports the aver- age runtime and standard deviation obtained for solving problems with E {5, 6, ..... 6,.., 12} (200 data points for each value of nt). We can see that, as expected, the runtime increases exponentially with the problem size due the complexity the non- linear programs involved. There- fore, solving random problems with more than 12 variables (over 4096 interpretations) becomes infeasible (i.e., exceeded a 24 hour time limit).
Table 1: Results for random LCNs.
Size (n)
Runtime (sec)
5
0.04 + 0.03
6
0.42 = 1.34
7
19.68 + 65.2
14.96 28.9
9
73.95 = 79.2
10
387.55 457.1
11
16794.36 + 24852
12
4.2 Mastermind Puzzles with Uncertainty
We consider variant of the popular Mastermind code breaking puzzle 18 in which the code-maker lies randomly at each round. A puzzle with n rounds can be specified by a Bayesian network with the feedback
4 hidden code variables {h1, f2 h3, h.). variables {ei..... Cn corresponding received each round and n variables (4.....,hy .n) indicating whether the code maker lied or not when he provided the feedback. We assume that imprecise information about the probability of lying given by Equations 18 21
......... 6), Vj E (1..... 4)) and given the code-maker feedback as evidence, the task is to find the color assignment to the hidden code variables such that its posterior marginal probability interval has the largest upper bound (maximax) or, alternatively, the largest lower bound (maximin). Namely, we compute:
Assuming 6 different colors for the hidden code variables (i.e., Cj E (1.....
H' argmax P(gle) and H argmax P(gle) 01,02,03.04
e1,02,6..04
where q f qı A 92 Q3 A q4 such that qj is the color assignment the jth code variable hy Cj. and e encodes the feedback (see the supplementary material for more details).
0.3 (P) S 0.7, sisn n
(18)
0.245 <P A22 < 0.360
(19)
0.795 <P (12 v S 0.903
(20)
0.207 <P (Is 44) S 0.273
(21)
We evaluate the following competing methods: (i) the Bayesian network
(BN) of the puzzle where
P(4) is
Table Results for Mastermind puzzles.
assumed to be the midpoint of the probability interval specified by (18);
Method
Accuracy
Runtime (sec)
(ii) the credal network (CN) speci- fied by (18;; (ii) the ProbLog (28 encoding that use the midpoint Pmndd of the probability intervals to anno- tate the logic formulas (18); (iv) the
BN
65.7% + 2.2%
0.4 0.5
CN (maximax)
60.3% + 2.3%
17.0
CN (maximin)
64.4% + 2.2%
1.6
ProbLog
65.7% + 2.2%
0.4
MLN
65.3% + 2.1%
0.5
Nilsson (maximax)
intractable
Markov Logic Network (MLN) repre-
sentation of (18) - using the mid-
Nilsson (maximin)
0%
LCN (maximax)
69.2% + 1.8%
684.4 + 54.1
points to calculate the weights w log(pmia//C - Pmnia) )) of the formulas.
LCN (maximin)
71.1% + 1.9%
1029.3 3 68.9
LCN (maxent)
72.5% + 1.7%
85.0 + 6.3
We note that BN, CN and Problogg
use only equations [88 while MLN

---

(21 For LCN and CN we use both the maximax and maximin criteria to determine the hidden code. Furthermore, the LCN based formulation assumes that sentences (99 ) are annotated with т = False so that they do not imply dependency among the variables. In addition, we consider I.C(maxent), an LCN variant that computes joint distribution of the 1 variables with the largest entropy and assumes that it is the true distribution of lies. For reference, we also ran Nilsson's 's method [23].
and LCN are able to utilize logic formulas like 19
In Table we report the mean accuracy and standard deviation obtained on 10 sets of puzzles, each set using different random seed and containing 730 random puzzles. We also record the mean total runtime and standard deviation. Accuracy is defined as the fraction of puzzles that an algorithm guessed the ground-trre hidden code correctly. We can see that our proposed LCN approach achieves the highest accuracy compared with its competitors. This is because the LCN is the only method able to aggregate multiple sources of imprecise knowledge in the most effective manner without making any unwarranted independence assumptions among different pieces of knowledge. Although MLN can exploit additional knowledge, does not gain accuracy because treats each logic formula as a statistically independent factor and the probabilities factor potentials; in other words, the probability midpoints are not treated as probabilities in the joint distribution. This is a major weakness of this method, in addition to its inability to handle intervals. In terms of runtime, LCN is slower than its competitors because of the far more complex non- non-linear programs that need to be solved for each puzzle. However, improving the LCN's runtime is direction of our future work.
Finally, we note that although Nilsson's method is able to utilize all the logic formulas and their bounds, it does not allow modeling 4 variables as being independent of each other. Given a puzzle, each possible hidden code e corresponds to a truth assignment to the I; variables; without independence relations, there always exists joint probability distribution of the 1; variables such that the particular truth assignment has zero probability. Consequently, the lower bound of the posterior probability given puzzle is zero for any c, and therefore the maximin criterion has no basis to make decisions upon. Intuitively, a similar effect should also impair the accuracy of Nilsson (mxximxx) However, we are unable to verify this empirically: computing the upper bound of the posterior by solving Nilsson's 's constraint program is computationally prohibitive due to the complexity of the objective function and the size of the program.
4.3 Credit Card Fraud Detection
We consider a realistic credit card fraud detection task based on the UCSD-FICO Data Mining Contest dataset [13] which contains 100,000 transactions over period of 98 days out of which 2,654 are fraudulent. Each transaction is characterized by 16 features, including the transaction amount, timestamp and hashed email address. We used the email addresses account IDs and split the data into two subsets: one containing 55,750 accounts, each with a single transaction, and another containing 14.374 accounts with multiple transactions, thus totaling 44,250 transactions. These two subsets were subsequently used as training (7) and test (V) sets, respectively. Additional imprecise knowledge regarding fraudulent transactions and account history is given by the logic rules (2 2.3
and 24 which were previously suggested in (21]
For our purpose, we created 10 randomized tasks such that for each task we sampled half of T and half of V. respectivelly We then calculated the lower and upper probability bounds of the logie rules (22 (4) as follows. For each formula and each of the 10 test sets, we measured the conditional probability that the consequent is true given that the antecedent true. We took the min and max over the test sets and obtain the following probability intervals for the three rules: [0.65, 0.74) for
22 [0.31, 0.66 for (33 and [0.44, 0.72] for (4), respectively.
Has Frauddisttooory (f') A Before (t' -Is--rrudd (t)
(22)
Has Zew.oooontnttittoooro (t') A Before (t't) --I--Fraud (t)
(23)
Has-Multizig (t') A Before (t',t) (Is-Fruud
(24)
We evaluated the following methods: (i) a NaiveBayes model learned directly from data; (ii) a
Bayesian network (BN) model that expands NaiveBayes by adding the antecedents of the three logic rules as parents of the Ts-Fraud node and uses a noisy-OR model together with the midpoint of the three probability intervals to represent this conditional probability distribution (the prior

---

probability of the three new nodes is 0.5); (iii) a credal network (CN) model with the same structure and noisy-OR model as the Bayesian network above but using the three probability intervals as well as the probability interval [0, 1] for the root nodes; (iv) Problog encoding of the NaiveBayes model using the midpoints of the three probability intervals to annotate the Problogg logic rules; (v) an MLN encoding of the NaiveBayes model extended with the three logic rules and annotated by
weights w log(Pmia/( P,mi)), where Pmid is the midpoint of the respective probability interval.
Table reports the mean and standard deviation of the Fl scores obtained over the 10 random tasks. In this case, the Fl score (defined as the harmonic mean of the precision and recall) is much better metric than accuracy because the classification task is imbalanced, namely, the probability of fraudulent transactions is much smaller than that of non-fraudulent ones. We also record the mean total runtime and standard deviation. We see again that our proposed LCN method substantially outperforms its competi- tors in terms of solution quality (F1 score). In
Table 3: Results for fraud detection.
Method
Fl score
Runtime (sec)
NaiveBayes
0,408 + 0.110
0.27 + 0.01
BN
0.090 = 0,015
0.29 = 0.02
CN
0.089 = 0.015
0.28 = 0.01
ProbLog
0.599 = 0,048
0.29 = 0.02
MLN
0.472 = 0,094
0.29 - 0.01
Nilsson LCN
intractable
0.630 0.046
0.29 + 0.01
this case, the BN and CN based approaches perform quite poorly because of the unique- aasgue--ssssmenttt requirement. Specifically, the Is-F raud node has three parents and therefore we are longer allowed to specify P (Is-Fraud). Since P (Is-Fraud) values are measured on the training data (e.g.. NaiveBayes), this information is lost in the Bayesian and credal models and, consequently, their false positive predictions increase dramatically. As before, the results demonstrate that LCNS are able to effectively aggregate and exploit multiple sources of information which leads significantly improved performance. Finally, we see that the performance of Nilsson's 's method is quite poor in this case as well.
5 Related Work
Nilsson's probabilistic logic 23 24 is perhaps the first system in which the truth values of logical sentences (or formulas) can range between 0 and 1 and are interpreted as the probability of those sentences being true but does not permit specifying independence relations. Bayesian logic (BL) combines probabilistic logic and Bayesian networks in order to capture conditional independence relations among propositions. Markov Logic Networks (MLN) [29] apply the ideas of Markov network to first-order logic where the weights attached to the logic formulas are used to define joint probability distribution over all possible interpretations and thus enable uncertain inference. Probabilistic Soft Logic (PSL) [15] combines Markov networks with soft real-valued logic (e.g.. Lukasiewiez logic). Probabilistic Logic Programs (PLP) (27] and Stochastic Logic Programs (SLP) 10 are logic programs in which some of the facts are annotated with probabilities. We emphasize that MLN, PSL, PLP, SLP do not allow probability bounds on logic formulas, while BL. constrains the formulas to specific structure. LCN is the only system that addresses these shortcomings.
6 Conclusions
In this paper we propose a new probabilistic logic that expresses both probability bounds for proposi- tional and first-order logic formulas with few restrictions and Markov condition that is similar to Bayesian networks. The formula bounds allow for flexibility in the form and precision of background knowledge that can be utilized, while the Markov condition restricts the space of distributions to enable a meaningful representation of uncertainties. In addition, we show how to perform exact marginal inference to answer queries for the new formalism. Our empirical evaluation on random problems as well as more realistic applications shows promising results, particularly in aggregating multiple sources of imprecise information. Potential future directions include extending to tempo- ral models, further algorithmic innovations to improve the runtime of exact inference, developing efficient approximate inference algorithms and experiments wider array of applications.
10

---

References
[1] K. Andersen and J. Hooker. Bayesian logic. Decision Support Systems, 11(2):1912210, 1994.
[2] M. Bazaraa and C. Shetty. Nonlinear Programming: Theory and Algorithms. Wiley, 1979.
[3] A. Cano and S. Moral. Using probability trees to compute marginals with imprecise probabilities.. International Journal of Approximate Reasoning. 29(1): 2002.
[4] R. Cavallo and M. Pittarelli. The theory of probabilistic databases. In Proceedings of 13th International Conference on Very Large Data Bases (VLDB), pages 71-81, 1987.
[5] V. Chandru and J. Hooker. Optimization Methods for Logical Inference. John Wiley & Sons,
1999.
[6] Cozman. Credal networks. Artificial Intelligence, 120(2): 100(2):1992333, 2000.
[7] Cozman. Generalizing variable-climination in Bayesian networks. In Workshop on Proba- bilistic reasoning in Bayesian networks at SBIA/Iberamia 2000, pages 21-26, 2000.
[8] F. Cozman and R. Polastro. Loopy propagation in probabilistic description logic. In Interna- tional Conference on Scalable Uncertainty Managemens, pages 120-133. Springer, 2008.
[9] F. Cozman and R. Polastro. Complexity analysis and variational inference for interpretation- based probabilistic description logies. In Proceedings of the Conference Uncertainty in Artificial Intelligence, pages 117-125, 2009.
[10] J. Cussens. Stochastic logic programs: Sampling, inference and applications. In Uncertainty in Artificial Intelligence (UAI), pages 112,122, 2000.
[11] M. Dürig and Studer. Probabilistic ABox reasoning: Preliminary results. Description Logics, pages 104-111, 2005.
[12] R. Fagin, J. Halpern, and N. Megiddo. A logic for reasoning about probabilities. Information and Computation, 87(1-2):78-122 128, 1990.
[13] FICO-UCSD. FICO Credit Card Dataset. 2009. http:://bbuuuuuuubb..uuuuggguzzu ucsd-data- mining-contest
[14] S. Flesca, F. Furfaro, and Parisi. Consistency checking and querying in probabilistic databases under integrity constraints. J. Compul. Syst. Sci., ((80))1448-11) 2014.
[15] L. Getoor and B. Taskar. Introduction to Statistical Relational Learning (Adaptive Computation and Machine Learning). MIT Press, 2007.
[16] Heinsohn. Probabilistic description logies. In Proceedings of the International Conference on Uncertainty in Artificial Intelligence, pages 311-318, 1994.
[17] M. Jaeger. Probabilistic reasoning in terminological logics. In Principles of Knowledge Representation and Reasoning, pages 305-316. Elsevier, 1994.
[18] D. Knuth. The computer as Master Mind. Journal of Recreational Mathematics, 9(1):166, 1976.
[19] D. Koller and N. Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT Press, 2009.
[20] J. Li and A. Deshpande. Consensus answers for queries probabilistic databases. In SIGMOD/ACM Symposium on Principles of Database Systems (PODS), pages 259-268, 2009.
[21] S. Li, L. Wang, R. Zhang, X. Chang, X. Liu, Y. Xie, Y. Qi, and L. Song. Temporal logic point processes. In International Conference on Machine Learning (ICML), pages 5990-600000 2020.
[22] Lukasiewicz. Expressive probabilistic description logies. Artificial Intelligence, 172(6- 7):852-883 2008.
[23] N. Nilsson. Probabilistic logic. Artificial Intelligence, 28(1):71-87, 1986.

---

[24] N. Nilsson. Probabilistic logic revisited. Artificial Intelligence, 39(1-2):39 42, 1994.
[25] P. Pardalos and S. Vavasis. Quadratic programming with one negative eigenvalue is (strongly) np-hard. Journal of Global Optimization, 1(1):15-22, 1991.
[26] J. Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, 1988.
[27] L. De Raedt, P. Frasconi, K. Kersting, and S. Muggleton. Probabilistic Inductive Logic Programming Theory and Applications. Springer, 2008.
[28] L. De Raedt, A. Kimmig, and H. Toivonen. Problog: A probabilistic prolog and its application in link discovery. In Proceedings of the International Joint Conference on Artificial Intelligence, volume 7, pages 2462-2467, 2007.
[29] M. Richardson and P. Domingos. Markov logic networks. Machine Learning, 62(1-2)1107-136. 2006.
[30] Sen and Deshpande. Representing and querying correlated tuples in probabilistic databases.
In International Conference on Data Engineering (ICDE), pages 596-605, 2007.
[31] A. Wächter and L. Biegler. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming, 106(1):25-57, 2006.
[32] J. Wang. Approximate nonlinear programming algorithms for solving stochastic programs with recourse. Annals of Operations Research, 31:371-384, 1991.
Checklist
1. Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Sections 3 and
2. Did you describe the limitations of your work? [Yes] See Section
3. Did you discuss any potential negative societal impacts of your work? [N/A]
4. Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
you are including theoretical results...
1. Did you state the full set of assumptions of all theoretical results? [Yes] See Section
2. Did you include complete proof's of all theoretical results? [N/A]
you ran experiments...
1. Did you include the code, data, and instructions needed reproduce the main experimental results (cither in the supplemental material or as URL)? [Yes] See supplementary material
2. Did you specify the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section F and supplementary material
3. Did you report error bars (c.g., with respect to the random seed after running experiments multiple times)? [Yes] See the tables in Section
4. Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section
If you are using existing assets (e.g., code, data, models) curating/releasing new assets...
1. If your work uses existing assets, did you cite the creators? [N/A]
2. Did you mention the license the assets? [N/A]
3. Did you include any new assets either in the supplemental material as URL? [Yes] The source code is included in the supplementary material
12

---

4. Did you discuss whether and how consent was obtained from people whose data you 're using/curating? [N/A]
5. Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
you used crowdsoureing or conducted research with human subjects...
1. Did you include the full text of instructions given to participants and screenshots, if applica- ble? [N/A]
2. Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
3. Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "smnJcRS2IJY", "reviewer": "Reviewer_Lye7", "summary": "A new probabilistic model called Logical Credence networks is proposed. The model allows us to specify ranges of probabilities for logical rules. The probabilities may be specified as conditionals or marginals. A mapping from the logical structure to a graphical structure is proposed that can specify independencies. An inference procedure is developed that is based on solving a system of equations over the grounded logical theory. This gives us an upper and lower bound on the marginal probabilities.\n\nExperiments are performed over synthetic structures as well as mastermind puzzles and a fraud detection dataset.", "questions": "To make the model complete, I think there needs to be a clear specification of how we can learn such models, so a discussion on this will be useful. \nAlso, it would be useful to hear about some of the concerns in the previous section.", "limitations": "Limitations (e.g. scalability) has been discussed.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1. The ability to specify ranges or bounds for the formulas may be useful instead of a single parameter (e.g. in MLNs)\n2. Constraining the marginal probabilities based on the independencies may result in probabilities that are more intuitive.\n\nWeakness\n1. The clarity of the contribution is somewhat lacking. For example,  the  representation and the inference procedure is presented, but how are the parameters learned? In the experiments, it seems to be done based on the test data (e.g. the fraud detection task). Without a standard learning procedure, it seems the model is a bit incomplete.\n2. From a practical perspective, the model seems to be not as scalable and am not sure if it would apply to real-world settings.\n3. I am not sure about the comparison with approaches such as MLNs and Problog since the weights are not learned here as I see it. Also, the statements in lines 280, 281 may not be fully accurate. In MLNs, the formulas are not independent since they are connected through a factored Probabilistic  Graphical Model. Maybe this needs to be rephrased.\n4. From a higher-level perspective, there are other types of models that seem similar. The one that comes to mind is PSL (Probabilistic Soft Logic) that allows arbitrary function to be specified over logical formulas (the ranges may be a special case of this). A discussion on the significance of the proposed approach will be useful.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "jVCIlkNnJJc", "reviewer": "Reviewer_ak6q", "summary": "This paper proposes a new graphical model and language to express probabilistic constraints over logical formulas, either in the propositional language or in first order logic, expressed either as unconditional or conditional formulas. Compared to previous languages, it offers more flexibility in terms of modelling, and assume variable independence as a default assumption, rather than as a declared property. Dependence then has to be explicitly stated. The paper introduces Markov conditions for this kind of models, and demonstrates through some small-scale experiments that the model increased expressiveness allow one to increase inference quality. ", "questions": "* In the paper, FOL problems are solved by grounding them, which clearly induces a quick explosion if the number of variables increase. Is this grounding actually the only way to solve the problem or could solvers directly adapted to FOL problems be used, e.g., by considering fragments of FOL rather than all of it? Echoing to this question, my feeling is that here authors consider that any Boolean sentence can be provided in each parts of the formulas. Would the inference problem become simpler if one were to restrict the possible formulas to peculiar fragments of logic (still expressive enough to warrant application, but with properties allowing for faster inferences). \n\n* Any ideas about approximation schemes for this particular language that would allow for some scalability? In the paper, this is left for future work, but maybe the authors have some ideas about it they can share. For example, would linearisation schemes help and allow to use LP tools? \n\n* In the comparisons with other approaches, authors mainly consider other probabilistic graphical models, at the exception of problog. What about using probabilistic versions of answer set programming, or PSAT solvers? \n\nTypos or other small remarks:\n\n* L195 and others: reference to equation is not between parenthesis. This is unusual (but maybe voluntary)\n\n* L217: missing parenthesis after $P(a|b,\\not c$", "limitations": "The main limitation of the presented approach, i.e., its scalability, is mentioned in the paper. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality**\n\n+: this is a new model to express probabilistic logic constraints, be they precise or imprecise. The proposal is quite convincing. \n\n**Quality**\n\n+: the paper is quite well-written and quite understandable. The proposal is sound, and the first results seem promising, even if scalability of the proposed will clearly be an issue. \n\n**Clarity**\n\n+: the paper presents the model clearly, even for a non-expert. \n\n**Significance**\n\n+: a new model that seems to present quite interesting properties in terms of logical inference (e.g., allowing for bounds over probabilistic information while not making inference quickly vacuous), and present a quite expressive model. \n\n-: two limits of the paper are clearly on the one hand its scalability if one has to perform exact inferences over it, and the need (?, see questions) to ground FOL problems into propositional ones. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "TWUU4wYU5NK", "reviewer": "Reviewer_WFaC", "summary": "The paper proposes a new probabilistic logic based on interval-valued probabilistic statements. This can be seen as a simultaneous generalisation of both Markov Logic Network and Credal Networks that, in turn, extend Bayesian networks. The syntax and semantics are provided and the inference is shown to correspond to a non-linear (hard) task. The experiments (Mastermind with Uncertainty, Fraud Detection Data) show promising results as MLN, BN, CN and ProbLog approaches are outperformed by the proposed technique.", "questions": "- In proving the hardness of LCN the authors follow the mapping to non-linear programs. What about using the link with complexity results for CN (see e.g., Mauà et al., JAIR 2012)? As LCN extends BN, it should also (trivially) extend CN inference.\n- It is not clear to me whether or not a \"grounding\" operations allows to write a LCN as a (larger) CN. This would be relevant for inference.\n- I consider the \"Remark\" paragraph quite important. The fact the LCN extendes both MLN and BN/CN is a strong justification for this new probabilistic logic. What about making the result more formal (i.e., a proposition with a proof)? I see the derivation is almost straightforward, but making this even more clear would be potentially important.\n- I am very happy with the discussion in S3.3, but I miss at least an extensive comments on how the existing literature (mostly in the CN area) addressed similar (multilinear or fractional multilinear) optimisation tasks. I am quite sure that some of the techniques considered for CN could be adapted to LCN and an extensive discussion on that point would be important.\n- I am not sure whether, in the experiments, MLN is equivalent to LCN with sharp probabilistic assessments in the midpoints. If this is not the case also that setup would be interesting.\n- The above point is also related to the fact that, in the experiments maximin/maximax/maxent, are clearly reasonable approaches to decision making with imprecise information if the goal is to output a single option, but it might be also interesting to see what happens if multiple outputs are considered. The simplest experiment would be to compare the maximin and the minimax solutions and to evaluate separately the accuracy (of some other, precise approach) when these two solutions are equal and when they are different. We might expect a clear separation between the two values.\n- I am a bit surprised by the very similar execution times in Tab3. Is there an explanation for that?\n- Regarding loopy propagation, Zaffalon's 2U algorithm for CN allows for polynomial inference in tree-shaped Boolean CNs. Cozman et al. provided a loopy version of 2U. These techniques can be probably applied to LCN. Of course this is also related to the work of Polastro & Cozman properly cited by the authors. What about commenting also this direction?\n\n", "limitations": "I don't see urgent issues related to the societal impact. Regarding the limitations, these are mostly related to the computational complexity, and the authors are very explicit on that.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The contribution is clearly novel and, in a sense, is filling a gap in the literature (Probabilistic Logic in interval-valued statements). \n- Although mostly heuristic, I don't see issues with the technical derivation of the results (e.g., the fact that LCN generalises both MLN and BN).\n- The presentation is clear and quite accessible.\n- The experiments are clearly showing the advantages of the proposed approach.\n\nWeaknesses\n- My only concern with the paper is related to the inference part. The authors clearly describe how to solve an LCN inference with a generic non-linear solver, but no particular attention is paid to exploit the specificities of the task in order to find faster solutions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ESYavnaNBYi", "reviewer": "Reviewer_F77m", "summary": "Logical Credal Networks (LCN) are an expressive probabilistic logic for expressing credal sets of distributions over interpretations of a logic theory. An LCN is a set of probabilistic statements expressing lower and upper bounds on the probability of a first order logic formula or on the conditional probability of a formula given another formula. The semantics of an LCN is the set of its models where a model is a probability distribution over the interpretations that satisfies the constraints plus the independence constraints that are implied by the model. An LCN can be drawn as a graph and the paper proposes a generalized Markov condition that can be read from the graph, namely that every atomic\nformula $x$ is conditionally independent of its non-descendant non-parent variables given its parents.\nThe paper shows that this Markov condition reduces to the one of Bayesian networks and Markov Logic Networks when the LCN represents one of these special cases.\nMarginal inference entails computing upper and lower bounds for $P(f)$ of $P(f|E)$ where $f$ is a formula and $E$ is a set of atomic formulas. The paper proposes a solution to the problem of inference by means of using a non-linear constraint program which has one variable for the probability of each interpretation, where, if there are $n$ atomic formulas, there are $2^n=N$ interpretations. The non-linear program is non-convex so the problem is NP-hard in $N$ and a bound on the complexity is $O(exp(N))$, thus doubly exponential in $n$.\n\nLCNs are evaluated by considering random LCNs, Mastermind puzzles and credit card fraud detection.\nOn random LCNs, the approach is able to solve problems with up to 11 atomic formulas.\nOn the Mastermind puzzles, a version of the game is considered where the code maker is allowed to lie. The task is to guess the most probable code set by the code-maker after a number of guesses. LCNs are compared with Bayesian networks, Credal Networks, ProbLog and MLN and found to be more accurate in guessing the correct solution, even if slower.\nOn the credit card fraud detection problem, a real dataset of credit card transaction is considered and the problem is to predict whether a transaction is fraudulent or not using an LCN composed of three rules together with constraints on them.\nLCNs are compared with a Naive Bayes model, a Bayesian Network, a Credal Network, a ProbLog program and an MLN and found to achieve better F1 in a comparable time.", "questions": "1) Can you imagine an algorithm that does not have to materialize all interpretations? Or can the language be restricted so that this is not necessary?", "limitations": "The limitations of the approach has been presented. The work does not have negative social impacts.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is surely original, to the best of my knowledge this is the first paper applying credal networks to a first order logic language. The expressiveness of the constraints of LCN is very high, giving the possibility of expressing a wide variety of knowledge on the domain, in particular imprecise knowledge and knowledge potentially coming from different sources that, when aggregated, break the acyclicity or unique-assessment requirements of Bayesian and Credal Network.\n\nThe paper appears technically sound, correctly identifying a way to extract the implicit independencies in the LCN through the Markov condition that are specifically proposed for LCNs. Importantly, if the LCNs encodes a Bayesian network or an MLN, the proposed Markov condition coincides with that of the specific models. I have only one observation on this:\npage 5 says that \"the descendants of any atomic node $x$ is always empty\" for LCN encoding MLNs. It seems to the that the descendants are always equal to their parents.\nThe approach for building the non-linear program for inference is correct and I'm convinced that the solution of the program is the solution of the marginal inference problem. I think there is a typo in eq (10) in the second formula: \n$A_q$ should be $A_{q\\wedge r}$\n\nThe experiments are sufficiently extensive to demonstrate the usefulness of the added expressiveness of LCNs with respect to the main competing methods. The random LCNs experiments give a clear idea of the scalability of the approach (11 variables), while the Mastermind and credit card fraud experiments show the improved solution quality of LCNs.\n\nThe main weakness of the approach is the scalability: 11 atomic formulas are not many for a relational domain. This is due to the fact that the whole set of interpretations of the first order logic theory has to be considered in the inference algorithm, making it doubly exponential in $n$, the number of atomic formulas. This is in stark contrast with Bayesian networks and MLNs where inference avoids generating all possible interpretations and this is the main strength of these approaches. It would be a very interesting direction for future work to overcome this limitation.\n\nOverall the paper is very clearly written, expressing the concepts in details and with illuminating examples. The only thing not very clear is the list of equations (18)-(21) that contain dots, meaning that there are others, but then the text only refers to (19)-(21), leading one to think there are only those. The situation is clarified in the supplementary material where the exact procedure for generating those equation is explained, confirming that there are many more.\nThis point could be clarified.\n\nMinor comments:\n\nPage 6, last line $P(a|b,\\neg c$ is missing a closing parenthesis", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept