Deep unsupervised feature selection
Authors: Ian Covert
Uygar Sumbul
Su-In Lee
Venue:  (2020)
Keywords: Single cell rna
microarray
feature selection
feature ranking

Abstract: Unsupervised feature selection involves finding a small number of highly informative features, in the absence of a specific supervised learning task. Selecting a small number of features is an important problem in many scientific domains with high-dimensional observations. Here, we propose the restricted autoencoder (RAE) framework for selecting features that can accurately reconstruct the rest of the features. We justify our approach through a novel proof that the reconstruction ability of a set of features bounds its performance in downstream supervised learning tasks. Based on this theory, we present a learning algorithm for RAEs that iteratively eliminates features using learned per-feature corruption rates. We apply the RAE framework to two high-dimensional biological datasets—single cell RNA sequencing and microarray gene expression data, which pose important problems in cell biology and precision medicine—and demonstrate that RAEs outperform nine baseline methods, often by a large margin.

Under review as a conference paper at ICLR 2020
DEEP UNSUPERVISED FEATURE SELECTION
Anonymous authors Paper under double-blind review
ABSTRACT
Unsupervised feature selection involves finding a small number of highly infor- mative features, in the absence of a specific supervised learning task. Selecting small number of features an important problem many scientific domains with high-dimensional observations. Here, we propose the restricted autoencoder (RAE) framework for selecting features that can accurately reconstruct the rest of the features. We justify our approach through novel proof that the reconstruc- tion ability of set of features bounds its performance downstream supervised learning tasks. Based on this theory, present learning algorithm for RAEs that iteratively eliminates features using learned per-feature corruption rates. We apply the RAE framework cell RNA sequencing and microarray gene expression data, which pose important problems in cell biology and precision medicine-ant and demonstrate that RAEs outperform nine baseline methods, often by large margin.
high-dimensional biological datasets-single
INTRODUCTION
Many domains involve high-dimensional observations X Rd, and it is often desired to select small number of representative features a priori and observe only this subset. For natural spatio- temporal signals, compressive sensing provides a popular solution to this problem (Candès et al.) 2006 Donoho et al.) 2006). While prior knowledge of the structure of data is not available in the more general setting, a similar approach can be fruitful: unsupervised feature selection should select features that are informative in general sense, and not just for a specific supervised learning task.
As a motivating example, we may restricted to measuring the expression levels of only a small number of genes, and then these measurements in variety of future prediction tasks, such as disease subtype prediction, cell type classification, and so on. More generally, big data problems impacting virtually all research, and the ability observe an informative subset of the original features offers important advantages. It yields knowledge about the structure of the data, reduces storage requirements, makes downstream computation more efficient, and alleviates the curse of dimensionality. By contrast with feature extraction methods, such as PCA (Jolliffe) (001)) feature selection also reduces the burden of measuring all features.
The prior work on unsupervised feature selection is diverse, with methods designed to provide good Dy Brodley, 2004) to preserve the local structure data Cai et al.) 2010), and to eliminate redundancy (Farahat et al.) | et al. 2002). The abundance of existing approaches reflects a lack consensus on the correct optimization objective for unsupervised feature selection. We argue that for settings where the selected features will be used downstream prediction tasks, the optimal approach is to select set of features that can accurately reconstruct all the remaining features.
clustering results (Cai et al., 2010
(He et al. 2006 Zhao & Liu 2007
The contributions of this paper are the following:
1. We propose the "restricted autoencoder" (RAE) framework for selecting features based on their reconstruction ability. The approach justified by novel theoretical results, which show that the reconstruction ability of a set of features bounds its performance in down- stream supervised learning tasks.
2. We propose approximate optimization algorithm for the RAE objective function, based on learning per-feature corruption rates. The algorithm trains a RAE by iteratively elimi- nating features that important for performing accurate reconstruction.

---

Under review as a conference paper at ICLR 2020
3. We apply our approach two biological datasets, where finding small number of infor- mative features is an important scientific problem. Experiments demonstrate that RAEs outperform nine bascline methods: they select features that achieve lower reconstruction error and perform better in downstream prediction tasks.
2 RELATED WORK
Early work unsupervised feature selection was motivated by the observation that PCA (Pearson 1901 Hotelling 1933) yields principal components (PCs) that depend on all input features. In two early studies, Jollifte (1972) developed heuristics to discard features while roughly preserving the results of PCA, and Krzanowski (1987) proposed assessing the quality of a feature subset through a rotation of its PCs. McCabe (1984) derived several criteria for defining optimal subset of features, taking inspiration from the numerous criteria that are optimized by PCA.
Among the criteria proposed by McCabe 1984), when the rejected features are reconstructed by the selected features using a linear function. The reconstruction loss was revisited in several more recent works, with each addressing the challenge of combinatorial optimization. Farahat et al. derive an efficient algorithm for greedy feature selection an leverage scores (Boutsidis et al. 2009a 2014 Papailiopoulos et al. 2014).
represents the mean squared error (MSE)
(Farahat et al., 2011), Masaeli al.] (2010) and et al. (2015) select features by sparsifying
linear model. Several methods optimize similar objective using per- per-feature
The prior work that considers reconstruction ability has focused primarily reconstruction with linear function, although one study proposed using multivariate regression trees (Questier et al.) 2005), and there have been nascent efforts to perform feature selection with autoencoders (Chandra & Sharma 2013] Han et al. 2018). The differences between our work and these studies are i) we rigorously justify the reconstruction loss through its implications for downstream prediction tasks, ii) we explain the importance of considering reconstruction with a nonlinear function, and iii) we propose an algorithm that optimizes the objective function more effectively.
Other approaches for unsupervised feature selection find clusters of similar features MMitra et al., 2002 Lu et al. 2007), select non-reeunddat features with a greedy algorithm based on PCA (Cui & Dy 2008), use spectral information to preserve the local structure of data (He et al.
2006 Zhao &
Liu 2007 Zhao et al., 2010), retain local discriminative information (Yang et al. [00 and attempt
to preserve clustering structure (Dy & Brodley 2004 Boutsidis et al. 2009a Cai el al. 2010). These
approaches are designed with other aims, not select features for use supervised learning tasks.
In Section 5
we implement many of these methods and compare them with our approach using multiple datasets and downstream experiments.
3 FEATURE SELECTION BASED ON IMPUTATION ABILITY
3.1 IMPUTATION LOss
For random variable X Rdd feature selection algorithms determine a set S C f1,2...... .d} of selected indices, and set R = .,,,,...uuu d] \ of rejected indices. We use the notation X E RIS) and X [ to denote selected and rejected features, respectively. For notational convenience we assume that all random variables have zero mean.
The goal of unsupervised feature selection is select features X that are most representative of the full observation vector X. An approach that has received some interest in prior work is to measure how well X can reconstruct X McCCbee 1984. Questier al., 2005 Farahat et al., al., 2014 Zhu et al. 20155] Han et al. 2018). It is
2011 Masacli et al.) 2010 Papailiopoulos intuitive to consider reconstruction ability, because if the rejected features can be reconstructed perfectly, then no information is lost when selecting subset of features. To make the motivation for this approach precise, we derive a rigorous justification that has not been presented in prior work.
To quantify reconstruction ability, define the imputation loss L(S) and the linear imputation loss Linear (S). Both quantify how much information X contains about R. and is clear from their definitions that L(S) < Liinear
2

---

