Breaking Boundaries Between Induction Time and Diagnosis Time Active Information Acquisition

Ashish Kapoor, Eric HorvitzNeurIPS 2009 · OpenReview

TL;DR

Traditionally, machine learning separates "learning" (building a model from data) and "diagnosis" (using that model to predict a specific case). This paper breaks that wall by introducing a unified framework that treats both as a single information-gathering problem. By strategically choosing whether to fill gaps in the training data or perform more tests on a current patient, the system achieves higher diagnostic accuracy at a significantly lower cost.

What Problem Does This Paper Address?

Imagine a doctor trying to diagnose a patient. The doctor has a limited budget—perhaps time, money, or the patient's tolerance for invasive tests. Usually, the doctor uses a pre-existing medical model to decide which tests to run on this specific patient. This is "diagnosis-time" information acquisition.

Meanwhile, researchers elsewhere are doing "active learning" (induction-time acquisition), deciding which historical records to complete to make the general model better.

Conceptual framework

The authors argue that this separation is inefficient. In many real-world scenarios, your training data is full of holes (missing features or labels). If you have a budget to acquire new information, is it better to spend it on a new test for the current patient, or on "cleaning up" a specific part of your training database that would make your model much more certain about the current case? This paper provides the mathematical framework to make that choice.

Methods

The authors propose a Bayesian approach that models the statistical dependencies between all data points—both training and test cases—simultaneously.

  • Joint Modeling: Instead of treating the predictive model as a fixed entity, they treat the model parameters ($\lambda$) as random variables. They marginalize over these parameters to see how different features (from any case) directly affect the prediction of the test case.
  • Boltzmann Machines: They represent the data using a Markov Random Field (specifically a Boltzmann machine) to capture pairwise relationships between features and labels.
  • Return on Information (ROI): To decide what data to "buy" next, they use a greedy selection criterion called ROI. Unlike the standard Value of Information (VOI), which requires costs and benefits to be in the same "currency" (like dollars), ROI measures the Information Gain per unit cost. This allows for a more flexible trade-off between the cost of a lab test and the cost of labeling a historical record.
  • Approximation Techniques: Because exact inference in these models is computationally "hard" (NP-hard), they use Laplace approximation and Loopy Belief Propagation to estimate the posterior distributions and make the system tractable for real-world use.

Datasets

The researchers evaluated their framework on three distinct types of data:

  1. Synthetic Boolean Data: A controlled environment with 14 features (some informative, some purely random) to test the basic logic of the algorithm.
  2. Pathfinder Data: A real-world medical dataset for diagnosing lymph-node diseases. It contains histological features viewed under microscopes.
  3. Congressional Voting Records: A dataset of U.S. House of Representatives members, where the goal is to predict party affiliation (Democrat vs. Republican) based on 16 key votes, many of which are missing in the historical record.

Key Insights and Ideas

  • The "Aha!" Moment: The most striking insight is that investing in the past can improve the present. Sometimes, the most cost-effective way to understand the patient in front of you isn't to poke them with another needle, but to spend that "budget" to find out the missing outcome of a similar patient from five years ago.
  • Breaking the Fixed-Model Assumption: Most AI systems assume the model is "done" once it's deployed. This paper suggests that learning should be a continuous, targeted process driven by the specific needs of the current diagnostic challenge.
  • Fine-Grained Triage: The unified approach allows for "parallel deliberation." The system looks at every missing bit of data in the entire ecosystem (training and test) and asks, "Which single bit of information, if revealed, reduces my uncertainty about this specific case the most for the least cost?"

Key Results

The authors compared their unified "Diagnosis+Induction" strategy against strategies that only did one or the other.

Accuracy vs Cost
  • Superior Accuracy-to-Cost Ratio: In all three datasets, the unified approach reached higher classification accuracy much faster (at lower cost) than the separate strategies.
  • Efficiency: On the synthetic data, the unified approach leveled off to maximum performance almost immediately, while "Diagnosis-only" or "Random" strategies lagged significantly behind.
  • Information Sourcing: On the Pathfinder (medical) data, the system showed a sophisticated behavior: it prioritized acquiring labels for training cases because they were highly informative, effectively "teaching" itself the most relevant parts of medical history to solve the current case.

Limitations and Future Work

  • Computational Complexity: While the authors used approximations like Loopy BP, the process of repeatedly calculating ROI for every missing bit of data is still computationally expensive. Scaling this to datasets with millions of records would be a challenge.
  • Binary Constraints: The current implementation focuses on binary features (0 or 1). Extending this to continuous data (like blood pressure or age) would require more complex probability models.
  • Myopic Selection: The algorithm is "greedy," meaning it only looks one step ahead. The authors mention that "non-myopic" extensions (looking multiple steps ahead) are a promising but difficult future direction.
  • Single vs. Stream: The paper primarily focuses on a single diagnostic challenge. Future work could explore how this works when a continuous stream of different patients is arriving at a clinic.

Summary updated

Abstract

There has been a clear distinction between induction or training time and diagnosis time active information acquisition. While active learning during induction focuses on acquiring data that promises to provide the best classification model, the goal at diagnosis time focuses completely on next features to observe about the test case at hand in order to make better predictions about the case. We introduce a model and inferential methods that breaks this distinction. The methods can be used to extend case libraries under a budget but, more fundamentally, provide a framework for guiding agents to collect data under scarce resources, focused by diagnostic challenges. This extension to active learning leads to a new class of policies for real-time diagnosis, where recommended information-gathering sequences include actions that simultaneously seek new data for the case at hand and for cases in the training set.
BibTeX
@inproceedings{kapoor2009breaking,
  author = {Ashish Kapoor and Eric Horvitz},
  title = {{Breaking Boundaries Between Induction Time and Diagnosis Time Active Information Acquisition}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=Sk-FJOWObB},
}
Figure