Information Graphs and Their Use forBayesian Network Graph Construction
Remi Wietena,∗, Floris Bexa,b , Henry Prakkena,c , Silja Renooijaa Department of Information and Computing Sciences, Utrecht University
b Institute for Law, Technology and Society, Tilburg Universityc Faculty of Law, University of Groningen

Abstract
In this paper, we present the information graph (IG) formalism, which provides
a precise account of the interplay between deductive and abductive inference
and causal and evidential information, where ‘deduction’ is used for defeasible‘forward’ inference. IGs formalise analyses performed by domain experts in theinformal reasoning tools they are familiar with, such as mind maps used in crime
analysis. Based on principles for reasoning with causal and evidential information given the evidence, we impose constraints on the inferences that may be
performed with IGs. Our IG-formalism is intended to facilitate the construction of formal representations within AI systems by serving as an intermediary
formalism between analyses performed using informal reasoning tools and formalisms that allow for formal evaluation. In this paper, we investigate the use of
the IG-formalism as an intermediary formalism in facilitating Bayesian network(BN) graph construction. We propose a structured approach for automaticallyconstructing from an IG a directed BN graph, together with qualitative constraints on the probability distribution represented by the BN. Moreover, we
prove a number of formal properties of our approach and identify assumptions
under which the construction of an initial BN graph can be fully automated.
Keywords: Bayesian networks, causal and evidential reasoning, deduction,
abduction, uncertainty, qualitative probabilistic reasoning
1. Introduction

5

10

Bayesian networks (BNs) [20] are compact graphical representations of joint
probability distributions that have found applications in many fields where uncertainty and evidence plays a role, including medicine, engineering, forensics
and law [16]. For instance, in recent years legal and forensic experts have increasingly developed and used BNs for the interpretation of different types of forensic
trace evidence [36], such as glass fragments, DNA traces and finger marks [34],as well as for modelling crime linkage [44]. A BN consists of a directed acyclic
graph (DAG), which captures the probabilistic independence relation among
variables relevant to the domain, and locally specified (conditional) probability∗ Corresponding author

Email address: g.m.wieten@uu.nl (Remi Wieten)

Preprint submitted to Elsevier

June 18, 2021

15

20

25

30

35

40

45

50

55

distributions that collectively describe a joint probability distribution. BNs are
well-suited for reasoning about the uncertain consequences that can be inferredfrom evidence. Domain experts, however, typically do not have the expertiseto construct mathematical models and misinterpret the directed arcs of a BN
as non-symmetric relations of cause and effect instead of collectively encoding
an independence relation [12]. Especially in data-poor domains, BN construction therefore needs to be done mostly manually through a knowledge elicitation
procedure in consultation with the domain expert, which is a difficult and errorprone task [18], and domain experts typically resort to using other reasoning
tools including mind maps [26, 38], argument diagrams [1, 3, 26], Wigmore
charts [43], and ontologies [17, 31], as well as basic text-based tools such as
Microsoft Word and Excel [26].
Methods have been proposed that facilitate BN construction by extracting
information relevant for a BN from analyses performed in tools used by experts.
For instance, methods for constructing BNs from information represented in
ontologies, knowledge representations which capture relations between concepts
in a domain, have been proposed [17, 31]. To apply these approaches in practice,
the problem under consideration first needs to be specified in the formal ontology
language required as input. Aforementioned tools such as mind maps, argument
diagrams and Wigmore charts similarly do not directly allow for guiding BN
construction due to their informal nature. In contrast with ontologies, thesetools are used to capture inferences made with causal and evidential information(see [2, 6]), instead of with generic relations between concepts. In this paper, we
focus on reasoning tools such as mind maps, where we wish to formalise analyses
performed using such tools in a manner that (1) adheres to principles from theliterature on reasoning with causal and evidential information [2, 21, 27, 29],
while (2) allowing inference to be performed in a manner closely related to theway in which inference is performed using such tools, and that (3) allows for
guiding BN construction.
Principles from the literature on reasoning with causal and evidential information state that inference is often performed using domain-specific generalisations [1, 2], also called defaults [27, 32], which capture knowledge about
the world in conditional form. We distinguish between causal generalisations(e.g. fire typically causes smoke) and evidential generalisations (e.g. smoke isevidence for fire) [2, 27]. Inference can be performed in a deductive or forward
fashion, where from a generalisation (e.g. fire typically causes smoke) and its
antecedent (fire), the consequent (smoke) is inferred, and in an abductive [21]or backward fashion, where from a causal generalisation and by affirming theconsequent the antecedent is inferred. Note that the term ‘deduction’ is not consistently used in the literature, as it can either mean strict inference, in which
the consequent universally holds given the antecedents (e.g. [30]), or defeasible
inference, in which the consequent tentatively holds given the antecedents (e.g.
[35]). In this paper, ‘deduction’ is used for defeasible ‘forward’ inference.
When performing analyses in aforementioned reasoning tools such as mind
maps, domain experts naturally mix both causal and evidential generalisations
and perform both deductive and abductive inferences, where the used generali2

60

65

70

75

80

85

90

95

100

sations and the inference type (deduction, abduction) are typically left implicit.
Hence, in formalising analyses performed using these tools we need a precise
account of the interplay between the different types of inferences and generalisations and the constraints on performing inference we need to impose. In
this paper we present the information graph (IG) formalism [42], which provides
such an account. IGs are knowledge representations that formalise analyses performed by domain experts using the informal reasoning tools they are familiar
with in a manner that makes the causal and evidential generalisations used inperforming inference explicit. Based on principles for reasoning with causal andevidential generalisations, we then define how deductive and abductive inference
can be performed with IGs given a set of propositions labelled evidence. Most
existing formalisms that allow both inference types with causal and evidential
information are logic-based (e.g. [2, 29, 35]); instead, we prefer a graph-basedformalism to remain closely related to analyses performed using aforementioned
graph-based tools as well as the BN-formalism.
Our IG-formalism is intended to facilitate the construction of formal representations within AI systems by serving as an intermediary formalism between
analyses performed using informal reasoning tools and formalisms that allow forformal evaluation. In this paper, we investigate the use of the IG-formalism as
an intermediary formalism in facilitating BN graph construction. We propose astructured approach for automatically constructing a directed BN graph froman IG by exploiting the causal and evidential knowledge expressed in an IG. In
manual BN graph construction, the notion of causality is commonly used as a
guiding principle [16, 20] instead of directly eliciting conditional independencies.
In IGs, causality information is made explicit and can thus be directly used in
BN graph construction. In addition, we demonstrate that the inferences thatcan be read from an IG given the evidence provide for qualitative constraints
on the probability distribution represented by the BN. We formally prove thatBN graphs constructed by our approach capture reasoning patterns similar to
those represented by the original IG. Moreover, we identify assumptions underwhich the fully automatically constructed initial graph is guaranteed to be a
DAG, and identify bounds on the complexity of probabilistic inference in BNs
constructed by our approach.
The IG-formalism as presented in this paper is a further specification of
the IG-formalism that appeared in our previous work [42], in which the relations between inference as it can be performed with IGs and argumentation
were investigated. Argumentation [15, 30] is particularly suited for adversarial
settings such as the legal domain, where arguments for and against claims areconstructed from evidence. In [42], it is shown that an Argumentation Framework (AF) as in Dung [15] can straightforwardly be generated from an IG byconsidering the available evidence, which allows arguments to be formally evaluated. The BN graph construction approach as presented in the current paper
extends on our previous work on facilitating BN graph construction [5, 39, 40];
further details of this work are discussed in Sect. 9.
The paper is structured as follows. In Sect. 2 we provide principles for reasoning with causal and evidential information. In Sect. 3 we present an example
3

105

110

115

of an analysis performed using a tool typically used by domain experts, namely
a mind mapping tool, which illustrates that both deduction and abduction is
performed by domain experts, using both causal and evidential generalisations.
Based on this example, in Sect. 4 we motivate and define our IG-formalism.
Sections 5 to 8 concern the construction of BNs from IGs. Section 5 provides
preliminaries on BNs. In Sect. 6 we present our approach for constructing BNgraphs from IGs. In Sect. 7 we prove formal properties of our approach. In
Sect. 8 we illustrate and perform a first validation of our approach by applying
it to parts of an actual legal case, namely the well-known Sacco and Vanzetti
case, where we compare our results to a previous BN modelling of the samecase [22]. In Sect. 9 related research on among others inference with causality
information and BN graph construction is discussed. In Sect. 10 we discuss
future work, summarise our findings, and conclude.
2. Reasoning with Causal and Evidential Information

120

125

130

135

140

In this section, we provide principles for reasoning with causal and evidential
information, where we review the terminology used to describe it and introduce
assumptions that demarcate the scope of the work presented in this paper. Inference is the process of drawing conclusions from premises starting from theevidence, where evidence is that what has been established with certainty inthe context under consideration. For instance, in the context of a legal trial theevidence consists of that what is actually observed by a judge or jury, such as
documents (e.g. police and autopsy reports) and other tangible evidence, as wellas testimonial evidence [2]. Inference is often performed using domain-specificgeneralisations [1, 2], also called defaults [27, 32], which capture knowledge
about the world in conditional form. We distinguish between causal and evidential generalisations [2, 27]. Causal generalisations are of the form ‘c1 , . . . , cn
usually/normally/typically cause e’ (e.g. ‘fire typically causes smoke’) and evidential generalisations are of the form ‘e1 , . . . , en are evidence for c’ (e.g. ‘smoke
is evidence for fire’). We denote generalisations as fire → smoke, where fire is
the generalisation’s antecedent and smoke its consequent. For a causal generalisation, its antecedents express a cause for the consequent, and for an evidential
generalisation, its consequent expresses the usual cause for its antecedents. We
assume that generalisations have one or more antecedents and exactly one consequent. In case a generalisation has multiple antecedents, it expresses that
only the antecedents together allow us to infer the consequent. The notation→c and →e is used for causal and evidential generalisations, respectively.
Different types of inferences can be performed with generalisations dependingon whether their antecedents or consequent are affirmed in that they are either
observed or inferred; here, a consequent or antecedent is inferred iff it is either
deductively or abductively inferred.

4

2.1. Deductive Inference
145

150

Inference can be performed in a deductive fashion, where from a causal or evidential generalisation and by affirming the antecedents, the consequent is inferred
by modus ponens on the generalisation. As noted in the introduction, the term
‘deduction’ is used for defeasible ‘forward’ inference; hence, deduction is not astronger or more reliable form of inference than abduction, which is anothertype of defeasible inference. Prediction [35] is a specific type of deductive inference in which the consequent of a causal generalisation is deductively inferredby affirming its antecedents.
2.2. Abductive Inference

155

160

165

Abduction [21] can also be performed: from a causal generalisation and by
affirming the consequent, the antecedents are inferred, since if the antecedents
are true it would allow us to deductively infer the consequent modus-ponensstyle. In case multiple causes for a common effect are abductively inferred using
multiple causal generalisations with the same consequent, then these causes
are considered to be competing alternative explanations [21] for the common
effect expressed by the consequent. In case a causal generalisation has multiple
antecedents, we assume that these antecedents are not in competition among
themselves.
Example 1. Consider the causal generalisations fire →c smoke and smoke
machine →c smoke. By affirming the common consequent ( smoke), fire andsmoke machine are abductively inferred, which are then competing alternative
explanations of smoke.

2.3. Representing Causal Knowledge

170

175

180

Abductive inference with causal generalisations and deductive inference withevidential generalisations are related: in some cases, we will accept not only
causal generalisation ‘c usually/normally/typically causes e’ but also evidential
generalisation ‘e is evidence for c’ [4, 27], which we will call the evidential
counterpart of the causal generalisation. However, it can be argued that weonly accept the evidential counterpart of a causal generalisation if c is the usual
cause of e, where we assume that only one cause can be the usual cause of e.
Example 2. Fire can be considered the usual cause of smoke, so we will accept
both causal generalisation g : fire →c smoke and its evidential counterpart g 0 :smoke →e fire. In this case, abductive inference with generalisation g can be
encoded as deductive inference with generalisation g 0 . Because a smoke machine
cannot be considered the usual cause of smoke, we will accept causal generalisation smoke machine →c smoke but we will not accept evidential generalisationsmoke →e smoke machine.
Note that a causal generalisation g can only have an evidential counterpart g 0
in case g has a single antecedent, as we assume generalisations have a single
5

185

consequent but multiple antecedents. Furthermore, as we assume that only
one cause can be the usual cause of e, only one of the causal generalisations
c1 →c e or c2 →c e can be replaced by an evidential generalisation. Hence, we
do not consider c1 and c2 to be competing alternative explanations of e in casededuction is performed using evidential generalisations e →e c1 and e →e c2 .
2.4. Mixed Inference

190

195

Deduction and abduction can be iteratively performed, where mixed abductivedeductive inference is also possible.
Example 3. Suppose that from the causal generalisation fire →c smoke and by
affirming its consequent ( smoke), its antecedent ( fire) is inferred. Now, if theadditional causal generalisation fire →c heat is provided, then its consequent( heat) can be deductively inferred (or predicted) as the antecedent ( fire) has
been previously abductively inferred.
Mixed deductive inference, using both causal and evidential generalisations,can also be performed [4], but as noted by Pearl [27] care should be taken in
performing mixed inference that no cause for an effect is inferred in case analternative cause for this effect was already previously inferred.

200

205

210

Example 4. (a) Consider the example in which a causal generalisation smoke
machine →c smoke and an evidential generalisation smoke →e fire are provided.
Deductively chaining these generalisations would make us infer that there is afire when seeing a smoke machine, which is clearly undesirable.
(b) Similarly, in performing mixed deductive-abductive inference, care should
be taken that no cause for an effect is inferred in case an alternative cause forthis effect was already previously inferred. Consider the above example, where
instead of an evidential generalisation smoke →e fire a causal generalisation
fire →c smoke is now provided. Upon seeing a smoke machine, this would makeus infer that there is a fire in case deductive inference and abductive inference
are performed in sequence, which is again undesirable.

Accordingly, we wish to prohibit these types of inference patterns, and refer tothe constraint that no cause for an effect should be inferred in case an alternativecause for this effect was already previously inferred as Pearl’s constraint [27].
2.5. Ambiguous Inference

215

220

Finally, situations may arise in practice in which both deductive and abductive
inference can be performed with the same causal generalisation; the inference
type is, therefore, considered ambiguous.
Example 5. Consider the causal generalisation fire →c smoke and assume
that both fire and smoke are affirmed but not observed, then both deductive andabductive inference can be performed to either infer smoke from fire or fire fromsmoke, respectively.
6

testimony_1

motive_1

testimony_2

motive_2

Whymarjan_murdered_leo

Who

Where
testimony_4

lietestimony_3

What
With

police_report

MurderExample CaseIn which way
When

Figure 1: Example of a partially filled in mind map.

3. Example of an Analysis Performed Using a Mind Mapping Tool

225

230

235

240

245

250

255

In this section, we present an example of an analysis performed using a mind
mapping tool [26], which is an example of a tool typically used by domain experts, for instance in crime analysis [38]. Based on this example, we motivate
and illustrate the design choices for our IG-formalism in Sect. 4. A mind map
usually takes the shape of a diagram in which hypotheses and claims are represented by boxes and underlined text, and undirected edges symbolise relations
between these hypotheses and claims. An example is depicted in Fig. 1, which
is based on a standard template used by the Dutch police for criminal cases
involving the suspicious death of a person. The mind map represents various
scenario-elements and the crime analyst uses evidence to support or oppose theseelements, indicated in the mind map by plus and minus symbols, respectively.
Example 6. An example of a partially filled in mind map is depicted in Fig. 1,
which also serves as our running example. In this example case, adapted from[2], the high-level hypothesis ‘Murder’ is considered; for illustration purposes
the details of the case have been changed. The case concerns the murder of Leo
de Jager, which took place in the small Dutch town of Anjum. Leo’s body was
found on the property of Marjan van der E.; we are interested in her involvement in the murder. As a police report ( police report) indicates that Leo’s bodywas found on Marjan’s property, the claim marjan murdered leo is added as ananswer to the ‘Who’ question. By means of a plus symbol and an undirectededge connecting the evidence to the claim, it is indicated that the police report
supports the claim that Marjan murdered Leo. Possible motives ( motive 1 andmotive 2) are provided as to why Marjan may have wanted to murder Leo, which
are connected to the ‘Why’ question via undirected edges. Claims testimony 1
and testimony 2 support these two motives, indicated by the plus symbols connected to these claims. In her testimony ( testimony 3), Marjan denied any
involvement in the murder of Leo, which is indicated by a minus symbol. This
opposes the claim that Marjan murdered Leo. Further testimony ( testimony 4)
indicates that Marjan had reason to lie when giving her testimony ( lie). Bymeans of a minus symbol and an undirected edge connecting lie to testimony 3,
it is indicated that this claim weakens the inference step from her testimony tothe claim that she did not murder Leo.
As the edges in a mind map are undirected, it is unclear from this graphical
7

260

265

270

275

280

representation alone which types of generalisations and inferences were used inconstructing this map. Establishing this with certainty would require directly
consulting the domain experts involved in constructing the chart. We note,however, that the reasoning performed in constructing this mind map can beinterpreted in multiple ways. One interpretation is that the domain expert first(preliminarily) inferred that Marjan murdered Leo from the police report via
deductive inference using the evidential generalisation police report →e marjan murdered leo, and then abductively inferred the two possible motives using
the causal generalisations gi : motive i →c marjan murdered leo; i = 1, 2. These
two causes are then competing alternative explanations as to why Marjan murdered Leo and are subsequently grounded in evidence, namely via deductive
inference from the testimonies using evidential generalisations gj0 : testimony j→e motive j ; j = 1, 2. An alternative interpretation is that the mind map wasconstructed iteratively from the evidence, where from the testimonies the motives are inferred via deductive inference using generalisations g10 and g20 . The
claim that Marjan murdered Leo is then inferred modus-ponens style: fromcausal generalisations g1 and g2 and the previously inferred antecedents, theconsequent is deductively inferred. In this way, the two motives are not incompetition for the common effect that Marjan murdered Leo.
The above example illustrates that the types of generalisations and inferences that are involved in the analysis of a case using a mind mapping tool
are typically left unspecified. Similarly, in mind maps the exact manner inwhich claims and links conflict is not precisely specified: a minus symbol caneither indicate support for the opposing claim (e.g. testimony 3 supports thenegation of marjan murdered leo) or indicate an exception to the performed
inference (e.g. lie opposes the inference from testimony 3 to the negation of
marjan murdered leo).
4. The Information Graph Formalism

