Most Probable Explanation in Probabilistic Answer Set Programming

1 Introduction

Statistical Relational Artificial Intelligence (StarAI) [Raedt et al., 2016] serves as umbrella term encompassing a wide range of approaches that integrate probability into logic-based languages. These approaches have recently gained renewed momentum thanks to the advent of the field of neuro-symbolic integration [d'Avila Garcez et al., 2019]. Here, we focus on the Probabilistic Answer Set Programming (PASP) formalism [Cozman and Mau´a, 2020; Mau´a and Cozman, 2020] and on the fundamental task of Most Probable Explanation (MPE) [Raedt et al., 2016], which, interestingly, is still an open problem for PASP [Azzolini et al., 2022]. Given a probabilistic answer set program and evidence e (in the form of conjunction of ground literals), MPE requires computing the world which has the highest probability and where e is cautiously or bravely true. These states are called lower and upper MPE states, respectively.

In this paper, we present three novel approaches for solving the MPE task in PASP that are based on: i) Knowledge compilation [Darwiche and Marquis, 2002], ii) Answer Set Programming (ASP) [Gelfond and Lifschitz, 1991; Brewka et al., 2011], and iii) ASP with quantifiers (ASP(Q)) [Amendola et al., 2019].

Knowledge compilation (KC) [Darwiche and Marquis, 2002] is a standard technique adopted in StarAI: the program is compiled into a form where the considered task can be solved more efficiently. After compilation, the initial problem boils down to solving a counting problem on the compiled form, which can often be expressed as Algebraic Model Counting (AMC) [Kimmig et al., 2017]. The expressivity of some languages and the complexity of some tasks require stacking two layers of AMC (2AMC) [Kiesel et al., 2022]. In this paper, we provide a 2AMC encoding of MPE as well as a practical implementation into the aspmc [Eiter et al., 2021; Eiter et al., 2024] solver. Then, we discuss an encoding in ASP which targets the computation of the upper MPE states only, that can be also adopted for the computation of the MPE state in probabilistic logic programs (i.e., stratified programs, where the lower and upper MPE states coincide). Lastly, building on the inherent complexity of the task, we also propose an encoding for computing the lower MPE state using ASP(Q) [Amendola et al., 2019]. ASP(Q) extends traditional ASP by introducing the concept of quantifiers over answer sets that makes the modeling of problems in the entire Polynomial Hierarchy [Stockmeyer, 1976] as natural as modeling NP-hard problems in standard ASP. Our proposals have been assessed through an extensive evaluation considering multiple datasets targeting different probabilistic scenarios, and revealed to be the best performing ones in the case of nonstratified programs.

2 Background

Answer Set Programming. We assume the reader to be familiar with the basic concepts of Logic Programming. A rule r is an expression of the form h1; . . . ; hn :- b1, . . . , bm where h1; . . . ; hn, with n ≥ 0, is a disjunction of atoms referred to as head and b1, . . . , bm, with m ≥ 0, is a conjunction of literals referred to as body. If n = 0 then r is a strong constraint; otherwise, if m = 0 then r is a fact. A choice rule is an expression of the form {a1; . . . ; an}, with n > 0, where each ai is a ground atom. Intuitively, a choice rule is a shorthand for a set of normal rules of the form "ai :- not nai", "nai :- not ai", where ∀i ∈ {1, . . . , n}, nai is a fresh atom not appearing elsewhere. Given a rule r, we denote by Hr the set of atoms appearing in the head and by Br the set of literals appearing in the body. Given a set of literals L, we denote by L+ (resp. L-) the set of positive (resp. negative) literals in L. A weak constraint is an expression of the form :∼ b1, . . . , bm [w, T ], where b1, . . . , bm, with m ≥ 0, is conjunction of literals, w is a term, and T is a (possibly empty)

tuple of terms (in this case, T is omitted). An answer set program (ASP, and we use the same acronym to denote Answer Set Programming, the context will disambigaute the meaning) is a finite set of safe rules (i.e., variables appear at least in one positive literal of the body) and weak constraints. An ASP is plain if it contains no weak constraints. An ASP expression (i.e., literal, rules, etc.) is ground if it contains no variables.

Given a program P, the Herbrand Universe, denoted by UP , is the set of constants that appears in P. The Herbrand Base, denoted by BP , is the set of ground atoms that can be built from predicates appearing in P and constants in UP . Given a rule r ∈ P, ground(r) denotes the set of ground instantiations of r obtained by substituting variables with constants in P. The grounding of P, denoted as ground(P), is the union of the grounding of rules in P. The dependency graph of P , denoted by GP , is a labeled directed graph whose nodes are atoms in BP and there is a positive (resp. negative) edge from an atom b to an atom h if there exists r ∈ ground(P) such that b ∈ B+ r (resp. not b ∈ Br ) and h ∈ Hr. A program P is said to be stratified if GP does not contain loops involving negative edges, whereas P is headcycle-free, if, for each r ∈ P and each pair of atom a, b ∈ Hr, does not exist a positive loop in GP involving both a and b. In what follows, ASP are assumed to be head-cycle-free.

