summaries: The main contribution of the paper is an integral model compression method that handles both weight and activation pruning. Increasing the network weight and activation sparsity can lead to more efficient network computation.  The authors show in the paper that pruning the network weights alone may result in a decrease in activation sparsity, which may not necessarily improve the overall computation. The proposed solution is a 2-stage process that first prunes the weights and then the activation.

summaries: This article presents a novel approach called Integral Pruning (IP) to reduce the computation cost of Deep neural networks (DNN) by integrating activation pruning along with weight pruning. The authors show that common techniques of exclusive weight pruning does compress the model size, but increases the number of non-zero activations after ReLU. This would counteract the advantage of DNN accelerator designs (Albericio et al., 2016; Reagen et al., 2016) that leverage activation sparsity to speed up the computations. IP starts with pruning the weights using an existing technique to mask out weights under a threshold and then fine-tune the network in an iterative fashion to maintain the accuracy. After weight pruning, IP further masks out the activations with smaller magnitude to reduce the computation cost. Unlike weight pruning techniques that use static masks, the authors propose to use dynamic activation masks for activation sparsity in order to account for various patterns that are being activated in DNN for different input samples. In order to do this, the 'winner rate' measure for every layer (or for a group of layers in deep networks like ResNet32) is defined, to dynamically set the threshold for the generation of activation masks which eventually controls the amount of non-zero activation entries. The article empirically analyzes the sensitivity of activation pruning on validation data by setting different winner rates at every layer in DNN and decides upon a set of winner rates accordingly followed by an iteration of fine-tuning the network to maintain its performance. The authors show that their technique produced lower number of non-zero activations in comparison with the intrinsic sparse ReLU activations and weight pruning techniques.

abstractText: With the rapidly scaling up of deep neural networks (DNNs), extensive research studies on network model compression such as weight pruning have been performed for efficient deployment. This work aims to advance the compression beyond the weights to the activations of DNNs. We propose the Integral Pruning (IP) technique which integrates the activation pruning with the weight pruning. Through the learning on the different importance of neuron responses and connections, the generated network, namely IPnet, balances the sparsity between activations and weights and therefore further improves execution efficiency. The feasibility and effectiveness of IPnet are thoroughly evaluated through various network models with different activation functions and on different datasets. With < 0.5% disturbance on the testing accuracy, IPnet saves 71.1% ∼ 96.35% of computation cost, compared to the original dense models with up to 5.8× and 10× reductions in activation and weight numbers, respectively. The source codes are available at (omitted for blind review).

authors:
Jorge Albericio
Patrick Judd
Tayler Hetherington
Tor Aamodt
Natalie Enright Jerger
Andreas Moshovos

title: Cnvlutin: Ineffectual-neuron-free deep neural network computing

venue: In ACM SIGARCH Computer Architecture News,

authors:
Jimmy Ba
Brendan Frey

title: Adaptive dropout for training deep neural networks

venue: In Advances in Neural Information Processing Systems,

authors:
Jon Louis Bentley
Dorothea Haken
James B Saxe

title: A general method for solving divide-andconquer recurrences

venue: ACM SIGACT News,

authors:
Yu-Hsin Chen
Joel Emer
Vivienne Sze

title: Eyeriss: A spatial architecture for energy-efficient dataflow for convolutional neural networks

authors:
Song Han
Jeff Pool
John Tran
William Dally

title: Learning both weights and connections for efficient neural network

venue: In Advances in neural information processing systems,

authors:
Song Han
Xingyu Liu
Huizi Mao
Jing Pu
Ardavan Pedram
Mark A Horowitz
William J Dally

title: Eie: efficient inference engine on compressed deep neural network

venue: In Computer Architecture (ISCA),

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Norman P Jouppi
Cliff Young
Nishant Patil
David Patterson
Gaurav Agrawal
Raminder Bajwa
Sarah Bates
Suresh Bhatia
Nan Boden
Al Borchers

title: In-datacenter performance analysis of a tensor processing unit

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks. In Advances in neural information processing

authors:
Baoyuan Liu
Min Wang
Hassan Foroosh
Marshall Tappen
Marianna Pensky

title: Sparse convolutional neural networks

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Alireza Makhzani
Brendan J Frey

title: Winner-take-all autoencoders

authors:
Huizi Mao
Song Han
Jeff Pool
Wenshuo Li
Xingyu Liu
Yu Wang
William J Dally

title: Exploring the granularity of sparsity in convolutional neural networks

venue: IEEE CVPRW,

authors:
Pavlo Molchanov
Stephen Tyree
Tero Karras
Timo Aila
Jan Kautz

title: Pruning convolutional neural networks for resource efficient inference

venue: arXiv preprint arXiv:1611.06440,

authors:
Jongsoo Park
Sheng Li
Wei Wen
Ping Tak Peter Tang
Hai Li
Yiran Chen
Pradeep Dubey

title: Faster cnns with direct sparse convolutions and guided pruning

venue: arXiv preprint arXiv:1608.01409,

authors:
Brandon Reagen
Paul Whatmough
Robert Adolf
Saketh Rama
Hyunkwang Lee
Sae Kyu Lee
José Miguel Hernández-Lobato
Gu-Yeon Wei
David Brooks

title: Minerva: Enabling low-power, highly-accurate deep neural network accelerators

authors:
Joseph Redmon
Santosh Divvala
Ross Girshick
Ali Farhadi

title: You only look once: Unified, real-time object detection

authors:
Tara N Sainath
Carolina Parada

title: Convolutional neural networks for small-footprint keyword spotting

venue: In Sixteenth Annual Conference of the International Speech Communication Association,

authors:
Wei Wen
Chunpeng Wu
Yandan Wang
Yiran Chen
Hai Li

title: Learning structured sparsity in deep neural networks

authors:
Jiecao Yu
Andrew Lukefahr
David Palframan
Ganesh Dasika
Reetuparna Das
Scott Mahlke

title: Scalpel: Customizing dnn pruning to the underlying hardware parallelism

authors:
Sergey Zagoruyko
Nikos Komodakis

title: Wide residual networks

venue: arXiv preprint arXiv:1605.07146,

title: Adadelta: an adaptive learning rate method

venue: arXiv preprint arXiv:1212.5701,

authors:
Chen Zhang
Peng Li
Guangyu Sun
Yijin Guan
Bingjun Xiao
Jason Cong

title: Optimizing fpgabased accelerator design for deep convolutional neural networks

venue: In Proceedings of the 2015 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays,

heading: 1 INTRODUCTION

text:
Deep neural networks (DNNs) have demonstrated significant advantages in many real-world applications, such as image classification, object detection and speech recognition (He et al., 2016; Redmon et al., 2016; Sainath & Parada, 2015). On the one hand, DNNs are developed for improving performance in these applications, which leads to intensive demands in data storage, communication and processing. On the other hand, the ubiquitous intelligence promotes the deployment of DNNs in light-weight embedded systems that are equipped with only limited memory and computation resource. To reduce the model size while ensuring the performance quality, DNN pruning is widely explored. Redundant weight parameters are removed by zeroing-out those in small values (Han et al., 2015; Park et al., 2016). Utilizing the zero-skipping technique (Han et al., 2016) on sparse weight parameters can further save the computation cost. In addition, many specific DNN accelerator designs (Albericio et al., 2016; Reagen et al., 2016) leveraged the intrinsic zero-activation pattern of the rectified linear unit (ReLU) to realize the activation sparsity. The approach, however, cannot be directly extended to other activation functions, e.g., leaky ReLU.
Although these techniques achieved tremendous success, pruning only the weights or activations cannot lead to the best inference speed, which is a crucial metric in DNN deployment, for the following reasons. First, the existing weight pruning methods mainly focus on the model size reduction. However, the most essential challenge of speeding up DNNs is to minimize the computation cost, such as the intensive multiple-and-accumulate operations (MACs). Particularly, the convolution (conv) layers account for most of the computation cost and dominate the inference time in DNNs (Park et al., 2016). Because weights are shared in convolution, the execution speed of conv layers is usually bounded by computation instead of memory accesses (Jouppi et al., 2017; Zhang et al., 2015). Second, the activation in DNNs is not strictly limited with ReLU. The intrinsic zeroactivation patterns do not exist in non-ReLU activation functions, such as leaky ReLU and sigmoid. Third, the weights and activations of a network together determine the network performance. Our experiment shows that the zero-activation percentage obtained by ReLU decreases after applying the weight pruning (Han et al., 2016). Such a deterioration in activation sparsity could potentially eliminate the advantage of the aforementioned accelerator designs.
In this work, we propose the integral pruning (IP) technique to minimize the computation cost of DNNs by pruning both weights and activations. As the pruning processes for weights and activations are correlated, IP learns dynamic activation masks by attaching activation pruning to weight pruning after static weight masks are well trained. Through the learning on the different importance of neuron responses and connections, the generated network, namely IPnet, balances the sparsity between activations and weights and therefore further improves execution efficiency. Moreover, our method not only stretches the intrinsic activation sparsity of ReLU, but also targets as a general approach for other activation functions, such as leaky ReLU. Our experiments on various network models with different activation functions and on different datasets show substantial reduction in MACs by the proposed IPnet. Compared to the original dense models, IPnet can obtain up to 5.8× activation compression rate, 10× weight compression rate and eliminate 71.1% ∼ 96.35% of MACs. Compared to state-of-the-art weight pruning technique (Han et al., 2015), IPnet can further reduce the computation cost 1.2× ∼ 2.7×.

