Bayesian Networks

Bayesian Networks

Consider a task in which a decision maker learns from cue profiles and uses them to compare objects. If training and test data coincide, memorizing the training profiles can exploit information about the very cases being tested. With separate test data, the model must generalize to new cases. Possibilities include regression, a Bayesian network, Bayesian CART, or a combination of a network and CART.

The task is to infer which of two objects A or B scores higher on a criterion, based on the values of a set of binary cues. Assume, furthermore, that the decision maker has nine cues at her disposal and she has full knowledge of the values these cues take on A and B. To work out a concrete example, let A and B have the cue profiles (100101010) and (011000011) respectively. The Bayesian asks herself: What is the probability that an object with cue profile (100101010) scores higher than an object with cue profile (011000011) on the established criterion? The probability of interest is whether A scores higher than B, given both cue profiles.

A network for our type of task considers pairs of objects (A,B) and the possible states of the cues, which are the four pairs of binary values (0,0), (0,1), (1,0), (1,1) on pairs of objects. A simple model treats the cues as conditionally independent given the outcome being predicted. This is known here as Idiot Bayes, or naive Bayes. It combines cue likelihoods under that assumption to estimate the outcome probabilities. Forced to a deterministic answer, Idiot Bayes will predict that A scores higher than B on the criterion if the probability of A > B computed in terms of this product is larger than the probability of B > A. Due to its simplicity, Idiot Bayes is sometimes used as a crude estimate of probability distributions. The independence assumption may be inaccurate, although a simple model can still predict well.

At the other extreme is a fully connected directed acyclic network: every pair of nodes has a single directed connection, with the directions following an ordering that prevents cycles. Computing the comparison probability with this network when training and test set coincide amounts to using the Profile Memorization Method. Neither extreme is guaranteed to perform best on separate test data. A network can instead concentrate on conditional dependencies that matter for prediction. Some may be so weak that it is convenient to neglect them in order to avoid overfitting. The Bayesian needs a Bayesian strategy to decide which are the relevant links that should remain and also to prune all the irrelevant ones. She needs a strategy to search through the possible networks and evaluate each network in terms of its performance. Bayesian techniques for performing this type of search in a smart and efficient way have been developed both in statistics and artificial intelligence. These methods are efficient in learning both structure and parameters. Nir Friedman and Leo Goldszmit (1996), for instance, have devised software for searching over networks and finding a good fit for a given set of data in a classification task. Because our task is basically a classification task (we are determining whether a pair of objects is rightly ordered), we are able to make use of Friedman and Goldszmit’s network. A complex network can make inference expensive. The following theorem simplifies the calculation of a node’s conditional probability given the states of all other nodes. In a Bayesian network, the nodes with arrows pointing to a fixed node are called the parents of that node. The node itself is called a child of its parents. What follows is a fundamental rule for operating with Bayesian networks.

THEOREM The conditional probability of a node j being in a certain state given knowledge on the state of all other nodes in the network is proportional to the product of the conditional probability of the node given its parents times the conditional probability of each of its children given its parents.

The product is normalized by a constant K. A node’s Markov Blanket consists of its parents, its children and the other parents of its children. Given their states, the node is conditionally independent of all remaining nodes. The blanket therefore determines its conditional probability distribution, rather than fixing its actual state.

This local calculation follows from the network’s factorization and Bayes’ rule. It can reduce the work needed to compute the specified conditional distribution. It is precisely due to this type of reduction of computational complexity that Bayesian networks have become a popular tool both in statistics and in artificial intelligence since the 1980s.

Figure 31.2 shows the Bayesian network obtained with Friedman’s search method for the task of comparing German cities according to their population, as in Gigerenzer and Goldstein (1996). In that paper, the reference class of the 83 German cities with more than 100,000 inhabitants was analyzed. The Bayesian network reveals that two of the nine cues, LP and WG, are irrelevant when the other seven cues are known. Figure 31.2 illustrates the Markov Blanket of the node size, which represents the hypothesis, “City A has more inhabitants than city B” and obviously can be in two states (the other state is “City B has more inhabitants than city A”). The same conditional-probability rule applies, with K as a normalizing constant. To estimate the required conditional probabilities, the program produces simple decision trees (actually CARTs), as illustrated in Fig. 31.3 for Prob(size | SO, EX, SC). The program searches among all possible trees for the one that best fits the data, pruning all irrelevant branches. That is, this approach combines a Bayesian network with a CART step at the end. CART models were popularized in the statistical community by the seminal book by Breiman, Friedman, Olshen, and Stone (1984).

Learning and evaluating the combined network-and-CART model can require substantially more computation than a simple heuristic such as Take the Best. The cost depends on the search procedure and network structure.

How much more accurate is such a computationally complex Bayesian network than the simple Take the Best? Table 31.7 reports performance for the Bayesian network and the Profile Memorization Method when training and test data coincide. The table itself is not included here. Performance was tested in four environments: 1. Which of two German cities has the higher population? 2. Which of two U.S. cities has a higher homelessness rate? 3. Which of two individual Arctic female charr fish produces more eggs? 4. Which of two professors at a Midwestern college has a higher salary?