Reliable Uncertain Evidence Modeling in
Bayesian Networks by Credal Networks
arXiv:1802.05639v1 [] 15 Feb 2018

Sabina Marchetti
Sapienza University of Rome
Rome (Italy)
sabina.marchetti@uniroma1.it
Alessandro Antonucci
IDSIA
Lugano (Switzerland)
alessandro@idsia.ch
February 16, 2018
Abstract
A reliable modeling of uncertain evidence in Bayesian networks based
on a set-valued quantification is proposed. Both soft and virtual evidences
are considered. We show that evidence propagation in this setup can be reduced to standard updating in an augmented credal network, equivalent to a
set of consistent Bayesian networks. A characterization of the computational
complexity for this task is derived together with an efficient exact procedure
for a subclass of instances. In the case of multiple uncertain evidences over
the same variable, the proposed procedure can provide a set-valued version
of the geometric approach to opinion pooling.

1

Introduction

Knowledge-based systems are used in AI to model relations among the variables
of interest for a particular task, and provide automatic decision support by inference algorithms. This can be achieved by joint probability mass functions. When
a subset of variables is observed, belief updating is a typical inference task that
propagates such (fully reliable) evidence. Whenever the observational process is
1

unable to clearly report a single state for the observed variable, we refer to uncertain evidence. This might take the form of a virtual instance, described by
the relative likelihoods for the possible observation of every state of a considered
variable [25]. Also, soft evidence [30] denotes any observational process returning
a probabilistic assessment, whose propagation induces a revision of the original
model [21]. Bayesian networks are often used to specify joint probability mass
functions implementing knowledge-based systems [22]. Full, or hard [30], observation of a node corresponds to its instantiation in the network, followed by
belief updating. Given virtual evidence on some variable, the observational process can be modeled à la Pearl in Bayesian networks: an auxiliary binary child
of the variable is introduced, whose conditional mass functions are proportional
to the likelihoods [25]. Instantiation of the auxiliary node yields propagation of
virtual evidence, and standard inference algorithms for Bayesian networks can be
used [22]. Something similar can be done with soft evidence, but the quantification of the auxiliary node should be based on additional inferences in the original
network [9].
In the above classical setup, sharp probabilistic estimates are assumed for the
parameters modeling an uncertain observation. We propose instead a generalized
set-valued quantification, with interval-valued likelihoods for virtual evidence and
sets of marginal mass functions for soft evidence. This offers a more robust modeling of observational processes leading to uncertain evidence. To this purpose,
we extend the transformations defined for the standard case to the set-valued case.
The original Bayesian network is converted into a credal network [12], equivalent
to a set of Bayesian networks consistent with the set-valued specification. We
characterize the computational complexity of the credal modeling of uncertain
evidence in Bayesian networks, and propose an efficient inference scheme for a
special class of instances. The discussion is indeed specialized to opinion pooling
and our techniques used to generalize geometric functionals to support set-valued
opinions.

1.1 Related Work
Model revision based on uncertain evidence is a classical topic in AI. Entropybased techniques for the absorption of uncertain evidence were proposed in the
Bayesian networks literature [30, 26], as well as for the pooling of convex sets
of probability mass functions [1]. Yet, this approach was proved to fail standard
postulates for revision operators in generalized settings [20]. Uncertain evidence
absorption has been also considered in the framework of generalized knowledge
representation and reasoning [17]. The discussion was specialized to evidence
theory [32, 23], although revision based on uncertain instances with graphical
models becomes more problematic and does not give a direct extension of the
2

Bayesian networks formalism [28]. Finally, credal networks have been considered
in the model revision framework [13]. Yet, these authors consider the effect of a
sharp quantification of the observation in a previously specified credal network,
while we consider the opposite situation of a Bayesian network for which credal
uncertain evidence is provided.

2

Background

2.1 Bayesian and Credal Networks
Let X be any discrete variable. Notation x and ΩX is used, respectively, for a
generic value and for the finite set of possible values of X. If X is binary, we
set ΩX := {x, ¬x}. We denote as P (X) a probability mass function (PMF) and
as K(X) a credal set (CS), defined as a set of PMFs over ΩX . We remove inner
points from CSs, i.e. those which can be obtained as convex combinations of other
points, and assume the CS finite after this operation. CS K0 (X), whose convex
hull includes all PMFs over ΩX is called vacuous.
Given another variable Y , define a collection of conditional PMFs as P (X|Y ) :=
{P (X|y)}y∈ΩY . P (X|Y ) is called conditional probability table (CPT). Similarly,
a credal CPT (CCPT) is defined as K(X|Y ) := {K(X|y)}y∈ΩY . An extensive
CPT (ECPT) is a finite collection of CPTs. A CCPT can be converted into an
equivalent ECPT by considering all the possible combinations from the elements
of the CSs.
Given a joint variable X := {X0 , X1 , . . . , Xn }, a Bayesian network (BN)
[25] serves as a compact way to specify a PMF over X. A BN is represented by
a directed acyclic graph G, whose nodes are in one-to-one correspondence with
the variables in X, and a collection of CPTs {P (Xi |Πi )}ni=0 , where Πi is the joint
variable of the parents of Xi according to G. Under the Markov condition, i.e. each
variable is conditionally independent of its non-descendants
Q non-parents given its
parents, the joint PMF P (X) factorizes as P (x) := ni=0 P (xi |πi ), where the
values of xi and πi are those consistent with x, for each x ∈ ΩX = ×ni=0 ΩXi .
A credal network (CN) [12] is a BN whose CPTs are replaced by CCPTs (or
ECPTs). A CN specifies a joint CS K(X), obtained by considering all the joint
PMFs induced by the BNs with CPTs in the corresponding CCPTs (or ECPTs).
The typical inference task in BNs is updating, defined as the computation of
the posterior probabilities for a variable of interest given hard evidence about some
other variables. Without loss of generality, let the variable of interest and the observation be, respectively, X0 and Xn = xn . Standard belief updating corresponds

