Consistency-based diagnosis is a well-known theory of diagnosis using main knowledge of the normal structure and behaviour of a system. Central in this theory is the notion of a con ict, which describes the relationship between the knowledge of the system and observations. In literature, at least two notions of a con ict have been proposed: (1) based on logical inconsistencies of the observations w.r.t. the system and (2) based on a probabilistic con ict measure. Probabilistic logic programming 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 preliminary results on the relationship between logical consistency and the probabilistic con ict measure.
Model-based diagnosis concerns itself with identifying faults based on a
description (a model) of the system [
Most of the foundational work on model-based diagnosis was done in the
1980s, in particular in consistency-based diagnosis [
An advantage of the logical approach is that the system description can be
written down in a rst-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
abduction reasoning, which was recognised in early papers (in particular [
In this paper, we discuss a preliminary exploration of con ict-diagnosis for
diagnostic problems modelled in ProbLog [
We brie y review the necessary preliminaries on consistency-based and con ictdiagnosis, given both logical models and in a probabilistic setting. 2.1
The following description is based on a recent survey on clinical model-based
diagnosis [
In this paper, we are concerned with what is called Deviation-from-NormalStructure-and-Behaviour diagnosis. For this type of diagnosis, we consider knowledge concerning normal structure and behaviour of the system. In contrast, little or no explicit knowledge is available about the relationships between abnormalities, on the one hand, and ndings to be observed when certain disorders are present, on the other hand. From a practical point of view, the primary motivation 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 system 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 described 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 discussed above are part of a system description SD. Classes of components can be described by quanti cation. In addition to the generic descriptions of the expected behaviour of components, a system description also includes logical speci cations of how the components are connected to each other (the structure of the system), and the names of the components constituting the system. Problem solving basically amounts to adopting particular assumptions about every component c, either whether Ab(c) is true or false.
A diagnostic problem is then de ned as a system description SD, together
with a set of observations OBS, i.e., a nite 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 i [
SD [ [ OBS 6j= ? (1) Typically, in this logical approach we aim to nd 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
Already from the start, uncertainty reasoning was widely recognised as an
essential ingredient of a diagnostic problem solving [
In this paper, we follow the approach by Flesch and Lucas [
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 [
Interestingly, the relationship between the joint probability distribution in a Bayesian diagnostic problem and logical inconsistency is captured by the following property:
P ( j ) 6= 0 i SD [ [ OBS 6j= ? If P ( j ) 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
probability theories. To measure the amount of consistency, Flesch and Lucas deviate
from logical consistency given by Equation 1, and instead used a probabilistic
con ict measure that had been proposed to detect potential con icts between
observations and a given Bayesian network. It is de ned as follows [
P ( 1)P ( 2)
P ( )
P ( n) conf ( ) = log
P (IS j )P (OS j )
P (IS; OS j ) if P (IS; OS j ) 6= 0. In case conf ( ) 0, then the inputs and outputs are positively correlated (or uncorrelated), i.e., there is no con ict between the inputs and output. It is then said that is a con ict-based diagnosis. A minimal con ict-based diagnosis is the one with the minimal con ict measure. 3
Given a system description SD, a diagnostic logic programming theory is simply de ned as ProbLog program that encodes a Bayesian diagnostic system. Each in1(o1) in2(o1) in2(a1)
O1 out(o1) A1 out(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 [
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 xing 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 signi cant advantage is that we can bene t 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 diagnostic 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 con ict-based diagnosis in a diagnostic PLP?
However rst, we note the following about con ict-based diagnoses. Proposition 1. For any set of observations given a diagnostic PLP, there is a con ict-based diagnosis.
Proof. Observe that there is a con ict-based diagnosis in a trivial sense, namely, if = a = fa j a 2 Ag, i.e., when all components are abnormal. In this case all outputs are conditionally independent of the inputs given , and therefore: conf ( ) = log
P (I j )P (O j
P (I; O j ) = log P (I j )P (O j
P (O j )P (I j ) ) ) = 0 0 3.1
We rst 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 con ict-based diagnosis coincide.
SD [ [ 6j= ?, then:
Proof. Let ai 2 A be an abnormality literal associated to the output Oi 2 O. It then holds that P (Oi j (Oi)) = 1 if :ai 2 (Oi) and P (Oi j (Oi)) = P (Oi j ai) otherwise.
Given these observations, the conditional probability of the output given the input can be written as follows: be a complete assignment with inputs and outputs. If P (O j I; ) =
P (Oi j ai) i.e., it is only determined by the constant Then, by similar reasoning, we have: and not by the value of the inputs.
P (O j ) = =
X P (O; I j
I
X
X P (O j I; )P (I)
I Y
P (Oi j ai)P (I) fIjSD[fO;Ig[ 6j=?g ai2 a = Y
P (Oi j ai)
X fIjSD[fO;Ig[ 6j=?g
P (I)
Y ai2 a ) = Therefore P (O j I; )
It then follows:
P (O j ). This is relevant, because logic programming can be used to detect this consistency 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 , i SD [ OBS [ 6j= ?, where E.
Proof. (() Directly by the construction of the PLP program. ()) We have L [ E j= , 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 con ict-based diagnosis by means of abductive 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, speci ed 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 = fin1(o1, false); in2(o1, false); out(o1, true)g, and = fn+ ab(o1)g. Obviously the only explanation for assumes that O1 is abnormal, hence is not a consistency-based nor a con ict-based diagnosis. Also, by Proposition 3, this explanation shows that 0 = fab(o1)g is a consistency-based diagnosis. Note that by Proposition 1, this is also a con ict-based diagnosis, in particular conf 0 ( ) = 0. 3.2
Now suppose partial observability, i.e., if ( I [O. The following example shows that when is P -consistent, then con ict-based diagnosis and consistency-based diagnosis does not necessarily coincide. Example 3. Reconsider the diagnostic program of Example 2. Given this program, suppose we take = fin1(o1, false); out(o1, true)g, and = fn+ ab(o1)g, which is clearly a consistency-based diagnosis, we have: and therefore:
P (I j ) = 0:5 P (O j ) = 0:75
P (I; O j ) = 0:25
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 = fL [ ag that proves IS [ f:Oi j Oi 2 OSg and contains :a0.
Proof. (sketch) We rst repeatedly apply the chain rule on the con ict measure given 0 by the structure of the underlying Bayesian network: conf 0 ( ) = log
P (OS j 0) = log
P (OS j IS; 0)
P (O0 j 0; (O0) \ OS)
Y P (O j 0; (O) \ OS)
P (O0 j IS; 0; (O0) \ OS) O2OSnfO0g P (O j IS; 0; (O) \ OS) Note that P (O0 j 0; (O0) \ OS) = P (O0 j IS; 0; (O0) \ OS) = P (O0 j a0), so the rst term in the product is equal to 1.
Now by contraposition, suppose all explanations for IS [ f:Oi j Oi 2 OSg given T contain a0. Then for the associated output O0 it holds T [ IS [ :O0 implies a0, or equivalently: L [ a [ :a0 [ IS j= O0. This then implies that P (O0 j IS; (O0) \ OS; ) = 1, and therefore:
P (O0 j (O0) \ OS; ) P (O0 j IS; (O0) \ OS; ) = P (O0 j (O0) \ OS; ) 1 Additionally, for all O 2 OS n fO0g, we have P (O j 0; (O) \ OS) = P (O j ; (O) \ OS) and P (O j IS; 0; (O) \ OS) = P (O j IS; ; (O) \ OS). Thus: conf 0 ( ) which concludes the proof. ? false
? true
O1 O2 true true
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 = fin2(o1,false), in2(o2,true)g
OS = fout(o1,true), out(o2,true)g This situation is depicted in Fig. 3. If = fn+ ab(o1); n+ ab(o2)g, 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); n+ ab(o1); in1(o1; false) i.e., the observed input for O1 could have produced a di erent output, suggesting that the observed input and output of O1 are not strongly correlated. Indeed, if we consider 0 = fab(o1); n+ ab(o2)g, we obtain conf 0 = 0:12, whereas if 00 = fn+ ab(o1); ab(o2)g, we compute conf 00 = 0:18. 4
In this paper, we have argued for using PLP as a basis for model-based diagnosis. Furthermore, we show how consistency-based and con ict-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 di erence between the two notions.
Furthermore, we have provided some preliminary ideas on how to compute con ict-based diagnosis from abductive explanations. A naive approach for computing a con ict-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 con ict-based diagnoses can be guided by explanations computed from a given diagnostic probabilistic logic program.
We would like to thank the anonymous reviewers for their suggestions and comments, which signi cantly improved the paper.