Communications - December 2010

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.