Query-based diagnostics (Agosta, Gardos, & Druzdzel, 2008) o ers passive, incremental construction of diagnostic models that rest on the interaction between a diagnostician and a computer-based diagnostic system. Effectively, this approach minimizes knowledge engineering, the main bottleneck in practical application of Bayesian networks. While this idea is appealing, it has undergone only limited testing in practice. We describe a series of experiments that subject a prototype implementing passive, incremental model construction to a rigorous practical test. We show that the prototype's diagnostic accuracy reaches reasonable levels after merely tens of cases and continues to increase with the number of cases, comparing favorably to state of the art approaches based on learning.
Even though Bayesian network (BN) models
One way of addressing this problem is learning
models from data accrued over past cases. Given a su
ciently large set of past cases, we can learn both the
structure and the parameters of Bayesian networks
While this idea is appealing, it has undergone only
limited testing in practice. To the best of our knowledge,
there are two existing prototypes implementing this
approach. An industrial prototype of the system has
been implemented and elded at Intel and tested in the
domain of diagnostics and corrective maintenance of
factory equipment
We will start with a brief review of the technology involved in a query-based diagnostic prototype like Marilyn, notably Bayesian networks, noisy-OR gates, and the EM algorithm.
2.1
Bayesian networks
The most important type of reasoning in Bayesian networks is known as belief updating and amounts to computing the probability distribution over variables of interest given the evidence. For example, in the model of Figure 1, the variable of interest could be Damaged CPU and the BN could compute the posterior probability distribution over this node given the observed values of Computer is old, Hard disk LED does not work, and Monitor LED never goes to steady green. Once the network has updated the probability values, these can be used to make a diagnostic decision. 2.2
Bayesian networks su er from a practical problem:
Because CPTs represent the probability distribution of a
node conditional on all combinations of parent
variables, their size grows exponentially with the number
of parents. Table 1 shows the CPT for the node
Monitor LED never goes to steady green. The node has
three parents and the size of its CPT is 23 = 8.
One solution to the exponential growth of CPTs is
application of Independence of Causal In uences (ICI)
models
Marilyn is based on the ICI model called the
noisyOR gate
In general, it is infeasible to explicitly include all
possible causes of an e ect. Marilyn uses an
extension of the noisy-OR gate called leaky noisy-OR gate
The Expectation-Maximization (EM) algorithm
Marilyn
Marilyn is a web-based application that implements
the idea of query-based diagnostics, i.e., passive
construction of diagnostic decision models. It is written
in C# and ASP.NET, using a Microsoft SQL database
to store data. It utilizes the Bayesian reasoning
engine SMILE2 running under the Microsoft Windows
Vista Server. Figure 2 shows Marilyn's
architecture. Marilyn appears to the user diagnostician as
a computer program for logging case data. The user
interacts with it though a web browser, entering
elements of the case at hand. The case data are entered in
free text format, although the system performs simple
text matching to suggest values entered in prior cases.
Marilyn presents the user unobtrusively with a list of
most likely diagnoses implied by the observations
entered so far, suggests additional observations to make
and tests to perform. Behind the screen, Marilyn
constructs a Bayesian network from the prior cases
stored in the database and, ultimately, adds the
current case to the database.
The Bayesian networks constructed by Marilyn
use a simpli ed structure called the BN3M model
Fault variables, which represent the problems that the diagnostician wants to identify (e.g., a disease or a device malfunction).
Observation variables, which include observed symptoms and results of diagnostic tests.
Context variables, which are the background, history, or other information known by the technician performing the diagnosis that may in uence the probability of a fault and, therefore, are relevant to the diagnosis.
The structure of BN3M networks consists of three levels, with the context information variables on the top, the fault variables in the middle, and the observation variables at the bottom. In uences are possible only between neighboring layers. Figure 3 shows an example of this structure. The rst context variable, User is a registered student, in uences the variable User has no print quota. The second context variable Computer lab is busy in uences the faults Printer is backing up and Printer is out of paper. No print job out is in uenced by any three of the fault variables. Trays 5 and 6 are empty is in uenced only by the fault Printer is out of paper. 3.2
When Marilyn starts, it constructs a Bayesian
network from the existing database (in the very
beginning, this database is empty). The database consists
of six tables: arcs, diagnosis, domains, nodes, lablog,
and emlog. The rst four tables store the information
about causal interactions among variables, the
number of diagnostic sessions that have been stored by the
system, the diagnostic domains, and variables,
respectively. The last two tables store data for each session
and store the diagnostic logs used in re ning the model
parameters.
necting all context variables and and all observation
variables to the fault node observed in the case (i.e.,
the nal diagnosis, as indicated by the diagnostician).
This provides a graph skeleton that is subsequently
quanti ed in the following way. All prior probability
distributions are set to 0.1/0.9. All conditional
probability distributions are set to 0.8/0.2. The EM
algorithm, which Marilyn subsequently invokes, treats
these initial values as a prior probability distributions
and re nes them by means of the records accrued
during the past diagnostic cases. While the above priors
are arbitrary, we found that they are capable of
inducing reasonable behavior on the part of the model, even
if the number of existing records is small. There is an
increasing body of evidence that the precise values of
the parameters are not crucial in practice
The nal model, i.e., model obtained after the parameter re nement stage, is used by Marilyn to generate a list of most likely diagnoses for the current diagnostic case. 4 4.1
We tested the accuracy of Marilyn on four di erent real data sets listed in Table 2. The computing lab data set was collected over the course of two semesters at a help desk of a University of Pittsburgh campus computing lab. Typical campus computing lab help desk problems involve printing problems and printer troubleshooting. Among the four hundred cases in the data set, there are a total of 16 di erent observations, 12 di erent context variables, and 21 di erent problems. The remaining three data sets originate from the UCI Machine Learning repository and were selected based on the following four criteria:
The data include a known class variable.
The attribute types of all variables are discrete. We wanted to avoid the need for discretization, which could become a factor confounding our experiment.
The number of cases in the data le should be over 100, which we believe to be large enough for the purpose of the experiment.
The data should have been used in the literature
in the past, so that we have information about
baseline performance of learning algorithms.
Marilyn constructs the BN3M structure by going
through all diagnostic cases entered so far and
conThe three Irvine repository data sets that ful lled the
above requirements were SPECT Heart, Breast
Cancer and Lymphography. Their properties are listed in
Table 2. #I in the table denotes the number of data
records, #A denotes the number of attributes, #CV
denotes the number of class variables, and MV
describes presence of missing values.
We wanted to test the accuracy of Marilyn as a
function of the number of cases that it has seen on each
of the data sets listed in Table 2. This is of interest
because the idea of query-based diagnostics is meant
to work especially when there are no data that can be
used to learn a model. Availability of a complete data
set would make Marilyn useless, as the model could
be learned from data by means of any of the Bayesian
network learning methods available in the literature.
We imitated Marilyn's diagnostician's work- ow,
which consists of entering three types of information:
context information, observations, and the nal
diagnosis. While, in case of the computing lab help desk
data, we had full knowledge of the three types of
information, we did not know which of the features in the
Irvine medical data sets were context variables and
which were observations. E ectively, we treated all
features in these data sets as observations. This is a
conservative assumption, as it is an additional
handicap for Marilyn in the experiments. The e ect of our
treatment of the medical data was that Marilyn
constructed two layer BN2O networks in these cases,
similarly to the QMR-DT model
Marilyn Results
We calculated Marilyn's cumulative accuracy after
each record, so as to know how this performance
develops as a function of the number of diagnostic cases
that the system has seen. Figure 4 shows the
average accuracy of Marilyn as a function of the number
of cases for each of the four data sets with range of
the curves (vertical bars) plotted for selected number
of records. The plots show that while Marilyn was
rather weak in the beginning (during the rst thirty
cases or so), it became quite accurate after roughly 70
to 100 cases (this varied per data set). Interestingly,
in case of the SPECT data set, Marilyn reached the
accuracy of over 60% after fewer than ten cases. In
all data sets, 40 or so cases were su cient to reach a
reasonable accuracy. This accuracy not only improved
over time but also improved reliably, as indicated by
smaller variance in the results of di erent random
orders of records. Interestingly, there is some similarity
between the plots of Marilyn's performance, as in
Figure 4, and the so called power curve of practice
in the psychology literature
Cumulative accuracy for the last record entered is the
nal accuracy result of Marilyn on the data set.
Marilyn's nal performance on the four data sets was
90.25%, 78.75%, 77.18%, and 69.95% for the Computer
Lab, SPECT Heart, Breast Cancer and Lymphography
data respectively (see the extreme right cumulative
performance in Figure 4). It has to be added that
in achieving this result Marilyn has seen (i.e., was
trained on) the average of 50% of the records. When
processing the rst case, Marilyn has seen zero prior
cases, when processing the 10th case, it has used only
9 preceding cases, when processing the last, nth case,
it has seen n 1 preceding cases. The average number
of training records is thus n=2.
In order to disambiguate the speci c procedure that
we used to obtain Marilyn's cumulative performance
from the capability of the learning function by
itself, we performed an experiment in which we allowed
Marilyn to learn from all available records
alongside with two Bayesian learning algorithms: (1) Naive
Bayes
The three data sets that we chose for our experiments
have been subject of experiments published in the
literature. The best accuracy result for SPECT heart
data with CLIP3 machine learning algorithm is 84%
Query-based diagnostic o ers passive, incremental construction of diagnostic models based on the interaction between a diagnostician and a computer-based diagnostic system. E ectively, this approach eliminates knowledge engineering, the main bottleneck in practical application of Bayesian networks.
While this idea is appealing, it has undergone only limited testing in practice. In this paper, we described a series of experiments that subject a prototype implementing passive, incremental model construction to a rigorous practical test. Data obtained from the Irvine repository made the evaluation fairly realistic. The results of our experiments show that a system like Marilyn is capable of giving reasonable suggestions after a modest number of observed cases. Performance in the order of 70-90% typically occurred not later than after roughly 40 cases. Even though this experiment o ers just a few data points and this type of systems need to be tested more in practice, we believe that the result is very promising and compares favorably with state of the art approaches based on learning.
This work has been supported by the National Institute of Health under grant number U01HL101066-01, the Government of the Kingdom of Thailand, the Air Force O ce of Scienti c Research grant FA9550{06{ 1{0243, and by Intel Research. Implementation of Marilyn is based on SMILE, a Bayesian inference engine developed at the Decision Systems Laboratory and available at http://genie.sis.pitt.edu/. We would like to express our thanks to the DSL members for their valuable suggestions. Special thanks go to Erik Pols, Mark Voortman and Adam Zagorecki.