Greedy Information Maximization for Online Feature Selection
Authors: Ian Connick Covert
Wei Qiu
MingYu Lu
Na Yoon Kim
Su-In Lee
Venue: Submitted to ICLR 2023 (2023)
Keywords: Online learning
feature selection
greedy optimization
mutual information

Abstract: Feature selection is commonly used to reduce feature acquisition costs, but the standard approach is to train models with static feature subsets. Here, we consider the online feature selection problem, where the model can adaptively query features based on the presently available information. Online feature selection has mainly been viewed as a reinforcement learning problem, but we propose a simpler approach of greedily selecting features that maximize mutual information with the response variable. This intuitive idea is difficult to implement without perfect knowledge of the joint data distribution, so we propose a deep learning approach that recovers the greedy procedure when perfectly optimized. We apply our approach to numerous datasets and observe better performance than both RL-based and offline feature selection methods

Under review as a conference paper at ICLR 2023
GREEDY INFORMATION MAXIMIZATION FOR ACTIVE FEATURE ACQUISITION
Anonymous authors Paper under double-blind review
ABSTRACT
Feature selection commonly used to reduce feature acquisition costs, but the standard approach is to train models with static feature subsets. Here, we consider the active feature acquisition problem where the model sequentially queries fea- tures based on the presently available information. Active feature acquisition has frequently been addressed using reinforcement learning (RL), but we explore a simpler approach of greedily selecting features based on their conditional mutual information. This approach is theoretically appealing but difficult to implement introduce learning algorithm based amortized optimiza- tion that recovers the greedy policy when perfectly optimized. We find that the greedy method outperforms both RL-based and static feature selection methods across numerous datasets, which validates our approach as a simple but powerful baseline for this problem.
in practice,
INTRODUCTION
Machine learning models require informative inputs make accurate predictions, but model's input features can be costly to acquire. In settings where information is gathered sequentially, and particularly when obtaining features requires time money, it reasonable to query features adap- tively based on the presently available information. We refer to this as active feature acquisition (Saar-Tsechansky et al. 2009), and it has been considered by many works in the last decade (Dulac- Arnold et al.) 2011 Chen et al. 2015b Early et al., 2016a He et al. 2016a; Kachuee et al. 2018))
Feature selection with fixed feature sets (static feature selection) has received more attention (see reviews by Li et al. 2017: et al. 2018), but active approaches offer the potential for better perfor- mance given a fixed budget. This easy to see, because selecting the same features for all instances (e.g., all patients visiting a doctor's office) is one possible policy but likely suboptimal in many sit- uations. On the other hand, active approaches are also more challenging because they require both learning selection policy and making predictions with multiple feature sets.
Prior work has approached active feature acquisition in several ways, but often using reinforcement learning (RL) (Dulac-Arno)) et al., 2011 Shim al. 2018 Kachuee et al., 2018 Janisch et al.) 2019 Li & Oliva 2021). RL is a natural approach for sequential decision-maker
problems, but current methods are difficult to train and do not reliably outperform static feature selection (Hender- son et al. 2018 Erion et al. 2021). Our work therefore explores a simpler approach: sequentially selecting features based their conditional mutual information (CMT) with the response variable.
The greedy CMI approach is discussed in prior work (Fleuret, 2004 Chen et al. 2015b Ma et al., 2018), but it remains difficult to implement because it requires perfect knowledge of the joint data distribution. The focus of this work is therefore developing simple method to approximate the greedy policy, Our main insight is to leverage amortized optimization (Amos] 2022): by developing an optimization- based characterization of the greedy CMI policy. we design an end-to-end learning approach that recovers the policy when is perfectly optimized.
Our contributions in this work are the following:
'The problem is also sometimes referred sequential dynamic feature selection.

---

Under review as a conference paper at ICLR 2023
1. We develop optimization- based characterization of the locally optimal selection policy, and we show that this yields greedy selections based on CMI for classification problems. These preliminary results later provide the foundation for our learning approach.
2. We describe a procedure to implement the greedy policy given perfect knowledge of the data dis- tribution. While impractical, this procedure relates our approach to a prior CMI approximation (Ma et al. 2018) and shows that the greedy policy is special case of existing expected utility frameworks (Saar-T et al. 2009 Harly et al. (2066a).
3. We develop an amortized optimization approach to approximate the greedy policy using deep learning. Our method permits simple end-to-end learning via stochastic gradient descent, and we prove that objective recovers the greedy CMI policy when it is perfectly optimized.
We demonstrate the effectiveness of our approach on numerous datasets, and the results show that our method outperforms both RL-based and static feature selection methods. Overall, our work shows that greedy policy is a simple and powerful method for active feature acquisition.
2 PROBLEM FORMULATION
In this section, we introduce notation used throughout the paper and describe the active feature acquisition problem.
2.1 NOTATION
Let x denote a vector of input features and y a response variable for a supervised learning task. The input consists of d distinet features, subset of indices and x, {x, i E }} subset of features, Bold symbols x, y represent random variables, the symbols æ, y are possible values, and p(x, denotes the data distribution.
(xi,..., Xa). We use [d] (1, -.. d) to denote
Our goal is to design a policy that controls which features are selected. The feature selection policy can be viewed as function πt (x.)) E [d]. meaning that receives subset of features as its input and outputs the next feature index to query. The policy is accompanied by predictor fxx)) that can make predictions given the set of available features; example, is discrete then predictions lie in the probability simplex, f(x.)) A for K classes. The notation f(x,, U x;)) represents the prediction given the combined features Teu(1)- The paper initially considers policy and predictor functions that operate on feature subsets because these are simpler to analyze, Sec[Sintion 4fpropsses an implementation using a mask variable m E [0, 1jd where the functions operate on x O m.
2.2 ACTIVE FEATURE ACQUISITION
The goal of active feature acquisition is to select features with minimal budget that achieve max- imum predictive accuracy. Access to more features generally makes prediction easier, so the chal- lenge is selecting small number of informative features. There are multiple formulations for this problem, including non-uniform feature costs and different budgets for each sample (Kachuee et al., 2018), but focus the setting with fixed budget and uniform costs. Our goal is begin with no features for each data example, sequentially select feature set I, such that |s| = k for fixed k d, and make accurate predictions for the response y.
Given a loss function that measures the discrepancy between predictions and labels (() v). a natural scoring criterion is the expected loss after selecting features. The scoring is applied policy- predictor pair (π, f), and we define the score for fixed budget l as follows,
Tye , f) Ep(x.)) [e( (f(,, v))
where feature indices are chosen sequentially for each (x, y) according to in ((x,, ((xx)))))))) V-=)). Our goal is to minimize uk (TT, f). or equivalently to maximize our final predictive accuracy.
One approach is to frame this as a Markov decision process (MDP) and solve it using standard RL techniques, where π and if are trained to optimize a reward function based on eq. (1) Indeed, several works have designed such formulations (Dulac-Amol) Armold et al. 2011 Shim et al. 2018 Kachuee (et al., 2018 Janisch et al. 2019 Li & Oliva 2021). Our work instead focuses on simpler greedy approach, which has the benetits of being simpler to interpret and easier to learn in practice.
2

---

Under review as a conference paper at ICLR 2023
3 GREEDY INFORMATION MAXIMIZATION
In this section, we define a greedy approach to active feature acquisition and show that reduces to selecting features based their CMI with the response variable. We then describe the difficulty of estimating CMI in practice, which motivates our main approach introduced in Secciion
3.1 THE GREEDY POLICY
Greedy algorithms are characterized by making locally optimal choices, and the locally optimal ap- proach here is to sequentially select features that maximize the one-step performance improvement. At any point in the selection process, the greedy approach should select the next feature x, that is most helpful given the current features x,, regardless of the feature count |s] and budget k.
More precisely, we define the current greedy selection as the index that minimizes the expected prediction loss, similar eq. (1) but with single additional feature. The expected loss depends on the predictor f. but we are interested primarily in the best-case scenario where we use an optimal predictor. Fortunately, the loss lossmminimizing predictor can be defined independently of the policy т, assuming that features are selected without knowledge of the remaining features or response variable. We formalize this in the following proposition (see proofs in Appendix A).
When y is discrete and is cross-entropy loss, the loss-minimizing predictor f for any policy is the Bayes classifier, or (x, ply x.))
Proposition
Note that the above property does not hold in problems where selections are based on the entire feature set (Chen et al.] 2018 Yoon et al. 2018). Now, assuming that we use the Bayes classifier f as predictor, we define greedy active feature acquisition via a policy T that minimizes the expected prediction loss at each step, where the expectation is with respect to the unknown variables ()) and conditions on the observed features I.,-
Definition 1 (Greedy feature acquisition). The greedy feature acquisition approach is represented by a policy n" that has the following output given features T.:
t (x=) arg min Ey.x,1x. [e( (x. Ux:),y)]
we find that greedy policy has an intuitive probabilistic interpretation. We focus on the case where y is discrete and is cross-entropy loss, but our results can also be general- ized to regression problems Appenddxx A). In the classification case, we can show the following result.
Following Definition
Proposition 2. Given the features Te, the greedy policy x" selects the feature x; having maximum CMI with the response variable, or
x T'xx)) = max I(y;x; x.))
According to this result, we can understand the greedy policy as sequentially selecting features that provide maximum information about the response variable. We therefore refer to the policy " as performing greedy information maximization. We can alternatively understand it as performing greedy uncertainty minimization, because maximizing CMI with y is equivalent minimizing y's expected conditional entropy (Cover & Thomas, 2012):
arg max I(y: x; xx)) arg min Ex,/=, [H x:)].
Maximizing the additional information about y at each step intuitive and should be an effective approach in many problems. Prior work has discussed CMI for active feature acquisition (Fleuret, 2004 Chen et al. 2015b Ma et al.) 2018)), but a reliable implementation has not yet been developed because CMI is challenging to calculate in practice. We next discuss one possible approximation approach that requires perfect knowledge of the data distribution, and we later use the optimization- based results derived here to develop new learning method (Section 4).
Note that this differs from greedily following the Q-network in RI., because the estimated Q-values reflect the reward after multiple selection steps.
3

