Credal probabilistic facts and credal annotated disjunctions have been recently introduced in the Probabilistic Answer Set Programming framework to manage imprecise probabilities. In a recent paper, inference within this formalism has been cast as a constrained non-linear optimization problem. In this paper, we review that contribution. Probabilistic Answer Set Programming (PASP) combines the efectiveness in solving combinatorial problems of Answer Set Programming with the flexibility in modelling complex distributions of Probabilistic Programming. Recently [1], PASP has been extended with primitives called credal probabilistic facts and credal annotated disjunctions to model imprecise probabilities, i.e., probabilities described by a range, rather than a sharp value. Here, we summarize the paper “Inference in Probabilistic Answer Set Programs with Imprecise Probabilities via Optimization” presented at the UAI 2024 conference [2], where we considered the inference task as a constrained non-linear optimization problem. Empirical results showed the efectiveness of this approach. The paper is structured as follows: Section 2 surveys the background knowledge, Section 3 shows how to cast inference as an optimization problem and discusses the experimental evaluation, and Section 4 concludes the paper.
Probabilistic facts [
A probabilistic answer set program under the credal semantics (PASP) is composed by an answer set
program extended with probabilistic facts [
∈ ̸∈ P() = P() =
∑︁ |∀∈(), |=
∑︁ |∃∈(), |= (), ().
P() and P() are called, respectively, lower and upper probability. The credal semantics requires
that every world has at least one answer set [
Credal probabilistic facts and credal annotated disjunctions (ADs) are two possible constructs to
model imprecise probabilities [
[, ] :: with 0 ≤ ≤ ≤ 1 and
[ 1, 1] :: ℎ1; . . . ; [ , ] :: ℎ : − 1, . . . , with 0 ≤ ≤ ≤ 1, + ∑︀̸= ≥ 1, + ∑︀̸= ≤ 1, ∀ ∈ {1, . . . , }. We will refer to PASP extended with either one of the two constructs as PASP with imprecise probabilities.
We proposed to perform inference in PASP with uncertain probabilities via optimization. Briefly, we extract a symbolic formula from the NNF representation of the program where the probabilities associated with credal facts and credal AD are kept symbolic and then call an optimization solver to minimize/maximize such formulas subject to constraints deriving from the structure of credal probabilistic facts and credal ADs. Namely, if () and () are the formulas for the lower and upper probability for a query and = { 1, . . . } denotes the set of probability parameters associated with credal probabilistic facts, the lower and upper probability of a query can be computed, respectively, as and
() s.t . ∈ [, ], ∀ ∈ {1, . . . , }
() s.t . ∈ [, ], ∀ ∈ {1, . . . , }.
Let us clarify this with an example.
Example 1. Consider the following PASP with two credal facts. [0.3,0.4]::a. [0.4,0.9]::b. q:- a. q ; r :- b.
First, we convert it into pa::a. pb::b. q:- a. q ; r :- b. where and are parameters. By traversing the NNF for the query we obtain two equations: () = for the lower probability, and (, ) = − · ( − 1) for the upper probability. P() is computed by minimizing () with ∈ [0.3, 0.4], obtaining 0.3. For P(), we need to maximize (, ) with ∈ [0.3, 0.4] and ∈ [0.4, 0.9]. In this case, we obtain 0.94. So, [P(), P()] = [0.3, 0.94].
If credal ADs are present, the optimization process becomes more involved and first it requires
converting each credal AD into a combination of probabilistic facts and normal rules [
Then, the optimization process also needs to consider constraints on the probabilities on the credal facts.
With credal ADs, the optimization problem for the lower probability is () .. · ∏︁(1 − ) − ≥ 0,
< − · ∏︁(1 − ) ≥ 0,
< ∀ ∈ {1, . . . , }, ∀ ∈ {1, . . . , } assuming = 1, where is the probability associated with the -th probabilistic fact related to the -th head of the -th AD and is the number of disjuncts in the -th AD. This requires imposing 2 · constraints for each credal AD with heads. The problem to solve for the computation of the upper probability is analogous. More concretely, with the credal AD shown above, we have the following set of constraints: 1 − 0.1 ≥ 0, 0.3 − 1 ≥ 0, (1 − 1) · 2 − 0.2 ≥ 0, 0.4 − (1 − 1) · 2 ≥ 0, (1 − 1) · (1 − 2) − 0.4 ≥ 0, and 0.6 − (1 − 1) · (1 − 2) ≥ 0.
The overall algorithm is as follows: first, credal facts and credal ADs are converted to remove ranges. Then, the program is converted into a NNF, and two equations are extracted, which are simplified to reduce the number of operations involved. Lastly, these are sent to a non-linear optimization solver that can manage non-linear constraints.
The algorithm was implemented in Python and the experimental evaluation was conducted by
considering SymPy [
In this paper, we summarized [