Van Harmelen F., Lifschitz V., Porter B. Handbook of Knowledge Representation

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

462 10. Model-based Problem Solving

[24] O. Dressler and P. Struss. Back to defaults: Characterizing and computing diag-

noses as coherent assumption sets. In Proceedings of the European Conference

on Artiﬁcial Intelligence (ECAI-92), 1992.

[25] O. Dressler and P. Struss. Model-based diagnosis with the default-based diagnos-

tic engine: Effective control strategies that work in practise. In 11th European

Conference on Artiﬁcial Intelligence, 1994.

[26] O. Dressler and P. Struss. A toolbox integrating model-based diagnosability

analysis and automated generation of diagnostics. In Proceedings of the 14th In-

ternational Workshop on Principles of Diagnosis, June 2003.

[27] M. Esser and P. Struss. Fault-model-based test generation for embedded software.

In International Joint Conference on Artiﬁcial Intelligence, 2007.

[28] G. Fleischanderl, G. Friedrich, A. Haselboeck, H. Schreiner, and M. Stumpt-

ner. Conﬁguring large systems using generativeconstraint satisfaction. Intelligent

Systems Archive, 13(4), 1998.

[29] A. Felfernig, G. Friedrich, D. Jannach, and M. Stumptner. Consistency-based

diagnosis of conﬁguration knowledge bases. Artiﬁcial Intelligence, 152, 2004.

[30] G. Friedrich, G. Gottlob, and W. Nejdl. Formalizing the repair process. In Pro-

ceedings of the 10th European conference on Artiﬁcial intelligence, 1992.

[31] G. Friedrich, G. Gottlob, and W. Nejdl. Physical impossibility instead of fault

models. In [39], 1992.

[32] M. Fisher. Temporal representation and reasoning. In V. Lifschitz, B. Porter,

and F. van Harmelen, editors. Handbook of Knowledge Representation. Elsevier,

2007.

[33] G. Friedrich and F. Lackinger. Diagnosing temporal misbehavior. In IJCAI-91,

1991.

[34] K. Forbus. Qualitative process theory. Artiﬁcial Intelligence, 24, 1984. Also in

[81].

[35] K. Forbus. Qualitative reasoning. In Handbook of Knowledge Representation.

Elsevier, 2008.

[36] B. Faltings and P. Struss. Recent Advances in Qualitative Physics. MIT Press,

1992.

[37] G. Friedrich, M. Stumptner, and F. Wotawa. Model-based diagnosis of hardware

designs. Artiﬁcial Intelligence, 3, 1999.

[38] R. Greiner, B.A. Smith, and R.W. Wilkerson. A correction to the algorithm in

Reiters theory of diagnosis. Artiﬁcial Intelligence, 41, 1989.

[39] W. Hamscher, J. de Kleer, and L. Console, editors. Readings in Model-based Di-

agnosis:Diagnosis of Designed Artifacts Based on Descriptions of their Structure

and Function. Morgan Kaufmann, 1992.

[40] U. Heller. Process-oriented consistency-based diagnosis-theory, implementation

and applications. PhD thesis, Akademische V.-G., 2001.

[41] U. Heller and P. Struss. Consistency-based problem solving for environmental de-

cision support. Computer-Aided Civil and Infrastructure Engineering, 17, 2002.

[42] G. Karsai, G. Biswas, S. Narasimhan, T. Szemethy, G. Peceli, G. Simon, and T.

Kovacshazy. Towards fault-adaptive control of complex dynamic systems. In T.

Samad and G. Balas, editors. Software-Enabled Control: Information Technolo-

gies for Dynamical Systems. Wiley–IEEE Press, 2003.

P. Struss 463

[43] D. Koeb and F. Wotawa. Fundamentals of debugging using a resolution calculus.

In International Conference on Fundamental Approaches to Software Engineer-

ing (FASE), LNCS, vol. 3922. Springer, 2006.

[44] P. Kim, B. Williams, and M. Abramson. Executing reactive, model-based pro-

grams through graph-based temporal planning. In Proceedings of the Interna-

tional Joint Conference on Artiﬁcial Intelligence, 2001.

[45] F. Lin. Situation calculus. In V. Lifschitz, B. Porter, and F. van Harmelen, editors.

Handbook of Knowledge Representation. Elsevier, 2007.

[46] G. Lamperti and M. Zanella. Diagnosis of Active Systems—Principles and Tech-

niques. Kluwer Academic Publisher, 2003.

[47] P. Mosterman and G. Biswas. A comprehensive methodology for building hybrid

