Challenge: What is the Impact of Bayesian Networks on Learning?

1 Introduction

A Bayesian network is a graphical representation of the joint probability distribution for a set of variables. The representation was originally designed to encode the uncertain knowledge of an expert [Wright , 1921;

David Heckerman Microsoft Research One Microsoft Way Redmond, WA 98052

Stuart Russell Computer Science Div. University of California Berkeley, CA 94720

Howard and Matheson, 1981 ; Pearl , 1988], and indeed today, they play a crucial role in modern expert sys­ tems, diagnosis engines, and decision support systems [Heckerman et a!., 1995]. They also have become the representation of choice among researchers interested in uncertainty in AI. One often-cited merit of Bayesian networks is that they have formal probabilistic seman­ tics and yet can serve as a natural mirror of knowl­ edge structures in the human mind [Spirtes et al. , 1993; Heckerman eta!. , 1995; Pearl, 1995] . This facilitates the encoding and interpretation of knowledge in terms of a probability distribution, enabling inference and optimal decision making.

A Bayesian network consists of two components. The first is a directed acyclic graph in which each vertex cor­ responds to a random variable. This graph represents a set of conditional independence properties of the rep­ resented distribution: each variable is probabilistically independent of its non-descendants in the graph given the state of its parents. This graph captures the qualita­ tive structure of the probability distribution, and is ex­ ploited for efficient inference and decision making. Thus, while Bayesian networks can represent arbitrary proba­ bility distributions, they provide computational advan­ tage for those distributions that can be represented with a simple structure. The second component is a collection of local interaction models that describe the conditional probability p(X;IPa.) of each variable X; given its par­ ents Pa; (see Figure 1) . Together, these two components represent a unique joint probability distribution over the complete set of variables X [Pearl, 1988]. The joint dis­ tribution is given by the following equation:

It can be shown that this equation implies the condi­ tional independence semantics of the graphical structure given earlier.

Equation 1 shows that the joint distribution speci­ fied by a Bayesian network has a factored representation as the product of individual local interaction models. Sparse Bayesian networks therefore correspond to con­ cise representations of joint distributions. If the num­ ber of parents of any variable is bounded by a constant k, then (for most reasonable representations of the lo­ cal interaction models , including all discrete models) the Bayesian network requires a number of parameters that is linear in the number of variables, instead of exponen­ tial for an unstructured representation. This observation is , of course, directly relevant to the learning problem, since concise parameterizations lead to statistically ef­ ficient !earning-provided that the problem domain ad­ mits of a sparse structure of conditional dependencies. The latter assumption is of course directly related to the usefulness of Bayesian networks as models of human knowledge structures.

The characterization given by Equation 1 is a strictly mathematical characterization in terms of probabilities and conditional independence statements. An informal connection can be made between this characterization and the intuitive notion of direct causal influence. It has been noted that if the edges in the network structure cor­ respond to causal relationships, where a variable's par­ ents represent the direct causal influences on that vari­ able, then resulting networks are often very concise and accurate descriptions of the domain. Thus it appears that in many practical situations, a Bayesian network provides a natural way to encode causal information. We can state this more precisely as the Causal Markov As­ sumption (CMA): if a network is constructed simply by connecting variables to other variables that they directly causally influence, then the resulting network interpreted according to Equation 1 will correctly reflect the condi­ tional independence statements that hold in the domain.

The naturalness of using causal information directly in constructing formally characterizable knowledge struc­ tures has made it possible to encode the knowledge of many experts. As a result, Bayesian networks have been incorporated into many expert systems, diagno­ sis engines, and decision-support systems [Heckerman et a!. , 1995]. Nonetheless, it is often difficult and time­ consuming to construct Bayesian networks from expert knowledge alone.

This observation, together with the fact that data is becoming increasingly available and cheaper to acquire has led to a growing interest in using data to learn both the structure and probabilities of a Bayesian network. Several groups have worked on learning structure from scratch [Spirtes eta!. , 1993; Pearl , 1995; Friedman eta!. , 1997] or with weak constraints such as variable order­ ing [Cooper and Herskovits, 1992, for example], while others have worked on learning structure by refining an initial model [Heckerman et a!., 1994]. Learning proba­ bilities, which is non-trivial when the network contains hidden variables or the data set has missing values , can be done by a variety of methods including EM [Lau­ ritzen, 1991; Lauritzen, 1995; Spiegelhalter et a!., 1993; Olesen et a!., 1992; Spiegelhalter and Cowell, 1992; Heckerman, 1996] gradient-based methods [Laskey, 1990; Golmard and Mallet , 1991; Neal, 1992; Russell et a!., 1995], and Monte-Carlo techniques [Neal, 1993] .

These researchers have cited several benefits of using the Bayesian-network representation, with its causal in­ terpretation, as a tool for learning:

