Ph.D. thesis available: Learning Cost-Sensitive Diagnostic Policies from Data

Tue Sep 9 01:25:56 EDT 2003

Dear Connectionists,

My Ph.D. thesis: Learning Cost-Sensitive Diagnostic Policies from Data

is available to download from
http://eecs.oregonstate.edu/library/?call=2003-13

Advisor: Prof. Tom Dietterich, Oregon State University

The abstract and table of context follow.

Best regards,
Valentina Bayer Zubek
http://web.engr.oregonstate.edu/~bayer/

-------------

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 temperature, 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 diagnosed).  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 misdiagnosis costs.
This research recognizes the practical importance of costs incurred
by performing measurements and
by making incorrect diagnoses and studies the tradeoff between them.
This dissertation develops improved greedy methods.  It also introduces a
new family of learning algorithms based on systematic search.  Systematic
search has previously been regarded as computationally infeasible for
learning diagnostic 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 overfitting.

Experimental studies on benchmark data sets show that in most cases the
systematic 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.

--------------

Table of Contents:

Chapter 1:Introduction

Chapter 2: Cost-sensitive Learning (CSL)
    2.1 Supervised Learning
    2.2 Markov Decision Problems (MDPs)
    2.3 Formal Description of the Cost-sensitive Learning Problem as an (Acyclic) MDP
    2.4 Example of Diagnostic Policies
    2.5 Assumptions and Extensions of Our Cost-sensitive Learning Framework
	2.5.1 Complex Attribute Costs and Misclassification Costs
        2.5.2 Complex Actions
        2.5.3 CSL Problem Changes in Time
        2.5.4 Missing Attribute Values
        2.5.5 Multiple Classes
        2.5.6 Continuous Attributes
        2.5.7 Objective Function
    2.6 Literature Review for the Cost-sensitive Learning Problem in Machine Learning
    2.7 Related Work in Decision-theoretic Analysis
    2.8 Summary

Chapter 3: Greedy Search for Diagnostic Policies
    3.1 General Description of Greedy Algorithms
    3.2 InfoGainCost Methods
    3.3 Modified InfoGainCost Methods (MC+InfoGainCost)
    3.4 One-step Value of Information (VOI)
    3.5 Implementation Details for Greedy Algorithms
    3.6 Summary

Chapter 4: Systematic Search for Diagnostic Policies
    4.1 AND/OR Graphs
    4.2 AO* Algorithm
    	4.2.1 Overview of the AO* Algorithm
    	4.2.2 Admissible Heuristic
        4.2.3 Optimistic Values and Optimistic Policy
        4.2.4 Realistic Values and Realistic Policy
        4.2.5 Selecting a Node for Expansion
        4.2.6 Our Implementation of AO* (High Level)
        4.2.7 AO* for CSL Problems, With an Admissible Heuristic, Converges to the Optimal Value Function V*
        4.2.8 Pseudocode and Implementation Details for the AO* Algorithm
    4.3 Regularizers
        4.3.1 Memory Limit
        4.3.2 Laplace Correction (L)
        4.3.3 Statistical Pruning (SP)
        4.3.4 Pessimistic Post-Pruning (PPP) Based on Misclassification Costs
        4.3.5 Early Stopping (ES)
        4.3.6 Dynamic Method
        4.3.7 AND/OR Graph Initialized with a Known Policy
        4.3.8 Combining Regularizers
    4.4 Review of AO* Literature
        4.4.1 AO* Relation with A*
        4.4.2 AO* Notations, Implementations, and Relation with Branch-and-Bound
        4.4.3 Theoretical Results on AO*
        4.4.4 POMDPs
        4.4.5 Decision-theoretic Analysis
        4.4.6 Test Sequencing Problem
        4.4.7 Relation of CSL with Reinforcement Learning
    4.5 Summary

Chapter 5: Experimental Studies
    5.1 Experimental Setup
	5.1.1 UCI Domains
        5.1.2 Setting the Misclassification Costs (MC)
        5.1.3 Training Data, Test Data, Memory Limit
        5.1.4 Notations for the Cost-Sensitive Algorithms
        5.1.5 Evaluation Methods
    5.2 Overfitting
    5.3 Results
        5.3.1 Laplace Correction Improves All Algorithms
        5.3.2 Results on the bupa Domain
        5.3.3 Results on the pima Domain
        5.3.4 Results on the heart Domain
        5.3.5 Results on the breast-cancer Domain
        5.3.6 Results on the spect Domain
        5.3.7 Summary of Algorithms' Performance
    5.4 Discussion
        5.4.1 An Overall Score for Algorithms (Chess Metric)
        5.4.2 The Most Robust Algorithms
        5.4.3 Comparing The Most Robust Algorithms Against the Best Algorithm on Each Domain
        5.4.4 Summary of Discussion
        5.4.5 Insights Into the Algorithms' Performance
    5.5 Summary

Chapter 6: Conclusions and Future Work
    6.1 Contributions of This Dissertation
    6.2 Future Work
    6.3 Thesis Summary

Appendices

Appendix A: Details on Our AO* Implementation

Appendix B: More Information on the Experimental Studies
    B.1 Misclassification Costs Matrices for the UCI Domains
    B.2 Comparing the Worst Algorithms in the Systematic and Greedy Search Families
    B.3 Comparing AO* with All the Other Algorithms using BDeltaCost
    B.4 Results of Comparing Each Laplace-Corrected Algorithm with All the Other Laplace-corrected Algorithms, on Each Domain and Misclassification Cost Level (MC)
    B.5 Paired-Graphs Comparing the Best Algorithm on Each Domain with Our Recommended Algorithms