Opportunistic Learning: Budgeted Cost-Sensitive Learning from Data Streams

Mohammad Kachuee, Orpaz Goldstein, Kimmo Kärkkäinen, Sajad Darabi, Majid Sarrafzadeh

In many real-world machine learning applications, data isn't free. Acquiring features—such as running medical tests, querying paid APIs, or gathering complex sensor readings—costs time, money, or energy. Standard machine learning models often assume that all features are available for free at both training and test time. However, in fields like medicine, a doctor doesn't order every possible test (like an MRI, extensive blood work, or genetic sequencing) for every patient. Instead, they start with cheap information, such as age and basic symptoms, and incrementally order expensive tests only if they are likely to change the diagnosis.

To address this, researchers have introduced Opportunistic Learning (OL), a framework that uses Reinforcement Learning (RL) to dynamically "buy" the most informative features for each specific data point. By using prediction uncertainty as a reward signal, the model learns to make highly accurate predictions while staying strictly within a defined budget.

The Challenge of Cost-Sensitive Learning

Existing methods for "cost-sensitive learning" often fall into two traps:

  1. Static Selection: They pick a fixed subset of features for all samples, ignoring that different patients or data points might need different information.
  2. Hard-to-Tune Trade-offs: They often require complex hyperparameters to balance accuracy versus cost, making them difficult to deploy in changing environments.

The OL framework tackles the challenge of budgeted, cost-sensitive feature acquisition in a "stream" setting, where the model must learn and make decisions on the fly as data arrives.

A Reinforcement Learning Approach to Feature Acquisition

The authors frame feature acquisition as an RL problem. The agent starts with zero features and must decide which feature to "purchase" next based on its potential value.

The Uncertainty-Based Reward Function

The paper's most novel contribution is its reward function. Instead of a generic reward for accuracy, the reward is defined as the change in prediction certainty divided by the cost of the feature. If a feature significantly reduces the model's doubt, it is deemed worth the price.

To avoid the "overconfidence" common in standard neural networks (where standard softmax outputs can be misleading regarding their own certainty), the authors use Monte Carlo (MC) Dropout. By running multiple forward passes with dropout enabled, they obtain a distribution of predictions. The variance in these predictions serves as a robust, calibrated measure of uncertainty.

Dual-Network Architecture

The system utilizes a dual-network architecture to balance prediction and feature evaluation:

  • P-Network (Predictor): Responsible for the actual classification task.
  • Q-Network (Value Estimator): A Deep Q-Network (DQN) that predicts the "value" of acquiring each missing feature.
Dual-network architecture showing the Predictor (P-Network) and Value Estimator (Q-Network) sharing representations.

To make training faster and more stable, the Q-Network "borrows" the internal representations (hidden layers) of the P-Network. This representation sharing allows the feature-buying agent to benefit from the patterns the classifier has already learned, significantly speeding up convergence.

Key Insights and Results

The model was evaluated on three distinct datasets: the classic MNIST dataset (treated as a stream where each pixel has a cost), the Yahoo Learning to Rank dataset (where features have varying computational costs), and a real-world Diabetes dataset (NHANES) containing 45 features with realistic medical costs assigned by an expert.

Context-Aware Prioritization

The OL framework successfully learns that the "value" of a feature isn't static. For instance, a blood sugar test is extremely valuable if a patient is symptomatic but might be a waste of money if other indicators already confirm a diagnosis. The Q-Network learns this context-aware priority dynamically. Furthermore, using the delta in uncertainty as a reward signal naturally handles the cost-accuracy trade-off without needing a "magic" hyperparameter.

Superior Accuracy-per-Dollar

Across the board, the OL method achieved higher accuracy at significantly lower costs compared to state-of-the-art baselines like RADIN and GreedyMiser.

Accuracy vs. Acquisition Cost on the Diabetes dataset, demonstrating OL's superior performance at lower budgets.

On the medical dataset, the model learned to prioritize cheap demographic data first, only "buying" expensive lab results when absolutely necessary. It vastly outperformed exhaustive sensitivity-based methods. Additionally, because the model generates a complete "accuracy vs. cost" curve in a single training run, it was roughly 10 times faster to evaluate than traditional RL methods that require retraining for every different budget level.

Limitations and Future Directions

While highly effective, the framework does have limitations:

  • Computational Overhead: While the model saves on feature acquisition costs, the use of MC Dropout (which requires multiple forward passes at test time) increases computational cost. This could be a bottleneck for ultra-low-latency applications.
  • Feature Independence: The current formulation treats features as independent acquisitions. In reality, some features come in "bundles" (e.g., a single blood draw provides multiple metrics). While the authors note that bundles are possible to implement, the primary experiments focus on individual features.

Ultimately, Opportunistic Learning presents a highly efficient, context-aware approach to machine learning in environments where data is expensive, paving the way for smarter, more cost-effective AI systems in healthcare, sensor networks, and beyond.

Summary updated

Abstract

In many real-world learning scenarios, features are only acquirable at a cost constrained under a budget. In this paper, we propose a novel approach for cost-sensitive feature acquisition at the prediction-time. The suggested method acquires features incrementally based on a context-aware feature-value function. We formulate the problem in the reinforcement learning paradigm, and introduce a reward function based on the utility of each feature. Specifically, MC dropout sampling is used to measure expected variations of the model uncertainty which is used as a feature-value function. Furthermore, we suggest sharing representations between the class predictor and value function estimator networks. The suggested approach is completely online and is readily applicable to stream learning setups. The solution is evaluated on three different datasets including the well-known MNIST dataset as a benchmark as well as two cost-sensitive datasets: Yahoo Learning to Rank and a dataset in the medical domain for diabetes classification. According to the results, the proposed method is able to efficiently acquire features and make accurate predictions.
BibTeX
@inproceedings{kachuee2019opportunistic,
  author = {Mohammad Kachuee and Orpaz Goldstein and Kimmo Kärkkäinen and Sajad Darabi and Majid Sarrafzadeh},
  title = {{Opportunistic Learning: Budgeted Cost-Sensitive Learning from Data Streams}},
  booktitle = {International Conference on Learning Representations},
  year = {2019},
  url = {https://openreview.net/forum?id=30yasTl-WyS},
}
Figure