![]() |
|||
![]()
|
![]() |
![]() |
![]() |
7.5. PROCESS OF USING A BELIEF NETWORKAll 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 NETWORKSMore 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. EXAMPLETo 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 RESEARCHWe 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
|
![]() |
|
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. |