models of physical systems. Artiﬁcial Intelligence, 121, 2000.

[48] I. Mozetic. Hierarchical model-based diagnosis. Int. J. of Man-Machine Studies,

35, 1991.

[49] S. McIlraith and R. Reiter. On tests for hypothetical reasoning. In [39], 1992.

[50] W. Mayer and M. Stumptner. Extending diagnosis to debug programs with ex-

ception. In IEEE Automated Software Engineering Conference, 2003.

[51] W. Mayer and M. Stumptner. Abstract interpretation of programs for model-

based debugging. In International Joint Conference on Artiﬁcial Intelligence

(IJCAI), 2007.

[52] P. Nayak. Automated Modeling of Physical Systems. Springer, 1995.

[53] S. Narasimhan and G. Biswas. Model-based diagnosis of hybrid systems. IEEE

Trans. on Systems, Man, and Cybernetics, Part A, 37(3), 2007.

[54] Y. Pencole and M.-O. Cordier. A formal framework for the decentralised diagno-

sis of large scale discrete event systems and its application to telecommunication

networks. Artiﬁcial Intelligence, 164, 2005.

[55] C. Picardi, L. Console, F. Berger, J. Breeman, T. Kanakis, J. Moelands, S. Col-

las, E. Arbaretier, N. De Domenico, E. Girardelli, O. Dressler, P. Struss, and

B. Zilbermann. AUTAS: a tool for supporting FMECA generation in aeronautic

systems. In Proceeding of the 16th European Conference on Artiﬁcial Intelli-

gence, 2004.

[56] B. Pulido and C.A. Gonzalez. Possible conﬂicts: a compilation technique for

consistency-based diagnosis. IEEE Transactions on Systems, Man and Cyber-

netics, Part B, 34(5), 2004.

[57] D. Poole. Normality and faults in logic-based diagnosis. In 11th International

Joint Conference on Artiﬁcial Intelligence, 1989. Also in [39].

[58] G. Provan and D. Pool. The utility of consistency-based diagnostic techniques. In

Proc. Second International Conference on Principles of Knowledge Representa-

tion and Reasoning, 1991.

[59] C. Price. Autosteve: Automated electrical design analysis. In Proceedings ECAI-

2000, 2000.

[60] O. Raiman, J. de Kleer, V. Saraswat, and M. Shirley. Characterizing non-

intermittent faults. In Proceedings of AAAI-91, 1991. Also in [39].

[61] R. Reiter. A logic for default reasoning. Artiﬁcial Intelligence, 13, 1980.

[62] R. Reiter. A theory of diagnosis from ﬁrst principles. Artiﬁcial Intelligence, 32(1),

1987. Also in [39].

[63] F. Rossi, P. van Beek, and T. Walsh. Constraint programming. In Handbook of

Knowledge Representation. Elsevier, 2008.

464 10. Model-based Problem Solving

[64] P. Struss and O. Dressler. Physical negation—integrating fault models into the

general diagnostic engine. In Proceedings of the International Joint Conference

on Artiﬁcial Intelligence (IJCAI-89), 1989.

[65] M. Sampath, S. Lafortune, and D. Teneketzis. Active diagnosis of discrete-event

system. IEEE Transactions on Automatic Control, 43(7), 1998.

[66] P. Struss and C. Price. Model-based systems in the automotive industry. AI Mag-

azine, 24, 2004.

[67] M. Sachenbacher and P. Struss. Task-dependent qualitative domain abstraction.

Artiﬁcial Intelligence, 162, 2005.

[68] M. Sachenbacher, P. Struss, and R. Weber. Advances in design and implemen-

tation of OBD functions for diesel injection systems based on a qualitative ap-

proach to diagnosis. In SAE 2000 World Congress, Detroit, USA, 2000.

[69] P. Struss. What’s in SD? Towards a theory of modeling for diagnosis. In [39],

1992.

[70] P. Struss. Testing for discrimination of diagnoses. In 5th International Workshop

on Principles of Diagnosis, 1994.

[71] P. Struss. Fundamentals of model-based diagnosis of dynamic systems. In 15th

International Joint Conference on Artiﬁcial Intelligence, 1997.

[72] P. Struss. Artiﬁcial intelligence methods for environmental decision support. In

e-Environment: Progress and Challenge, 2004.

[73] P. Struss. Automated test reduction. In 19th Int. Workshop on Qualitative Rea-

soning. 16th International Workshop on Principles of Diagnosis, 2005.

[74] P. Struss. A model-based methodology for the integration of diagnosis and fault

analysis during the entire life cycle. In Proceedings Volume from the 6th IFAC

