=Paper=
{{Paper
|id=Vol-3915/paper-6
|storemode=property
|title=Summary of Inference in Probabilistic Answer Set Programs with Imprecise Probabilities via Optimization (Short paper)
|pdfUrl=https://ceur-ws.org/Vol-3915/Paper-6.pdf
|volume=Vol-3915
|authors=Damiano Azzolini,Fabrizio Riguzzi
|dblpUrl=https://dblp.org/rec/conf/aiia/AzzoliniR24
}}
==Summary of Inference in Probabilistic Answer Set Programs with Imprecise Probabilities via Optimization (Short paper)==
https://ceur-ws.org/Vol-3915/Paper-6.pdf
Summary of Inference in Probabilistic Answer Set
Programs with Imprecise Probabilities via Optimization
Damiano Azzolini1,* , Fabrizio Riguzzi2
1
Department of Environmental and Prevention Sciences β University of Ferrara
2
Department of Mathematics and Computer Science β University of Ferrara
Abstract
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.
Keywords
Probabilistic Answer Set Programming, Optimization, paper formatting, Imprecise Probabilities
1. Introduction
Probabilistic Answer Set Programming (PASP) combines the effectiveness in solving combinatorial
problems of Answer Set Programming with the flexibility in modelling complex distributions of Proba-
bilistic 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 effectiveness 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.
2. Background
Probabilistic facts [3] are of the form π :: π with the meaning that π is the probability associated with
the fact π. According to the distribution semantics [4], a world is identified by including or not each
probabilistic fact in the program. π (π€), the probability of a world π€, is computed as:
βοΈ βοΈ
π (π€) = ππ (1 β ππ ).
ππ βπ€ ππ ΜΈβπ€
A probabilistic answer set program under the credal semantics (PASP) is composed by an answer set
program extended with probabilistic facts [5]. The credal semantics describes the probability of a query
π, i.e., a conjunction of ground atoms, with a range [P(π), P(π)] where
βοΈ
P(π) = π (π€π ),
π€π |βπβπ΄π(π€π ), π|=π
βοΈ
P(π) = π (π€π ).
π€π |βπβπ΄π(π€π ), π|=π
AIxIA 2024 Discussion Papers - 23rd International Conference of the Italian Association for Artificial Intelligence, Bolzano, Italy,
November 25β28, 2024
*
Corresponding author.
$ damiano.azzolini@unife.it (D. Azzolini); fabrizio.riguzzis@unife.it (F. Riguzzi)
Β© 2025 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
P(π) and P(π) are called, respectively, lower and upper probability. The credal semantics requires
that every world has at least one answer set [6]. Inference in these programs can be cast as a Second
Level Algebraic Model Counting (2AMC) problem [7]. aspcs is a framework that extends aspmc [8]
allowing inference in PASP, that converts the program into a Negation Normal Form (NNF, which
is a rooted directed acyclic graph where internal nodes are labeled with AND (conjunction) and OR
(disjunction) and leaves are associated with literals), via a process called knowledge compilation [9].
This representation allows fast inference.
Credal probabilistic facts and credal annotated disjunctions (ADs) are two possible constructs to
model imprecise probabilities [1]. Their syntaxes are, respectively,
[πΌ, π½] :: π
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.
3. Inference via Optimization
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
πππππππ§π πππ (π)
s.t. ππ β [ππ , π’π ], βπ β {1, . . . , π}
and
πππ₯ππππ§π ππ’π (π)
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 [10]. For example,
[0.1,0.3]::red;[0.2,0.4]::green;[0.4,0.6]::blue.
is expanded into
p1::f1.
p2::f2.
red :- f1.
green :- not f1, f2.
blue :- not f1, not f2.
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 con-
sidering SymPy [11] to simplify equations and SciPy [12] as optimization solver with the COBYLA [13]
and SLSQP [14] algorithms. Empirical results showed that: i) solving the optimization problem by
considering a simplified version of the equations is much faster than considering the equations directly
extracted from the NNF, even if the simplification process may be slow (for larger datasets, this takes
more than 50% of the total execution time); ii) this approach is much faster than already existing solver
based on enumeration [15]; iii) COBYLA is often more efficient and effective than SLSQP.
4. Conclusions
In this paper, we summarized [2] where inference in probabilistic answer set programs under the credal
semantics with imprecise probabilities has been cast as a constrained non-linear optimization problem.
Empirical results against an already existing solver based on enumeration shows the effectiveness of
this approach.
References
[1] D. D. MauΓ‘, F. G. Cozman, Specifying credal sets with probabilistic answer set programming, in:
International Symposium on Imprecise Probabilities and Their Applications, 2023.
[2] D. Azzolini, F. Riguzzi, Inference in probabilistic answer set programs with imprecise probabilities
via optimization, in: N. Kiyavash, J. M. Mooij (Eds.), Proceedings of the Fortieth Conference on
Uncertainty in Artificial Intelligence, volume 244 of Proceedings of Machine Learning Research,
PMLR, 2024, pp. 225β234.
[3] L. De Raedt, A. Kimmig, H. Toivonen, ProbLog: A probabilistic Prolog and its application in link
discovery, in: M. M. Veloso (Ed.), 20th International Joint Conference on Artificial Intelligence
(IJCAI 2007), volume 7, AAAI Press, 2007, pp. 2462β2467.
[4] T. Sato, A statistical learning method for logic programs with distribution semantics, in: L. Sterling
(Ed.), Logic Programming, Proceedings of the Twelfth International Conference on Logic Program-
ming, Tokyo, Japan, June 13-16, 1995, MIT Press, 1995, pp. 715β729. doi:10.7551/mitpress/
4298.003.0069.
[5] F. G. Cozman, D. D. MauΓ‘, The joy of probabilistic answer set programming: Semantics, complexity,
expressivity, inference, International Journal of Approximate Reasoning 125 (2020) 218β239.
doi:10.1016/j.ijar.2020.07.004.
[6] G. Brewka, T. Eiter, M. TruszczyΕski, Answer set programming at a glance, Communications of
the ACM 54 (2011) 92β103. doi:10.1145/2043174.2043195.
[7] D. Azzolini, F. Riguzzi, Inference in probabilistic answer set programming under the credal
semantics, in: R. Basili, D. Lembo, C. Limongelli, A. Orlandini (Eds.), AIxIA 2023 - Advances in
Artificial Intelligence, volume 14318 of Lecture Notes in Artificial Intelligence, Springer, Heidelberg,
Germany, 2023, pp. 367β380. doi:10.1007/978-3-031-47546-7_25.
[8] T. Eiter, M. Hecher, R. Kiesel, aspmc: New frontiers of algebraic answer set counting, Artificial
Intelligence 330 (2024) 104109. doi:10.1016/j.artint.2024.104109.
[9] A. Darwiche, P. Marquis, A knowledge compilation map, Journal of Artificial Intelligence Research
17 (2002) 229β264. doi:10.1613/jair.989.
[10] L. De Raedt, B. Demoen, D. Fierens, B. Gutmann, G. Janssens, A. Kimmig, N. Landwehr, T. Man-
tadelis, W. Meert, R. Rocha, V. Costa, I. Thon, J. Vennekens, Towards digesting the alphabet-soup
of statistical relational learning, in: NIPS 2008 Workshop on Probabilistic Programming, 2008.
[11] A. Meurer, C. P. Smith, M. Paprocki, O. ΔertΓk, S. B. Kirpichev, M. Rocklin, A. Kumar, S. Ivanov, J. K.
Moore, S. Singh, T. Rathnayake, S. Vig, B. E. Granger, R. P. Muller, F. Bonazzi, H. Gupta, S. Vats,
F. Johansson, F. Pedregosa, M. J. Curry, A. R. Terrel, v. RouΔka, A. Saboo, I. Fernando, S. Kulal,
R. Cimrman, A. Scopatz, SymPy: symbolic computing in python, PeerJ Computer Science 3 (2017)
e103. doi:10.7717/peerj-cs.103.
[12] P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski,
P. Peterson, W. Weckesser, J. Bright, S. J. van der Walt, M. Brett, J. Wilson, K. J. Millman, N. Mayorov,
A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, Δ°. Polat, Y. Feng, E. W. Moore, J. VanderPlas,
D. Laxalde, J. Perktold, R. Cimrman, I. Henriksen, E. A. Quintero, C. R. Harris, A. M. Archibald,
A. H. Ribeiro, F. Pedregosa, P. van Mulbregt, SciPy 1.0 Contributors, SciPy 1.0: Fundamental
Algorithms for Scientific Computing in Python, Nature Methods 17 (2020) 261β272. doi:10.1038/
s41592-019-0686-2.
[13] M. J. D. Powell, A direct search optimization method that models the objective and constraint
functions by linear interpolation, in: S. Gomez, J.-P. Hennart (Eds.), Advances in Optimiza-
tion and Numerical Analysis, Springer Netherlands, Dordrecht, 1994, pp. 51β67. doi:10.1007/
978-94-015-8330-5_4.
[14] D. Kraft, Algorithm 733: TOMP-fortran modules for optimal control calculations, ACM Transac-
tions on Mathematical Software 20 (1994) 262β281. doi:10.1145/192115.192124.
[15] R. L. Geh, J. Goncalves, I. C. Silveira, D. D. Maua, F. G. Cozman, dPASP: A comprehensive
differentiable probabilistic answer set programming environment for neurosymbolic learning and
reasoning, arXiv (2023).