The semantics of ASP is defined in terms of answer sets [Gelfond and Lifschitz, 1991]. More precisely, an answer set of a program P is an interpretation I (i.e., a subset of BP ) that (i) satisfies all the rules in ground(Π) (i.e., for each r ∈ ground(P ), Hr ∩I ̸= ∅ whenever B+ r ⊆ I and {a | not a ∈ Br }∩I = ∅); and (ii) I is a ⊂-minimal model of its (Gelfond-Lifschitz) reduct [Gelfond and Lifschitz, 1991]. Let AS(P) be the set of answer sets of P, then P is coherent if AS(P) ̸= ∅; otherwise it is incoherent. The cost of an answer set M is defined as C(P,M) = ∑(w,T)∈ws(P,M) w, where ws(P,M) = {(w, T) | :∼ b1, . . . , bn, [w, T] ∈ ground(P), w is a numeric constant, and M |= b1, . . . , bn}. An answer set M ∈ AS(P) is optimal if there does not exist M ′ ∈ AS(P) having a strictly lower cost (i.e., such that M is dominated by M ′ ). For further details on the ASP semantics, we refer the reader to the dedicated literature [Gelfond and Lifschitz, 1991; Buccafurri et al., 2000; Calimeri et al., 2020].

Example 1. Let us consider the following program:

Here we have two answer sets M1 = {a} and M2 = {na}. Since a is true inM1, its cost is 1. Conversely, since a is false inM2, its cost is 0. Thus, only M2 is optimal.

Answer Set Programming with Quantifiers. ASP with Quantifiers (ASP(Q)) extends ASP by introducing quantifiers over answer sets [Amendola et al., 2019; Mazzotta et al., 2024]. Namely, an ASP(Q) Π is an expression of the form:

where for each i ∈ {1, . . . , n}, □i ∈ {∃st , ∀st } and Pi is a plain ASP, C is a plain stratified program with strong constraints, and C ω is a set of weak constraints. An ASP(Q) is said to be existential if □1 = ∃st ; otherwise, it is universal. The coherence of an ASP(Q) Π is defined as follows:

• ∃stP : C : C ω is coherent, if there exists M ∈ AS(P) such that C ∪ fixP(M) admits an answer set;
• ∀stP : C : C ω is coherent, if for every M ∈ AS(P), C ∪ fixP(M) admits an answer set;
• ∃stP Π′ is coherent, if there exists M ∈ AS(P) such that Π′P,M is coherent;
• ∀stP Π′ is coherent, if for every M ∈ AS(P), Π′P,M is coherent.

where Π′ is an ASP(Q) of the form (1), ΠP,M denotes the ASP(Q) obtained from Π by replacing P1 with P1 ∪ fixP (M ) (i.e., ΠP,M = □1(P1∪fixP(M)) □2P2 · · ·□nPn : C : C ω ), and fixP(M) denotes the set of facts and strong constraints {a | a ∈ M} ∪ {← a | a ∈ BP \ M}. For an existential ASP(Q) Π, M ∈ AS(P1) is a quantified answer set of Π if (□2P2 · · ·□nPn : C : C ω )P1,M is coherent. We denote by QAS(Π) the set of quantified answer sets of Π.

For an ASP(Q) of the form (1), the set of weak constraints C ω , referred to as global weak constraints, are used for specifying preferences criteria over quantified answer sets. More formally, let Π be an existential ASP(Q) of the form (1) and M1,M2 ∈ QAS(Π). We say that M1 is dominated by M2 if C(P ∗ 1 ,M2) < C(P ∗ 1 ,M1) where P ∗ 1 = P1 ∪C ω . A quantified answer set M ∈ QAS(Π) is optimal if does not exist M ′ ∈ QAS(Π) such that M is dominated by M ′ .

Example 2. Let us consider an ASP(Q) Π = ∃P1∀P2 : C : C ω , where P1 is the ASP from Example 1, P2 is the program:

C = { :- a, nb}, and C ω = :∼ a. From Example 1, P1 admits M1 and M2 as answer sets. If we fix M1 in P2 we obtain two answer sets, M3 = {a, b} and M4 = {a, nb}. Since M4 violates the constraint in C then M1 is not a quantified answer set. Instead, by fixing M2 in P2 we obtain two answer sets, M5 = {na, b} and M6 = {na, nb}. Since both M5 and M6 satisfy the constraint in C, thenM2 is the only quantified answer set for Π and so it is also optimal.