285

290

295

The example from Sect. 3 makes it plausible that both deduction and abduction
is performed by domain experts when performing analyses using reasoning tools
they are familiar with. In performing such analyses, the used generalisations,as well as the inference type (deduction, abduction), are left implicit. Furthermore, the assumptions of domain experts underlying their analyses are typicallynot explicitly stated, making these analyses ambiguous to interpret. For current purposes, we wish to provide a precise account of the interplay between
the different types of inferences and generalisations that formalises and disambiguates these analyses in a manner that makes the used generalisations explicit.
Information graphs (IGs) [42], which we define in Sect. 4.1, are knowledge representations that explicitly describe causal and evidential generalisations in thegraph. In Sect. 4.2, we define how deductive and abductive inferences can beread from IGs given the evidence, based on the principles for reasoning withcausal and evidential information discussed in Sect. 2.

8murderg1

police

e

c
g3
mot1

c
g5
mot2
g4 e
tes2

g2 e
tes1

murder¬murder
g6 e

tes3

(a)

lie
g7 e
tes4

g3

c

mot1
g2 e
tes1

mot2
g4 e
tes2
(b)

Figure 2: An IG corresponding to a possible interpretation of the mind map of Fig. 1 (a);adjustment to the IG of Fig. 2a including generalisation arc g3 : {mot 1 , mot 2 } → murder (b).

4.1. Information Graphs
IGs are defined as follows.
300

305

Definition 1 (Information graph). An information graph (IG) is a directed
graph GI = (P, AI ), where P is a set of nodes representing propositions froma propositional literal language with ordinary negation symbol ¬. AI is a set of(hyper)arcs that divides into three pairwise disjoint subsets G, N and Exc ofgeneralisation arcs, negation arcs and exception arcs, defined in Definitions 2,
6, and 7, respectively.
We write p = −q in case p = ¬q or q = ¬p. Note that an IG GI does not haveto be a connected graph.

310

315

320

325

Definition 2 (Generalisation arc). Let GI = (P, AI ) be an IG. A generalisation arc g ∈ G ⊆ AI is a directed (hyper)arc g : {p1 , . . . , pn } → p, indicating a generalisation with antecedents P1 = {p1 , . . . , pn } ⊆ P and consequentp ∈ P \ P1 . Here, propositions in P1 are called the tails of g, denoted byTails(g), and p is called the head of g, denoted by Head(g). G divides into
two disjoint subsets Gc and Ge of causal and evidential generalisation arcs,
respectively.
Curly brackets are omitted in case |Tails(g)| = 1. In figures in this paper,
generalisation arcs are denoted by solid (hyper)arcs, which are labelled ‘c’ forg ∈ Gc and ‘e’ for g ∈ Ge .
A causal generalisation g : c → e may have an evidential counterpart of theform g 0 : e → c (see Sect. 2.3), but only if c is the usual cause of e. Definition
2 does not prohibit the coexistence of a causal generalisation g : c → e andits evidential counterpart g 0 : e → c in an IG, and inferences can be read from
IGs including both generalisations without yielding anomalous results; hence,both generalisations may be included if this is considered desirable. However,it should be noted that g and g 0 represent the same knowledge, and that careshould be taken in for instance modelling exceptions to generalisations (seeDefinition 7), as an exception to g can also be considered an exception to g 0 .
Ultimately, it is the responsibility of the knowledge engineer in consultation

9

330

335

340

345

with the domain expert to decide which knowledge to include in the IG and toensure this knowledge is correctly and consistently represented.
In the following example, the mind map of Sect. 3 is modelled as an IG.
Example 7. In Fig. 2a, an IG is depicted for a possible interpretation of
the running example. First, we consider the undirected edges connected to thetestimonies and the police report in the mind map of Fig. 1. In an empirical study in the legal domain, van den Braak and colleagues [6] found that
subjects often considered testimonies to be evidential, where generalisations areof the form ‘Testimony to fact x is evidence for x’. Police reports can similarly be considered evidential. The IG therefore includes generalisation arcs
g1 , g2 , g4 , g7 ∈ Ge to denote these generalisations. As tes3 concerns Marjan’s
testimony to denying any involvement in the murder, ¬murder is included in
P and g6 : tes3 → ¬murder in Ge . A motive for committing an act can beconsidered a cause for committing that act [6]. The IG therefore includes generalisation arcs g3 : mot1 → murder and g5 : mot2 → murder in Gc to denotethese generalisations.
Specific configurations of generalisation arcs express that two propositions arealternative causes of a common effect, as captured by the following definition.
Definition 3 (Alternative causes). Let GI = (P, AI ) be an IG. Then c1 ∈ P
and c2 ∈ P are alternative causes of e ∈ P, as indicated by generalisations g
and g 0 in G, iff one of the following holds:

350

355

1. g ∈ Ge , Head(g) = c1 , e ∈ Tails(g), and either:1a) g 0 ∈ Ge , g 0 6= g, Head(g 0 ) = c2 , e ∈ Tails(g 0 ), or;1b) g 0 ∈ Gc , Head(g 0 ) = e, c2 ∈ Tails(g 0 ).
2. g ∈ Gc , Head(g) = e, c1 ∈ Tails(g), and either:2a) g 0 ∈ Gc , g 0 6= g, Head(g 0 ) = e, c2 ∈ Tails(g 0 ), or;2b) g 0 ∈ Ge , Head(g 0 ) = c2 , e ∈ Tails(g 0 ).
Generalisation chains are sequences of generalisation arcs.
Definition 4 (Generalisation chain). Let GI = (P, AI ) be an IG. Generalisation arcs g1 , . . . , gm ∈ G ⊆ AI form a generalisation chain [g1 , . . . , gm ] in GI
iff Head(gi−1 ) ∈ Tails(gi ) for 1 < i ≤ m.
Note that a subchain of a generalisation chain is again a generalisation chain.

360

365

Example 8. In the IG of Fig. 2a, [g2 , g3 ] is a generalisation chain as Head(g2 )= mot1 ∈ Tails(g3 ).
Consider the IG of Fig. 2b, which is an adjustment to the IG of Fig. 2a inwhich generalisation arc g3 : {mot1 , mot2 } → murder in Gc is included insteadof two separate generalisation arcs g3 and g5 . According to Definition 4, [g2 , g3 ]is a generalisation chain, but mot2 is neither a head nor a tail of generalisation
arc g2 ; it suffices that Head(g2 ) = mot1 ∈ Tails(g3 ).
We define the following notion of a causal cycle.
10

s
r

g3 c
r

e g'3
q3

g2 c

e g'2

g2 e

c g'2

q1

q2
e g'1

q1

q2
e g'1

g1 c

g1 c

p

p

(a)

(b)

Figure 3: Examples of IGs including causal cycles.

375

Definition 5 (Causal cycle). Let GI = (P, AI ) be an IG. Proposition p ∈ P
expresses a direct cause for q ∈ P iff ∃g ∈ G ⊆ AI with g ∈ Gc , p ∈ Tails(g),q = Head(g) or g ∈ Ge , p = Head(g), q ∈ Tails(g). Proposition p1 ∈ P
expresses an indirect cause for p3 ∈ P iff ∃p2 ∈ P, p2 6= p1 , p2 6= p3 , such thatp1 expresses a direct cause for p2 and p2 expresses a direct or indirect cause forp3 . A causal cycle exists in GI iff ∃p, q ∈ P such that p expresses a direct orindirect cause for q ∈ P and q or −q expresses a direct or indirect cause for p
or for −p.

380

Examples of IGs including causal cycles are provided in Fig. 3.
We assume that graphs constructed in our IG-formalism conform to thefollowing restrictions on generalisation chains, which arguably are reasonablerational constraints to impose on IGs. Informally, assumptions 1 and 2 exclude
the possibility of using a proposition p to deductively infer itself or −p.

385

1. IGs only contain non-repetitive generalisation chains [g1 , . . . , gm ] in that
Head(gm ) ∈/ Tails(g1 ).
2. IGs only contain consistent generalisation chains [g1 , . . . , gm ] in that @i, j ∈{1, . . . , m} such that Head(gi ) = −Head(gj ).
3. IGs do not include causal cycles (see also [29]).

370

A negation arc captures a conflict between a proposition and its negation1 expressed in an IG.

390

Definition 6 (Negation arc). Let GI = (P, AI ) be an IG. A negation arc
n ∈ N ⊆ AI is a bidirectional arc n : p ! q in GI that exists between a pairp, q ∈ P iff q = −p.
Example 9. Consider the running example. As both murder and ¬murder are
included in the IG of Fig. 2a, negation arc n : murder ! ¬murder is also
included in the graph.

1 Note that while we only consider ordinary negation in this paper, more general notionsof conflicts such as contrariness (see e.g. [30]) are also available.

11

395

As generalisations hardly ever hold universally, exceptional circumstances can beprovided under which a generalisation may not hold; hence, we allow exceptions
to generalisations to be explicitly specified in IGs.
Definition 7 (Exception arc). Let GI = (P, AI ) be an IG. An exception arc
exc ∈ Exc ⊆ AI is a hyperarc exc : pg, where p ∈ P is called an exception
to generalisation g ∈ G.

400

405

410

An exception arc directed from p to g indicates that p provides exceptional
circumstances under which g may not hold.
Example 10. In the running example, proposition lie, which states that Marjan
had reason to lie when giving her testimony, provides an exception to evidential
generalisation g6 : tes3 → ¬murder in Ge . In Fig. 2a, this is indicated by acurved hyperarc exc : lie
g6 in Exc.

4.2. Reading Inferences from Information Graphs
We now define how deductive and abductive inferences can be read from IGs. By
itself, a generalisation arc only expresses that the tails together allow us to infer
the head in case this generalisation is used in deductive inference, or that thetails together can be inferred from the head in case of abductive inference. Only
when considering the available evidence can directionality of inference actually
be read from the graph.
Definition 8 (Evidence set). Let GI = (P, AI ) be an IG. An evidence set isa subset Ep ⊆ P such that for every p ∈ Ep it holds that ¬p ∈/ Ep .

415

420

The restriction that for every p ∈ Ep it holds that ¬p ∈/ Ep ensures that not
both a proposition and its negation are observed. In figures in this paper,
nodes in GI corresponding to elements of Ep are shaded and all shaded nodes
correspond to elements of Ep . We emphasise that various evidence sets Ep canbe used to establish (different) inferences from the same IG.
Example 11. In the running example, the evidence consists of the testimonies
and the police report. In Fig. 4, the IG of Fig. 2a is again depicted, with nodes
in Ep = {tes1 , tes2 , tes3 , tes4 , police} shaded.

We now define when we consider configurations of generalisation arcs and evidence to express deductive and abductive inference.

425

430

4.2.1. Deductive InferenceFirst, we specify under which conditions we consider a configuration of generalisation arcs and evidence to express deductive inference.
Definition 9 (Deductive inference). Let GI = (P, AI ) be an IG, and let Ep ⊆P be an evidence set. Let p1 , . . . , pn , q ∈ P, with q ∈/ Ep . Then given Ep ,q is deductively inferred from propositions p1 , . . . , pn using a generalisationg : {p1 , . . . , pn } → q in G, denoted p1 , . . . , pn g q, iff ∀pi , i = 1, . . . , n:12

g1

policee¬murdermurder
g3
g5
c
c

g6 e

mot1
g2 e

mot2
e g4

tes1

tes2

tes3

lie
e g7
tes4

Figure 4: The IG of Fig. 2a, where evidence Ep and resulting inference steps () are also
indicated.

435

440

445

450

455

460

1. pi ∈ Ep , or;
2. pi is deductively inferred from propositions r1 , . . . , rm ∈ P using a generalisation g 0 : {r1 , . . . , rm } → pi , where g 0 ∈ Ge if g ∈ Ge , or;
3. pi is abductively inferred from a proposition r ∈ P using a g 0 : {pi , r1 , . . . , rm }→ r in Gc , g 6= g 0 , r1 , . . . , rm ∈ P (see Definition 10).
In accordance with our assumptions stated in Sect. 2.1, deductive inference
can be performed using both causal and evidential generalisations. The condition q ∈/ Ep ensures that deductive inference cannot be performed with ageneralisation to infer its consequent in case its consequent is already observed.
Deductive inference can only be performed using a generalisation g ∈ G to infer
its consequent Head(g) from its antecedents Tails(g) in case every antecedentpi ∈ Tails(g) has been affirmed in that either pi is observed (i.e. pi ∈ Ep ), pi itself is deductively inferred, or pi is abductively inferred. In correspondence with
Pearl’s constraint (see Sect. 2.4), we assume in condition 2 that a propositionq ∈ P cannot be deductively inferred from p1 , . . . , pn ∈ P using a generalisationg ∈ Ge if at least one of its antecedents pi ∈ Tails(g) is deductively inferredusing a generalisation g 0 ∈ Gc . Condition 3 of Definition 9 is further explainedin Sect. 4.2.3, after abductive inference is defined.
Example 12. In the IG of Fig. 4, given Ep mot1 and mot2 are deductively
inferred from tes1 and tes2 using generalisations g2 and g4 , respectively, as tes1 ,tes2 ∈ Ep (condition 1 of Definition 9). Similarly, murder, ¬murder and lie
are deductively inferred from police, tes3 and tes4 using generalisations g1 , g6
and g7 , respectively, as police, tes3 , tes4 ∈ Ep .
Proposition murder is also deductively inferred from mot1 and mot2 using
causal generalisations g3 and g5 , as mot1 and mot2 are deductively inferred(condition 2 of Definition 9). This illustrates mixed deductive inference using
both evidential and causal generalisations.

The following example illustrates the restrictions put on performing deductive
inference within our IG-formalism.
Example 13. Figure 5a depicts an example of an IG in which q cannot be
deductively inferred from p using g1 , as Head(g1 ) = q ∈ Ep . In Fig. 5b, q
cannot be deductively inferred from p1 and p2 using g1 , as p2 ∈/ Ep and p2 isneither deductively nor abductively inferred.
13

q

q
g1 e
p
(a)

g1

c

p2

p1
(b)

fire
e g2
smoke
c g1
smoke_machine(c)Figure 5: Examples of IGs illustrating the restrictions put on performing deductive inference
within our IG-formalism (a-c).

465

470

475

480

485

490

495

In Fig. 5c, Example 4a from Sect. 2.4 illustrating Pearl’s constraint for
deductive inference is modelled as an IG. As smoke machine ∈ Ep , smoke isdeductively inferred from smoke machine using g1 by condition 1 of Definition
9. fire cannot in turn be inferred from smoke using g2 , as g2 ∈ Ge and smoke
is deductively inferred using g1 ∈ Gc .

4.2.2. Abductive Inference
Next, we specify under which conditions we consider a configuration of generalisation arcs and evidence to express abductive inference.
Definition 10 (Abductive inference). Let GI = (P, AI ) be an IG, and let
Ep ⊆ P be an evidence set. Let p1 , . . . , pn , q ∈ P, with {p1 , . . . , pn } ∩ Ep = ∅.
Then given Ep , p1 , . . . , pn are abductively inferred from q using a generalisationg : {p1 , . . . , pn } → q in Gc , denoted q g p1 ; . . . ; q g pn , iff:
1. q ∈ Ep , or;
2. q is deductively inferred from r1 , . . . , rm ∈ P using a generalisation g 0 : {r1 , . . . ,rm } → q, g 6= g 0 (see Definition 9), where g 0 ∈ G \ Gc , or;
3. q is abductively inferred from a proposition r ∈ P using a generalisation
g 0 : {q, r1 , . . . , rm } → r in Gc , r1 , . . . , rm ∈ P.
In accordance with our assumptions stated in Sect. 2.2, abduction is modelledusing only causal generalisations and not evidential generalisations. The condition {p1 , . . . , pn } ∩ Ep = ∅ ensures that abduction cannot be performed witha causal generalisation to infer its antecedents in case at least one of its antecedents is already observed. Furthermore, abduction can only be performed
using a generalisation g ∈ Gc to infer its antecedents Tails(g) from its consequent Head(g) in case Head(g) has been affirmed in that either Head(g) isobserved (i.e. Head(g) ∈ Ep ), Head(g) is deductively inferred, or Head(g) isitself abductively inferred. In correspondence with Pearl’s constraint (see Sect.
2.4), we assume in condition 2 that propositions p1 , . . . , pn ∈ P cannot be abductively inferred from a proposition q ∈ P using a generalisation g ∈ Gc if its
consequent q is deductively inferred using a generalisation g 0 6= g, g 0 ∈ Gc .
Example 14. In the IG of Fig. 6a, p is abductively inferred from q using
generalisation g1 ∈ Gc by condition 2 of Definition 10, as q is deductively
14

r

g3

c

q
g2

e

c

r

q

g1

g1

p

p1

c

(a)

c

r1

g2

p2
(b)

Figure 6: Examples of IGs illustrating abductive inference (a-b).

500

inferred from r using generalisation g2 ∈ Ge by condition 1 of Definition 9. In
the IG of Fig. 6b, q and r1 are abductively inferred from r using generalisation
g3 : {q, r1 } → r in Gc by condition 1 of Definition 10, as r ∈ Ep . Then bycondition 3 of Definition 10, p1 and p2 are abductively inferred from q using
generalisations g1 and g2 , respectively.
The following example illustrates that Pearl’s constraint for mixed deductiveabductive inference is adhered to (see Sect. 2.4).

505

Example 15. In Fig. 7a, Example 4b from Sect. 2.4 is modelled as an IG. As
smoke machine ∈ Ep , smoke is deductively inferred from smoke machine using
g1 . fire cannot be inferred from smoke, as g2 ∈ Gc and smoke is deductively
inferred using g1 ∈ Gc (condition 2 of Definition 10).

4.2.3. Prediction
Our IG-formalism allows for predictive reasoning (deductive inference with causal
generalisations, see Sect. 2.1).

510

515

Remark 1 (Prediction). Let GI = (P, AI ) be an IG, and let Ep ⊆ P be an
evidence set. Let g ∈ Gc . Then Head(g) is predicted from Tails(g) iff Head(g)is deductively inferred from Tails(g).
Example 16. In Fig. 7b, Example 3 from Sect. 2.4 illustrating prediction
is modelled as an IG. From smoke, fire is abductively inferred using g1 , assmoke ∈ Ep . Then heat is deductively inferred (or predicted) from fire using g2(condition 3 of Definition 9).

