One natural approach to probabilistic logic programming is Nilsson's probabilistic logic. We discuss the basic framework in the propositional setting, some reasoning ideas and extensions that allow handling inconsistent information. We then discuss its relationship to probabilistic epistemic argumentation. Roughly speaking, probabilistic epistemic argumentation is to classical argumentation as Nilsson's probabilistic logic is to classical logic. We discuss similarities and diferences between the two and in which scenarios one approach may be better suited than the other.
https://www.ipvs.uni-stuttgart.de/institute/team/Potyka-00001/ (N. Potyka)
© 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
Our focus here is on Nilsson’s probabilistic logic [
Another popular knowledge representation formalism closely related to logic is
argumentation. Argumentation can be roughly divided into structured approaches [
The remainder of this paper is structured as follows: We give an introduction to Nilsson’s probabilistic logic in Section 2. We start with a simple language in Section 2.1 and explain the basic reasoning problem in Section 2.2. In Section 2.3, we discuss some important extensions of the language. In particular, we explain the idea of relational extensions by means of a larger example. We finish the section with an overview of some ideas to make probabilistic logic inconsistency-tolerant. In Section 3, we give an analogously structured overview of epistemic probabilistic argumentation. We do not assume any familiarity with argumentation and sketch all necessary basics. As we will explain later, we will use some non-standard notation, to highlight the relationships to Nilsson’s probabilistic logic. Again, we will start from the basic framework and then discuss basic reasoning problems, extensions of the basic language, give a larger example and explain how to make the framework robust against inconsistencies. Along the way, we will highlight similarities and diferences to Nilsson’s probabilistic logic and why both frameworks are interesting in their own right. We close the paper with some conclusions and some potential ideas for future research in the area.
We start from a classical propositional language defined over a finite set of propositional atoms using the logical connectives ¬, ∧, ∨, →, ↔. An interpretation ∶ → {0, 1} is a mapping from atoms to truth values, where we associate with 0 and with 1. We let Int denote the set of all interpretations. The interpretation of complex formulas is defined as usual, for example, (¬ ) = 1 − ( ) and ( ∧ ) = ( ) ⋅ () . We say that satisfies a formula if ( ) = 1 and call a model of in this case. We let Mod( ) = { ∈ Int ∣ satisfies } denote the models of .
The conceptual idea of Nilsson’s probabilistic logic is simple. In the language of probability
theory, we understand interpretations as elementary events and associate formulas with events
by identifying them with the set of their models. What probabilistic logic adds to probability
theory is a simple formal language to describe events. Formally, a probabilistic formula is
an expression of the form ( )[] , where is a formula in our classical logical language and
∈ [
Nilsson’s propositional probabilistic logic is already completely defined. if ( ) = . With this, Two probabilistic interpretations that satisfy 1.
A probabilistic knowledge base is a finite set of probabilistic formulas. There are two fundamental reasoning problems. The probabilistic satisfiability problem asks if there is a probabilistic interpretation that satisfies every probabilistic formula in . If is satisfiable, we are interested in what
entails about the probability of formulas. It may come as a surprise to the reader that we actually cannot necessarily derive point probabilities. This should be clear for the empty knowledge base as it is satisfied by every probabilistic interpretation. Therefore, for every formula, we can only entail that the probability must be between 0 and 1. However, even in non-trivial cases, our knowledge bases do not necessarily entail point probabilities. Example 2.1. Consider the knowledge base 1 = {()[0.5], ( → )[0.5]} interpretations. It is easy to check from the definition that they satisfy 1 . Table 1 shows two . However, we have 1() = 0 and 2() = 0.5 . By doing a more sophisticated analysis, one can actually show that if there are two probability distribution that satisfy and assigns probabilities 1 and 2 to a formula , then for every ∈ [
1, 2], there must be another probability distribution that satisfies and assigns probability to . In other words, the entailed probabilities form an interval. In our example, one can check that
entails that the probability of must be in the interval [0, 0.5].
Since the entailed probabilities form an interval (a point probability is the special case of an interval of length 0), the entailment problem is usually solved by computing the lower and upper bound. This leads to two optimization problems. Given a probabilistic knowledge base and a formula over the same language, the probabilistic entailment problem is to solve the following minimization and maximization problem:
min / max ( ) subject to satisfies .
. Both the probabilistic
satisfiability and the entailment problems are linear optimization problems [
correspond to Krom clauses [
( ∣ )[, ] if ≤ ( ∧)
( ) Since knowledge bases generally entail interval probabilities, a first natural extension is to allow interval probabilities in knowledge bases. Probabilistic formulas have then the form ( )[, ] and a probabilistic interpretation satisfies such a formula if ≤ ( ) ≤ . Computationally, nothing changes for the satisfiability and entailment problem. The optimization problems remain exponentially large linear optimization problems.
Another important extension are conditional probabilities. Sometimes people tend to apply probabilistic implications instead, but it is important to note that they do not have the same meaning. ( → )[] says that the probability that the statement → is true is . It does not speak about the probability of under the assumption that is true. The latter is indeed what conditional probability captures. Probabilistic conditionals are written in the form ( ∣ )[, ] and can be read as ’the conditional probability of given is between and ’. Roughly speaking, satisfaction is defined by the usual definition of conditional probability. That is, satisfies ≤ . However, this expression is undefined if ( ) = 0 . Therefore, ≤ (¬ ∨ ) ≤ for ( ∣ )[, ]
. the precise definition is usually that satisfies ( ∣ )[, ] if ⋅ ( ) ≤ ( ∧ ) ≤ ⋅ ( ) which is obtained from the original inequality by multiplying all terms by ( ) . This form has the additional advantage that it again corresponds to linear inequalities, which means that the probabilistic satisfiability and entailment problem again maintain the original structure.
and there is some philosophical
discussion about potential advantages and disadvantages of this stricter definition of satisfaction.
However, one can show that, in most cases, it does not make a big diference for the entailed
probabilities [
, just is ≤ ( → ) ≤ , or equivalently, , which is clearly diferent from the condition ⋅ ( ) ≤ ( ∧ ) ≤ ⋅ ( )
When allowing conditionals in the knowledge base, it is natural to also allow conditionals in queries. The entailment problem then, more generally, becomes
min / max ( ∣ )
subject to satisfies .
For ≡ ⊤ , one obtains the original problem. While conditional probabilities lead to a non-linear
objective function of the optimization problem, fractional programming techniques can be
applied to transform the problem into an equivalent linear optimization problem again [
In the following, we can simply assume that probabilistic knowledge bases contain only conditionals of the form ( ∣ )[, ]
. For = , we get the special case of point probabilities and for ≡ ⊤ , we get the special case of unconditional probabilistic formulas. Implementations benefit from treating these special cases separately, but the algorithmic complexity will change only by a constant. The first example shows again that we may entail interval probabilities even if all conditionals in the knowledge base contain point probabilities. The rough intuitive reasoning in this example is as follows: We know that is a bird and that is a cat. Therefore, there is a 90% chance that is larger than . In this case, there is only a 10% chance that attacks . This makes up for the lower bound 0.09. However, there is also a 10% chance that is not larger than . In this case, we can say nothing about the probability that attacks , which basically makes up for the 10% uncertainty that are reflected in the upper bound 0.19. The probabilities in this example have been computed with the Java library Log4KR that can be downloaded as part of the Kreator project1. The documentation of the library can be found in the appendix of [20].
Finally, let us mention that the language can be extended further indefinitely. For example, one can take the logical closure of probabilistic formulas (probabilistic formulas are then the atoms of a boolean language) or assign probabilities to probabilistic formulas that express the degree of belief that the degree of belief in the original formula is correct (second-order probabilities). This ideas can be applied repeatedly, so that an infinite number of possible extensions of the basic language exists. However, the computational problems also become significantly harder, so that we will not discuss these extensions here. A systematic investigation and classification of such extensions can be found in [ 21].
When a classical knowledge base is inconsistent, it entails everything. This is one of the few properties that do not generalize from classical to Nilsson’s probabilistic logic immediately. When a probabilistic knowledge base is inconsistent, there is no interpretation that satisfies the knowledge base. Therefore, the optimization problem corresponding to the probabilistic entailment problem simply has no solution. One may close the definition gap by just saying that it entails arbitrary conditionals in this case to maintain consistency with classical logic. In practice, it does not make a big diference because the entailment results would be meaningless in this case. What seems more important is a way to deal with inconsistent knowledge bases. Like in classical logic, one could try to repair the knowledge base or define new reasoning procedures that can derive non-trivial results from inconsistent knowledge bases. Some examples for approaches to repair inconsistent probabilistic knowledge bases can be found in [22, 23, 24]. Some inconsistency-tolerant reasoning approaches can be found in [25, 26].
We discuss the inconsistency-tolerant reasoning approach in [26] in a little bit more detail
because it allows generalizing many reasoning problems (including the probabilistic entailment
problem) to inconsistent knowledge bases without changing their asymptotic complexity. The
conceptual idea is very simple. The probabilistic entailment problem is undefined when a
knowledge base is unsatisfiable. To overcome the problem, one can consider probability
distributions that satisfy the knowledge base ’as well as possible’. One way to do this is to consider
probability distributions that violate the knowledge base in a minimal way. The violation can
be measured with respect to the linear constraints that encode the meaning of conditionals in
the knowledge base [27]. It is interesting to note that the problem of computing the degree
1https://sourceforge.net/projects/kreator-ide/
of violation can be solved by a linear optimization problem with almost the same structure
as the probabilistic satisfiability problem. Once the degree of violation has been computed, a
generalized probabilistic entailment problem can be solved by a linear optimization problem
with almost the same structure as the probabilistic entailment problem. In particular, if the
knowledge base is consistent, the generalized probabilistic entailment results are equal to the
standard probabilistic entailment results. Furthermore, the generalized probabilistic entailment
problem has a continuity property that guarantees that when a knowledge base is close to a
consistent knowledge base, the generalized reasoning results will be close to the reasoning
results under the consistent knowledge base [
While Nilsson’s probabilistic logic extends classical logic, probabilistic epistemic argumentation
[
Instead of a set of propositional atoms, we now have a set of abstract arguments that we again denote by . For our purposes, an argument is simply something that can be accepted or rejected. We refer to [29] for a more sophisticated discussion. Instead of having conditionals that express relationships between propositional atoms, we now have edges that express relationships between arguments. In the most basic framework, there are only attack edges. Intuitively, if attacks , then accepting should imply that we reject . An argumentation framework can then be defined as a pair ( , Att) consisting of a set of arguments and a set Att ⊆ × of attacks between them. With a slight abuse of notation, we let Att() = { ∈ ∣ (, ) ∈ Att} denote the attackers of argument .
The goal of probabilistic epistemic argumentation is to add a degree of belief to every
argument. To this end, we proceed similar to probabilistic logic. We start again by defining
interpretations ∶ ← {0, 1} that can accept (1) or reject (0) arguments. In the context of
abstract argumentation, it is more common to consider sets of accepted arguments instead, but
we use interpretations here to highlight the similarity. Note that there is a 1-1-correspondence
between the two because every interpretation can be associated with the set of arguments that
it accepts and vice versa. We let again Int denote the set of all interpretations and consider
probability distributions ∶ Int → [
Att)? To answer this question, probabilistic epistemic argumentation allows defining the meaning of attack edges by constraints over probability distributions. While many diferent options exist, we present only a small selection from [30] here. We say that respects
Att and () > 0.5
implies that () ≤ 0.5 , Coherence if (, ) ∈
Att implies that () ≤ 1 − () , Foundedness if Att() = ∅ implies () = 1 , Optimism if () ≥ 1 −
∑∈ Att() () .
To understand the intuition of these constraints, it is important to know that probability 0.5 is
associated with indiference, whereas probabilities greater than
0.5 tend towards acceptance
and probabilities smaller than 0.5 tend towards rejection. Intuitively, the constraints generalize
ideas from classical abstract argumentation. Rationality states that if attacks and we accept
, then we should not accept . Coherence encodes the same idea in a more continuous way. As
our belief in increases, our belief in must decrease. Foundedness generalizes Dung’s idea
that arguments can be accepted when it can be successfully argued against their attackers [
A probabilistic epistemic argumentation framework can now be seen as a triple ( , Att, ) consisting of an argumentation framework and a collection of constraints like Coherence and Optimism. A probability distribution satisfies the framework if it satisfies all constraints in .
In order to compute degrees of belief, we can proceed analogously to probabilistic logic. Among all propbability distributions that satisfy a probabilistic epistemic argumentation framework ( ,
Att, ) , we minimize and maximize the probability of an argument to obtain the lower and the upper bound for the belief, respectively. As these beliefs can only be computed if the argumentation framework is satisfiable, it also makes sense to consider a satisfiability problem. Formally, the probabilistic epistemic satisfiability problem asks if a given probabilistic epistemic argumentation framework is satisfiable. The
probabilistic epistemic entailment problem takes an argument as additional input and asks for the solutions of the following minimization and maximization problem: min / max ()
subject to satisfies ( , Att, ).
The dificulty of the probabilistic epistemic entailment problem depends on the nature of the constraints contained in . The constraints proposed in [30] are almost all linear. The only exception is the Rationality constraint. Recall that it states that a probability distribution must satisfy () ≤ 0.5 whenever (, ) ∈
(, ) ∈
Att, we must have () ≤ 0.5
or () ≤ 0.5 , where the or is the logical inclusive or. This is a disjunction of two linear constraints that is computationally dificult to handle. However, all other constraints in [30] can be brought into the form =1 ∑ ⋅ ( ) ≤ 0, where 1, … , ∈ are arguments and 0, … , ∈ ℝ. Note that this form also encompasses =1 ⋅ ( ) = 0 is equivalent to two inequalities ∑ =1 ⋅ ( ) ≤ equalities because an equality ∑
0 and ∑ =1 ⋅ (
) ≥ 0. Constraints of this general form are called linear atomic constraints
and one can show that the probabilistic epistemic satisfiability and entailment problems can
be solved in linear time when only linear atomic constraints are involved [31]. Intuitively,
the reason for this is that the constraints only involve probabilities over atomic arguments.
Therefore, one can show that probability distributions ∶ Int → [
that assign probabilities to arguments directly without changing the semantics. Note, in particular, that the probabilistic epistemic satisfiability problem is indeed simpler than the probabilistic satisfiability problem over Krom clauses that is NP-hard as we discussed before. For the same reason that probabilistic satisfiability over Krom clauses is NP-hard, allowing the conjunction or disjunction of two arguments in constraints immediately renders the probabilistic epistemic satisfiability problem NP-hard [ 31].
A first natural extension of the basic framework is to not only consider attack, but also support edges. This corresponds to the idea of bipolar abstract argumentation [32, 33]. A bipolar abstract argumentation framework is a triple ( ,
Sup() = { ∈ ∣ (, ) ∈ of attacks between them. As before, with a slight abuse of notation, we let
discussion about how support should be defined, but one natural idea is to consider it as the opposite of attack [34]. Whereas an attacker weakens the attacked argument, a supporter should strengthen it. One may then introduce symmetric constraints for support. For example, we could say that respects
Sup and () > 0.5
implies that () > 0.5 , S-Coherence if (, ) ∈
Sup implies that () ≥ () .
The ideas are symmetrical to Rationality and Coherence for attacks. S-Rationality says, intuitively, that if supports and we accept , then we must accept as well. S-Coherence again encodes a similar idea in a continuous way. As the belief in increases, our belief in must increase as well. Similar to the attack constraints, S-Rationality is a dificult non-linear constraint that corresponds to a discjunction of two constraints. S-Coherence is a linear atomic constraint. As we discussed before, the probabilistic epistemic satisfiability and entailment problems can be solved in polynomial time for linear atomic constraints.
The most general extension of probabilistic epistemic argumentation has been discussed in
[
To illustrate the idea, let us consider the argumentation graph in Figure 2 from [31], where solid edges denote attack and dashed edges denote support relations between arguments. The scenario is that we want to decide between two alternatives for treating a muscle injury. Treatment 1 involves immobilizing the limb for some weeks before starting physical therapy. meaning of edges and additional constraints on the probabilities of arguments. The directly constrained arguments are highlighted in red.
Treatment 2 starts physical therapy immediately. The arguments 1, … 4 state reasons for or against the two treatments. Arguments 1, … , 5 represent studies that, in turn, support or attack 1, … 4 or, in case of 5, attack other studies. We use Coherence and S-Coherence to encode the meaning of attack and support edges. For the associated optimization problems, we basically add one linear constraint for every edge. Table 2 shows some probabilistic epistemic entailment results when adding additional constraints on the belief in arguments (shown in red in the respective columns). For example, in the second column, we assume that we are indiferent about the studies (probability
0.5). As a result, we are also indiferent about the treatment. In the fourth column, we assume that we fully accept the second study (probability 1). This enforces that we fully accept treatment 1 and reject treatment 2. The probabilities in this example have been computed with the Java library Attractor 2 that supports polynomial-time reasoning over linear atomic constraints.
Some ideas for more sophisticated general-purpose constraints and general design templates for probabilistic epistemic argumentation graphs can be found in [35].
Given the close relationship between probabilistic logic and probabilistic epistemic argumentation, one can apply the same ideas to deal with inconsistencies. One inconsistency-tolerant version of the probabilistic epistemic entailment problem has been discussed in [30]. However, as opposed to the generalized probabilistic entailment problem that we discussed before, the formulation makes the optimization problems actually harder. It should be possible, however, to use the same ideas like in [26] to get an inconsistency-tolerant version that maintains the linear structure of the optimization problems. In particular, the complexity for this generalization should remain polynomial for linear atomic constraints. Investigating this direction further, is one interesting direction for future work in this area.
2https://sourceforge.net/projects/attractorproject/
We discussed relationships between Nilsson’s probabilistic logic and probabilistic epistemic argumentation. While both are closely related, there are two main diferences worth highlighting. First, the atomic fragment that is not of considerable interest in the logical setting, is interesting from an abstract argumentation perspective and allows solving simple reasoning problems in a quite intuitive and computationally eficient way. Second, argumentation graphs allow modelling reasoning problems in a way that can be more intuitive for domain experts without logical background. Hence, while probabilistic logic adds a formal language to describe events to probability theory, probabilistic epistemic argumentation adds a graphical language to describe probabilistic reasoning problems. From a probabilistic programming perspective, one could say that probabilistic logic turns probability theory into a logical programming language while probabilistic epistemic argumentation turns it into a graphical programming language.
The question which research directions are most interesting is, of course, very subjective. In my opinion, the main diference between probabilistic logic and the more expressive (and computationally expensive) forms of probabilistic epistemic argumentation is that users can potentially model reasoning problems in a more intuitive graphical way. Therefore, one interesting direction for future research in probabilistic epistemic argumentation is to look deeper into ways how to automatically extract meaningful probabilistic constraints from argumentation graphs.
It seems indeed that the logical formalism of probabilistic epistemic argumentation has now
become equivalent to extensions of Nilsson’s probabilistic logic that have been studied before.
Therefore, it may be worthwhile to take a step back and to unify the results in the two areas.
The framework of linear probabilistic knowledge bases [
We did not have space to talk much about relational probabilistic logics, but they are, of course, a very interesting topic in their own right. The main challenge when using Herbrand semantics is that the number of ground atoms grows rapidly. Lifted inference approaches [36] try exploiting symmetries to control the blowup. While some similar ideas have been considered for probabilistic logics [37, 38], it seems worthwhile revisiting the state-of-the-art and to evaluate which recent ideas can be transferred to probabilistic logic. It seems also interesting to investigate to which extent relational probabilistic logics can be applied to add expressiveness to probabilistic epistemic argumentation. For example, one could associate arguments with constants, consider a unary predicate accept that expresses acceptance of an argument and binary predicates like attack and support for edges to allow both uncertainty about arguments and relationships between them. [20] N. Potyka, Solving reasoning problems for probabilistic conditional logics with consistent and inconsistent information, Ph.D. thesis, FernUniversität in Hagen, 2016. [21] G. De Bona, F. G. Cozman, M. Finger, Towards classifying propositional probabilistic logics, Journal of Applied Logic 12 (2014) 349–368. [22] M. Finthammer, G. Kern-Isberner, M. Ritterskamp, Resolving inconsistencies in probabilistic knowledge bases, in: German Conference on Artificial Intelligence (KI), Springer, 2007, pp. 114–128. [23] D. Picado-Muiño, Measuring and Repairing Inconsistency in Probabilistic Knowledge
Bases, International Journal of Approximate Reasoning (2011). [24] M. Thimm, Inconsistency measures for probabilistic logics, Artificial Intelligence 197 (2013) 1–24. [25] L. Daniel, Paraconsistent probabilistic reasoning: applied to scenario recognition and voting theory, Ph.D. thesis, École Nationale Supérieure des Mines de Paris, 2010. [26] N. Potyka, M. Thimm, Probabilistic reasoning with inconsistent beliefs using inconsistency measures, in: Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015. [27] N. Potyka, Linear programs for measuring inconsistency in probabilistic logics, in: International Conference on the Principles of Knowledge Representation and Reasoning (KR), 2014. [28] N. Potyka, Reasoning over linear probabilistic knowledge bases with priorities, in:
International Joint Conference on Artificial Intelligence (IJCAI), Springer, 2015, pp. 121–136. [29] P. Baroni, M. Caminada, M. Giacomin, An introduction to argumentation semantics, The knowledge engineering review 26 (2011) 365–410. [30] A. Hunter, M. Thimm, On partial information and contradictions in probabilistic abstract argumentation, in: International Conference on the Principles of Knowledge Representation and Reasoning (KR), 2016. [31] N. Potyka, A polynomial-time fragment of epistemic probabilistic argumentation, International Journal of Approximate Reasoning 115 (2019) 265–289. [32] L. Amgoud, C. Cayrol, M.-C. Lagasquie-Schiex, P. Livet, On bipolarity in argumentation frameworks, International Journal of Intelligent Systems 23 (2008) 1062–1093. [33] N. Oren, T. J. Norman, Semantics for evidence-based argumentation, in: International Conference on Computational Models of Argument (COMMA), IOS Press, 2008, pp. 276–284. [34] N. Potyka, Bipolar Abstract Argumentation with Dual Attacks and Supports, in: International Conference on Principles of Knowledge Representation and Reasoning (KR), 2020, pp. 677–686. [35] I. Ibs, N. Potyka, Explainable automated reasoning in law using probabilistic epistemic argumentation, in: Workshop on Models of Legal Reasoning (MLR), 2020. [36] K. Kersting, Lifted probabilistic inference., in: European Conference on Artificial Intelligence (ECAI), 2012, pp. 33–38. [37] M. Thimm, Probabilistic reasoning with incomplete and inconsistent beliefs, AKA, 2012. [38] C. Beierle, N. Potyka, J. Baudisch, M. Finthammer, Towards lifted inference under maximum entropy for probabilistic relational fo-pcl knowledge bases, in: European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty (ECSQARU), Springer, 2015, pp. 506–516.