3

to:

P

P (x0 |xn ) = P

x1 ,...,xn−1

Qn

x0 ,x1 ,...,xn−1

Qi=0
n

P (xi |πi )

i=0

P (xi |πi )

.

(1)

Updating is NP-hard in general BNs [11], although efficient computations can be
performed in polytrees [25] by message propagation routines [22].
CN updating is similarly intended as the computation of lower and upper
bounds of the updated probability in Eq. (1) with respect to K(X). Notation
P (x0 |xn ) (P (x0 |xn )) is used to denote lower (upper) bounds. CN updating extends BN updating and it is therefore NP-hard [14]. Contrary to the standard
setting, inference in generic polytrees is still NP-hard [24], with the notable exception of those networks whose variables are all binary [18].

2.2 Virtual and Soft Evidence
Eq. (1) gives the updated beliefs about queried variable X0 . The underlying assumption is that Xn has been the subject of a fully reliable observational process,
and its actual value is known to be xn . This is not always realistic. Evidence
might result from a process which is unreliable and only the likelihoods for the
possible values of the observed variable may be assessed (e.g., the precision and
the false discovery rate for a positive medical test). Virtual evidence (VE) [25]
applies to such type of observation. Notation λXn := {λxn }xn ∈ΩXn identifies a
VE, λxn being the likelihood of the observation provided (Xn = xn ). Given VE,
the analogous of Eq. (1) is:
P
xn λxn P (x0 , xn )
PλXn (x0 ) := P
,
(2)
xn λxn P (xn )

where the probabilities in the right-hand side are obtained by marginalization
of the joint PMF of the BN. Eq. (2) can be equivalently obtained by augmenting the BN with auxiliary binary node DXn as a child of Xn . By specifying
P (dXn |xn ) := λxn for each xn ∈ ΩXn , it is easy to check that P (x0 |dXn ) =
PλXn (x0 ), i.e. Eq. (2) can be reduced to a standard updating in an augmented BN.
The notion of soft evidence (SE) refers to a different situation, in which the
observational process returns an elicitation P ′ (Xn ) for the marginal PMF of Xn .
See [5] for a detailed discussion on the possible situations producing SE. If this is
the case, P ′(Xn ) is assumed to replace the original beliefs about Xn by Jeffrey’s
updating [21], i.e.
X
PX′ n (x0 ) :=
P (x0 |xn ) · P ′(xn ) .
(3)
xn

4

Eq. (3) for SE reduces to Eq. (1) whenever P ′ (Xn ) assigns all the probability
mass to a single value in ΩXn . The same happens for VE in Eq. (2), when all
the likelihoods are zero apart from the one corresponding to the observed value.
Although SE and VE refer to epistemologically different informational settings,
the following result provides means for a unified approach to their modeling.
Proposition 1 ([9]). Absorption of a SE P ′ (Xn ) as in Eq. (3) is equivalent to
Eq. (2) with a VE specified as:
λx n ∝

P ′(xn )
,
P (xn )

(4)

for each xn ∈ ΩXn .1
Vice versa, absorption of a VE λXn as in Eq. (2) is equivalent to Eq. (3) with
a SE specified as:

for each xn ∈ ΩXn .

λx P (xn )
P ′ (xn ) := P n
,
xn λxn P (xn )

(5)

In the above setup for SE, states that are impossible in the original BN cannot
be revised, i.e. if P (xn ) = 0 for some xn ∈ ΩXn , then also P ′ (xn ) = 0 and any
value can be set for λxn . Vice versa, according to Eq. (5), a zero likelihood in a
VE renders impossible the corresponding state of the SE. Thus, at least a non-zero
likelihood should be specified in a VE. All these issues are shown in the following
example.
Example 1. Let X denote the actual color of a traffic light with ΩX := {g, y, r}.
Assume g (green) more probable than r (red), and y (yellow) impossible. Thus, for
instance, P (X) = [4/5, 0, 1/5]. We eventually revise P (X) by a SE P ′ (X), which
keeps yellow impossible and assigns the same probability to the two other states,
i.e. P ′ (X) = [1/2, 0, 1/2]. Because of Eq. (4), this can be equivalently achieved by
a VE λX ∝ {1, 1, 4}. Vice versa, because of Eq. (5), a VE λ̃X ∝ {1, 1, 5} induces
an updated Pλ̃ (X) = [4/9, 0, 5/9]. Such PMF coincides with P (X|dX ) in a twonode BN, with DX child of X, CPT P (DX |X) with P (dX |X) = [1/10, 1/10, 1/2]
and marginal PMF P (X) as in the original specification.
1
VE is defined as a collection of likelihoods, which in turn are defined up to a multiplicative
positive constant. This clearly follows from Eq. (2). The relation in Eq. (4) is proportionality and
not equality just to make all the likelihoods smaller or equal than one.

