Korb K.B., Nicholson A.E. Bayesian Artificial Intelligence

Подождите немного. Документ загружается.

FIGURE 11.7

BN for airport data: (a) CaMML; (b) TETRAD II without prior information; (c)

TETRAD II with prior temporal ordering; (d) expert elicitation.

11.4.4.2 Predictive accuracy of the BOM rule-based system

The BOM had estimated that the predictive accuracy of their rule-based system (RB)

was around 67 %, but more detailed statistics were unavailable. Our test results were

roughly consistent with this. In our testing, we assumed that the prevailing gradient

wind pattern would stay constant for the period of the test, which is an approximation

whose accuracy declines with the lookahead time.

Weather balloons providing usable data were generally launched from Sydney

airport twice a day, at approximately 5am and 11pm. Predictions were made with a

lookahead time in increments of three hours. Predictions were generated for each of

the AWS sites. The mean accuracy of coastal and inland seabreezes over the different

AWS sites is reported in Figure 11.8 (for 5am based predictionsonly; the 11pm based

predictions are similar). A more interesting and difﬁcult task than predicting the

mere existence of seabreezes is the prediction of wind direction, which is reported

every 30 minutes by the AWS. The RB system was easily adapted to this task and

the results are again in Figure 11.8, reported as coastal and inland wind direction

0 5 10 15 20 25 30

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

BOM RB system using 5am readings

forecast lookahead

predictive accuracy

sea breeze (coastal)

wind direction (coastal)

sea breeze (inland)

wind direction (inland)

FIGURE 11.8

Comparison of RB predictive accuracy for all sites using 5am readings across looka-

head times (in hours).

average accuracies.

As might be expected, the predictive accuracy of the system varied in a rough

sine pattern, with a maximum reached at about 4pm, at an accuracy of 80%. Wind

direction accuracy was 10 to 20% lower. When comparing the geographic location

of individual AWS sites with the predictive accuracy, we can see that sites on the

coastline outperform those inland. Presumably, a seabreeze on the coast would not

always be of sufﬁcient strength to penetrate inland, making prediction harder.

11.4.4.3 Predictive accuracy of the Bayesian networks

We tested four Bayesian networks for predictive accuracy (see Figure 11.7), one

discovered by MML, two by TETRAD II and one elicited from experts. The wind

direction predictive accuracy results for these four BNs, together with the BOM RB

system, are given in Figure 11.9. It is clear that, with the exception of the earliest

3 hour prediction, the differences between the BNs are not statistically signiﬁcant,

while the simple BOM RB system is clearly underperforming all of the Bayesian

networks.

In general, the Bayesian network predictive performance was maximal (up to 80%

accuracy) at lookahead times which were multiples of 12 hours, correspondingto late

afternoon or early morning. Clearly, there is a strong periodicity to this prediction

problem. In the future, such periodicity could be explicitly incorporated into models

using MML techniques (e.g., in selecting parameters for a sine function). The pre-

dictive differences between BN models appear not to be interesting here. The real

0 10 20 30 40 50 60

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

forecast time (hours)

predictive accuracy

CaMML

TETRAD−a

TETRAD−b

Expert

BoM−RB

FIGURE 11.9

Wind direction predictive accuracy for airport-type networks.

differences were in usability. The expert network took considerable effort to elicit

and build; while TETRAD II either required additional prior information (temporal

constraints) or else hand-made posterior edits in comparison with CaMML.

11.4.4.4 Incremental parameter learning

The training method examined thus far has the drawback that both the structure of the

model and its parameters are learned in batch mode, with predictions generated from

a ﬁxed, fully speciﬁed model. Since weather systems change over time, we thought

a better approach might be to learn the causal structure in batch mode with 1997

data, but to reparameterize the Bayesian network incrementally using 1998 data,

applying fading (see

9.4.1) through a time decay factor so as to favor more recent

over older data. The (unnormalized) weight applied to data for incremental updating

of the network parameters was optimized by a greedy search, which resulted in a

weight applied of

where is the number of sample cases since the data were

measured. This is an example of adaptation (see

9.4).

Figure 11.10 shows the average performance of the MML Bayesian networks

when incrementally reparameterized. The improvement in predictive accuracy for

the AWS and Olympic data sets is statistically signiﬁcant at the 0.05 level, despite

the fact that the average scores reported here are themselves presumably suboptimal,

since the predictions made early in the year use parameters estimated from small

data sets. Incremental reparameterization in those two cases has also had the curious

effect of smoothing out the sine wave variation in predictive performance.

0 5 10 15 20 25 30 35 40

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

forecast time (hours)

predictive accuracy

AWS−inc

Olympic−inc

Airport−inc

AWS−norm

Olympic−norm

Airport−norm

FIGURE 11.10

Comparison of incremental and normal training methods for MML networks.

11.4.5 KEBN aspects

In this seabreeze study we combined a number of KEBN activities. We compared

elicited with discovered causal models of seabreezes. We used a large weather data

base for automated structure and parameter learning and also for evaluating the

