[Next] [Up] [Previous]
Next: Implementing a Q-DAG Evaluator Up: Query DAGs: A Practical Previous: Introduction

Query DAGs


This section starts our treatment of Q-DAGs with a concrete example. We will consider a particular belief network, define a set of queries of interest, and then show a Q-DAG that can be used to answer such queries. We will not discuss how the Q-DAG is generated; only how it can be used. This will allow a concrete introduction to Q-DAGs and will help us ground some of the formal definitions to follow.

The belief network we will consider is the one in Figure 4(a). The class of queries we are interested in is tex2html_wrap1018, that is, the probability that variable tex2html_wrap1015 takes some value given some known (or unknown) value of tex2html_wrap1014. Figure 4(b) depicts a Q-DAG for answering such queries, which is essentially a parameterized arithmetic expression where the values of parameters depend on the evidence obtained. This Q-DAG will actually answer queries of the form tex2html_wrap1021, but we can use normalization to compute tex2html_wrap1018.

First, a number of observations about the Q-DAG in Figure 4(b):

According to the semantics of Q-DAGs, the value of node tex2html_wrap1030 is 1 if variable tex2html_wrap1031 is observed to be tex2html_wrap1032 or is unknown, and 0 otherwise. Once the values of ESNs are determined, we evaluate the remaining nodes of a Q-DAG using numeric multiplication and addition. The numbers that get assigned to query nodes as a result of this evaluation are the answers to queries represented by these nodes.

For example, suppose that the evidence we have is tex2html_wrap1033. Then ESN tex2html_wrap1027 is evaluated to 1 and ESN tex2html_wrap1028 is evaluated to 0. The Q-DAG in Figure 4(b) is then evaluated as given in Figure [*](a), thus leading to
from which we conclude that tex2html_wrap1036. We can then compute the conditional probabilities tex2html_wrap1037 and tex2html_wrap1038 using:


If the evidence we have is tex2html_wrap1039, however, then tex2html_wrap1027 evaluates to 0 and tex2html_wrap1028 evaluates to 1. The Q-DAG in Figure 4(b) will then be evaluated as given in Figure [*](b), thus leading to

Figure: Evaluating the Q-DAG in Figure 4 with respect to two pieces of evidence: (a) tex2html_wrap1033 and (b) tex2html_wrap1039.  

We will use the following notation for denoting variables and their values. Variables are denoted using uppercase letters, such as tex2html_wrap1044, and variable values are denoted by lowercase letters, such as tex2html_wrap1045. Sets of variables are denoted by boldface uppercase letters, such as tex2html_wrap1044, and their instantiations are denoted by boldface lowercase letters, such as tex2html_wrap1045. We use tex2html_wrap1048 to denote the set of variables about which we have evidence. Therefore, we use tex2html_wrap1049 to denote an instantiation of these variables that represents evidence. Finally, the family of a variable is the set containing the variable and its parents in a directed acyclic graph.

Following is the formal definition of a Q-DAG.
Evidence variables tex2html_wrap1063 correspond to network variables about which we expect to collect evidence on-line. For example, in Figure [*], C is the evidence variable. Each one of these variables has a set of possible values that are captured by the function tex2html_wrap1064. For example, in Figure [*], the evidence variable C has values tex2html_wrap_inline1230 and tex2html_wrap_inline1232. The special value tex2html_wrap1065 is used when the value of a variable is not known. For example, we may have a sensor variable with values ``low,'' ``medium,'' and ``high,'' but then lose the sensor value during on-line reasoning. In this case, we set the sensor value to tex2html_wrap1065.[+] Query nodes are those representing answers to user queries. For example, in Figure [*], B is the query variable, and leads to query nodes tex2html_wrap_inline1236 and tex2html_wrap_inline1238.

An important notion is that of evidence:
When a variable tex2html_wrap1031 is mapped into tex2html_wrap1073, then evidence tells us that tex2html_wrap1031 is instantiated to value tex2html_wrap1032. When tex2html_wrap1031 is mapped into tex2html_wrap1065, then evidence does not tell us anything about the value of tex2html_wrap1031.

We can now state formally how to evaluate a Q-DAG given some evidence. But first we need some more notation:

  1. Numeric-Node: tex2html_wrap1079 denotes a node labeled with a number tex2html_wrap1080;
  2. ESN: tex2html_wrap1081 denotes a node labeled with tex2html_wrap1030;
  3. Operation-Node: tex2html_wrap1083 denotes a node labeled with * and having parents tex2html_wrap1084;
  4. Operation-Node: tex2html_wrap1085 denotes a node labeled with + and having parents tex2html_wrap1084.

The following definition tells us how to evaluate a Q-DAG by evaluating each of its nodes. It is a recursive definition according to which the value assigned to a node is a function of the values assigned to its parents. The first two cases are boundary conditions, assigning values to root nodes. The last two cases are the recursive ones.


One is typically not interested in the values of all nodes in a Q-DAG since most of these nodes represent intermediate results that are of no interest to the user. It is the query nodes of a Q-DAG that represent answers to user queries and it is the values of these nodes that one seeks when constructing a Q-DAG. The values of these queries are captured by the notion of a Q-DAG output.

This output is what one seeks from a Q-DAG. Each element in this output represents a probabilistic query and its answer.

Let us consider a few evaluations of the Q-DAG shown in Figure 4, which are shown in Figure [*]. Given evidence tex2html_wrap1101, and assuming that tex2html_wrap1102 and tex2html_wrap1103 stand for the Q-DAG nodes labeled tex2html_wrap1023 and tex2html_wrap1024, respectively, we have
meaning that tex2html_wrap1106 and tex2html_wrap1107. If instead the evidence were tex2html_wrap1108, a set of analogous computations can be done.

It is also possible that evidence tells us nothing about the value of variable tex2html_wrap1014, that is, tex2html_wrap1110. In this case, we would have
meaning that tex2html_wrap1111 and tex2html_wrap1112.

[Next] [Up] [Previous]
Next: Implementing a Q-DAG Evaluator Up: Query DAGs: A Practical Previous: Introduction