Probabilistic Answer Set Programming. One possible formalism to encode uncertain data with a logic-based language is Probabilistic Answer Set Programming under the credal semantics [Cozman and Mau´a, 2020; Mau´a and Cozman, 2020], PASP, for short. A PASP is an ASP extended with probabilistic facts that follows the syntax [De Raedt et al., 2007] p :: a with p ∈ [0, 1] and a an atom. We assume that probabilistic facts cannot appear as the head of rules. For a PASP P, we denote with F(P) the set of atoms {a | p :: a ∈ P} and with P(P) the underlying ASP. A selection σ is a set of atoms associated with probabilistic facts, i.e., σ ⊆ F(P). We denote by Σ the set of all selections, i.e., Σ = 2F(P) . The probability of a selection σ is computed as P (σ) = ∏ai∈σ pi ∏ai̸∈σ (1 - pi). A selection σ identifies a world ψσ composed of the rules of P and a fact ai for each ai ∈ σ. The probability of a world ψ is equal to the probability of the corresponding selection, i.e., P(ψσ) = P(σ). To simplify the notation, when it is clear from the context, we will use P(ψ) and drop the subscript. The log-probability of a selection can be computed by considering summations as log(P (σ)) = ∑ai∈σ log(pi) + ∑ai̸∈σ log(1 - pi). Then, the probability of a world ψ, P(ψ), can be computed from log(P(ψ)) as elog(P(ψ)) . A PASP P with n probabilistic facts in ground(P) has 2n worlds, and the credal semantics requires that each world has at least one answer set. A query is a conjunction of ground literals. The probability of a query q belongs to a range [P(q),P(q)], where the two bounds are called lower and upper probability, respectively, with P(q) = ∑ψi|∀M∈AS(ψi), M|=q P(ψi) and P(q) = ∑ψi|∃M∈AS(ψi), M|=q P(ψi). Note that |AS(ψi)| > 0 as required by the credal semantics. That is, the worlds where the query is true in every answer set (i.e., where the query is cautiously entailed) contribute to both the lower and the upper probability, while the worlds where the query is true only in some answer sets (i.e., the query is bravely entailed) contribute only to the upper probability. To clarify, consider the following example.

Example 3. The following program is one of the possible encodings for the graph 3-coloring task.

r(X) :- n(X), not g(X), not b(X). g(X) :- n(X), not r(X), not b(X). b(X) :- n(X), not r(X), not g(X). edg(X,Y) :- e(X,Y). edg(X,Y) :- e(Y,X). :- edg(X,Y), r(X), r(Y). :- edg(X,Y), g(X), g(Y). :- edg(X,Y), b(X), b(Y).

Consider a graph with four nodes, where two of them have a fixed color:

Suppose that we are uncertain about the presence of edges between nodes. We describe this with the probabilistic facts:

Also suppose that we want to compute the probability that blue is assigned to at least one of the two uncolored nodes. This can be encoded with the rules blue :- b(2) and blue :- b(3) and by asking for the probability of blue. This program has 24 = 16 worlds. For example, in the world where all edges except e(1, 2) are present, we have two answer sets representing two possible color assignments for node 2, either red or blue, while the color of node 3 is fixed to blue in both. So, this world contributes to both the lower and upper probability. Overall, the probability of blue is [0.1816, 1].

MPE in PASP. Let us introduce theMPE problem in PASP. Definition 1. Given a PASP P and a conjunction of ground literals e called evidence, the cautious MPE problem consists in finding the selection σ with the highest associated probability where e is entailed in every answer set of the corresponding world ψσ, i.e.:

while the brave MPE problem consists in finding the selection σ with the highest associated probability where the e is entailed in at least one answer set of the corresponding world ψσ, i.e.:

The results of the two aforementioned problems are respectively called lower and upper MPE states. We use P (MPE(e)) and P (MPE(e)) to denote the probability of the selection (world) representing the lower and upper MPE state, respectively, and explicitly mark the atoms not present in such states by prepending them with not. In what follows, we assume w.l.o.g. that e is a single atom. Indeed, it is possible to add a rule with the conjunction of literals in e in the body and as head a new atom e′ that does not appear elsewhere in the program and considering as evidence e′ (as in Example 3).

Example 4. Consider again Example 3. If we consider as evidence blue as defined in Example 3, we obtain MPE(blue) = {e(1, 2), not e(1, 3), e(2, 4), e(3, 4)} with P(MPE(blue)) = 0.0756 and MPE(blue) = {e(1, 2), not e(1, 3), not e(2, 4), e(3, 4)} with P(MPE(blue)) = 0.3024. Note that, as in this example, the lower and upper MPE states may not coincide.

