Brought to you by EarthWeb
IT Library Logo

Click Here!
Click Here!

Search the site:
 
EXPERT SEARCH -----
Programming Languages
Databases
Security
Web Services
Network Services
Middleware
Components
Operating Systems
User Interfaces
Groupware & Collaboration
Content Management
Productivity Applications
Hardware
Fun & Games

EarthWeb Direct EarthWeb Direct Fatbrain Auctions Support Source Answers

EarthWeb sites
Crossnodes
Datamation
Developer.com
DICE
EarthWeb.com
EarthWeb Direct
ERP Hub
Gamelan
GoCertify.com
HTMLGoodies
Intranet Journal
IT Knowledge
IT Library
JavaGoodies
JARS
JavaScripts.com
open source IT
RoadCoders
Y2K Info

Previous Table of Contents Next


7.5. PROCESS OF USING A BELIEF NETWORK

All that is left to use the network is to encode an instance of a problem and pose queries to the inference engine. The task is to compute the probability for a single or set of query variables, Q, given exact values for some evidence variables P(Q|E). It should be noted that in the general case, the problem of updating the network is NP-Hard (Cooper, 1987). In fact, even approximations are NP-Hard (Dagum and Luby, 1993). A particular algorithm presented in Russell and Norvig (1995) uses backward chaining in a specific type of network with the topology of a singly connected network called a polytree. In a polytree there is at most one undirected path between any two nodes in the network. This routine has a linear time complexity and is used as the workhorse in more general networks. In multiply connected networks, the complexity is exponential in the worst case. The recursive procedure spreads out from the query variable Q along all paths. The basis cases occur on root nodes, evidence nodes, and leaf nodes. Recursive calls exclude the node from which they were called; thus, each node is covered only once. Those readers interested in the derivation of this algorithm are encouraged to see Russell and Norvig (1995). Pearl (1988) also presents an algorithm for polytrees. The values for evidence variable are obtained from sensors or other reasoning agents.

7.6. MULTIPLY CONNECTED BELIEF NETWORKS

More complex belief networks require other algorithms. Multiply connected networks contain more than one undirected path between two nodes. There are three basic algorithms for evaluating multiply connected networks. Clustering uses a merging of the offending nodes into an equivalent polytree. Conditioning transforms the network into several polytrees by instantiating variables to definite values and then evaluating each polytree. Finally, stochastic simulations use the network to generate a large number of concrete models of the domain that are consistent with the network distribution. Approximation by this method is the current method of choice.

7.7. EXAMPLE

To illustrate the fact that the belief network is a compact representation of the joint PD, we will calculate P(StorageOK = true, AgeOK = true, YeastOK = true, IngredOK = true, DoughRises = true). In order for the notation to be concise, let S = StorageOK, A = AgeOK, Y = YeastOK, I = IngredOK, and D = DoughRises. Then, using the chain rule and the conditional independence shown in the belief network above, one obtains:

The following illustrates an example of a query given some evidence. Assume that we wish to calculate P(Y|S, I, ~D). We will first work out the details of the formulas starting with Bayes theorem and then add numbers from the belief network in Figure 4.

8. FUTURE RESEARCH

We behave and problem-solve under uncertainty. Though there has been much discussion of how to think about uncertainty and a number of attempts to sidestep the problems with probabilistic reasoning have been made, Bayesian reasoning is theoretically anchored, the approach of choice, and the most important of the various approaches to the problem of uncertainty in reasoning systems. Some variant of Bayesian reasoning is desirable because it requires explicit detailing of the prior knowledge upon which a belief or decision is based. Decision-making under uncertainty is a difficult task. It requires lots of knowledge and a well-developed model. There is no way around this issue if one wants to build a refined and high-precision system. Bayesian belief networks are proving very valuable, for example, as a tool for implementing normative inferencing. They have been used for model-based diagnosis and in case-based reasoning systems to provide a way of organizing case bases and controlling problem-solving.

REFERENCES

Buchanan, B.G. and Shortliffe, E.H. (1985). Rule-Based Expert Systems the MYCIN
Experiments of the Stanford Heuristic Programming Project. Reading, MA: Addison-Wesley.
Charniak, Eugene (1991). Bayesian networks without tears. AI Magazine, 12(2), 50-63.
Cooper, Gregory F. (1987). Probabilistic Inference Using Belief Networks is NP-Hard
(Technical Report KSL-87-27). Medical Computer Science Group, Stanford University.
Dagum, Paul and Luby, Michael (1993). Approximating probabilistic inferences in Bayesian
belief networks is NP-Hard. Artificial Intelligence, 60(1), 141-153.
Gonzalez, A.J. and Dankel, D. D. (1993). The Engineering of Knowledge-Based Systems
Theory and Practice. Englewood Cliffs, NJ: Prentice-Hall.
Gordon, J. and Shortliffe, E.H. (1985a). The Dempster-Shafer theory of evidence. In
Buchanan, B.G. and Shortliffe, E.H. (Eds.), Rule-Based Expert Systems the MYCIN Experiments of the Stanford Heuristic Programming Project. Reading, MA: Addison-Wesley.
Gordon, J. and Shortliffe, E.H. (1985b). Evidential reasoning in a hierarchy.
Artificial Intelligence, 26(3), 323-357.
Heckerman, D. (1990). Probabilistic interpretations for MYCINS certainty factors. In Kanal,
L.N. and Lemmer, J.F (Eds.), Uncertainty in Artificial Intelligence. NewYork: New-Holland.
Heckerman, D. (1995). A Tutorial on Learning with Bayesian Networks (Technical
Report MSR-TR-95-06, Microsoft Research, 1995.
Kanal, L.N. and Lemmer, J.F. (Eds.). (1990) Uncertainty in Artificial Intelligence. New York:
New-Holland.
Norvig, P. (1992). Paradigms of Artificial Intelligence Programming: Case Studies in
Common Lisp. San Mateo, CA: Morgan Kaufmann.
Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible
Reasoning.
San Mateo, CA: Morgan-Kaufmann.
Russell, S.J. and Norvig, P. (1995). Artificial Intelligence: A Modern Approach. Englewood
Cliffs, NJ: Prentice-Hall.
Stefik, M. (1995). Introduction to Knowledge Systems. San Francisco: Morgan Kaufmann.
Shortliffe, E.H. (1976). Computer-Based Medical Consultations: MYCIN. New York: Elsevier.


Previous Table of Contents Next

footer nav
Use of this site is subject certain Terms & Conditions.
Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details.