Scalable feature selection via sparse learnable masks
Authors: Yihe Dong
Sercan O Arik
Venue: Submitted to ICLR 2023 (2023)
Keywords: Feature selection
mutual information
end-to-end learning
sparse mask

Abstract: We propose a canonical approach for feature selection, sparse learnable masks (SLM). SLM integrates learnable sparse masks into end-to-end training. For the fundamental non-differentiability challenge of selecting a desired number of features, we propose duo mechanisms for automatic mask scaling to achieve the desired feature sparsity, and gradually tempering this sparsity for effective learning. In addition, SLM employs a novel objective that maximizes the mutual information between the selected features and the labels. Empirically, SLM achieves state-of-the-art results on several benchmark datasets, often by a significant margin, especially on real-world challenging datasets.

Under review as a conference paper at ICLR 2023
SCALABLE FEATURE SELECTION VIA SPARSE LEARNABLE MASKS
Anonymous authors Paper under double-blind review
ABSTRACT
We propose canonical approach for feature selection, sparse learnable masks (SLM). SLM integrates learnable sparse masks into end-to-end training. For the fundamental non-differentiabilit challenge of selecting desired number of features, we propose duo mechanisms for automatic mask scaling to achieve the desired feature sparsity, and gradually tempering this sparsity for effective learning. In addition, SLM employs novel objective that maximizes the mutual information (MI) between the selected features and the labels, an efficient and scalable way. Empirically, SLM achieves state-of-the-ard results on several benchmark datasets, often by a significant margin, especially on real-world challenging datasets.
INTRODUCTION
R1: In many machine learning scenarios, a significant portion of the input features may be irrelevant to the output, especially with modern data management tools allowing easy construction of large- scale datasets by combining different data sources. 'Feature selection', filtering the most relevant features for the downstream task, is an everlasting problem. with many methods proposed to date and used (Guyon Elisseefi 2003 et al. 2017: Dash & Liu 1997). Feature selection can bring a multitude of benefits. Smaller number of features can yield superior generalization and hence better test accuracy, by minimizing reliance on spurious patterns that do not hold consistently (Sagawa et al.) 2020), and not wasting model capacity on the irrelevant features. In addition, reducing the number of input features can decrease the computational complexity and cost for deployed models, as the models need to learn the mapping from smaller dimensional input data, and the reduced infrastructure requirement to support only the selected features. Lastly, feature selection helps with interpretability, as the users can focus their efforts to understand the model to a smaller subset of input features.
RI: How can we select the target number of features in an optimal way? Feature selection has been studied with numerous approaches, summarized in { For superior task accuracy. the feature selection method should consider the predictive model itself, as the optimal set of features would depend on the how the mapping is done between the inputs and outputs. Such methods have been approached in different ways, such as via sparse regularization and its extensions (Lemhadri et al. 2019). In the context of deep learning, the fundamental challenge is the selection operation (given the target number of selected features) being non-differentiable This necessitates design of soft approximations for feature selection operator, incorporated into end-to-end task learning.
R1: To address these fundamental challenges, we propose Sparse Learnalee Masks (SLM), novel approach for scalable feature selection. SLM can be integrated into any deep learning architecture, given the optimization is gradient-descen way of adjusting the learnable masks to select the exact number desired features, addressing the differentiability challenges. In addition, SLM uses novel mutual information (MI) regularizer, based on a quadratic relaxation of the MI between the labels and the selected features, conditioned on the probability that feature is selected. SLM comes with scaling benefits, yielding efficient feature selection even when the number of features or samples are very large. We demonstrate state-of-the-art feature selection results with SLM in different scenarios across a wide range of datasets.
based for joint training. SLM proposes effective
2 RELATED WORK
Feature selection methods: Numerous methods have been studied for feature selection, and broadly fall under three categories (Guyon & Elisseeff 2003):

---

Under review as a conference paper at ICLR 2023
Wrappers recompute the predictive model for each subset of features. As exhaustive search is NP-hard and computationally intractable, efficient search strategies such as forward selection or backward elimination have been developed. For instance, HSIC-Lasso (Yamada et al., 2014) proposes a feature-wise kernelized Lasso for capturing non-linear dependencies. Wrappers are difficult to integrate with modern deep learning, the training complexity gets prohibitively large.
Filters select subsets of variables as a pre-processing step, independent of the predictive model. (Gu et al. 2012) developed the Fisher score, which selects features to maximize (minimize) the distances between data points in different (same) classes in the space spanned by the selected features. Principal feature analysis (PFA) (Lu et al. 20076) selects features based on principal component analysis. (Pan et al. 2020) uses adversarial validation to select the features, based on how much their characteristics differ between training and test splits, as a way to improve robustness. There are also various methods based on MI maximization (Ding & Peng 2 selecting features independent of the predictive model (unlike SLM). CMIM (Flcuret 2004) maximizes the conditional MI between selected features and the class labels to account for feature inter-dependence JMIM (Benmasar et al. 2015) maximizes the joint MI between class labels and the selected features, while addressing overconfidence in features that correlate with already- selected features, with greedy search that selects features one at a time. (Zadeh et al., 20177) formulates feature selection as diversity maximization problem using MI-based metric amongst features. The fundamental disadvantage of ilter-based methods, of not being optimized with the predictive models, results in them often yielding suboptimal performance.
Embedded methods combine selection into training and are usually specific to given predictive models. Lasso regularization [Tibshiran]] 1996) employs feature selection by varying the strength of the L1 regularization. (Feng & Simon (017) extends this idea by proposing an input-sparse neural network, where the input weights are penalized using the group Lasso penalty. (Lemhadri et al. 2019) selects only a subset of the features using input-to-output residual connections, allowing features to have non-zero weights only if their skip-layer connections are active. R3:
Concrete Autoencoder (Abid et al. 2019) proposes an unsupervised feature selector based on using a concrete selector layer as the encoder and using a standard neural network as the decoder. FsNet (Singh et al., 2020)) uses concrete random variable for discrete feature selection in a selector layer and a supervised deep neural network regularized with the reconstruction loss. STG (Yamada et al., 2020) learns stochastic gates with a probabilistic relaxation of the count of the number of selected features, it selects features and learns task prediction end-to-end.
Masking in deep neural networks: Masking the inputs to control information propagation is a commonly-ure used approach in deep learning. Attention based architectures, such as the Transformer (Vaswani et al.] 2017) and the Perceiver (Taegle et al. 202T), show strong results across many domains, with learnable key and query representations, whose alignment yield the masks that control the contribution of corresponding value representations. While these effectively reweight the inputs, they typically do not completely mask out (i.e. yielding zero attention weight) the inputs. Towards this end, various works have focused on bringing sparsity into masking, such as based on thresholding (Zhao al. 2019) sparse normalization (Correia al. 2019). TabNet (Arik & Pfister 2019) directly generates sparse attention masks and applies them sequentially to input data, which can perform sample-dependent feature selection. R1: (Correia al. 2020) achieves sparsity in latent distributions in neural networks, by using sparsemax and its structured analogs, allowing for efficient latent variable marginalization. (Lei et al. (016)) and (Bastings et al. 2019) learn Bernoulli variables. which are analogous to our feature mask but in local setting, for extractive rationale prediction in text. (Paranjape et al., 2020) extends these ideas by proposing to control sparsity by optimizing the Kullback-Leibler (KL) divergence between the mask distribution and a prior distribution with controllable sparsity levels. (Guerreiro & Martins 202T) develops a flexible rationale extraction mechanism using constrained structured prediction algorithm factor graphs, All these perform sample-wise, not global, input selection. R3: In this work, our goal is to explore global feature selection. When train and test sets perfeetly align in distribution, local feature selection can give superior performance due to its input- input-dependence. However, there is rarely such perfect alignment, and global selection provides robustness benefits when there is distribution shift between train and test sets, in addition to allowing more computational efficiency by globally removing features.
3 METHODS
Algorithm| deseribes SLM's end-to-end feature selection and task learning. The predictor fo can be any gradient-descent based model, such an MIP,, with R3: task-specific loss function l such as
2

---