---

Under review as a conference paper at ICLR 2023
3.2 AN ITERATIVE IMPLEMENTATION
The greedy policy is trivial to implement if we can directly calculate the CMI [(y: xx), but this rarely the case in practice. Before introducing our main approach, we first describe a procedure to estimate CMI given access to the response distributions p(y X,) for all C [d] and the feature conditional distributions p(x; x²) for all s S [d] and E [d].
At any point in the selection procedure, given the current features we can iteratively score the features x, where & s as follows. First, we can sample multiple values for x; from its conditional distribution, or x! p(x; xz) for j E [n]. Next, we can generate Bayes optimal predictions for each sampled value, or ply | Iz, x:)) Finally, we can calculate the mean prediction and the mean KL divergence relative to the mean prediction, which yields the following selection criterion:
-- -
Σ DKL DEL (ply Ies xf) 1I TI Ely xz. =).
(5)
This per-feature score measures the variability among predictions and captures whether different x, values significantly affect y's conditional distribution. Selecting the next feature according to arg max; I coincides with the greedy policy due to the following limiting result (see dee/AAppedix A);
lim 1 = [y; X; x.)).
(6)
This procedure thus provides a simple way identify greedy selections by iteratively scoring fea- tures according to I,". Similar feature scoring ideas were explored in prior work (Chen et al. 20155a] Early et al., 2016aa b). but the implementation choices in these works prevented them from per- forming greedy information maximization. Our procedure can be viewed as special case of the expected utility frameworks from Ssaaa-Tsy et al. (2009); [aarly et al. (2016a), but with a carefully chosen predictor, utility measure, and sampling distribution for missing features 3
The iterative procedure is theoretically justified, but it is impractical because we typically lack access to p(y x.) and p(x, x.). We can instead use learned substitutes for each distribution, e.g., classifier that approximates f(x.) As p(y xx)) and a conditional generative model that approximates samples from p(x; x.). Ma et al. (2018) proposed an approach of this form, but it relies on modified variational autoencoders for generative modeling (Kingma et al., 2013). This approach is limited in practice for several reasons: the difficulty of training reliable generative models, the challenge of working with mixed continuous and categorical features (Ma et al. 2022), and the slow iterative scoring procedure. [Section therefore explores a different approach that avoids modeling feature conditional distributions p(x, x,) by directly learning to output the greedy selections.
3.3 GREEDY SUBOPTIMALITY
Before introducing our main approach, we briefly consider the performance gap between the greedy policy and the optimal selection procedure. By definition, the greedy approach cannot achieve better pair, or performance than the optimal min (T J) S (
x.f
We refer to the difference between the optimal and greedy scores as the greedy suboptimality gap, or G(p, k) ( f*) minl,,, 2t (TT, f). where the gap depends the data distribution p(x. and feature budget k. The greedy suboptimality gap is difficult to assess in practice, but we design several simple scenarios to illustrate that the gap can be large small.
Example When ls 1, the greedy and optimal policies are identical and G(p, k) = for all data distributions y)x,y). The gap becomes non-zero only when selecting k > features.
Example 2. Consider data distribution p(x,y) y) where consists of d independent Gaussian vari- ables x; ~ (O, )²), the variances are ordered as of > >... > oz and the response is defined as y Σi= X4. If we let E be squared error loss, then the greedy policy selects the features in order, or X1,.. ., Xjs, and the optimal policy selects the same features in arbitrary order. The gap is therefore G(p, k) 0 for all 1 < k S d.
In our approach, set the utility to the KI. divergence with the mean prediction, we assume the Bayes classifier, and we sample features from p(x; x.) rather than p(x.).
4

---