Under review as a conference paper at ICLR 2020
Definition (Imputation loss). The imputation loss ((S) and the linear imputation loss Llinear quantify how well X can reconstruct X using an unrestricted function, and using a linear func- tion, respectively. They are defined as:
((S) = min E| |[ - 1(xx)112
h
Liiuear (S) min E X WX
(2)
Either one could serve as a feature selection criterion, so we aim to address the following questions:
Why is it desirable to optimize for the reconstruction ability selected features X5?
2. Is it preferable to measure reconstruction ability using L(S) or Liinerr (S)?
3.2 IMPLICATIONS OF IMPUTATION Loss FOR DOWNSTREAM TASKS
In this section, we demonstrate through theoretical results that reconstruction ability is connected to performance in downstream supervised learning tasks. These results aim to characterize the usefulness of X for predicting a target variable Y E R. All proofs are in Appendix
To facilitate this analysis, we assume that all learned models are optimal; this assumption ignores practical problems such as overfitting and non-convex optimization, but makes possible to shed light on the connection between reconstruction ability and predictive power. Our analysis focuses on the degradation in performance (henceforth called performance loss) when a model is fitted to X instead of X. Intuitively, performance in the downstream task must suffer when information is discarded. The question is, by how much?
Consider fixed partitioning of features into (X.S. ..).. The first result addresses the situation when a linear model is used to predict Y given X Theorem I states that the performance loss has exact expression, which can be related (S). For this result define the notation Σ, Cov(X E, = Cov(X (R)), Eer = Cov(XS (x)), and = Eg Eggr
Theorem (Performance loss with linear model). Assume a prediction target Y such that
(bn, c.) arg min
brx - -
(3)
b,c
Then, the performance loss for features x is:
min E[(Y n² x min B[(Y oJ x)3] Emp
The performance loss is a quadratic form based on the matrix Erjs, structure of the matrix. To ensure strong performance in downstream tasks, it is therefore desirable select X so that E, has small eigenvalues. The result is notable because can be shown that the linear imputation loss is equal the sum of the eigenvalues, i.c., Ciinear (S) = Tr(2,;)) Select- ing X to minimize Liinea((S) therefore minimizes the performance loss with linear models. This perspective has not been presented in prior work, but lends support to several existing approaches Masaeli et al. 2010; Farahat et al. 2011 Papailiopoulos et al., 2014 Zhu et al. 20155).
dependent on the eigen-
The second result addresses the situation where nonlinear model is used to predict Y. Nonlinear models (c.g., neural networks, gradient boosting machines) are predominant many machine learn- ing applications, so this result more relevant to contemporary practices. Theorem 2 states that the performance loss can be upper bounded using L(S).
The result requires mild assumption about the Hölder continuity (a generalization of Lipschitz contintuity) of the conditional expectation function E|Y | X = æ] that is not verifiable in practice. Nonetheless, it connects the performance of X in prediction tasks with its ability impute X
3

---

Under review as a conference paper at ICLR 2020
A) Linear vs. Nonlinear Models
C)
Nonlinear model comparison
C) Linear model com parison
Shoonee MSE (Nonlinear)
Yaxis
Y
3:5
Saatmer MSE
X Seueeioo MSE
2.00
1.75
125
100 125
150
175
2.00 225 250
1.00 125
1550
175
2000
225
2.50
3.00 125
150
2:50 175
2000
225
Xhooto MSE (Linear)
XSrra MSE
XStraar MSE
Figure I: Feature comparison on simulated prediction tasks. Each point represents single task, and the legend shows the portion of tasks in which the method on y-axis outperforms the method on x-axis.
Theorem 2 (Performance loss with nonlinear model). Assume a prediction target Y such that the conditional expectation E[Y X = x] is (C, a) a--Hööler continuous with exponent 0 < a S 1, so that the following holds almost everywhere in the distribution of X:
B X
E X
6112-
(5)
Then, the performance loss for features X
can be upper bounded:
min B - min EE (2())) S C² C...(S))
(6)
f1
f2
The bound Theorem 2 suggests that X should be selected to minimize L(S), because doing so reduces the upper bound the performance loss. We appeal to the minimax principle argue that the minimization of C(S), by effectively minimizing the worst-case performance loss, provides the most conservative way to select small number of features (Von Neumann & Morgenstern) 1944).
While this result is easiest to prove for Hölder continuous tasks with the MSE loss function, the idea that good reconstruction ability leads strong predictive power should apply more broadly. Our experiments in Section confirm this empirically.
To make these results concrete, present a simulation experiment involving two feature sets from the single-cell RNA sequencing data described in Section The feature sets X X'sinnus and X Smas were chosen so that ((XSmalinn I C(XSSue)) ), but Llinear (X Smalicca Z Liiuear (X Suse), ). We simu- lated 250 response variables with linear dependencies on subsets of the original features (see Sec- tion 5.4), and trained linear and nonlinear (neural network) predictive models for each task.
Figure shows the relative performance of the two feature sets. The important observations from this experiment are that across a wide variety of tasks, nonlinear models perform better overall (Fig- ure IA), X Smitnne usually performs better when using nonlinear models (Figure [B), and X Smor usually performs better when using linear models (Figure These results provide empirical con- firmation of both Theorem and Theorem [ and summarize approach feature selection.
To our knowledge, these results are novel in the space of unsupervised feature selection. despite the long history of the linear imputation loss (McCabe) 1984) and recent interest in the nonlinear imputation loss (Questier et al. 20055] Han al. 2018).. While it tangential to unsupervised feature selection, also show in Appendix that the results can be stated more generally for unsupervised feature extraction.
Given these findings, and the predominance of nonlinear models in contemporary machine learning. we proceed with an approach to select X by minimizing the imputation loss as follows:
S =" { min E X f(x
=
4

---

Under review as a conference paper at ICLR 2020
Rejected features
Prediction targets
Predictive model
Predictive model
Predictive model
RAE
Selected features
Selected features
Figure 2: Features are selected by learning restricted autoencoder (RAE), and can be applied in downstream prediction tasks.
RESTRICTED AUTOENCODERS FOR FEATURE SELECTION
4.1 RESTRICTED AUTOENCODERS
We aim to select & features by solving the problem Eq. However, two obstacles make the problem difficult. First, L(S) is unknown in practice because do not have access the optimal imputation functions. Second, the combinatorial number of sets of size k make an exhaustive search infeasible. We therefore propose the framework of restricted autoencoders (RAEs) jointly op- timize for S and f, and train a model to reconstruct the full observation vector while relying on subset of the inputs. The approach depicted in Figure 2 but it requires a non-trivial learning algorithm.
The concept RAE is straightforward,
Sparsity inducing penalties (Feng & Simon 2017 Tank al., 2018 provide one option, but we
found that these did not perform well on large datasets. Indeed, experiments in Section [5 show show that method of Han et al. (2018) fails to effectively optimize for reconstruction ability. Instead, we introduce a learning algorithm based on backwards elimination.
There are multiple ways to measure the sensitivity of a network to each input, and these can easily be adapted into feature ranking methods; highly ranked features those that most critical for performing accurate reconstruction. Instead simply selecting the top ranked features, it may prove beneficial to reject a small number of features, and reassess the importance of the remaining ones. Following this logic, we present Algorithm T for learning a RAE by iteratively training a model, ranking features, and eliminating the lowest ranked features, in procedure that is analogous to recursive feature elimination (Guyon et al. (2002).
To improve the running time of Algorithm he can be warm started using the model from multi-layer percep-
Algorithm 1: Learning RAE
inputs dalasel (X.) schedule
the previous iteration. tron (MLP) is natural choice because of the multitask prediction target; the model from the previous iteration can be modified by deleting columns from the first layer's weight matrix corresponding to eliminated features. In prac- tice, we observe that this significantly reduces the number of training steps each iteration.
+- -1,1,, (1,2,...,p) for k in schedule do
train he |R| + ng to predict X given X rank features in S
< {k highest ranked features in S}
end return S
4.2 FEATURE RANKING METHODS
The purpose of the ranking step is to determine features that can be removed from S without impact- ing the model's accuracy. We consider two sensitivity measures, both of which are based on learning per-feature corruption rates. The first method stochastically sets inputs to zero using learned dropout rates Py for each feature j E S (Chang et al. 2017). Similarly, the second method injects Gaussian noise using learned per-feature standard deviations oy- We refer these methods as Bernoulli RAE and Gaussian RAE, due to the kind noise they inject. Based on the logic that important features tolerate less corruption, rank features according p, G-j-
5

---

Under review as a conference paper at ICLR 2020
Single Cell RNA
Gene Microarray
0.80
0.95
Imuptation loss (MSE)
0.78
0.90
Bern. RAE
6.76
Laplacian
0.74
0.85
MCFS
0.72
UDFS
Jollifle
0.10
Greedy
Levorage
0.75
AEFS
0.70
Number of teatures
Number of teatures
Figure 3: Imputation loss results. The MSE is normalized by the total variance of each dataset.
During training, both methods require penalty terms to encourage non-zero corruption rates. A hyperparameter À controls the tradcoff between accurate reconstruction and the amount of noise injected. The objective functions to be optimized at each iteration of Algorithm | are shown in Eqs. and both are optimized using stochastic gradient methods and the reparameterization trick (Rezende et al. 2014 Maddison et al. 2016).
min Emp Ex ho mm)) - - Σ
logpj
(8)
P.
jES
min E Exl(X ho(x* + +1)) + Σ 0,
log(1 + o
(9)
jES
EXPERIMENTS
5.1 DATASETS AND BASELINE METHODS
We apply the RAE feature selection approach to two publicly available biological datasets: single- cell RNA sequencing data, and microarray gene expression data. The single-cell RNA sequencing dataset is from the Allen Brain Atlas, and contains expression counts for n 24,411 cells and 5,081 genes (Tasic et al. 2018). The microarray data were collected from patients with breast cancer. Our dataset combines unlabeled samples from multiple Gene Expression Omnibus datasets (n = 11,963), as well as labeled samples from The Cancer Genome Atlas (TCGA) (n = 590), and we consider all genes that present in both datasets (d 7,592). We followed standard pre- processing techniques: we used log lp of the expression counts for the single-cell RNA sequencing data, and applied batch correction to the combined gene microarray datasets.
For both of these data domains, determining a small subset of informative features is an important problem. In precision medicine, key goal is to identify small set of expression markers for subtype classifications. As another example, fluorescent in-situ hybridization (FISH) methods (Raj 2008 Chen al. (2015) that measure the expression levels of pre-selected genes intact tissue have become popular in brain sciences. However, such probes are typically limited to handful of genes per hybridization round, and problem practical significance is design the most informative FISH probes using as few genes possible. The resulting spatial transcriptomic data can then be used to study multiple scientific problems (i.e., downstream tasks) relating cell function, communication, and tissue organization.
We compare RAES with nine baseline methods. Jolliffe B4 (Jolliffe) 1972) and principal feature selection (PFS, Cui & Dy (2008)) are both based preserving the results of PCA. Greedy feature selection (GFS, Farahat et al. (201T)) and the leverage score method (Papailiopoulos et al. 2014) both optimize for reconstruction with linear function. Autoencoder feature selection (AEFS, Han jet al.] (2018) selects features by attempting to induce sparsity in a shallow MLP. Max variance simply selects features with the largest variance; it could not be applied to the microarray data,

---

Under review as a conference paper at ICLR 2020
Table 1: Classification accuracy using subsets of features
Cell type classification
Cancer subtype classification
# Features
5
10
20
30
50
5
10
20
30
50
Laplacian
0.219
0.251
0.443
0.505
0.680
0.676
0.640
0.748
0.748
0.748
MCFS
0.111
0.278
0.532
0.622
0.713
0.532
0.514
0.613
0.685
0.685
UDFS
0.291
0.510
0.656
0.702
0.767
0.505
0.532
0.631
0.640
0.649
PFS
0.268
0.335
0,465
0,565
0.649
0,622
0.685
0.703
0.721
0,712
AEFS
0.320
0.574
0.759
0.806
0.847
0.523
0.486
0.550
0.640
0.604
Variance
0.447
0.541
0.741
0.793
0.822
Leverage
0.463
0.634
0.780
0.816
0.852
0.523
0.568
0.613
0.658
0.649
Jolliffe
0.264
0.557
0.712
0.793
0.844
0.667
0.676
0.622
0.685
0.703
Greedy
0.203
0.367
0.580
0.691
0.820
0.657
0.673
0.684
0.750
0.753
B. RAE 0.484
0.674
0.789
0.822
0.845
0.679
0.687
0,701
0.721
0.753
G. RAE 0.487
0.667
0.771
0.822
0.846
0.645
0.678
0.686
0.694
0.740
because batch correction sets all features to have unit variance. Laplacian scores (He et al. 2006 and multi-cluster feature selection (MCFS, Cai et al. (2010) both aim to preserve local structure in the data through spectral information. Unsupervised discriminative feature selection (UDFS, Yang et al. 1) aims to retain local discriminative information.
5.2 IMPUTATION ABILITY
We first demonstrate that RAEs select features that achieve a low imputation loss. Both datasets were split into training, validation and test sets, and used only the unlabeled samples for the gene microarray data. For both datasets, we trained 20 RAEs by iteratively eliminating features using learnable Bernoulli and Gaussian noise. After features were selected, separate imputation model was trained to predict only the rejected features, and the best features from the 20 trials were selected using a validation set. Similarly, imputation models were trained using features selected by all the baseline methods. The imputation loss was then estimated on the test set.
Hyperparameter choices were made on validation data, and are detailed in Appendix E The RAEs are robust to both shallow and deep architectures, because the feature rankings are more important than the prediction accuracy. Iteratively eliminating features proved be critical for both datasets, and we eliminated 20% of the remaining features at each iteration of Algorithm
Figure displays the results, showing the imputation loss for different numbers of selected features. RAES achieve the best performance on both datasets. The gap is larger on the single-cell RNA sequencing data, where the RAEs perform significantly better than all baselines. RAEs and GFS achieve similar results the microarray data, outperforming all other methods by large margin.
GFS is a competitive baseline method, possibly because while it optimizes for linear reconstruction ability, it has the benefit of performing forward selection. Jolliffe and PFS somewhat com- petitive, likely due to implicit connections between PCA and the linear imputation loss. Mean- while, AEFS does not appear to effectively optimize for nonlinear reconstruction ability, and the non-reconstructton methods (Laplacian, MCFS, UDFS) naturally lead to poor reconstruction. In Appendix D we provide these results in table. In Appendices G we demonstrate the importance of eliminating features itcratively, and analyze the variability between trials of RAEs.
5.3 REAL DOWNSTREAM PREDICTION TASKS
Next, we assess the performance of selected features in downstream prediction tasks. Both datasets have associated classification problems that, in certain settings, would need to be performed using a subset features: cell type classification (150 types) for the single-cell RNA data, and cancer subtype classification (4 types) for the microarray data. For the single-cell data, used the same dataset split; for cancer classification we split the labeled TGCA samples. MLPs were trained for each task, and the reported accuracy is the average performance of 10 models the test data.
7

---

Under review as a conference paper at ICLR 2020
Linear Tasks
Quadratic Tasks
Interaction Tasks
Been RAF
048 8:44 0.73 OBL 0.86 038 082 033 036
0:00 0.75 0.75
0:00 0:9
8:8 0.76 0.2 984 0.5 084
Gauss RAF 0052
9.74 0.77 081 0.87 8:68 086 055 035
0:40
061 0.70 0.74 0.78 0.75 0.0 099 089 083
0.51
052 6666 0.2 075 0.2 976 043 081 041
Greedy
0.2 0.6
0.5 082 0.75 8.89 0.70 082 335 055
1.52 0.39
082 087 0.76 0.77 0.78 D37 052 034
0:47 0:48
8.64 0.70 0 0.77 882 906 0.79 082
joliifee
027 025 045
038 0.75 0.5 0.76 030 037 051
1224 0:50 0.08
082 0.6 Ded 0.72 USS 035 0.00
0:05 0:54 0.39
0.0 DS0 032 075 925 0.14 0.72
teverage 0.13 010013300 0:38 0.32
0.55 0.9 030 087 085 082
0225 0.6 0.35 0.35
035 0.3 D63 D83 0.75 045
0.22 0:08 0:30 640
D50 054 038 0:78 061 043
Vanance-
0144 027 0.7 0.4
0.54 040 0.78 032 084
0114 022 024 0.34 0455
054 058 075 0788 065
6.24 025 022 6:3 644
048 050 066 062 066
PFS 012 928 0.5 041 0.45
048 063 036
0.16 024 023 0.37 047 646
033 056 0.22 087
0.26 0.88 023 8:8 046 052
0:0 043 050 064
001 014 033 024 042 032 032
0.2 086 077
0.19 020 022 0.88 0.37
0.74 0:0 029
0.28 0:44
6:7 042 050 050
043 050 042
005 038 010 013 0.22 035
0.10
044
022 0:32 037
044 053
Lapiscion
o0t 0.5 008
642
057
NCB
Bern BAB
Gauss RAE
Grendy pilife
Leverage
Pr
uDnS
ARTS
Laplecian
MCP5
Bern RAB
Gauss RAE
Greedy
jaluree
Leverage
Variance
IPS
UDYS
AETS
Laplocian
MKFS
Bern RAE Gamss RAE
Greedy joliife
Leverage
Veriance
PS
AEPS
Laplacion
Figure 4: Results from the simulation study using scRNA data. Heatmaps provide pairwise compar- isons, showing the portion of tasks in which features from the method on the y-axis achieved better performance than features from the method on the x-axis.
Table | displays the results for both datasets. Features selected by RAES perform very well in both tasks, particularly when using a smaller number of features. Overall, RAEs achieve the best perfor- mance most of the time (7/10), and when they do not, they are still among the best. In Appendix D we present the same results a plot that reveals a strong correlation between imputation ability and classification accuracy. We posit that features selected by RAEs perform well not because they were lucky to select "marker genes" for these tasks, but because they were optimized for reconstruction ability, and are therefore guaranteed to perform well in variety of prediction problems.
5.4 LARGE-SCALE SIMULATION STUDY
The prediction problems in Section 5.3 provide one approach for verifying that RAEs select features with strong predictive power. However, would be more informative to assess performance across large number of prediction tasks. Since these two datasets do not offer a large number of prediction targets, our final experiment is a large-scale simulation study.
Using the single-cell RNA sequencing data, we simulate response variables with three kinds of dependencies on the original features. The response variables are simulated with either linear de- pendencies, quadratic dependencies, or involve interactions terms. There are 250 prediction targets of each type, and the simulation method is described in more detail in Appendix H We then trained MLPs to predict the response variables using the features selected by each algorithm.
The full results are in Appendix and a representative summary is displayed in Figure 4 with heatmaps showing how often features from one method achieve better performance than features from another method. These results show that the features selected by a Bernoulli RAE and Gaus- sian RAE, which achieve lower imputation loss than all baselines, also achieve better performance in a majority of prediction tasks. Conversely, the features that perform most poorly (MCFS, Lapla- cian scores) are those with the worst reconstruction ability. The simulation study provides further empirical evidence for the theory in Section 3.2, underscoring the idea that selecting features for reconstruction ability leads to strong performance across a wide variety of prediction problems.
DISCUSSION
In this work we proposed a feature selection approach based on reconstruction ability, which we showed both theoretically and empirically has implications for the performance of features in down- stream prediction tasks. We present the framework of restricted autoencoders (RAEs), and propose a learning algorithm based on iterative elimination, using learnable per-feature corruption rates to identify features that unimportant to the model. Given the firm theoretical foundation for this feature selection approach, future work could focus on developing better algorithms for training RAFs, e.g., through forward selection.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Christos Boutsidis, Petros Drineas, and Michael W Mahoney. Unsupervised feature selection for the k-means clustering problem. In Advances Neural Information Processing Systems, pp- 153-161, 2009a.
Christos Boutsidis, Michael W Mahoney, and Petros Drineas. An improved approximation algorithm for the column subset selection problem. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pp. 968-977 SIAM, 2009b.
Christos Boutsidis, Petros Drineas, and Malik Magdon-Ismail. Near-optimal column-based matrix reconstruction. SIAM Journal on Computing, 43(2):687-717, 2014.
Deng Cai, Chiyuan Zhang, and Xiaofei He. Unsupervised feature selection for multi-cluster data. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 233-342. ACM, 2010.
Emmanuel Candès, Justin Romberg, and Terence Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on information theory, 52(2):489-55 509,,50900000 2006.
B Chandra and Rajesh K Sharma. Exploring autoencoders for unsupervised feature selection. In 2015 International Joint Conference on Neural Networks (IJCNN), pp. 1-6. IEEE, 2015.
Chun-Hao Chang, Ladislav Rampasek, and Anna Goldenberg, Dropout feature ranking for deep learning models. arXiv preprint urXiv:1712.08644 2017.
Kok Hao Chen, Alistair N Boettiger, Jeffrey R Moffitt, Siyuan Wang, and Xiaowei Zhuang. Spatially resolved, highly multiplexed ra profiling in single cells. Science, 348(6233) 2015.
Ying Cui and Jennifer G Dy. Orthogonal principal feature selection. 2008
David L Donoho et al. Compressed sensing. IEEE Transactions on information theory, 52(4): 1289-1306, 2006.
Jennifer G Dy and Carla E Brodley. Feature selection for unsupervised learning. Journal of machine learning research, 5(Aug):845-88) 2004.
Ahmed K Farahat, Ali Ghodsi, and Mohamed S Kamel. An efficient greedy method for unsupervised feature selection. 20/1 IEFE 11th International Conference on Data Mining, pp. 161-170. IEEE, 2011.
Jean Feng and Noah Simon. Sparse-input neural networks for high-dimensional nonparametric regression and classification. arXiv preprint arXiv: 2017.
Isabelle Guyon, Jason Weston, Stephen Barnhill, and Vladimir Vapnik. Gene selection for cancer classification using support vector machines. Machine learning, 46(1-3):389 2002.
Kai Han, Yunhe Wang. Chao Zhang, Chao Li, and Chao Xu. Autoencoder inspired unsupervised feature selection. In 2018 IEEE International Conference on Acoustics, Speech and Signal Pro- IEEE, 2018.
cessing (ICASSP), pp.
Xiaofei He, Deng Cai, and Partha Niyogi. Laplacian score for feature selection. In Advances in neural information processing systems, pp. 507-514. 2006.
Geoffrey E Hinton and Ruslan R Salakhutdinov. Reducing the dimensionality of data with neural networks. science, 313(5786):504-507, 2006.
Harold Hotelling. Analysis of a complex of statistical variables into principal components. Journal of educational psychology, 24(6):417, 1933.
Ian Jolliffe. Discarding variables in a principal component analysis. i: Artificial data. Journal of the Royal Statistical Society: Series C (Applied Statistics), 2102):100-173, 1972.

---

Under review as a conference paper at ICLR 2020
Ian T Jolliffe. A note the of principal components in regression. Statistical Society: Series (Applied Statistics), 31(3):300-30 1982.
Journal of the Royal
Ian Jolliffe. Principal component analysis. Springer, 2011.
Wojtek J Krzanowski. Selection of variables to preserve multivariate data structure, using principal components. Journal of the Royal Stafistical Society: Series C. (Applied Statistics), 36(1)) 36(1):22-33 1987.
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. ACM, 2007.
Chris Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. arXiv preprint arXiv:1611.0077 2016.
Mahdokht Masaeli, Yan Yan, Ying Cui, Glenn Fung, and Jennifer G Dy. Convex principal feature selection. Proceedings of the 2010 SIAM International Conference on Data Mining, pp. 619-
628. SIAM, 2010.
George P McCabe. Principal variables. Technometrics, 26(2):137-144, 1984.
Pabitra Mitra, CA Murthy, and Sankar K. Pal. Unsupervised feature selection using feature similar- ity. IEEE transactions on pattern analysis and machine intelligence, 24(3)301-312, 2002.
Dimitris Papailiopoulos, Anastasios Kyrillidis, and Christos Boutsidis. Provable deterministic lever- age score sampling. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 997-1006. ACM, 2014.
Karl Pearson. Liii on lines and planes of closest fit to systems of points in space. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 2(11):559-573 1901.
F Questier, R Put, D Coomans, B Walczak, and Y Vander Heyden. The use of cart and multivariate regression trees for supervised and unsupervised feature selection. Chemometrics and Intelligent Laboratory Systems, 76( 76(1):45-54 2005.
Arjun Raj, Patrick Van Den Bogaard, Scott A Rifkin, Alexander Van Oudenaarden, and Sanjay Tyagi. Imaging individual mrna molecules using multiple singly labeled probes. Nature methods, 5(10):877, 2008
Danilo Jimenez. Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference deep generative models. arXiv preprint arXiv:1401.4000 2014.
Alex Tank, Ian Covert, Nicholas Foti, Ali Shojaie, and Emily Fox. Neural granger causality for 2018.
nonlinear time series. arXiv preprint /802
Bosiljka Tasic, Zizhen Yao, Lucas T Graybuck, Kimberly A Smith, Thue Nghi Nguyen, Darren Bertagnolli, Jeff Goldy, Emma Garren, Michael Economo, Sarada Viswanathan, et al. Shared and distinct transcriptomic cell types across neocortical areas. Nature, 563(7729):72,, 2018.
J Von Neumann and O Morgenstern. Theory of games and economic behavior. 1944.
Yi Yang, Heng Tao Shen, Zhigang Ma, Zi Huang, and Xiaofang Zhou. L2, 1-norm regularized dis- criminative feature selection for unsupervised. In Twenty-Second International Joint Conference on Artificial Intelligence, 2011.
Zheng Zhao and Huan Liu. Spectral feature selection for supervised and unsupervised learning. In Proceedings of the 24th international conference on Machine learning, pp. 1151-1157. ACM, 2007.
Zheng Zhao, Lei Wang, and Huan Liu. Efficient spectral feature selection with minimum redun- dancy. In Twenty-forrth AAAI conference on artificial intelligence, 2010.
Pengfei Zhu, Wangmeng Zuo, Lei Zhang, Qinghua Hu, and Simon CK Shiu. Unsupervised feature selection by regularized self-representation. Pattern Recognition, 48(2):438-446, 2015.
10

---

Under review as a conference paper at ICLR 2020
A THEOREMS FOR UNSUPERVISED FEATURE EXTRACTION
In Section 3.2, we presented theoretical results to motivate the use of reconstruction loss for un- supervised feature selection. Similar results can be stated for the more general problem of unsuper- vised feature extraction.
Consider an embedding function g Rd R for a random variable E Rd. The embedding function induces distribution for new random variable Z E TR. which can be used in place of X in downstream tasks. Here, we state two theorems for how well Z should perform when predicting target variable Y R.
The first result addresses the situation where the embedding function is linear, i.e., Z = WX, and linear model is used for the prediction task. For this result, we define the notation Σ Cov(X), Σzx = Cov(Zz X), Σg = Cov(Z). We restrict our attention to linear operations such that Z is non-degenerate, that Σz W WEWT is invertible. As in the main text, assume that all random variables have mean zero.
Theorem (Performance loss with linear model). Assume a prediction target Y such that
U. arg min E[(Y o x)?].
(10)
Then, the performance lossfor linear embedding variable Z = WX is:
min B[(Y - n² 2) min E(
x\ = v. Σ Ezx)e.
(11)
To see the connection with reconstruction ability, we point out that the reconstruction ability of Z the trace of precisely the same matrix, i.e., ming E| ||X - - | Tr - > Σzx). Therefore, learning Z to achieve low reconstruction error can be understood as minimizing the performance loss. This is precisely what done by PCA (Joliife 2011). so this result supports the classic idea of principal components regression (Jolliffe 1982).
The second result addresses the situation where nonlinear model used for the prediction task. Similarly Theorem tional expectation function.
2 the result requires assumption about the Hölder-continuity of the condi-
Theorem (Performance loss with nonlinear model), Assume a prediction target Y such that the conditional expectation function E[y X = 2]) is (C, oo--Hölder continuous with exponent 0 < S
1, so that the following holds almost everywhere in the distribution of X:
B | = a] EY X 6] S C b1B.
(12)
Then, the performance loss for an embedding variable = g(X) can be bounded:
min E[(Y - [[(Y--((X))) min B[(Y f2(x)) C². (min E[ 13 (13)
f2
This second result provides support for autoencoders (AEs, Hinton & Salakhutdinov (2066). which jointly learn an encoder and decoder h to optimize the reconstruction loss that shows up in the bound of Eq. 13 The connection with feature selection is that is very particular linear function.
B PROOFS OF THEOREMS FOR UNSUPERVISED FEATURE EXTRACTION
We begin by proving the results stated in Appendix A Appendix C we show that these lead to straightforward proofs for the results in the main text.

---

Under review as a conference paper at ICLR 2020
We introduce the notation Exy Cov(X,Y) Y) E R and calculate the MSE arising from the optimal linear model fit to X.
Proof of Theorem 3
V = mig B - x)
-x-EExx-
EI(Y - uf = EE(YY -xxy D 1X]
= =Var(Y) Ex Exxy
Similarly, we calculate the MSE from the model fit to Z.
u. arg min B((Y 2)2]
(WEWW")-WWS
B - - B[(Y - (0(Y--X-WW) W (W
Var(Y)
- E W (WEWT)
Taking the difference between the two terms, get the desired result:
min [[ 21 min E - x" x = - Exy ) "WEXY
v.-Ev. "''''' (WWW"WWWW
= Ee, - of "2''""''' Ezxu=
of' -
Proof of Theorem Consider the terms on the left side of the inequality. Both can be understood in terms of conditional variance.
min E 11 min ((YYYEEY(2)) + (Z -(Y)))))
f1
E[(Y - BBY 1
E\Var(YY
min E 2 (2())) min ((Y--EYIIJ]* - -E(xx))))()1
f2
f=
E((Y -|-|)))
E|[ar(Y||X)]
(14)
Now, consider the first term in more detail. The following be shown by using the Hölder tinuity of the conditional expectation function, and applying the law total variance and Jensen's inequality.
12

---

Under review as a conference paper at ICLR 2020
Var(Y|Z= = Ex]z=, X) + (B z1 2, x))
(E 2,) Varx z= (B(r Z = XX E[y]X E[X Z = =]]
- ExIz= [ 2, X] B[ = E =1))²]
(x - E[v|X | = =]])²]
< C² Ex| - E[X|Z = =]
C
= =]| lm
C (Cov(X|2 =))
min B(Y - - fi(z)) = E|Var(Y| = =
Ex.z/Var 22, + E (Cov(X(2))
Ex,z + Tr (B( Cov (2) l) E|Var(Y|X)] + Tr (El Cov(X ))
(15)
Then, combine Eqs. 14 15
obtain the following bound:
min B[
min E[(Y fix)) s C². Tr (B. ()) fz
(16)
Finally, consider the term that appears in the right side of Eq. 16 It can also be understood in terms of conditional covariance. Substituting this value into the above iequalltyy completes the proof.
min B ||X M(Z)1²]
h B ||X
E|x|
[E[ ||X - -|
[E[T ((X E[ -
= Tr (B/ Cov(X ))
C PROOFS OF THEOREMS FOR UNSUPERVISED FEATURE SELECTION
Now, we proceed with proofs of the results presented in Section 3.2 of the main text. They follow in straightforward manner from proofs in Appendix B
Proof of Theorem 7 Feature selection is an embedding with particular kind of linear function. can be seen that x = 7 W X for W E RR with single in each row, corresponding to the selected features, and zeros everywhere else. Without loss generality, we can assume that the features are ordered such that the full covariance matrix can be partitioned into blocks corresponding to the selected features S and rejected features R.
Σ
Σgr
Σ
Σ
Σ
Then, the following can be seen:
13

---

Under review as a conference paper at ICLR 2020
-- 3 1 = = (WE) (WEWT) (WWWWWWWWWW) (W2))
Σ
=
ST
Σ (2is Mirr)
Σ,
Egr
= Σ
ΣT Σー Eisr Egg
0
0
0
0
Erls
The expression for the performance loss then follows from Theorem
3
b.
T
b. c+
min [ u² x min E -
x)
Erle
C+
2irlsC
Proof of Theorem 2 The bound involving the imputation loss L(S) follows directly from Theo- rem 4 upon the observation that L(S) precisely the term in the upper bound.
min E X 1(Z)]1]] = min E X )(x0)112]
min | 1(x5)1121
L(S)
D IMPUTATION ABILITY AND DOWNSTREAM CLASSIFICATION RESULTS
In this section, we present results from Section 5.2 and Section 5.3 in alternate form. Table shows the imputation loss for the single-cell RNA sequencing data, and Table shows the results for the gene microarray data. As in the main text, the MSE is normalized to reflect the portion of total variance. It is clear that RAEs nearly always select features that achieve the best imputation loss.
Figure 5 shows the results from the downstream classification tasks in graphical form, for 10 fea- tures. The plot shows a very clear linear trend between imputatation ability and classification accu- racy, further underscoring the idea that features selected by RAES perform well precisely because they have good reconstruction ability.
E HYPERPARAMETER TUNING
In this section we detail all hyperparameter choices that were made in this work. In general, we followed best practices of tuning hyperparameters on training and validation data, and reserved the test set for getting a final estimate of model's 's performance. The validation set was also used to perform early stopping: we trained all models until they failed to achieve new best value of the loss function for several consecutive epochs.
shows hyperparameter choices that were made for training RAEs with either Bernoulli or Gaussian noise (Section 5.2). The "schedule" indicates the portion of remaining features that were eliminated at each iteration of Algorithm I Eliminating features iteratively proved to be critical for these high-ding nigh-dimensional datasets (see Appendix G). For the penalty hyperparameter À that is used in both methods, indicates that was annealed at each iteration. After the model converged, features were eliminated if the average dropout rate P5 exceeded 0.5. Otherwise, À doubled and the
Table 4
14

---

Under review as a conference paper at ICLR 2020
Cell Type Classification
Cancer Subtype Classification
6.1
X
Classification Accuracy
0.55
Leplacian
MCFS
0.50
Joliiite
Gready
0.55
AEPS
Vanaacce
Imputation Loss (MSE)
Imputation Loss (MSE)
Figure 5: Downstream prediction accuracy versus imputation loss for subsets of 10 features selected by each method. Results across both datasets reveal a relationship between reconstruction ability and the predictive power of subsets of features.
Table Single-cell RNA sequencing imputation loss (MSE)
# Features
10
20
30
40
50
Laplacian
0.782
0.771
0.729
0.714
0.696
0.685
MCFS
0.869
0.784
0.731
0.702
0.694
0.682
UDFS
0.792
0.732
0.700
0.688
0.675
0.666
PFS
0.758
0.741
0.706
0.686
0.677
0.669
AEFS
0.783
0.720
0.684
0.670
0.663
0.658
Variance
0.752
0.719
0,694
0.669
0.665
0.660
Leverage
0.793
0.711
0.684
0.675
0.667
0.663
Jolliffe
0.769
0.710
0.683
0.674
0.667
0.662
Greedy
0.765
0.725
0.685
0.667
0.657
0.650
Bern. RAE
0.731
0.680
0.658
0.650
0.647
0.643
Gauss. RAE
0.731
0.678
0.657
0.650
0.647
0.644
Table 3: Gene microarray imputation loss (MSE)
# Features
10
20
30
40
50
Laplacian
0,912
0.874
0.833
0.807
0.787
0.772
MCFS
0.949
0.899
0.840
0.796
0.770
0.747
UDFS
0.985
0.945
0.842
0.806
0.780
0.762
PFS
0.895
0.847
0.790
0.757
0.732
0.717
AEFS
0.984
0.933
0.869
0.830
0.805
0.779
Leverage
0.962
0.925
0.867
0.814
0.785
0.770
Jolliffe
0.900
0.848
0.797
0.772
0.747
0.732
Greedy
0.887
0.823
0.766
0.739
0.713
0.696
Bern. RAE
0.896
0.835
0.774
0.737
0.713
0.696
Gauss. RAE
0.887
0.832
0.770
0.737
0.714
0.698
15

---

Under review as a conference paper at ICLR 2020
Table 4: Restricted autoencoder hyperparameters
Single-cell RNA
Gene microarray
Bernoulli
Gaussian
Bernoulli
Gaussian
Optimizer
Adam
Adam
Adam
Adam
Learning rate
10-3
10
10
10-3
Minibatch size
256
256
32
32
Architecture
[100] x 4
[100] x 4
[100] x 2
[100] x 2
Activations
ELU
ELU
ELU
ELU
Schedule
20%
20%
20%
20%
10.0*
0.1
10.0*
10.0
Table 5: Imputation model hyperparameters
Single-cell RNA
Gene microarray
Optimizer Learning rate
Adam
Adam
10-3
10-3
Minibatch size
264
256
Architecture
[100] x 4 ELU
[500] x 2 ELU
Activations
model was retrained. Overall, both methods were robust to most hyperparameters, except for the penalty parameter À and the schedule.
Jable[]ssows hyperparameters that were used to train imputation models given the features selected by each algorithm. Table shows hyperparameters that were used to train models for downstream tasks, including both real classification problems (Section 5.3) and simulated tasks (Section (54).
Finally, several baseline methods required hyperparameter choices. For Laplacian scores and MCFS, we calculated the 0-1 similarity matrix between data points using nearest neighbors. For the leverage scores method, calculated leverage scores using latent dimension of 25. For AEFS, we used MLP with single hidden layer of size 100, and tuned the regularization hyperparameter on validation data.
F VARIANCE WITHIN TRIALS
Unlike many the baseline methods we considered, RAEs do not select features deterministically. Variability arises from the model initialization and optimization, and manifests itself in the selection of different features each trial. That variability is beneficial, in the sense that the best features can be selected by measuring their performance on validation data. Here, we analyze the amount of variability incurred by RAEs through several experiments on the single-cell RNA sequencing data.
In Figure 6 we plot the mean and standard deviation of the imputation loss across 20 trials. For context, we include two baseline methods: Jolliffe, which somewhat competitive, and Laplacian
Table 6: Downstream prediction model hyperparameters
Cell type
Cancer subtype
Simulated tasks
Loss function
Cross entropy
Cross entropy
MSE
Optimizer
Adam
Adam
Adam
Learning rate
10-3
10-3
10-3
Minibatch size
64 [100] x
32
32
Architecture
[16] X
[50] x
Activations
ELU
ELU
ELU
16

---

Under review as a conference paper at ICLR 2020
0.90
Random (Mean)
Random (Mean 20))
Jolliffe
Imputation Loss (MSE)
0.85
Laplacian
Bernoulli RAE
Gaussian RAE
0.70
0.65
Number of features
Figure 6: Variance of imputation loss achieved by RAEs, and comparison with randomly selected features.
Table 7: Stability analysis
10 Features
30 Features
50
Features
Jaccard
Adj. Rand
Jaccard
Adj. Rand
Jaccard
Adj. Rand
Bernoulii RAE
0.722
0.833 0.843
0.722
0.834 0.833
0.718
0.830
Gaussian RAE
0.736
0.720
0.832
0.905
scores, which is among the least competitive baselines. We also include the results from 100 ran- domly selected sets of features. The results indicate that the amount of variance in the imputation loss from RAEs is negligible, compared to the gap with baseline methods. They also indicate that selecting features random naturally performs much worse, but that is easier to pick good features when the set is larger.
In Table 7 we quantify the consistency in the features that are selected within 20 trials. We calculate the average Jaccard index, and the average adjusted Rand index between each pair of trials. The results indicate that both methods are quite consistent, but that there is always variability.
To observe the variability in selected features across the two RAE methods, Bernoulli RAE and Gaussian RAE, Figure shows the number times each gene was selected among the 10 features, within 20 trials. Both methods very consistent with of their features, selecting them over 15 times within 20 trials. The two methods even tend to select 7 of the same features most trials. These results show that the methods have degree of consistency in the features they select. We leave for future work an analysis of the function of these genes for single-cell data.
G IMPORTANCE OF ITERATIVE ELIMINATION
To illustrate the importance of iterative elimination of features, as in Algorithm D we conduct an ablation experiment where remove this aspect of the method. On both datasets, learn RAEs by training an AE with Bernoulli or Gaussian noise a single time, ranking the features, and simply selecting the top ranked features. For fair comparison, chose the best results from 20 trials.
Figure shows a comparison with the results the main text, with the additional context of two baseline methods: Jolliffe, which is somewhat competitive, and Laplacian scores, which is among the least competitive baselines. The results demonstrate that iterative elimination is key to perform- ing effective feature selection, especially for small numbers of features.
17

---

Under review as a conference paper at ICLR 2020
Number gene selections
Bernoull
Gaussian
30
15
10
Cok
Pep4
Rab3b
Synpr
Rgad
Ptn
Malat1
Atplas aa
Ubb
Meg3
Fxyds
Coroc
Lamp5
Egra
Snhg11
Gabrai
Sparc12
Hapad
Seg2
Ckó
Carl
Pepdi1
Pdela
Ap1s2
Caimz
Noy
Tmsbot
Figure 7: Bar chart of gene selections single-cell RNA sequencing data. The stacked bar chart
shows how many times each gene was among the genes selected by each method, within 20 trials.
Single-cell RNA
Gene Microarray
0.65
Bernoull RAE (Iterative)
0.95
Bernoulli RAE (Iterative)
Gaussian RAE (Iterative)
Caussian RAE (Iteralive)
Imputation loss (MSE)
0.80
Dernoulli RAE (Ranking)
Gaussian RAE (Ranking)
Deroulli RAE (Renking)
Gaussian RAE (Ranking)
Laplacion
Loplecian
Jolliffe
jolliffe
0.75
0.70
0.85
0.70
10
20
40
10
30
40
50
Number of features
Number of features
Figure Comparison of RAFs learned through iterative elimination, and a single ranking step.
18

---

Under review as a conference paper at ICLR 2020
H SIMULATION STUDY
For the simulation study in Section 5.4 we simulated 250 response variables for each of three kinds of dependencies: linear, quadratic, and interaction effects. The precise method for simulating response variables was as follows.
For each the linear task, selected 50 genes uniformly at random, then simulated a coefficient vector from (0, Iso). The response variables were then calculated for every observation vector in the dataset, with additional noise added. The simulation method was similar for the quadratic and interaction effect tasks. For the quadratic tasks, we selected 25 genes to have linear dependencies, and 25 genes to have quadratic dependencies. For the interaction tasks, we selected 25 genes have linear dependencies, and then 25 pairs of genes (selected uniformly at random), where the response variable depended linearly on the product of the two genes' expression levels.
The full results of the simulation study are shown in Figure 9 including results for sets of 10, 20, and 30 genes. The results show that the features selected by the Bernoulli RAE and Gaussian RAE outperform other features in large portion of tasks. The most plausible explanation for these features' consistent ability to make better predictions their superior reconstruction ability.
19

---

Under review as a conference paper at ICLR 2020
Linear Tasks (10 Feats.)
Linear Tasks (20 Feats.)
Linear Tasks (30 Feats.)
Bern RAI
048 0.14 0.73 885 885 888 0.50 (355 0:6 856
0:50 0:00 8.66 8:00 8.5 0.1 0.4 0.90 0.99 039
0.2 0.78 889 0:4 853 052 052 091 039 1.0
Gauss
RAF 005
0.74 3.53 8.5 8:0 0.00 0:55 035 838
240
0.72 0.82 0.76 0.00 0.99 032 0.85 0.9 100
0.48
0.79 0.65 0.7 0:0 0:1 0.4 0.00 030 0:5
Creedy
0.2 0.2
0.55 0.2 8.33 880 070 0:2 335 035
020 028
2.00 0:00 0.76 0.85 0a5 0.14
033 100
0.22 0.2
0.72 0.70 076 0:00 031 0.77 1.0 050
Joliiffe
027 023 045
366 973 666 0.76 (30 357 087
014 018 0.32
643 6:68 064 0.75 0.1 051 057
011 0.28
0.46 956 665 066 052 096 666
Leverage
0.19 0.3
0.38 0.22
8.5 659 058 (37 315 082
020 026 0.38 857
0.2 057 0.75 0.75 032 037
0.15 0.3 0.30 0.4
6:5 052 072 065 033 654
Voniacce
0.14 012 027 027 044
054 640 376 024
007 012 024 0.22 028
0:5 053 0.0
038 030
0.09 0.20 0.4
0.22 0:5
042 0.44 054 804 086
PFS 0.12
012 020 033 041 646
640 045 226 088
0.00 0:1 014 0:6 0:3 642
040 0.43
075 033
0.00 0.99 0.2
0.35 0:38 0:58
044 033 686
UDFS
0.18 014
0.30 024 042 852 652
022 077
0.00 0.0 015 024 024 037 052
0.43 054 075
0.00 0.0 0.0 0:31 028 626
0.0 037 083
000
002 018 010 033 022 0:3 028
072 072
0 014 0.2 020 025 0:00 055 057
033 077
0.00 012 023 0:38 0:55 0:6 056 064
054
Laplscion
not 001 002 081 035 8888800000 0:4 034 028
050
001 0:00 oot 0:0 0:00 6:2 0:2 031
051
000 0.2 0:0 081 057 0:6
052
MCFS
no2 002 not 33 3 16 0:2 0.2 028 0:12
n00 0:00 nog 033 0:3 8:20 617 0:25 0:3 6.49
0.00 not 00) 016 0:4 1 10 o.0
Bern RAB
Gauns RAB
Gready
polifte
Leverage
Variance
PPS
uons ABTS
Laplacion
McPs
Bern. RAE
Gaund R48
Gready
jolifte
unverage
Varianca
PPS uOnS
AETS Laplacion
MCRS
Bem RAe
Gauns RAG
Greedy
juliife
Leverage
Variancc
PFS
uDrS
ABtS
Laplacinn
MCPS
Quadratic Tasks (10 Feats.) )
Quadratic Tasks (20 Feats.)
Quadratic Tasks (30 Feats.)
050 088 0.6
2 58 884 081 330 030 9:9
0.50 039 8:5 7.7 891 0:00 0:55 0.44 0.99 639
0.9 034 075
080 836
0.40
061 0.0 324 778 7 030 030 089 083
850
042: 0.74 7:0 057 057 0.55 0.54 0.55 034
051
037 077
054 054
Greedy
0.32 0.39
062 057 976 077 0T6 037 032 034
042 0:39
0.70 0:0 0:2 0.96 0.85 0.7 031 033
0.46 0.3
0.2 050 0:4
0.5 080 074 050
Jollifee
0:30 0:38
052 966 663 072 2 022 070
025 0.6 0:30
042 0:00 D.GG 0.70 0.7 0.00 078
0.5 023 0.23
0.50 0:5 0:3 050 085 083
Leverage
0.25
020
0.30 038
655 653 0m) 932 073 045
028 0:30 0:35 0:0
677 072 0.28 077 081 0.97
024 0.2 0:31 050
043 0:66 0.0
Vanance
0.14 0.2
020
034 045
654 050 075 665
809 013 018
034 023
0.50 0:4 046 0.22 064
017 016 02 0:45 039
077
053
AETS-
Laplacian
NCER
041
Barn RAE
Gauss RAB
Grendy
jaliffe
Leverage
Variance
PPS
uorg
ADDS
aaplacian
HCPS
Bern PAE
Gause RAB
Greedy
jaliffe
Lnverape
Variance
4075
Laplacion
MEPS
Ban RAE
causs, RAB
Grevey
Joliffe
Leverage
Variance
PPS
uons
AG1S
Laptecian
MCFS
Interaction Tasks (10 Feats.
Interaction Tasks (20 Feats.
Interaction Tasks (30 Feats.)
035
Gauss. RAE
Greedy
joliifee
Leverage
Vanance
9:44
051
PFS
650 063
017
UDFS
024 0:2 8:2
363 058
018
AFTS 016 017 014 035 023 032 037 037
544
037 022 018 0:3
0.2 023
Laplacian 0.5 010019000 022 026 039
042 a56
057
022 0:2 000 840 0:39 052 0.4 051 052
013 855 0.3 036 037
MCFS
016 019 018 028 335 8.34 8.36 038 0.7 343
930 012 oog 022 024 0.37 0:34 0.44 035 0.2
030 014 0.8 024 025 026 0.36 0.39
Bem RAB
Gauss RAB
Greedy patite
Leverage
Variance
PCS
Leorg
A27S Laplacian
MCFS
Bern RAE
Cause RAE
Greedy juturee
Leverage
Vananice
PPS
Lors aBrS Laplacian
MCFS
Bam RAB
Gauss RAE
Greedy juliffee
Leverage Vanance
PPS
urons ASPS
Laplaciin
MCFS
Figure 9: Results from the simulation study using single-cell RNA sequencing data. 250 response variables were simulated with three kinds of dependencies on the original features (750 total tasks) and were predicted using subsets of features. Heatmaps show pairwise comparisons between feature sets, displaying the portion of tasks in which features from the method on the y-axis outperformed those on the x-axis.
20


Reviews:
[{"review_id": "SyejVTsd9S", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper is concerned with unsupervised feature selection, in a lossy compression perspective. Formally, the idea is to select a subset of features that supports the reconstruction of the whole dataset.\n\nThe idea is good, but the the same idea (same reconstruction goal, also relying on auto-encoders) was published this year, see here: https://ecmlpkdd2019.org/programme/awards/\n\nAlgorithmically speaking, the approach is very close to the above paper; as far as I can tell, the main difference lies in the recursive feature elimination heuristics.\n\nI feel that the originality of the paper is thus severely undermined. The authors might want to address this, through:\n* thorough empirical comparisons (experimental setting, considering other datasets; comparing with other regularization schemes)\n* examining the stability of the selected features (among runs).\n\nThe analysis definitely is a good point of the paper; however, parts of it are straightforward (Thm1). \n\nDetails: continuity, p.3\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "SkeKMsaJqH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes an unsupervised feature selection method by minimizing reconstruction error with restricted autoencoders. The proposed method employs iterative elimination to select features with learned per-feature corruption rates. \n\n1) The novelty of the paper is very limited: using reconstruction for unsupervised feature selection has been explore in many papers, such as [1][2][3]. So the proposed method is a bit incremental.\n\n2) Time complexity of the proposed method should be discussed.\n\n3) Experimental results are not convincing at all due to the following reasons:\n  a) Only one baseline (out of 9) was proposed after 2011. Outperforming these decade old approaches is not very difficult. There has been much progress on unsupervised feature selection and several hundred papers in this area have been published in the past 5 years.  The author should include more recent state-of-the-art baselines.\n  b) When tuning the hyper-parameters (e.g., \\lambda) for the proposed method and baseline methods (UDFS) on validation dataset, the author should list the value range used in the parameter search. Also, as unsupervised feature selection methods, using validation dataset (which has supervision labels) to choose parameters is not a fair way, as it does use supervision information.\n  c) Unsupervised feature selection papers in the past 5 years typically use 6~8 datasets to demonstrate the effectiveness while this paper only shows results on 2 datasets.\n\nGiven the reasons above, this paper needs improvement in many aspects and not ready to publish in its current form.\n\n\n[1] Zhu et al. Unsupervised feature selection by regularized self-representation\n\n[2] Yang et al. Unsupervised Feature Selection Based on Reconstruction Error Minimization\n\n[3] Li et al. Reconstruction-based Unsupervised Feature Selection: An Embedded Approach", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "ByglajI6FS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Authors of this paper propose the restricted autoencoder (RAE) framework for selecting features that can accurately reconstruct the rest of features. Authors justify the proposed method via the proof that the reconstruction ability of a set of features bounds its performance in downstream supervised learning tasks. The algorithm that iteratively eliminates features using learned per-feature corruption rates is proposed.\n\nThe fundamental of this paper is built on the argument that the optimal approach is to select a set of features that can accurately reconstruct all the remaining features for the settings where they will be used in downstream prediction tasks. Authors studied the performance losses of linear and nonlinear models by using the defined imputation losses.  Some concerns are listed as follows:\n1. the theorem based on strong assumptions that all learned models are optimal. The applicability of the theoretical results to general prediction model is still questionable. \n2. only the prediction problems of least square (linear or nonlinear) are studied. It is not equivalent to the downstream supervised learning tasks. It is just a special case study.\n3. It is unclear how to get the conclusion from Theorem 1 that the linear imputation loss is equal to the sum of eigenvalues. Please clarify it in details.\n\nThe RFE-like algorithm is used to solve (7). However, the sensitivity measures used in Algorithm 1 seems to take the different optimization problems since additional regularization terms are added. This is different from RFE where a single SVM optimization problem is used and the ranking score is solely based on the learned SVM classifier. The discussion on the inconsistency of learning h_{\\theta} and the sensitivity measures could be interesting. \n\nIn the experiments, authors did not mention the parameter settings of all compared methods. It is known that the unsupervised feature selection methods incorporate priors with usually various parameters. For fair comparisons, it is better to report the properly tuned results since these parameters are often data-dependent. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes Restricted AutoEncoders (REAs) for unsupervised feature selection, and applies and evaluates it in applications in biology. The paper was reviewed by three experts. R1 recommends Weak Reject, identifying some specific technical concerns as well as questions about missing and unclear experimental details. R2 recommends Reject, with concerns about limited novelty and unconvincing experimental results. R3 recommends Weak Accept saying that the overall idea is good, but also feels the contribution is "severely undermined" by a recently-published paper that proposes a very similar approach. Given that that paper (at ECMLPKDD 2019) was presented just one week before the deadline for ICLR, we would not have expected the authors to cite the paper. Nevertheless, given the concerns expressed by the other reviewers and the lack of an author response to help clarify the novelty, technical concerns, and missing details, we are not able to recommend acceptance. We believe the paper does have significant merit and hope that the reviewer comments will help authors in preparing a revision for another venue.
Decision: Reject