=Paper=
{{Paper
|id=Vol-1661/paper-03
|storemode=property
|title=Toward Computing Conflict-Based Diagnoses in Probabilistic Logic Programming
|pdfUrl=https://ceur-ws.org/Vol-1661/paper-03.pdf
|volume=Vol-1661
|authors=Arjen Hommersom,Marcos L.P. Bueno
|dblpUrl=https://dblp.org/rec/conf/ilp/HommersomB16
}}
==Toward Computing Conflict-Based Diagnoses in Probabilistic Logic Programming==
https://ceur-ws.org/Vol-1661/paper-03.pdf
Toward Computing Conflict-Based Diagnoses in
Probabilistic Logic Programming
Arjen Hommersom1,2 and Marcos L.P. Bueno2
1
Open University of the Netherlands
2
Radboud University Nijmegen, The Netherlands
Abstract. Consistency-based diagnosis is a well-known theory of diag-
nosis using main knowledge of the normal structure and behaviour of a
system. Central in this theory is the notion of a conflict, which describes
the relationship between the knowledge of the system and observations.
In literature, at least two notions of a conflict have been proposed: (1)
based on logical inconsistencies of the observations w.r.t. the system and
(2) based on a probabilistic conflict measure. Probabilistic logic pro-
gramming languages combine probabilities with logic, so this raises the
question to which extent these two notions coincide. In this paper, we
consider consistency-based diagnosis in ProbLog and discuss some pre-
liminary results on the relationship between logical consistency and the
probabilistic conflict measure.
1 Introduction
Model-based diagnosis concerns itself with identifying faults based on a descrip-
tion (a model) of the system [7]. With the ever increasing models that are learned
from data, diagnostic methods are still very applicable, see e.g. a recent overview
of model-based diagnosis in medicine [10].
Most of the foundational work on model-based diagnosis was done in the
1980s, in particular in consistency-based diagnosis [6,13,4] and abductive diag-
nosis [11]. Certainly in consistency-based diagnosis there will be many candi-
date hypotheses that explain the observations. To make a choice between these
candidates, the probability of a diagnosis has been proposed as a way to rank
the different hypothesis. Early work in this area includes the general diagnos-
tic engine (GDE) [6], which computes probabilities of candidate diagnosis by
making strong independence assumptions. In more recent years, Bayesian net-
works together with a probabilistic conflict measure has been proposed as an
alternative [3].
An advantage of the logical approach is that the system description can be
written down in a first-order logical language which provides a concise theory
of the system. In recent years several probabilistic logical programming (PLP)
languages have been proposed that can be seen as relational generalisations of
Bayesian networks, therefore forming an attractive foundation for probabilistic
model-based diagnosis. There is obviously a close relationship between PLP and
30
abduction reasoning, which was recognised in early papers (in particular [12]),
but the relationship to consistency-based diagnosis approach is less clear.
In this paper, we discuss a preliminary exploration of conflict-diagnosis for
diagnostic problems modelled in ProbLog [1] programs. We show that abductive
explanations of probabilistic logic programs can be exploited to find conflict-
based diagnoses.
2 Preliminaries
We briefly review the necessary preliminaries on consistency-based and conflict-
diagnosis, given both logical models and in a probabilistic setting.
2.1 Logic-based Consistency-based Diagnosis
The following description is based on a recent survey on clinical model-based
diagnosis [10]. As described in this survey, in consistency-based diagnosis, in
contrast to abductive diagnosis, the malfunctioning of a system is diagnosed by
using mainly knowledge of the normal structure and normal behaviour of its
components [6,13,4].
In this paper, we are concerned with what is called Deviation-from-Normal-
Structure-and-Behaviour diagnosis. For this type of diagnosis, we consider knowl-
edge concerning normal structure and behaviour of the system. In contrast, little
or no explicit knowledge is available about the relationships between abnormal-
ities, on the one hand, and findings to be observed when certain disorders are
present, on the other hand. From a practical point of view, the primary motiva-
tion for investigating this approach to diagnosis is that in many domains little
knowledge concerning abnormality is available, which is certainly true for new
human-created artifacts. For example, during the development of a new printer,
experience with respect to the faults that may occur when the printing sys-
tem is in operation is lacking. Thus, the only conceivable way in which initially
such faults can be handled is by looking at the normal structure and functional
behaviour of the printer.
In consistency-based diagnosis, normal behaviour of a component c is de-
scribed by logical implications of the following form:
¬Ab(c) → Behaviour(c)
In this formalisation, the literal ¬Ab(c) expresses that the behaviour associated
with the component c only holds when the assumption that the component is
not abnormal, i.e. ¬Ab(c), is true for component c. For example, if component O
is an OR-node in a logical circuit with two inputs (In1 and In2 ), we may write:
¬Ab(O) → (In1 (O, true) → Out(O, true))
to partially specify its behaviour. Logical behaviour descriptions of the form dis-
cussed above are part of a system description SD. Classes of components can
31
Fig. 1. Example Bayesian diagnostic system from [3].
be described by quantification. In addition to the generic descriptions of the
expected behaviour of components, a system description also includes logical
specifications of how the components are connected to each other (the structure
of the system), and the names of the components constituting the system. Prob-
lem solving basically amounts to adopting particular assumptions about every
component c, either whether Ab(c) is true or false.
A diagnostic problem is then defined as a system description SD, together
with a set of observations OBS, i.e., a finite set of logical formulas. Let ∆ be
an assignment of either a normal (¬Ab(c)) or an abnormal (Ab(c)) behavioural
assumption to each component c. Denote ∆¬a for all the normal and ∆a for all
the abnormal behavioural assumptions, i.e., ∆ = ∆¬a ∪ ∆a . We say that ∆ is a
consistency-based diagnosis iff [8]:
SD ∪ ∆ ∪ OBS 6|= ⊥ (1)
Typically, in this logical approach we aim to find a subset-minimal diagnosis,
i.e., a diagnosis ∆ such that there does not exists a ∆0 which is also a diagnosis
and ∆0a ⊂ ∆a .
2.2 Probabilistic diagnostic problems
Already from the start, uncertainty reasoning was widely recognised as an essen-
tial ingredient of a diagnostic problem solving [6]. For example, given a proba-
bilistic model of the system, one could compute the maximum a posterior (MAP)
assignment of a set of potential diagnosis given a set of observations. Lucas [9]
has proposed to combine consistency-based diagnosis and a Bayesian network
approach by computing likelihoods of candidate diagnoses ∆. This can lead to
a significant reduction of the number of diagnoses that have to be considered in
a direct MAP approach.
In this paper, we follow the approach by Flesch and Lucas [3], which gen-
eralised consistency-based diagnosis to conflict-based diagnosis. They define a
32
Bayesian diagnostic system as a Bayesian network with nodes I ∪ O ∪ A, where
A denotes the abnormality literals. The edges of the graph are derived from a
mapping from connections in SD. For more details on the mapping of SD to
a Bayesian network, we refer to [2]. An example of such a Bayesian network
is shown in Fig. 1. Given the structure of the network, it is assumed that the
inputs are conditionally independent of the output of a particular component
if the component is functioning abnormally. In particular, if π(V ) denotes the
parents of node V in the graph, then it is assumed that for each Oi ∈ O, it holds
that P (Oi | π(Oi ) \ {Ai }, ai ) = P (Oi | ai ). Moreover, it is assumed that the
distribution of P (Oi | ai ) is fixed of every component. Furthermore, if the com-
ponent is functioning normally, then the output of the component is determined
by a deterministic function of its inputs.
In this approach, the set of observations OBS is split into a set of inputs
variables I and output variables O. By the notation of [3], we will denote observed
inputs and outputs by IS and OS , whereas the remaining non-observed outputs
are denoted by IR and OR , i.e., I = IS ∪ IR and O = OS ∪ OR . Furthermore,
define Ω = IS ∪ OS the full set of observations.
Interestingly, the relationship between the joint probability distribution in a
Bayesian diagnostic problem and logical inconsistency is captured by the follow-
ing property:
P (Ω | ∆) 6= 0 iff SD ∪ ∆ ∪ OBS 6|= ⊥
If P (Ω | ∆) 6= 0, the hypothesis ∆ is called P -consistent. Thus, the existence
of a consistency-based diagnosis coincides with the existence of a P -consistent
diagnosis.
For P -consistent diagnoses, the situation is more subtle when using proba-
bility theories. To measure the amount of consistency, Flesch and Lucas deviate
from logical consistency given by Equation 1, and instead used a probabilistic
conflict measure that had been proposed to detect potential conflicts between
observations and a given Bayesian network. It is defined as follows [5].
P (Ω1 )P (Ω2 ) · · · P (Ωn )
conf(Ω) = log
P (Ω)
A natural choice is then to measure the conflict between the input and output
in the observations, given a particular hypothesis ∆, as follows:
P (IS | ∆)P (OS | ∆)
conf∆ (Ω) = log
P (IS , OS | ∆)
if P (IS , OS | ∆) 6= 0. In case conf∆ (Ω) ≤ 0, then the inputs and outputs
are positively correlated (or uncorrelated), i.e., there is no conflict between the
inputs and output. It is then said that ∆ is a conflict-based diagnosis. A minimal
conflict-based diagnosis is the one with the minimal conflict measure.
3 Consistency-based diagnosis in ProbLog
Given a system description SD, a diagnostic logic programming theory is simply
defined as ProbLog program that encodes a Bayesian diagnostic system. Each
33
in1 (o1 )
O1 out(o1 )
in2 (o1 )
A1 out(a1 )
in2 (a1 )
Fig. 2. Simple logical circuit with an OR-gate O1 and AND-gate A1 .
random variable is mapped to a literal, such that each input is represented by
inn(COMP, Value), where n is the nth input of the component, the output
represented by out(COMP, Value), and each abnormality random variable is
represented by ab(COMP). Without loss of generality, Value is assumed to have
groundings true and false. Furthermore, by abuse of notation, we will refer to
these literals by I, O, and A as there is a one-to-one mapping of these literals
to random variables in the diagnostic Bayesian network.
Using annotated disjunctions [14], a diagnostic PLP L contains the following
clauses:
– α::ab(C).
– β::in(C,true); (1 − β)::in(C,false).
– γ::out(C, true); (1-γ)::out(C,false) :- ab(C).
– out(C,Value) :- \+ ab(C), b(inputs).
where inputs is a set of literals consisting of inputs of C ink(C,Ik) or
outputs from other components out(C’,V), and b is a Boolean function.
Given the assumptions mentioned in Section 2.2, and fixing the prior distribution
of inputs and abnormalities, it is straightforward to see that the distribution of
a Bayesian diagnostic system and this PLP system is the same.
Example 1. Consider a simple circuit as depicted in Fig. 2. The system can be
encoded by a diagnostic PLP as follows:
0.1::ab(C).
0.5::in1(C,true) ; 0.5::in1(C,false).
0.5::in2(C,true) ; 0.5::in2(C,false).
0.5::out(C, true) ; 0.5::out(C,false) :- ab(C).
out(o1, true) :- \+ ab(o1), (in1(o1, true) ; in2(o1,true)).
out(o1, false) :- \+ ab(o1), in1(o1,false), in2(o1, false).
out(a1, true) :- \+ ab(a1), in1(a1, true), out(o1, true).
out(a1, false) :- \+ ab(a1), (in1(a1, false) ; out(o1,false)).
One apparent advantage of using a PLP is that we can specify the local logical
structure directly, whereas in a Bayesian network, logical formulas have to be
encoded into the CPT. Furthermore, a significant advantage is that we can
34
benefit from logical variables to specify the behaviour of classes of component,
e.g. OR-components.
In the remainder of this section, we consider some properties of these di-
agnostic logic programs. If we are using PLP we are both in a logical and a
probabilistic setting, so the natural question is: what is the relationship between
consistency-based diagnosis and conflict-based diagnosis in a diagnostic PLP?
However first, we note the following about conflict-based diagnoses.
Proposition 1. For any set of observations given a diagnostic PLP, there is a
conflict-based diagnosis.
Proof. Observe that there is a conflict-based diagnosis in a trivial sense, namely,
if ∆ = ∆a = {a | a ∈ A}, i.e., when all components are abnormal. In this case
all outputs are conditionally independent of the inputs given ∆, and therefore:
P (I | ∆)P (O | ∆)
conf∆ (Ω) = log
P (I, O | ∆)
P (I | ∆)P (O | ∆)
= log =0≤0
P (O | ∆)P (I | ∆)
3.1 Complete observation
We first consider the case where we have complete observations on the inputs and
outputs, i.e., Ω = I ∪ O. The following propositions show that in this complete
case consistency and conflict-based diagnosis coincide.
Proposition 2. Let Ω be a complete assignment with inputs and outputs. If
SD ∪ Ω ∪ ∆ 6|= ⊥, then:
conf∆ (Ω) ≤ 0
i.e., ∆ is a conflict-based diagnosis.
Proof. Let ai ∈ A be an abnormality literal associated to the output Oi ∈ O. It
then holds that P (Oi | π(Oi )) = 1 if ¬ai ∈ π(Oi ) and P (Oi | π(Oi )) = P (Oi | ai )
otherwise.
Given these observations, the conditional probability of the output given the
input can be written as follows:
Y
P (O | I, ∆) = P (Oi | ai )
ai ∈∆a
i.e., it is only determined by the constant γ and not by the value of the inputs.
Then, by similar reasoning, we have:
X X
P (O | ∆) = P (O, I | ∆) = P (O | I, ∆)P (I)
I I
X Y
= P (Oi | ai )P (I)
{I|SD∪{O,I}∪∆6|=⊥} ai ∈∆a
Y X
= P (Oi | ai ) P (I)
ai ∈∆a {I|SD∪{O,I}∪∆6|=⊥}
35
Therefore P (O | I, ∆) ≥ P (O | ∆).
It then follows:
P (I | ∆)P (O | ∆) P (O | ∆)
conf∆ (Ω) = log = log ≤0
P (I, O | ∆) P (O | I, ∆)
This is relevant, because logic programming can be used to detect this consis-
tency in a direct way, shown in the following proposition.
Proposition 3. Let L be a diagnostic logic program. There is an explanation
E consisting of choices for each probabilistic fact in L that proves Ω, iff SD ∪
OBS ∪ ∆ 6|= ⊥, where ∆ ⊆ E.
Proof. (⇐) Directly by the construction of the PLP program. (⇒) We have
L ∪ E |= Ω, hence, the assignment on the abnormality literals ensures that the
inputs and outputs are consistent.
Propositions 2 and 3 are convenient, because this means that for complete
observations, we can always obtain a conflict-based diagnosis by means of ab-
ductive reasoning alone, i.e., without computing marginal probabilities from the
PLP.
Example 2. In the remainder of the paper, we use a very simple diagnostic PLP
with only a single OR-gate, specified as follows.
0.01::ab(C).
0.5::in1(C,true);0.5::in1(C,false).
0.5::in2(C,true);0.5::in2(C,false).
0.5::out(C, true);0.5::out(C,false) :- ab(C).
out(o1, true) :- \+ ab(o1), (in1(o1, true) ; in2(o1,true)).
out(o1, false) :- \+ ab(o1), in1(o1,false), in2(o1, false).
Suppose Ω = {in1(o1, false), in2(o1, false), out(o1, true)}, and ∆ =
{\+ ab(o1)}. Obviously the only explanation for Ω assumes that O1 is abnor-
mal, hence ∆ is not a consistency-based nor a conflict-based diagnosis. Also, by
Proposition 3, this explanation shows that ∆0 = {ab(o1)} is a consistency-based
diagnosis. Note that by Proposition 1, this is also a conflict-based diagnosis, in
particular conf∆0 (Ω) = 0.
3.2 Partial observations
Now suppose partial observability, i.e., if Ω ( I ∪O. The following example shows
that when ∆ is P -consistent, then conflict-based diagnosis and consistency-based
diagnosis does not necessarily coincide.
36
Example 3. Reconsider the diagnostic program of Example 2. Given this pro-
gram, suppose we take Ω = {in1(o1, false), out(o1, true)}, and ∆ =
{\+ ab(o1)}, which is clearly a consistency-based diagnosis, we have:
P (I | ∆) = 0.5
P (O | ∆) = 0.75
P (I, O | ∆) = 0.25
and therefore:
0.5 · 0.75
conf∆ (Ω) = log ' 0.18
0.25
This example shows that logical reasoning cannot be used to derive a conflict-
based diagnosis alone, something that would be expected. Of course, in this case,
the only conflict-based diagnosis is again the trivial one by Proposition 1, namely
∆0 = {ab(o1)}, because then conf∆0 (Ω) = 0.
The question is now: given a consistency-based diagnosis, can we extend this
to a non-trivial conflict-based diagnosis? The following proposition suggests that
abductive explanations can also be used for this.
Proposition 4. Let L be a diagnostic PLP and ∆ be a hypothesis. If ∆0a =
∆a ∪a0 , with a0 being an abnormality predicate for one of the observed outputs O0
such that conf∆0 (Ω) < conf∆ (Ω), then there is an explanation for T = {L ∪ ∆a }
that proves IS ∪ {¬Oi | Oi ∈ OS } and contains ¬a0 .
Proof. (sketch) We first repeatedly apply the chain rule on the conflict measure
given ∆0 by the structure of the underlying Bayesian network:
P (OS | ∆0 )
conf∆0 (Ω) = log
P (OS | IS , ∆0 )
P (O0 | ∆0 , π(O0 ) ∩ OS ) Y P (O | ∆0 , π(O) ∩ OS )
= log
P (O0 | IS , ∆0 , π(O0 ) ∩ OS ) P (O | IS , ∆0 , π(O) ∩ OS )
O∈OS \{O 0 }
Note that P (O0 | ∆0 , π(O0 ) ∩ OS ) = P (O0 | IS , ∆0 , π(O0 ) ∩ OS ) = P (O0 | a0 ), so
the first term in the product is equal to 1.
Now by contraposition, suppose all explanations for IS ∪ {¬Oi | Oi ∈ OS }
given T contain a0 . Then for the associated output O0 it holds T ∪ IS ∪ ¬O0
implies a0 , or equivalently: L ∪ ∆a ∪ ¬a0 ∪ IS |= O0 . This then implies that
P (O0 | IS , π(O0 ) ∩ OS , ∆) = 1, and therefore:
P (O0 | π(O0 ) ∩ OS , ∆)
= P (O0 | π(O0 ) ∩ OS , ∆) ≤ 1
P (O0 | IS , π(O0 ) ∩ OS , ∆)
Additionally, for all O ∈ OS \ {O0 }, we have P (O | ∆0 , π(O) ∩ OS ) = P (O |
∆, π(O) ∩ OS ) and P (O | IS , ∆0 , π(O) ∩ OS ) = P (O | IS , ∆, π(O) ∩ OS ). Thus:
conf∆0 (Ω) ≥ conf∆ (Ω)
which concludes the proof.
37
?
O1 true
false
?
O2 true
true
Fig. 3. Circuit with observations used in Example 4.
The intuition is that explanations for alternative outputs for the same input
reduces the correlation between the observed input and output. Hence, these
components are more likely to act abnormally, so we conjecture that the converse
of the property above also holds.
Example 4. Consider the problem of Example 3, and add another OR-node:
out(o2, true) :- \+ ab(o2), (in1(o2,true) ; in2(o2,true)).
out(o2, false) :- \+ ab(o2), in1(o2,false), in2(o2,false).
Consider Ω = IS ∪ OS with:
IS = {in2(o1,false), in2(o2,true)}
OS = {out(o1,true), out(o2,true)}
This situation is depicted in Fig. 3. If ∆ = {\+ ab(o1), \+ ab(o2)}, then
conf∆ (Ω) ' 0.05. The most likely explanation which includes IS but not OS
that contains a normality assumption is:
in2(o1, false), in2(o2, true), \+ ab(o1), in1(o1, false)
i.e., the observed input for O1 could have produced a different output, suggesting
that the observed input and output of O1 are not strongly correlated. Indeed,
if we consider ∆0 = {ab(o1), \+ ab(o2)}, we obtain conf∆0 = −0.12, whereas if
∆00 = {\+ ab(o1), ab(o2)}, we compute conf∆00 = 0.18.
4 Conclusions
In this paper, we have argued for using PLP as a basis for model-based diagnosis.
Furthermore, we show how consistency-based and conflict-based diagnosis can be
formalised as part of a single framework. In case there are complete observations,
the two notions coincide, whereas if certain inputs or outputs remain unobserved,
there is a qualitative difference between the two notions.
Furthermore, we have provided some preliminary ideas on how to compute
conflict-based diagnosis from abductive explanations. A naive approach for com-
puting a conflict-based diagnosis would need to consider all possible hypotheses,
which is exponential in the number of components. Instead, the observations
we made in this paper suggests that computing conflict-based diagnoses can
be guided by explanations computed from a given diagnostic probabilistic logic
program.
38
Acknowledgements
We would like to thank the anonymous reviewers for their suggestions and com-
ments, which significantly improved the paper.
References
1. Fierens, D., Van den Broeck, G., Renkens, J., Shterionov, D., Gutmann, B., Thon,
I., Janssens, G., De Raedt, L.: Inference and learning in probabilistic logic pro-
grams using weighted boolean formulas. Theory and Practice of Logic Program-
ming 15(03), 358–401 (2015)
2. Flesch, I.: On the use of independence relations in Bayesian networks. Ph.D. thesis,
Radboud University Nijmegen (2008)
3. Flesch, I., Lucas, P.J., van der Weide, T.P.: Conflict-based diagnosis: Adding un-
certainty to model-based diagnosis. In: IJCAI. vol. 2007, pp. 380–385 (2007)
4. Forbus, K., De Kleer, J.: Building Problem Solvers. The MIT Press, Cambridge,
MA (1993)
5. Jensen, F., Nielsen, T.: Bayesian networks and decision graphs. Springer Science
& Business Media (2009)
6. de Kleer, J., Williams, B.: Diagnosing multiple faults. Artificial Intelligence 32,
97–130 (1987)
7. Kleer, J.d.: Local methods for localizing faults in electronic circuits. Tech. rep.,
DTIC Document (1976)
8. Kleer, J.d., Mackworth, A.K., Reiter, R.: Characterizing diagnoses and systems.
Artificial Intelligence 56(2-3), 197–222 (1992)
9. Lucas, P.J.: Bayesian model-based diagnosis. International Journal of Approximate
Reasoning 27(2), 99–119 (2001)
10. Lucas, P.J., Orihuela-Espina, F.: Representing knowledge for clinical diagnostic
reasoning. In: Foundations of Biomedical Knowledge Representation, pp. 35–45.
Springer (2015)
11. Poole, D.: Normality and faults in logic-based diagnosis. In: IJCAI. vol. 89, pp.
1304–1310 (1989)
12. Poole, D.: Probabilistic Horn abduction and Bayesian networks. Artificial intelli-
gence 64(1), 81–129 (1993)
13. Reiter, R.: A theory of diagnosis from first principles. Artificial Intelligence 32,
57–95 (1987)
14. Vennekens, J., Verbaeten, S., Bruynooghe, M.: Logic programs with annotated
disjunctions. In: International Conference on Logic Programming. pp. 431–445.
Springer (2004)