Learning Diagnostic Policies from Examples by Systematic Search
  A diagnostic policy specifies what test to perform next, based on the results
of previous tests, and when to stop and make a diagnosis. Cost-sensitive
diagnostic policies perform tradeoffs between (a) the cost of tests and (b) the
cost of misdiagnoses. An optimal diagnostic policy minimizes the expected total
cost. We formalize this diagnosis process as a Markov Decision Process (MDP).
We investigate two types of algorithms for solving this MDP: systematic search
based on AO* algorithm and greedy search (particularly the Value of Information
method). We investigate the issue of learning the MDP probabilities from
examples, but only as they are relevant to the search for good policies. We do
not learn nor assume a Bayesian network for the diagnosis process. Regularizers
are developed to control overfitting and speed up the search. This research is
the first that integrates overfitting prevention into systematic search. The
paper has two contributions: it discusses the factors that make systematic
search feasible for diagnosis, and it shows experimentally, on benchmark data
sets, that systematic search methods produce better diagnostic policies than
greedy methods.