¬heat
smoke
g2 c
c g1
fire
smoke_machine
(a)

heat
g2

c

smoke
c g1
fire

(b)

Figure 7: An IG illustrating Pearl’s constraint for mixed deductive-abductive inference (a);an IG illustrating prediction (b).

15

520

525

In the above example, prediction is performed with g2 by affirming its antecedent fire via abductive inference; besides illustrating prediction, this example thus also illustrates that mixed abductive-deductive inference can be
performed within our IG-formalism, as apparent from Definitions 9 and 10.
4.2.4. Ambiguous Inference
The conditions under which we consider a configuration of generalisation arcs
and evidence to express deductive and abductive inference according to Definitions 9 and 10 are not mutually exclusive. Under specific conditions, bothinference types can be established from the same causal generalisation in an IG
given the provided evidence; the inference type is, therefore, ambiguous (seeSect. 2.5). The following result follows directly from Definitions 9 and 10.

530

Remark 2 (Ambiguous inference). Let GI = (P, AI ) be an IG, and let Ep ⊆ P
be an evidence set. Let g ∈ Gc with Head(g) = q, Tails(g) = {p1 , . . . , pn }, andp1 , . . . , p n , q ∈/ Ep . Assume that for every p1 , . . . , pn , q, it holds that it is deductively or abductively inferred. Then q is deductively inferred from p1 , . . . , pn
and p1 , . . . , pn are abductively inferred from q using g.

535

Example 17. Consider the IG of Fig. 4. Given Ep , murder is deductively
inferred from police using g1 and mot1 and mot2 are deductively inferred fromtes1 and tes2 using g2 and g4 , respectively. As murder, mot1 , mot2 ∈/ Ep ,
murder is deductively inferred from mot1 and mot2 and mot1 and mot2 are
abductively inferred from murder using g3 and g5 , respectively.


540

545

550

555

4.2.5. Competing Alternative Explanations
Finally, we consider how the concept of competing alternative explanations (seeSect. 2.2) is captured within our IG-formalism.
Definition 11 (Competing alternative explanations). Let GI = (P, AI ) be an
IG, and let Ep ⊆ P be an evidence set. Let g, g 0 ∈ Gc with g 6= g 0 , Head(g) =Head(g 0 ) = p, and possibly Tails(g) ∩ Tails(g 0 ) 6= ∅. Then given Ep , Tails(g)is considered to be in competition with Tails(g 0 ) for the same effect expressed by
p in case Tails(g) and Tails(g 0 ) are abductively inferred from p given Ep using
g and g 0 , respectively, and p can neither be deductively inferred from Tails(g)nor from Tails(g 0 ) given Ep using g or g 0 , respectively.
The condition that g, g 0 ∈ Gc with g 6= g 0 , Head(g) = Head(g 0 ) = p implies that every pair of propositions pi , qj for pi ∈ Tails(g), qj ∈ Tails(g 0 )are considered alternative causes of p by condition 2a of Definition 3. The
condition that only abduction and not deduction is performed with g and g 0
implies that the inference type for neither g nor g 0 is ambiguous (see Remark
2). The above definition captures competition between sets of propositions
Tails(g) and Tails(g 0 ), as these sets are abductively inferred from p using g and
g 0 , respectively. More specifically, individual propositions in Tails(g) are notin competition with individual propositions in Tails(g 0 ) in case separate causal
generalisations gi : pi → p and gj0 : qj → p for pi ∈ Tails(g), qj ∈ Tails(g 0 ) are16

murderg3

murderg1epolice

g3

c

c

mot1

g5

mot1
g2 e

mot2

tes1

(a)

c

mot2
e g4
tes2
(b)

Figure 8: Adjustment to the IG of Fig. 2a involving two competing alternative explanations
mot 1 and mot 2 for murder (a); the IG of Fig. 2b with evidence Ep and resulting inference
steps now indicated, involving two non-competing alternative explanations mot 1 and mot 2
for murder (b).

560

565

570

not provided. In case a causal generalisation arc has multiple tails, we assume
that these tails are not in competition among themselves, as the generalisation
expresses that only the tails together allow us to infer the head.
Example 18. Consider Fig. 8a, which depicts an adjustment to the IG of Fig.
2a. Given Ep = {police}, propositions mot1 and mot2 are abductively inferredfrom murder using g3 and g5 , respectively, as murder is deductively inferredfrom police using g1 . Furthermore, murder can neither be deductively inferredfrom mot1 nor from mot2 using g3 or g5 , respectively. Therefore, mot1 andmot2 are in competition for common effect murder.
In Fig. 8b, the IG of Fig. 2b is again depicted, where evidence Ep ={tes1 , tes2 } and resulting inferences are also indicated. In this IG, murder isdeductively inferred from {mot1 , mot2 } given Ep using g3 : {mot1 , mot2 } →murder in Gc ; therefore, mot1 and mot2 are not in competition for murder.
5. Bayesian Networks

575

580

In this section, Bayesian networks (BNs) [20] are reviewed. A BN compactly
represents a joint probability distribution Pr(V) over a finite set of discreterandom variables V; in this paper we assume all variables to be Boolean, where
we write v to denote V = true and ¬v to denote V = false. Formally, a BN is
defined as follows:
Definition 12 (Bayesian network). A Bayesian network (BN) is a pair (GB , Pr),
where GB is a directed acyclic graph (DAG) (V, AB ) over nodes V representing
random variables2 . AB ⊆ V × V is a set of directed arcs Vi → Vj from parent
Vi ∈ V to child Vj ∈ V, where Par(V) denotes the set of parents of V andCh(V) denotes the set of children of V. Pr is a probability function which specifies for each variable V ∈ V a conditional probability table (CPT). This CPT
2 There is a one-to-one correspondence between nodes and variables in BNs. Throughout
this paper, the terms ‘node’ and ‘variable’ are, therefore, used interchangeably.

17

describes the conditional probability distributions Pr(V | x) for each possible
joint value combination x for Par(V).
585

590

595

600

605

610

The reflexive, transitive closures of V under the parent and child relations aredenoted by Par∗ (V) and Ch∗ (V), respectively, where nodes in Par∗ (V) arecalled ancestors of V and nodes in Ch∗ (V) are called descendants of V.
A BN is generally used for probabilistic inference [20], that is, calculating any
prior or posterior distribution over the variables represented in the network. Posterior distributions are obtained by instantiating one or more variables EV ⊆ V
in that they are set to a specific value. Instantiations are also called evidence.
The inference algorithms associated with the BN-formalism provide for computing probabilities of interest and for processing evidence; these algorithms
constitute the basic building blocks for reasoning with knowledge represented
in the formalism. As in the current paper the focus lies on the knowledge that isrepresented by a BN by means of its graphical structure GB and its probability
function Pr, algorithms for probabilistic inference are not further discussed.
Example 19. An example of a BN graph and one of its CPTs is depicted in Fig.
9, where ovals represent nodes and instantiated nodes are shaded. In this BNgraph, we are interested in whether a given suspect committed a burglary (Bur).
This node is connected by arcs to nodes Mot1 , Mot2 and Opp, which describe
whether the suspect had motive(s) and opportunity to commit the burglary. Inturn, nodes Mot1 , Mot2 and Opp are connected to instantiated nodes Tes1 , Tes2
and Tes3 , which capture the testimonies provided to these claims.

5.1. Bayesian Network Graphs
The BN graph GB encodes the probabilistic independence relation among its
variables by means of the notion of d-separation, which is defined by the notionsof blocked and active chains. In the following, let GB = (V, AB ) be a BN graph.
Definition 13 (Chain). A chain c = (V1 , A1 , V2 , . . . , An−1 , Vn ) is a sequence ofdistinct nodes V1 , . . . ,Vn ∈ V and arcs A1 , . . . , An−1 ∈ AB such that for every
Ai , 1 ≤ i < n, it holds that either Ai ≡ Vi → Vi+1 or Ai ≡ Vi+1 → Vi .
Definition 14 (Head-to-head node). A node V ∈ V is called a head-to-headnode on a chain c in GB if it has two incoming arcs on c.

615

Definition 15 (Blocked chain). A chain c between nodes V1 ∈ V and V2 ∈ V
in GB is blocked by a (possibly empty) set of instantiated nodes iff it includes
a node V ∈/ {V1 , V2 } such that either:• V is an uninstantiated head-to-head node on c without instantiated descendants, or;• V is instantiated and has at most one incoming arc on c.

620

A chain that is not blocked by the evidence is called active.
Definition 16 (d-separation). Two sets of nodes V1 ⊆ V and V2 ⊆ V are
d-separated by a set of nodes Z ⊆ V iff there exist no active chains between any
node in V1 and any node in V2 given instantiations for nodes Z.
18

Bur
Mot1 Mot2 Opp
t
t
t
t
t
f
t
f
t
t
f
f
f
t
t
f
t
f
f
f
t
f
f
f

Bur
Mot1

Mot2

Opp

Tes1

Tes2

Tes3

t

f

0.90
0.20
0.70
0.10
0.80
0.10
0.05
0.01

0.10
0.80
0.30
0.90
0.20
0.90
0.95
0.99

(b)

(a)

Figure 9: An example of a BN (a); CPT for node Bur (b), where Mot1 and Mot2 exhibit anegative product synergy wrt value Bur = true in presence of uninstantiated parent Opp.

625

630

If V1 and V2 are d-separated given instantiations for Z ⊆ V, then their corresponding variables are considered conditionally independent given Z.
Example 20. In Fig. 9, given the evidence for Z = {Tes1 , Tes2 , Tes3 } allchains between Mot1 and Mot2 are blocked, as Bur is an uninstantiated headto-head node without instantiated descendants on chain (Mot1 , Mot1 → Bur,
Bur, Mot2 → Bur, Mot2 ); hence, Mot1 and Mot2 are considered conditionallyindependent given the evidence for Z.

Finally, we review the following concept from graph theory.
Definition 17 (Weakly connected component). Let G = (V, A) be a directed
graph and let C = (Vc , Ac ) with Vc ⊆ V and Ac ⊆ (Vc × Vc ) ∩ A be a
sub-graph of G. Then C is a weakly connected component of G iff:

635

640

645

1. For every pair of nodes V1 , V2 ∈ Vc , there exists a chain between V1 andV2 in C;
2. C is a maximal sub-graph of G for which property 1 holds.
5.2. Intercausal Interactions and Qualitative Probabilistic Constraints
Next, we review the concepts of intercausal interactions and qualitative probabilistic constraints. In case a head-to-head node or one of its descendants in a
BN graph is instantiated, an active chain is induced between the parents of thehead-to-head node, allowing for intercausal interactions 3 . If one of the parents
is true, then the probability of another parent being true as well may change,depending on the synergistic effect modelled in the CPT for the head-to-headnode. In case the probability that one of the other parents is true decreases, thisis called the ‘explaining away’ effect [13]. For Boolean nodes, we will generally
assume an ordering true > false on its values unless specified otherwise. In case
3 We note that, while the term ‘intercausal interactions’ is used, these interactions can also
occur regardless of the type of relation between parents and child.

19

650

655

this ordering is reversed, then the occurrences of these two values need to beinterchanged in the equations appearing in Definitions 18 and 20. To achieve
the explaining away effect between two parents V1 and V3 of V2 for value v2 ,the CPT for V2 needs to be constrained such that V1 and V3 exhibit a negative
product synergy wrt v2 . First, we review the concept of product synergy I [13],which captures the special case in which all other parents of V2 are instantiated.
Definition 18 (Product synergy I). Let B = (GB , Pr) be a BN and let V1 ,V3 ∈V be parents of V2 ∈ V in GB . Let X = Par(V2 ) \ {V1 ,V3 } and let x be the
combination of observed values for X. Then V1 and V3 exhibit a negative
product synergy wrt v2 , written X− ({V1 ,V3 }, v2 ), iffPr(v2 | v1 , v3 , x) · Pr(v2 | ¬v1 , ¬v3 , x) ≤ Pr(v2 | v1 , ¬v3 , x) · Pr(v2 | ¬v1 , v3 , x)

660

665

670

675

680

685

In case X = ∅, then this equation simplifies by leaving out every occurrence ofx. V1 and V3 exhibit a zero product synergy wrt v2 , written X0 ({V1 ,V3 }, v2 ), incase ≤ in the above equation is replaced by =. In this case, no direct intercausal
interaction effect exists between parents V1 and V3 for value v2 of V2 . V1 andV3 exhibit a positive product synergy wrt v2 , written X+ ({V1 ,V3 }, v2 ), in case≤ is replaced by ≥ in the above equation. In this case, the joint occurrence ofthe causes may be a more likely explanation of the common effect than would
either of them considered individually.
Next, the case is considered in which X 6= ∅ is not instantiated to a combination of values. First, we review the concept of matrix half negative semidefiniteness.
Definition 19 (Half negative semi-definite matrix). Let M be a square n × nmatrix, n ≥ 1, and let x be any non-negative vector x of n elements. Then M
is called half negative semi-definite iff xT M x ≤ 0.
Similarly, a square matrix M is called half positive semi-definite iff xT M x ≥ 0
for any non-negative vector x of n elements. We now provide the definition ofextended product synergy, termed product synergy II [13].
Definition 20 (Product synergy II). Let B = (GB , Pr) be a BN and let V1 ,V3 ∈ V be parents of V2 ∈ V in GB . Let X = Par(V2 )\{V1 , V3 }. Let n denotethe number of possible combinations of values for X. Then V1 and V3 exhibit
a negative product synergy wrt v2 iff the n × n matrix M with elements Mij =Pr(v2 | v1 , v3 , xi ) · Pr(v2 | ¬v1 , ¬v3 , xj ) − Pr(v2 | v1 , ¬v3 , xi ) · Pr(v2 | ¬v1 , v3 , xj )is half negative semi-definite for all combinations of values xi and xj for X.
For a positive or zero product synergy, the matrix M has to be half positive
semi-definite or zero, respectively. Note that product synergy I is a special
case of product synergy II; hence, in referring to the general concept of productsynergy throughout this article, we are referring to product synergy II.
Example 21. Consider the BN of Fig. 9. The entries of the CPT of Fig.
9b are chosen such that Mot1 and Mot2 exhibit a negative product synergy wrt
20

value Bur = true in presence of uninstantiated parent Opp. Specifically, the 2×2
matrix M consisting of the following four elements is half negative semi-definite:690

M11 = 0.9 · 0.05 − 0.7 · 0.8 = −0.515; M12 = 0.9 · 0.01 − 0.7 · 0.1 = −0.061
M21 = 0.2 · 0.05 − 0.1 · 0.8 = −0.070; M22 = 0.2 · 0.01 − 0.1 · 0.1 = −0.008 

695

700

705

5.3. BN Construction
BN construction is typically an iterative process. After constructing an initial
BN graph, it should be verified that it is acyclic and that it correctly captures the(conditional) independencies. If the graph does not yet exhibit these properties,
arcs should be reversed, added or removed by the BN modeller in consultation
with the domain expert. We call this the ‘graph validation step’. Related
research on BN graph construction is reviewed in Sect. 9.2.
The (conditional) probabilities of the BN are elicited in a separate quantification step. In the current paper, the focus lies on deriving the graphicalstructure of BNs and not on deriving the modelled probability distribution, although in some cases qualitative constraints on the (conditional) probabilitiesof the BN under construction in the form of product synergies are derived thatcan subsequently be used in the quantification step.
6. Constructing Bayesian Network Graphs from Information Graphs

710

715

720

725

730

Based on our IG-formalism, we now propose a structured approach for automatically constructing a directed BN graph from an IG. In our approach, we
focus on exploiting the knowledge captured in an IG to constrain the graphical structure of the BN and the conditional independence relation it encodes
by means of the d-separation criterion, as well as constraining its probability
function by means of product synergies.
Our IG-formalism serves as an intermediary formalism between analyses performed using informal reasoning tools and BNs. We expect direct IG construction to be more straightforward than direct BN construction for domain experts
unfamiliar with the BN-formalism, a claim we intend to empirically evaluate in
our future work. We believe this to be a plausible assumption, however, among
other things due to the fact that the arcs of a BN are easily misinterpretedby domain experts unfamiliar with BNs as non-symmetric relations of cause
and effect instead of collectively encoding an independence relation [12], making manual BN construction a difficult and error-prone process (see also [18]).
Moreover, it is justified to assume that information regarding causality is present
in the domain expert’s original analysis (see [2, 6]), and in manual BN graphconstruction, conditional independencies are typically not directly elicited, butinstead the notion of causality is commonly used as a guiding principle [16, 20].
In IGs, causality information is made explicit by means of causal and evidential generalisations and can thus be directly used in BN graph construction.
Whereas the ultimate goal of our approach is to facilitate domain experts inconstructing BNs that can be used to evaluate their problems in a probabilistic manner, our proposed approach only serves for constructing an initial BN
21

735

740

745

graph and for deriving qualitative constraints on the probabilities of the BN
under construction. More specifically, as IGs only express qualitative and notquantitative (probabilistic) information, our BN construction approach can only
serve for constructing a partially specified initial BN. Moreover, the qualitative
probabilistic constraints that are derived from an IG given the evidence are
generally only a subset of those required for the specification of a QPN [33](see also Sect. 9.3). Hence, initial BNs constructed by our approach are only
partially specified and cannot be directly used for probabilistic inference. The
derived constraints may serve as input for a subsequent elicitation procedure forobtaining a fully specified QPN or BN for (qualitative) probabilistic inference.
In Sects. 6.1 and 6.2 we motivate the steps of our approach for automaticallyconstructing an initial BN graph from an IG; the approach itself is presented in
Sect. 6.3. In Sect. 6.4 we then explain and illustrate the steps of our approachwith several examples.
6.1. Extracting Information from an IG
First, we consider the graphical structure of the BN. For constructing a BNgraph from an IG, the IG’s structure is used, specifically the generalisations,
exceptions and negations expressed in the graph.

750

755

760

765

770