5

3

Credal Uncertain Evidence

3.1 Credal Virtual Evidence
We propose credal VE (CVE) as a robust extension of sharp virtual observations.
Notation ΛXn is used here for the intervals {λxn , λxn }xn ∈ΩXn . CVE updating is
defined as the computation of the bounds of Eq. (2) with respect to all VEs λXn
consistent with the interval constraints in ΛXn . Notation P ΛXn (x0 ) and P ΛXn (x0 )
is used to denote these bounds. CVE absorption in BNs is done as follows.
Transformation 1. Given a BN over X and a CVE ΛXn , add a binary child DXn
of Xn and quantify its CCPT K(DXn |Xn ) with constraints λxn ≤ P (dXn |xn ) ≤
λxn .2 A CN with a single credal node results.
By Tr. 1, CVE updating in a BN is reduced to CN updating.
Theorem 1. Given a CVE in a BN, consider the CN returned by Tr. 1. Then:
P (x0 |dXn ) = P ΛXn (x0 ) ,

(6)

and analogously for the upper bounds.
Standard VE can be used to model partially reliable sensors or tests, whose
quantification is based on sensitivity and specificity data. Since these data are not
always promptly/easily available (e.g., a pregnancy test whose failure can be only
decided later), a CVE with interval likelihoods can be quantified by the imprecise
Dirichlet model3 [6] as in the following example.
Example 2. The reference standard for diagnosis of anterior cruciate legament
sprains is arthroscopy. In a trial, 40 patients coming in with acute knee pain are
examined using the Declan test [10]. Every patient also has an arthroscopy procedure for a definitive diagnosis. Results are TP=17 (Declan positive, arthroscopy
positive), FP=3 (Declan positive, arthroscopy negative), FN=6 (Declan negative,
arthroscopy positive) and TN=14 (Declan negative, arthroscopy negative). Patients visiting a clinic have prior sprain probability P (x) = 0.2. Given a positive
Declan, the imprecise Dirichlet model (see Footnote 3) with s = 1 corresponds
to CVE λx = 17/23 + 1, λx = 17 + 1/23 + 1, λ¬x = 3/17 + 1, λ¬x = 3 + 1/17 + 1. The
bounds of the updated sprain probability with respect to the above constraints
are P ΛX (x) = 1/3, P ΛX (x) ≃ 0.53. A VE with frequentist estimates would have
produced instead PλX ≃ 0.51.
2

For binary B, constraint l ≤ P (b) ≤ u defines a CS K(B) with elements P1 (B) := [l, 1 − l]
and P2 (B) := [u, 1 − u].
3
Given N observations of X, if n(x) of them reports x, the lower bound of P (x) for to the
n(x)
n(x)+s
imprecise Dirichlet model is N
+s , and the upper bound N +s , with s effective prior sample size.

6

3.2 Credal Soft Evidence
Analogous to CVE, credal soft evidence (CSE) on Xn can be specified by any
CS K ′ (Xn ). Accordingly, CSE updating computes the bounds spanned by the
updating of all SEs based on PMFs consistent with the CS, i.e.
X
P ′Xn (x0 ) := ′ min′
P (x0 |xn ) · P ′ (xn ) ,
(7)
P (Xn )∈K (Xn )

xn

′

and analogously for the upper bound P Xn (x0 ).
The shadow of a CS K(X) is a CS K̂(X) obtained from all the PMFs P̂ (X)
such that, for each x ∈ ΩX :
min

P (X)∈K(X)

P (x) ≤ P̂ (x) ≤

max

P (X)∈K(X)

P (x) .

(8)

A CS coinciding with its shadow is called shady. It is a trivial exercise to check
that CSs over binary variables are shady. 4
The following result extends Pr. 1 to the imprecise framework.
Theorem 2. Absorption of a CSE with shady K ′ (Xn ) is equivalent to that of CVE
ΛXn such that:
P ′ (xn )
λx n ∝
,
(9)
P (xn )
where P ′ (xn ) := minP ′ (Xn )∈K ′ (Xn ) P ′ (xn ) and analogously for the upper bound.
Vice versa absorption of a CVE ΛXn is equivalent to that of a CSE such that:
P ′ (xn ) =

P (xn )λxn
,
P
P (xn )λxn + x′n 6=xn P (x′n )λx′n

(10)

and analogously with a swap between lower and upper likelihoods for the upper
bound.
By Th. 1 and 2, CSE updating in a BN is reduced to standard updating in a CN.
This represents a generalization to the credal case of Pr. 1. For CSEs with nonshady CSs, the procedure is slightly more involved, as detailed by the following
result.
Proposition 2. Given a CSE K ′ (Xn ) := {Pi′ (Xn )}ki=1 in a BN, add a binary child
DXn of Xn quantified by an ECPT {Pi (DXn |Xn )}ki=1 such that Pi (dXn |xn ) ∝
Pi′ (xn )
for each i = 1, . . . , k and xn ∈ ΩXn . Then:
P (xn )
P ′Xn (x0 ) = P (x0 |dXn ) .
4