Theoretical results from [Mau´a and Cozman, 2020] proved that the MPE problem is hard (i.e., for propositional PASP, it lies between NP and Σp3 , depending on the considered ASP fragment) and early approaches to solve this task [Azzolini et al., 2023] were based on projected answer set enumeration [Gebser et al., 2009]. We now provide novel alternative ways to handle the MPE computation.

3 Algebraic Representation of MPE

Second-level algebraic model counting (2AMC) [Kiesel et al., 2022] is a generic framework that extends algebraic model counting [Kimmig et al., 2017].

Definition 2 (2AMC). Given a propositional theory Π whose variables are partitioned into (Vi, Vo), two commutative semirings [Gondran and Minoux, 2008] Ri = (Ri ,⊕i ,⊗i , ni⊕, ni⊗) and Ro = (Ro ,⊕o ,⊗o , no⊕, no⊗), two weight functions, wi and wo, and a transformation function fio mapping the values of Ri to Ro , let T be T = (Π, Vi, Vo, Ri, Ro, wi, wo, fio). 2AMC on T is defined as:

where µ(Vo) is the set of possible assignments to Vo and φ(Π | Io) the set of assignments Ii of Vi such that (Ii, Io) satisfies Π.

Each of the two layers in 2AMC is a tuple Ax = (Vx,RX,wx). So, there is an inner layer Ai = (Vi,Ri,wi) whose values are mapped via a transformation function fio to values of the outer layer Ao = (Vo,Ro,wo). MPE inference in PASP can be cast as a 2AMC, as follows.

Definition 3 (MPE as 2AMC). Consider a PASP P with Herbrand base BP and evidence e. P is transformed into a propositional theory Π with a one-to-one correspondence between the answer sets and the models of Π. This is achieved with the steps of grounding, simplification, cycle breaking, and Clark's completion, as described in [Eiter et al., 2024]. For the innermost layer Ai we have [Azzolini and Riguzzi, 2023a]: as semiring, Ri = (N2 , +, ·, (0, 0), (1, 1)), where + and · are applied component-wise, as variables BP \ F(P), as weight function:

The two components store, respectively, the count of the answer sets where the query is true and the count of all the answer sets. As transformation function, we consider fio(n1, n2) = (vlp, vup, {}, {}) where vlp = 1 if n1 = n2, 0 otherwise, and vup = 1 if n1 > 0, 0 otherwise.

For the outer layer Ao we have the semiring Ro = (R2 × Σ2 , max 4 , times 4 , (0, 0, F(P), F(P)), (1, 1, {}, {})), as variables F(P), and as weight function

where max 4 ((v0, v1, S0, S1), (va, vb, Sa, Sb)) = (vx, vy, Sx, Sy) with vx = v0 and Sx = S0 if v0 > va, else vx = va and Sx = Sa; vy = v1 and Sy = S1 if v1 > vb, else vy = vb and Sy = Sb. times 4 ((v0, v1, S0, S1), (va, vb, Sa, Sb)) = (v0 · va, v1 · vb, S0 ∪ Sa, S1 ∪ Sb). If v0 = va, then Sx = min>(S0, Sa); if v1 = vb, then Sy = min>(S1, Sb), where, in both cases, > is a fixed total order on Σ. The first two components store, respectively, the value associated with the lower and upper MPE states while the last two store the probabilistic facts present in such states.

In other words, in the inner layer, we have the probabilistic facts fixed, and we need to compute whether the current world contributes to the lower or upper MPE state (i.e., if the evidence is cautiously or bravely entailed) while in the outer layer we range over the possible worlds.

4 Logic Based Encodings for MPE

In this section, we propose logic-based encodings to solve the MPE problem in PASP. In particular, we propose a natural ASP(Q) encoding to solve the cautious MPE problem and an ASP one to solve the brave MPE problem. Both rely on the following encoding of probabilistic facts as ASP rules.

Definition 4. Let P be a PASP. worlds(P) denotes the program obtained by encoding every p :: a ∈ P as follows:

where ida is a unique identifier for the probabilistic fact p :: a, w = log(p), and w = log(1 - p).

In this definition, choice rules encode possible selections σ while normal rules derive an atom storing either log(p) if a is chosen in σ; otherwise log(1 - p), for each p :: a ∈ P.

4.1 Cautious MPE Problem in ASP(Q)

Given a PASP P and evidence e, we encode the MPE(e) task by means of an existential ASP(Q) such that quantified answer sets are in one-to-one correspondence with selections that cautiously entail the evidence e and the optimal quantified answer sets correspond to lower MPE states.

Definition 5. Let P be a PASP and e be the evidence, then aspq(P, e) = ∃stP1 ∀stP2 : C : C ω , where P1 = worlds(P), P2 = P(P), C = {← not e}, and C ω = {:∼ prob(W,A) [-W,A]}.