Under review as a conference paper at ICLR 2023
Example 3. Consider data distribution y)x.y) where consists of 10 independent Bernoulli variables X; ~ (ern(0.5) and the response is defined as y = xor (X,, Given a budget = 2, the optimal policy selects both x, and X2 and the optimal score is minf,a U2 (2 f) 0. In contrast, the greedy policy will fail to discover this because neither X1 nor X2 provide any information on their own. The greedy policy is indifferent among the features, and if fails to select both x1 and X2 then it has no information about y and we have G(p, 2) 2)- = log 2 (the entropy of a coin flip).
The third example illustrates the perils of following greedy approach: it fails to account for each selection's 's impact later the selection procedure. contrast, non-greedy policy can make sub- optimal selections that yield large improvements in later steps. We find that the greedy approach provides strong performance in practice (Section 6), but understanding the conditions that let us bound the suboptimality gap is important topic.
In the static feature selection context, numerous works have exploited weak submodularity to prove the effectiveness of greedy algorithms (Das & Kempel 2011: Elenberg et al., [017] 2018). The analogous notion of adaptive submodularity (Golovin & Krause 2011) does not apply to active feature acquisition based CMI, but Chen et al. (2015b) derived suboptimality bounds based on strict distributional assumptions. More general characterizations are an open topic for future work.
4 PROPOSED METHOD
We now introduce our main approach, practical implementation of the greedy selection policy trained using deep learning.
4.1 AN AMORTIZED OPTIMIZATION APPROACH
Instead of iteratively scoring features (Section 3.2p, propose to learn model that directly outputs the next greedy selection given the current features. Our approach can be learned using a dataset of labeled examples, and does not require annotations indicating the correct greedy selections. Rather, we cast the optimization- bbased characterization of the greedy CMI policy (Section 3.1) as an objective function be optimized by learnable network, leveraging an approach known as amortized optimization (Amos 2022).
First, because it facilitates gradient-based optimization, we now consider that the policy outputs a distribution over feature indices. With slight abuse of notation, this section lets the policy be function 77 (Ix,) Ad-1 which generalizes the previous definition ग (Ix,) E [d]. Using this stochastic policy, we can now formulate our objective function as follows.
Let the selection policy be parameterized by neural network ı (x,; Φ) and the predictor by a neural network fxx,; 0). Let p(s) represent a distribution over subsets with p(s) > 0 for all |s < d. Then, our objective function L(,, Φ) is defined as
C(0, .) = Ep(x,y) Ep(s) (i-T((x))) [((f(xs Ux; 0x,;
(8)
Intuitively. leq. (8) represennt generating a random feature set Xs, sampling a feature index according to ~ Λ (xx;: σ), and then measuring the loss of the prediction f(x. U x,; 0). Our objective thus optimizes for individual selections and predictions rather than the entire trajectory. which lets us build on earlier results from compSection 3] We describe this as an implementation of the greedy approach because recovers the greedy behavior if it is perfectly optimized. In the classification case, we can show the following result under mild assumption that there is a unique optimal selection.
Theorem 1.
When y is discrete and l cross-entropy loss, the global optimum of leg. (8) predictor that satisfies f(z 0²) = ply xz) and policy π (II;; x") that puts all probability mass on arg max, x x..).
If we relax the assumption of a unique optimal selection, the optimal policy is simply indifferent among the optimal indices. A similar result holds in the regression case, where can interpret the greedy policy as performing conditional variance minimization.
5

---

Under review as a conference paper at ICLR 2023
Policy
Predictor
Concrete
0
X
(
X
f(:00)
"
0
Update masked input
=0
X4
X
Repeat for selection steps
Figure 1: Diagram of our training approach. Left: features are selected by making repeated calls to the policy network using masked inputs. Right: predictions are made after each selection using the predictor network. Solid lines are backpropagated through when performing gradient descent.
When y is continuous and é is squared error loss, the global optimum of eg. (8) is predictor that satisfies fxx,;0") Ely xz) and policy x x(Ix::") that puts all probability mass Egg x.
Theorem 2.
on arg min; Ex, [Varly
Proofs for these results are in Appendix A] This approach has two key advantages over the iterative procedure from
from/Sectin Section 3.2 First, we avoid modeling the conditional distributions p(x; x,) for all
(s, Modeling these distributions is a difficult intermediate step, and our approach instead aims to directly output the optimal index. Second, our approach faster because each index is generated in single forward pass: selecting k features using the iterative procedure requires ((dk) scoring steps, but our approach requires only forward passes through the selector π (x+:
Furthermore, compared to policy learned by RL, the greedy approach is easier to learn. Our training procedure can be understood as a form of reward shaping (Sutton et al. 1998 Randlev & Alstrom 1998), where the reward accounts for the loss after each step and provides strong signal about whether each selection helpful. comparison, observing the reward only after selecting k features provides comparably weak signal to the policy network. RL methods generally face challenging exploration-exploiaaion trade-off, but learning the greedy policy is simpler hecause only requires finding the locally optimal choice among ((d) options at each step.
4.2 CONTINUOUS RELAXATION
Our objective yields the greedy selection policy when it is perfectly optimized, but C(O, 6) is diffi- cult optimize by gradient descent. In particular, gradients are difficult propagate through the policy network given a sampled index i ~ T [<.,; The REINFORCE trick (Williams) 1992) one way to get stochastic gradients, but high gradient variance can make ineffective in many problems. There is robust literature reducing gradient variance in this setting (Mnih & Gregor 2014 Tucker et al. 2017; Grathwohl et al. 2018), but we opt for a simple alternative: the Concrete distribution (Maddison et all.22116)
An index sampled according to i T(Z;: Φ) can be represented by a one-hot vector m E 10, indicating the chosen index, and with the Concrete distribution instead sample approximately one-hot vector in the probability simplex, or m E A d-1 This continuous relaxation lets us calculate gradients via the reparameterization trick (Maddison al., 2016 Jang et al., 2016). Relaxing the subset s C [d] to a continuous vector also requires relaxing the policy and predictor functions, so let these operate a masked input ær the element-wise product about whether features are zero or masked, we can also pass the mask as an input.
m. To avoid ambiguity
Training with the Concrete distribution also requires specifying temperature parameter 7 to control how discrete its samples are. Previous works have trained with a fixed temperature or annealed it over a pre-determined number of epochs (Chang al.) [017 Chen et al. 2018 Balm et al. 2019). but we instead train with sequence of values and perform early stopping at each step. his effectively removes the temperature and number of epochs as important hyperparameters. Our training procedure is summarized in Figure I and Algorithn I
There are also several optional steps that we found can improve optimization:
Parameters can be shared between the predictor and policy networks f(x: 6), n [x, Φ). This does not complicate their joint optimization, and learning a shared representation in the early network layers can in cases help the networks optimize faster.

---

Under review as a conference paper at ICLR 2023
Rather than training with random subset distribution p(s), generate subsets using features selected by the policy π (xx; o). This allows the models to focus on subsets likely to be encoun- tered at inference time, and it does not affect the globally optimal policy/predictor: gradients are not propagated between selections, so bothleq, (8) and this sampling approach treat each feature set as independent optimization problem, only with different weights (see Appendixx D).
We pre-train the predictor f(x; 0) using random subsets before jointly training the policy- predictor pair. This works better than optimizing [(0, Φ) from a random initialization, because random predictor f(x: () provides no signal to т T(x; σ) about which features are useful.
5 RELATED WORK
Prior work has frequently addressed active feature acquisition using RL. Among these, Dulac- Arnold et al. (2011); Shim et 2018) Danisch et al. (2019): Li & Oliva (202)) optimize a reward based on the final prediction accuracy, and Kachuee et al. (2018) use reward that accounts for prediction uncertainty. RL is a natural approach for sequential decision -akinn problems, but it can be difficult to learn in practice: RL requires complex architectures and training routines, is slow to converge and is highly sensitive to its initialization (Henderson et al. 2018). As a result, RL does not reliably outperform static feature selection methods in practice (Erion et al. 2021)
Several other approaches include imitation learning (He et al.) 2012 2016a) and iterative feature
scoring methods (Melville et al.] 20044; Ssar--ssechansk al., 2009 Chen et al.) [2015a] Early et al. 2016bla). a). Imitation learning casts active feature acquisition as supervised classification; in comparison, our training approach bypasses the need for an oracle policy. Most existing iterative techniques are greedy methods, like ours, but they use scoring heuristics unrelated to maximizing CMI (Section 3.2). Two iterative feature scoring methods are designed calculate CMI, but they suffer from practical limitations: [Fleuret (2004) assumes binary features, and et al. (2018) relies on difficult-to-train generative models. Our approach is simpler, faster and more flexible, because the selection logic is contained within learned policy network. Finally, Chen et al. (2015b) study the CMI approach but from a theoretical rather than learning perspective.
Static feature selection is a long-standing problem (Guyon & Elisseefi 2003 Cai et al. 2018 There are no default approaches for neural networks, but several options include ranking features by local global importance scores (Breiman 2001 Shrikumar al. 2017 Sundararajan et al.
2017] Covert et al.] 2020) and differentiable feature selection: several prior works have leveraged
continuous rel relaxations learn feature selection strategies by gradient descent. For example. Chang
jet al. (0117) Balin et al. ):11)): Yamada et al. (2020): Lindenbaum et al. (2021): )): [ee et al. (2021) perform static feature selection, and Chen al. (2018); Jethani et al. (202) perform instance- feature selection given all the features. Our work uses a similar optimization technique but in a different context, and our method learns selection policy rather than static selection layer.
EXPERIMENTS
We now demonstrate the use of our greedy approach on several datasets We first explore tabular datasets of various sizes, including four medical diagnosis tasks, and we then consider two image classification datasets. Several of the tasks are natural candidates for active feature acquisition, and the remaining ones serve as useful tasks to test the effectiveness of our approach.
As comparisons for our method, we use several active and static baselines. To ensure consistent comparisons, we only use methods applicable to neural networks. As static baselines, we use two methods that rank feature importance based on model accuracy, permutation tests (Breiman) 2001) and SAGE (Covert et al. 2020). We also use two methods that quantify importance on per- prediction level, DeepLift (Shrikumar et al., 2017) and Integrated Gradients (Sundararajan et al.) 2017). We then use supervised version of Concrete Autoencoders (Balm et 20.1), differen- tiable feature selection method. As active baselines, we use the RL-based Opportunistic Learning (OL) approach (Kachuee et al. 22018), and we follow the authors' implementation with minor mod- ifications (Appendxx C). Finally, we use a version of our iterative procedure from [Section 3.2 for simplicity, we train predictor with random feature subsets (similar to our predictor pre-training
Link to code removed for anonymity.

---

Under review as a conference paper at ICLR 2023
Bleeding AUROC Comparison
Respiratory AUROC Comparison
Fluld AUROC Comparison
0.75
0.70
0.60
0.65
0.75
0.75
0.60
0.70
10
15
20
0.65
25
10
20
# Selected Features
Selected Features
# +eelectdd Festures
IntGrad DeepLift
SAGE
Opportunistic (OL)
Porm Test
Rerative
Greedy Active (Durs)
Figure 2: Evaluating the greedy active approach on three medical diagnosis tasks.
in Section 4.2 we sample values from their marginal rather than conditional distributions, and we calculate the scoring criterion in eq. (5) using 128 samples.
6.1 TABULAR DATASETS
We first applied our method to three medical diagnosis tasks derived from an emergency medicine setting. The tasks involve predicting a patient's bleeding risk via a low fibrinogen concentration (bleeding), whether the patient requires endotracheal intubation for respiratory support (respiratory), and whether the patient will be responsive to fluid resuscitation (fluid). [Appendix B provides more dataset details. In each scenario, gathering all possible inputs is challenging due to time and resource constraints, thus making active feature acquisition a natural solution.
Figure 2 shows the results of applying each method with various feature budgets. We use fully connected architectures for all methods, and we use dropout to reduce overfitting (Srivastava et al., 2014). The classification accuracy is measured via AUROC, and the greedy method achieves the best results at nearly all feature budgets for all three tasks. Among the baselines, several static methods sometimes close, but OL provides unstable results and the iterative method is only competitive on the fluid task. The greedy method's advantage is largest when selecting a small number of features, and it becomes narrower once the accuracy saturates.
Next, we conducted experiments using three publicly available tabular datasets: spam classification (Dua & Graff 2017). particle identification (MiniBooNE) (Roe al. (2055) and diabetes diagnosis Miller 1973). The diabetes task is natural application for active feature acquisition and was used in prior work (Kachuee et al., 2018). We again tested various feature numbers, and (Figure 5 shooss plots of the AUROC for each budget; on these tasks, the greedy method is most accurate for all numbers of features. TTall 1 summarizes the results via the mean AUROC across = 1,..., 10 features, emphasizing the benefits of the greedy method across all six datasets. (Appeddxx E. also shows plots demonstrating the variability of selections across samples for each dataset.
The results on these datasets reveal that active methods can often be outperformed by static methods. Interestingly, this point was not highlighted in prior work because strong static selection methods were not always used (Kachuee et al., 2018 Janisch et al. 2019). Active methods are in principle capable of performing better, so the sub-par results from OL and the iterative method underscore the difficulty of learning both selection policy and prediction function for multiple feature sets. In our experiments across these six datasets, ours is the only active method to do both successfully. The greedy approach trains more easily for the reasons described in Section 4, and we suspect that OL has difficulty optimizing for larger feature budgets in particular due to its delayed rewards.
Table I: AUROC averaged across budgets of 1-10 features (+: one standard deviation).
Spam
MiniBooNE
Diabetes
Bleeding
Respiratory
Fluid
IntGrad
88.08 0.36
86.77
1 0.86
88.99 1 0.34
69.27 1.18
80.42
0.18
78.31 0.82
Statie
DeepLiit
89.02 1.51
86:33
0.20
94.89
0.21
67.52
0.27
77.66
+ 0.31
77.37 0.15
SAGE
90.45 + 0.65
91.57 0.10
95
+ 0.03
70.31
+ 0.38
82.20
+ 0.37
79.60 + 0.58
0.34
0.15
95.50
0.02
68.29
79.24
CAE
92.46 1 0.29
93.04 1 0.16
95.88 1 0.11
70.03 1 0.37
82.78 1. 0.33
76.39 1 1.60
Active
Lterative
87.00 + 1.40
92.17
95.61
70.63
78.85
84.33
Opportunistic (OL)
85.93 1: 0.22
69.22 0.73
83.06 1: 0.93
60.60 1: 0.62
74.44 1: 0.48
78.12
0.35
Greedly Active (Ours)
94.22 0.20
94.39
96.04
72.83 0.31
84.52
86.00 0.31
8

---

Under review as a conference paper at ICLR 2023
MNIST Accuracy Comparison
GIAR-100 Accuracy Comparison
1.0
0.8
Tap-1 Accuraci
0.0
Top Accuracy
IntGrad
CAE
0.5
0.4
DeepLift
Opporturistic (OL)
Center Crop
SAGE
Greedy Active (Ours)
0.4
Random Mask
Perm Test
Greedy Active (Ours)
10
20
30
40
50
10
15
20
25
30
Selected Pixels
Selected Patches
Home
Trurk
Nitiane
Sh
Frog
Home
Deer
Bog
30%
99.85%
Figure 3: Greedy active feature acquisition for image classification. Top left: accuracy comparison on MNIST. Top right: accuracy comparison on CIFAR-10. Bottom: example selections and predic- tions for the greedy approach given 10 out of 64 patches for CIFAR-10 images.
6.2 IMAGE CLASSIFICATION DATASETS
Next, considered two standard image classification datasets: MNIST (LeCun et al. 1998) and CIFAR-10 (Krizhevsky et al.] 2009). Our goal to begin with a blank image, sequentially reveal multiple pixels or patches, and ultimately make classification using small portion of the image. This is not an obvious use case for active feature acquisition, but represents challenging problem for our method, and similar tasks have been considered in several earlier works (Karayev et al.,
2012 Mnih et al. 2014 Early et al. 2016a Janisch et al. 2019).
fully connected architectures for both the policy and predictor, and treat pixels as individual features (where d = 784). For CIFAR- 10, we use shared ResNet backbone (He al. 2016b) for the policy and predictor networks, and each network uses its own output head. The 32 32 images are coarsened into d 64 patches of size 4 x 4, so the selector head generates logits corresponding to each patch, and the predictor head generates probabilities for each class.
For MNIST,
Figure3]shows 3Jshows our method's s accuracy for different feature budgets. For MNIST, we use the previous baselines but exclude the iterative method due to computational cost. observe a large perfor- mance gap, particularly when making small number of selections: the greedy method reaches nearly 90% accuracy with just pixels, which is nearly 10% higher than the best baseline and considerably higher than prior work (Balnn et al.) 2019: Yamada et al.) 20200] Covert et al.) 2020 OL yields the worst results, and trains slowly, wly, likely due to the large number of states. For CIFAR- 10, two simple baselines: center crops and random masks of various sizes. For the random baseline, we plot the mean and standard deviation calculated across ten random masks. Our greedy approach is slightly less accurate with 1-2 patches, but it reaches significantly higher accuracy when using 5-20 patches. Figure also shows qualitative examples of our method's predictions after se- lecting 10 out of 64 patches, and Appendixx Elshos similar plots with different numbers of patches.
7 CONCLUSION
In this work, we developed a greedy approach to active feature acquisition that selects features based on their CMI with the response variable. We then proposed an approach to learn the greedy policy using amortized optimization, and we conducted experiments that show our method outperforms variety of existing feature selection methods. Future work this topic may include incorporating non-uniform features costs, automatically determining the feature budget on a per-sample basis, and further characterizing the greedy suboptimality gap. Some progress has been made in analyzing the suboptimality gap in the active feature acquisition setting (Chen et al. 2015b). but more general characterizations remain open topic for future work.

