Abstract:
In its simplest form, the process of diagnosis is a decision-making process in which
the diagnostician performs a sequence of tests culminating in a diagnostic decision.
For example, a physician might perform a series of simple measurements (body tem-
perature, weight, etc.) and laboratory measurements (white blood count, CT scan,
MRI scan, etc.) in order to determine the disease of the patient. A diagnostic policy
is a complete description of the decision-making actions of a diagnostician under all
possible circumstances. This dissertation studies the problem of learning diagnostic
policies from training examples. An optimal diagnostic policy is one that minimizes
the expected total cost of diagnosing a patient, where the cost is composed of two
components: (a) measurement costs (the costs of performing various diagnostic tests)
and (b) misdiagnosis costs (the costs incurred when the patient is incorrectly diag-
nosed). The optimal policy must perform diagnostic tests until further measurements
do not reduce the expected total cost of diagnosis.
The dissertation investigates two families of algorithms for learning diagnostic
policies: greedy methods and methods based on the AO* algorithm for systematic
search. Previous work in supervised learning constructed greedy diagnostic policies
that either ignored all costs or considered only measurement costs or only misdiag-
nosis costs. This research recognizes the practical importance of costs incurred by performing measurements and by making incorrect diagnoses and studies the tradeo
between them. This dissertation develops improved greedy methods. It also intro-
duces a new family of learning algorithms based on systematic search. Systematic
search has previously been regarded as computationally infeasible for learning diag-
nostic policies. However, this dissertation describes an admissible heuristic for AO*
that enables it to prune large parts of the search space. In addition, the dissertation
shows that policies with better performance on an independent test set are learned
when the AO* method is regularized in order to reduce over tting.
Experimental studies on benchmark data sets show that in most cases the sys-
tematic search methods produce better diagnostic policies than the greedy methods.
Hence, these AO*-based methods are recommended for learning diagnostic policies
that seek to minimize the expected total cost of diagnosis.