Information in Proposition Nodes. For every proposition p ∈ P in an
IG, we propose to form a single BN node in V describing both values p and¬p, as captured by step 1 of our approach. By this step, two propositionsp, −p ∈ P involved in negation are captured as two mutually exclusive values ofthe same node. Negation arcs present in an IG can thus be disregarded in BN
construction, as such arcs are drawn between a pair p, q ∈ P iff q = −p.
Information in Causal and Evidential Generalisations. In the manual
construction of BN graphs, arcs are typically directed using the notion of causality as a guiding principle [16, 20]. Specifically, if the domain expert indicatesthat p or ¬p typically causes q or ¬q, then the arc is set from node P to node Q.
By following this heuristic, causes form a head-to-head connection in the nodecorresponding to their common effect. As such, possible interactions between
causes, for example due to the fact that they could be in competition, can bedirectly captured in the CPT for this node. Hence, we propose to use the same
heuristic in automatically directing arcs, where we exploit causality information
explicitly expressed in an IG by means of causal and evidential generalisations.
Specifically, arcs in the BN graph are set in the same direction as generalisationarcs in Gc and in the opposite direction for generalisation arcs in Ge . This iscaptured by step 2 of our approach.
Information in Exceptions. Arcs in Exc denote exceptions to generalisations. For instance, if a generalisation is in the evidential direction, then an
exception suggests an alternative cause for the same effect. Exceptions to causal
generalisations do not suggest alternative causes for the same effect, but do possibly interact with them (examples are provided in Sect. 6.4.2). Accordingly,
22

775

we propose to enable capturing possible interactions between an exception anda generalisation arc, if any, in the CPTs for head-to-head nodes formed in the
BN graph. This is captured by step 3 of our approach.
6.2. Exploiting Induced Inferences Expressed by IGs

780

785

By itself, a generalisation arc only captures knowledge about the world in conditional form; only when considering the available evidence Ep in the IG candirectionality of inference be read from the graph. In comparison, from a BNgraph we can read the chains between nodes that are active given the evidence
and will be exploited to propagate the evidence upon probabilistic inference. In
our approach, we want to ensure that the sequences of propositions that canbe iteratively inferred from each other given Ep in an IG are captured in the
BN graph by means of active chains given the available evidence for EV ⊆ V
corresponding to Ep ⊆ P. In Sect. 7.2, we formally prove that BN graphs
constructed by our approach indeed allow reasoning patterns similar to the sequences of propositions that can be iteratively inferred from each other given
Ep in the original IG.

805

Exploiting Competing Alternative Explanations. Probabilistic constraints
on the BN under construction are derived by considering the inferences that canbe read from an IG given Ep . In case the tails of two causal generalisations arecompeting alternative explanations for the common effect expressed by the head
given Ep (see Definition 11), we propose to constrain the CPT for the variablecorresponding to the head such that the explaining away effect can occur between the variables corresponding to the tails of the generalisations, as captured
by step 5a. In case abductive inference is performed with a generalisation given
Ep , then the tails are not in competition among themselves and the explaining
away effect should not occur, as captured by step 5b. Similarly, the tails of ageneralisation are not in competition among themselves if deductive inferenceis performed, which is captured by the same step.
We note that various evidence sets Ep can be used to establish inferencesfrom the same IG, and thus that, depending on Ep , different probabilistic constraints may be derived on the BN under construction. The structure of the BN
does not depend on Ep , as the IG’s structure is used in BN graph construction
and not the IG’s inferences.

810

Exploiting Interactions Between Exceptions and Generalisations. The
presence of an exception to a generalisation g weakens an inference step performed with g. Depending on whether deductive or abductive inference is performed with g given Ep , different probabilistic constraints are derived, as captured by step 6 of our approach.

790

795

800

6.3. The Approach
In this subsection, we present the steps of our approach. Let Var : P → V bean operator mapping every proposition p or ¬p ∈ P in an IG to a BN node

23

815

820

825

830

Var(p) = Var(¬p) ∈ V describing values p and ¬p. For an IG GI = (P, AI ), a
BN graph GB = (V, AB ) is constructed as follows:1) ∀p, ¬p ∈ P, include Var(p) in V; if p or ¬p ∈ Ep , also include Var(p) in EV .
2) For every generalisation arc g : {p1 , . . . , pn } → p:2a) If g ∈ Ge , include Var(p) → Var(pi ), i = 1, . . . , n in AB .
2b) If g ∈ Gc , include Var(pi ) → Var(p), i = 1, . . . , n in AB .
3) For every exception arc exc : p
g in Exc with g : {q1 , . . . , qn } → q:3a) If g ∈ Ge , include Var(p) → Var(qi ), i = 1, . . . , n in AB .
3b) If g ∈ Gc , include Var(p) → Var(q) in AB .
While our approach exploits the domain knowledge captured in the IG in constructing an initial BN graph, the IG may lack information needed to prevent
cycles and unwarranted (in)dependencies in the obtained BN graph; hence, thefollowing manual validation step should be performed by the BN modeller in
consultation with the domain expert. We note that this type of validation isstandard in BN construction, especially in data-poor domains (see Sect. 5.3):
4) Manually verify the properties of the constructed graph GB by applying
the standard graph validation step (see Sect. 5.3).
We define the following probabilistic constraints on the BN under construction:

8355) For every generalisation arc g : P1 → q in G, P1 = {p1 , . . . , pn } ⊆ P:5a) ∀g 0 : Q → q in G, Q = {q1 , . . . , qm } ⊆ P, g 6= g 0 such that bothg, g 0 ∈ Gc and for which, given Ep , P1 and Q are competing alternative explanations for the common effect expressed by q (see Definition
11), constrain the CPT for Var(q) such that X− ({Var(pi ), Var(qj )}, q)for pi ∈ P1 \ Q, qj ∈ Q \ P1 .
5b) If g is used to perform inference given Ep , constrain the CPT for Var(q)such that Xδ ({Var(pi ), Var(pj )}, q) with δ 6= −, pi , pj ∈ P1 , pi 6= pj .

8506) For every exc : p
g in Exc with p ∈ P and g : {q1 , . . . , qn } → q in G:6a) If g ∈ Ge and q is deductively inferred from q1 , . . . , qn given Ep usingg, constrain the CPT for Var(qi ) such that X− ({Var(p), Var(q)}, qi ),i = 1, . . . , n. If in addition ∃exc0 : p0
g in Exc, further constrain the
CPT for Var(qi ) such that X− ({Var(p), Var(p0 )}, qi ), i = 1, . . . , n.
6b) If g ∈ Gc and q is deductively inferred from q1 , . . . , qn given Ep usingg, constrain the CPT for Var(q) such that Pr(q | p, q1 , . . . , qn ) < Pr(q |¬p, q1 , . . . , qn ).
6c) If g ∈ Gc and q1 , . . . , qn are abductively inferred from q given Ep usingg, constrain the probabilities of the BN such that Pr(qi | p, q) < Pr(qi |¬p, q), i = 1, . . . , n.

855

We reiterate that the initially constructed BN by our approach should always
be verified by the BN modeller in consultation with the domain expert, which
includes verifying the derived probabilistic constraints. After this verification
step, the derived constraints can be used in subsequent probability assessment,
thereby partially simplifying it. In particular, since we are considering BN con-

840

845

24

860

865

870

875

880

885

struction in data-poor domains the required conditional probabilities will often
need to be elicited from domain experts, where it can be monitored whether theassessed conditional probabilities satisfy the derived probabilistic constraints.
We note that the above probabilistic constraints concern intercausal interactions between individual nodes and not sets, as to the best of our knowledge noapproaches have been proposed in the literature that allow for capturing interactions between sets of parents of a node. The type of competition between setsof nodes in an IG as captured by Definition 11 can, therefore, not be straightforwardly captured between variables in a corresponding BN; instead, in step 5a
we propose to constrain the CPT for Var(q) such that X− ({Var(pi ), Var(qj )}, q)for pairs of propositions pi ∈ P1 \ Q, qj ∈ Q \ P1 , where the intersection ofP1 and Q is not considered. Similarly, in step 6a interactions between pairs of
nodes and not sets are considered. In our future work, we intend to investigate
whether the concept of product synergy can be extended to sets of nodes.
6.4. Explanation and Illustration of the Steps of the Approach
In this section, we explain and illustrate the steps of our approach through ourrunning example, introduced in Sect. 3. In Sect. 6.4.1 we illustrate that steps
1 − 2 of our approach suffice for constructing BN graphs from restricted IGs notincluding exception arcs, where the CPTs of the BN under construction should
be constrained according to step 5. In Sect. 6.4.2 we then illustrate that the
BN under construction needs to be further constrained in case exception arcs
are present in the IG; this is accounted for in steps 3 and 6 of our approach.
6.4.1. Explanation and Illustration of Steps 1 − 2 and 5First, we explain and illustrate the main idea behind our approach by applying
it to the IG depicted in Fig. 8a.
Steps 1 − 2. The first step is to capture every proposition in GI and its negation as two mutually exclusive values of the same BN node in GB . In steps 2aand 2b, arcs in the BN graph are directed using the notion of causality in thatfor every g ∈ Gc , arcs in the BN graph are directed from nodes corresponding
to Tails(g) to Var(Head(g)), and vice versa for g ∈ Ge . This formalises the approach typically taken in the manual construction of BN graphs, namely that of
MurderPolice
Mot1

Mot1
t
t
f
f

Murder
Mot2

Mot2 t
t
0.4
f
0.6
t
0.5
f
0.1

f
0.6
0.4
0.5
0.9

(b)

(a)

Figure 10: BN graph constructed from the IG of Fig. 8a by our approach (a); a possible CPT
for node Murder (b).

25

setting arcs in the causal direction as a guiding principle [16, 20]. The resulting
BN graph is depicted in Fig. 10a.

890

895

900

905

910

915

920

Step 5a. The inferences that can be read from an IG given the evidence allow
us to derive constraints on the CPTs of the BN. In the IG of Fig. 8a, given Ep ={police} propositions mot 1 and mot 2 are abductively inferred from murder using
g3 and g5 , respectively, as given Ep murder is deductively inferred from policeusing g1 . Therefore, mot 1 and mot 2 are competing alternative explanations
for common effect murder in that accepting one explanation will diminish ourbelief in the other (see Definition 11). We propose to link this type of intercausal
interaction in IGs to the explaining away effect in BNs. Specifically, as proposedin step 5a of our approach, the CPT for Murder should be constrained suchthat X− ({Mot1 , Mot2 }, murder). Note that the IG only informs us that there
should be a negative product synergy between Mot1 and Mot2 wrt value Murder= true; it does not inform us whether a product synergy should also be exhibited
between these variables wrt value Murder = false, as proposition ¬murder does
not appear in the IG. Figure 10b depicts a possible CPT for Murder, whereX− ({Mot1 , Mot2 }, murder) as 0.4·0.1 ≤ 0.6·0.5. However, as 0.6·0.9 ≥ 0.4·0.5,
it also holds that X+ ({Mot1 , Mot2 }, ¬murder). Care should be taken, therefore,
in eliciting the involved probabilities, as it may be undesirable that a positive
product synergy for value ¬murder is exhibited.
By following steps 2a and 2b of our approach, causes automatically form ahead-to-head connection in the node corresponding to their common effect for
any given IG; interactions between causes in an IG, for instance because they arecompeting alternative explanations for the common effect, can, therefore, always
be directly captured in the CPT for the node corresponding to the common
effect. We note that directing arcs in the BN graph in the same direction
as the inferences that can be read from an IG given the evidence would leadto undesirable results. Consider the IG depicted in Fig. 11a. By directing
arcs according to the inferences that can be read from this IG given Ep , theBN graph of Fig. 11b is constructed. In the IG of Fig. 11a, p and q arecompeting alternative explanations for common effect r given Ep ; however, thiscompetition cannot be directly captured in the CPT for node R in the BNgraph of Fig. 11b as a divergent connection is formed. Moreover, all chains
between P and Q are blocked given EV = {R}; hence, interactions between
causes expressed in an IG cannot always be captured by directing arcs in a
r
g1

c

c

q

p
(a)

R

g2

P

R
Q

(b)

P

Q
(c)

Figure 11: Example of an IG (a); the BN graph constructed by directing arcs according to theinferences that can be read from this IG given Ep (b); the BN graph constructed by directing
arcs according to the generalisations in the IG (c).

26

Murder

Murder
Mot1

Mot2

Tes1

Tes2

Mot1
t
t
f
f

(a)

Mot2 t
t
0.8
f
0.2
t
0.2
f
0.1
(b)

Figure 12: BN graph constructed from the IG of Fig. 8b by our approach (a); a possible CPT
for node Murder (b).

corresponding BN graph according to the induced inferences in an IG.

925

930

935

940

945

950

Step 5b. Next, consider the IG of Fig. 8b. Given Ep , murder is deductively
inferred from mot 1 and mot 2 using g3 ; therefore, mot 1 and mot 2 are not competing alternative explanations for murder in this IG. By following steps 1 − 2of our approach, the BN graph of Fig. 12a is constructed. As mot 1 and mot 2
are not competing alternative explanations for murder in this example, we needto assure that the explaining away effect cannot occur between Mot1 and Mot2
for value Murder = true. This can be achieved by constraining the CPT for
Murder such that Xδ ({Mot1 , Mot2 }, murder) for δ 6= −, as captured by step 5bof our approach. This is a relaxation of our previously proposed solution [39],in which we proposed to constrain the CPT for the node corresponding to thecommon effect such that a zero product synergy is exhibited wrt the indicatedvalue in the IG. Specifically, we now also allow that a positive product synergy is
exhibited; what counts is that no negative product synergy is exhibited between
Mot1 and Mot2 for value Murder = true, as mot 1 and mot 2 are not competingalternative explanations for the common effect. Figure 12b depicts a possible
CPT for Murder, where X+ ({Mot1 , Mot2 }, murder) as 0.8 · 0.1 ≥ 0.2 · 0.2.
6.4.2. Explanation and Illustration of Steps 3 and 6
Next, IGs including exception arcs are considered.
Step 3a. In Fig. 13a, an example of an IG is depicted in which exceptions
to both an evidential and a causal generalisation are provided. Proposition lie,
which states that Marjan had reason to lie when giving her testimony, provides an exception to the evidential generalisation tes3 → ¬murder. Since tes 3
is either the result of Marjan truly not committing the murder or due to a lie,
¬murder and lie can be seen as competing alternative explanations for Marjan’s
testimony. Generally, exceptions to an evidential generalisation can be considered competing alternative explanations for the common effects expressed by
the antecedents of the generalisation. We therefore propose to enable capturing such interactions between an exception and an evidential generalisation byforming head-to-head nodes in the nodes corresponding to the tails of the generalisation arc. By step 2a of our approach, the BN graph under construction
includes arc Murder → Tes3 . A head-to-head node can, therefore, be formed in27murderepolicec
mot1¬murder

Police

¬opp

e

lie

e
alibi

tes3

e
tes4

Mot1

Murder
Opp

Lie

Alibi

(a)

Tes3
(b)

Tes4

Murder Lie
f
t
f
f
t
t
t
f

Tes3
t
0.2
0.8
0.3
0.01

(c)

Figure 13: IG involving exceptions to generalisation arcs in Ge and Gc (a); the corresponding
BN graph constructed by our approach (b); a possible CPT for node Tes3 (c).

955

960

965

970

975

980

985

node Tes3 by adding additional arc Lie → Tes3 to the BN graph; this is captured
by step 3a of our approach.
Step 6a. Given Ep = {police, alibi, tes 3 , tes 4 }, ¬murder is deductively inferredfrom tes 3 . As proposition lie provides an exception to the generalisation usedin performing this inference step and thereby weakens the inference, we propose
to constrain the CPT for Tes3 such that the explaining away effect can occur
between Lie and Murder for value Tes3 = true. This is achieved by constraining
the CPT for Tes3 such that X− ({Lie, Murder}, tes3 ), as captured by step 6a of
our approach. In this particular example, ¬murder is one of the possible causesof tes 3 ; therefore, for variable Murder the ordering false > true is assumed. For
example, the CPT for Tes3 can be chosen as in Fig. 13c, as in this case it holds
that Pr(tes3 | ¬murder, lie) · Pr(tes3 | murder, ¬lie) = 0.2 · 0.01 ≤ Pr(tes3 |¬murder, ¬lie) · Pr(tes3 | murder, lie) = 0.8 · 0.3.
We note that multiple exceptions to an evidential generalisation arc g express
different competing alternative explanations for the common effects expressedby Tails(g). We therefore propose to constrain the CPTs for the nodes corresponding to the tails such that a negative product synergy is exhibited between
the nodes corresponding to each pair of exceptions, as captured by step 6a of
our approach.
Step 3b. In the IG of Fig. 13a, proposition ¬opp, which states that Marjan
did not have opportunity to commit the murder as she has an alibi (alibi ),provides an exception to the causal generalisation arc mot 1 → murder. In
contrast with the exception to the evidential generalisation arc, this exception
cannot be considered a competing alternative explanation for the tail of thegeneralisation arc; the absence of opportunity cannot be considered a cause for
motive. Instead, it allows us to infer that Marjan did not murder Leo (¬murder ).
For exceptions to generalisations g ∈ Gc , we therefore propose to form a headto-head node in Var(Head(g)) as opposed to in Var(pi ) for pi ∈ Tails(g). By
step 2b of our approach, the BN graph under construction includes arc Mot1 →Murder. A head-to-head node can, therefore, be formed in Murder by adding
additional arc Opp → Murder to the BN graph; this is captured by step 3b ofour approach. The corresponding BN graph is depicted in Fig. 13b. As Murder
describes both values murder and ¬murder, possible interactions, if any, between
mot 1 and ¬opp, and hence between Mot1 and Opp, can be captured in the CPT
for this node.
28

990

995

1000

1005

1010

1015

Steps 6b-c. Bex and Renooij [5] previously noted that, for deduction, thepresence of a proposition opposing an inference step from q1 , . . . , qn to q should
decrease the probability that q is true. We propose to take a similar approach for
exceptions to causal generalisations used in performing inference. For deduction
with a generalisation q1 , . . . , qn → q in Gc in presence of an exception p, we
propose to constrain the CPT for Var(q) such that Pr(q | p, q1 , . . . , qn ) < Pr(q |¬p, q1 , . . . , qn ), as captured by step 6b of our approach. For abduction witha generalisation q1 , . . . , qn → q in Gc , the probability that qi is true given q
should decrease in the presence of an exception p for i = 1, . . . , n. Accordingly,
we propose to constrain the probabilities of the BN such that Pr(qi | p, q) <Pr(qi | ¬p, q), i = 1, . . . , n, as captured by step 6c of our approach. The latter
constraints cannot be directly imposed on the CPTs for nodes Var(p), Var(q),or Var(qi ), as nodes Var(qi ) and Var(p) are parents of node Var(q) by steps 2b
and 3b of our approach. We note that approaches have been proposed thatallow one to use this set of probability constraints in an elicitation procedurefor obtaining the required local probability distributions [14].
7. Properties of the Approach
In this section, we prove a number of formal properties of our approach. In
Sect. 7.1, we study conditions on IGs under which the fully automaticallyconstructed initial BN graph is guaranteed to be acyclic. In Sect. 7.2, we provethat, as intended, BN graphs constructed by our approach capture reasoning
patterns similar to those that can be read from an IG given the evidence. In
Sect. 7.3, we look into the size of the CPTs and complexity of probabilistic
inference in BN graphs constructed by our approach. Finally, in Sect. 7.4,
we look into mapping properties of our approach; specifically, we investigate
conditions under which the same BN graph is constructed from different IGs
by our approach, and discuss ways by which a distinction can be made in the(conditional) probabilities of the BN under construction.
7.1. Constructing Acyclic Graphs