---

Under review as a conference paper at ICLR 2023
REFERENCES
National health and nutrition examination survey, 2018. URL https: www. cdc. gew.cccsoo/ccc//////oo
nhanes.
Brandon Amos. Tutorial on amortized optimization for learning to optimize over continuous do- mains. arXiv preprint wwxiv:2202.00665 2022.
Muhammed Fatih Balm, Abubakar Abid, and James Zou. Concrete autoencoders: Differentiable feature selection and reconstruction. International Conference on Machine Learning, pp. 444- 453. PMLR, 2019.
Leo Breiman. Random forests. Machine Learning, 45(1):5-32, 2001.
Jie Cai, Jiawei Luo, Shulin Wang, and Sheng Yang. Feature selection in machine learning: A new perspective. Neurocomputing. 300:70-79, 2018.
Chun-Hao Chang, Ladislav Rampasek, and Anna Goldenberg. Dropout feature ranking for deep learning models. arXiv preprint arXiv: 1712 2017.
Jianbo Chen, Le Song, Martin Wainwright, and Michael Jordan. Learning to explain: An information-thooretie perspective model interpretation. In International Conference Ma- chine Learning, pp. 883-892. PMLR, 2018.
Suming Chen, Arthur Choi, and Adnan Darwiche. Value of information based on decision robust- ness. Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015a.
Yuxin Chen, S Hamed Hassani, Amin Karbasi, and Andreas Krause. Sequential information max- imization: When greedy near-optimal? In Conference on Learning Theory, pp. 338-363. PMLR, 2015b.
T.M. Cover and J.A. Thomas. Elements of Information Theory. Wiley, 2012. ISBN 9781 18585771.
Ian Covert, Scott M Lundberg, and Su-In Lee. Understanding global feature contributions with additive importance measures. Advances Neural Information Processing Systems, 33:17212- 17223, 2020.
Ian Covert, Scott M Lundberg, and Su-In Lee. Explaining by removing: unified framework for model explanation. Journal of Machine Learning Research, 22:209-1, 2021.
Abhimanyu Das and David Kempe. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. arXiv preprint 1rxiv:110..3975, 2011.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. httt:http//chhhi
ics. uds.ucdiidd
Gabriel Dulac-Arnold, Ludovic Denoyer, Philippe Preux, and Patrick Gallinari. Datum-wise classi- fication: a sequential approach to sparsity. Joint European Conference on Machine Learning and Knowledge Discovery Databases, pp. 375-390. Springer, 2011.
Kirstin Early, Stephen E Fienberg, and Jennifer Mankoff. Test time feature ordering with FOCUS: Interactive predictions with minimal user burden. In Proceedings of the 2016 ACM International Joint Conference on Pervasive and Ubiquitous Computing, pp. 992-1003, 2016a.
Kirstin Early, Jennifer Mankoff, and Stephen E Fienberg. Dynamic question ordering in online surveys. arXiv preprint arXiv: 1007.0409, 2016b
Ethan Elenberg, Alexandros G Dimakis, Moran Feldman, and Amin Karbasi. Streaming weak sub- modularity: Interpreting neural networks on the fly. Advances in Neural Information Processing Systems, 30, 2017.
Ethan R Elenberg, Rajiv Khanna, Alexandros G Dimakis, and Sahand Negahban. Restricted strong convexity implies weak submodularity. The Annals of Statistics, 46(66):353933666 2018.
10

---

Under review as a conference paper at ICLR 2023
Gabriel Erion, Joseph D Janizek, Carly Hudelson, Richard B Utarnachitt, Andrew M McCoy, Michael Sayre, Nathan White, and Su-In Lee. CoAl: Cost-aware artificial intelligence for health care. medRxiv, 2021.
François Fleuret. Fast binary feature selection with conditional mutual information. Journal of Machine Learning Research, 5(9), 2004.
Yarin Gal and Zoubin Ghahramani. Dropout as bayesian approximation: Representing model uncertainty in deep learning. In International Conference on Machine Learning, pp. 1050-1059. PMLR, 2016.
Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research, 42:427-42 2011.
Will Grathwohl, Dami Choi, Yuhuai Wu, Geoff Roeder, and David Duvenaud. Backpropagation through the void: Optimizing control variates for black-box gradient estimation. In International Conference on Learning Representations, 2018.
Isabelle Guyon and André Elisseeff. introduction to variable and feature selection. Journal of Machine Learning Research, 3 2003.
He He, Hal Daumé III, and Jason Eisner. Cost-sensitive dynamic feature selection. In ICML Infer- ning Workshop, 2012.
He He. Paul Mineiro, and Nikos Karampatziakis. Active information acquisition. arXiv preprint a6Xiv: 2016a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp- 770-778, 2016b.
Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. Deep reinforcement learning that matters. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparaatetaaaannooiiiooooo with Gumbel-softmax, arXiv preprint ar arXiv:1611.00 144, 2016.
Jaromír Janisch, Tomás Pevný, and Viliam Lisý. Classification with costly features using deep rein- forcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3959-3966, 2019.
Neil Jethani, Mukund Sudarshan, Yindalon Aphinyanaphongs, and Rajesh Ranganath. Have we learned to explain?: How interpretability methods can learn to encode predictions in their inter- pretations. In International Conference on Artificial Intelligence and Statistics, pp. 1459-1467.
PMLR, 2021.
Mohammad Kachuee, Orpaz Goldstein, Kimmo Kärkkäinen, Sajad Darabi, and Majid Sarrafzadeh. Opportunistic learning: Budgeted cost-sensitive learning from data streams. In International Conference on Learning Representations, 2018.
Mohammad Kachuee, Kimmo Karkkainen, Orpaz Goldstein, Davina Zamanzadeh, and Majid Sar- rafzadeh. Cost-sensitive diagnosis and learning leveraging public health data. arXiv preprint 1902.07000 2019.
Sergey Karayev, Tobias Baumgartner, Mario Fritz, and Trevor Darrell. Timely object recognition. Advances in Neural Information Processing Systems, 25, 2012.
Durk P Kingma, Tim Salimans, and Max Welling. Variational dropout and the local reparameteri- zation trick. Advances in Neural Information Processing Systems, 28, 2015.
11

---