By exploiting such an encoding, each optimal quantified answer set M of aspq(P, e) corresponds to a lower MPE state in which all the atoms in F(P) ∩ M are chosen to be true and the remaining ones in F(P) are false. Thus, all the lower MPE states can be obtained by enumerating optimal quantified answer sets. The associated probability can be obtained by considering the probabilities of the facts selected in the quantified answer set.

Theorem 1. Let P be a PASP, e be an evidence, and Π = aspq(P, e), then M is an optimal quantified answer set of Π iff σ = M ∩ F(P) is a lower MPE state.

Proof Sketch. (⇒) By construction, each answer set M1 of P1 corresponds to a selection σ = M1 ∩ F(P). Then, by fixing M1 in the program P2, answer sets of the program P2 ∪ fixP1 (M1 ) are in one-to-one correspondence with answer sets of the world ψσ identified by σ. According to the coherence of ASP(Q), if for every M2 ∈ AS(P2∪fixP1 (M1 )) the constraint :- not e is satisfied, then M1 is a quantified answer set. This means that for every answer set of ψσ the evidence is entailed and so ψσ cautiously entails e. Moreover, the cost of M1 is obtained by summing up -W for each atom of the form prob(W, Id) that is true w.r.t. M1. By construction, for each p :: a ∈ P, either prob(w, ida) or prob(w, ida) is true w.r.t. M1 and so the cost of M1 is equal to -log(P(σ)). Since an optimal quantified answer set minimizes such a cost, we are indeed maximizing log(P (σ)), and, if M1 is optimal, then σ is a lower MPE state.

(⇐) Here the proof follows by noting that each lower MPE state σ could be mapped to an optimal quantified answer set M = σ ∪ {prob(log(p), ida) | p :: a ∈ P, a ∈ σ} ∪ {prob(log(1 - p), ida) | p :: a ∈ P, a /∈ σ}.

Example 5. Let us consider the PASP problem of Example 3. We can encode MPE(blue) with the following ASP(Q):

%@exists

{e(1,2);e(1,3);e(2,4);e(3,4)}. prob(log(0.6),e12):- e(1,2). prob(log(0.4),e12):- not e(1,2). prob(log(0.1),e13):- e(1,3). prob(log(0.9),e13):- not e(1,3). prob(log(0.2),e24):- e(2,4). prob(log(0.8),e24):- not e(2,4). prob(log(0.7),e34):- e(3,4). prob(log(0.3),e34):- not e(3,4). %@forall r(X) :- n(X), not g(X), not b(X). g(X) :- n(X), not r(X), not b(X). b(X) :- n(X), not r(X), not g(X).

edg(X,Y) :- e(X,Y). edg(X,Y) :- e(Y,X). :- edg(X,Y), r(X), r(Y). :- edg(X,Y), g(X), g(Y). :- edg(X,Y), b(X), b(Y). blue :- b(2). blue :- b(3). n(1..4). r(1). g(4). %@constraint :- not blue. %@global :∼ prob(W,A). [-W,A]

Answer sets of P1 represent selections with their associated probability. For example, consider M1={e(1, 2), e(1, 3), e(3, 4), prob(log(0.6), e12), prob(log(0.1), e13), prob(log(0.8), e24), prob(log(0.7), e34)} ∈ AS(P1). By fixing M1 into P2, we obtain two answer sets of P2 ∪ fixP1 (M1 ), where in the first both nodes 2 and 3 are blue, while in the second nodes 2 and 3 are green and blue, respectively, which are indeed the answer set of the world ψσ with σ = {e(1, 2), e(1, 3), e(3, 4)}. Since in both cases blue is true, the constraint in C is satisfied, M1 is a quantified answer set, and σ cautiously entails blue. The cost of M1 is -log(P(σ)) ≈ 3.3932. Similarly, M ′1 = {e(1, 2), e(2, 4), e(3, 4), prob(log(0.6), e12), prob(log(0.9), e13), prob(log(0.2), e24), prob(log(0.7), e34)} ∈ AS(P1) is a quantified answer set. M ′1 is associated with the selection σ′ = {e(1, 2), e(2, 4), e(3, 4)} so the cost of M ′1 is -log(P(σ′ )) ≈ 2.5829. M1 is dominated by M ′1 , and so not optimal. No better quantified answer set exists, so M ′1 is optimal and σ′ is a lower MPE state with probability 0.0756.

4.2 Brave MPE Problem in ASP

The brave MPE problem can be encoded with an ASP whose optimal answer sets correspond with upper MPE states.

Definition 6. Let P be a PASP and e be an evidence, then asp(P, e) is the program obtained from worlds(P) by adding P(P), the constraint :- not e, and the weak constraint :∼ prob(W, Id) [-W, Id].