1020

1025

1030

In this section, we study conditions under which the initial graph constructedby steps 1 − 3 of our approach is guaranteed to be a DAG. Hence, under these
conditions the (manual) verification step of whether the obtained graph contains
cycles (part of step 4 of our approach) can be skipped.
Conditions a) and b) of Proposition 1 concern the existence of exception
arcs in IGs. Specifically, cycles are possibly introduced within weakly connectedcomponents of the BN graph under construction in step 3 of our approach in case
exception arcs exist within weakly connected components of IGs (condition a).
Furthermore, cycles are also possibly introduced in the BN graph from a node V1
in one weakly connected component via a node V2 in another weakly connectedcomponent in this step in case exception arcs exist between propositions inseparate weakly connected components of IGs (condition b). Examples of IGs
violating these conditions are provided after the formal result.

29

Proposition 1. Consider IG GI = (P, AI ), and let G∗I = (P, A∗I ) be thepossibly disconnected sub-graph of GI with A∗I = AI \ Exc. Let C = {C =(Pc , AcI ) | Pc ⊆ P, AcI ⊆ A∗I , C is a weakly connected component of G∗I } be theset of IG components. Assume that the following conditions are satisfied:
1035

1040

1045

1050

1055

1060

1065

a) For any IG component C ∈ C, there does not exist an exc : p
g in Exc
with p ∈ Pc , g ∈ AcI .
b) For every pair of IG components C1 , C2 ∈ C, there does not exist both an
exc1 : p1
g1 in Exc with p1 ∈ Pc1 , g1 ∈ AcI2 and an exc2 : p2
g2 in Exc
with p2 ∈ Pc2 , g2 ∈ AcI1 .
Let GB = (V, AB ) be the graph constructed from GI according to steps 1 − 3 ofour approach. Then GB is a DAG.
Proof. By setting arcs in AB per step 2 of our approach, no cycles are introduced.
Specifically, our non-repetitiveness and consistency assumptions (see Sect. 4.1)
jointly assume that for every p ∈ P there does not exist a generalisation chain[g1 , . . . , gm ] with p ∈ Tails(g1 ) such that either Head(gm ) = p or Head(gm ) =−p. Therefore, no chain of arcs exists in AB from a node P to itself. The only
other case in which cycles are possibly introduced in GB is when a causal cycle
exists in GI , which is also prohibited by assumption (see Sect. 4.1).
We now prove that if C ∈ C is an IG component of GI , then the BN segment C 0 obtained from C after step 2 is a weakly connected component of thethus far constructed BN graph GB . Let C ∈ C be an IG component of GI .
Then propositions within C are interconnected by arcs in G and N but are notconnected to other propositions in the supergraph GI ; therefore, corresponding
nodes in BN segment C 0 are interconnected but not connected to other nodes
in supergraph GB . This is the case as per step 2, AB only includes arcs between
the variables corresponding to Tails(g) and Head(g) for every g ∈ G; no arcs
are introduced corresponding to n ∈ N. We then call C 0 the weakly connectedcomponent corresponding to IG component C. In step 3 of our approach, additional arcs are included in AB for every exc ∈ Exc. We now prove that nocycles are introduced within the weakly connected components of GB or from anode V1 in one weakly connected component to itself via a node V2 in anotherweakly connected component of GB in step 3. Under condition a), no cycles
are introduced within a weakly connected component C 0 of GB in this step.
Specifically, C 0 contains no cycles after step 2 and no cycles are introduced in
C 0 in step 3 as no exception arc is directed from a p ∈ Pc to a g ∈ AcI in corresponding IG-component C. Furthermore, for every pair of IG components C1
and C2 of GI with corresponding weakly connected components C10 and C20 of
GB , no cycles are introduced from a node V1 ∈ C10 to itself via a node V2 ∈ C20
under condition b). The resulting BN graph is therefore acyclic.


1070

Figures 14a, 14c and 14e depict examples of IGs that do not satisfy condition a)of Proposition 1 and hence result in cyclic graphs. In general, an IG violating
only condition a) either contains:(1a) A generalisation chain [g1 , . . . , gm ], g1 , . . . , gm ∈ Gc and an exception arc
30Figure 14: Examples of IGs (a, c, e, g) for which a cyclic graph is constructed by steps 1 − 3of our approach (b, d, f, h).

exc : Head(gj )gi for 1 ≤ i < j ≤ m (see Figs. 14a and 14c), or;(1b) A generalisation chain [g1 , . . . , gm ], g1 , . . . , gm ∈ Ge and an exception arc
exc : Head(gi )gj for 1 ≤ i < j ≤ m, or;(2) Propositions r, ¬r with n : r ! ¬r in N, where ¬r provides an exception
to a generalisation gi in a generalisation chain [g1 , . . . , gm ] with either:
1080(2a) Head(gm ) = r and g1 , . . . , gm ∈ Gc (see Fig. 14e), or;(2b) r ∈ Tails(g1 ) and g1 , . . . , gm ∈ Ge .

1075

1085

1090

1095

1100

For 1a), Head(gj ) poses an exception to a generalisation that was used in iteratively inferring Head(gj ) in case solely deductive inferences are performed withthe generalisations in the chain, as illustrated in Fig. 14a. However, in caseabductive inferences are performed with generalisations in the chain, it may not
be the case that Head(gj ) poses an exception to a generalisation that was usedin iteratively inferring Head(gj ), as illustrated in Fig. 14c. For 1b) Head(gi )poses an exception to a generalisation that is used to iteratively deductively
infer another proposition from Head(gi ), as only deduction can be performed
with evidential generalisations. For (2), the question remains whether realistic
examples of IGs including such conflict relations can be constructed; an abstract
example is provided in Fig. 14e. Condition a) of Proposition 1 thus mostly posesa technical constraint to ensure acyclic graphs are constructed by our approach.
IGs violating condition b) may appear more frequently; an example is provided in Fig. 14g. In the validation step that follows the initial constructionof BN graphs corresponding to IGs violating conditions a) and b), arcs can bereversed or removed to make these graphs acyclic. The choice of arc to reverseor remove will depend on its effect on active chains, including those between
nodes not directly incident on the arc. We note that this type of (manual) verification is standard in BN construction, especially in data-poor domains (see31Sect. 5.3). While the domain knowledge expressed in the original IG has been
exploited to construct an initial BN graph, additional domain knowledge mayneed to be elicited to obtain a valid graph.
7.2. Capturing Induced Reasoning Patterns Expressed by IGs as Active Chains

1125

In this section, we study whether BN graphs constructed by our approach capture reasoning patterns similar to those that can be read from the original IG
given the evidence. As motivated throughout this paper, generalisation arcs only
capture knowledge about the world in conditional form; only when considering
the available evidence Ep in the IG can directionality of inference be read fromthe graph. Specifically, in Definitions 9 and 10 conditions are specified underwhich (a set) of proposition(s) are deductively respectively abductively inferredfrom another (set of) proposition(s) given Ep . The following notion of an inference chain describes a sequence of propositions that are iteratively inferredfrom each other given Ep . For those familiar with argumentation, we note thatinference chains are comparable to arguments as defined in ASPIC+ [30]. A
key distinction is that we define inference chains and not inference trees (which
would more closely resemble arguments), as our current focus lies on defining
a concept that is more closely related to the concept of active chains for BNs.
Furthermore, the notion of attack is not required for our current purposes. In
previous work [42], we investigated the relations between argumentation andinference as it can be performed with our IG-formalism; more specifically, it isshown that an Argumentation Framework (AF) as in Dung [15] can straightforwardly be generated from an IG by considering the available evidence. For
details, the reader is referred to [42].
First, we define the concept of a chain for IGs.

1130

Definition 21 (Chain in an IG). Let GI = (P, AI ) be an IG, and let Ep ⊆ P
be an evidence set. Let {p1 , . . . , pn } ⊆ P and let G0 = {g1 , . . . , gn−1 } ⊆ G.
Then (p1 , g1 , p2 , g2 , . . . , pn−1 , gn−1 , pn ) is a chain in GI iff for all 1 < i ≤ n iteither holds that Head(gi−1 ) = pi , pi−1 ∈ Tails(gi−1 ) or Head(gi−1 ) = pi−1 ,pi ∈ Tails(gi−1 ).

1105

1110

1115

1120

We now define when a chain in an IG is an inference chain.

1135

1140

Definition 22 (Inference chain). Let GI = (P, AI ) be an IG, and let Ep ⊆ P
be an evidence set. Let G0 = {g1 , . . . , gn−1 } ⊆ G, and let {p1 , . . . , pn } ⊆ P suchthat @i, j ∈ {1, . . . , n} with pi = −pj , and such that (p1 , g1 , p2 , g2 , . . . , pn−1 , gn−1 ,pn ) is a chain in GI . Let p1 ∈ Ep or let p1 be deductively or abductively inferredusing a generalisation g ∈ G \ G0 given Ep (see Definitions 9 and 10). Then
chain (p1 , g1 , p2 , g2 , . . . , pn−1 , gn−1 , pn ) is an inference chain in GI given Ep iff
for all 1 < i ≤ n it holds that:
1. pi is deductively inferred using generalisation gi−1 ∈ G0 given Ep (see Definition 9), where Head(gi−1 ) = pi , pi−1 ∈ Tails(gi−1 ), or;
2. pi is abductively inferred from pi−1 using generalisation gi−1 ∈ G0 given Ep(see Definition 10), where Head(gi−1 ) = pi−1 , pi ∈ Tails(gi−1 ).
32murder
g3 c
mot1
mot2
g2 e
e g4
tes1

tes2

Figure 15: The IG of Fig. 8b, where inference chains are also indicated by connecting arcs
with open arrowheads.

1145

1150

1155

1160

1165

1170

1175

We emphasise that an inference chain (p1 , g1 , p2 , g2 , . . . , pn−1 , gn−1 , pn ) does not
only describe that pi−1 was used in inferring pi for all 1 < i ≤ n; it also describesthat the inference chain needs to start in a proposition p1 that is either observed
or inferred, hence the conditions regarding p1 in Definition 22. We refer to theassumption that for inference chains (p1 , g1 , p2 , g2 , . . . , pn−1 , gn−1 , pn ) it holds
that all pi are distinct (enforced by assuming that {p1 , . . . , pn } ⊆ P) as our nonrepetitiveness assumption on inference chains. We refer to the assumption thatfor {p1 , . . . , pn } it holds that @i, j ∈ {1, . . . , n} with pi = −pj as our consistency
assumption on inference chains.
Compared to generalisation chains (see Definition 4), which are solely captured by the graphical structure of IGs, inference chains can only be read froman IG by considering the evidence Ep . In case an inference chain only describes
deductive inference steps, then our non-repetitiveness and consistency assumptions on inference chains coincide with our non-repetitiveness and consistency
assumptions on generalisation chains as described in Sect. 4.1; however, theseassumptions do not coincide in case an inference chain also describes abductive
inference steps.
The following example illustrates the concept ‘inference chain’ and how it
compares to the concept ‘generalisation chain’.
Example 22. In the IG of Fig. 15, (tes1 , g2 , mot1 , g3 , murder) is an inference
chain given Ep , as mot1 is deductively inferred from tes1 ∈ Ep using g2 , where
Head(g2 ) = mot1 and tes1 ∈ Tails(g2 ), and murder is deductively inferred frommot1 and mot2 using g3 , where Head(g3 ) = murder and mot1 ∈ Tails(g3 ). In
this IG, [g2 , g3 ] is also a generalisation chain (see Example 8). Note that thepresence of this inference chain does not imply that mot1 is by itself sufficient toinfer murder; instead, murder can only be deductively inferred using g3 in caseboth mot1 and mot2 are affirmed. The broader context in which the inference
step from mot1 to murder is performed using g3 is thus not directly apparent
from this inference chain; instead, the role of proposition mot2 becomes apparent
in considering other inference chains that can be read from this IG given Ep ,specifically inference chain (tes2 , g4 , mot2 , g3 , murder).
In the IG of Fig. 4, (police, g1 , murder, g3 , mot1 ) is an inference chain given
Ep : murder is deductively inferred from police ∈ Ep using generalisation g1 andmot1 is abductively inferred from murder using generalisation g3 . However,33[g1 , g3 ] is not a generalisation chain, as Head(g1 ) = murder ∈/ Tails(g3 ).

1180



To remain closely related to the concept of active chains for BNs, we assume
in Definition 22 that inference chains (p1 , g1 , p2 , g2 , . . . , pn−1 , gn−1 , pn ) do notneed to start in evidence in that it does not need to hold that p1 ∈ Ep , as longas p1 is deductively or abductively inferred using a g ∈ G \ G0 given Ep .
Example 23. In Fig. 15, (mot1 , g3 , murder) is an inference chain given Ep :murder is deductively inferred from mot1 and mot2 using g3 . However, mot1∈
/ Ep ; instead, mot1 is deductively inferred using g2 ∈ G \ {g3 } given Ep .


1185

1190

The following example illustrates that inference chains are generally not symmetrical, in contrast with active chains for BNs.
Example 24. In the IG of Fig. 15, (tes1 , g2 , mot1 , g3 , murder) is an inference
chain (see Example 22), but (murder, g3 , mot1 , g2 , tes1 ) is not an inference
chain as mot1 cannot be inferred from murder using g3 and tes1 cannot be
inferred from mot1 using g2 .
We prove the following properties of inference chains. Lemma 1 states that for
inference chains, only the first proposition in the chain can possibly be observed.

1195

Lemma 1. Let GI = (P, AI ) be an IG, and let Ep ⊆ P be an evidence set.
Let p1 , . . . , pn ∈ P, g1 , . . . , gn−1 ∈ G and let (p1 , g1 , p2 , g2 , . . . , pn−1 , gn−1 , pn )be an inference chain in GI given Ep . Then pi ∈/ Ep for i > 1.
Proof. Let i > 1. In case pi is deductively inferred from pi−1 using gi−1 , thenpi = Head(gi−1 ) ∈/ Ep per the restrictions of Definition 9. Similarly, in case pi
is abductively inferred from pi−1 using gi−1 , then pi ∈/ Ep , as pi ∈ Tails(gi−1 )and Tails(gi−1 ) ∩ Ep = ∅ per the restrictions of Definition 10.
1200

Lemma 2 states that an inference step between two consecutive propositions pi
and pi+1 in an inference chain can only be performed with a generalisation gi forwhich Head(gi ) = pi and pi+1 ∈ Tails(gi ) in case gi is a causal generalisation.

1205

1210

1215

Lemma 2. Let GI = (P, AI ) be an IG, and let Ep ⊆ P be an evidence set.
Let p1 , . . . , pn ∈ P, g1 , . . . , gn−1 ∈ G and let (p1 , g1 , p2 , g2 , . . . , pn−1 , gn−1 , pn )be an inference chain in GI given Ep . Let i ∈ {1, . . . , n − 1} and assume that
Head(gi ) = pi , pi+1 ∈ Tails(gi ). Then gi ∈ Gc .
Proof. Assume a generalisation gi with Head(gi ) = pi and pi+1 ∈ Tails(gi )is indicated in GI , then pi+1 cannot be inferred from pi in case gi ∈ Ge , asthis would be an instance of abductive inference while per the restrictions ofDefinition 10 abduction can only be performed using generalisation arcs in Gc .
In performing inference care should be taken that no cause for an effect isinferred if an alternative cause for this effect was already previously inferred(Pearl’s constraint, see Sect. 2.4). In the context of IGs, for g ∈ Gc , propositionsin Tails(g) express a cause for the common effect expressed by Head(g), and
34

1220

1225

for g ∈ Ge , Head(g) expresses the usual cause for propositions in Tails(g).
Hence, in defining how inferences can be read from IGs, restrictions are put in
Definitions 9 and 10 such that Pearl’s constraint is adhered to. We now formally
prove that the inference chains that can be read from an IG given an evidence
set Ep indeed never violate Pearl’s constraint.
First, we formally define Pearl’s constraint in the context of IGs.
Definition 23 (Pearl’s constraint). Let GI = (P, AI ) be an IG, and let Ep ⊆ P
be an evidence set. Let c1 , c2 ∈ P be alternative causes of e ∈ P, as indicated bygeneralisations g, g 0 ∈ G (see Definition 3). Then chain (c1 , g, e, g 0 , c2 ) is not
an inference chain in GI given Ep .
We now formally prove that Pearl’s constraint is indeed adhered to.

1230

1235

1240

1245

1250

1255

Proposition 2 (Adherence to Pearl’s constraint). Let GI = (P, AI ) be an
IG, and let Ep ⊆ P be an evidence set. Let c1 , c2 ∈ P be alternative causes ofe ∈ P, as indicated by generalisations g, g 0 ∈ G (see Definition 3). Then Pearl’s
constraint is adhered to.
Proof. We need to prove that chain (c1 , g, e, g 0 , c2 ) is not an inference chain in
GI given Ep . In performing the inference step from c1 to e, a generalisationg ∈ Ge , Head(g) = c1 , e ∈ Tails(g) could not have been used (case 1 ofDefinition 3) per Lemma 2. Thus, we only need to consider case 2 of Definition
3, which is a deductive inference step. First, consider case 2a of Definition 3.
Then by Definition 10 (condition 2), c2 cannot be inferred from e using g 0 . Next,
consider case 2b of Definition 3. Then by Definition 9 (condition 2), c2 cannot
be inferred from e using g 0 .