Symposium on Fault Detection, Supervision and Safety of Technical Processes

(Safeprocess06), 2006.

[75] Y. Sun and D. Weld. A framework for model-based repair. In Proceedings of

AAAI-93, 1993.

[76] M. Tiller. Introduction to Physical Modeling with MODELICA. The Springer

International Series in Engineering and Computer Science, vol. 615. Springer,

2001.

[77] L. Trave-Massuyes, M.O. Cordier, and X. Pucel. Comparing diagnosability in

CS and DES. In Proceedings Volume from the 6th IFAC Symposium on Fault

Detection, Supervision and Safety of Technical Processes (Safeprocess06), 2006.

[78] L. Trave-Massuyes and R. Milne. TIGER

—gas turbine condition monitoring

using qualitative model-based diagnosis. IEEE Expert, 12(3), 1997.

[79] Y. Umeda, T. Tomiyama, H. Yoshikawa, and Y. Shimomura. A design methodol-

ogy for self-maintenance machines. IEEE Expert: Intelligent Systems and their

Applications Archive, 9(3), 1994.

[80] I. Vatcheva, O. Bernhard, H. de Jong, and N.J.I. Mars. Experiment selection for

the discrimination of semi-quantitative models of dynamical systems. Artiﬁcial

Intelligence, 170, 2006.

[81] D. Weld and J. de Kleer. Readings in Qualitative Reasoning about Physical Sys-

tems. Morgan Kaufmann, 1990.

[82] B. Williams. Interaction-basedinvention: Designing novel devices from ﬁrst prin-

ciples. In Proceedingsof the National Conference on Artiﬁcial Intelligence,1990.

[83] B. Williams. Interaction-basedinvention: Designing novel devices from ﬁrst prin-

ciples. In [36], 1992.

P. Struss 465

[84] B. Williams and P. Nayak. A model-based approach to reactive self-conﬁguring

systems. In Proceedings of AAAI-96, 1996.

[85] F. Wotawa. On the relationship between model-based debugging and program

slicing. Artiﬁcial Intelligence, 135, 2002.

[86] B. Williams and R. Ragno. Conﬂict-directed A* and its role in model-based em-

bedded systems. Journal of Discrete Applied Math., 2003.

This page intentionally left blank

Handbook of Knowledge Representation

Edited by F. van Harmelen, V. Lifschitz and B. Porter

DOI: 10.1016/S1574-6526(07)03011-8

467

Chapter 11

Bayesian Networks

A. Darwiche

11.1 Introduction

A Bayesian network is a tool for modeling and reasoning with uncertain beliefs.

A Bayesian network consists of two parts: a qualitative component in the form of

a directed acyclic graph (DAG), and a quantitative component in the form conditional

probabilities; see Fig. 11.1. Intuitively, the DAG of a Bayesian network explicates

variables of interest (DAG nodes) and the direct inﬂuences among them (DAG edges).

The conditional probabilities of a Bayesian network quantify the dependencies be-

tween variables and their parents in the DAG. Formally though, a Bayesian network

is interpreted as specifying a unique probability distribution over its variables. Hence,

the network can be viewed as a factored (compact) representation of an exponentially-

sized probability distribution. The formal syntax and semantics of Bayesian networks

will be discussed in Section 11.2.

The power of Bayesian networks as a representational tool stems both from this

ability to represent large probability distributions compactly, and the availability of

inference algorithms that can answer queries about these distributions without nec-

essarily constructing them explicitly. Exact inference algorithms will be discussed in

Section 11.3 and approximate inference algorithms will be discussed in Section 11.4.

Bayesian networks can be constructed in a variety of ways, depending on the appli-

cation at hand and the available information. In particular, one can construct Bayesian

networks using traditional knowledge engineering sessions with domain experts, by

automatically synthesizing them from high level speciﬁcations, or by learning them

from data. The construction of Bayesian networks will be discussed in Section 11.5.

There are two interpretations of a Bayesian network structure, a standard interpre-

tation in terms of probabilistic independence and a stronger interpretation in terms

of causality. According to the stronger interpretation, the Bayesian network speciﬁes

a family of probability distributions, each resulting from applying an intervention to

the situation of interest. These causal Bayesian networks lead to additional types of

queries, and require more specialized algorithms for computing them. Causal Bayesian

networks will be discussed in Section 11.6.

468 11. Bayesian Networks

A Θ

true 0.6

false 0.4

ABΘ

B|A

true true 0.2

true false 0.8

false true 0.75

false false 0.25

ACΘ