Intuitively, rules in worlds(P) model the search for a possible selection and rules in P(P) model possible worlds. Finally, the constraint :-not e forces the entailment of the evidence, whereas the weak constraint allows the maximization of the sum of the log-probability associated with probabilistic facts. Thus, to obtain all the upper MPE states it is sufficient to enumerate all the optimal answer sets of asp(P, e).

Theorem 2. Let P be a PASP, e be an evidence, and P = asp(P, e). Then, M is an optimal answer set for P if and only if σ = M ∩ F(P) is an upper MPE state.

Proof Sketch. (⇒) By construction, there is a one-toone correspondence between the answer sets of worlds ψσ that bravely entails the evidence e and the answer sets of asp(P, e). Thus, for each M ∈ AS(asp(P, e)), there exists a selection σ = M ∩F(P) such that, by removing atoms over predicate prob/2 fromM, we obtain M ′ ∈ AS(ψσ) such that M ′ |= e. Moreover, each answer set M of asp(P, e) has an associated cost that, as for the ASP(Q) encoding, is obtained by summing up -W for each atom of the form prob(W, Id) that is true w.r.t. M. Thus, as for the previous encoding, we are indeed maximizing log(P(σ)) and so an optimal answer set corresponds to an upper MPE state.

(⇐) Here the proof follows by noting that an upper MPE state σ could be mapped to an optimal answer set M = M ′ ∪ {prob(log(p), ida) | p :: a ∈ P, a ∈ σ} ∪ {prob(log(1 - p), ida) | p :: a ∈ P, a /∈ σ}, where M ′ ∈ AS(ψσ).

Example 6. Let P be the PASP of Example 3. MPE(blue) can be encoded as asp(P, blue). The resulting ASP is the ASP(Q) of Example 5 where all subprograms are merged into a unique ASP. For the sake of compactness, we avoid reporting it explicitly. Here, M1 = {n(1), n(2), n(3), n(4), g(4), r(1), e(1, 2), e(3, 4), prob(log(0.6), e12), prob(log(0.9), e13), prob(log(0.8), e24), prob(log(0.7), e34), b(2), b(3), blue, edg(1, 2), edg(3, 4), edg(2, 1), edg(4, 3)} is an optimal answer set of asp(P, blue). M1 can be mapped to the selection σ = {e(1, 2), e(3, 4)}. By removing atoms over the predicate prob/2 from M1, we can obtain M ′1 ∈ AS(ψσ) such that M ′1 |= blue. The cost of M1 = -log(P(σ)) ≈ 1.1960. No answer sets better than M1 exists, so σ is an upper MPE state with probability 0.3024.

5 Experimental Evaluation

The experiments were executed on a machine running at 3.7 GHz with 32 GB of RAM and a time limit, for each instance, of 3600 seconds (1 hour). We used the bash command time to extract the execution time and collected the real values. Source code and datasets are available at https://t.ly/kqulc.

5.1 Datasets Description

We consider two types of datasets: stratified and nonstratified. For both types, we randomly generated instances of increasing size (a fixed seed ensures reproducibility).

Stratified Dataset. Stratified dataset refers to PASP where the underlying ASP is a stratified program. Thus, in this category we considered the well-known reachability problem, with graphs following three different structures: Barab´asi Albert, Erd˝os-R´enyi, and complete. For each type, we generated directed graphs with an increasing number of nodes (considered as the size of the instance), starting from 2 and up to 100. We considered two variations, having the same edges but different probabilities: fixed to 0.4 and random (uniform) between 0.001 and 0.999. We obtained 588 programs in total.