Example 25. In the IG of Fig. 5c, [g1 , g2 ] is a generalisation chain but(smoke machine, g1 , smoke, g2 , fire) is not an inference chain, as per Pearl’s
constraint fire cannot be deductively inferred from smoke using g2 .
An IG, by means of its inference chains, describes sequences of propositions
that can be iteratively inferred from each other given the available evidence. In
comparison, from a BN graph we can read the chains between nodes that are
active given the evidence and will be exploited to propagate the evidence upon
probabilistic inference. We now formally prove that all inference chains that canbe read from an IG given the evidence are captured in the BN graph by means ofactive chains given the available evidence for EV ⊆ V corresponding to Ep ⊆ P.
This result implies that, for every inference chain (p1 , g1 , p2 , g2 , . . . , pn−1 , gn−1 ,pn ) given Ep , nodes Var(p1 ) and Var(pn ) are not d-separated given the evidence
for EV .
Proposition 3. Let GI = (P, AI ) be an IG with evidence set Ep ⊆ P, and let
GB = (V, AB ) be the BN graph constructed from GI according to steps 1 − 3of our approach. Let (p1 , g1 , p2 , g2 , . . . , pn−1 , gn−1 , pn ) be any inference chainthat can be read from GI given Ep . Then there exists an active chain between
Var(p1 ) and Var(pn ) in GB given the evidence for EV .
35

1260

1265

1270

1275

1280

1285

1290

1295

1300

Proof. Following steps 1 − 2 of our approach, a sequence of nodes and arcs isformed between Var(p1 ) and Var(pn ) in GB , as for every gi , 1 ≤ i < n arcs
between Tails(gi ) and Head(gi ) are added to AB . By our non-repetitivenessand consistency assumptions on inference chains, this is a sequence of distinct
nodes and arcs and thus a chain in GB . We now prove that this chain in the BNgraph is active given EV , as all options to block a chain do not occur. First,
note that per Lemma 1 it holds that pi ∈/ Ep for i > 1; therefore, corresponding
nodes Var(pi ) in the BN graph are not instantiated and hence do not blockchains. Possibly only p1 ∈ Ep . However, in this case, the corresponding node
Var(p1 ) is an end-point of the chain which, therefore, does not block it. Hence,
chains between Var(p1 ) and Var(pn ) are never blocked by EV .
The only other option to block a chain occurs in case it includes an uninstantiated head-to-head node without instantiated descendants. Consider pi−1 , pi ,pi+1 for an arbitrary 1 < i < n, and let gi−1 and gi be the corresponding generalisations used in the inferences from pi−1 to pi and from pi to pi+1 , respectively.
We show that a head-to-head node Var(pi−1 ) → Var(pi ) ← Var(pi+1 ) is neverformed. Note that by steps 2a and 2b of our approach, a head-to-head node
Var(pi−1 ) → Var(pi ) ← Var(pi+1 ) is only formed in case:
1. gi−1 ∈ Ge , Head(gi−1 ) = pi−1 , pi ∈ Tails(gi−1 ), and either:1a) gi ∈ Ge , Head(gi ) = pi+1 , pi ∈ Tails(gi ), or;1b) gi ∈ Gc , Head(gi ) = pi , pi+1 ∈ Tails(gi ).
2. gi−1 ∈ Gc , Head(gi−1 ) = pi , pi−1 ∈ Tails(gi−1 ), and either:2a) gi ∈ Gc , Head(gi ) = pi , pi+1 ∈ Tails(gi ), or;2b) gi ∈ Ge , Head(gi ) = pi+1 , pi ∈ Tails(gi ).
However, in performing the inference steps from pi−1 to pi and from pi to pi+1
none of these combinations of generalisations could have been used, as provenin Proposition 2. Thus a head-to-head node Var(pi−1 ) → Var(pi ) ← Var(pi+1 )is never formed, and chains between Var(p1 ) and Var(pn ) are never blocked.
Finally, in step 3 AB is extended for exception arcs. This step does notchange the chains formed between Var(p1 ) and Var(pn ) in step 2, which therefore remain active given EV .

The implication in the other direction of Proposition 3 does not generally hold.
Specifically, it does not generally hold that for every induced active chain ina BN graph constructed from an IG GI , there exists a corresponding induced
inference chain in GI . For instance, since the notion of an active chain isa symmetrical concept, a BN graph will also capture reasoning patterns in
the direction opposite of the inference chains that can be read from an IG.
As inference chains are generally not symmetrical (see Example 24), reasoning
patterns may appear in the BN graph that do not appear in the original IG.
7.3. Size and Complexity of Constructed BNs
The following properties concern the size and complexity of the resulting BN
model. Proposition 4 gives an upper-bound on the total number of nodes andarcs introduced in a BN graph constructed from an IG by our approach.
36

1305

Proposition 4. Let GI = (P, AI ) be an IG, and let GB = (V, AB ) be the BNgraph constructed from GI according to steps 1 − 3 of our approach. Let Exceand Excc be disjoint subsets of Exc consisting of exceptions to generalisationcarcs in Ge andP G , respectively. cThen |V|
P= |P| − |{p | p ∈ P and ¬p ∈ P}|
and |AB | ≤|Tails(g)| + |Exc | +|Tails(g)|.

g∈G

1310

1315

1320

1325

1330

p

g in Exce

Proof. By step 1 of our approach, both p and its negation are mapped to thesame node Var(p) = Var(¬p) ∈ V. Therefore, the exact number of nodes introduced in this step is |P \ {p | p ∈ P and −p ∈ P}|. In step 2, at most |Tails(g)|arcs are added to AB for every g ∈ G. For every exc ∈ Excc , one additionalarc is added to AB in step 3b. For every exc : p
g in Exce , at most |Tails(g)|arcs are added to AB in step 3a.
As a corollary, note that the complexity of constructing a BN graph from an IG
using our approach is linear in the number of proposition nodes, generalisationarcs and exceptions arcs in the IG, as nodes in the BN graph are directly added
according to the IG’s proposition nodes and arcs in the BN graph are directly
added according to the IG’s generalisation arcs and exception arcs.
Proposition 5 gives an upper-bound on the number of parents introducedby our approach for each node Var(p) in V, which bounds both the size of the
CPTs and the complexity of probabilistic inference in the BN [11, pp. 141–142]. Informally, this bound captures the number of generalisation arcs andexception arcs that involve either proposition p or ¬p. The terminology used in
Proposition 5 is illustrated in Fig. 16.
Proposition 5. Let GI = (P, AI ) be an IG, and let GB = (V, AB ) be the BNgraph constructed from GI according to steps 1 − 3 of our approach. For everyp ∈ P, let Parp = {pi | pi ∈ Tails(g), g ∈ Gc , Head(g) ∈ {p, ¬p}}. Let Gep be asubset of Ge , where g ∈ Gep iff p ∈ Tails(g). Let Excp ⊆ Exc be the subset of
exception arcs directed to a g ∈ Gep or a g ∈ Ge¬p . Similarly, let Exc0p ⊆ Exc be
the subset of exception arcs directed to a g ∈ Gc for which Head(g) ∈ {p, ¬p}.
Then an upper-bound for the number of parents of Var(p) is:|Parp | + |Excp | + |Exc0p | + |Gep | + |Ge¬p |

Gcpe

e

...

e

Ge¬p

Excp

e ...

p
c

...

e

¬p
c

Exc'p

Parp

c

...

c

Parp

Figure 16: Illustration of the terminology used in Proposition 5.

37

1335

1340

Proof. For every g ∈ Gc with Head(g) ∈ {p, ¬p}, Var(p) has at most |Tails(g)|parents by step 2b of our approach; hence the term |Parp |. By steps 3a and
3b, AB includes a single arc directed towards Var(p) for every exception exc in
Excp or in Exc0p , respectively; hence the terms |Excp | and |Exc0p |. For everyg ∈ Ge with p or ¬p in Tails(g), a single arc directed towards Var(p) is includedin AB by step 2a of our approach; hence the terms |Gep | and |Ge¬p |.

Note that, in case Gep = Ge¬p = ∅, it follows that Excp = ∅; hence, terms |Gep |,|Ge¬p | and |Excp | are equal to zero in this case. Similarly, Parp may be empty,
in which case Exc0p = ∅ and terms |Parp | and |Exc0p | are equal to zero.
7.4. Mapping Properties and Probabilistic Constraints

1345

1350

1355

1360

Finally, we investigate conditions under which the same BN graph is constructedfrom different IGs by our approach, and discuss ways by which a distinction canbe made between these different cases in the (conditional) probabilities of the
BN. First, we prove in Proposition 6 that for every finite BN graph GB , there
exists a finite IG such that this IG is mapped to GB by our approach.
Proposition 6. Let IG be the space of finite IGs and let BN be the space offinite BN graphs. Let F : IG → BN be the function defined by steps 1 − 3 ofour approach. Then F is a surjection.
Proof. Let GB = (V, AB ) be a BN graph in BN. Then we need to find at leastone IG GI = (P, AI ) ∈ IG s.t. F (GI ) = GB . Define GI as follows. For every
node P ∈ V, include proposition p ∈ P. For every arc P1 →P2 ∈ AB , include
generalisation arc g : p1 → p2 in Gc . Then F (GI ) = GB by steps 1 and 2b. 
However, F is not an injection. Figures 17a-d depict examples of IGs for which
the same BN graph, namely the graph depicted in Fig. 17e, is constructed by
F . Possible differences between these IGs can be captured in the (conditional)
probabilities of the BN under construction. In Fig. 17a, a negation arc isdrawn between r and ¬r. A possible probabilistic interpretation is that this IG
r

¬r

r
c

c

c

q
(b)

(a)

r

r
c
p

c

p

q

p

q

R

p

c

P

q

(c)

(d)

Q
(e)

Figure 17: Examples of IGs (a-d) for which the same BN graph (e) is constructed by ourapproach.

38

1365

1370

1375

informs us on probabilities Pr(r | p, q) and Pr(¬r | p, q), where a preference forr over ¬r defines an ordering on these two probabilities. In our IG-formalism,
we opted not to account for preferences, as these are typically not indicatedusing reasoning tools; hence, possible probabilistic constraints resulting fromsuch preferences are not further discussed.
In Fig. 17b, p and q can each be considered sufficient for deductively inferring r, while in Fig. 17c both p and q are needed. A possible probabilistic
interpretation of the IG in Fig. 17b is that it only informs us on probabilities
Pr(r | p) and Pr(r | q) and not on Pr(r | p, q), while the reverse holds for the IG
of Fig. 17c. Figure 17c is distinguished from Fig. 17a, as Fig. 17c only informs
us on Pr(r | p, q) while Fig. 17a also informs us on Pr(r | q) and Pr(¬r | p).
For exception arcs, specific probabilistic constraints are derived, as captured
by step 6 of our approach. Specifically, in the example of Fig. 17d, constraint
Pr(r | p, q) < Pr(r | ¬p, q) is derived. Related research on the relations between
probability and inference is discussed in Sect. 9.3.
8. Case Study: The Sacco and Vanzetti Case

1380

1385

1390

1395

1400

In this section, we apply our BN graph construction approach to parts of an
actual legal case, namely the well-known Sacco and Vanzetti case. The caseconcerns Sacco and Vanzetti, who were convicted for shooting and killing payroll guard Berardelli during a robbery in South Braintree, Massachusetts on 15
April 1920; a detailed description of the case is provided by Kadane and Schum[22]. Kadane and Schum performed a probabilistic analysis of this case by first
constructing Wigmore charts [43] (described below) of aspects of the case andthen manually constructed corresponding BNs by assessing the modelled independence relation and assessing the necessary (conditional) probabilities. In thissection, we illustrate and perform a first validation of our approach by formalising one of Kadane and Schum’s Wigmore charts (chart 25, [22, pp. 330–331])
as an IG, where we compare the obtained BN graph to their BN graph. The
currently presented case study is an extension of the case study that appearedin our previous work [39] in which parts of the case were interpreted as a preliminary version of an IG in which the roles of generalisation and inference are notseparated. In the current paper, we describe our IG modelling choices in moredetail and we provide a more detailed comparison of the BN graph constructedby our approach to that of [22].
This section is structured as follows. In Sect. 8.1 Kadane and Schum’s
Wigmore chart concerning Sacco’s consciousness of guilt is presented, where apossible formalisation of this Wigmore chart as an IG is provided in Sect. 8.2.
In Sect. 8.3 we then apply our BN graph construction approach to this IG andcompare the obtained BN graph to that of Kadane and Schum. In Sect. 8.4 wethen conclude the case study.
8.1. Wigmore Chart Concerning Sacco’s Consciousness of Guilt
According to Kadane and Schum, the ultimate claim under consideration in the
Sacco and Vanzetti case is Π3 , which states that ‘It was Sacco who, with the
39

PROSECUTION 149. Following his arrest, Sacco attempted to put

his hand under his overcoat.
Connolly’s testimony to 149.
Spear’s testimony to 149.
Sacco intended to draw his concealed weapon.
Sacco intended to use his weapon on
the arresting officers.
154. Sacco intended to escape from his arrest.
155. Sacco was conscious of having committeda criminal act.

155

150.
151.
152.
153.

154

153
462

152

463

149

DEFENCE 461. Sacco’s testimony to denying 149.

465
464

466

462. Sacco carried a weapon because heintended to shoot rabbits with it.
463. Sacco’s testimony to 462.
464. Sacco’s wife’s testimony to 462.
465. Sacco carried a weapon because of his duties
as a night watchman.
466. Sacco’s testimony to 465.
467. Sacco was not a night watchman.
468. Sacco’s admission on cross-examination.

467

468
150

151

461

Figure 18: Wigmore chart concerning Sacco’s consciousness of guilt, along with the corresponding key list, adapted from Kadane and Schum [22, pp. 330–331].

1405

1410

1415

1420

1425

1430

assistence of Vanzetti, intentionally fired shots that took the life of Berardelliduring the robbery and shooting that took place in South Brain tree.’ In theprosecution’s case against Sacco and Vanzetti, their alleged consciousness of
guilt in the South Braintree crime played an important role. However, as notedby Kadane and Schum the inferences made based on the available evidence forthis part of the case are not particularly strong; a significant part of Kadane
and Schum’s analysis is, therefore, devoted to this part of the case. During theirarrest, Sacco and Vanzetti were armed. According to the two arresting officers,
Connolly and Spear, Sacco and Vanzetti made suspicious hand movements, fromwhich the prosecution concluded that they intended to draw their concealed
weapons in order to escape their arrest. This suggests that they were consciousof having committed a criminal act. In the remainder of this section, we only
consider this part of the case.
In Fig. 18, a modernised Wigmore chart concerning Sacco’s consciousness of
guilt is depicted, adapted from Kadane and Schum [22, pp. 330–331]. Wigmore
charts are diagrams familiar to many legal experts in which symbols indicating
hypotheses and claims are joined by lines representing relations between thesehypotheses and claims. Wigmore charts were introduced by John Henry Wigmore [43] and were further developed and studied from an academic perspectiveby the so-called ‘New Evidence Theorists’ including Anderson, Schum and Twining (see [22, pp. 70–71]), who provided a modernised, more user-friendly version
of Wigmore’s charting method. Wigmore introduced his method as an aid in
structuring a mass of evidence in a legal case in detailed way. An important
aspect of his method is that it not only used for expressing supporting reasons
but also for revealing possible sources of doubt. Wigmore’s charts can be considered a precursor of diagrams in argument diagramming tools [26], as well as
a forerunner of instantiations of formal argumentation systems [1].
Compared to Kadane and Schum’s original chart, we consider a subset of

40

1435

1440

1445

1450

1455

1460

the mapped claims; in particular, claims 469, 470, 155a, 156 and Π3 , additional
claims regarding Sacco’s political beliefs (claims 471 − 480 in the original chart),and claims that were provided post-trial by historians are not considered. On
the right-hand side of Fig. 18 the corresponding key list is depicted, whichindicates for every number in the chart to which claim it corresponds. As notedby Kadane and Schum [22, p. 88], vertical arcs between nodes in their version of
Wigmore’s charts indicate inferences between corresponding claims, where thegeneralisations used in performing these inferences are not explicitly recorded in
the chart. Instead, in their analysis of the case some of the used generalisations
are indicated in the text (see e.g. [22, pp. 97–98]). For instance, generalisations
used in the inferences from the provided testimonies are of the general form ‘Ifa person testifying under oath tells us that event E occurred, then this event(probably, usually, often, etc,) did occur.’ [22, p. 88]. As noted by Kadane
and Schum [22, pp. 74–76], in constructing their charts abduction is in someinstances performed to generate interim hypotheses between the evidence andthe ultimate claim Π3 . However, Kadane and Schum do not explicitly indicate
which inferences in their charts are abductive and which are deductive.
In their version of Wigmore charts, Kadane and Schum make a distinction
between directly relevant and ancillary claims4 , where the role of an ancillaryclaim is to show why a generalisation holds or fails in a particular situation[22, p. 53]. Directly relevant and ancillary claims provided by the defence arerepresented as diamonds and triangles, respectively; for the prosecution, these
are represented as circles and squares, respectively. Note that in the Wigmore
chart of Fig. 18, all claims provided by the prosecution are directly relevant.
All nodes in Kadane and Schum’s charts indicate either directly relevant or
ancillary claims and nodes corresponding to the evidence are shaded. An arc
directed from a node corresponding to an ancillary claim to an arc between two
or more claims indicates that this ancillary claim either supports or weakens theapplicability of the generalisation in the inference at hand [22, p. 87]. Finally,horizontal lines in the Wigmore chart indicate that information needs to be
combined to draw a conclusion.
8.2. Formalising the Wigmore Chart as an IG

1465

1470

We now provide a possible formalisation of Kadane and Schum’s Wigmore chartof Fig. 18 as an IG. In Fig. 19, an IG is depicted for a possible interpretationof this Wigmore chart. For every claim p in the Wigmore chart, a proposition
node p is included in P. In establishing which generalisations could have beenused in performing the inferences indicated in the chart, we take the following
general approach. In case generalisations are explicitly indicated by Kadane
and Schum in the text, then these generalisations are used; otherwise, we firstestablish whether or not there is a causal relation between the nodes in the chart,
4 Kadane and Schum [22] use the terms ‘directly relevant evidence’ and ‘ancillary evidence’.
To avoid confusion with the manner in which the term ‘evidence’ is used in this paper (i.e.
that what has been established with certainty), we instead use the term ‘claim’.

41

PROSECUTION 149. Following his arrest, Sacco attempted to put

155

g6

his hand under his overcoat.
Connolly’s testimony to 149.
Spear’s testimony to 149.
Sacco intended to draw his concealed weapon.
Sacco intended to use his weapon on
the arresting officers.
154. Sacco intended to escape from his arrest.
155. Sacco was conscious of having committeda criminal act.

c

150.
151.
152.
153.