Under review as a conference paper at ICLR 2023
cross entropy for classification or MAE for regression. The following sections present SLM's key components in detail.
Notation. R1: R2: R3: Throughout this work, we let X E Raxd denote the input data, Xsp E IRa the selected features, and mup E Rd the learned feature selection mask. We use @ to denote element-wise multiplication between each input sample and map: Xup = X O mag. We let F; denote the number of selected features at step i, and N the total training steps. Furthermore, Y) denotes the mutual information between X and Y. and (x, its quadratic relaxation.
ALGORITHM Training for SLM-based feature selection.
Input: Input data with target labels Y
Input: Total training steps N Initialize: Learnable mask argument m f- all ones vector for f. 1 to N do
Obtain the number of selected features F3 using Eq 4 for step t.
Generate sparse mask sup sparsemax(m).
Select and weight input features: Xap = X @ Map. Non-selected features are zeroed out. Input the selected features into the predictor fo(Xsp) for the downstream task.
Compute training task loss ( (X.p,, Y) and MI loss E(X.p. Y) in Eq 9
Update the parameters 9 and m, using task loss I and MI loss E.
3.1 MASK SPARSITY
R1: R3: SLM selects features by learning a mask msp E R and zeroing out the features in the input X E Raxd whose corresponding mask entries are zero. We use sparsemax normalization (Martins & Astudillo, 2016) to achieve sparsity in m. Sparsemax achieves sparsity in its output by returning the Euclidean projection of the input vector v E Rd onto the probability simplex Ad-1 = E Rd Σx f& 1}:
sparsemax()) = argmin -p- 011².
We apply sparsemax to the mask argument m Rd obtain sparse feature mask:
map sparsemax E RS
(2)
For the commonly- used softmax normalization is employed with thresholding, the probability simplex projection in sparsemax(r) scales the top values in so they are more equidistributed over [0, 1]. This equidistribution leads to greater feature weight separation, encouraging the model to discriminate amongst the features.
3.2 MASK SCALING TO YIELD DESIRED NUMBER OF SELECTED FEATURES
Following its formulation, sparsemax does not yield a predetermined number of non-zero elements, as the sparsity depends on the location on the probability simplex A d-11 that projects onto. For non-uniform vector u R2, we can adjust its projection onto A d by multiplying v by a positive scalar. In partieular, sufficiently large scalar increases the sparsity, while sufficiently small scalar decreases the sparsity. To illustrate this, we give a simple example in [
Example 3.1 (Adjusting sparsemax(1) sparsity by scaling). The probability simplex A in IR2 the line connecting (0, 1) and (1, with these two points the simplex boundary. Let (z, y) be point in 2 and (z, w) its projection onto A We show that by varying multiplier m, sparsemax (mv) would have varying degree of sparsity. The projection (z, w)) sparsemax (ar, y)) is the unique point that satisfies (2, w) = argmin (=.w) (lly - w/ + ||x - ). (z, w) elementwise positive, and
+ w 1. As we scale (z, y) with m, pparsemax(m(z,))) v)) ar argmin (IImy w|l + |mmz 21l?). This projection distance expands
d(z, w) = |m 12 + | - x|12
= mm 2myw + 2² + m² 2mrz + 22
Hence, 1( d(0.5, 0.5) = mar - my + 0.5, which means that for any (x,, y) and m with y > x, sparsemax(mmz,, v)) is closer to (0, 1) E A whenever m > 1/(2(y - x)). and closer to (0.5, 0.5) otherwise. Since projection is linear, this means varying the multiplier m varies the sparsity of sparsemax((z,9))
3

---

Under review as a conference paper at ICLR 2023
This example conveys the intuition that larger multipliers lead to sparser outputs. More generally, one can show:
144
simplex
12
Lemma 3.2. Given non non-uniform vector R., to obtain F nonzero elements in sparsemax(1), ),, v should be multiplied with the scalar
0.8
E - (()) (F+ +0+1 (((+)))))
if sparsemax(()
> 01
m
0.4
1i=1 D(i) F. .r)
if sparsemax(() 0
F
(3)
where v(1) 2 1(2) 2 ((a) denote sorted elements of u in descending order.
0.00
0.25
0.50
0.75
100
Scaling from the black to the red point moves its projec- tion (green dotted line) onto A closer to the sim- plex boundary, increas- ing sparsemax(v) spar- sity.
Figure 1:
The proof can be found in A.3
Lemma 3.2 allows us to scale the mask to achieve the desired number of non-zero features. R1: Note that since sparsemax has particular scaling its argument by m is equivalent scaling the regularizer by 1/m in the Fenchel-Youee formulation (Blondel et al.] 20200 Peters et al. 2019).
loss (Blondel et al. 2020),
3.3 TEMPERING FEATURE SPARSITY
Starting training on only a randomly selected subset of features likely leads to suboptimal learning in the initial steps, and if feature selection converges before the predictor converges, the predictor would be trained with suboptimal features. To alleviate these and improve training stability, we propose gradually decreasing the number of features selected until reaching the target Fx:
Fo FNN LIN
EN)
if l < Nomp
F. =
if Nemp:
where F3 is the number of selected features at step f, Nemmp is the tempering threshold. In our experiments, we simply set Ntmp = N/2 as it was observed be a reasonable value across wide range of datasets. To further stabilize training, instead of continuously decreasing the number of features, we decrease the number of features at five evenly spaced steps. This tempering allows the model to learn from more than the final target number of features during training not shared by baseline methods. Furthermore, learning from all features initially likely provides a more robust initialization compared to starting learning with the target number of features, as the randomness in the initial selection is seldom optimal.
advantage
3.4 MUTUAL INFORMATION MAXIMIZATION
As an inductive bias the model that accounts for sample labels during feature selection, we propose to maximize the mutual information (MI) between the distribution of the selected features and the distribution of the labels. Specifically, we condition the MI on the probability that a feature is selected, as given by the mask m. This stands in contrast to prior MI-based feature selection works such as (Fleuret 2004 Bennasar et al. 2013), which yield binary decisions on whether to select a feature.
Let X denote the random variable representing the features, and Y the random variable representing the labels, with value spaces X X' and Y V. Methods based on maximizing either the conditional or the joint MI between selected features and labels require the computation of an exponential number of probabilities, the optimization of which is intractable (Fleuret) (2004). R2: Therefore, we propose quadratic relaxation of MI, which is end-to-end differentiable. When we model X and Y as random variables, their MI (X
can be defined and reformulated as:
(T,))== Ensx Eyey Px,y (x. boloy)oogg log (a. u) Py)
I(X, Y,,Y)= =
Px,((z,)) =LErEx Eye log Px,((x.))
- vEy
Pv log (v), (5)
Px(x)
where the second step derives from marginalizing over X. Since the second term above does not depend on features X, it can be ignored during optimization.
4

---