Following [8], a shadow is just the set of probability intervals induced by a generic CS.

7

(11)

To clarify these results, consider the following example.
Example 3. Consider the same setup as in Ex. 1. Let us revise the original
PMF P (X) by a CSE based on the shady CS K ′ (X) := {P1′ (X), P2′ (X)}, with
P1′ (X) := [0.6, 0, 0.4] and P2′ (X) := [0.4, 0, 0.6]. Th. 2 can be used to convert
such CSE in a CVE ΛX := {2-3 : 1 : 8-12}. Vice versa, the beliefs induced
by CVE Λ̃X := {3-5 : 1 : 8-10} are P Λ̃X (g) = 3/5, P Λ̃X (g) = 2/3, P Λ̃X (y) =
P Λ̃X (y) = 0, and P Λ̃X (r) = 1/3, P Λ̃X (r) = 2/5. These bounds may be equivalently obtained in a two-node CN with DX child of X and CCPT K(DX |X) such
that P (dX |X = g) ∈ [0.6, 1], P (dX |X = y) = 1, and P (dX |X = r) ∈ [0.8, 1].
Alternatively, following Pr. 2, absorption of K ′ (X) can be achieved by a ECCPT
with two CPTs.
We point out that conservative updating (CU), a credal updating rule for reliable treatment of missing non-MAR data [15], falls as a special case in our formalism. CU is defined as:
P ′Xn (x0 ) = min P (x0 |xn ) ,
xn ∈ΩXn

(12)

and represents the most conservative approach to belief revision. A vacuous
CCPT is specified, with [0, 1] intervals for each value, either i) by Tr. 1, given CVE
whose likelihoods take any value between zero and one 5 , or ii) by straightforward
application of Th. 2, if a vacuous CSE K0′ (Xn ) is provided. The resulting ECPT
with |ΩX | CPTs6 corresponds to the CU implementation in [3]. Also, Eq. (7) reduces to Eq. (12), given vacuous CSE. We can similarly proceed in the case of
incomplete observations, i.e. some values of Xn are recognized as impossible, but
no information can be provided about the other ones. If this is the case, we just
replace ΩXn with Ω′Xn ⊂ ΩXn .

4

Credal Probability Kinematics

Given two joint PMFs P (X) and P ′(X), we say that the latter comes from the
first by probability kinematics (PK) on the (coarse) partition of ΩX induced by
Xn if and only if P ′ (x|xn ) = P (x|xn ) for each x ∈ ΩX and xn ∈ ΩXn [16, 9].7
This is the underlying assumption in Eq. (3). If P ′(X) is replaced by a CS, PK is
generalized as follows.
5

As VE likelihoods are defined up to a positive multiplicative constant, we can set any positive
λxn provided that λxn = 0.
6
The induced ECPT contains all 2|ΩXn | combinations of zero and ones in the CPTs. Yet, only
those having a single one in the row associated to dXn remains after the convex hull.
7
Full consistency of P ′ with the evidence inducing the revision process is not explicitly required. A more stringent characterization of PK was proposed, among others, by [31]

8

Definition 1. Let P (X) and K ′ (X) be, respectively, a joint PMF and a joint CS.
We say that K ′ (X) comes from P (X) by credal probability kinematics (CPK) on
′
the partition of ΩX induced by Xn if and only if it holds P ′ (x|xn ) = P (x|xn ) =
P (x|xn ), for each x ∈ ΩX and xn ∈ ΩXn .
That is, any revision process based on (generalized) PK guarantees invariance
of the relevance of xn , for each xn ∈ ΩXn , to any other possible event in the
model, say x0 . The following consistency result holds for CSEs.
Theorem 3. Given a BN over X and a shady CSE K ′ (Xn ), convert the CSE into
a CVE as in Th. 2 and transform the BN into a CN by Tr. 1. Let K ′ (X, DXn )
be the joint CS associated to the CN. Then, K ′ (X|dXn ) comes from P (X) by
CPK on the partition induced by Xn . Moreover K ′ (Xn |dXn ) coincides with the
marginal CS in the CN.

5

Multiple Evidences

So far, we only considered the updating of a single CVE or CSE. We call uncertain
credal updating (UCU) of a BN the general task of computing updated/revised beliefs in a BN with an arbitrary number of CSEs, CVEs, and hard evidences as well.
Here, UCU is intended as iterated application of the procedures outlined above.
See for instance [17], for a categorization of iterated belief revision problems and
their assumptions. When coping with multiple VEs in a BN, it is sufficient to add
the necessary auxiliary children to the observed variables and quantify the CPTs
as described. We similarly proceed with multiple CVEs.
The procedure becomes less straightforward when coping with multiple SEs or
CSEs, since quantification of each auxiliary child by Eq. (4) requires a preliminary
inference step. As a consequence, iterated revision might be not invariant with
respect to the revision process scheme [31].
Additionally, with CSEs, absorption of the first CSE transforms the BN into
a CN, and successive absorption of other CSEs requires further extension of the
procedure in Th. 2. We leave such an extension as future work, and here we just
consider simultaneous absorption of all evidences. If this is the case, multiple
CSEs can be converted in CVEs and the inferences required for the quantification
of the auxiliary children is performed in the original BN.