154

g5 c
153
465

g4 e

462

467

g8 e

e

e g9

152

466

g3 c

468

g1
150

DEFENCE 461. Sacco’s testimony to denying 149.

g7
464

463

149

¬149

e

e g2

151

461

462. Sacco carried a weapon because heintended to shoot rabbits with it.
463. Sacco’s testimony to 462.
464. Sacco’s wife’s testimony to 462.
465. Sacco carried a weapon because of his duties
as a night watchman.
466. Sacco’s testimony to 465.
467. Sacco was not a night watchman.
468. Sacco’s admission on cross-examination.

Figure 19: An IG corresponding to a possible interpretation of the Wigmore chart of Fig. 18,
along with the corresponding key list.

1475

1480

1485

1490

1495

1500

and if so, what the direction of causality is. To aid in this process, we determine
whether sequences of described events can be interpreted as instances of so-calledstory schemes [2], which capture stereotypical patterns of causal reasoning. In
case p usually/normally/typically causes q, then we establish whether p can beconsidered the usual cause for q. If this is the case, then evidential generalisationq → p is included in Ge to explicitly capture in the IG that p is considered theusual cause of q; otherwise, causal generalisation p → q is included in Gc (seealso Sect. 2.3).
As noted by Kadane and Schum [22, p. 88], the generalisations used in theinferences from the provided testimonies are evidential (see Sect. 8.1). As
propositions 150, 151, 463, 464, 466 and 468 denote testimonies, the IG includes
generalisation arcs g1 : {150, 151} → 149, g7 : {463, 464} → 462, g8 : 466 → 465
and g9 : 468 → 467 in Ge . Here, testimonies 150, 151 and 463, 464 are combinedin the antecedents of generalisations g1 and g7 , respectively, as these sets ofpropositions concern testimonies to the same claim.
The manner in which claims and links conflict is not precisely specified in
Kadane and Schum’s Wigmore charts. As we wish to formalise the Wigmore
chart of Fig. 18 as an IG, we consider how possible conflicts between claims
proposed by the prosecution and defence can be interpreted in terms of theconflict relations defined in Sect. 4.1. As 461 concerns Sacco’s testimony todenying 149, proposition ¬149 is included in P, generalisation arc g2 : 461 →¬149 is included in Ge , and negation arc n1 : 149 ! ¬149 is included in N.
Kadane and Schum do not indicate which (types of) generalisations wereused in performing the inferences between propositions 149 and 155. We notethat the inferences between 149 and 155 fit a so-called episode scheme for intentional actions [2, p. 64], a story scheme in which someone’s psychological state
causes them to form certain goals, which in turn lead to actions that have consequences. In this case, Sacco intended to escape from his arrest (154; goal) as
he was conscious of having committed a criminal act (155; psychological state);
therefore, we consider 155 to typically cause 154. Sacco’s intention to use his
42

1505

1510

1515

1520

1525

1530

1535

1540

1545

weapon (153) can then be considered a sub-goal of 154 and his intention to
draw his concealed weapon (152) a further sub-goal of 153. Sacco’s intention
to draw his weapon (152) caused Sacco to attempt to put his hand under his
overcoat (149; action); more specifically, we consider 152 to typically cause 149.
Finally, we consider 153 to be the usual cause for 152, as the usual cause forwanting to draw a weapon is wanting to use this weapon; we therefore include
g4 : 152 → 153 in Ge . Generalisation arcs g3 : 152 → 149, g5 : 154 → 153 andg6 : 155 → 154 are then included in Gc , as we do not consider their antecedents
to express the usual cause for their consequents. Alternatively, it may be argued that some (or all) of these relations are evidential. Below, we show thatsimilar inferences can be performed with the constructed IG and that the same
BN graph are constructed from the IG regardless of whether these relations areinterpreted as causal or evidential.
In Kadane and Schum’s Wigmore chart, it is indicated that 467 is an ancillaryclaim that weakens (or supports) the applicability of generalisation g8 : 466 →
465 in the inference from 466 to 465. In this particular instance, 467 can beinterpreted as an exception to generalisation g8 , as the claim that Sacco was
not a night watchman indicates that Sacco’s veracity in providing his testimony
about the reason for carrying a weapon is questionable. Therefore, we include
exc1 : 467
g8 in Exc.
Finally, the conflicts between the defence’s claims 462 and 465 and the prosecution’s claims 152 and 153 are considered. A possible interpretation is that462 and 465 indicate exceptions to generalisation g4 : 152 → 153 in Ge . Specifically, 462 and 465 can be considered competing alternative explanations for 152:
as Sacco carried his weapon for an innocent reason (462 or 465), this caused
him to draw his weapon (152) with the intention of surrendering it. In Fig.
19, these exceptions are indicated by curved hyperarcs exc2 : 462
g4 andexc3 : 465
g4 in Exc.
In the Wigmore chart of Fig. 18, the evidence consists of the testimonies;
hence, Ep = {150, 151, 461, 463, 464, 466, 468}. Given Ep , the inferences thatcan be read from the IG of Fig. 19 coincide with the inferences indicated in
the Wigmore chart. Specifically, given Ep , propositions 149, ¬149, 462, 465
and 467 are deductively inferred from 150 and 151, 461, 463 and 464, 466, and
468 using generalisations g1 , g2 , g7 , g8 and g9 , respectively. Proposition 152
is then abductively inferred from 149 using g3 , as 149 is deductively inferred.
Propositions 153, 154 and 155 are then iteratively inferred using generalisations
g4 , g5 and g6 , respectively.
As mentioned earlier, instead of including causal generalisations g3 : 152 →
149, g5 : 154 → 153 and g6 : 155 → 154, an alternative interpretation is thatthe antecedents of these generalisations express the usual cause for their consequents; accordingly, evidential generalisations g30 : 149 → 152, g50 : 153 → 154
and g60 : 154 → 155 may instead be included. Similar inferences can then be
performed with the constructed IG given Ep ; specifically, propositions 152, 153,
154 and 155 are then iteratively deductively inferred given Ep using g30 , g4 , g50
and g60 instead of that some of these inferences are abductive.

43

8.3. Constructing a BN Graph from the IG
1550

1555

1560

1565

1570

1575

1580

1585

1590

We now apply our BN graph construction approach to the IG of Fig. 19 andcompare the obtained graph to that of Kadane and Schum.
8.3.1. Applying the BN Graph Construction Approach
By applying our BN graph construction approach to the IG of Fig. 19, theBN graph depicted in Fig. 20b is obtained. By step 1 of our approach, every
proposition and its negation are captured as two mutually exclusive values ofthe same node. Arcs in the BN graph corresponding to generalisation arcs inGe ∪ Gc are then directed according to step 2. Additional arcs are then added
to AB for every exception arc in Exc by step 3 of our approach. Specifically,exc1 : 467
g8 , exc2 : 462
g4 and exc3 : 465
g4 are specified in the IG,
where g8 , g4 ∈ Ge ; therefore, additional arcs 467 → 466, 465 → 152 and 462 →152 are included in AB by step 3a.
Note that in case causal generalisations g3 , g5 and/or g6 are replaced byevidential generalisations g30 , g50 and/or g60 , the same BN graph is obtained by
our approach. More specifically, by step 2b arc Var(p) → Var(q) is included forevery causal generalisation g : p → q, where the same arc is included in AB bystep 2a of our approach for every evidential generalisation g : q → p.
8.3.2. Comparison to Kadane and Schum’s BN Graph
The structure of the obtained graph is largely identical to that of the BN graphthat Kadane and Schum manually constructed for this part of the case, depicted in Fig. 20c; the differences and similarities between the two BN graphs
are now discussed. First, note that Kadane and Schum aggregate nodes 463
and 464 into a single Boolean node K. Similarly, nodes 466, 467 and 468 areaggregated into Boolean node J; possible intercausal effects between 467 and465 can, therefore, not be explicitly captured in their BN. While aggregation
as performed by Kadane and Schum reduces the number of conditional probabilities to be assessed, we prefer to explicitly capture all elements of the IG
in the corresponding BN graph to prevent loss of information. The only casein which IG elements are aggregated by our approach is when two propositions
p and ¬p appear in the graph, which are then captured as two values of thesame node. We note that, by step 6a of our approach, constraints on the CPTsof the BN under construction are automatically obtained, which partially simplifies subsequent probability assessment. Specifically, a head-to-head node isformed in 466, which allows for directly capturing possible interactions between
465 and 467. By step 6a, constraint X− ({465, 467}, 466 = true) is derived on
the CPT for node 466. For instance, entries for this CPT can be chosen as follows: Pr(466 | 465, 467) = 0, Pr(466 | ¬465, ¬467) = 0.4, Pr(466 | 465, ¬467) =0.9, Pr(466 | ¬465, 467) = 0.2, as in this case 0 · 0.4 ≤ 0.9 · 0.2. Note that theconditioned event of conditional probability Pr(466 | 465, 467) cannot actuallyoccur in practice, as Sacco cannot both be and not be a night watchman at
the same time. Hence, the exact number to which this conditional probability
is set is irrelevant: we choose to set Pr(466 | 465, 467) = 0. In case Sacco was

44

155

g6

c

155

155

154

154

153

153

154

g5 c
153
465
467

g8 e

e g9

466

g4 e

462
e

152

g3 c

468

149

g1
150

g7

467

465

152

462

468

466

149

463

150

151

461

465

152

462

J

149

K

150

151

461

464

463

¬149

464

e g2

e

151

461

(b)

(a)

(c)

Figure 20: The IG of Fig. 19 (a); the corresponding BN graph constructed according to ourapproach (b); adaptation of the BN graph constructed by Kadane and Schum [22, p. 232] (c).

1595

1600

1605

1610

1615

1620

indeed a night watchman (467 is not true) but Sacco did not carry a weapon
because of this reason (465 is not true), then we find it plausible that Sacco waslying under oath in providing his testimony (Pr(466 | ¬465, ¬467) = 0.4); more
specifically, as he was indeed a night watchman, he can use this as an excuse
to claim that he carried his weapon because of this reason. In case Sacco was anight watchman (467 is not true) and Sacco actually carried a weapon becauseof his duties as a night watchman (465 is true), then we consider the event that
Sacco testifies to this claim (466) to be very likely (Pr(466 | 465, ¬467) = 0.9).
Finally, in case Sacco was not a night watchman (467 is true) and Sacco did notcarry his weapon because of his duties as a night watchman (465 is not true),then we set Pr(466 | ¬465, 467) = 0.2 to again take into account the probability
that Sacco may be lying under oath. We believe this probability to be lower
than Pr(466 | ¬465, ¬467), as we consider it less likely for Sacco to come up
with the explanation that he carried his weapon because of his duties as a nightwatchman if he was in fact not a night watchman.
In the BN graph of Fig. 20b, a head-to-head node is also formed in node152, which allows for directly capturing possible interactions between 462, 465
and 153. These interactions cannot be captured in the BN graph of Fig. 20c,as in this graph arcs 153 → 465 and 153 → 462 are included instead of arcs
465 → 152 and 462 → 152. By step 6a, constraints X− ({462, 153}, 152 = true),
X− ({465, 153}, 152 = true) and X− ({465, 462}, 152 = true) are derived on the
CPT for node 152 in our BN graph. Note that in the BN graph of Kadane andSchum, variables 462 and 465 are conditionally independent from 152 given 153;
therefore, in contrast with our BN under construction, for Kadane and Schum’s
BN it needs to hold that Pr(152 | 462, 465, 153) = Pr(152 | 153). As the entries
for the CPT for node 152 in our BN cannot be compared to that of Kadane andSchum, the assessment of the involved probabilities is not further discussed.
We note that for every active chain that exists between two nodes in the
BN graph of Fig. 20b given the evidence, there exists an active chain between
these nodes in the BN graph of Fig. 20c given the evidence and vice versa;

45

1625

1630

therefore, given EV , similar probabilistic inferences can be performed in both
BN graphs, besides the aforementioned differences. More specifically, as 152 has
an instantiated descendant in the BN graph of Fig. 20b, chains between 465
and 462 are active.
Finally, note that the BN constructed from the IG of Fig. 20a cannot bedirectly used for probabilistic inference. More specifically, the BN is partially
specified as only qualitative probabilistic constraints and no exact probabilities
are derived on the BN under construction. Moreover, the derived qualitative
probabilistic constraints are only a subset of those required for the specificationof a QPN [33] (see also Sect. 9.3). The derived qualitative probabilistic constraints may serve as input for a subsequent elicitation procedure for obtaining
a fully specified QPN or BN for (qualitative) probabilistic inference.
8.4. Concluding Remarks

1635

1640

1645

1650

In this section, we have performed a first validation of our BN graph construction
approach by means of a case study. We have provided a possible interpretationof Kadane and Schum’s Wigmore chart as an IG, which illustrates that the IGformalism is sufficiently expressive to model a complex case in a precise way. We
have then applied our approach to the constructed IG. Upon comparing the BNgraph obtained by applying our approach to the BN graph that Kadane andSchum manually constructed, we have concluded that the graphs are largely
identical and that similar probabilistic inferences can be performed for the caseat hand. As Kadane and Schum provided a thorough and extensive probabilistic
analysis of the case, these similarities are a positive result of our validation andoffer a first indication that BNs constructed from IGs by our approach are ofgood quality. Moreover, the differences obtained illustrate that our approach
may provide a more principled way of constructing BN graphs than the mannerin which Kadane and Schum constructed their BNs. In particular, Kadane andSchum in some cases aggregated multiple claims in the Wigmore chart into
single nodes in the BN graph, while by applying our approach all elements of
the IG are explicitly captured in the corresponding BN graph to prevent lossof information. Furthermore, in comparison to the BN graph of Kadane andSchum head-to-head nodes are formed in our BN graph, which allows for directly
capturing possible interactions between nodes in the graph.
9. Related Research

1655

In this section, related research on inference with causality information (Sect.
9.1), BN graph construction (Sect. 9.2), the relations between probability andinference (Sect. 9.3), and intermediary formalisms (Sect. 9.4) are discussed.
9.1. Inference with Causality Information

1660

In this paper, we have presented the graph-based IG-formalism for deductive
and abductive inference with causal and evidential information. As mentioned
earlier, the currently presented IG-formalism is a further specification of the
46

1665

1670

1675

1680

1685

1690

1695

1700

1705

IG-formalism that appeared in our previous work [42]. More specifically, in thecurrent paper we define a number of new concepts, namely negation arcs (Definition 6), competing alternative explanations (Definition 11) and (restrictionson) generalisation chains (Definitions 4 and 5 and p. 11), and we now explicitly
describe a number of concepts in the form of definitions and remarks, including
prediction (Remark 1), ambiguous inference (Remark 2) and alternative causes(Definition 3). Our IG-formalism extends on a preliminary formalism used in[39, 40], in which the roles of generalisation and inference are not separated;
therefore, this preliminary formalism does not provide a precise enough accountof reasoning with causal and evidential information.
Most related formalisms for inference with causal and evidential information are logic-based instead of graph-based [2, 4, 21, 29, 35]. Poole’s Theorist
framework [29] allows for both deductive and abductive inference, which is established using only causal defaults. Complications with reasoning using bothcausal and evidential defaults as identified by Pearl [27] are thus avoided. In the
hybrid theory proposed by Bex [2], deductive and abductive inference are usedin constructing evidential arguments and causal stories. Compared to our IGformalism, the hybrid theory does not allow for most types of mixed inference
and largely avoids the problems associated with mixed inference as identified by
Pearl [27]. Building on his hybrid theory, Bex proposed his integrated theoryof causal and evidential arguments [4]. In Bex’ integrated theory, the roles ofgeneralisation and inference are not separated; instead, causal and evidential
inference rules are defined and arguments are constructed by forward chaining such inference rules. Actual abductive inference is thus not performed byconstructing arguments.
As noted in Sect. 7.2, inference chains in IGs are comparable to arguments as
defined in ASPIC+ [30]. Besides the mentioned distinctions between these formalisms, our graph-based IG-formalism deviates from the logic-based ASPIC+
framework as we introduce a new type of conflict, namely conflict between competing alternative explanations, and impose constraints on the different typesof inferences that may be performed with the different types of generalisations.
Graph-based formalisms for reasoning with causality information have also
been proposed, notably Pearl’s causal diagrams [28]. Pearl provides a framework for causal inference in which diagrams are queried to determine if theassumptions available are sufficient for identifying causal effects. Compared to
our IG-formalism, the aim of this framework is different in that it serves to
identify causality instead of providing a way to reason with modelled causal
knowledge. Furthermore, causal diagrams require probabilistic quantification
to be queried, while IGs are qualitative.
9.2. BN Graph Construction
To facilitate BN graph construction, construction methods have been proposedin the literature. As noted in the introduction, work on the construction of
BNs from information represented in ontologies [17, 31] is related to our BN
construction approach based on IGs. In the approach of Fenz [17], an initial BNgraph is automatically constructed after a manual selection of relevant concepts
47

1710

1715

1720

1725

1730

1735

1740

1745

1750

and relations from an OWL ontology. Specifically, concepts are mapped to nodes
in the BN graph and the direction of the relation between two concepts is used
to direct arcs between corresponding nodes in the graph as a first heuristic.
However, properties regarding the represented independence relation are notinvestigated; instead, Fenz notes that the obtained BN graph needs to be verified
and refined manually by the BN modeller. Ramı́rez-Noriega and colleagues [31]proposed a similar approach in the domain of intelligent tutoring systems, where
the focus lies on obtaining the quantitative part of the BN.
In other related work, Bex and Renooij [5] identified constraints on BNs
given arguments, based on the inferences on which arguments are built and theexisting conflicts between arguments. These constraints suffice for constructing
an undirected skeleton of a BN graph. In their approach, ASPIC+ [30] is taken
as a starting point for BN graph construction; for reasons mentioned in Sect.
9.1, we wish to refrain from using ASPIC+ as an intermediary formalism. In
our previous work, we explored the possibility of BN construction from a graphbased intermediary formalism using a preliminary version of IGs in [39, 40]. As
mentioned in Sect. 9.1, this preliminary IG-formalism does not provide a precise
enough account of reasoning with causal and evidential information; hence, theBN construction approaches provided in these papers are also imprecise.
Throughout the literature, many (often domain-specific) BN fragments andmodules, also called idioms, have been proposed. In the legal domain, Fenton
and colleagues [16, Ch. 13] proposed BN fragments to model recurring patternsof legal reasoning, such as structures for corroboration. Laskey and Mahoney[25] proposed BN fragments in the domain of military situation assessment,
and studied how fragments can be combined to construct more complex networks. In contrast with these manual fragment-based approaches for BN graphconstruction, our approach allows for automatically constructing an initial BNgraph from an IG that satisfies a number of desirable properties, for instanceregarding the represented independence relation, where generalisations and conflicts can be incorporated and combined in an IG without having to conformto any predefined pattern or configuration. Arguably this allows our BN construction approach to be applied more flexibly in practice, a claim that shouldbe empirically evaluated in future work.
To facilitate incremental BN construction, Object-Oriented BNs (OOBNs)
were introduced by Koller and Pfeffer [24]. With OOBNs, it becomes possible
to incrementally construct a BN top-down, using fragments and modules suchas proposed throughout the literature to gradually construct a network. Unlike
our approach, OOBNs do not provide an automated way of constructing BNgraphs; instead, OOBNs allow experts to more quickly construct a BN manuallyby allowing recurrent patterns to be incorporated. The concept of reusable
network fragments was also the basis of Hypothesis Management Frameworks(HMFs) proposed by Van Gosliga and van de Voorde [19], which are generally
applicable and not intended for a specific domain. With HMFs, a modular
approach is taken, enabling the specification of details about a case without
losing perspective on the case as a whole.