Under review as a conference paper at ICLR 2023
Quadratic relaxation. We propose quadratic relaxation Ig(X, of Eq simplify I(X, Y) and its optimization, while retaining much of its properties:
1(X,Y)= (EREx Pxr(x.)))) - ENye Pr(v)² P
(6)
Here, terms of the form p logg q are relaxed to pq. Note that both p plog q and pg are convex with respect to p and q, and hence have the same correlation behavior with respect to and q. From an optimization perspective, [X, Y) is good approximation of [XX, Y) where Px,y (X, /x)x(()) and (y) in Eq 6 lie in the neighborhood 11-6,1+0). In this neighbor- hood, using Taylor expansion: log (4) 1og(()) + (ggg9o//ol /000/////////////// (//000)22200))) +... When g0=1, this becomes
3/300//2//-//22--------- /2, hence, log( has the second order approx- imation - 2pp2+2p (or - 2pp222pp when p=q). Applying this to Eq 5 is (x, y) in the first term and (v) in the second. Since both Px.y (æ. y) and Py (v) probabilities, and hence must sum to across the label space for any given sample, the linear term - -pp/2 does not affect gradient descent optimization. Normalization linear term in the objective. Therefore, during optimization, Px,y (ar, y) log( Px,y (I, y)/ (x)) and Px.y (x, // Px (z), and thus Lg (X, Y) and (X, Y). agree on their second order approximation. Note that the proposed relaxation is variant of the commonly-used quadratie approximation based on Taylor's 's theorem (Shafer 1974 Hsieh et al. (011).
hard constraint enforced during training that supersedes this
Relating MI Y) to model error E(X, Y). Next connect (X(X,)) Y) with the model's predictions using Lagrange multipliers. Let R(x, y) X' x y - [0, 1] denote the model's probability output for sample æ and outcome y. Below we model the discrete label case, e.g. for elassification; the case where labels are continuous can be reduced to the discrete case by quantization (Fleuret 2004]. First, we define the quadratic error term E(X, Y) terms of R(z, y). and expand:
(1 (a- (1- R(x, 2)) Everr R(x,5'²)
E(X,Y) E (x)((1)))
- Px.((r,)
1 1- (-22 + R(x,1)² + Every R(x,8/)²)
- (x, -2 2 LxExyEy (x,((,,)))(a
+ +E E ((2 Combine last two terms and expand.
= =1-2 > EmEXyey
+ Enexwey (( < Marginalize.
Theorem 3.3. Let and denote the random variables representing the features and labels, respectively, and y the value space for Y. then maximizing the quadratic relaxation of mutual information [X, Y') is equivalent to minimizing the error E(X,Y) More specifically,
() x) E - L(X,Y).
The proof uses Lagrange multipliers to solve for the optimal model predictions in terms of Px,y (x, v) and Px (x), this can then be used to express the objective E(X, as a function of Ix,X, Y). The full proof can be found in A..4
Application to feature selection. Now, we apply this finding concretely to feature selection, by selecting given number of features that minimize E(X, Y). Given dataset, let I denote the index set of the dataset samples, J the index set of the features, and L the set of possible labels. Let C J denote the index set of features selected, X the random variable representing a selected subset of features for the th sample, and Y, the random variable representing the label for the 8th sample. Then, the joint probability can be written as Px,y(x, y) = (i I = x, Y, / Plugging this into the definition of FXXX, Y) obtain:
5

---

Under review as a conference paper at ICLR 2023
E(X,Y) Emex (x, (1--((,)))) + R(x,
-ErExwEy E X = x, = =HHl (1-R(X; Y:)) +
uyY R(X; x))²)
[
-ier ( (1-R(X;) Yi))
Σ UzY, R(X; (,x;,)))/1Z7) /zZi
(8)
During training, Eq. 8 is minimized under the following consistency constraint: for two samples il and i2 that have the same values in the selected features, i.e. x X their model predictions must be the same, i.. R(X;, X,) = R(X;, Y12). To encourage the model to satisfy this constraint, turn it into soft consistency regularization term Tes, converting constrained optimization to unconstrained optimization with regularization:
ros Σ (1idi))zz P(X; x (R(X,, Y1,) R(X;, X.))
where P(X; x is the probability that the samples X;, and Xi, take the same values in the selected feature S.
Let the learned mask consists of probabilities m {pibee,, i.e. Pj is the probability that feature j is selected, then P(X; = x = xx + (1 Pý). i.e. P(X; = =x;² is the product over probabilities that feature j is not selected, if X; and X;, differ at feature j. (The difference in a feature that not selected does not contribute to P(X; is x²))). In this probabilistic form, the consistency regularizer also encourages the selection of features with diverse ranges, since it encourages high Pj for the features with many x-()) + x pairs. Therefore, the regularized objective to maximize the MI I [XX, Y) between the selected features and the labels becomes:
-ier ( (a--R(X; (I-R(X;))) x.)) + E UxY R(X..1)) /
Tes
where
II [IN p2) (R(X;, Y., R(x (..))
Tos L ia
(10)
R1: In practice, Tos can be enforced batch-wise, and can be efficiently vectorized for the parallel computation of all x()) * x(i) pairs per batch using tensor operations. Note that since R(XS, Y;) are just model predictions, and pý are learned feature mask probabilities, each component in E(X, Y) easily accessible. When the labels are in the continuous space, the minimization objective with the consistency regularizer is derived the exact the same way to yield:
E(X,Y) Σier (Y, R(X;))² /|Z + Tes-
Our analysis is done with random variables X and Y to apply tools from probability theory, the data samples X and labels Y can be thought of as samples drawn from the distributions to which X and Y belong, where in the limit with infinitely many samples X and Y perfectly reflect these distributions.
3.5 COMPUTATIONAL COMPLEXITY
R1: As above, let h be the hidden dimension, n denote the number of samples, the batch size, and N the total number of train steps; let Fo be the total number of features, and Fx the target number of features. We first discuss the complexity of individual components. The sparsemax operation dominated by sorting, and hence has complexity O(Fo log Fo) per sample, with an overall complexity of OnFF log Fo). The consistency regularizer Tes in the MI-maximizing objective E ((X, Y) has complexity OnbFN)),
the calculation x f 3 Eq 10 occurs over the selected feature index set j S. and is done between each sample and others in its batch. The non-regularizer component E(X, X Y) has complexity ne, where c is the constant for the number of discrete or binned labels. Assuming MLP classifier with hidden units, which
pU) (R(X, Y.) R R(X, Y.)) in

---

Under review as a conference paper at ICLR 2023
has complexity O(nh²), the overall algorithm has complexity On log Fu nbFy + nc + nh?), making SLM amenable to scaling to a large number of features. R3: In addition, SLM amortizes the cost of feature selection across batches throughout training, making it more scalable with respect to the number of samples. This is in contrast to PFA (Lu et al. 2007a) or many other MI-hased methods such CMIM (Fleuret (004) or JMIM (Bennasar al., al.]| 2015), which place the memory and compute burden of selection for the entire dataset in the same step.
4 EXPERIMENTS
4.1 DATASETS AND SETTINGS
We present the efficacy of SLM in feature selection on wide range of datasets from numerous domains. For all experiments, we ensure fair comparison by employing similar hyperparameter search space and budget- - to search for hyperparameters such as batch size and learning rate for each baseline method and dataset, we conduct an extensive random search within the search grid, by randomly generating a value within a conceivable range. We run total of 300 trials for each method-datased combination to ensure sufficient coverage, and tune all hyperparameters based on the validation accuracy. R1: R2: R3: Additional experiments on selected feature interpretability, compute timings and synthetic data experiments to demonstrate SLM's scalability, as well as comparison with further end-to-end baselines, can be found in [A.6] A.7
A.8
A.9.
respectively.
We benchmark on a variety of real-world datasets across many domains, including computer vision, biological data, financial data, etc. Concretely, we benchmark on Mice, MNIST, Fashion-MNIST, Isolct Coil-20, Activity, Ames Housing, and IEEE-CIS Fraud datasets. R3: We use a 10-10-20 train/validation/tess split; and when available, we use the exact same train/validation/tesst samples as (Lemhadri et al. 2019) for fair comparison. We give further detailed descriptions in AA. Cross entropy is used as the task loss function for classification tasks, and MAE the task loss for regression.
We benchmark SLM against a variety of competitive methods. The mutual information (MI) based feature selection baseline uses entropy estimation from k-nearest neighbors distances described in (Kraskov et al.] [004] Ross 2014) to estimate MI. Tree-based methods yield Gini importance scores, which can be used for feature selection. For this we benchmark two commonly used methods: random forest (RF) (Breiman 2001), an ensemble of independent trees, and XGBoost (Chen &
Guestrin 2016). a scalable end-to-end tree boosting system. We furthermore benchmark against methods as discussed in 2 LassoNet (Lemhadri et al., 2019). which uses residual connections to allow the network learn whether to use any given feature in particular layer; feature importance ranking based on the Fischer score (Gu et al. 2012); principal feature analysis (PFA) (Lu et al., 2007a), a PCA-based method; and HSTC-Lasso Yamada et al. 2014),, which uses kernel learning to find non- feature interactions. Lastly, we benchmark against linear regression, where feature importance is determined by the Icarned feature coefficients. When available, we use results from (Lemhadri al. 2019). R1: For consistency and fairness, each baseline method uses the same input as SLM to select features, which are then passed to an MLP to compute the task metric.
4.2 TASK PERFORMANCE WITH FEATURE SELECTION
RI: In this work, we consider feature importance to be measured by contribution towards the task metric, as accurate predictor performance is typically the end goal, and the importance of each individual feature is not well-defined due to feature interactions. Therefore, we focus on benchmarking task predictive accuracy given the selected features as the metric.
First, we study selecting a fixed number of features across a wide range of high dimensional datasets (most with >00 features) and feature selection methods. R3: We consistently choose 50 selected features, as this represents small fraction of the total features for most datasets, as often done in practice. This number is kept consistent without tuning for any given method, avoid favoring any given one. Table I] shows that the SL.M consistently yields competitive performance, outperforming all methods in all cases except on Mice and Ames, for which the performance saturated due to small numbers of original features, making feature selection less relevant. Most feature selection methods are not consistent in their performance. On the other hand, SLM's strong performance is consistent. Interestingly, we observe that there are cases where SLM even outperforms the baseline of using all features, which can likely be attributed to superior generalization when the limited model capacity is focused the most salient features.
Next, we focus on the Fraud dataset, a large-scale dataset for the complex task from many heteroge- neous features. It is highly non i.i.d. (Grover et al. 2022), thus making feature selection important
7

---

Under review as a conference paper at ICLR 2023
Method
Micef
MNISTT
Fashion
Isolet
Coil-201
Activity?
Ames.
Fraud
All-features
0.990
0.928
0.833
0.953
0.996
0.956
0.283
0.782
SLM (ours)
0.981
0.953
0.835
0.919
0.996
0.947
0.274
0.911
Fisher
0.944
0.813
0.671
0.793
0.986
0.769
0.286
0.743
HSIC-Lasso
0.958
0.870
0.785
0.877
0.972
0.829
0.273
0.846
PFA
0.939
0.873
0.793
0.863
0.975
0.779
0.356
0.852
XGBoost
0,968
0,913
0,832
0.879
0.986
0.926
0.403
0.872
MI
0.949
0.882
0.645
0.751
0.976
0.883
0.335
0.711
Linear
0.982
0.452
0.787
0.760
0.983
0.914
0.318
0.871
Anova 0.995
0.113
0.719
0.811
0.986
0,901
0.358
0.744
RF 0.967
0.928
0.829
0.892
0.993
0.893
0.303
0.773
Lassonet
0.958
0.873
0,800
0,885
0.991
0.849
0.342
0.842
Table I: Test performance on real-world benchmarks with 50 selected features. SLM outperforms competitive baselines. The metrics reported are AUC for Fraud, since there a high class imbalance; hence AUC is reported; the median MAE accuracy is reported on all other datasets. The arrow next to each dataset indicates whether a higher lower value is more optimal. These test results selected based the best validation set performance during 300 hyperparameter grid search trials.
coandard-normaaizee
labels is reported for Ames; and
given that high capacity models be prone overfitting and poor generalization. Table 2 shows that SI.M outperforms other methods consistently for different number selected features, and its performance degradation with much less number of features is smaller. Indeed, the AUC with 20 features out of 432, is >> 10% better than using all features, indicating improved generalization.
Test AUC
Method
20 features
50 features
100 features
SLM (ours)
89.32
91.06
91.75
Anova
71,81
74.41
82.91
RF
72.16
77.29
78.72
Linear
84.32
87.11
87.46
MI
65.37
71.05
74.91
XGBoost 85,45
87.24
81.67
Table 2:
Test AUC Fraud dataset with different feature selection methods, choosing 20, 50 100 features. The superiority of SLM persists across different numbers of selected features.
4.3
ABLATION STUDIES
Effects of MI regularizer
Effects of Tempering
Performance vs # of features selected
rogularizer
tomporing with tempering
0.94
MI regularizer
094
0.94
0.2
Accuracy
0.90
0.88
0/83
0.86
0.5
0.84
Mice
Islett
Mice
Isolet
Dataset
Dataset
3) # features selected
Figure 2: (1) and (2) show ablation studies the effect of MI regularization and tempering the number of features. R3: Both ablation studies have the same number (50) of selected features on all datasets. (3) shows the task accuracy function of the number of features selected on the activity dataset. The dark line shows the average ten random hyperparameter trials, shown with light hue, demonstrating that task performance
be near-optimal
with small subset of features.
We study the utility of SLM components in this section, in particular the effects the MI regularizer and tempering the number of features, which gradually decreases the number of selected features
8

---

Under review as a conference paper at ICLR 2023
from the full feature set to the target number. The effects are measured by randomly selecting ten hyperparameter settings and a seed, and recording the average performance R3: with or without either MI regularizer or tempering (without tempering refers to keeping the number of selected features constant throughout training.). Fig 2 shows that both MI regularization and tempering positively affect task performance. This is consistent with the theory developed in [ the MI regularizer encourages maximal mutual information sharing between the labels and the selected features; and tempering allows the model to initialize learning based on all features, rather than randomly selected subset.
DISCUSSION
Feature importance intepretability. SLM learns sparse mask M that contains the feature selection coefficients. We show that this approach yields superior results with end-to-end learning by allowing a smooth transition between selecting and un-selecting features. In addition, SLM can also be used for interpretation of global feature importance during inference, yielding the importance ranking of selected features, similar to other commonly-used methods like SHAP (Lundberg Leel 2017). This can be highly desired in high-stakes upplications such healthcare finance, where importance score can be more useful than simply whether a feature is selected or not.
Feature interdependence during selection. Compared to prior MI-based feature selectors (Ding & Peng 2005; Fleuret 2004 Bennasar et al., 2015), SLM accounts for feature inter-dependenc by learning inter-dependent probabilities {p, hy for the selected feature, where {py jointly maximize the MI between features and labels. Furthermore. SLM learns feature selection and the task objective in end-to-end way, which alleviates the selection of repetitive features that may individually be predictive, as gradient descent favors increasing the probability for a non-redundant and loss decreasing but less predictive feature over an individually predictive but redundant feature.
Improved model generalization via feature selection. Feature selection can help improve general- ization beyond the training set, especially for high capacity models like deep neural networks, which can easily overfit patterns from spurious features that do not hold across training and test data splits (Arjovsky al. 2019). For instance, Table [ shows that on some datasets, especially with SLM, prediction on a subset of features can outperform that on all features. Furthermore, Fig 2 shows that task performance can reach near-optimum with even small subset of all features. Therefore, feature selection is potential alternative for alleviating compute cost during training and inference, without sacrificing on accuracy.
Relation to other MI estimations in deep learning. R2: MI-based objectives have been used in other deep learning methods, such as InfoNCE (Oord et al. 2018), InfoGAN (Chen et al.) 2016), and Deep Graph Infomax (Velickovic al. 2019). To estimate MI, these typically train classifiers samples drawn from the joint distribution and the product of the marginals, whose exact distributions can be intractable. In contrast, for feature selection, while the exact distributions of the features and the labels are known, the computation of their mutual information and its maximization is computationally intractable. To address this. SLM proposes a quadratic relaxation MI optimization, applied to feature selection by converting MI maximization to minimizing a loss function. SLM does not need sample from the joint or marginal distributions, a potentially computationally intensive process. Furthermore, prior works (Chen et al. 2016 Velickovic et al. 2019) often require a contrastive term in estimation of MI with negative sampling, a process that is not needed in SLM.
Future work. SLM can be integrated into unsupervised or semi supervised learning, with modified objectives. In addition, our results indicate more significant outperformance for datasets with non i.i.d. characteristics as feature selection can effectively reduce the feature dimensionality and reduce the risk of overfitting to the spurious correlations of irrelevant features. Lastly, feature selection for data with structure (e.g. temporal or graph) is interesting extension, which might be based on modifying SLM to apply masking to entire time-series or graph data.
6 CONCLUSION
We introduce SLM, sparse learnable mask based feature selection framework that maximizes the MI between features and labels, while optimizing the training objective end-to-end. Learning the feature masks allows smooth, probabilistic selection of features as well as insights feature importance. SLM demonstrates competitive performance against SOTA baselines, and opens door to future applications in domains such graph or time series representation learning.

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
p gives detailed description of the methodology used. All results derive from repeated cross validation. In particular, the main results reported in [ derive from extensive grid search during 300 trials for each method-dataset combination, where the test result based on the best validation performance reported. Code will be open-sourced after the review process.
REFERENCES
Abubakar Abid, Muhammed Fatih Balin, and James Zou. Concrete autoencoders for differentiable feature selection and reconstruction. Proceedings of the 37th International Conference on Machine Learning, 2019.
Sercan O. Arik and Tomas Pfister. Tabnet: Attentive interpretable tabular learning, 2019.
Martin Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Paz. Invariant risk minimization, 2019. /ttppsttss//aaxxvv.oo orgg 907 02893
Jasmijn Bastings, Wilker Aziz, and Ivan Titov, Interpretable neural predictions with differentiable binary variables. In Proceedings of the 57th Anmual Meeting of the Association for Computational Linguistics. pp. 2963-2977, Florence, Italy, July 2019. Association for Computational Linguistics. doi: 10.18653/v1/P19- 1284. URLhttps: a anthol http:hhhlllly..r//1111e///
Mohamed Bennasar, Yulia Hicks, and Rossitza Setchi. Feature selection using joint mutual informa- tion maximisation. Expert Systems with A 42(22):8520-8332, 2015. URL https
w/www. www.nccieeeedi..o rect. cwm wtt.:///c...accce....rree///////
Mathieu Blondel, André F. T. Martins, and Vlad Niculae. Learning with fenchel-young losses. In Journal of Machine Learning Research, 2020.
Leo Breiman. Random forests. Machine learning, 45(1):5-32, 2001.
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In KDD, 2016. doi: 10.1 (0.1145/2336772.29900 29397785.
Xi Chen, Yan Duan, Rein Houthooft, John Schulman, Ilya Sutskever, and Pieter Abbeel. Info- gan: Interpretable representation learning by information maximizing generative adversarial nets. Advances in neural information processing systems, 29, 2016.
De Cock. Ames, iowa: Alternative to the boston housing data an end of semester regression project. Journal of Statistics Education, 19, 2011.
Gonçalo M. Correia, Vlad Niculae, and André T. Martins, Adaptively sparse transformers. CoRR, Abs/1999.00015 2019. URL /RR/httt:://axi..rr///// www.or//aab//r/ooo 00015
Gonçalo M. Correia, Vlad Niculae, Wilker Aziz, and André F. T. Martins. Efficient marginalization of discrete and structured latent variables via sparsity. In Advances in Neural Information Processing Systems, 2020.
M. Dash and H. Liu. Feature selection for classification, Intelligent Data Analysis, 1(1):311-166 1997. ISSN 1088-467X. doi: http://dw...yyooooooosssssss442o URL https //www. www.sssceeeeeeieeeeeeeee
Chris Ding and Hanchuan Peng. Minimum redundancy feature selection from microarray gene expression data. Journal of bioinformatics and compulational biology, (02)):185-205, 2005.
Frederick J. Eggers and Fouad Moumen. American housing survey: Between-survey changes in the number of bedrooms unit, 2013.
Jean Feng and Noah Simon. Sparse-input neural networks for high-dimensional nonparametric regression and classification, 2017.
François Fleuret. Fast binary feature selection with conditional mutual information. Journal of Machine learning research, 5(9), 2004.
10

---

Under review as a conference paper at ICLR 2023
Prince Grover, Zheng Li, Jianbo Liu, Jakub Zablocki, Hao Zhou, Julia Xu, and Anqi Cheng. Fdb: Fraud dataset benchmark, 2022. URL hRLps:/:: /ttp://aavvvvv..a
http://bb//222...2mm2 http://wwww...../b/////2/...0... 14417
Quanquan Gu, Zhenhui Li, and Jiawei Han. Generalized fisher score for feature selection, 2012. URL
https: /wwp///a////// www.aa/........... 1202.3725
Nuno Miguel Guerreiro and André F. T. Martins. Spectra: Sparse structured text rationalization, 2021.
Isabelle Guyon and André Elisseeff. An introduction to variable and feature selection. Mach. Learn. Res., 3:1157-1182, mar 2003.
Cho-Jui Hsieh, Inderjit Dhillon, Pradeep Ravikumar, and Mátyás Sustik. Sparse inverse covariance matrix estimation using quadratic upproximation. Advances in neural information processing systems, 24, 2011.
Andrew Jaegle, Felix Gimeno, Andrew Brock, Andrew Zisserman, Oriol Vinyals, and Joao Carreira. Perceiver: General perception with iterative attention, 2021.
Kaggle. IEEE-CIS fraud detection, 2022.
URL httpss//w..kgggee..oom
leee- lest--ffrudddetecc
A. Kraskov, H. Stogbauer, and P. Grassberger. Estimating mutual information. Phys. Rev. E, 69, 2004.
Tao Lei, Regina Barzilay, and Tommi Jaakkola. Rationalizing neural predictions, 2016.
Ismael Lemhadri, Feng Ruan, Louis Abraham, and Robert Tibshirani. Lassonet: A neural network with feature sparsity. arXiv: /907. 2019.
2019.
Jundong Li, Kewei Cheng, Suhang Wang, Fred Morstatter, Robert P. Trevino, Jiliang Tang, and Huan Liu. Feature selection: A data perspective. ACM Comput. Surv. 50(6), dee 2017. ISSN 0360-0300 doi: (0.1145/3136625,
Yijuan Lu, Ira Cohen, Xiang Sean Zhou, and Qi Tian. Feature selection using principal feature analysis. In Proceedings of the 15th ACM international conference Multimedia, pp. 301-304, 2007a.
Yijuan Lu, Ira Cohen, Xiang Sean Zhou, and Qi Tian. Feature selection using principal feature analysis. In Proceedings of the 15th ACM International Conference on Multimedia, MM '07. pp. 301-304, New York, NY. USA, 2007b. Association for Computing Machinery. ISBN 9781595937025. doi: 10.1145/1211233119999
URL https:://6l.org//000
129
Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predic- tions. In I. Guyon, U. V. Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vish- wanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 4765-4774. Curran Associates, Inc., 2017. URL http:httpp/eete /ttppr/aapee..a//aa/peee www.siccppppp...e watpsscccpppppe /appp/pp// 7062-a-uni
ing mode -predictioons
Andre Martins and Ramon Astudillo. From softmax to sparsemax: sparse model of attention and multi-label classification. In International conference machine learning, pp. 1614-1623. PMLR, 2016.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding, 2018. URL URLl/ttpp:://rrvv.oorr//bb//
03748
Jing Pan, Vincent Pham. Mohan Dorairaj. Huigang Chen, and Jeong- Yoon Lee. Adversarial validation approach to concept drift problem automated machine learning systems. CoRR, 0bs/2004.030455 2020. URL https://arxivv http://awwwwvooo//aaaaa/aaaaaaa/ /204.. 03344000000000040303333 03045

---

Under review as a conference paper at ICLR 2023
Bhargavi Paranjape, Mandar Joshi, John Thickstun, Hannaneh Hajishirzi, and Luke Zettlemoyer. An information bottleneck approach for controlling conciseness in rationale extraction. In Proceedings of the 2020 Conference Empirical Methods in Natural Language Processing (EMNLP), pp. 1938-1952, Online, November 2020. Association for Computational Linguistics. doi: 10. 10.18653/v1/
2020.emnlp-main.155 URL //acl anwahoooyyyy.oo wrg./og...or././o 2000 emn p- in. 153
Ben Peters, Vlad Niculae, and André F. T. Martins. Sparse sequence-to se-uuencc models, 2019.
B. C. Ross. Mutual information between discrete and continuous data sets. PLoS ONE, 9, 2014.
Shiori Sagawa, Aditi Raghunathan, Pang Wei Koh, and Percy Liang. An investigation of why overparameterizzttoon exacerbates spurious correlations. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 8346 8356. PMLR, 13-18 Jul 2020. URL https::/prrocediin .ml.m.mr..... pre.s.sss.eespp.....mm..mm..
press / v v119/ wtw.://aaaaaaaaaaaa html
Robert E Shafer. On quadratic approximation. SIAM Journal on Numerical Analysis, 11(2):447446, 1974.
Dinesh Singh, Héctor Climente-Gonzäiae Mathis Petrovich, Eiryo Kawakami, and Makoto Yamada. Fsnet: Feature selection network on high-dimensional biological data. 2020.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodologicul), 58(1) 11:2772288, 1996.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention all you need. U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Gameet (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Asso- ciates, Inc., 2017. URL 1tteee225557deeeeeeo0d0o333ddod hatp://oossccccaaaaaaaaaaeeeee. pdf
Guyon,
hew.eiinn.nnnnnnuneeeeeeee neurips. cttppp..ccppppee cc/ppappr/2211///1eee
Petar Velickovic, William Fedus, William Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. ICIRR, 2(3):4, 2019.
Makoto Yamada, Wittawat Jitkrittum, Leonid Sigal, Eric Xing, and Masashi Sugiyama. High- dimensional feature selection by feature-wis wise kernelized lasso. Neural Computation, 26(1): 185-207, jan 2014. doi: 10. 162/necoo a 00537.
Yutaro Yamada, Ofir Lindenbaum, Sahand Negahban, and Yuval Kluger. Feature selection using stochastic gates. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. PMLR, 13-18 Jul 2020. URL httpt::::///... httpp::/ppoceedingggt.. .mw...mm.......mmmmmm..mm....... www.s..reessvill.1
yamada20a... html
Sepehr Abbasi Zadeh, Mehrdad Ghadiri, Vahab Mirrokni, and Morteza Zadimoghaddam. Scalable feature selection via distributed diversity maximization. In Thirty-Fine AAAI Conference on Artificial Intelligence, 2017.
Guangxiang Zhao, Junyang Lin, Zhiyuan Zhang, Xuancheng Ren, Qi Su, and Xu Sun. Explicit sparse transformer: Concentrated attention through explicit selection, 2019.
12

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A.1 DATASET DETAILS
This section provides additional details the experimental data. We first consider the real-world benchmark datasets in (Lemhadri et al. (019). Mice consists of protein expression levels measured in the cortex of normal and trisomic mice who had been exposed to different experimental conditions. Each feature is the expression level one protein. MNIST and Fashion-MNIST consist of 28-by-28 grayscale images of hand-written digits and clothing items, respectively. The images are converted to tabular data by treating each pixel as a separate feature. Isolet consists of preprocessed speech data of people speaking the names of the letters the English alphabet with each feature being one of the preprocessed quantities, including spectral coefficients and sonorant features. Coil-20 consists of centered gray-scale images of 20 objects taken at certain pose intervals, hence the features are image pixels. Activity consists of sensor data collected from a smartphone mounted on subjects while they performed several activities such as walking or standing. For these datasets, we use the exact same data splits and preprocessing approaches with (Lemhadri et al. 2019) for fair comparison, the same model hyperparameter search space In addition, we consider the Ames housing dataset (Cock) 2011). with the goal of predicting residential housing prices based each home's 's features; as well as the IEEE-CIS Fraud Detection dataset (Kaggle 2022), with the goal of identifying fraudulent transactions from numerous transaction and identity dependent features. Table 3
well as
summarizes the
characteristics of the datasets used in the experiments.
Dataset
Number of samples
Number of features
Number of classes
Mice
1080
77
8
MNIST
10000
784
10
Fashion
10000
784
10
Isolet
7797
617
26
Coil-20
1440
400
20
Activity
5744
561
Ames
1460
81
N/A
IEEE Fraud
590540
432
Table 3: Attributes of datasets used in experiments.
A.2 EXPERIMENTAL DETAILS
As described, we use hyperparameter tuning based on the validation accuracy for all cases, We use the Adam optimizer for training, with exponential decay. For benchmarks from (Lemhadri al.) 2019), for fair comparison, our hyperparameter search space is same as the original paper. For Fraud, which is larger and more complex, we extend the search space as in Table 4
Hyperparameter
Search space
Batch size
[512, 1024, 2048, 4096]
Learning rate
[0.001, 0.003, 0.01]
Decay steps
[1000, 10000]
Decay rate
[0.7, 0.9, 0.95, 0.99]
Number of epochs
[30, 100, 200]
Number of hidden units
[50, 100, 200]
Number of layers
[1, 2, 3, 4]
Table 4: Hyperparameter tuning search space for experiments on the Fraud dataset.
For baselines such as LassoNet, we tune additional method-specific hyperparameters. For instance, for LassoNet, in addition to the hyperparameters, also tune the l penalization on the skip connection, the hierarchy parameter, and the dropout rate. For XGBoost, we also tune the number of estimators and the maximum tree depth.
We use single layer multi-layer perceptron (MIP) as the predictor, where the number of units is chosen from 2M/3,2M/3 M, 4M/3).
13

---

Under review as a conference paper at ICLR 2023
A.3 PROOF OF LEMMA 3.2
Lemma 3.2. Given a nonuniform vector v E IR",, to obtain P nonzero elements in spansemax(t), should be multiplied with the scalar
F+1 i= v(a) -F*+ + x(0+11)
if (sparsemax()) > F
m
(11)
F Ci=i ((t) F UF)
if sparsemax(()) > 0 < F,
where v(1) 2 1(2) 2 ((K) denote sorted elements descending order.
Proof. We first show the case when sspassema (v) > 0| > i.e.
ie. the sparsity needs to be increased
(the case where sparsity needs to be decreased works analogously). By (Martins & Astudillo
2016). the projection of v onto A K in Eq takes the form sparsemax(t) = 1 7 where
[x] max zz and takes the form Eigaonn "(a)=1 with k(v) defined the index
k(w) := max kk {1,.... K} 1 kU(B)
Σ
"(1)
(12)
Hence, increasing the sparsity such that sparsemax outputs only F nonzero elements, i.e. de- creasing the index k(v) to F, requires finding the smallest m such that 1 + (F 1)m > Eis(p-1) () does not hold, i.e. F + 1 must be the first fail the condition kv(s) > Eigk P(1). Rewriting this condition in terms of we obtain:
1 + (F 1)m0(F+11) > EigIeto m)(()
implies >> m
Σ EE
P(()
(F + 1)U(F+1)
(13)
13 does not hold is The smallest such that condition Eq.
(EE o(0) - (F + 1) v(F+1) which given Eq 12 implics me has F nonzero elements. Analogously, to derive the multiplier for v to decrease sparsemax(1) sparsity, we need increase the index k(v) to F. This requires finding the largest m such that 1 + F(mur) > Eisr m)(
holds, which implies: m
EEE (()) F *V(FF)
A.4 PROOF OF THEOREM 3.3
Theorem 3.3. Let X and Y denote the random variables representing the features and labels, respectively, and y the value space for Y, then maximizing the quadratic relaxation of mutual information L (X, Y') is equivalent to minimizing the error E(X, Y). More specifically,
E(X,Y)=1->> Σ vEy
Proof. During training, the model seeks to produce the optimal predictions R(x, y) that minimize E(X, Y). while satisfying the constraint Eyey R(z,y) tipliers to solve for the optimal R(x, y). Taking the derivatives of E(X, Y) and the constraint g(X,Y)= EzEx R(x, v) - |X' with respect to R(z,)):
Hence we can apply Lagrange mul-
E'(X,Y) = -xexyEY--22
+ (2x
(14)
g'(X,Y) -
By Lagrange multiplier theory, for an optimum set of model predictions R* Y), there exists some À such that E' >g' (X, Y). Marginalizing E' E'(X, Y) over Y yields:
E'X,Y))= = = ZEX (x) 2Px (Px 0 4 Since Σ R(z,v) =
14

---

Under review as a conference paper at ICLR 2023
Therefore, by Eq 14 R(x, y) = (x, ()))))()(((() Plugging this into Eq relating the mutual information (x(X, Y) and the error E Y):
obtain expression
B(X,))= = Σ
+EX.NE () +
E Px(x)
Px, (2,1)
(x,((11))²
1 -
Σ TEX.NE (x,
+
Px (x(x)
Px(x)
(x,
-- E WENWEY (x(x)
= =1 - DEy Py( (X,)) 4 By Eq
Since Py(y) is fixed for given dataset, maximizing Ig(X, () is equivalent to minimizing E(X, Y).
A.5 SPARSEMAX VS SOFTMAX WITH THRESIIOLDING
Besides using sparsemax, an alternative method for learning the sparse mask Map to apply softmax normalization, followed by top-k operation, and additional normalization render it probability mask. This method is not only unwieldy with additional steps, but also from an optimization point of view, the top-k operation can only pass gradients through the top k values of softmax v), whereas sparsemax can pass gradients through all of sparsemax( v). Furthermore, because the softmax-topp normalization normalizes with respect to the absolute value of v, whereas sparsemax normalizes with respect to its relative values (by subtracting a v-dependent threshold), sparsemax (1) is more equi-distributed over the interval [0, 1] than softmax-top-k normalization (i.e. sparsemax(t) has lower entropy than softmax-top-4 normalization), making it more discriminatory for feature selection.
A.6
R1: R3: FEATURE INTERPRETARILIT RESULTS
While SLM optimizes feature selection for the task metric, the fact that the selected features are global readily opens the door for feature importance interpretability applications, as the chosen features can give insights about the task. To this end, we focus on the Ames housing dataset (Cock 201 as its features easily understandable. As mentioned in AA.1 the features in the Ames dataset consist of characteristics of houses, and the prediction target is the house price. We use the model parameters found in the best validation trial reported in Table [ and select the top ten out of the 81 features. To obtain importance scores of the selected features, we study the selection probabilities learned in the feature mask. Using this, the ten highest-probability features in terms of determining a house's 's prices are, with learned feature probabilities: 'OverallQual' (0.211), 'FullBath' 10.182), 'GarageCars' (0. 124). 'BsmtFullBath' (0.0795). 'MSSubClass' (0.0758), 'GarageFinish" (0.0739), 'HalfBath' (0.0718), 'PoolArea'' (0.0562), 'Fireplaces' (0.0473), 'HouseStyle' (0.0403).
Some aspects of this selection conform common sense: the overall quality of the property, the number of bathrooms, and the size of the garage pool are good predictors of housing value. Other aspects are more surprising, for instance the feature 'BedroomAbyGr" the number of bedrooms above ground is not selected, even though would expect the number of bedrooms to be an important selling factor. However, on further thought, as the number of bedrooms is positively correlated with the number of bathrooms (Eggers & Moumen, 2013), SLM is avoiding feature redundancy by only selecting one of the correlated features. The same reasoning applies for the features 'verralQuaal, the overall quality, which is selected, and 'OverallCond', the overall condition, which is not selected.
A.7 R1: R3: COMPUTATIONAL COMPLEXITY EXPERIMENTS
As stated in 3.5, let Fo be the total number of features, and n the number of samples, SLM has O(nFo log Fo) dependence on Fo. To test that this low complexity in theory translates to actual fast feature selection practice, we present the wall clock timing of SLM. We compare specifically against LassoNet, strong baseline that also selects features end-to-end. Table shows the timing results for one epoch on the mice dataset, demonstrating that SLM's 's low complexity in theory also translates to fast execution in practice.
15

---

Under review as a conference paper at ICLR 2023
Feature Selection Method
Timing (s) 1.21 0.016
SLM
LassoNet
19.62 1 0.796
Table 5: Timing results for one epoch on the mice dataset between SLM and LassoNet. This comparison is down under the exact same settings for both methods: hidden dimension 64, batch size 256, 1 MLP predictor layer, selecting 50 features, run on single V V100 GPU. The result statistics collected over five different runs. Only the training component is measured, not including data splitting and processing.
A.8
R2: R3: SYNTHETIC DATA EXPERIMENTS
We demonstrate the performance of SLM on synthetic dataset that specifically constructed such that only small subset of features affect the output value while the vast majority are not useful for the task. All input features X1J are sampled from the uniform distribution U| U[-1, 1] and the noise at the end EL, are sampled from standard Gaussian random variable with zero mean and unit variance. The input-output relationship are governed by the equations shown below:
Tij
Σ
exp (X1))
(15)
L
1
21.
T exp( T
Σ
ssin (2
(16)
i=L+1
T
(3) 1
Σ
log(L.1 1.11++++11 + X1j)),
(17)
1=21+1
4T.
T
Σ
Xij,
(18)
i=3L+1
5L
T 1/(1+ L
Σ
(tanh(X,))),,
(19)
x= 44+11
1, YIJ
if (T otherwise
+ T + T + + + +T 3 -.2eg))) > 0,
(20)
0,
As can seen, the function highly nonlinear in dependence to the input features, and in total 5L features are salient.
Hyperparameter
Search space
Batch size
[128, 256, 512]
Learning rate
[0.001, 0.003, 0.01]
Decay steps
[1000, 10000]
Decay rate
[0.7, 0.9, 0.95, 0.99]
Number of epochs
[30, 100, 200]
Number hidden units
[30, 50, 100]
Number of layers
[1, 2, 3.]
Table 6: Hyperparameter tuning search space for experiments the Synthetic dataset.
We construct the dataset with 3000 features among which only 100 or 300 are salient, i.c = 20 or L 60 for two different training dataset size values, 35000 and 14000 training samples
16

---

Under review as a conference paper at ICLR 2023
respectively. Train- validation-test split with 0.7-0.1-0.2 ratio, similar to all other experiments and hyperparameter tuning is done with the search space presented 6 We compare SLM with other feature selection methods, when they are used to select the 300 features. Table 7 and highlight the superior performance of SLM compared to the alternative methods for challenging datasets with a very large number of features.
Feature selection method
Test accuracy (%)
SLM
71.5
Anova
67.9
RF
62.6
Linear
67.0
MI
63.0
Table 7: Test accuracy (%) on the Synthetic dataset with 300 salient features (L = 60) and 14000
training samples.
Feature selection method
Test accuracy (%)
SLM
73.9
Anova
69.0
RF
69.9
Linear
69.7
MI
61.2
Table 8: Test accuracy (%) on the Synthetic dataset with 100 salient features (L = 20) and 35000
training samples.
A.9 R3: FURTHER COMPARISON WITH END-TO-END BASELINES
One of SLM's strengths is end-to-end feature selection along with task learning, which allows the model to incorporate inductive biases from the task directly into feature selection. Therefore, we specifically focus on comparing SL.M with additional end-to-end feature selection methods, beyond the results in Table ! As discussed in $2 Concrete Autoencoder (Abid et al. 2019) proposes unsupervised feature selector based on using a concrete selector layer as the encoder and using a deep neural network as the decoder. FsNet (Singh et al. 2020) for discrete feature selection in a selector layer and a supervised deep neural network regularized with the reconstruction loss, with focus biological data, which often nigh-dimensional with limited sample size. STG (Yamada et al. 2020) develops a fully embedded supervised method that learns stochastic gates with probabilistic relaxation of the count of the number of selected features. While all these works selects features and learns task prediction end-to-end, given that SLM is supervised model, with general focus beyond the high-dimensionality and low-sample-size setting, STG (Yamada et al., 2020) is the strongest, most related baseline to compare SLM with. Table shows the comparison between SLM and STG on the Isolet and Activity datasets with selected features. There are certain similarities between how SLM and STG control which feature to select: SLM learns a sparse probability mask m for the features, whereas STG learns learn the parameters of the approximate Bernoulli distributions via gradient descent for each feature. While STG learns the parameters for each Bernoulli variable independently. one advantage SLM has is accounting for interdependence amongst selected features, through both the fact that the probabilities in m interdependent, and through the MI regularizer (further details discussed in
concrete random variable
17

---

Under review as a conference paper at ICLR 2023
Feature Selection Method
Isolet
Activity f
SLM
92.49
0.20
93.35 + 0.82
STG
84.50 + 1.98
91.81 0.71
Table 9; Test accuracy (%) comparison between SLM with closely related, end-to-end feature selection baseline STG, which controls feature selection via learned stochastic gates, on the Isolet and Activity datasets with 50 features selected. The two methods are compared under the exact same conditions to the largest extent possible: using the same hidden dimension, number of epochs, batch size, learning rate, etc., all randomly generated from within feasible range. The non-shared hyperparameters are also generated from random within a feasible range. The results are averaged over ten different runs. SLM is able account for interdependence amongst selected features, through the learned mask m and the MI regularizer.
18


Reviews:
[{"review_id": "gtI3oKFwEbr", "reviewer": "Reviewer_BDBF", "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": "In this paper, the authors propose a method to dynamically select a subset of features in a neural network. In contrast to standard approaches, this set of features is _global_, and therefore the same subset of features will be ignored for all samples in the dataset.\nThe proposed method consists of three ingredients:\n1. Scaling sparsemax to the desired sparsity level.\n2. Linearly increase the desired level of sparsity during training.\n3. Optimize the task loss with a regularization term that captures the mutual information between the selected features and the label.\n\nResults on 8 datasets showcase the method's effectiveness, and ablation studies are performed to understand the impact of the sparsity level and the regularization term.", "summary_of_the_review": "Overall this paper provides a new method to induce a sparse global model. Although the sparsity can be exploited to interpret the model globally, the paper does not provide examples or evaluations toward this goal. However, the predictive performance is impressive across a wide range of datasets, and the ablation studies help illuminate the proposed approach's main contributions. ", "strength_and_weaknesses": "Things that I liked in this paper:\n- The motivation is clear.\n- The idea of scaling inputs by sparsemax globally is exciting.\n- Lemma 3.2 is incredibly useful.\n- The results are impressive, and the ablation studies are very informative.\n\n\nHowever, there are many things to be improved:\n\n- The math notation makes the paper hard to follow. \n- Although I liked the connection to the classical literature on feature selection, the related work on masking covers a small number of recent works. See some important missing references below.\n- It is hard to assess if the subset of selected features is meaningful since the ground truth feature importance is unknown for the experimented datasets.\n- Linked to the above point, there are no concrete examples of the interpretability of the selected features. Are the selected features plausible? \n- Although the authors claim the regularizer can be computed efficiently, the paper can be improved by reporting the running costs.\n\nOn sparse masks with a controlled sparsity level:\n- Lei, Tao, Regina Barzilay, and Tommi Jaakkola. \"Rationalizing neural predictions.\" arXiv preprint arXiv:1606.04155 (2016). \n- Bastings, Jasmijn, Wilker Aziz, and Ivan Titov. \"Interpretable neural predictions with differentiable binary variables.\" arXiv preprint arXiv:1905.08160 (2019).\n- Guerreiro, Nuno Miguel, and André FT Martins. \"Spectra: Sparse structured text rationalization.\" arXiv preprint arXiv:2109.04552 (2021).\n- Paranjape, Bhargavi, Mandar Joshi, John Thickstun, Hannaneh Hajishirzi, and Luke Zettlemoyer. \"An information bottleneck approach for controlling conciseness in rationale extraction.\" arXiv preprint arXiv:2005.00652 (2020)\n- Correia, Gonçalo, Vlad Niculae, Wilker Aziz, and André Martins. \"Efficient marginalization of discrete and structured latent variables via sparsity.\" Advances in Neural Information Processing Systems 33 (2020): 11789-11802.", "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": "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": "K3rydae0dZ2", "reviewer": "Reviewer_1pMd", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 method with the automatic mask scaling which can gradually temper this sparsity. The proposed SLM maximize a quadratic relaxation (with the help of Taylor approximation) of the mutual information between the selected features and the labels.", "summary_of_the_review": "The main concerns come from the limited novelty. However, I would like to update score after discussion, if my concerns can be addressed.  ", "strength_and_weaknesses": "### Strength\n- The quadratic relaxation of MI is interesting to some extent. \n- The experiments seems effective (even though the experiments may be insufficient). \n\n### Weakness\n- The novelty seems a little limited. Maybe I misunderstood something important due to the poor description of the motivation. Sections 3.2-3.4 are not attractive enough. The quadratic relaxation of MI may be interesting to some extent. Did the authors consider different estimators of MI, which have been extensively studied in representation learning? What is the primary advantage of the quadratic relaxation?\n- The writing of this paper could be further improved. For example, the formal definitions of mathematical notations could be summarized in an individual paragraph or section. The writing and poor motivation extremely limits the readability of this paper. \n- The experiments are not sufficient. Although the space is limited, the extra experiments with different selected features could be reported in appendix. ", "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": "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": "5rFKQHOvuI", "reviewer": "Reviewer_DZWY", "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": "The authors address a challenging and important problem of feature selection. The new approach is an embedded-type method that relies on sparse max to impose sparsity on the input features of a model. They use 8 real datasets and compare to several baselines to demonstrate the effectiveness of the method. ", "summary_of_the_review": "Overall the authors present a new method for an important problem. They use sparse max with tempering and demonstrate the approach on 8 datasets. However, the experimental results are quite limited as they don’t provide statistics and don’t compare to highly related works (mentioned above). The MI component is interesting, but it’s hard to judge its value since figure 2 is not well explained. I would expect a comparison between the proposed method and a baseline that incorporates the sparsemax mask into a cross-entropy loss guiding the selection of features. Based on these reasons, I can’t recommend accepting the paper.\n", "strength_and_weaknesses": "The problem is well-studied but still important for the community. The English level is satisfactory, and overall I enjoyed reading the paper. The problem statement and solutions are clear. The evaluation seems clear, and they further provide an ablation study to demonstrate that the proposed components are beneficial. Related work is mostly well-written. Another strength is the ability of the method to select exactly k features. \n\nThe major weakness of the paper is its framing; the authors name their method Scalable FS… but I don’t see any analysis of how scalable the method is.\nIn fact, the authors only apply it to dimensions that are not so large (D<1000). It is worthwhile to add the dimensions and sizes of all datasets. Furthermore, some strong, highly related baselines are missing, for example: \n\n[1] Lemhadri et al. Lassonet: Neural networks with feature sparsity\n\n[2] Yamada et al. Feature Selection using stochastic gates, 2020\n\n[3] Balin et al .Concrete autoencoders: Differentiable feature selection and reconstruction\n\n[4] Singh et al. Fsnet: Feature selection network on high-dimensional biological data\n\nIn the following, I provide detailed comments to help the authors improve the paper:\nIntroduction: “vast majority of the feature selection methods cannot take advantage of end-to-end learning.” This sentence is wrong and misleading, there are countless embedded methods that DO take advantage of this type of training, including 1-3, and many, many more.\n\nMissing works in related work 1-3.\n\nOn page 2, the authors say that local feature selection models can improve accuracy, in the next sentence, they say they it doesn’t alleviate overfitting. This is somewhat of a contradiction.\n\nIn the algorithm please mention where \\ell and E losses are explained in the paper.\n\nSection 3.1 is called Sparse attention, but it has nothing to do with attention.\nAlso this section is not very clear.\n\nCommas missing in Eq.7. and after theorem 3.3\n\nWhy do you choose specifically 50 features for all datasets? This is very restrictive, and limits the analysis.\n\nFigure 2 -subfigure 3 is confusing. The variability between different models seems HUGE, this means that the model strongly depends on initialization? You need to elaborate on this and demonstrate.\n\nAre the results in table 1 the average over multiple runs? Or just the best run out of 300 runs based on the validation accuracy?\n\nStatistics are required to understand the performance of all methods.\n\nWhat are the train/ test validation sizes?\n\nAt least one simulation evaluating the FS capabilities of the method is required. For example, using synthetic data or datasets from the Nuerips 2003 FS challenge. Thus providing information to the reader about the model's ability to recover the informative features.\n\n Page 9 “Feature importance intepretability” the model is global; how do you interpret the FS locally for each sample? Also, nor example is given.\n\nHow do I interpret figure 2? Are all comparisons using FS at the same level?\nIf so, how are features selected without the MI without tempering? I can’t judge these results without this explanation. \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": {}}]

Author rebuttal:

Decision: Reject