Deep-EC2: A Non-Myopic Active Feature Acquisition Framework

Abstract

Active Feature Acquisition (AFA) addresses the problem of sequentially deciding which features to observe in order to maximise predictive accuracy while minimising acquisition cost. Non-myopic methods, which account for how an acquisition changes the value of later ones, typically rely on reinforcement learning (RL), with its reward design, rollouts, and hyperparameter sweeps. This thesis proposes Deep-EC2, an AFA framework that replaces reinforcement learning with supervised regression onto analytical targets derived from the Equivalence Class Edge Cutting (EC2) criterion, the only AFA objective known to be adaptive submodular. A value network learns to rank candidate features by their expected EC2 gain, estimated with a masked k-nearest-neighbour estimator over the training set, and a third training phase adapts the predictor to the subsets that the learned policy acquires. At inference, acquisition requires only greedy forward passes, with no rollout or planning. Experiments on eleven benchmarks—three synthetic gated tasks, the CUBE-NM context-feature benchmark, and seven real-world tabular datasets—compare Deep- EC2 with seven published AFA methods, the RL method Opportunistic Learning (OL), and a random reference, under identical splits, three seeds, and seed-paired significance tests. On CUBE-NM, Deep-EC2 acquires a context feature first on every instance, significantly outperforms every baseline including OL, and reaches perfect accuracy after 7–8 acquisitions. On the synthetic task Syn3 it acquires the gate first on every instance and is on par with the strongest non-RL baselines. On both benchmarks a budget-by-budget analysis reveals an invest-then-exploit signature— an early deficit incurred by acquiring an individually uninformative context feature or gate, repaid by significant mid-budget gains—the hallmark of non-myopic acquisition. On the real-world tabular data Deep-EC2 remains competitive, and adapting the predictor to the policy improves all eleven benchmarks. Training a model takes 8–18 minutes on the synthetic benchmarks, faster than OL on each of them and about six to eighty times cheaper once OL’s hyperparameter sweep is counted. Overall, the thesis shows that non-myopic acquisition can be obtained from a supervised value network trained on EC2 targets, at myopic inference cost and without reinforcement learning.