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.3. STRUCTURE OF A BELIEF NETWORK

Before discussing the structure of the belief network, an example will be given in order to illustrate the concepts discussed herein. Suppose we are in the process of modeling the probability of the dough rising when making bread. The storage of the yeast is proper with a prior probability of 0.8. The yeast is within the expiration date with a prior probability of 0.9. The other ingredients are added correctly with a prior probability of 0.8. The storage and age of the yeast directly influence the condition of the yeast. The condition of the yeast and the proper addition of other ingredients directly affect the dough rising. Other probabilities will be given when needed. We now begin the discussion of the structure of the network using this example.

The components that make up a belief network as well as their relationships are presented. See Figure 4 for the complete belief network for the above problem statement. Components of the figure are explained below. As previously stated, the belief network is a graph structure. More precisely, the graph is a directed acyclic graph (DAG). Within any problem domain there are variables that are used to define the state of the domain. These variables are represented by the nodes of the belief network. Directed arcs from one node to another represent a causal relationship. For example, an arc from node A to node B means that the value of A has a direct effect on the probability of B. In graph terms, A is said to be a parent of B. Each root node (a node with no parents) has associated with it a prior probability. Each non-root node (a leaf node or interior node) of the has an associated conditional probability table (CPT) associated with it. CPTs provide a decomposed representation of the joint PD. The input to this truth table is each parent's state and the output is the belief that the node is in a certain state. Each row represents a possible combinations of states of the parents and each row adds up to 1.0. Since the rows of the CPTs add to 1.0, it is common to eliminate the last variable assignment probability from the table as shown above. Since the YeastOK is either true or false, only probabilities for true values are put in the table. An example of a belief network using the bread dough example is shown in Figure 4.

P(Storage = true) = 0.8
P(Ingred OK = true) = 0.8
P(Age = true) = 0.8

StorageOK AgeOK YeastOK
 
False False 0.1
False True 0.2
True False 0.3
True True 0.9

IngredOK YeastOK DoughRises
 
False False 0.1
False True 0.2
True False 0.3
True True 0.9


FIGURE 4 An example belief network.

7.4. KNOWLEDGE ENGINEERING

A method used to build the belief network for any given problem domain is given. This method guarantees that the belief network so constructed will be an acyclic network and will minimize redundant information. The process of building the network consists of the following steps: choose a set of domain variables, construct the topology of the belief network, and then specify the conditional probabilities. (Russell and Norvig, 1995).

In choosing a set of domain variables, decide what is relevant to the problem domain, that is, decide which factors/variables are of interest to track. In representing the problem, the degree of approximation can be improved if additional relevant information is provided, but at the expense of increased complexity. Once the variables have been identified, decide what to name the variables and determine their possible values. This last step may include discretizing a continuous variable. In the above example, each of the variables takes on only two possible values.

The next step is to construct the topology of the graph. The parents of a node should be only those nodes that DIRECTLY influence that node in order to capture the most gain in terms of simplicity of the derived network. Therefore, first decide what each node directly affects and what nodes directly affect it; then, choose a causal ordering for the variables. See Table 2 which contains the ordering for the example. The prerequisites for connecting the nodes have now been identified. The procedure begins by adding root variables first. Recall, these nodes have no parents in the causal ordering. Starting with the next node in the ordering, add it to the graph. Connect it to the minimal set of existing nodes in the network that directly influence the new node. Continue in this manner until all nodes are added. Figure 4 above displays the resultant topology.


TABLE 2
Variables, Values, and Orders
 
Variable Values

Order
 
StorageOK True False 1
AgeOK True False 2
IngredOK True False 3
YeastOK True False 4
DoughRises True False 5

Once the relationships among the nodes are in place, the next step is to specify the conditional probabilities tables. Recall that CPTs express the probabilities of a node given the states of the parents. Values are obtained from expert subjective experience, measurement of frequencies, or a combination of the two. See Figure 4 for the CPTs that have been added for our example to the nodes YeastOK and DoughRises.


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.