48

1755

1760

1765

1770

1775

1780

1785

1790

1795

9.3. The Relations Between Probability and Inference
As discussed by Bex and Renooij [5], the exact probabilistic interpretation ofinference and evidence, and hence the various types of constraints on a BN, is acontentious issue. The interpretation of strict inferences is straightforward: theconsequent is necessarily true given the antecedents. However, with respect todefeasible inferences different ideas exist on how they should be modelled probabilistically. For instance, for a defeasible inference from p1 , . . . , pn to q it canbe assumed that Pr(q | p1 , . . . , pn ) > 0; however, this constraint is rather weak.
Another possible interpretation is that this probability should be greater than
0.5 in that the antecedents make it more likely than not that the consequent istrue. Yet another reading is that the probability of the consequent given the antecedents should be greater than the prior probability of the consequent, which
is a Bayesian interpretation explored by for instance Crupi and colleagues [10].
This interpretation is based around the notion of conditional independence: incase Pr(q | p1 , . . . , pn ) = Pr(q), q is conditionally independent from {p1 , . . . , pn },and learning that {p1 , . . . , pn } is the case will be uninformative to q. Therefore,
according to this interpretation it should hold that Pr(q | p1 , . . . , pn ) > Pr(q).
Another possible probabilistic interpretation is to view inferences that canbe read from an IG given the evidence as qualitative influences [13]. Specifically, variable P is said to have a positive qualitative influence on variable Q if
Pr(q | p) ≥ Pr(q | ¬p) and a negative qualitative influence if Pr(q | p) ≤ Pr(q |¬p). Interpreting all inferences between propositions p1 , . . . , pn and q that canbe read from an IG as positive qualitative influences and all inferences between
propositions p1 , . . . , pn and ¬q as negative qualitative influences, a fully specified
qualitative probabilistic network (QPN) may be constructed by our approach
which can be used for qualitative probabilistic inference [33]. Quantification of
QPNs can then be performed incrementally by specifying probability intervals
for CPTs for nodes in the graph as an intermediary step, resulting in so-calledsemi-qualitative probabilistic networks [33] that can also be used for probabilistic inference. Alternatively, a credal network [9] can be constructed [7].
The point of the above discussion is that there are many probabilistic interpretations of inference and evidence, and choosing exactly which ones to use
is not trivial. One way to deal with discussions involving probabilistic constraints is to allow one to reason about such constraints [23, 41]. Specifically,
the approaches proposed in [23, 41] allow domain experts to reason and argue
about BN modelling decisions, where computational argumentation [15] is used
to resolve disagreements as much as possible.
9.4. Intermediary Formalisms
Our IG-formalism serves as an intermediary formalism between analyses performed using informal reasoning tools and formal AI systems such as argumentation systems (see [42]) and BNs. Viewed this way, in the context of argumentation the IG-formalism is comparable to the Argument Interchange Format(AIF) [3], an argumentation ontology that serves as an intermediary formalism between analyses performed using argument diagramming tools [1, 26] andformal argumentation frameworks such as the ASPIC+ framework [30].
49

1800

In the context of BNs, another graph-based intermediary formalism was
proposed by Timmer and colleagues [37]. They introduced the support graphthat captures general reasoning patterns represented by a BN for the purpose of
explaining such patterns in terms of argumentation. Compared to the present
paper, Timmer and colleagues’ work is in the reverse direction, namely from
BNs to domain-specific rules and inferences (i.e. arguments).
10. Conclusion and Future Research

1805

1810

1815

1820

1825

1830

1835

In this paper, we have presented the IG-formalism, which provides a precise
account of the interplay between deductive and abductive inference and causal
and evidential generalisations and which imposes constraints on the inferencesthat may be performed with this knowledge given the evidence. Moreover, wehave introduced a BN graph construction approach that demonstrates that theknowledge expressed in an IG, namely the generalisations and conflicts expressedin the graph, can be directly exploited for this purpose. Given the evidence,
sequences of inferences can be read from an IG; we have formally proven that all
such sequences in an IG are captured in the form of induced active chains in thecorresponding BN graph constructed by our approach, as intended. Moreover,by considering the inferences that can be read from an IG given the evidence,some qualitative constraints on the (conditional) probabilities of the BN underconstruction are derived. These qualitative probabilistic constraints may serve
as input for a subsequent elicitation procedure for obtaining a fully specified
QPN [33] or BN for (qualitative) probabilistic inference. We have identified
conditions on the IG under which the fully automatically constructed initialgraph is guaranteed to be a DAG, simplifying the (manual) verification step.
Lastly, we have identified bounds on the size of the CPTs and the complexityof probabilistic inference in BNs constructed by our approach.
Our IG-formalism, together with our BN construction approach, allow us toconstruct an initial BN graph from a domain expert’s initial analysis, capturing
similar reasoning patterns as can be read from their IG given the evidence; it
thereby simplifies the BN elicitation process. We note that BN construction is
an iterative process in which both the domain expert and BN modeller should
stay involved; this also holds when applying our approach, as even the provided
IG may be incomplete or may be subject to change over time. To aid in thisiterative process, approaches can be used [23, 41] such as discussed in Sect. 9.3.
IGs formalise analyses performed by domain experts using the informal reasoning tools they are familiar with. In interpreting a performed analysis as anIG, an additional knowledge elicitation step in consultation with the domain
expert may be required as the used generalisations and the manner of conflictare typically left implicit in these analyses. IGs may also be directly constructedby domain experts in case work. As mentioned earlier, we expect direct IG construction to be more straightforward than direct BN construction for domain
experts unfamiliar with the BN-formalism, a claim we intend to empiricallyevaluate in our future work.

50

1840

1845

1850

1855

1860

1865

1870

1875

In future work general guidelines for IG construction may be formulated. In
our case study of Sect. 8 we constructed an IG corresponding to a Wigmore
chart according to a number of general heuristics. For instance, in establishing
which generalisations could have been used in constructing the chart we among
other things determined whether sequences of described events could be interpreted as instances of story schemes [2] (see Sect. 8.2). In future work a databaseof schemes that capture general patterns of defeasible reasoning (including argumentation schemes [1] and story schemes) may be composed, instantiationsof which can be used as building blocks in facilitating IG construction. Suchan approach would in turn facilitate BN graph construction. In the context
of BNs such an approach is comparable to the idiom-based approaches to BN
construction discussed in Sect. 9.2.
We also intend to increase the expressivity of our IG-formalism by allowing
generalisations that are neither causal nor evidential. For instance, definitions,or abstractions [8] allow for reasoning at different levels of abstraction, such as
stating that guns can generally be considered deadly weapons. Another example
of a different type of generalisation is a generalisation representing a mere statistical correlation, such as a correlation between homelessness and criminality.
In the manual construction of BN graphs, arcs are typically directed using thenotion of causality as a guiding principle; however, non-causal relations are also
considered in the literature. For instance, in the BN construction guidelines ofFenton and colleagues [16, Ch. 7] not only causal but also definitional relations
are considered, in which arcs in the BN graph are oriented in the direction inwhich a sub-attribute (or combination of sub-attributes) defines an attribute.
In previous research, we investigated BN graph construction from a preliminary
form of IGs including abstractions and other types of generalisations [40]; in our
future work, we intend to generalise the currently proposed BN graph construction approach to an extended IG-formalism allowing for such generalisations.
We will also focus on deriving more probabilistic constraints such as qualitative influences corresponding to inferences that can be read from an IG given
the evidence. Our approach may then serve to construct fully specified QPNs
for qualitative probabilistic inference [33], as discussed in Sect. 9.3. We also
intend to evaluate our approach by assessing the quality of BNs constructedfrom IGs. Since we are considering BN construction in data-poor domains, we
assume that there is insufficient data to learn a reliable BN from and that sucha BN is therefore not available for comparison. A quality assessment should
therefore mainly be based on compliance with best practice guidelines for BN
construction [16, Ch. 7].

51

References[1] F. Bex, H. Prakken, C. A. Reed, and D. Walton. Towards a formal accountof reasoning about evidence: argumentation schemes and generalisations.
Artificial Intelligence and Law, 11(2–3): 125–165, 2003.
[2] F. Bex. Arguments, Stories and Criminal Evidence: A Formal Hybrid Theory. Springer, 2011.
[3] F. Bex, S. Modgil, H. Prakken, and C. A. Reed. On logical specificationsof the argument interchange format. Journal of Logic and Computation,
23(5): 951–989, 2013.
[4] F. Bex. An integrated theory of causal stories and evidential arguments. In
Proceedings of the Fifteenth International Conference on Artificial Intelligence and Law, pp. 13–22. ACM Press, 2015.
[5] F. Bex and S. Renooij. From arguments to constraints on a Bayesian network. In P. Baroni, T. F. Gordon, T. Scheffler, and M. Stede, eds., Computational Models of Argument: Proceedings of COMMA 2016, pp. 95–106.
IOS Press, 2016.
[6] S. W. van den Braak, H. van Oostendorp, H. Prakken, and G. A. W.
Vreeswijk. Representing narrative and testimonial knowledge in sensemaking software for crime analysis. In E. Francesconi, G. Sartor, and D.
Tiscornia, eds., Legal Knowledge and Information Systems: JURIX 2008:
The Twenty-First Annual Conference, pp. 160–169. IOS Press, 2008.
[7] C. P. de Campos and F. Cozman. Belief updating and learning in semiqualitative probabilistic networks. In F. Bacchus and T. Jaakkola, eds.,
Proceedings of the Twenty-First Conference on Uncertainty in Artificial
Intelligence, pp. 153–160. AUAI Press, 2005.
[8] L. Console and D. T. Dupré. Abductive reasoning with abstraction axioms.
In G. Lakemeyer and B. Nebel, eds., Foundations of Knowledge Representation and Reasoning, vol. 810, pp. 98–112. Springer, 1994.
[9] F. G. Cozman. Credal networks. Artificial Intelligence, 120: pp. 199–233,
2000.
[10] V. Crupi, K. Tentori, and M. Gonzalez. On Bayesian measures of evidential
support: theoretical and empirical issues. Philosophy of Science, 74(2):229–252, 2007.
[11] A. Darwiche. Modeling and Reasoning with Bayesian Networks. Cambridge
University Press, 2009.
[12] A. P. Dawid. Beware of the DAG! In I. Guyon, D. Janzing and B. Schölkopf,
eds., NIPS Causality: Objectives and Assessment, pp. 59–86, 2010.

52

[13] M. J. Druzdzel and M. Henrion. Intercausal reasoning with uninstantiatedancestor nodes. In D. Heckerman and E. Mamdani, eds., Proceedings of theNinth Conference on Uncertainty in Artificial Intelligence, pp. 317–325.
Morgan Kaufmann, 1993.
[14] M. J. Druzdzel and L. C. van der Gaag. Elicitation of probabilities forbelief networks: combining qualitative and quantitative information. In
P. Besnard and S. Hanks, eds., Proceedings of the Eleventh Conference
on Uncertainty in Artificial Intelligence, pp. 141–148. Morgan Kaufmann,
1995.
[15] P. M. Dung. On the acceptability of arguments and its fundamental role innonmonotonic reasoning, logic programming and n-person games. Artificial
Intelligence, 77(2): 321–357, 1995.
[16] N. Fenton and M. Neil. Risk Assessment and Decision Analysis with Bayesian Networks. CRC Press, 2012.
[17] S. Fenz. An ontology-based approach for constructing Bayesian networks.
Data & Knowledge Engineering, 73: 73–88, 2012.
[18] L. C. van der Gaag and E. M. Helsper. Experiences with modelling issues inbuilding probabilistic networks. In A. Gómez-Pérez and V. R. Benjamins,
eds., International Conference on Knowledge Engineering and Knowledge
Management, vol. 2473, pp. 21–26. Springer, 2002.
[19] S. P. van Gosliga and I. van de Voorde. Hypothesis management framework: a flexible design pattern for belief networks in decision support systems. In S. Renooij, H. J. M. Tabachneck-Schijf, and S. M. Mahoney, eds.,
Proceedings of the Sixth Bayesian Modelling Applications Workshop at theConference on Uncertainty in Artificial Intelligence. CEUR, 2008.
[20] F. V. Jensen and T. D. Nielsen. Bayesian Networks and Decision Graphs.
Springer, 2nd ed., 2007.
[21] J. R. Josephson and S. G. Josephson. Abductive Inference: Computation,
Philosophy, Technology. Cambridge University Press, 1994.
[22] J. B. Kadane and D. A. Schum. A Probabilistic Analysis of the Sacco and
Vanzetti Evidence. John Wiley & Sons Inc., 1996.
[23] J. Keppens. On modelling non-probabilistic uncertainty in the likelihood ratio approach to evidential reasoning. Artificial Intelligence and Law, 22(3):239–290, 2014.
[24] D. Koller and A. Pfeffer. Object-oriented Bayesian networks. In D. Geiger
and P. Shenoy, eds., Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence, pp. 302–313. Morgan Kaufmann, 1997.

53

[25] K. B. Laskey and S. M. Mahoney. Network fragments: representing knowledge for constructing probabilistic models. In D. Geiger and P. P. Shenoy,eds., Proceedings of the Thirteenth Conference on Uncertainty in Artificial
Intelligence, pp. 334–341. Morgan Kaufmann, 1997.
[26] A. Okada, S. J. Buckingham Shum, and T. Sherborne, eds., Knowledge
Cartography: Software Tools and Mapping Techniques. Springer, 2nd ed.,2014.
[27] J. Pearl. Embracing causality in default reasoning. Artificial Intelligence,35(2): 259–271, 1988.
[28] J. Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, 2nd ed., 2009.
[29] D. Poole. Representing diagnosis knowledge. Annals of Mathematics andArtificial Intelligence, 11(1–4): 33–50, 1994.
[30] H. Prakken. An abstract framework for argumentation with structured arguments. Argument & Computation, 1(2): 93–124, 2010.
[31] A. Ramı́rez-Noriega, R. Juárez-Ramı́rez, J. J. Tapia, V. H. Castillo, and S.
Jiménez. Construction of conditional probability tables of Bayesian networks using ontologies and Wikipedia. Computación y Sistemas, 23(4):1275–1289, 2019. doi:10.13053/CyS-23-4-2705.
[32] R. Reiter. A logic for default reasoning. Artificial Intelligence, 13(1–2):
81–132, 1980.
[33] S. Renooij and L. C. van der Gaag. From qualitative to quantitative probabilistic networks. In A. Darwiche and N. Friedman, eds., Proceedings ofthe Eighteenth Conference on Uncertainty in Artificial Intelligence (UAI),
pp. 422–429. Morgan Kaufmann, 2002.
[34] A. de Ronde, B. Kokshoorn, C. J. de Poot, and M. de Puit. The evaluationof fingermarks given activity level propositions. Forensic Science International, 302: 109904, 2019.
[35] M. Shanahan. Prediction is deduction but explanation is abduction. In N. S.
Sridharan, ed., Proceedings of International Joint Conference on Artificial
Intelligence 89, pp. 1055–1060. Morgan Kaufmann, 1989.
[36] F. Taroni, C. G. Aitken, P. Garbolino and A. Biedermann. Bayesian Networks for Probabilistic Inference and Decision Analysis in Forensic Science.
Wiley, 2014.
[37] S. T. Timmer, J.-J. C. Meyer, H. Prakken, S. Renooij, and B. Verheij.
A two-phase method for extracting explanatory arguments from Bayesian
networks. International Journal of Approximate Reasoning, 80: 475–494,
2017.
54

[38] N. Timmers. The hybrid theory in practice: a case study at the Dutch
police force. Master’s thesis, Utrecht University, The Netherlands, 2017.
[39] R. Wieten, F. Bex, H. Prakken, and S. Renooij. Exploiting causality inconstructing Bayesian networks from legal arguments. In M. Palmirani, ed.,Legal Knowledge and Information Systems. JURIX 2018: The Thirty-First
Annual Conference, vol. 313, pp. 151–160. IOS Press, 2018.
[40] R. Wieten, F. Bex, H. Prakken, and S. Renooij. Constructing Bayesian
network graphs from labeled arguments. In G. Kern-Isberner and Z. Ognjanović, eds., Proceedings of the Fifteenth European Conference on Symbolicand Quantitative Approaches to Reasoning with Uncertainty (ECSQARU),
LNAI, vol. 11726, pp. 99–110. Springer, 2019.
[41] R. Wieten, F. Bex, H. Prakken, and S. Renooij. Supporting discussions
about forensic Bayesian networks using argumentation. In Proceedings of
the Seventeenth International Conference on Artificial Intelligence andLaw, pp. 143–152. ACM Press, 2019.
[42] R. Wieten, F. Bex, H. Prakken, and S. Renooij. Deductive and abductive reasoning with causal and evidential information. In H. Prakken, S.
Bistarelli, F. Santini, and C. Taticchi, eds., Computational Models of Argument. Proceedings of COMMA 2020, pp. 383–394. IOS Press, 2020.
[43] J. H. Wigmore. The Principles of Judicial Proof. Little, Brown and Company, 1913.
[44] J. de Zoete, M. Sjerps, D. Lagnado, and N. Fenton. Modelling crime linkage
with Bayesian networks. Science and Justice, 55(3): pp. 209–217, 2015.

55