learned and elicited Bayesian networks. We also employed parameter adaptation,

using fading to get parameters to track changes in weather patterns.

The seabreeze study provides a useful example of the application of Bayesian

network technology in data mining problems. There are two basic approaches to

deploying Bayesian networks, namely eliciting Bayesian networks from domain ex-

perts and using machine learning programs to learn them from data. The initial

rule-based predictive system, built in-house by BOM, was shown to be inferior to

all of the Bayesian networks developed in this study. The Bayesian network elicited

from the domain experts performed on a par with those generated automatically by

data mining. Nevertheless, data mining with Bayesian networks shows itself to be a

very promising alternative, performing as well as the elicited network and so offering

a good alternative for similar problems where human expertise is unavailable. Fur-

thermore, the adaptive parameterization outperformed the static Bayesian networks

however they were generated and provides one model for combining elicitation with

automated learning.

11.5 Summary

The three case studies demonstrate most of the main knowledge engineering features

presented in the previous two chapters. The poker case study illustrates the spiral

model of prototype development. All the poker structures were hand-crafted, and

their evaluation was based in experimental use against both automated and human

opponents. In the ITS case study both the structure and parameters were initially

elicited from experts, with automated methods used to validate aspects of the model,

using data that was only available for the DCT part of the system. Much more

data was available for the ﬁnal seabreeze prediction case study, which allowed both

parameter and structure learning to be performed, as well as parameter adaptation.

Consequently, the domain experts had a smaller role in this case study, compared to

the ﬁrst two, and evaluation consisted only of validation methods based on the data.

Our experiences in these, and other, projects were useful in the development of our

ideas for the KEBN process presented in this text. KEBN, in turn, should feed into

our future Bayesian network projects, resulting in better focused application efforts.

Appendix A

Notation

This appendix provides a list of notational symbols and acronyms, together with page

numbers where they are deﬁned or ﬁrst used.

degree of increased belief p. 5

degree of increased disbelief p. 5

certainty factor p. 5

is independent of p. 7

is independent of given p. 7

th state of variable p. 9

state space of variable p. 9

is dependent upon given p. 41

normalizing constant p. 54

likelihood p. 54

parameter in message-passing algorithm p. 57

message sent from parent to child p. 58

message sent from child to parent p. 58

evidence connected to p. 58

an instantiation of p. 58

estimated distribution p. 72

assignment (used in algorithms) p. 73

measure of conﬂict between evidence p. 78

returns the that gives maximum p. 103

node for variable at the th time-slice p. 105

evidence nodes from ﬁrst to th time-slice p. 107

predicted belief for p. 109

linear coefﬁcient for p. 155

mean of p. 155

standard deviation of p. 155

path coefﬁcient for p. 155

sample correlation between and p. 156

active path p. 157

valuation of an active path p. 157

parameterization of model p. 165

partial correlation between X and Y, S ﬁxed p. 167

sample covariance between and p. 171

sample standard deviation of p. 171

sample partial correlation p. 171

Dirichlet distribution with parameters p. 179

the vector p. 179

parent set of p. 198

instantiations of parent set of p. 199

number of matching sample cases p. 199

entropy of p. 204

mutual information between and p. 204

an instantiation of p. 204

Normal (Gaussian) distribution p. 210

the distribution p. 218

Good’s information reward p. 280

Bayesian information reward p. 282

Acronyms

BN Bayesian network p. 29

CPT conditional probability table p. 32

I-map Independence-map p. 33

D-map Dependence-map p. 33

LS logic sampling p. 72

LW likelihood weighting p. 74

KL Kullback-Leibler divergence p. 76

MPE most probable explanation p. 78

EU expected utility p. 104

EB expected beneﬁt p. 104

DBN dynamic Bayesian network p. 104

DDN dynamic decision network p. 110

BPP Bayesian poker player p. 124

EW expected winnings p. 127

NAG Nice Argument Generator p. 127

EM expectation maximization p. 185

MML minimum message length p. 201

MDL minimum description length p. 201

TOM totally ordered model p. 209

GA genetic algorithm p. 211

KEBN Knowledge Engineering with Bayesian Networks p. 225

VE the Verbal Elicitor software package p. 243

QPN qualitative probabilistic networks p. 250

OOBN object-oriented Bayesian networks p. 250

ITS intelligent tutoring system p. 290

BOM Bureau of Meteorology p. 305

AWS automatic weather station p. 306

Appendix B

Software Packages

B.1 Introduction

The rapid development of Bayesian network research over the past 15 years has been

accompanied by a proliferation of BN software tools. These tools have been built to

support both these research efforts and the applications of BNs to an ever-widening

range of domains. This appendix is intended as a resource guide to those software

tools.

We incorporate Kevin Murphy’s listing of software packages for Bayesian net-

works and graphical models (

B.3), which has been built up and maintained over a

number of years

. We also note other Web sites for BN software and other resources.

Next, we describe some of the major software packages — those with the most

functionality, or with a particular feature of interest — in more detail. Most of these

packages have a long list of features that we cannot even list here, so our survey is by