Under review as a conference paper at ICLR 2023
Narine Kokhlikyan, Vivek Miglani, Miguel Martin, Edward Wang, Bilal Alsallakh, Jonathan Reynolds, Alexander Melnikov, Natalia Kliushkina, Carlos Araya, Siqi Yan, et al. Captum: A unified and generic model interpretability library for PyTorch. arXiv preprint arXiv:2009.07896, 2020.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):227--2324, 1998.
Changhee Lee, Fergus Imrie, and Mihaela van der Schaar. Self-supervision enhanced feature selec- tion with correlated gates. International Conference on Learning Representations, 2021.
Jundong Li, Kewei Cheng, Suhang Wang, Fred Morstatter, Robert Preevino, Jiliang Tang, and Huan Liu. Feature selection: A data perspective. ACM Computing Surveys (CSUR), 50(6): 2017.
Yang Li and Junier Oliva. Active feature acquisition with generative surrogate models. Interna- tional Conference on Machine Learning, pp. 6450 6459. PMLR, 2021.
Ofir Lindenbaum, Uri Shaham, Erez Peterfreund, Jonathan Svirsky, Nicolas Casey, and Yuval Kluger. Differentiable unsupervised feature selection based on a gated Laplacian. Advances in Neural Information Processing Systems, 34:1530-1542, 2021.
Chao Ma, Sebastian Tschiatschek, Konstantina Palla, José Miguel Hernández-Lobato, Sebastian Nowozin, and Cheng Zhang. EDDI: Efficient dynamic discovery of high-value information with partial VAE. arXiv preprint 1809 112,, 2018.
Chao Ma. Sebastian Tschiatschek, Richard Turner, José Miguel Hernández-Lobato, and Cheng Zhang. VAEM: a deep generative model for heterogeneous mixed type data. Advances in Neural Information Processing Systems, 13:11227-11247, 2020.
Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The Concrete distribution: A continuous relaxation of discrete random variables. arXiv preprint arXiv:1611.0077 1000 2016.
Prem Melville, Maytal Saar- Tsechansc,,,,,, Foster Provost, and Raymond Mooney. Active feature- value acquisition for classifier induction. In Fourth IEEE International Conference Data Min- ing (ICDM (CCD)'04, pp. 483-486. IEEE, 2004.
Henry W Miller. Plan and operation of the health and nutrition examination survey, United States, 1971-1973. DHEW publication no. (PHS)-Dept. of Health, Education, and Welfare (USA), 1973.
Andriy Mnih and Karol Gregor. Neural variational inference and learning in belief networks. In International Conference on Machine Learning, pp. 1791-1799. PMLR, 2014.
Volodymyr Mnih, Nicolas Heess, Alex Graves, et al. Recurrent models of visual attention. Advances in Neural Information Processing Systems, 27, 2014.
Michael Mosesson. Fibrinogen and fibrin structure and functions. Journal of Thrombosis and Haemostasis, 389):1894-9944 2005.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. 2017.
Jette Randløv and Preben Alstrøm. Learning to drive a bicycle using reinforcement learning and shaping. In ICMI., volume 98, pp. 463 471-471. Citeseer, 1998.
BP Roe, HJ Yand. J Zhu, Y Lui, Stancu, et al. Boosted decision trees, an alternative to artificial neural networks. Nucl. Instrm. Meth. A, 543:577-584, 2005.
Maytal Saar- Tsechansky, Prem Melville, and Foster Provost. Active feature- value acquisition. Man- agement Science, 55(4):664-684 2009.
12

---

Under review as a conference paper at ICLR 2023
Hajin Shim, Sung Ju Hwang, and Eunho Yang. Joint active feature acquisition and classification with variable-size set encoding. Advances in Neural Information Processing Systems, 31, 2018.
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In International Conference on Machine Learning, pp. 3145- 3153. PMLR, 2017.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: simple way to prevent neural networks from overfitting. The Jourmal of Machine Learning Research, 15(1):1929-1958, 2014.
ATLS Subcommittee, International ATLS Working Group, al. Advanced trauma life support (atls@): the ninth edition. The Journal of Trauma and Acute Care Surgery, 7465):1333-1366, 2013.
Mukund Sundararajan, Ankur Taly, and Qigi Yan. Axiomatic attribution for deep networks. In International Conference on Machine Learning, pp. 3319-3328, PMLR, 2017.
Richard S Sutton, Andrew G Barto, et al. Introduction to reinforcement learning. 1998.
George Tucker, Andriy Mnih, Chris Maddison, John Lawson, and Jascha Sohl-Dickstein. Rebar: Low-variance, unbiased gradient estimates for discrete latent variable models. Advances in Neural Information Processing Systems, 30, 2017.
Ronald J Williams. Simple statistical seaddeen-following algorithms for connectionist reinforcement learning. Machine Learning, 8(3):299-256, 1992.
Yutaro Yamada, Ofir Lindenbaum, Sahand Negahban, and Yuval Kluger. Feature selection using stochastic gates. In International Conference on Machine Learning. PMLR, 2020.
Jinsung Yoon, James Jordon, and Mihaela van der Schaar. INVASE: Instance-wise variable selection using neural networks. In International Conference Learning Representations, 2018.
13

---

Under review as a conference paper at ICLR 2023
A PROOFS
In this section, we re-state and prove our main theoretical results. We begin with our proposition regarding the optimal predictor f for an arbitrary policy π.
When y is discrete and is cross-entropy loss, the loss-minimizing predictor f" for any policy is the Bayes classifier, or (x,) p(y x.s)-
Proposition 1.
Proof. The optimal prediction given 2s is defined by minimizing the expected loss, where the ex- pectation is with respect to and we must condition on the observed values I.. Because features are selected sequentially by т with no knowledge of the non-selected values, there is no other infor- mation to condition on. We can therefore derive the optimal prediction follows:
(xx,) = arg min Eyle, y)]
arg min Σply = i xx) log Di
Ey
arg min DRl xx)) ll 1) + H( x.)
ply xx).
In the case of continuous response E with squared error loss, we have similar result involving the response's 's conditional expectation:
(x(x)) arg min By v. [i y)
arg min Ey n. [U Ely Ix,1) + Var(y xx)
Ely xz).
Proposition 2.
Given the features ye the greedy policy x² selects the feature x; having maximum conditional mutual information with the response variable, or
π (Ix) = arg max 1(y; I2).
(9)
Proof. Consider the expected loss from observing an additional feature x; given the values T. The only available information T., so our expected loss with respect the conditional distribution y, X; Zy. We thus have the following expected loss:
Ey.x (x,+)
Ey.x, [e(p(y Ias xx,x))))))
Ex; Eylz,,x, [l(p(y Ie, xx,x)))))]]
Exx, le, [H(y) [s [x)x
H(y xx)) Iyy;x; x..).
Note that (y (x.) a constant that does not depend i. When identifying the index that yields the minimum expected loss, we thus have the following result:
arg min Ey,, v. (x, xx) arg max T(y;x; x.))-
14

---

