of the two fans given that the system is
unavailable? What single component
can be replaced to increase the overall system reliability by 5%? Consider
Figure 7: What is the most likely channel input that would yield the channel
output 1001100? These are example
questions that would be of interest in
these application domains, and they
are questions that can be answered
systematically using three canonical
Bayesian network queries. 8 A main
benefit of using Bayesian networks in
these application areas is the ability to
capitalize on existing algorithms for
these queries, instead of having to invent a corresponding specialized algorithm for each application area.
Probability of Evidence. This query
computes the probability Pr(e), where
e is an assignment of values to some
variables E in the Bayesian network—
e is called a variable instantiation or
evidence in this case. For example, in
Figure 3, we can compute the probability that an individual will come out
positive on both tests using the probability-of-evidence query Pr( T1 = +ve, T2
= +ve). We can also use the same query
to compute the overall reliability of the
system in Figure 5, Pr(S = avail). The
decision version of this query is known
to be PP-complete. It is also related to
another common query, which asks
for computing the probability Pr(x|e)
for each network variable X and each
of its values x. This is known as the
node marginals query.
Most Probable Explanation (MPE).
Given an instantiation e of some variables E in the Bayesian network, this
query identifies the instantiation q
of variables Q = E that maximizes the
probability Pr (q|e). In Figure 3, we
can use an MPE query to find the most
likely group, dissected by sex and condition, that will yield negative results
for both tests, by taking the evidence e
to be T1 = –ve; T2 = –ve and Q = {S, C}. We
can also use an MPE query to restore images as shown in Figures 8 and 9. Here,
we take the evidence e to be Cij = true
for all i, j and Q to include Pi for all i. The
decision version of MPE is known to
be NP-complete and is therefore easier
than the probability-of-evidence query
under standard assumptions of complexity theory.
Maximum a Posteriori Hypothesis
(MAP). Given an instantiation e of some
figure 10. an arithmetic circuit for the Bayesian network B ← A → C. inputs labeled
with θ variables correspond to network parameters, while those labeled with λ variables
capture evidence.
Probability-of-evidence, node-marginals, and mPE queries can all be
answered using linear-time traversal
algorithms of the arithmetic circuit.
+
*
*
λa
θa
λā
θā
+
+
+
+
*
*
*
*
*
*
*
*
θb|a
λb θb|ā
θ ¯ b|a
λ ¯ b θ¯ b|ā
λc θc|a
θc|ā θ¯ c|a
λ¯ c
θ¯ c|ā
figure 11. Two networks that represent the same set of conditional independencies.
Earthquake?
(E)
Burglary?
(B)
Earthquake?
(E)
Burglary?
(B)
radio?
(R)
Alarm?
(A)
radio?
(R)
Alarm?
(A)
Call?
(C)
Call?
(C)
(a)
(b)
figure 12. Extending Bayesian networks to account for interventions.
Earthquake?
(E)
radio?
(R)
Alarm?
(A)
Burglary?
(B)
Tampering
(T)
Earthquake?
(E)
radio?
(R)
Alarm?
(A)
Burglary?
(B)
Tampering
(T)
Call?
(C)
Call?
(C)
(a)