5.1 Algorithmic and Complexity Issues
ApproxLP [2] is an algorithm for general CN updating based on linear programming. It provides an inner approximation of the updated intervals with the same

9

complexity of a BN inference on the same graph. Roughly, CN updating is reduced by ApproxLP to a sequence of linear programming tasks. Each is obtained
by iteratively fixing all the local models to single elements of the corresponding
CSs, while leaving a free single variable. It follows the algorithm efficiently produces exact inferences whenever a CN has all local CSs made of a single element
apart from one. This is the case of belief updating with a single CVE/CSE.

5.2 Complexity Issues
Since standard BN updating of polytrees can be performed efficiently, the same
happens with VEs and/or SEs, as Tr. 1 does not affect the topology (nor the
treewidth) of the original network. Similarly, with multiply connected models,
BN updating is exponential in the treewidth, and the same happens with models
augmented by VEs and/or SEs.
As already noticed, with CNs, binary polytrees can be updated efficiently,
while updating ternary polytrees is already NP-hard. An important question is
therefore whether or not a similar situation holds for UCU in BNs. The (positive)
answer is provided by the two following results.
Proposition 3. UCU of polytree-shaped binary BNs can be solved in polynomial
time.
The proof of this proposition is trivial and simply follows from the fact that
the auxiliary nodes required to model CVE and/or CSE are binary (remember
that CSs over binary variables are always shady). The CN solving the UCU is
therefore a binary polytree that can be updated by the exact algorithm proposed in
[18].
Theorem 4. UCU of non-binary polytree-shaped BNs is NP-hard.
The proof of this theorem is based on a reduction to the analogous result for
CNs [24]. This already concerns models whose variables have no more than three
states and treewidth equal to two. In these cases, approximate inferences can be
efficiently computed by ApproxLP.

6

Credal Opinion Pooling

Consider the generalized case of m ≥ 1 overlapping probabilistic instances on
Xn . For each j = 1, . . . , m, let Pj′ (Xn ) denote the SE reported by the j-th source.
Straightforward introduction of m auxiliary nodes as outlined above would suffer

10

confirmational dynamics, analogous to the well-known issue with posterior probability estimates in the naive Bayes classifier [27]. This might likely yield inconsistent revised beliefs, i.e. P̃ ′ (Xn ) falls outside the convex hull of {Pj′(Xn )}m
j=1 .
A most conservative approach to prevent such inconsistency adopts the convex hull of all the opinions [29]. In our formalism, this is just the CS K ′ (Xn ) :=
′
′
{Pj′ (Xn )}m
j=1 . Yet, consider any small ǫ > 0, and assume P1 (xn ) = ǫ, P2 (xn ) =
′
1 − ǫ, and Pj (xn ) = p ∈ (ǫ, 1 − ǫ) for each j = 3, . . . , m. Despite the consensus of all remaining sources on sharp value p, the conservative approach above
would yield K ′ (Xn ) ≃ K0 (Xn ). To what extent should this be preferred to the
confirmational case is an open question.
A compromise solution might be offered by the geometric pooling
operator
Pm
(or LogOp) [4]. Given a collection of positive weights {αj }m
,
with
j=1
j=1 αj =
1, the LogOp functional produces the PMF P̃ ′ (Xn ) such that:
′

P̃ (xn ) ∝

m
Y

Pj′ (x)αj ,

(13)

j=1

for each xn ∈ ΩXn . P̃ ′ (Xn ) belongs to the convex hull of {Pj′(Xn )}m
j=1 for any
specification of the weights [1]. The overlapping SEs associated to the PMF in
Eq. (13) can be equivalently modeled by a collection of m VEs defined as follows.
Transformation 2. Consider a BN over X and a collection of SEs on Xn , {Pj′(Xn )}m
j=1 .
(j)
For each j = 1, . . . , m, augment the BN with binary child DXn of Xn whose CPT
h ′
iαj
Pm
(j)
(xn )
is such that P (dXn |xn ) ∝ PP (x
,
with
j=1 αj = 1.
)
n
The transformation is used for the following result.

Proposition 4. Consider the same inputs as in Tr. 2. Then:
(1)

(m)

P̃X′ n (x0 ) = P (x0 |dXn , . . . , dXn ) ,

(14)

where the probability on the left-hand side is obtained by the direct revision induced by P̃ ′ (Xn ), while the probability on the right-hand side of Eq. (14) has been
computed in the BN returned by Tr. 2.
The proof follows from the conditional independence of the auxiliary nodes
given Xn . Also, note how our proposal simultaneously performs pooling and
absorption of overlapping SEs.
Suppose m sources provide generalized CSEs about Xn , say {Kj′ (Xn )}m
j=1 .
′
′
Let K̃ (Xn ) denote the CS induced by LogOp as in Eq. (13), for each Pj (Xj ) ∈
Kj′ (Xn ), j = 1, . . . , m [1]. We generalize Tr. 2 as follows:
11