Under review as a conference paper at ICLR 2023
In the case of a continuous response with squared enror loss and optimal predictor given by f (x,) Ely Øz]. we have a similar result:
Ey yx (x, Ux;) - y)) = By x (Eyy Iss x;] y)
= Ex ls, Eyle, [EEl [ig x;] - y
Ex, (aar(y Tz, x;]]-
When selecting the index with minimum expected loss, our selection is thus the index that yields the lowest expected conditional variance:
arg min Exple, [xgle,[Var(( 2zg X,)]
We also prove the limiting result presented in eg. (6) which states that 17 - I(y;x, x,).
Proof. Conditional mutual information [y;; x; x.) is defined as follows (Cover & Thomas 2012):
ply, X; v.)
xyy;x; xx)) = By x,12,
log p(x;
Ts)p(y (..))
Rearranging terms, we can also write it as an expected KL divergence:
log p(y, X4 xx)
T(y;x; X4 xx.) = Ex,,ue, lee, Ex
p(x; I. 1y)p(( x.e)
log ply Jsz xx)]
= -Ex, Eylersi
ply | (x,))
= =xxi DRCL. (p(y)
Ds, x;) || p(y x...
Now, when we sample multiple values w!...., x. p(x; xx.) and make predictions using the Bayes classifier, we have the following mean prediction becomes large:
lim 1 Σ p(y Iz x²) Ex,1,, [ply Egn x:)] ply [x.). n
Calculating the mean KL. divergence across each of the predictions, we arrive at the following result:
lim 1 = Ex,12 (ply Ix., x:) ply [(ss)]]] = 7(y; Ix).
Theorem When y is discrete and cross-entropy loss, the global optimum of eg. (8) is predictor that satisfies [x, 07) ply x.) and policy n xxx Φ²) that puts all probubility mass on = arg max, I(y: X, w.)).
0). When the predictor is given the feature values T., it means that one index E s was chosen by the policy according to π T( Φ) and the remaining indices s \ were sampled from p(s). Because s is sampled independently from (x, y), and because π: ( Φ) is not given access to (x(d)as X,, y). the predictor's expected loss must be
Proof. We first consider the predictor network f(x;;
15

---

Under review as a conference paper at ICLR 2023
considered with respect to the distribution y Zg.. The globally optimal predictor f(zg:0") is thus defined as follows, regardless the selection policy (2.;; Φ) and which index was selected last:
f(x,;0") arg min Byln, ()( -pyy x=).
The above result follows from our proof for Proposition Now, given the optimal predic- tor f(zz; ). we can define the globally optimal policy by minimizing the expected loss for fixed input gz. Denoting the probability mass placed on each index [d] as (1 o), where n (Its; () E A dd-1, the expected loss is the following:
(awn(es;d) x: [e[[(2r, U x;; xx;00),,))
Σ iE|d]
(1 o) y, x,12, [e(S(s,, Ux: 0*),
Σ iE
T. (xii Φ D (y Tas xi)
The above result follows from our proof for Proposition yields the lowest expected conditional entropy, or
If there exists a single index 8 [d] that
Ex n. (y Fgy X3, )] Ex la, [H Fzg x;)x Vi x
then the optimal predictor must put all its probability mass i", क. (I:s; x²) Note that the corresponding feature X;- has maximum conditional mutual information with y, because we have
Xy; xx.)
Hly ar.)) Ex,- (H(y [.s. x:=)) )]-
Constant
To summarize, we derived the global optimum our objective L(B, Φ) by first considering the optimal predictor (xx:; 0*), and then the optimal policy π <X.i o²) assuming the optimal predictor.
When y continuous and é is squared error loss, the global optimum of eg.. (8) is predictor that satisfies f(x,;0" = JEyy x.] and policy π T(x,;0" that puts all probability mass on arg min; [xa]=./Var(. Fg x,)
Theorem 2.
Proof. Our proof follows the same logic as proof for Theorem an arbitrary policy, we have:
For the optimal predictor given
flz 0*) = arg min Eylz, [(0 - ([} = E xx].
Then, for the policy's 's expected loss, have:
By. (( -
-
Σ (x. Bx,,, [Var(y [2,,,)) (ea
REld]
If there exists an index i* [d] that yields the lowest expected conditional variance, then the optimal policy must put all its probability mass on i" or n. (I.; = 1.
16

---

Under review as a conference paper at ICLR 2023
B DATASETS
The datasets used in our experiments summarized in Table 2 the two image classification datasets are publicly available, and the three emergency medicine tasks were privately curated from the Harborview Medical Center Trauma Registry.
Three of the tabular datasets and
Table 2: Summary of datasets used in experiments.
Dataset
# Features
# Feature Groups
# Classes
# Samples
Fluid
224
162
2,850
Respiratory
112
37
65,515
Bleeding
121
46
6,496
Spam
58
2
4,601
MiniBooNE
130,064
Diabetes
45
92,062 3
MNIST
784
10
60,000
CIFAR- 10
1,024
64
10
60,000
B. MINIBOONE SPAM CLASSIFICATION
The spam dataset includes features extracted from e-mail messages predict whether or message is spam. Three features describes the shortest, average, and total length of letters in the message, and the remaining 54 features describe the frequency with which certain key words are used. The MiniBooNE particle identification dataset involves distinguishing electron neutrinos from muon neutrinos based on various continuous features (Roe et al. 2005). Both datasets were obtained from the UCI repository (Dua & Grafi 2017)
B.2 DIABETES CLASSIFICATION
This dataset is obtained from from the National Health and Nutrition Examination Survey (NHANES) (NHA) 2018), an ongoing survey designed to assess the well-being of adults and chil- dren in the United States. We used version of the data pre-processed by Kachuce al. (2018) 2019) that includes data collected from 1999 through 2016. The input features include demographic information (age, gender, ethnicity, etc.), lab results (total cholesterol, triglyceride, etc.), examina- tion data (weight, height, etc.), and questionnaire answers (smoking, alcohol, sleep habits, etc.). An expert also asked to suggest costs for each feature based the financial burden, patient privacy, and patient inconvenience, but we assume uniform feature costs in our experiments for simplicity. Finally, the fasting glucose values were used define three classes based on standard threshold values: normal, pre-diabetes, and diabetes.
B.3 IMAGE CLASSIFICATION DATASETS
The MNIST and CIFAR- 10 datasets were downloaded using PyTorch (Paszke et al. (017). We used the standard train-test splits, and we split the train set to get validation set with the same size as the test set.
B.4 EMERGENCY MEDICINE DATASETS
The emergency medicine data used in this study gathered over 13-year period (2007-2020) and encompasses 14,463 emergency department admissions. We excluded patients under the age of 18, and curated clinical cohorts commonly 1) pre-hospital fluid resuscitation, 2) emergency department respiratory support, and 3) bleeding after injury. These datasets not publicly available due to patient privacy concerns.
in pre-hospitalization settings. These include
17

---

Under review as a conference paper at ICLR 2023
Pre-hospital fluid resuscitation We selected 224 variables that were available in the pre-hospital setting, including dispatch information (injury date, time, cause, and location), demographic infor- mation (age, sex), and pre-hospital vital signs (blood pressure, heart rate, respiratory rate). The outcome was each patient's response to fluid resuscitation, following the Advanced Trauma Life Support (ATLS) definition (Subcommittee et al. 2013).
Emergency department respiratory support In this cohort, our goal is predict which pa- tients require respiratory support upon arrival in the emergency department. Similar to the previous dataset, we selected 112 pre-hospital clinical features including dispatch information (injury date, time, cause, and location), demographic information (age, sex), and pre-hospital vital signs (blood pressure, heart rate, respiratory rate). The outcome is defined based whether patient received respiratory support, including both invasive (intubation) and non-invasive (BiPap) approaches.
Bleeding In this cohort, we only included patients whose fibrinogen levels were measured, as this provides an indicator for bleeding fibrinolysis (Mosesson 2005). Like the previous datasets, demographic information, dispatch information, and pre-hospital observations were used as input features. The outcome, based on experts' opinion, defined by whether an individual's fibrinogen level is below 200 mg/dl., which represents higher risk of bleeding after injury.
C BASELINES
This section provides more details on the baseline methods used in our experiments (Section 6).
C.I GLOBAL FEATURE IMPORTANCE METHIOSS
Two of our static feature selection baselines, permutation tests and SAGE, are known global feature importance methods because they rank features based on their role in improving model accuracy (Covert et al., 2021). In our experiments, we run each method using single classifier trained on the entire dataset, and we then select the top & features depending on the budget.
When running the permutation test, we calculate the validation AUROC while replacing values in the corresponding feature column with random draws from the training set. When running SAGE, use the authors' implementation with automatic convergence detection (Covert et al. 2020).. For the six tabular datasets, we averaged across 128 sampled values for the held-out features, and for MNIST we used zeros baseline to achieve faster convergence.
C.2 LOCAL FEATURE IMPORTANCE METHODS
Two of our static feature selection baselines, DeepLift and Integrated Gradients, are known as local feature importance methods because they rank features based on their importance to single predic- tion. our experiments, we generate feature importance scores for the true class using all examples in the validation set. We then select the top le features based their mean absolute importance. We use a mean baseline for Integrated Gradients (Sundararajan et al. 2017), and both methods were run using the Captum package (Kokhlikyan al. 2020).
C.3 OPPORTUNISTIC LEARNING
Kachuee et al. (2018) proposed Opportunistic Learning (OL), an approach to solve active feature acquisition using RL. The model consists of two networks analogous to our policy and predictor: Q-network that estimates the value associated with each action, where actions correspond to features, and P-network responsible for making predictions. When using OL, use the same architectures as our approach, and OL shares network parameters between the P. and Q-networks.
Kachuee al. (2018) introduce utility function for their reward, shown in inleq. (10) which calculates the difference in prediction uncertainty as approximated by MC dropout (Gal & Ghahramani 2016).
The reward also accounts for feature costs, but we all feature costs
18

---

Under review as a conference paper at ICLR 2023
Ti [Cert(x)) Cert(x' U Uz!)ll
(10)
To provide fair comparison with the remaining methods, we made several modifications to the authors' implementation. These include 1) preventing the prediction action until the pre-specified budget is met, 2) setting all feature costs to be identical, and 3) supporting pre-defined feature groups as described in Appendix D.3] When training. we update the P-, Q- and target Q-networks every + 100 experiences, where d is the number of features in dataset. In addition, the replay buffer set to store the 1000d most recent experiences, and the random exploration probability is decayed so that it eventually reaches value of 0.1.
d
D TRAINING APPROACH AND HYPERPARAMETERS
This section provides more details on training approach and selected hyperparameters.
D.I TRAINING PSEUDOCODE
Algorithm summarizes our training approach. Briefly, we select features by drawing a Concrete sample using policy network's logits, calculate the loss based the subsequent prediction, and we then update the mask for the next step using a discrete sample from the policy's 's distribution. We implemented this approach using PyTorch (Paszke al. 2017) and PyTorch Lightning
Algorithm 1: Training pseudocode
Input: Data distribution p(x, v(x,y) y). budget k > O, learning rate >> 0, temperature т >> 0 Output: Predictor model ff (x; 0), selector model T (xx; σ) initialize fx; 0). (x: while not converged do sample
p(x, y)
initialize [ = 0, m = 00
for j = 1 to k: do calculate logits = (x @ m; Φ), sample G; ~ Gumbel for i E [d] set m max (m, softmax(G (G a, // update with Concrete
set max (m, softmax + 0)) // update with one-hot update L C (f(( @ m):),y)
end
update +- 0 - VoL. @ - o 7
end return 0), (xx;
One notable difference between Algorithm and our objective L(O. Φ) the main text is the use of the policy π (x; Φ) for generating feature subsets. This differs from fromeq..co (8) which generates feature subsets using a subset distribution p(s). The key shared factor for both approaches that there are separate optimization problems over each feature subset that can be viewed independently. For each feature set Te, the problem incorporates both the policy and predictor and can be written as follows:
Ex-n(xx:)) [f(((x U Ux;;0) x))
(1I)
The problems for each subset do not interact the sense that during optimization, the selection given v, is based only the immediate change in the loss; gradients are not propagated through multiple selections, as they would for an RL-based solution. In solving these multiple problems, the difference is simply that eq. (8) weights them according p(s), whereas Algorithm I weights them according to the current policy T (xx, o).
http:://www.yytorcchhgghtnn
19

---

Under review as a conference paper at ICLR 2023
D.2 HYPERPARAMETERS
Our experiments with the six tabular datasets all used fully connected architectures with dropout in all layers (Srivastava et al. 2014). The dropout probability is set 0.3, the networks have two hidden layers of width 128, and we performed early stopping using the validation loss. For our method, the predictor and selector were separate networks with identical architectures. When training models with the features selected by static methods, we reported results using the best model from multiple training runs based on the validation loss. We did not perform any additional hyperparameter tuning due to the large number of models being trained.
For MNIST, we used fully connected architectures with two layers of width 512 and the dropout probability set to 0.3. Again, our method used separate networks with identical architectures. For 10, we used shared ResNet backbone (He et al., 2016b) consisting of several residually connected convolutional layers. The classification head consists of global average pooling and linear layer, and the selection head consisted of a transposed convolution layer followed by I x convolution, which output grid of logits with size 8 8. Our CIFAR-10 1 networks are trained using random crops and random horizontal flips as augmentations.
D.3 FEATURE GROUPING
All of the methods used in our experiments were designed to select individual features, but this is undesirable when using categorical features with one-hot encodings. Each of our three emergency medicine tasks involve such features, so we extended each method to support feature grouping.
SAGE and permutation tests are trivial to extend to feature groups: we simply removed groups of features rather than individual ones. For DeepLift and Integrated Gradients, we used the summed importance within each group, which preserves each method's 's additivity property. For the differen- tiable method based on Concrete Autoencoders (Bahn et al. 2019). we implemented a generalized version of the selection layer that operates feature groups. We also extended OL to operate on feature groups by having the actions map to groups rather than individual features.
Finally, for method, we parameterized the policy network (x; 6) that the number of outputs the number of groups rather than the total number of features d (where g S d). When applying masking, we first generate a binary mask using a binary groups matrix M E {0, 1] 1]dx9, where Mij = 1 if feature is in group j and Mij = otherwise. Thus, our masked input vector is given by @ (Mm).
[0, 1|9, and we then project the mask into [0, 1]a
E ADDITIONAL RESULTS
This section provides several additional experimental results. First.FFigure 4 shoows the same results as Figure but larger for improved visibility. Next, Figure 5) shows the AUROC for each feature selection method under different feature budgets for the three publicly available tabular datasets. Here, our greedy active approach achieves the best results for all feature budgets on all three tasks. Notably, our two active baselines are often outperformed by static methods, and OL remains unsta- ble.
Next, Figure 6) though Figure 11 display the feature selection frequency for each of the tabular datasets when using the greedy active method. The heatmaps in each plot show the portion of the time that feature (or feature group) is selected under a specific feature budget. These plots reveal that our method is indeed selecting different features for different samples.
displays examples of CIFAR-10 predictions given different numbers revealed patches. The predictions generally become accurate after revealing only small number of patches, reflecting a similar result as Figure 3] Qualitatively, we can see that the policy network learns to select vertical stripes, but the order which it fills out each stripe depends on where it guesses important information may be located.
Finally, Figure 12
20

---

Under review as a conference paper at ICLR 2023
Bleeding AUROC Comparison
0759
0.25
0.70
AUNOC
0.75
0.25
0.00
0.75
10
15
20
Selected Features
Respiratory AUROC Comparison
0.80
10
15
20
Features
AUROC Comparison
0.80
0.75
0.65
Selected Festures
IntGrad
Opportunistic
DeepLitt
Perm Tast
Rerative
Greedy Active (Durs)
Figure 4: AUROC comparison on the three emergency medicine diagnosis tasks.
21

---

Under review as a conference paper at ICLR 2023
Spam AUROC Comparison
0.5
0.90
0.65
0.60
0.75
0.70
10
15
20
# Selected Features
MiniBooNE AUROC Compartson
0.95
0.85
0.70
10
15 Features
20
Comparison
0.95
0.90
0.85
0.80
0.75
0.70
0.65
Selected Festures
IntGra
Opportunistic
DeepLitt
Perm Tast
Rerative
Greedy Active (Durs)
Figure 5: AUROC comparison on the three public tabular datasets.
22

---

Under review as a conference paper at ICLR 2023
Bleeding Feature Selection Frequency
Selections
0.6
15-
0.4
20-
0.
40
Figure 6: Feature selection frequency for the greedy active approach on the clotting dataset.
Respiratory Feature Selection Frequency
Selections
40
0.6
35
0.0
Index
Figure Feature selection frequency for the greedy active approach on the respiratory dataset.
0.8
Fluid Feature Selection Frequency
Selectians
0.6
is B
20
60
100
12c
140
160
Feature Index
0.2
0.0
Figure 8: Feature selection frequency for the greedy active approach the fluid dataset.
23

---

Under review as a conference paper at ICLR 2023
Spam Feature Selection Frequency
008
Selections
10-
15-
0.4
16
Figure 9: Feature selection frequency for the greedy active approach on the spam dataset.
MiniBooNE Feature Selection Frequency
0.8
Selections
0.6
20-
25
10
20
30
40
Feature Index
Figure 10: Feature selection frequency for the greedy active approaeg on the MiniBooNE dataset.
Diabetes Feature Selection Frequency
10
0.8
1.
15.
04
02
25
10
20
30
35
Feature Index
Figure 11: Feature selection frequency for the greedy active approach the diabetes dataset.
24

---

Under review as a conference paper at ICLR 2023
Horse
Automoblie
Truck
Cat
Dog
Frog
Ship
Full Image
Prob 8.04%
Prob 27.61%
Prob 12.60%
Prob 12.08%
Prob 69.06%
Prob 38.50%
Prob 40.99%
1 Patches
Prob 48. 18.14%
Prob 99.39%
Prob 16.02%
Prob 27.03%
Prob 99.38%
Prob 94.315
Prob 94.02%
Patches
Prob 76. 26.57%
Prob 97%
Prob 96.655 96.65%
Prob 43.52%
Prob 99, 99.99%
Prob 99.75%
Prob 82.71%
10 Patches
Patches
Prob 81.35%
Prob 1.00 .0%%
Prob 96.01%
Prob 79.03%
Probo 99. 90.93
Prob 90 9.%
Prob 99.90%
20 Patches
97.02%
Prob
Prob
Prob 99.91%
Prob
Prob 99.88%
23 Patcnics
20 Patches
Figure 12: CIFAR-10 predictions with different numbers of patches revealed by greedy active method.
25


Reviews:
[{"review_id": "yNz9R3FIhY7", "reviewer": "Reviewer_d6k9", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a greedy-based approach for online feature selection.  This paper defines greedy online feature selection and also provides an iterative procedure to implement the greedy approach with a deep learning approach. \n", "summary_of_the_review": "The paper proposes a new greedy-based method to address online feature selection. The technical novelty in the individual parts is limited. ", "strength_and_weaknesses": "Strengths:\n+ The problem is interesting and meaningful. Feature selection, especially online feature selection, could be used in various application scenarios in practice. \n+ The empirical evaluation is comprehensive and overall convincing. The paper conduct extensive experiments on several datasets including tabular datasets and image classification datasets, and the proposed method outperforms both RL-based and offline feature selection methods. The authors will release the source code as mentioned in Section 6. \n\nWeaknesses:\n- The novelty is limited. Though the framework is novel, the individual models are not. \n- The diagram in Figure 1 is interesting. However, the key point of the proposed method is not reflected in Figure 1.  More information could be added to the diagram. \n- Some typos should be modified. For example, in Subsection 2.1, “X_{\\hat{s}} is the set complement X_{[d]\\s}” -> “X_{\\hat{s}} is the set complement to X_{s}”. \n- Some details could be improved. For example, the “eq.”  could be changed to “Equation”  in order to be consistent with the description “Figure”, “Table”, etc. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ntBqGga4yC", "reviewer": "Reviewer_oRCJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces a new greedy method for the online feature selection problem. The method is locally optimal in selecting features that maximize the conditional mutual information with the response variable. The authors propose a deep learning-based approach to learning a selection policy network, which is trained by amortized optimization. The new method is of low complexity compared to other RL-based methods and has good performance compared to online and offline methods on tabular and image data.", "summary_of_the_review": "This work presents a smart way to make online feature selection, which is novel given the literature. The paper is also well-written, and the experiments demonstrated the method well. But as I mentioned above, I’m still curious about the adaptive part of the problem definition. The main results may require more explanations or assumptions.\n", "strength_and_weaknesses": "Strengths:\n- The method is novel based on its description. The solution is interesting.\n- The writing is of high quality \n- Experiments well demonstrated the proposed method.\n\nWeaknesses:\n- One weakness is the clarity of the notations. Although the author defined the notations at the beginning of section 2. I found I still got lost while reading the paper, especially when trying to distinguish between an index set and a single index. This could be due to the redefinition of the bold type and the normal type.\n- About the clarity of the problem definition: I’m not familiar with this task, but when people refer to “online,” they usually will indicate the data distribution changes or is stationary. I guess here the problem assumes a stationary distribution, and “online” indicates the sequential nature of the selection, right? If so, there is no adaptive part of the problem, and the method sounds like a sequential version of the offline counterpart.\n- For the theoretical results, I feel Eq. 8 and thm 1,2 may require more explanations or assumptions. (But these impressions could also be due to my misunderstanding.) I had the following questions while I was reading the paper\n  1. Does p(s) depend on $\\phi$ or $\\theta$? \n  2. In the proof of Thm 1, what are the mild conditions mentioned in the main paper? I didn’t follow how Eq. 8 simplifies to Proposition 1.\n- It seems the practical objective function of the experiments has a gap with Eq. 8. I.e., I didn’t see how to sample from $p(s)$ from Alg. 1. It would be great to state the objective function in experiments (with monte carlo estimates of the expectations).\n- Should Eq. 7 have a reverse inequality sign because $v$ is the expected loss? This is the same for the gap definition below.\n- I felt some parts of section 3 (mainly sec. 3.2) are pretty technical but didn’t help me understand the main method in section 4. Perhaps leaving more space in section 4 to explain the training procedure is more rewarding to the audience. (Maybe it’s only a personal taste.)\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "lQmauU2lOJ", "reviewer": "Reviewer_H6xQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the author(s) considered the problem of online feature selection which was different from the standard feature selection with fixed feature subsets (i.e., offline feature selection). The author(s) proposed a deep learning-based algorithm to process the greedy information maximization for online feature selection. Then, the author(s) demonstrated that empirical experiments showed the advantage of the proposed algorithm.\n\n---\n", "summary_of_the_review": "The work in this paper is interesting; However, there are many unclear aspects in the description (including experiments) of this paper, and the innovation also needs to be further discussed. In addition, the work largely ignores existing works.\n", "strength_and_weaknesses": "### Strength:\n\nFeature selection is a significant branch of machine learning, and most of the existing feature selection studies mainly focus on offline feature selection. In practice, online feature selection is more challenging and more important.\n\n---\n\n### Weaknesses:\n\n1. The novelty of this proposed algorithm is limited.\n\n2. The review and comparison with online/offline feature selection are insufficient.\n\n3. There are potential issues in the calculation of experimental results (especially the lack of stability analysis for selected features, which is necessary for deep model-based feature selection).\n\n4. Some descriptions in this paper are not clear.\n\nFor more details, please see the section of \"Clarity, Quality, Novelty And Reproducibility\"\n\n---\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "k94iepFT7cH", "reviewer": "Reviewer_dhvL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper focus on the online feature selection problem which mainly viewed as a reinforcement learning problem by traditional methods. Authors introduced a greedy approach to online feature selection that selects features according to their conditional mutual information with the response variable and then proposed a deep learning approach to learn the greedy policy.  Experiments on numerous datasets show that the proposed method outperforms a variety of existing feature selection methods.", "summary_of_the_review": "Overall, the article has a complete structure and clear thinking. But the content needs to be further improved, if authors can solve my problems, I think this paper is a very good article.\n", "strength_and_weaknesses": "Strength:\n1. Starting from the greedy algorithm, the author continuously analyzed the algorithm from the theoretical and strategic levels, so as to get their proposed algorithm, which I think is very reasonable.\n2. The effectiveness of the proposed method was demonstrated on various datasets. The authors also provide their codes of experiments.\nWeaknesses:\n1. I think the explanation of eq.(8) is far from sufficient. It's better to restate how far it differs from eq.(1) and how do you derive this formula from the greedy algorithm in more detail.\n2. In section 3, authors say that 'The third example illustrates the perils of following a greedy approach: it fails to account for each\nselection’s impact later in the selection procedure. In contrast, a non-greedy policy can make suboptimal selections that yield large improvements in later steps.' Does that show up in the experimental section? If not, can you design it?\n3. In Figure 3, a visualization of the selected features is given, which I think is very good. But I think it would be better if there was a reasonable explanation for the chosen features.\n\n\n\n\n\n\n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "K4pdKJRBKtj", "reviewer": "Reviewer_h13P", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a greedy strategy to feature selection based on information maximization criterion.", "summary_of_the_review": "I think there are concerns about theoretical justifications and the authors missing relevant works when motivating their method. The empirical results are interesting, but not surprising given the generally strong performance of the greedy method. The paper is not ready to be published at a conference like this one.", "strength_and_weaknesses": "Strengths:\n--- Clear and easy to read\n--- Empirical evaluations are interesting and useful. \n\n\nWeaknesses:\n--- The paper lacks solid theoretical justification. They cite Das/Kempe 2011 who analyze linear regression functions, but miss citing some other relevant literature that very likely covers their cost functions. \n\nGeneral cost functions: \nRestricted strong convexity implies weak submodularity. Elenberg et al. Annals of Stats\n\nStreaming feature selection: \nStreaming Weak Submodularity: Interpreting Neural Networks on the Fly. Elenberg et al. Neurips 2017\nOnline Streaming Feature Selection. Wu et al. ICML 2010\n\n--- While the authors have tried to cite many relevant works, the citations on feature selection are still limited. For example, gradient \nbased feature selection is also covered in Elenberg et al works above and other works such as: \nFast Feature Selection with Fairness Constraints. Quinzan et al. \n\n--- I am not sure why modeling p(x_i | x_s) as explained in Sec 3.2 is even important. Sec 4 onwards the authors explain ways to circumvent it. But many other methods (some of which are listed above) only care about the correlation with y when selecting features (along with iterative strategies that ensure the selected features are uncorrelated amongst themselves). This also obviates the development in Sec 4. \n\n\n\n--- Other than the above point, I am not sure why E_s in the cost function is a good idea, especially in a greedy strategy. Why would one want to take an expectation over ALL subsets of size s when we care only about a particular set as formed by the greedy strategy? Is that not a gross overkill ? It seems it is done for a theoretical justification, but again, it seems unfounded and not really required given theoretical justification based on weak submodularity. \n\n--- The section on greedy suboptimality is interesting, but I think it is also superseded by the weak submodularity papers.\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "DtMyfL5-oh", "reviewer": "Reviewer_84q8", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work studies an RL-based greedy feature selection algorithm that uses\nconditional mutual information with the label as the scoring criteria. The\nauthors propose using a differentiable method in each greedy step by combining\nthe true model and the \"concrete distribution\" (for feature masking) to learn\nthe best policy given the current set of features, i.e., to identify the next\nbest feature. They provide some theoretical justification for their approach,\nand give a diverse set of feature selection experiments that suggest their\nmethod is both effective and practical.", "summary_of_the_review": "This paper is on to something, especially if the experiments are dominant\nacross many averaged trials and model trainings. That said, I think the paper's\nmessage could be greatly simplified by very directly presenting the algorithm\nand not justifying all of the decisions with lemmas about mutual information,\nsince most these ideas are reasonably well-known. I recommend the paper be\nrejected from ICLR 2023, but encourage the authors to refine the work and\nresubmit to a comparable venue in the future.", "strength_and_weaknesses": "**Strengths:**\n- Example 3 is a nice instance that shows the difficulty of feature\n  selection, especially when using pairwise feature information.\n- The experiments look *very strong*. Other methods seem somewhat noisy and\n  \"less monotonic\". How many trials were used for the different methods -- both\n  feature selection and model trainings?\n\n**Weaknesses:**\n- The paper bounces back and forth between \"combinatorial\" and RL-based feature\n  selection.  It would be beneficial to present the main algorithm as directly\n  as possible (possibly by just explaining all the details of Figure 1): how\n  exactly do you use RL, what is the differentiable masking expression, is the\n  criteria ultimately that of the downstream model, etc. There are many more\n  details and asides that take away from the empirical results.\n- Is Theorem 1 actually true? In the hidden XOR case if $y = x_1 \\otimes x_2\n  \\otimes x_3$ and $d = 10$, then in the second step of feature selection, all\n  candidates are equally good (i.e., we don't need to put all the mass on one\n  feature). Maybe say \"a global optimum\" in the event of ties.\n- This work isn't really about \"online feature selection\" -- it's just adaptive\n  and \"normal\" supervised feature selection.\n- In Section 6.1, you have \"In each of these problems, gathering all possible\n  inputs is impractical due to time and resource constraints, thus making\n  online feature selection a natural solution.\" How do you learn the RL policy\n  then? It seems that you need all of the features since you learn a mask on the\n  unselected features via RL and the downstream model.\n- Table 1: Why is the mean loss for different feature set sizes a meaningful\n  quantity? It carries some signal, but these values are better understood when\n  plotted as a Pareto curve as in Figure 2.\n- It would be valuable to compare your RL-based greedy algorithm to the true\n  greedy algorithm that compute the conditional mutual information in each step\n  (relative to set $s$). Of course, this can be too expensive to compute in\n  practice, but it would be valuable to know ``what is achievable'' as an upper\n  bound and how close your algorithm comes to that.\n\n**Suggestions:**\n- [page 2] Suggestion: The conventional notation is to use $S \\subseteq [d]$ for\n  a subset of features (i.e., capital $S$).\n- [page 4] It would be worthwhile to discuss how $I_i^n$ in Equation (5) is\n  related to the empirical conditional mutual information on the training data.\n- [page 7] Suggestion: The related works section would go better at the end of\n  the introduction. \n- [page 7] In the related works when discussing \"iterative feature scoring\n  methods\", it would be good to cite the landmark paper \"Fast binary feature\n  selection with conditional mutual information\" (Fleuret JMLLR, 2004) for the\n  CMIM algorithm, since this is a strictly combinatorial version of the (binary)\n  cross entropy algorithm you propose.\n- [page 7] How do you differentiate online feature selection vs \"offline\n  feature selection\". As far as I can tell, these problems are equivalent and\n  best described as \"feature selection\" or \"supervised feature selection\".\n- [page 8] Suggestion: Include the standard deviation of each value in Table 1.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject