Abstract
Given a set of observations, feature acquisition is about finding the subset of unobserved features which would enhance accuracy. Such problems have been explored in a sequential setting in prior work. Here, the model receives feedback from every new feature acquired and chooses to explore more features or to predict. However, sequential acquisition is not feasible in some settings where time is of essence. We consider the problem of feature acquisition in batch, where the subset of features to be queried in batch is chosen based on the currently observed features, and then acquired as a batch, followed by prediction. We solve this problem using several technical innovations. First, we use a feature generator to draw a subset of the synthetic features for some examples, which reduces the cost of oracle queries. Second, to make the feature acquisition problem tractable for the large heterogeneous observed features, we partition the data into buckets, by borrowing tools from locality sensitive hashing and then train a mixture of experts model. Third, we design a tractable lower bound of the original objective. We use a greedy algorithm combined with model training to solve the underlying problem. Experiments with four datasets show that our approach outperforms these methods in terms of trade-off between accuracy and feature acquisition cost.
Introduction
In many real-world machine learning applications, models must make predictions based on an incomplete set of initial features. To improve confidence, the system can choose to "acquire" more features—for instance, a clinician ordering specific blood tests based on initial symptoms. While prior research has focused on sequential acquisition, this is often impractical in time-sensitive domains like healthcare. This paper addresses batch feature acquisition, where the model must decide on a subset of missing features to query simultaneously based on initial data. This task is computationally challenging due to the massive space of feature combinations and the coupling of selection with model training.
Methodology: The GENEX Framework
The authors propose GENEX (Generator Assisted Mixture of Experts), which introduces three key technical innovations:
1. Feature Generators for Cost Reduction
Instead of querying all desired features from an expensive "oracle," GENEX employs a pre-trained generative model ($\beta$-VAE) to synthesize a subset of them. If the classifier achieves high confidence using these "hallucinated" features, it accepts them; otherwise, it falls back to an oracle query. This hybrid approach significantly reduces the total cost of acquisition.
2. Random Hyperplane Clustering for Mixture of Experts
Handling heterogeneous observed features across instances is difficult for a single model. GENEX partitions data into "buckets" to train specialized experts. Unlike standard K-Means, which can lead to severe bucket imbalance, GENEX uses Random Hyperplane (RH) based Approximate Nearest Neighbor clustering. This geometric approach ensures a more uniform data distribution across the Mixture of Experts.
3. Tractable Optimization via Greedy Algorithms
Jointly optimizing model parameters and discrete feature sets is NP-hard. The authors derive a surrogate loss function and decouple the optimization. By extending concepts of partial monotonicity and weak submodularity, they provide a mathematical guarantee that their greedy selection strategy yields near-optimal feature subsets.
Experimental Results
The GENEX framework was evaluated on four datasets: Disease Prediction (DP), MNIST, CIFAR100, and TinyImagenet (TI).
Superior Accuracy-Cost Tradeoff
GENEX consistently outperforms state-of-the-art baselines such as JAFA, EDDI, and ACFlow. As shown in Figure 1, GENEX (red line) maintains higher classification accuracy across varying levels of feature acquisition budgets on the CIFAR100 dataset compared to other methods like CwCF and DiFA.
Cost Reduction through Generation
A critical finding is the efficiency gained by using generated features. Ablation studies demonstrate that the variant utilizing the generator ($V \subset U$) achieves comparable accuracy to an oracle-only variant ($V=U$) while requiring 3 to 5 times fewer real-world queries. This is visualized in Figure 2, where the fraction of features acquired from the oracle is significantly lower for the generator-assisted model at the same accuracy levels across the DP and TI datasets.
Conclusion
GENEX provides a robust solution for batch feature acquisition by leveraging generative models and balanced mixture-of-experts architectures. By drastically reducing oracle query costs while maintaining high accuracy, it offers a practical path forward for time-sensitive applications in healthcare and beyond. Future work may involve refining the greedy strategy with exploration-exploitation mechanics to further optimize feature selection.
Summary updated