Transformation 3. Consider a BN over X and the collection of CSEs {Kj′ (Xn )}m
j=1 .
(j)
For each j = 1, . . . , m, augment the BN with binary child DXn of Xn , whose
iαj
iαj
h ′
h ′
(j)
(j)
(xn )
P (xn )
CCPT is such that P (dXn |xn ) ∝ PP (x
and
.
P
(d
|x
)
∝
n
Xn
P (xn )
n)
This transformation returns a CN. A result analogous to Pr. 4 can be derived.
Theorem 5. Consider the same inputs as in Tr. 3. Then:
′

(1)

(m)

P̃ Xn (x0 ) = P (x0 |dXn , . . . , dXn ) ,

(15)

where the lower probability on the left-hand side has been computed by absorption of the single CSE K̃ ′ (Xn ) and the probability on the right-hand side has
been computed in the CN returned by Tr. 3. The same relation also holds for the
corresponding upper probabilities.

7

Conclusions

Credal, or set-valued, modeling of uncertain evidence has been proposed within
the framework of Bayesian networks. Such procedure generalizes standard updating. More importantly, our proposal allows to reduce the task of absorption of
uncertain evidence to standard updating in credal networks. Complexity results,
specific inference schemes, and generalized pooling procedures have been also
derived.
As a future work we intend to evaluate the proposed technique with knowledgebased decision-support systems based on Bayesian network to model unreliable
observational processes. Moreover the proposed procedure should be extended
to the framework of credal networks, thus reconciling the orthogonal viewpoints
considered in this paper and in [13], and tackling the case of non-simultaneous
updating.

A Proofs
Proof of Th. 1. The proof follows from the analogous result with BNs. For any
BN consistent with the CN returned by Tr. 1, we have:
P (x0 , dXn )
P (d )
P Xn
P (x0 |xn )P (dXn |xn )P (xn )
= xn P
.
xn P (dXn |xn )P (xn )

P (x0 |dXn ) =

12

As P (dXn |xn ) reaches its minimum at λxn , for every xn ∈ ΩXn , the minimization
of the last term coincides with that of Eq. (2) and gives P ΛXn (x0 ), the other elements being constant. Analogous reasoning yields P ΛXn (x0 ).
For the proof of Th. 2, we need to introduce the following transformation and
lemma.
Transformation 4. Consider a CSE K ′ (Xn ) in a BN. Let {Pi′(Xn ), i = 1 . . . , nv }
denote the elements of the CS K ′ (Xn ).8 In the BN, compute the marginal PMF
P (Xn ) with standard algorithms. Augment the BN with a binary node DXn , such
that ΠXn := {Xn }. Quantify the local model for DXn as an ECPT K(DXn |Xn ),
specified as a set of nv CPTs {Pi (DXn |Xn ) : i = 1, . . . , nv }. Pi (DXn |Xn ) is
defined as:
P ′ (xn )
Pi (dXn |xn ) ∝ i
,
(16)
P (xn )
for each i = 1, . . . , nv . The same prescriptions provided after Pr. 1 for the case of
zero-probability events should be followed here.
Lemma 1. Given a CSE K ′ (Xn ) in a BN, consider the CN returned by Tr. 4.
Then:
(17)
P (x0 |dXn ) = P ′Xn (x0 ) ,
and analogously for the upper bound.
Proof. DXn is the only credal node in the CN. Thus:
P (x0 |dXn ) =

P (x0 , dXn )
.
P (dXn |Xn )∈K(dXn |Xn ) P (dXn )
min

(18)

Let us rewrite Eq. (18) by: (i) explicitly enumerating the CPTs in the ECPT
K(DXn |Xn ), (ii) making explicit the marginalization of Xn , (iii) exploiting the
fact that, by the Markov condition, we have conditional independence between
DXn and X0 given Xn . The result is:
P
xn P (x0 |xn ) · Pi (d|xn ) · P (xn )
P
min
.
(19)
i=1,...,nv
xn Pi (d|xn ) · P (xn )

Thus, because of Eq. (16):

min

i=1,...,v

P

xn

P (x0 |xn ) · Pi′ (xn )
P
.
′
xn Pi (xn )

(20)

As the denominator in Eq. (20) is one we obtain Eq. (7). This proves the lemma.
8

Remember that in our definition of CS we remove the inner points of the convex hull.

13

We can now prove the second theorem.
Proof of Th. 2. Let us first prove the second part of the theorem. As a consequence of Pr. 1, each VE consistent with the CVE can be converted in a SE
defined as in Eq. (5). The CS implementing the CSE equivalent to the CVE is
therefore:


K ′ (Xn ) :=

P ′ (Xn )

P ′ (xn )= P

P (xn )λxn
xn P (xn )λxn

λxn ≤λxn ≤λxn ∀xn

.

(21)

The computation of P ′ (xn ) is therefore a linearly constrained linear fractional
task. If P (xn ) > 0, we can rewrite the objective function as:
−1
X λx′ P (x′n )
n
 .
P ′(xn ) = 1 +
P
(x
)
λ
n
xn
x′ 6=x


