Article: Integrating Learning from Examples into the Search for Diagnostic Policies

Skip to first unread message

Aug 26, 2005, 9:24:22 PM8/26/05
JAIR is pleased to announce the publication of the following article:

Bayer-Zubek, V. and Dietterich, T.G. (2005)
"Integrating Learning from Examples into the Search for Diagnostic
Volume 24, pages 263-303.

For quick access via your WWW browser, use this URL:

This paper studies the problem of learning diagnostic policies from
training examples. A diagnostic policy is a complete description of
the decision-making actions of a diagnostician (i.e., tests followed
by a diagnostic decision) for all possible combinations of test
results. An optimal diagnostic policy is one that minimizes the
expected total cost, which is the sum of measurement costs and
misdiagnosis costs. In most diagnostic settings, there is a tradeoff
between these two kinds of costs.
This paper formalizes diagnostic decision making as a Markov Decision
Process (MDP). The paper introduces a new family of systematic search
algorithms based on the AO* algorithm to solve this MDP. To make
AO* efficient, the paper describes an admissible heuristic that
enables AO* to prune large parts of the search space. The paper
also introduces several greedy algorithms including some improvements
over previously-published methods. The paper then addresses the
question of learning diagnostic policies from examples. When the
probabilities of diseases and test results are computed from training
data, there is a great danger of overfitting. To reduce overfitting,
regularizers are integrated into the search algorithms. Finally, the
paper compares the proposed methods on five benchmark diagnostic data
sets. The studies show that in most cases the systematic search
methods produce better diagnostic policies than the greedy methods.
In addition, the studies show that for training sets of realistic
size, the systematic search algorithms are practical on today's
desktop computers.

The article is available via:

-- (also see

-- World Wide Web: The URL for our World Wide Web server is
For direct access to this article and related files try:

-- Anonymous FTP from Carnegie-Mellon University (USA):
The compressed PostScript file is named

For more information about JAIR, visit our WWW or FTP sites, or

Steven Minton
JAIR Managing Editor

Reply all
Reply to author
0 new messages