C|A

true true 0.8

true false 0.2

false true 0.1

false false 0.9

BCDΘ

D|B,C

true true true 0.95

true true false 0.05

true false true 0.9

true false false 0.1

false true true 0.8

false true false 0.2

false false true 0

false false false 1

CEΘ

E|C

true true 0.7

true false 0.3

false true 0

false false 1

Figure 11.1: A Bayesian network over ﬁve propositional variables. A table is associated with each node

in the network, containing conditional probabilities of that node given its parents.

11.2 Syntax and Semantics of Bayesian Networks

We will discuss the syntax and semantics of Bayesian networks in this section, starting

with some notational conventions.

11.2.1 Notational Conventions

We will denote variables by upper-case letters (A) and their values by lower-case let-

ters (a). Sets of variables will be denoted by bold-face upper-case letters (A) and their

instantiations by bold-face lower-case letters (a). For variable A and value a, we will

often write a instead of A = a and, hence, Pr(a) instead of Pr(A = a) for the prob-

ability of A = a. For a variable A with values true and false, we may use A or a to

denote A = true and ¬A or

a to denote A = false. Therefore, Pr(A),Pr(A = true) and

Pr(a) all represent the same probability in this case. Similarly, Pr(¬A),Pr(A = false)

and Pr(

a) all represent the same probability.

A. Darwiche 469

Table 11.1. A probability distribution Pr(.) and the result of conditioning it on evidence Alarm,Pr(.|Alarm)

World Earthquake Burglary Alarm Pr(.) Pr(.|Alarm)

true true true 0.0190 0.0190/0.2442

true true false 0.0010 0

true false true 0.0560 0.0560/0.2442

true false false 0.0240 0

false true true 0.1620 0.1620/0.2442

false true false 0.0180 0

false false true 0.0072 0.0072/0.2442

false false false 0.7128 0

11.2.2 Probabilistic Beliefs

The semantics of Bayesian networks is given in terms of probability distributions and

is founded on the notion of probabilistic independence. We review both of these no-

tions in this section.

Let X

,...,X

be a set of variables, where each variable X

has a ﬁnite number

of values x

. Every instantiation x

,...,x

of these variables will be called a possible

world, denoted by ω, with the set of all possible worlds denoted by Ω.Aprobabil-

ity distribution Pr over variables X

,...,X

is a mapping from the set of worlds Ω

induced by variables X

,...,X

into the interval [0, 1], such that



Pr(ω) = 1;

see Table 11.1.Anevent η is a set of worlds. A probability distribution Pr assigns a

probability in [0, 1] to each event η as follows: Pr(η) =



ω∈η

Pr(ω).

Events are typically denoted by propositional sentences, which are deﬁned induc-

tively as follows. A sentence is either primitive, having the form X = x, or complex,

having the form ¬α, α ∨ β, α ∧ β, where α and β are sentences. A propositional

sentence α denotes the event Mods(α), deﬁned as follows: Mods(X = x) is the set

of worlds in which X is set to x, Mods(¬α) = Ω \ Mods(α), Mods(α ∨ β) =

Mods(α) ∪ Mods(β), and Mods(α ∧ β) = Mods(α) ∩ Mods(β).InTable 11.1,the

event {ω

,ω

} can be denoted by the sentence Burglary ∨ Earthquake

and has a probability of 0.28.

If some event β is observed and does not have a probability of 0 according to

the current distribution Pr, the distribution is updated to a new distribution, denoted

Pr(.|β),usingBayes conditioning:

(11.1)Pr(α|β) =

Pr(α ∧ β)

Pr(β)

Bayes conditioning follows from two commitments: worlds that contradict evidence

β must have zero probabilities, and worlds that are consistent with β must maintain

their relative probabilities.

Table 11.1 depicts the result of conditioning the given

distribution on evidence Alarm = true, which initially has a probability of 0.2442.

When evidence β is accommodated, the belief is some event α may remain the

same. We say in this case that α is independent of β. More generally, event α is inde-

This is known as the principle of probability kinematics [88].

470 11. Bayesian Networks

pendent of event β given event γ iff

(11.2)Pr(α|β ∧ γ) = Pr(α|γ) or Pr(β ∧ γ)= 0.

We can also generalize the deﬁnition of independence to variables. In particular, we

will say that variables X are independent of variables Y given variables Z, written

I(X, Z, Y),iff

Pr(x|y, z) = Pr(x|z) or Pr(y, z) = 0

for all instantiations x, y, z of variables X, Y and Z. Hence, the statement I(X, Z, Y)