n

(22)

n

As f (α) = (1 + α)−1 is a monotone decreasing function of α, minimizing the
objective function is equivalent to maximize:
X λx′ P (x′n )
n
,
λ
xn P (xn )
′

(23)

xn 6=xn

and vice versa for the maximization. As each λxn can vary in its interval independently of the others, the maximum of the function in Eq. (23) is obtained by
maximizing the numerator and minimizing the denominator, i.e., for λxn = λxn
and λx′n = λx′n . This proves Eq. (10), which remains valid also for P (xn ) = 0.
To prove the first part of the theorem, because of Lm. 1, we only need to prove
that the CN returned by Tr. 4 and the CN returned by Tr. 1 for the CVE specified
in Eq. (9) provides the same P (x0 |xn ). This lower posterior probability in the
second CN rewrites as:
P
xn P (x0 |xn )λxn P (xn )
P
P (x0 |dXn ) = min
.
(24)
λxn ≤λxn ≤λxn
xn λxn P (xn )

Again, this is a linearly constrained linear fractional task, which can be reduced to a linear task by [7]. In the linear task, the minimum is achieved when the
λxn corresponding to the maximum coefficient P (x0 |xn )P (xn ) of the numerator
P ′ (x )
of the objective function takes the minimum value λxn . But as λxn = mini Pi(xnn) ,
we can equivalently obtain this value with the ECPT in the first CN. This proves
the first part of the theorem.

14

Proof of Th. 3. The result follows from the analogous for PK. Thus, let us first
assume K ′ (Xn ) composed of a single PMF P ′ (Xn ). This means that the CSE degenerates into a standard SE. Let λXn denote the corresponding VE and consider
the augmented BN obtained by adding the auxiliary binary child DXn . Also, let
x ∈ ΩXn be any configuration of the joint variable X. By the Markov condition:
P ′ (x|xn ) = P (x|xn , dXn )
P (x|xn )P (xn )P (dXn |xn )
=
P (xn )P (dXn |xn )
= P (x|xn ) .
For a CSE K ′ (Xn ) including more than a PMF, we just repeat the same above
considerations separately for each P ′ (Xn ) ∈ K ′ (Xn ) and obtain the proof of the
statement. Also, by Th. (2) it holds K ′ (x)↓Xn = K ′ (xn ), for all configurations x
consistent with Xn = xn , for all xn ∈ Xn .
Proof of Th. 4. To prove the theorem we show that the non-binary polytreeshaped CN used by [24, Th. 1] to prove the NP-hardness of non-binary credal
polytrees can be used to model UCU in a non-binary polytree-shaped BN. To do
that for an arbitrary k, consider the BN over X := (X0 , X1 , . . . , X2k ) with the
topology in Fig. 1, Nodes (X0 , . . . , Xk=1 ) are associated to binary variables, the
others to ternary variables. A uniform marginal PMF is specified for Xk , while
the CPTs for the other ternary variables are as indicated in Table 2 of the proof
we refer to (the numerical values being irrelevant for the present proof). For the
binary variables we also specify a uniform prior.
We specify indeed a vacuous CSE for each binary variable. These CSEs can be
asborbed by replacing the uniform PMFs with vacuous CSs. The resulting model
is exactly the CN used to reduce CN updating to the PARTITION problem [19]
and hence proves the thesis.

Xk

X0

X1

X2

Xk+1

Xk+2

Xk+3

Xk−1

···

X2k

Figure 1: A polytree-shaped directed acyclic graph.

15

Proof of Th. 5. For any BN consistent with the CN resulting from Tr. 3 it holds
(m)
(1)
PLogOpα,P ′ (x0 ) = P (x0 |dXn , . . . , dXn ), by Prop. 4. By definition, see Eq. (13), we
have:
min

Pj ∈Kj ,Kj ∈K ′

cLogOpα
K ′ (xn )

=k

m
Y

P ′j (xn )αj ,

(25)

j=1

with k being the normalization constant and P ′j (xn ) = minP ∈Kj′ (xn ) P (xn ), for
every j = 1, . . . , m and for all xn ∈ ΩXn .
It follows:
min

P (xn )∈cLogOpα
(xn )
K′

P̃ (x0 ) = k

X
xn

=

P (x0 |xn )

n
Y

P ′j (xn )

j=1

(1)
(m)
P (x0 |dXn , . . . , dXn ) ,

where the second term comes by Eq. (2) and Eq. (25). This gives the proof of the
theorem.

References
[1] Martin Adamčı́k, The information geometry of Bregman divergences and
some applications in multi-expert reasoning, Entropy 16 (2014), no. 12,
6338–6381.
[2] A. Antonucci, C.P. de Campos, M. Zaffalon, and D. Huber, Approximate
credal network updating by linear programming with applications to decision making, International Journal of Approximate Reasoning 58 (2014),
25–38.
[3] A. Antonucci and M. Zaffalon, Decision-theoretic specification of credal
networks: a unified language for uncertain modeling with sets of Bayesian
networks, International Journal of Approximate Reasoning 49 (2008), no. 2,
345–361.
[4] Michael Bacharach, Group decisions in the face of differences of opinion,
Management Science 22 (1975), no. 2, 182–191.
[5] Ali Ben Mrad, Véronique Delcroix, Sylvain Piechowiak, Philip Leicester,
and Mohamed Abid, An explication of uncertain evidence in Bayesian networks: likelihood evidence and probabilistic evidence, Applied Intelligence
43 (2015), no. 4, 802–824.
16