1. Incorporation of prior knowledge. Bayesian net­ works facilitate the translation of human knowledge into probabilistic form, making it suitable for refine­ ment by data.
2. Validation and insight. In many cases, a learned Bayesian network can be given a causal interpre­ tation. Consequently, a Bayesian network is more easiiy understood than "black box" representations such as neural networks . As an immediate byprod­ uct, people will more readily accept the recommen­ dations of a Bayesian network than those of a model justified only by its raw predictive performance. In addition, users are more likely to gain insights from Bayesian networks.
3. Learning causal interactions. Unlike purely proba­ bilistic relationships, causal relationships allow us to make predictions given direct interventions or manipulations of the world. Therefore, by learning with Bayesian networks, there is a hope that we can make better predictions in the face of intervention. Learning causal relationships is crucial in scientific discovery, where interventional studies are often ex­ pensive or impossible. Similarly, the ability to learn

causal relationships is crucial for intelligent agents that must act in their environment on the basis of acquired knowledge.

Other benefits of using Bayesian networks for learning are derived from their probabilistic semantics. Because sophisticated yet efficient methods have been developed for using a Bayesian network to answer probabilistic queries, they can be used both for predictive inference and diagnostic (or abductive) inference. This is in con­ trast to standard regression and classification methods (e.g., feed forward neural networks and decision trees) that encode only the probability distribution of a tar­ get variable given several input variables. Whereas the Bayesian-network representation can describe the casual ordering in the domain, there are no restrictions as to the directions of the queries. Thus, there is no inher­ ent notion of inputs and outputs of the network. This property also allows Bayesian networks to reason effi­ ciently with missing values, by computing the marginal probability of the query given the observed values . One other cited benefit of the Bayesian-network representa­ tion, which derives from its probabilistic nature, is that it can be used to determine optimal decisions.

Even though these claims are compelling, it is yet to be demonstrated that these issues provide tangible advantages in applications. The purpose of this paper is therefore to challenge researchers to characterize and quantify these claims, including the specification of do­ mains where they made a difference in the efficiency of learning (e.g., through the use of prior knowledge) , in the quality of the resulting model (e.g., a new causal theory that is accepted by the experts), or in the deployment the system (e.g., through combination with utility esti­ mation).

We hope that this challenge will focus the research community on a high-impact research agenda. We be­ lieve that in order to meet the challenge, at least three kinds of activities will take place:

1. We believe that experience in applications provide valuable lessons. Thus, we are interested in "suc­ cess stories," that is papers that describe applica­ tions where learning Bayesian networks has led to significant advantages over other methods. These papers should attempt to distill the characteristics of the problem that made Bayesian networks the preferred solution.
2. We propose a series of "bake-offs" to experimen­ tally evaluate how Bayesian networks and alterna­ tive approaches can exploit prior knowledge, deal with missing data, and learn causal models. These bake-offs will allow for controlled study and evalua­ tion of the impact of the various alternatives. Sec­ tion 2 describes our proposal for organizing these

bake-offs and evaluating the results.

1. We identify specific technical research problems whose solution is, in our view, crucial for meeting the challenge. In Section 3, we outline these prob­ lems.

For a comprehensive assessment of the state of the art of the field, we refer the reader to Heckerman [1996] as well as the papers cited earlier .

2 Experimental Bake-Offs

As mentioned in the introduction, we propose a series of bake-off competitions with the objective to evaluate the extent to which the special features of Bayesian networks benefit the learning task and the resulting models. To this end, we will maintain a web site, where data sets , background information about them, and evaluation cri­ terion will be made available.

We are currently assembling several collections of data sets, both syntactic and real, for the bake-offs described below. In order to preserve the validity of these experi­ ments, some of them will be done using "blind" evalua­ tion. That is, participants In the bake-off will have access to a portion of the training data and will have to regis­ ter the learned models by a certain date. The learned models will be tested on unseen data by the central web server. 1

Our hope is that these data sets will provide appro­ priate test beds for testing theories and new algorithms. We encourage practitioners and researchers interested in other induction methods to participate in these bake-offs and to use these datasets. 2

The exact evaluation criteria will be decided based on inputs from participants and the discussions that will follow the presentation of this challenge. These crite­ ria will include various error measures such as log-loss , cross-entropy or KL distance, and classification accuracy, and will depend on the different learning strategies (e.g. , batch learning and incremental learning).

We propose to focus these bake-offs on three issues : in­ corporation of background knowledge, handling of miss­ ing data, and learning causal interactions.

Background knowledge. The main problem with ex­ periments testing the influence of background knowledge in the learning process is to make the expertise read­ ily available to all participants in a way that does not provide advantages to any particular learning method .

1 This stricture is intended to get around the irresistible tendency, noted during the Statlog project, for researchers to "peek" at test data and report "best" results selected from runs with different knob settings.

2 Toward this end, we plan to submit these data sets to both the UCI machine learning repository and the XXX repository at Toronto.

(A similar problem has arisen with experimental studies of inductive logic programming methods; we expect to compare notes.) We are considering two strategies . The first one is to provide summary of background expert knowledge in the form of free-form text and tables. The second strategy is to provide data about a domain famil­ iar enough that anybody can be regarded as an expert, and define a prediction task in that domain. One such domain is that of TV shows. Data could be provided about shows, viewers characteristics etc. , and the task would be to predict the shows that new subjects will like based on other shows they like.