is a compact representation of an exponential number of independence statements of

the form given in (11.2).

Probabilistic independence satisﬁes some interesting properties known as the

graphoid axioms [130], which can be summarized as follows:

I(X, Z, Y) iff I(

Y, Z, X)

I(X, Z, Y) & I(X, ZW, Y) if

f I(X, Z, YW).

The ﬁrst axiom is called Symmetry, and the second axiom is usually broken down into

three axioms called decomposition, contraction and weak union; see [130] for details.

We will discuss the syntax and semantics of Bayesian networks next, showing the

key role that independence plays in the representational power of these networks.

11.2.3 Bayesian Networks

A Bayesian network over variables X is a pair (G, Θ), where

• G is a directed acyclic graph over variables X;

• Θ is a set of conditional probability tables (CPTs), one CPT Θ

X|U

for each

variable X and its parents U in G.TheCPTΘ

X|U

maps each instantiation xu to

a probability θ

x|u

such that



x|u

= 1.

We will refer to the probability θ

x|u

as a parameter of the Bayesian network, and to

the set of CPTs Θ as a parametrization of the DAG G.

A Bayesian network over variables X speciﬁes a unique probability distributions

over its variables, deﬁned as follows [130]:

(11.3)Pr(x)

def

x|u

:xu∼x

x|u

where ∼ represents the compatibility relationship among variable instantiations;

hence, xu ∼ x means that instantiations xu and x agree on the values of their common

variables. In the Bayesian network of Fig. 11.1,Eq.(11.3) gives:

Pr(a,b,c,d,e) = θ

e|c

d|b,c

c|a

b|a

where a, b, c, d, e are values of variables A, B, C, D, E, respectively.

The distribution given by Eq. (11.3) follows from a particular interpretation of the

structure and parameters of a Bayesian network (G, Θ). In particular:

A. Darwiche 471

• Parameters: Each parameter θ

x|u

is interpreted as the conditional probability

of x given u,Pr(x|u).

• Structure: Each variable X is assumed to be independent of its nondescendants

Z given its parents U: I(X,U, Z).

The above interpretation is satisﬁed by a unique probability distribution, the one given

in Eq. (11.3).

11.2.4 Structured Representations of CPTs

The size of a CPT Θ

X|U

in a Bayesian network is exponential in the number of par-

ents U. In general, if every variable can take up to d values, and has at most k parents,

the size of any CPT is bounded by O(d

k+1

). Moreover, if we have n network vari-

ables, the total number of Bayesian network parameters is bounded by O(nd

k+1

This number is usually quite reasonable as long as the number of parents per vari-

able is relatively small. If number of parents U for variable X is large, the Bayesian

network representation looses its main advantage as a compact representation of prob-

ability distributions, unless one employs a more structured representation for network

parameters than CPTs.

The solutions to the problem of large CPTs fall in one of two categories. First,

we may assume that the parents U interact with their child X according to a spe-

ciﬁc model, which allows us to specify the CPT Θ

X|U

using a smaller number of

parameters (than exponential in the number of parents U). One of the most popular

examples of this approach is the noisy-or model of interaction and its generalizations

[130, 77, 161, 51]. In its simplest form, this model assumes that variables have binary

valuestrue/false,that each parent U ∈ U being trueis sufﬁcientto make X true, except

if some exception α

materializes. By assuming that exceptions α

are independent,

one can induce the CPT Θ

X|U

using only the probabilities of these exceptions. Hence,

the CPT for X can be speciﬁed using a number of parameters which is linear in the

number of parents U, instead of being exponential in the number of these parents.

The second approach for dealing with large CPTs is to appeal to nontabular rep-

resentations of network parameters that exploit the local structure in network CPTs.

In broad terms, local structure refers to the existence of nonsystematic redundancy

in the probabilities appearing in a CPT. Local structure typically occurs in the form

of determinism, where the CPT parameters take extreme values (0, 1). Another form

of local structure is context-speciﬁc independence (CSI) [15], where the distribution

for X can sometimes be determined by only a subset of its parents U. Rules [136, 134]

and decision trees (and graphs) [61, 80] are among the more common structured rep-

resentations of CPTs.

11.2.5 Reasoning about Independence

We have seen earlier how the structure of a Bayesian network is interpreted as declar-

ing a number of independence statements. We have also seen how probabilistic inde-

pendence satisﬁes the graphoid axioms. When applying these axioms to the indepen-

dencies declared by a Bayesian network structure, one can derive new independencies.

AvariableZ is a nondescendant of X if Z/∈ XU and there is no directed path from X to Z.