Non-Stratified Datasets. Here, we considered six different benchmarks. For all, the evidence is the atom qr. For each of the first four benchmarks, an instance of size i has a total number of i probabilistic facts having the signature aj/0 with j ∈ {0, . . . , i - 1}. An instance of size i of the dataset p1 has i/2 rules of the form qrj; nqrj :- ⋄ aj with j even where ⋄ can be either not or omitted, i/2 rules of the form qrk-1 :- ⋄ ak with k odd and ⋄ as before, and a rule qr :- ∧ qri with i even. An instance of size i of the dataset p2 has i/2 rules of the form qrj; nqrj :- ◦, ⋄aj with j even where ◦ can be qrk-1 or nqrk-1 and ⋄ can be not or omitted (except when j = 0, where not is omitted), i/2 rules of the form qrk :- ◦, ⋄ak with k odd and the rest as before, and i rules qr :- qri. An instance of size i of the dataset p3 has i rules of the form ∨j∈{0,i-1} qrj :- ⋄ai and a rule qr :- qrj for each j ∈ {0, i - 1}. An instance of size i of the dataset p4 has one rule with head qr; nqr and body composed of a conjunction of random probabilistic facts where each one can be also considered as negated, and a rule with head qr and body as before. Note that here some of the probabilistic facts may not be considered in the two rules. For these benchmarks we randomly generated instances with sizes from 5 up to 100 by sampling values for ◦ and ⋄ with uniform distributions. In addition, we considered both the well known graph coloring (col) problem where the edges are considered as probabilistic facts and the evidence is the color of a given node, and the friend-smokers (smk) benchmark [Totis et al., 2023], representing a network of people where the smoking behavior is influenced by friendship and existing pathologies. Here, the evidence encodes whether at least one individual smokes. An instance of size i of col has i probabilistic facts and encodes a graph with i nodes. We generated instances starting with size 7 and up to 100 by adding random edges between nodes. An instance of size i of smokers involves i people and has 5i - 1 probabilistic facts in total. We generated instances starting from size 2 and up to 30, also by adding pathologies and connections between people. In all instances, we ensured that every world has at least one answer set (as required by the credal semantics) and the lower MPE state always exists. Also here we consider two variations, with probabilities fixed to 0.4 and random. We have 1014 programs in total.

5.2 Compared Algorithms

In these experiments, we compare the proposed approaches with the ones available in the literature: PASTA [Azzolini et al., 2022; Azzolini and Riguzzi, 2023b], cplint [Bellodi et al., 2020], ProbLog [Shterionov et al., 2015], and plingo [Hahn et al., 2024]. plingo is a recently introduced system to perform inference in a (subset of) ProbLog programs using the ASP solver clingo [Gebser et al., 2019] as a backend. Essentially, plingo rewrites weighted rules [Lee and Yang, 2017] into ASP and then uses clingo to compute answer sets. To model the MPE problem in plingo we need to specify probabilistic facts with external atoms in this way: for a probabilistic fact p :: a, we add a :- &problog(p). Furthermore, the evidence e is encoded as &evidence(e). We implemented the 2AMC method of Section 3 into the aspmc [Eiter et al., 2021; Eiter et al., 2024] solver, that we indicate with aspmc in the following. For ASP, we used the solver clingo with the encoding of Section 4.2. In ASP and ASP(Q) implementations, we discretize log-probabilities as ⌊k · log(p)⌋ and use k = 103 . Moreover, for both ASP and plingo we used the clingo option --opt-strategy=usc [Andres et al., 2012] which revealed to be an effective strategy for both solvers.

5.3 Results

The goal of our experiments was to empirically answer the following questions: Q1) is knowledge compilation effective in solving MPE in PASP? Q2) is ASP a good candidate for MPE when considering stratified programs? Q3) does the probability associated with facts influence the runtime? Q4) is ASP(Q) a good approach for solving MPE in PASP? Q5) does the structure of the program influence the runtime?

Results on stratified datasets. In these datasets, every instance has a unique answer set per world, so lower and upper probability coincide and also lower and upper MPE states (that we simply call MPE states). In this setting, both logicbased approaches can be used but, based on their own complexity, we consider only the ASP-based one. Concerning cplint and ProbLog, instead, it is important to point out that if the program contains probabilistic facts that are not relevant to the computation of the probability, these facts are ignored. Thus, the states these two systems find are not the MPE states, but they can be straightforwardly extended to be so. If S′ is the state computed with either one of the two tools, the MPE state is given by S = S′ ∪ ⋃ai∈F∩S′ p(ai) where for a probabilistic fact pi :: ai, p(ai) returns {ai} if pi > 0.5, else it returns {}, and the probability of such a state can be computed accordingly.

Figure 1 reports the cactus plot for the experiments on stratified datasets. We recall that instances in a cactus plot are sorted by execution time and a point (x, y) indicates that a given system solved the x-th instance in y seconds. PASTA is the slowest algorithm, being it based on (projected) enumeration. aspmc closely follows it, despite being based on knowledge compilation. This is probably due to the grounding phase, which also considers parts of the program not relevant to the computation of the probability of the evidence. This has a high impact, in particular on Barab´asi Albert graphs, where often only a few edges are relevant for the computation. ProbLog can solve approximately twice the instances of cplint. ASP and plingo are the best performing approaches with comparable execution times. For both, even the largest instance is solved in approximately 1 second. This provides a partial positive answer to Q1 and positive answer to Q2. KC in ProbLog and cplint is more effective than KC in aspmc, since it considers only the relevant part of the program.