[6] Jean-Marc Bernard, An introduction to the imprecise Dirichlet model for
multinomial data, International Journal of Approximate Reasoning 39
(2005), no. 2-3, 123–150.
[7] Stephen Boyd and Lieven Vandenberghe, Convex optimization, Cambridge
university press, 2004.
[8] L. Campos, J. Huete, and S. Moral, Probability intervals: a tool for
uncertain reasoning, International Journal of Uncertainty, Fuzziness and
Knowledge-Based Systems 2 (1994), no. 2, 167–196.
[9] Hei Chan and Adnan Darwiche, On the revision of probabilistic beliefs using
uncertain evidence, Artificial Intelligence 163 (2005), no. 1, 67–90.
[10] J. Cleland, Orthopaedic clinical examination: An evidence-based approach
for physical therapists, Saunders, 2005.
[11] G. F. Cooper, The computational complexity of probabilistic inference using
Bayesian belief networks, Artificial Intelligence 42 (1990), 393–405.
[12] F. G. Cozman, Credal networks, Artificial Intelligence 120 (2000), 199–233.
[13] J.C.F. da Rocha, A.M. Guimaraes, and C.P. de Campos, Dealing with soft
evidence in credal networks, Proceedings of Conferencia Latino-Americana
de Informatica, 2008.
[14] C. P. de Campos and F. G. Cozman, The inferential complexity of
Bayesian and credal networks, Proceedings of IJCAI ’05 (Edinburgh), 2005,
pp. 1313–1318.
[15] G. De Cooman and M. Zaffalon, Updating beliefs with incomplete observations, Artificial Intelligence 159 (2004), no. 1-2, 75–125.
[16] Persi Diaconis and Sandy L. Zabell, Updating subjective probability, Journal
of the American Statistical Association 77 (1982), no. 380, 822–830.
[17] Didier Dubois, Three scenarios for the revision of epistemic states, Journal
of Logic and Computation 18 (2008), no. 5, 721–738.
[18] Enrico Fagiuoli and Marco Zaffalon, 2U: an exact interval propagation
algorithm for polytrees with binary variables, Artificial Intelligence 106
(1998), 77–107.
[19] Michael R. Garey and David S. Johnson, Computers and intractability: a
guide to the theory of NP-completeness, W. H. Freeman & Co., 1979.
17

[20] Adam J. Grove and J. Y. Halpern, Probability update: conditioning vs. crossentropy, Proceedings of the Thirteenth conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann Publishers Inc., 1997, pp. 208–214.
[21] Richard C Jeffrey, Ethics and the logic of decision, The Journal of Philosophy 62 (1965), no. 19, 528–539.
[22] D. Koller and N. Friedman, Probabilistic graphical models: principles and
techniques, MIT Press, 2009.
[23] Jianbing Ma, Weiru Liu, Didier Dubois, and Henri Prade, Bridging Jeffrey’s
rule, AGM revision and Dempster conditioning in the theory of evidence,
International Journal on Artificial Intelligence Tools 20 (2011), no. 04, 691–
720.
[24] D.D. Mauá, C.P. de Campos, A. Benavoli, and A. Antonucci, Probabilistic
inference in credal networks: new complexity results, Journal of Artificial
Intelligence Research 50 (2014), 603–637.
[25] J. Pearl, Probabilistic reasoning in intelligent systems: networks of plausible
inference, Morgan Kaufmann, San Mateo, California, 1988.
[26] Yun Peng, Shenyong Zhang, and Rong Pan, Bayesian network reasoning
with uncertain evidences, International Journal of Uncertainty, Fuzziness
and Knowledge-Based Systems 18 (2010), no. 05, 539–564.
[27] Irina Rish, An empirical study of the naive Bayes classifier, IJCAI 2001
workshop on empirical methods in Artificial Intelligence, vol. 3, IBM New
York, 2001, pp. 41–46.
[28] Christophe Simon, Philippe Weber, and Eric Levrat, Bayesian networks and
evidence theory to model complex systems reliability, Journal of Computers
2 (2007), no. 1, 33–43.
[29] Rush T Stewart and Ignacio Ojea Quintana, Probabilistic opinion pooling
with imprecise probabilities, Journal of Philosophical Logic (2017), 1–29.
[30] Marco Valtorta, Young-Gyun Kim, and Jiřı́ Vomlel, Soft evidential update
for probabilistic multiagent systems, International Journal of Approximate
Reasoning 29 (2002), no. 1, 71–106.
[31] Carl G. Wagner, Probability kinematics and commutativity, Philosophy of
Science 69 (2002), no. 2, 266–278.

18

[32] Chunlai Zhou, Mingyue Wang, and Biao Qin, Belief-kinematics Jeffrey’s
rules in the theory of evidence, Proceedings of UAI 2014, 2014, pp. 917–
926.

19