Missing data. The basic problem of coping with miss­ ing values and hidden variables in the data set is ad­ dressed very simply in Bayesian networks, because like­ lihoods can be computed no matter what subset of vari­ ables are available as evidence. The tricky problem arises when the data is missing due to specific values that other variables take. In this case, the failure to observe a vari­ able may in itself be informative about the true state of the world [Rubin , 1978]. In principle, a successful in­ duction algorithm would be able to take advantage of a good modeL about the relationship between the state of the world and what variables are missing.

For this challenge we will provide both synthetic data and real-life data. The former allows controlled exper­ iments that account for the number of missing values and the dependence of omissions on the true state of the world . We also plan to provide data sets where the target task involves a large amount of incomplete information.

Causal interactions. In this study, we will attempt to learn cause and effect from observational studies. Ide­ ally, we will also have interventional data to verify the real causal structure of the domain. We are currently in­ vestigating data sets in social sciences and epidemiology; the University of Michigan survey data archive contains thousands of data sets, some running into the gigabytes , that might be very suitable. We will also try to pro­ vide synthetic data as follows . We will contact experts that will provide us with causal models for their domain (e.g. , epidemiology), from which we will create synthetic data. Since prior knowledge plays a significant role in the induction of causal theories, these experts would also provide summary of the prior knowledge they consider reasonable for the domain they created (e.g., known tem­ poral ordering relations and possible latent causes).

We plan to evaluate the learned causal models as fol­ lows. First , we will measure how well they predict the effects of interventions (using standard statistical mea­ sures). Second, we will measure how many causal inter­ actions were correctly and incorrectly identified.

3 Technical Challenges

Many researchers are now concentrating on learning in more expressive probabilistic models , including hybrid (discrete and continuous) models [Lauritzen and Wer­ muth, 1989], mixed (undirected and directed) models [Buntine, 1994; Cooper, 1995; Spirtes et a!., 1995], dy­ namic Bayesian network models representing stochastic processes [Russell et a!., 1995], and stochastic gram­ mars [Stolcke and Omohundro, 1993] . Another impor­ tant problem is the specification of prior distributions over parameters- most current work makes strong as­ sumptions such as parameter independence and likeli­ hood equivalence. MacKay [1992] and others are work­ ing on hierarchical models that relax the assumption of parameter independence. A third area of active re­ search is the development of efficient approximation al­ gorithms for probabilistic inference-a key component of learning-including Monte-Carlo [Thomas et a!., 1992] and variational methods [Saul et a!., 1996] .

There are two technical challenges that we believe are critical to the success of Bayesian networks and for which much work needs to be done. One challenge is the efficient handling of incomplete data. One impor­ tant subcomponent of the first task is the creation of search methods for Bayesian networks with hidden vari­ ables. Clever search strategies are needed to constrain the infinite search space. In addition, as mentioned in the previous section, learning with incomplete data is particularly difficult when the mere failure to observe some variable is informative about the true state of the world. For example, the fact that a patient drops out of a drug study may suggest that the he or she could not tolerate the effects of the drug. Several researchers have developed basic principles and methods for dealing with such situations, including Rubin [1978], Robins [1986], Cooper [1995], Spirtes et a!. [1995], and Chickering and Pearl [1996], but more work needs to be done to connect these basic principles with graphical models and to make these methods more efficient .

A second challenge is the creation of simple but ex­ pressive probability distributions for the local interaction models in a Bayesian network . Most work on learning with Bayesian networks concentrates on discrete vari­ ables where each variable is associated with a set of multinomial distributions, one distribution for each con­ figuration of its parents. Thiesson [1995] discusses a class of local likelihoods for discrete variables that use fewer parameters. Geiger and Heckerman [1994] and Buntine [1994] discuss simple linear local likelihoods for continu­ ous variables that have continuous and discrete variables. Bun tine [1994] also discusses a general class of local likeli­ hoods from the exponential family. Nonetheless , alterna­ tive likelihoods for discrete and continuous variables are desired. Local likelihoods with fewer parameters might allow for the selection of correct models with less data as demonstrated empirically by Friedman and Goldszmidt [1996] . In addition, local likelihoods that express more accurately the data generating process would allow for easier interpretation of the resulting models.

4 Concluding Remarks

There are of course a number of other promising re­ search avenues, challenges, and needs that directly con­ cern learning Bayesian networks and their impact on real world applications for data analysis, pattern recogni­ tion and classification, knowledge discovery, and others. There is for example the belief that Bayesian networks will play a significant role in issues of feature engineering, selection and abstraction; as well as in the formulation of the learning problem and the various tradeoff evaluations of knowledge representation versus quality of prediction of the induced models. Our particular choice of prob­ lems and challenges were based not only on immediate relevance, but more important , on the fact that progress can be accomplished in the next two years.

Needless to say, our hope is that researchers and prac­ titioners of all induction methods will participate in our challenge so that a fair comparison can be made and true scientific knowledge can be distilled.

Acknowledgments

The participation of Nir Friedman and Stuart Russell was funded by ARO through MURI DAAH04-96-1-0341, and by NSF through FD96-34215.