Results on non-stratified datasets. In non-stratified datasets each world may have one or more answer sets, thus, we compare only aspmc, PASTA, and ASP(Q) + ASP on the computation of both lower and upper MPE states. Our approaches based on ASP(Q) and 2AMC are, to the best of our knowledge, the only ones, in addition to PASTA, that can compute the lower MPE state in PASP. Note that, aspmc and PASTA compute both upper and lower MPE states in one single call, while ASP(Q) and ASP computes only the lower and upper MPE states, respectively. Thus, for a fair comparison, we sum the execution times of the two for each instance. However, it is important to point out that the execution time of ASP is negligible (less than 1 second) and solves all of them, so the discussion below mainly considers ASP(Q).

Table 1 shows the largest solvable instance and the cumulative execution time on each dataset. The superscripts r and f denote the instances with random and fixed associated probability, respectively. For PASTA the total execution time and the number of instances solved seems not to be affected by the choice of probability, except for p1f : here, the instance of size 24 is solvable within the time limits while the instance of same size with random probabilities cannot be solved. The independence between the choice of the probability and of the execution time is expected in PASTA, since it adopts enumeration and the number of generated answer sets does not depend on the probabilities associated with probabilistic facts. PASTA always halts for the time limit. For aspmc, the execution always halts due to an out-of-memory error. The number of solvable instances in ASP(Q), differently from the other solvers, is highly dependent from the probabilities associated to probabilistic facts: on four datasets with fixed probabilities, it can solve all the instances, while this does not happen when random probabilities are considered. This is due to the upper-bound improving algorithm employed by the ASP(Q) system which starts from a quantified answer set with a given cost and searches for a better one until the program becomes unsatisfiable. In this scenario, proving unsatisfiability can be hard, especially when many worlds have costs that are better than the current upper-bound but none of them cautiously entail the query (i.e., they do not contribute to lower MPE state). ASP(Q) always halts due to timeout. For some datasets, ASP(Q) has dramatically better performance: in p3f , aspmc stops at size 20, PASTA gets to size 23, while ASP(Q) can solve all. This is reflected in the total number of solved instances, as shown in the cactus plot of Figure 2. This answers positively Q4 in general and Q3 for ASP(Q) (but not for PASTA and aspmc). Overall, KC is also beneficial here (Q1), but the clever encoding of ASP(Q) that prunes dominated solutions during the search scales better.

6 RelatedWork

Related work falls into two categories: alternative semantics for ASP extended with constructs representing uncertainty and alternative MPE encodings. Other semantics, still targeting ASP, are: P-log [Baral et al., 2009], LPMLN [Lee and Wang, 2016; Lee and Yang, 2017], smProbLog [Totis et al., 2023], and the L-credal semantics [Rocha and Gagliardi Cozman, 2022; Mau´a et al., 2024]. These differ on how the uncertainty is distributed among the different answer sets of the program. dPASP [Geh et al., 2024] is a tool to perform inference in PASP, but it does not support MPE. The authors of [Lee and Yang, 2017] were the first to propose the use of weak constraints to compute the most probable stable model, albeit in the LPMLN semantics. Alternative encodings can be used to model MPE in PASP, among these, disjunctive ASP and advanced techniques such saturation [Eiter and Gottlob, 1995; Dantsin et al., 2001], but they can be considered less intuitive than ASP(Q). Moreover, the stable-unstable semantics [Bogaerts et al., 2016], and quantified answer set semantics [Fandinno et al., 2021], can be also used to model problems of such complexity but they do not support explicitly optimization statements that allow for a natural maximization of the probability of probabilistic worlds. Finally, note that all the available systems that can performMPE for PASP (including those handling syntactic fragments of the formalism) are described and empirically compared in Section 5.

7 Conclusion

In this paper, we proposed three alternative techniques for solving the MPE problem in PASP. We start from an approach based on knowledge compilation and second-level algebraic model counting. Then, we proposed two logic-based encodings, one in ASP for the upper MPE state, and one that leverages ASP(Q), specifically targeting the lower MPE state. A broad experimental evaluation shows that ASP(Q) + ASP are the most effective solutions to solve MPE on non-stratified programs. There are many directions for future work, such as studying the considered tasks under different semantics and speeding up even more the execution time adopting multishot [Gebser et al., 2019] approaches.

Acknowledgements

This work has been partially supported by Spoke 1 "FutureHPC & BigData" of the Italian Research Center on HighPerformance Computing, Big Data and Quantum Computing (ICSC) funded by MUR Missione 4 - Next Generation EU (NGEU), by the Italian Ministry of Industrial Development (MISE) under project EI-TWIN n. F/310168/05/X56 CUP B29J24000680005, and by the Italian Ministry of Research (MUR) under projects: PNRR FAIR - Spoke 9 - WP 9.1 CUP H23C22000860006, Tech4You CUP H23C22000370006, and PRIN PINPOINT CUP H23C22000280006. DA and FR are members of the Gruppo Nazionale Calcolo Scientifico - Istituto Nazionale di Alta Matematica (GNCS-INdAM).