[Next] [Up] [Previous]
Next: Q-DAG Reduction Up: A Diagnosis Example Previous: A Diagnosis Example

Q-DAG Generation

The first step is to generate the Q-DAG. This is accomplished by applying the Q-DAG clustering algorithm with the fault as a query variable and the sensors as evidence variables. The resulting Q-DAG has five query nodes, tex2html_wrap1716, tex2html_wrap1717, tex2html_wrap1718, tex2html_wrap1719, and tex2html_wrap1720. Each node evaluates to the probability of the corresponding fault under any instantiation of evidence. The probabilities constitute a differential diagnosis that tells us which fault is most probable given certain sensor values.

Figure 15 shows a stylized description of the Q-DAG restricted to two of the five query nodes, corresponding to tex2html_wrap1721 and tex2html_wrap1722. The Q-DAG structure is symmetric for each fault value and sensor.

 figure355
Figure: A partial Q-DAG for the car example, displaying two of the five query nodes, broken_fuel_pump and normal. The shaded regions are portions of the Q-DAG that are shared by multiple query nodes; the values of these nodes are relevant to the value of more than one query node.  

Given that the Q-DAG is symmetric for these possible faults, for clarity of exposition we look at just the subset needed to evaluate node tex2html_wrap1721. Figure 16 shows a stylized version of the Q-DAG produced for this node. Following are some observations about this Q-DAG. First, there is an evidence-specific node for every instantiation of sensor variables, corresponding to all forms of sensor measurements possible. Second, all other roots of the Q-DAG are probabilities. Third, one of the five parents of the query node tex2html_wrap_inline1732 is for the prior on tex2html_wrap_inline1734, and the other four are for the contributions of the four sensors. For example, Figure 16 highlights (in dots) that part of the Q-DAG for computing the contribution of the battery sensor.

 figure366
Figure: A partial Q-DAG for the car example.  


[Next] [Up] [Previous]
Next: Q-DAG Reduction Up: A Diagnosis Example Previous: A Diagnosis Example

Darwiche&Provan