heading: 2 RELATED WORKS

text:
Weight Pruning: The weight pruning emerges as an effective compression technique in reducing the model size and computation cost of neural networks. A common approach of pruning the redundant weights in DNN training is to include an extra regularization term (e.g., the `1-normalization) in the loss function (Liu et al., 2015; Park et al., 2016) to constrain the weight distribution. Then the weights below a heuristic threshold will be pruned. Afterwards, a certain number of finetuning epochs will be applied for recovering the accuracy loss due to the pruning. In practice, the directpruning and finetuning stages can be carried out iteratively to gradually achieve the optimal trade-off between the model compression rate and accuracy. Such a weight pruning approach demonstrated very high effectiveness, especially for fully-connected (fc) layers (Han et al., 2015). For conv layers, removing the redundant weights in structured forms, e.g., the filters and filter channels, has been widely investigated. For example, Wen et al. (2016) proposed to apply group Lasso regularization on weight groups in a variety of self-defined sizes and shapes to remove redundant groups. Molchanov et al. (2016) used the first-order Taylor series expansion of the loss function on feature maps to determine the rankings of filters and those in low ranking will be removed. The filter ranking can also be represented by the root mean square or the sum of absolute values of filter weights (Mao et al., 2017; Yu et al., 2017).
Activation Sparsity: The activation sparsity has been widely utilized in various DNN accelerator designs. Chen et al. (2016), Albericio et al. (2016) and Reagen et al. (2016) accelerated the DNN inference with reduced off-chip memory access and computation cost benefiting from the sparse activations originated from ReLU. A simple technique to improve activation sparsity by zeroing out small activations was also explored (Albericio et al., 2016). However, the increment of activation sparsity is still limited without accuracy loss. The biggest issue in the aforementioned works is that they heavily relied on ReLU. However, zero activations do not exist in non-ReLU activation function. To regulate and stretch the activation sparsity, many dropout-based methods are proposed. Adaptive dropout (Ba & Frey, 2013), for instance, developed a binary belief network overlaid on the original network. The neurons with larger activation magnitude incur higher probability to be activated. Although this method achieved a better regularization on DNNs, the inclusion of belief network complicated the training and had no help on inference speedup. The winners-take-all (WTA) autoencoder was built with a regularization based on activation magnitude to learn deep sparse representations from various datasets (Makhzani & Frey (2015)).
As can be seen that the model size compression is the main focus of weight pruning, while the use of activation sparsification focuses more on the intrinsic activation sparsity by ReLU or exploring the virtue of sparse activation in the DNN training for better model generalization. In contrast, our proposed IP aims for reducing the DNN computation cost and therefore accelerating the inference by integrating and optimizing both weight pruning and activation sparsification.

heading: 3 APPROACH

text:
As depicted in Figure 1, the proposed IP consists of two steps by concatenating the activation pruning to the weight pruning. Both stages seek for unimportant information (weights and activations,
respectively) and mask them off. We aim to keep only the important connections and activations to minimize the computation cost. In this section, we will first explain the integration of the two steps. The technical details in model quality (e.g., accuracy) control will then be introduced. The prediction method for deriving activation masks is also proposed to speed up the inference of IPnets. At last, the appropriate settings of dropout layers and training optimizers are discussed.

heading: 3.1 INTEGRATION OF WEIGHT PRUNING AND ACTIVATION PRUNING

text:
Weight pruning. In the weight pruning stage, weight parameters with magnitude under a threshold are masked out, and weight masks will be passed to the following finetuning process. After the model is finetuned for certain epochs to recover accuracy loss, weight masks need to be updated for the next finetuning round. There are two crucial techniques to help weight pruning. 1) The threshold used to build weight masks are determined based on the weight distribution of each layer. Because of different sensitivity for weight pruning, each layer owns a specific weight sparsity pattern. Basically, the leading several conv layers are more vulnerable to weight pruning. 2) The whole weight pruning stage needs multiple pruning-finetuning recursions to search an optimal weight sparsity. Weight masks are progressively updated to increase pruning strength.
Activation pruning. While weak connections between layers are learned to be pruned, activaitons with small magnitude are taken as unimportant and can be masked out to further minimize interlayer connections, and hence to reduce computation cost. Notice that, neurons in DNNs are trained to be activated in various patterns according to different input classes, thus dynamic masks should be learned in the activation pruning stage, which are different from the static masks in the weight pruning stage. The selected activations by the dynamic mask are denoted as winners, and the winner rate is defined as:
Winner rate = Swinner Stotal , (1)
where Swinner and Stotal denote the number of winners and total activation number. The winner rate per layer is determined by the analysis of activation pruning sensitivity layer-wise on the models obtained after weight pruning. The winner activation after the pruning mask, Am, obeys the rule:
Am = { Aorig, if |Aorig| > θ 0, otherwise
(2)
where θ is the threshold derived at run-time from the activation winner rate for each layer, andAorig is the result from original activation function. Same with weight pruning, the model with dynamic activation masks is finetuned to recover accuracy drop. No iterative procedure of mask updating and finetuning is required in our activaiton pruning method.

heading: 3.2 WINNER RATE SETTINGS

text: Not all layers share the same winner rate. Similar to the trend in weight pruning, deeper layers tolerate larger activation pruning strength. To analyze the activation pruning sensitivity, the model with activation masks is tested on a validation set sampled from the training images with the same size as the testing set. Accuracy drops are taken as the indicator of pruning sensitivity for different winner rate settings. Before finetuning, the activation winner rate per layer is set empirically to keep accuracy drop less than 2%. For the circumstances that model accuracy is resistant to be tuned back, winner rates in the leading several layers should be set smaller. Examples of sensitivity analysis will be given and discussed in Section 5.

heading: 3.3 THRESHOLD PREDICTION IN ACTIVATION PRUNING

text: The dynamic activation pruning method increases the activation sparsity and maintains the model accuracy as well. The solution of determining threshold θ in Equation (2) for activation masks is actually a canonical argpartion problem to find top-k arguments in an array. According to the Master Theorem (Bentley et al., 1980), argpartition can be fast solved in linear time O(N) through recursive algorithms, where N is the number of elements to be partitioned. To further speed up, threshold prediction can be applied on the down-sampled activation set. An alternate threshold θ′ is predicted by selecting top-αk elements from the down-sampled activation set comprising αN elements with α as the down-sampling rate. θ′ is applied for the original activation set afterwards.

heading: 3.4 DROPOUT LAYER WITH ACTIVATION PRUNING

text:
For DNN training, dropout layer is commonly added after large fc layers to avoid over-fitting problem. The neuron activations are randomly chosen in the feed-forward phase, and weights updates will be only applied on the neurons associated with the selected activations in the back-propagation phase. Thus, a random partition of weight parameters are updated in each training iteration. Although the activation mask only selects a small portion of activated neurons, dropout layer is still needed, for the selected neurons with winner activations are always kept and updated, which makes over-fitting prone to happen. In fc layers, the remaining activated neurons are reduced to Swinner from Stotal neurons as defined in Equation (1). The dropout layer connected after the activation mask is suggested to be modified with the setting:
Dropout rate = 0.5 √ Swinner Stotal = 0.5 √ Winner rate, (3)
where 0.5 is the conventionally chosen dropout rate in the training process for original models, and the activation winner rate is introduced to regulate the dropout strength for balancing over-fitting and under-fitting. The dropout layers will be directly removed in the inference stage.

heading: 3.5 OPTIMIZER AND LEARNING RATE

text: We find different optimizer requirements for weight pruning and activation pruning. In the weight pruning stage, it’s recommended to adopt the same optimizer used for training the original model. The learning rate should be properly reduced to 0.1× ∼ 0.01× of the original learning rate. In the activation pruning stage, our experiments show that Adadelta (Zeiler, 2012) usually brings the best performance. Adadelta adapts the learning rate for each individual weight parameter. Smaller updates are performed on neurons associated with more frequently occurring activations, whereas larger updates will be applied for infrequent activated neurons. Hence, Adadelta is beneficial for sparse weight updates, which is exactly the common situation in our activation pruning. During finetuning, only a small portion of weight parameters are updated because of the combination of sparse patterns in weights and activations. The learning rate for Adadelta is also reduced 0.1× ∼ 0.01× compared to that used in training the original model.

heading: 4 EXPERIMENTS

text:
All of our models and evaluations are implemented in TensorFlow. IPnets are verified on various models ranging from simple multi-layer perceptron (MLP) to deep convolution neural networks (CNNs) on three datasets, MNIST, CIFAR-10 and ImageNet as in Table 1. For AlexNet (Krizhevsky et al., 2012) and ResNet-32 (Zagoruyko & Komodakis, 2016), we focus on conv layers because conv layers account for more than 90% computation cost in these two models.
The compression results of IPnets on activations, weights and MACs are summarized in Table 1 compared to the original dense models. IPnets achieve a 2.3× ∼ 5.8× activation compression rate and a 2.5× ∼ 10× weight compression rate. Benefiting from sparse weights and activations, IPnets only need 3.65% ∼ 28.9% of MACs required in dense models. The accuracy drop is kept less than 0.5%, and for some cases, e.g., MLP-3 and AlexNet in Table 1, the IPnets achieve a better accuracy.
Table 1 shows that our method can learn both sparser activations and sparse weights and thus save computation. More importantly, in Figure 2, we will show that our approach is superior to ap-
proaches which explore intrinsic sparse ReLU activations and state-of-the-art weight pruning. The ReLU function brings intrinsic zero activations for MLP-3, ConvNet-5 and AlexNet in our experiments. However, the non-zero activation percentage increases in weight-pruned (WP) models as depicted in Figure 2 (a). The increment of non-zero activations undermines the effort from weight pruning. The activation pruning can remedy the activation sparsity loss and prune 7.7% - 18.5% more activations even compared to the original dense models. The largest gain from IP exits in ResNet-32 which uses leaky ReLU as activation function. Leaky ReLU generates dense activations in the original and WP models. The IPnet for ResNet-32 realizes a 61.4% activation reduction. At last, IPnets reduce 4.4% ∼ 22.7% more MACs compared to WP models as depicted in Figure 2 (b), which means a 1.2× ∼ 2.7× improvement. More details on model configuration and analysis are discussed as follows.

heading: 4.1 MLP-3 ON MNIST

text: The MLP-3 on MNIST has two hidden layers with 300 and 100 neurons respectively, and the model configuration details are summarized in Table 2. The amount of MACs is calculated with batch size as 1, and the non-zero activation percentage at the output per layer is averaged from random 1000 samples from the training dataset. The following discussions on other models obey the same statistics setting. The model size of MLP-3 is firstly compressed 10× through weight pruning. IP further reduces the total number of MACs to 3.65% by keeping only 17.1% activations. The accuracy of the priginal dense model is 98.41% on MNIST, and the aggressive reduction of MACs (27.4×) doesn’t decrease the accuracy.

heading: 4.2 CONVNET-5 ON CIFAR-10

text: For digit images in MNIST dataset have specific sparse features, the results on small-footprint MLP3 are very promising. IP is further applied for a 5-layers CNN, ConvNet-5, on a more complicated dataset, CIFAR-10. With two conv layers and three fc layers, the original model has an 86% accuracy. As shown in Table 3, the IPnet for ConvNet-5 only needs 27.7% of total MACs compared to the dense model through pruning 59.6% of weights and 56.4% of activations at the same time. The accuracy only has a marginal 0.06% drop. The dominant computation cost is from conv layers accounting for more than 4/5 of total MACs for inference. Although fc layers can generally be pruned in larger strength than conv layers, the computation cost reduction of IPnet is dominated by the pruning results in conv layers.

heading: 4.3 ALEXNET ON IMAGENET

text: We push IP onto AlexNet for ImageNet ILSVRC-2012 dataset which consists of about 1.2M training images and 50K validating images. The ALexNet comprises 5 conv layers and 3 fc layers and achieves 57.22% top-1 accuracy on the validation set. Similar to ConvNet-5, the computation bottleneck of AlexNet exits in conv layers by consuming more than 9/10 of total MACs. We focus on conv layers here. As shown in Table 4, deeper layers have larger pruning strength on weights and activations because of the sparse high-level feature abstraction of input images. For example, the MACs of layer conv5 can be reduced 10×, while only a 1.2× reduction rate is realized in layer conv1. In total, the needed MACs are reduced 3.5× using IP with 38.8% weights and 44.2% activations.

heading: 4.4 GOING DEEPER

text:
CNN models are getting deeper with tens to hundreds of conv layers. We verify the IP method on ResNet-32 as shown in Table 5. The ResNet-32 consists of 1 conv layer, 3 stacked residual units and 1 fc layer. Each residual unit contains 5 consecutive residual blocks. The filter numbers in residual units increase rapidly, and same for weight amount. An average pooling layer is connected before the last fc layer to reduce feature dimension. Compared to conv layers, the last fc layer can be neglected in terms of weight volume and computation cost. The original model has a 95.01% accuracy on CIFAR-10 dataset with 7.34G MACs per image. Weight and activation pruning strength is designed unit-wise to reduce the exploration space of hyperparameters, i.e., threshold settings. Notice that leaky ReLU is used as the activation function, thus zero activations are extremely hard to occur in the original and WP model. Only with IP, the activation percentage can be reduced down to 38.6%. As shown in Table 5, the model size is compressed 3.1×, and the final gain is that 86.3% of MACs can be avoided while keeping the accuracy drop less than 0.5%.
By randomly selecting 500 images from the training images, the activation distribution of the first residual block in baseline model is depicted in Figure 3 (a). Activations gather near zero with
long tails towards both positive and negative directions. The activation distribution after IP are shown in Figure 3 (b). Activations near zero are pruned out, and the major contribution comes from removing small negative values. In addition, the kept activations are trained to be stronger with larger magnitude, which is consistent with the phenomenon that the non-zero activation percentage increases after weight pruning when using ReLU as illustrated in Figure 2 (a).

heading: 5 DISCUSSION

text:
The static activation pruning approach has been widely adopted in efficient DNN accelerator designs (Albericio et al., 2016; Reagen et al., 2016). By selecting a proper static threshold θ in Equation (2), more activations can be pruned with little impact on model accuracy. For the activation pruning in IP, the threshold is dynamically set according to the winner rate and activation distribution layer-wise. The comparison between static and dynamic pruning is conducted on ResNet-32 for CIFAR-10 dataset. For the static pruning setup, the θ for leaky ReLU is assigned in the range of [0.07, 0.14], which brings different activation sparsity patterns.
As the result of leaky ReLU with static threshold shown in Figure 4, the accuracy starts to drop rapidly when non-zero activation percentage is less than 58.6% (θ = 0.08). Using dynamic threshold settings according to winner rates, a better accuracy can be obtained under the same activation sparsity constraint. Finetuning the model using dynamic activation masks will dramatically recover
the accuracy loss. As our experiment in Section 4.4, the IPnet for ResNet-32 can be finetuned to eliminate the 10.4% accuracy drop caused by the static activation pruning.
In weight pruning, the applicable pruning strength is different per layer (Han et al., 2015; Molchanov et al., 2016). Similarly, the pruning sensitivity analysis is required to determine the proper activation pruning strength layer-wise, i.e., the activation winner rate per layer. Figure 5 shows two examples on WP models from AlexNet and ResNet-32. For AlexNet in Figure 5 (a), the accuracy drops sharply when the activation winner rate of layer conv1 is less than 0.3. Meanwhile, the winner rate of layer conv5 can be set under 0.1 without hurting accuracy. Deeper conv layers can support sparser activations. The ResNet-32 in Figure 5 (b) has a similar trend of activation pruning sensitivity. Layer conv1 is most susceptible to the activation pruning. Verified by thorough experiments in Section 4, the accuracy loss can be well recovered by finetuning with proper activation winner rates.
As discussed in Section 3.3, the process to select activation winners can be accelerated by threshold prediction on down-sampled activation set. We apply different down-sampling rates on the IPnet for AlexNet. As can be seen in Figure 6, layer conv1 is most vulnerable to threshold prediction. From the overall results, it’s practical to down-sample 10% (α = 0.1) of activations by keeping the accuracy drop less than 0.5%.

heading: 6 CONCLUSION

text: To minimize the computation cost in DNNs, IP combining weight pruning and activation pruning is proposed in this paper. The experiment results on various models for MNIST, CIFAR-10 and ImageNet datasets have demonstrated considerable computation cost reduction. In total, a 2.3× - 5.8× activation compression rate and a 2.5× - 10× weight compression rate are obtained. Only 3.65% - 28.9% of MACs are left with marginal effects on model accuracy, which outperforms the weight pruning by 1.2× - 2.7×. The IPnets are targeted for the dedicated DNN accelerator designs with efficient sparse matrix storage and computation units on chip. The IPnets featuring compressed model size and reduced computation cost will meet the constraints from memory space and computing resource in embedded systems.


summaries: The paper presents a deep-learning-based version of the knockoff method by Candes et al. for FDR control in feature selection problems to avoid assumptions posed on the distribution of features by the original method. In a supervised feature selection setting, the goal of the knockoff framework is to select a set of input features that are statistically associated to an output variable Y, while controling the FDR. The basic idea behind knockoff is to generate artificial input feature vectors, (i.e. knockoffs) that are independent of Y, when conditioned on the real feature vector X, but after swapping arbitrary elements with X, are distributed as X. Sets of associated features and FDR estimates are obtained by contrasting suited feature selction criteria that measure associations of knockoffs and real features with the target Y.

summaries: This paper introduces a novel feature selection method by utilizing GAN to learn the distributions. The novelty of this paper is to incorporate two recent works, i.e. knockoff for feature selection and W-GAN for generative models. Compared to the latest knockoff work which requires a known multivariate Gaussian distribution for the feature distribution, the proposed work is able to generate knockoffs for any distribution and without any prior knowledge of it.

abstractText: Feature selection is a pervasive problem. The discovery of relevant features can be as important for performing a particular task (such as to avoid overfitting in prediction) as it can be for understanding the underlying processes governing the true label (such as discovering relevant genetic factors for a disease). Machine learning driven feature selection can enable discovery from large, high-dimensional, nonlinear observational datasets by creating a subset of features for experts to focus on. In order to use expert time most efficiently, we need a principled methodology capable of controlling the False Discovery Rate. In this work, we build on the promising Knockoff framework by developing a flexible knockoff generation model. We adapt the Generative Adversarial Networks framework to allow us to generate knockoffs with no assumptions on the feature distribution. Our model consists of 4 networks, a generator, a discriminator, a stability network and a power network. We demonstrate the capability of our model to perform feature selection, showing that it performs as well as the originally proposed knockoff generation model in the Gaussian setting and that it outperforms the original model in non-Gaussian settings, including on a real-world dataset.

authors:
John A Ambrose
Rajat S Barua

title: The pathophysiology of cigarette smoking and cardiovascular disease: an update

venue: Journal of the American college of cardiology,

authors:
Rina Foygel Barber
Emmanuel J

title: Candes. A knockoff filter for high-dimensional selective inference

venue: arXiv preprint arXiv:1602.03574,

authors:
Mohamed Ishmael Belghazi
Aristide Baratin
Sai Rajeshwar
Sherjil Ozair
Yoshua Bengio
Devon Hjelm
Aaron Courville

title: Mutual information neural estimation

venue: In Proceedings of the 35th International Conference on Machine Learning,

authors:
Yoav Benjamini
Yosef Hochberg

title: Controlling the false discovery rate: a practical and powerful approach to multiple testing

venue: Journal of the royal statistical society. Series B (Methodological), pp

authors:
Yoav Benjamini
Daniel Yekutieli

title: The control of the false discovery rate in multiple testing under dependency

venue: Annals of statistics,

authors:
Emmanuel Candès
Yingying Fan
Lucas Janson
Jinchi Lv

title: Panning for gold: Model-free knockoffs for high-dimensional controlled variable selection

venue: arXiv preprint arXiv:1610.02351,

authors:
Antonio Ceriello
Dario Giugliano
Antonio Quatraro
Pierre J Lefebvre

title: Anti-oxidants show an anti-hypertensive effect in diabetic and hypertensive subjects

venue: Clinical Science,

authors:
Yingying Fan
Emre Demirkaya
Gaorong Li
Jinchi Lv

title: Rank: large-scale inference with graphical nonlinear knockoffs

venue: arXiv preprint arXiv:1709.00092,

authors:
Jaime Roquero Gimenez
Amirata Ghorbani
James Zou

title: Knockoffs for the mass: new feature importance statistics with false discovery guarantees

venue: arXiv preprint arXiv:1807.06214,

authors:
Ian Goodfellow
Jean Pouget-Abadie
Mehdi Mirza
Bing Xu
David Warde-Farley
Sherjil Ozair
Aaron Courville
Yoshua Bengio

title: Generative adversarial nets

authors:
Isabelle Guyon
André Elisseeff

title: An introduction to variable and feature selection

venue: Journal of machine learning research,

authors:
C Jaffiol
F Thomas
K Bean
B Jégo
N Danchin

title: Impact of socioeconomic status on diabetes and cardiovascular risk factors: results of a large french survey

venue: Diabetes & metabolism,

authors:
Pekka Jousilahti
Erkki Vartiainen
Jaakko Tuomilehto
Pekka Puska

title: Symptoms of chronic bronchitis and the risk of coronary disease

title: Sex, age, cardiovascular risk factors, and coronary heart disease: a prospective follow-up study of 14 786 middle-aged men and women

venue: in finland. Circulation,

authors:
Alan Jović
Karla Brkić
Nikola

title: Bogunović. A review of feature selection methods with applications

venue: In Information and Communication Technology, Electronics and Microelectronics (MIPRO),

authors:
Eugene Katsevich
Chiara Sabatti

title: Multilayer knockoff filter: Controlled variable selection at multiple resolutions

venue: arXiv preprint arXiv:1706.09375,

authors:
D Lawlor
S Ebrahim
G Davey Smith

title: The association between components of adult height and type ii diabetes and insulin resistance: British women’s heart and health

venue: study. Diabetologia,

authors:
Christian Ledig
Lucas Theis
Ferenc Huszár
Jose Caballero
Andrew Cunningham
Alejandro Acosta
Andrew P Aitken
Alykhan Tejani
Johannes Totz
Zehan Wang

title: Photo-realistic single image super-resolution using a generative adversarial network

venue: In CVPR,

authors:
Michael Marmot
Eric Brunner

title: Alcohol and cardiovascular disease: the status of the u shaped curve

venue: BMJ: British Medical Journal,

authors:
Tahir Mehmood
Kristian Hovde Liland
Lars Snipen
Solve Sæbø

title: A review of variable selection methods in partial least squares regression

venue: Chemometrics and Intelligent Laboratory Systems,

authors:
Howraman Meteran
Vibeke Backer
Kirsten Ohm Kyvik
Axel Skytthe
Simon Francis Thomsen

title: Heredity of chronic bronchitis: a registry-based twin study

venue: Respiratory medicine,

authors:
Sebastian Nowozin
Botond Cseke
Ryota Tomioka

title: f-gan: Training generative neural samplers using variational divergence minimization

authors:
Carl Rietschel
Jinsung Yoon
Mihaela van der Schaar

title: Feature selection for survival analysis with competing risks using deep learning

venue: arXiv preprint arXiv:1811.09317,

authors:
Matteo Sesia
Chiara Sabatti
Emmanuel J Candès

title: Gene hunting with knockoffs for hidden markov models

venue: arXiv preprint arXiv:1706.04677,

authors:
Suzanne M Shoff
Polly A Newcomb

title: Diabetes, body size, and risk of endometrial cancer

venue: American journal of epidemiology,

authors:
Don D Sin
SF Paul Man

title: Chronic obstructive pulmonary disease: a novel risk factor for cardiovascular disease

venue: Canadian journal of physiology and pharmacology,

authors:
James R Sowers
Melvin A Lester

title: Diabetes and cardiovascular disease

venue: Diabetes care,

authors:
Lars C Stene
Per Nafstad

title: Relation between occurrence of type 1 diabetes and asthma

venue: The Lancet,

authors:
Jiliang Tang
Salem Alelyani
Huan Liu

title: Feature selection for classification: A review

venue: Data classification: Algorithms and applications, pp

title: Regression shrinkage and selection via the lasso

venue: Journal of the Royal Statistical Society. Series B (Methodological), pp

authors:
Ramachandran S Vasan
Martin G Larson
Eric P Leip
Jane C Evans
Christopher J O’donnell
William B Kannel
Daniel Levy

title: Impact of high-normal blood pressure on the risk of cardiovascular disease

venue: New England journal of medicine,

authors:
Alexandros N Vgontzas
Duanping Liao
Slobodanka Pejovic
Susan Calhoun
Maria Karataraki
Edward O Bixler

title: Insomnia with objective short sleep duration is associated with type 2 diabetes: a population-based study

authors:
Sandeep Vijan
Rodney A Hayward

title: Pharmacologic lipid-lowering therapy in type 2 diabetes mellitus: background paper for the american college of physicians

venue: Annals of Internal Medicine,

authors:
SG Wannamethee
AG Shaper
IJ Perry
KGMM Alberti

title: Alcohol consumption and the incidence of type ii diabetes

venue: Journal of Epidemiology & Community Health,

authors:
Marvin N Wright
Theresa Dankowski
Andreas Ziegler

title: Unbiased split variable selection for random survival forests using maximally selected rank statistics

venue: Statistics in medicine,

heading: 1 INTRODUCTION

text:
Feature selection is a pervasive problem. Often the goal is to discover features that are relevant to a particular outcome, either for the sake of discovery itself or to aid in prediction [16; 25]. When the focus is on discovery, feature selection methods typically focus on trying to control either the Family-Wise Error Rate (FWER) or the False Discovery Rate (FDR). The FWER measures the probability of making a single false discovery (a Type I error) among the selected features (i.e. selecting one which is not relevant), whereas the FDR measures the proportion of false discoveries made (i.e. the proportion of selected features which are false). Controlling FWER, however, leads to reduced power (i.e. selecting fewer relevant variables) since it controls the probability of making any false discovery, whereas FDR tries to control the proportion of false discoveries.
Controlling the FDR is important [5; 6; 3]. Often, data-driven feature selection will be used to select a set of candidate features for further investigation. When further investigation is expensive (for example when further investigation would involve conducting new experiments and collecting more data), a method that cannot control the FDR may result in a large amount of wasted resources, with no guarantee that anything meaningful will be discovered. On the other hand, being able to control the FDR at, say, 10% ensures that at most, 10% of the spent resources are wasted, and 90% are in fact spent on discovering positive, useful results. It should be noted, however, that estimating
the FDR of a method empirically is hard in practice, since we do not have access to the ground truth relevance. As such, a theoretical analysis of the method and its (potential) FDR-controlling properties must be carried out, which does not exist for many existing feature selection methods.
[3] is the seminal paper on the knockoff framework, which is an innovative FDR-controlling feature selection method. Knockoffs are features that are generated to “look like” the real features but be conditionally independent of the label given the real features. Feature statistics (such as the coefficients of a LASSO [32]) are compared between the real features and their knockoffs and a selection is made when this difference is sufficiently large. Performing the selection in this way allows for an estimate of the FDR to be obtained and the selection threshold can be adjusted to control the FDR at the selected level. In the original paper, the relationship between the label and the features is constrained to be of a very specific form; in [7], they remove this constraint and instead provide a theoretical analysis that shifts the burden of knowledge onto knowing the underlying feature distribution. Unfortunately, while the theoretical results hold for any feature distribution, they rely on being able to generate valid knockoffs, for which [7] only provide a method for generating knockoffs when the distribution is a (known) multivariate Gaussian distribution. In this paper, we modify the Generative Adversarial Networks (GAN) [11] framework to address this problem, allowing us to generate knockoffs for any distribution (and without any prior knowledge of it). GANs have been shown to be a powerful method for learning to generate complex distributions [24; 20; 2].
Our main contribution is in modifying the discriminator used in the GAN framework in such a way that the generator learns to generate knockoffs satisfying the necessary swap condition [7] which requires that when a feature and its knockoff are swapped, the joint distribution remains unchanged. In addition, we propose a method for maximizing the power of our model using Mutual Information Neural Estimation (MINE) [4] and investigate a regularization method to improve the stability of training. Our model consists of four networks: (1) a generator network that takes as input noise and the real features, and outputs a set of candidate knockoff features; (2) a discriminator network taking as input “swapped” feature-knockoff features that attempts to determine which variables have been swapped; (3) a Wasserstein GAN discriminator that we use as a regularization term; and (4) a MINE network that estimates the mutual information between each feature-knockoff pair allowing us to maximize the power of the knockoff procedure.

heading: 2 RELATED WORKS

text:
Feature selection is a well-studied problem with a wealth of related works ([12; 31; 17; 22] provide a summary of a lot of existing literature); however, most methods do not attempt to control the FDR. The most common feature selection method for FDR control is the Benjamini-Hochberg (BHq) procedure and its variants [5; 6], which relies on obtaining valid marginal p-values for each selection.
Knockoffs are an active area of research [9; 18; 10]. The notion of a knockoff was first introduced in [3] with the theory there requiring that the relationship between the features and the label be of a specific form. In [7], they build on the knockoff framework, removing this requirement but instead shifting the requirement to one of knowing the distribution of the features. As noted in the introduction, the theory in [7] holds independent of the distribution of the features - relying only on being able to generate valid knockoffs (which exist for any distribution of features). However, they only propose a method for generating knockoffs when the distribution of features is jointly Gaussian. While they do propose a method for generating approximate knockoffs in the non-Gaussian setting (by simply approximating the features as Gaussian), the guarantees on FDR control do not hold for their approximate knockoffs. In [26] and [10], they add to the class of constructible knockoffs, describing methods for constructing knockoffs for Markov Chains, Hidden Markov Models and Gaussian Mixture Models. Though once again, knowledge of the full distribution is still necessary for their construction.
In this paper we use a framework motivated by GANs [11] to learn to generate knockoffs without any assumptions on the distribution of the features. To do this, we modify the discriminator so that rather than trying to determine whether a sample is real or fake, it attempts to identify which components have been “swapped”. In [38], an unconventional discriminator is used that performs component-wise discrimination for the purpose of imputation. While the problem addressed in that paper is different to the one here, the key idea relies on a similar modification to the discriminator to be able to appropriately guide the generator.
In order to maximize the power of our variable selection mechanism, it will be desirable that the feature-knockoff pairs are ”as independent as possible” (this is discussed in [7]). In order to achieve this we will investigate the use of a promising recent paper, MINE [4]. MINE proposes a neural architecture and training procedure capable of estimating the mutual information between two random variables. As the mutual information between two random variables is zero only when they are independent, we will use this as a measure of independence and attempt to minimize it during the training of our modified GAN.

heading: 3 BACKGROUND

text:
In this section we introduce our notation and define knockoffs as in [7]. Let us denote the feature space by X and the label space by Y . Let the dimension of X be d. Suppose that X = (X1, ..., Xd) and Y are random variables over X and Y . As in [7], we will work with the notion of a null set. Definition 1. A variable Xj is said to be ”null” if and only if Y is independent of Xj conditional on {Xi : i 6= j}. We defineH0 to be the set of all null variables.
Our goal will be to discover as many relevant features as possible while controlling the FDR. For a given (potentially random) selection procedure that selects Ŝ ⊂ {1, ..., d}, we define the FDR to be
FDR = E [ |Ŝ ∩ H0| |Ŝ| ] .
Note that this agrees with the usual notion of FDR (i.e. when defined in terms of the Markov blanket) under mild assumptions (for a more thorough discussion see [7]).

heading: 3.1 KNOCKOFFS

text:
Definition 2. A knockoff [7] for X is a random variable X̃ ∈ X satisfying the following two properties:
(X, X̃) d. = (X, X̃)swap(S) (1)
X̃ ⊥⊥ Y |X (2) for all S ⊂ {1, ..., d} where (·, ·)swap(S) denotes the vector obtained by swapping the ith component with the (i+ d)th component for each i ∈ S and d.= is equality in distribution.
In order to use knockoffs for feature selection, we must define an appropriate feature statistic, Wj , that depends on X, X̃ and Y , i.e. Wj = wj((X, X̃), Y ) for some function wj . This function wj must satisfy the following flip-sign property:
wj((X, X̃)swap(S), Y ) = { wj((X, X̃), Y ) if j /∈ S −wj((X, X̃), Y ) if j ∈ S.
(3)
One of the procedures used in [7] to construct these statistics is to perform LASSO, treating the augmented feature-knockoffs as the features on which to regress. This gives LASSO coefficients b1, ..., b2d, and the statistic Wj is set to be the LASSO Coefficient Difference given by
Wj = |bj | − |bj+d|.
Note that the FDR control guarantees hold independently of the choice of statistic, but a poorly chosen statistic can significantly impact the power of the test. In particular, using the LASSO Coefficient Difference in non-linear settings can yield few discoveries. The focus of this paper, however, is on generating the knockoffs, not on the statistic used on top of the generated knockoffs and so in our synthetic experiments, we use a linear model for Y to be able to draw fair comparisons between our model and [7]. In the real world data experiment, we use a statistic based on Random Forests for both methods [37].
The following result from [7] depends only on having obtained knockoffs that satisfy Definition 2 and feature statistics satisfying (3) (and in particular do not depend specifically on using LASSO to obtain the statistics).
Theorem 1. Let q ∈ [0, 1]. Given test statistics, W1, ...,Wd, satisfying (3), let
τ = min { t > 0 :
1 + |{j : Wj ≤ −t}| |{j : Wj ≥ t}|
≤ q } .
Then the procedure selecting the variables
Ŝ = {j : Wj ≥ τ} controls the FDR at level q, i.e.
E [ |Ŝ ∩ H0| |Ŝ| ∨ 1 ] ≤ q.

heading: 4 KNOCKOFFGAN

text: It should be noted that in order to satisfy equation (2), it simply needs to be the case that the knockoffs are constructed without looking at the label, Y . In order to satisfy equation (1) we use a modified GAN framework, which gives us the flexibility to learn to generate knockoffs without any assumptions on the distribution of the original features.

heading: 4.1 GENERATOR

text: The generator, G, will be a function G(·, ·;φ) : X × [0, 1]c → X , parametrized by φ that takes a realization x of X and random noise, z ∼ U([0, 1]c), as inputs and outputs knockoff features x̃. We define X̃ := G(X, z). We model G as a fully connected neural network with weights φ.

heading: 4.2 DISCRIMINATOR

text:
The main innovation of our paper is in defining the discriminator. Equation (1) imposes a condition on the joint distribution of (X, X̃) and as such we must define a discriminator with a loss that is (not necessarily uniquely) minimized only for joint distributions satisfying this condition. To that end, the discriminator, D, will be a function D(·;ψ) : X × X → [0, 1]d that takes as input a swapped sample-knockoff pair (x, x̃)swap(S) and outputs a vector in [0, 1]d with the ith component of D((x, x̃)swap(S)) corresponding to the probability that i ∈ S. The discriminator is attempting to detect which variables have been swapped and, intuitively, when the discriminator is unable to determine this, the swapped and unswapped joint distributions must be the same.
The loss we use to train the discriminator is the multi-output cross-entropy loss given by LD = ∑
S∈{0,1}d EX∼PX [EX̃∼P̃X(X)[S·log(D((X, X̃)swap(S)))+(1−S)·log(1−D((X, X̃)swap(S)))]]
(4)
where · is the standard dot, 1 = (1, ..., 1), S = (S1, ..., Sd) with Si = I(i ∈ S) (I is the indicator function) and log is taken element-wise. The following theorem is our main theoretical result, which states that the training regime employed by KnockoffGAN will result in a procedure that generates valid knockoffs. Theorem 2. Equation (4) is maximized (with respect to G) if and only if equation (1) is satisfied by G.
Proof. The proof, alongside supporting theoretical results, can be found in the Appendix.
In practice, the sum is too computationally expensive (O(2d)) to calculate and so we perform stochastic gradient descent using minibatches with S sampled uniformly from {0, 1}d, independently for each sample in the minibatch.
We also found that training with respect to the full loss resulted in a poor performance, particularly when d is large. We found that the discriminator struggled to learn anything when asked to find the full swap vector, and the poor discriminator resulted in a poorly trained generator. In order to overcome this, we introduce a hint vector - first introduced in [38] - that we use to reveal partial information to the discriminator about the swap vector. We do this by using the hint to reveal some, but not all, of the components of S to the discriminator. In doing so, we reduce the burden of the discriminator from needing to determine the entire swap vector to only needing to determine some of the swap vector.
Formally, the hint, H, will be a random variable depending on S, that we pass to the discriminator, alongside (X, X̃)swap(S). We use the hint to control the amount of information we pass to D about S before asking D to predict S. In practice, our hinting mechanism involves sampling a multivariate Bernoulli random variable, B from i.i.d. components, which each take value 1 with probability 0.9. The hint is then constructed by setting Hi = Si if Bi = 1 and Hi = 0.5 if Bi = 0. The discriminator is therefore being asked only to predict the values of S for which Bi = 0; the others, D is able to directly infer from Hi. In order to avoid overfitting to the hint, it becomes necessary to remove these terms from our loss. Our loss now becomes
LD = ∑
S∈{0,1}d EX∼PX
[ EX̃∼P̃X(X) [ EH∼PH|S [ (S (1−B)) · log(D((X, X̃)swap(S),H)) (5)
+ ((1− S) (1−B)) · log(1−D((X, X̃)swap(S),H)) ]]]
where denotes element-wise multiplication and the expectation over B is implicit in the expectation over H.

heading: 4.3 STABILITY

text:
We found that adding a regularization term in the form of a Wasserstein GAN discriminator (with Gaussian Process (GP) regularization) [2], f , aided performance. We note that when equation (1) holds, we must have that X d.= X̃ and so the addition of this regularizing term does not affect the optimal solution to our loss. We model f as a fully connect neural network with weights ν. The loss is given by
Lf = E [ f(X)− f(X̃)− η(||∇X̂f(X̂)||2 − 1) 2 ]
where ∼ U [0, 1], X̂ = X + (1 − )X̃ and η is a hyper-parameter (set to 10 in practice). Note that we have rewritten the loss to be the negative of the one given in [2], allowing us to write our overall objective as a minimax problem. This loss is added to the generator loss as an additional regularization term.

heading: 4.4 MAXIMIZING POWER

text:
As noted in [7], it is intuitive that in order to maximize the power of the knockoff selection procedure, we wish to make Xj and X̃j as ”independent” as possible. Doing so ensures that as little as possible of the dependence between the real feature and the label is present between the knockoff and the label; this allows us to determine whether or not the relationship between the feature and label is only through the feature’s correlation with other features, or is in fact a true signal.
In order to achieve maximal independence, we look to minimize the mutual information between each feature and its knockoff. Actually computing the true mutual information requires access to both the joint density of the feature-knockoff pairs and to the marginal densities of each feature and knockoff, which we do not have.
Instead, we look to a promising recent work, Mutual Information Neural Estimation (MINE [4]), that provides a framework for estimating the mutual information using neural networks. To do so, they estimate the mutual information between random variables U and V by performing gradient ascent on the following objective:
sup θ∈Θ EP(n)UV [Tθ]− log(EP(n)U ⊗P(n)V [e Tθ ])
where PUV denotes the joint measure of (U, V ) with PU = ∫ V dPUV and PV = ∫ U dPUV denoting the marginal measures. (n) denotes the empircal distribution associated with n i.i.d. samples.
Using MINE we approximate the mutual information between each pairXj and X̃j by using d neural networks1, T 1, ..., T d, each parametrized by θ1, ..., θd, that we refer to collectively as the power network, and will write P to denote the collection of networks T 1, ..., T d. The mutual information is added using a trade-off parameter λ to the loss for G. Formally, define LP by
LP = d∑ j=1 ( n∑ i=1 (T jθj (x (i) j , x̃ (i) j ))− log( n∑ i=1 exp(T jθj (x (κ(i)) j , x̃ (i) j ))) )
where κ is a random permutation of [n]2 and (i) denotes the ith sample - noting that dependence on G is through X̃.

heading: 4.5 FINAL OBJECTIVE

text:
The resulting minimax game played by G, D, W and P is given by
min G ( max D (LD) + λmax P (LP ) + µmax f (Lf ) )
where λ, µ are hyper-parameters (set to 1 in the experiments section).
We train each of G, D, W and P iteratively. Pseudo-code of our knockoff construction algorithm can be found in Algorithm 1 and a visual representation of our architecture in Fig. 1.
After generating knockoffs, feature statistics are computed according to some procedure (in the synthetic experiments we use LASSO and in the real data experiment we use a Random Forestbased statistic [37]). Features are then selected based on these statistics according to Theorem 1.

heading: 5 EXPERIMENTS

text:
In this section we demonstrate the capability of our method to match the results of [7] in settings where their model is correctly specified (i.e. when the underlying feature distribution is Gaussian) and then go on to show, in settings where the underlying feature distribution is non-Gaussian, that our method is able to outperform their Gaussian approximation. We compare to two versions of the BHq method [5; 6] to provide a baseline.
We also perform a qualitative analysis of KnockoffGAN on a real-world dataset. We compare features found by KnockoffGAN to PubMed literature and show that KnockoffGAN discovers several meaningful features for 2 different disease outcomes.
1In practice we use a single neural network with diagonalized weights to parallelize these networks. 2In our pseudo-code, we write U(Sn) to denote the uniform distribution over the set of all permutations of
[n] = {1, ..., n}.
Algorithm 1 Pseudo-code of KnockoffGAN 1: Inputs: mini-batch size nmb > 0, Initialize parameters φ, ψ, ν, θ1, ..., θd 2: while Converge do 3: Discriminator Update 4: Sample x1, ...,xnmb from D, z1, ..., znmb ∼ PZ 5: Sample S1, ...,Snmb
i.i.d∼ U({0, 1}d), b1, ...,bnmb ∼ Ber(0.9) 6: for i = 1, ..., nmb do 7: x̃i ← G(xi, zi;φ) 8: hi = Si bi + 0.5(1− bi) 9: Update D by ascending its stochastic gradient
∇ψ nmb∑ i=1 [ (Si (1− bi)) · log(D((xi, x̃i)swap(S)),hi)
+ ((1− Si) (1− bi)) · log(1−D((xi, x̃i)swap(S),hi)) ]
10: MINE Update 11: Sample x1, ...,xnmb from D, z1, ..., znmb ∼ PZ , κ ∼ U(Snmb) 12: for i = 1, ..., nmb do 13: x̃i ← G(xi, zi;φ) 14: for j = 1, ..., d do 15: Update Tj by ascending its stochastic gradient
∇θj (∑nmb i=1 T j θj (x (i) j , x̃ (i) j ) ) − log (∑nmb i=1 exp(T j θj (x (i) j , x̃ (κ(i)) j )) ) 16: WGAN-GP Update 17: Sample x1, ...,xnmb from D, z1, ..., znmb ∼ PZ 18: for i = 1, ..., nmb do 19: Sample ∼ U [0, 1] 20: x̃i ← G(xi, zi;φ) 21: x̂i = xi + (1− )x̃i 22: Update f by ascending its stochastic gradient
∇ν ∑nmb i=1 [ f(xi)− f(x̃i)− η(||∇x̂if(x̂i)||2 − 1)2 ] 23: Generator Update 24: Sample x1, ...,xnmb from D, z1, ..., znmb ∼ PZ 25: Sample S1, ...,Snmb
i.i.d∼ U({0, 1}d), κ ∼ U(Snmb) 26: for i = 1, ..., nmb do 27: x̃i ← G(xi, zi;φ) 28: Update G by descending its stochastic gradient
∇φ(LD + λLP + µLf )

heading: 5.1 SYNTHETIC DATA EXPERIMENTS

heading: 5.1.1 SIMULATION SETTINGS

text:
Evaluating feature selection methods on real data is difficult as we do not have access to the ground truth. To evaluate KnockoffGAN, we conduct a series of experiments using synthetic data, replicating those carried out in [7] and extending them to more general settings. In each of the following synthetic experiments, we set the feature dimension to be d = 1000 and the number of samples to be n = 3000. For each feature distribution we perform two experiments:
1. Y-Logit: P (Y = 1|X) = exp(m(X))(1+exp(m(X)))
2. Y-Gaussian: Y ∼ N (m(X), 1)
where m(X) = ∑60 i=1 αδiXi with δi ∈ {−1, 1} sampled uniformly and then fixed for each experiment. α controls the strength of the influence that X has on Y , and in the experiments we vary this (as in [7]). Note that for the auto-regressive settings (found in Section 5.1.2 and the Appendix) the relevant variables are sampled uniformly at random from among the 1000 features (rather than being the first 60); in the non-auto-regressive settings this is not necessary.
We report the True Positive Rate (TPR), which is also commonly referred to as the power, defined as
TPR = |Ŝ ∩ S∗| |S∗|
(6)
where S∗ = {1, ..., d} \ H0 is the set of all non-null features. We also report the FDR to verify that the methods do indeed control it at the specified level which we set to be 10%. Note that we are not using FDR as a metric - a lower FDR is not desirable when we set the threshold to 10%. In fact, we want the methods to be as close to 10% as possible (so that they are achieving maximum power). We perform 100 replications of each experiment and report the average TPR and FDR.

heading: 5.1.2 GAUSSIAN SETTINGS

text:
We begin by replicating the setup from [7] in which the underlying feature distribution is Gaussian. In this setting, we do not expect KnockoffGAN to perform better than the original knockoff framework as the original framework assumes a Gaussian distribution. Our goal here is simply to achieve a similar performance, demonstrating that little performance is lost even when the distribution is known to be Gaussian.
In the first experiment that we replicate from [7], the features are set to be auto-regressive (AR(1)) with Gaussian marginal distributions, i.e. Xi = φXi−1 +Zi with Zi being chosen such thatXi
i.i.d.∼ N (0, 1n ). In this experiment we vary φ, which determines the correlation between features, rather than α. We fix α = 3.5 for Y-Gaussian and α = 10 for Y-Logit. The results are reported in Fig. 2.
As in [7], we observe that BHq Marginal, which tests for marginal independence of the feature from Y , suffers from severely increased FDR as we increase the correlation, invalidating the seemingly good TPR. To make the remaining results clearer, we omit BHq marginal from the rest of this section. Aside from this, we see in Fig. 2, that the other methods control the FDR at or very close to the specified 10% threshold. We also see that across the entire range of α, KnockoffGAN achieves a very similar TPR to the original Knockoff framework.
In the second experiment, we set the underlying feature distribution to be i.i.d. Gaussian. We found in this case also that KnockoffGAN was able to control the FDR and achieve a similar TPR to the
original knockoff framework. More details of this experiment and the results for it can be found in the Appendix

heading: 5.1.3 NON-GAUSSIAN SETTINGS

text:
We now move on to the key results for the paper in which the underlying feature distribution is no longer Gaussian. In this setting, we expect to outperform the original Knockoff framework due to the fact that they approximate the distribution as Gaussian. In particular, when this approximation is poor, the knockoffs are no longer valid and as such no FDR guarantees can be given. On the other hand, KnockoffGAN does not place any requirements on the distribution of the features and as such is able to generate valid knockoffs.
We performed experiments for several different underlying feature distributions, and found that KnockoffGAN achieved a higher TPR than the original knockoff framework in all cases, while controlling the FDR at the specified level. We give the results for X coming from a 4-Gaussian mixture model in Fig. 3 - results for Uniform, Dirichlet, and other (2 and 3) Gaussian mixture models can be found in the Appendix.
To create our 4-mixture model, we set the means (m1,m2,m3,m4) of the 4 Gaussians to be:
• m1i = 1 for i = 1 to 100 and 0 for i = 101 to 1000, • m2i = 1 for i = 1 to 50 and -1 for i = 51 to 100 and 0 for i = 101 to 1000, • m3i = −1 for i = 1 to 50 and 1 for i = 51 to 100 and 0 for i = 101 to 1000, • m4i = −1 for i = 1 to 100 and 0 for i = 101 to 1000.
We scale the variance of each Gaussian to be such that the overall variance of each feature is 1n .
We see in Fig. 3 that KnockoffGAN consistently outperforms the original knockoff framework, achieving a higher TPR across the entire range of α while consistently controlling the FDR at 10%. In fact, in the Y -Gaussian setting we see that the original knockoff framework performs almost identically to BHq Maximum Likelihood.

heading: 5.1.4 IMPACT OF WGAN REGULARIZATION

text:
We conclude the synthetic experiments by demonstrating the effect of the WGAN regularizer3. We conduct this experiment using an auto-regressive model with U(− √ 3/n, √ 3/n) marginal distributions. We fix α = 5 for Y-Logit and α = 2.5 for Y-Gauss.
3The WGAN regularizer was included in all previous experiments.
As we see in Fig. 4, the WGAN regularizer has a significant effect on the results, with the improvement in some places being almost as much as KnockoffGAN without WGAN makes over the original knockoff framework. As noted in Section 4.3, there is no trade-off introduced by the inclusion of this regularizer; the optimal solution to the loss is unchanged and therefore this regularization is ”free” in terms of FDR control, but as demonstrated improves TPR performance.

heading: 5.2 REAL DATA EXPERIMENT

text:
In this section we use a biobank dataset (with 387 dimensions) to qualitatively analyze the performance of KnockoffGAN. We use KnockoffGAN to select features for two different outcomes: (1) Cardiovascular Disease (CVD) and (2) Diabetes and then use PubMed literature to asses the validity of the selected features.
We found that the original knockoff framework was unable to select even the most well-known features (such as Age and Sex for CVD [15]), even when the FDR threshold was increased to 20%. Therefore, there are no relevant features to report for the original knockoff framework and so Table 1 contains only the features selected by KnockoffGAN that were deemed relevant by PubMed literature. For this the FDR threshold was set to 5% so that the number of discoveries was manageable for cross-reference with PubMed.
As we see in Table 1, KnockoffGAN discovers 9 relevant features for CVD and 8 relevant features for diabetes. Some of the relevant features, such as Age, Sex and Long-standing illness for CVD are
well-known relevant features. The remaining features are all supported by the literature in PubMed. While this is a qualitative result (it relies on using PubMed as the ground truth), we do believe this demonstrates that KnockoffGAN is a significant improvement over the original knockoff generation procedure.

heading: 6 CONCLUSION

text:
In this paper we built on the knockoff framework introduced in [3] by developing a novel GAN framework, KnockoffGAN, capable of generating knockoffs with no assumptions on the underlying data. We demonstrated through a series of experiments on a range of synthetic datasets and on a real world dataset that our method improves on the performance of the original knockoff framework.
While we feel this is a significant step towards being able to generate knockoffs for any data, there is still more work to be done. In particular, generalizing this method to time-series data would be non-trivial, and would be an interesting avenue for further investigation.

heading: ACKNOWLEDGEMENT

text: The authors would like to thank the reviewers for their helpful comments. The research presented in this paper was supported by the Office of Naval Research (ONR) and the NSF (Grant number: ECCS1462245, ECCS1533983, and ECCS1407712).

heading: APPENDIX

heading: THEORETICAL RESULTS

text:
In order to prove Theorem 2, we use similar techniques to those used in the original GAN paper [11]. In what follows, we analyze the minimax game defined by:
min G max D ∑ S∈{0,1}d EX∼PX [EX̃∼P̃X(X)[S·log(D((X, X̃)swap(S)))+(1−S)·log(1−D((X, X̃)swap(S)))]] (7) where we have used the version of LD given by equation (4) in the main manuscript (i.e. without hinting). The theoretical results that follow are proven only for this version of the loss, though we do believe that the theorem holds more generally for the hinting version of the loss - this is backed up by our empirical results demonstrating strict FDR control while using the hint mechanism. After proving that the optimal solution to this game does indeed provide us with valid knockoffs, we will then show that the additional term Lf does not change the optimal solution. Let p be the density of (X, X̃).
We begin by stating a lemma, that follows from a similar proof to Proposition 1 in [11].
Lemma 1. Let (x, x̃) ∈ X × X . Then for a fixed generator, G, the ith component of the optimal discriminator, D∗((x, x̃)) is given by
D∗((x, x̃))i = p((x, x̃)swap({i}))
p((x, x̃)swap({i})) + p((x, x̃)) (8)
for each i ∈ {1, ..., d}.
Proof. The proof of this involves some basic integral manipulation to get that the objective in (7) can be rewritten as
d∑ i=1 ∫ X×X logD((x, x̃))ip((x, x̃)swap({i})) + log(1−D((x, x̃))i)p((x, x̃))dx.
We then observe that y 7→ a log y + b log(1 − y) achieves its maximum in [0, 1] at aa+b and so the objective is maximized (with respect to D, for fixed G) when
D∗((x, x̃))i = p((x, x̃)swap({i}))
p((x, x̃)swap({i})) + p((x, x̃))
for each i ∈ {1, ..., d}.
With this lemma, we are now able to prove our key result.
Theorem 3. Equation (7) is maximized (with respect to G) if and only if equation (1) (in the main paper) is satisfied by G.
Proof. We begin by rewriting our loss, substituting in D∗, to give us the following loss for G:
LG = ∑
S⊂{1,...,d} EX,X̃ (∑ i∈S log p((x, x̃)swap(S\i)) p((x, x̃)swap(S\i)) + p((x, x̃)swap(S))
+ ∑ i/∈S log p((x, x̃)swap(S)) p((x, x̃)swap(S∪i)) + p((x, x̃)swap(S)) ) where we note that
((x, x̃)swap(S))swap({i}) = { (x, x̃)swap(S\i) if i ∈ S (x, x̃)swap(S∪i) if i /∈ S.
Then by inspecting each term in the sum, we see that each term is a KL-divergence term that is minimized only when p((x, x̃)swap({S\i})) = p((x, x̃)swap(S)) (9) and
p((x, x̃)swap({S∪i})) = p((x, x̃)swap(S))
for every i ∈ {1, ..., d}, every S ⊂ {1, ..., d} and each (x, x̃) ∈ X × X . By iteratively applying equation (9), we get that
p((x, x̃)swap(S)) = p((x, x̃)swap(S\1)) = ... = p((x, x̃)swap(S\{1,...,d−1}))
= p((x, x̃)swap(S\{1,...,d})) = p((x, x̃)
proving the theorem.
Lemma 2. The addition of the term Lf to our loss, does not affect the optimal solution to it.
Proof. By theorem 2, it suffices to show that any distribution satisfying equation (1) also minimizes maxf Lf . But we note that, as shown in [2], maxf Lf (or rather supf Lf ) is the Wasserstein distance between X and X̃, which is 0 (and minimal) when X d.= X̃. It therefore suffices to show that equation (1) implies X d.= X̃.
Let S = {1, ..., d}. Then if (X, X̃) satisfy equation (1), we get that (X, X̃) d.= (X̃,X). Since the joint distributions are equal, it follows that the marginal distributions are equal and so by projecting onto the first d variables, we get that X d.= X̃.

heading: MINE

text:
We state the key theory used by MINE to estimate the mutual information. For full details see the original paper, [4].
The mutual information is defined as
I(U ;V ) = ∫ U×V log dPUV dPU ⊗ dPV dPUV
where U and V are random variables over some spaces U and V , respectively with joint measure PUV and marginal measures PU = ∫ V dPUV and PV = ∫ U dPUV , respectively.
The mutual information can also be characterized by the Kullback-Leibler divergence, DKL, as
I(U ;V ) = DKL(PUV ||PU ⊗ PV )
The Donsker-Varadhan representation then gives us for any two probability measures P and Q over a probability space Ω
DKL(P||Q) = sup T :Ω→R EP[T ]− log(EQ[eT ])
where the supremum is taken over all functions T such that the two expectations are finite.
A simple corollary of this is that fixing a classF of functions (such as a parametrized class {Tθ : θ ∈ Θ}) over which the supremum is taken will provide us with a lower bound for the mutual information that approaches the true mutual information as the class becomes sufficiently rich. MINE [4] fix the class to be parametric in this way - given a fixed neural network architecture, they let F = {Tθ : θ ∈ Θ} be the set of all functions parametrized by this network.

heading: IMPLEMENTATION OF KNOCKOFFGAN

text: In the experiments, the depth of the generator, discriminator and WGAN-GP networks is set to 4 and power network is set to 3. The number of hidden nodes in each layer is d/4, d/16 d/4 for the generator, discriminator, and WGAN-GP, respectively. For the power network, we use 2 diagonal matrices for each layer to make two hidden nodes for each feature separately. We use ReLu and tanh as the activation functions for each layer except for the output layer where we use a linear activation function for the generator, power network and WGAN-GP networks and sigmoid activation function for the discriminator network. The number of samples in each mini-batch is 128. KnockoffGAN is implemented in tensorflow.

heading: DETAILS OF BENCHMARKS

text:
We use the following links for the implementations of 3 benchmarks.
• Knockoff: http://web.stanford.edu/group/candes/knockoffs/ software/knockoff/index.html
• BHq Max: http://web.stanford.edu/group/candes/knockoffs/ software/knockoff/tutorial-4-r.html
• BHq Marginal: Modifying the original code of BHq Max in http://web.stanford. edu/group/candes/knockoffs/software/knockoff/tutorial-4-r. html
Except for the knockoff generation step, KnockoffGAN follows the same procedures as the original knockoff framework described at http://web.stanford.edu/group/candes/ knockoffs/software/knockoff/tutorial-2-r.html to select features.

heading: ADDITIONAL EXPERIMENTS

heading: INDEPENDENT GAUSSIANS

text:
In the following experiment, features were taken to be i.i.d. Gaussian, with mean 0 and variance 1n , i.e. X ∼ N (0, 1nIn). The results are reported in Fig. 5.
As we see in Fig. 5, all methods control the FDR at or very close to the specified 10% threshold. We also see that across the entire range of α, KnockoffGAN achieves a very similar TPR to the original knockoff framework.

heading: NON-GAUSSIAN SETTINGS

heading: INDEPENDENT UNIFORM

text:
In this experiment we set the feature distribution to be a Uniform distribution with mean 0 and variance 1n (to be consistent with the Gaussian experiments). Fig. 6 displays the results for each component of X being i.i.d. U(− √ 3/n, √ 3/n). Once again we see that KnockoffGAN consistently outperforms the original knockoff framework, achieving a higher TPR across the entire range of α in both settings.
3/n). TPR is used to
quantify performance and FDR is reported to verify that it is at the specified threshold (10%).

heading: DIRICHLET

text: In this experiment we set the feature distribution to be a Dirichlet(1, ..., 1) distribution - i.e. the uniform distribution over the (d− 1)-simplex. Correlation here exists through the requirement that∑d i=1Xi = 1.

heading: GAUSSIAN MIXTURE MODELS

text:
For the GMM2 model we set the means (m1,m2) of the 2 Gaussians to be:
• m1i = 1 for i = 1 to 100 and 0 for i = 101 to 1000, • m2i = −1 for i = 1 to 100 and 0 for i = 101 to 1000.
For the GMM3 model we set the means (m1,m2,m3) of the 3 Gaussians to be:
• m1i = 1 for i = 1 to 100 and 0 for i = 101 to 1000, • m2i = 1 for i = 1 to 50 and -1 for i = 51 to 100 and 0 for i = 101 to 1000, • m3i = −1 for i = 1 to 100 and 0 for i = 101 to 1000.

heading: HYPER-PARAMETER ANALYSIS

text:
Hyper-parameter selection in the feature selection problem is difficult; hyper-parameter selection cannot be performed using cross-validation as we do not have access to ground truth. The hyperparameters must therefore be fixed a priori. For this we believe that λ = 1 and µ = 1 are perhaps the most canonical choice we could make and thus these were used in the main manuscript. In the following experiments, we investigate the sensitivity of the results to various settings of λ and µ. The results below are in the auto-regressive Uniform setting with Y-Logit and FDR set to 10%.
As can be seen in Table 2 and 3, the performance of KnockoffGAN is not sensitive to the value of λ and µ. The only significant difference can be seen when either λ or µ is set to 0 which represents the exclusion of either the power network or WGAN-discriminator network, respectively, from the model. In particular, the lack of sensitivity to µ aligns with Lemma 2 in which we see that there is not a trade-off between Lf and LD but rather the two can be simultaneously minimised. To further understand the effects of the WGAN network, we report the final values of the other losses (LD and LP ) when µ = 1 and µ = 0 (i.e. with and without the WGAN regularisation). The results are given below in the auto-regressive Uniform setting with Y-Logit and FDR set to 10%.
As can be seen in Table 4, the inclusion of the WGAN network improves the final value of LD, bringing it significantly closer to its optimal value of log(2) ≈ 0.693. On the other hand, the power network loss is increased, however, this trade-off is expected and acceptable - the FDR guarantees rely on the discriminator loss (LD) and not the power network. As we see in Table 3, the TPR does not suffer from this increased loss for the power network.
For our final hyper-parameter evaluation, we investigate the effect of varying the hinting probability, p, which determines the probability with which Bi = 1. We note that this hyper-parameter is used to trade-off between speed of learning and optimality of the learned solution. A low probability makes for fast convergence, but suboptimal convergence whereas a high probability makes for slow convergence (but a more optimal solution). We chose 0.9 to balance this, following the implementation of [38]. To demonstrate this trade-off we vary this hyper-parameter (from 0 to 0.9). The results below are for the auto-regressive Uniform distribution with Y-Logit and FDR set to 10%.

heading: RESULTS WITH FDR THRESHOLD 5%

text: In all of the synthetic experiments above, the FDR threshold is set to 10% (which is the level most thoroughly investigated by [3]). In this final experiment, we set the FDR threshold to 5% (which aligns with our real-world experiment) and verify that KnockoffGAN is capable of controlling the FDR at this level and still outperforms the original knockoff framework. We conduct the experiments on (1) an auto-regressive distribution with Gaussian marginal distributions, (2) an auto-regressive distribution with Uniform marginal distributions, and (3) a 4-mixture Gaussian mixture model.

heading: STATISTICS OF REAL-WORLD BIOBANK DATASET

text: To preserve anonymity of the authors, the full details of this dataset will be given upon acceptance of the paper. In Table 1, we provide the basic statistics of the real-world biobank dataset.