no means exhaustive. We endeavor to point out particular features that relate to issues

we have raised earlier in this text. Note that we have personal experience, through

teaching, research projects or application development, with the following software:

BNT, BUGS, CABeN, CaMML, Hugin, IDEAL, Netica, SMILE and TETRAD II.

In general, all the packages with GUIs include the advanced GUI features (e.g.,

menu options, short-cut icons, drag-and-drop, online help) that have become the

norm in recent years. In this resource review, we will generally ignore GUI aspects,

unless there is some feature that stands out. Instead, we will concentrate on aspects

of the functionality.

We make no attempt to give any sort of ranking of these packages; so our survey

presents the packages alphabetically. The Murphy listing notes whether the products

are free or commercial but available in a restricted form. Otherwise we do not make

any comments on the cost of commercial products.

Our thanks to Kevin Murphy for giving us permission to use this listing.

B.2 History

The development of the ﬁrst BN software, beyond algorithm implementation, oc-

curred concurrently with the surge of BN research in the late 1980s. Hugin [6] was

developed at the University of Aalborg in Denmark (see

B.4.5 below) and went on

to become a commercial product now widely used. The Lisp-base IDEAL (Inﬂuence

Diagram Evaluation and Analysis in Lisp) test-bed environment was developed at

Rockwell [266]

Another early BN inference engine was CABeN (a Collection of Algorithms for

Belief Networks) [58], which contains a library of routines for different stochastic

simulation inference algorithms. Lumina Decision Systems, Inc., was founded in

1991 by Max Henrion and Brian Arnold, which produce Analytica. The development

of Netica, now produced by Norsys Ltd, was started in 1992.

B.3 Murphy’s Software Package Survey

http://www.ai.mit.edu/˜murphyk/Software/BNT/bnsoft.html

This survey is given in Tables B.1, B.2 and B.3. The ﬁrst two tables gives the soft-

ware package name, its producers and where it is available online. If the software is

commercial but the company has links with particular institutions or BN researchers,

those are also noted. Table B.3 covers basic feature information such as technical

information about source availability, platforms, GUI and API, very high level func-

tionality such as types of nodes supported (i.e., discrete and/or continuous), whether

decision networks are supported, whether undirected graphs are supported. It in-

cludes whether the software allows learning (parameters and/or structure), describes

the main inference algorithms (if this information is available) and indicates whether

the software is free or commercial. The details of the meaning of each column are

given in Figure B.1.

Google’s list of tools is available at:

http://directory.google.com/Top/Computers/Artificial

Intelligence/Belief Networks/Software/

The Bayesian Network Repository contains examples of BNs, plus datasets for learn-

ing them:

http://www.cs.huji.ac.il/labs/compbio/Repository/

One of the authors used it for her Ph.D. research.

Src Is the source code included? N=no. If yes, what language? J =Java,M = Matlab,

L =Lisp,C, C++, R, A =APL.

API Is an application program interface included?

N means the program cannot be integrated into your code, i.e., it must be run as

a standalone executable. Y means it can be integrated.

Exec The executable runs on: W = Windows (95/98/2000/NT), U = Unix, M = Mac-

Intosh, - = Any machine with a compiler.

GUI Is a Graphical User Interface included? Y=Yes,N=No.

D/C Are continuous-valued nodes supported (as well as discrete)? G = (condition-

ally) Gaussians nodes supported analytically, Cs = continuous nodes supported

by sampling, Cd = continuous nodes supported by discretization, Cx = con-

tinuous nodes supported by some unspeciﬁed method, D = only discrete nodes

supported.

DN Are decision networks/inﬂuence diagrams supported? Y=Yes,N=No.

Params Does the software functionality include parameter learning? Y=Yes,N=No.

Struct Does the software functionality include structure learning? Y=Yes,N=No.

CI means Y, using conditional independency tests (see

6.3)

K2 means Y, using Cooper & Herskovits’ K2 algorithm (see

8.2)

D/U What kind of graphs are supported? U = only undirected graphs, D = only

directed graphs, UD = both undirected and directed, CG = chain graphs (mixed

directed/undirected).

Inf Which inference algorithm is used? (See Chapter 3)

JT = Junction Tree, VE = variable (bucket) elimination, PT = Pearl’s poly-

tree, E = Exact inference (unspeciﬁed), MH = Metropolis Hastings, MC =

Markov chain Monte Carlo (MCMC), GS = Gibbs sampling, IS = Impor-

tance sampling, S = Sampling, O = Other (usually special purpose), ++ =

Many methods provided, ? = Not speciﬁed, N = None, the program is only

designed for structure learning from completely observed data.

NB: Some packages support a form of sampling (e.g., likelihood weighting,

MDMC), in addition to their exact algorithm; this is indicated by (+S).

Free Is a free version available? O=Free (though possibly only for academic use), $

= Commercial (although most have free versions which are restricted in various

ways, e.g., the model size is limited, or models cannot be saved, or there is no

API.)

FIGURE B.1

Description of features used in Murphy’s BN software survey, in Table B.3.