Deep Neural Networks for High Dimension, Low …

1 Deep Neural Networks for high Dimension, Low Sample Size DataBo Liu, Ying Wei, Yu Zhang, Qiang YangHong Kong University of Science and Technology, Hong Kongfbliuab, yweiad, zhangyu, Neural Networks (DNN) have achieved break-throughs in applications with large sample , when facing high dimension, low samplesize (HDLSS) data , such as the phenotype predic-tion problem using genetic data in bioinformatics,DNN suffers from overfitting and high -variancegradients. In this paper, we propose a DNN modeltailored for the HDLSS data , named Deep NeuralPursuit (DNP). DNP selects a subset of high dimen-sional features for the alleviation of overfitting andtakes the average over multiple dropouts to calcu-late gradients with low variance. As the first DNNmethod applied on the HDLSS data , DNP enjoysthe advantages of the high nonlinearity, the robust-ness to high dimensionality, the capability of learn-ing from a small number of samples, the stabilityin feature selection, and the end-to-end training.

2 Wedemonstrate these advantages of DNP via empiricalresults on both synthetic and real-world IntroductionIn bioinformatics, phenotype prediction using genetic vari-ants suffers from the growing challenges of high dimensional-ity and low sample size. Until 2008, biologists had identified15 million genetic variants (single-nucleotide polymorphismsor SNP) for Homo Sapiens. The number of recognized ge-netic variants quadrupled in 2011 and increased to 150 mil-lion in 2016. In contrast, only thousands of samples are avail-able[Consortium, 2015]. This kind of high dimension, lowsample size (HDLSS) data is also vital for scientific discover-ies in other areas such as chemistry, financial engineering, andetc[Fan and Li, 2006]. When processing this kind of data , thesevere overfitting and high -variance gradients are the majorchallenges for the majority of machine learning algorithms[Friedmanet al.]

3 , 2000].Feature selection has been widely regarded as one of themost powerful tools to analyze the HDLSS data . Firstly,selecting the optimal subset of features reduces the sizeof feature space, thereby alleviating the risk of overfit-ting. Secondly, new scientific knowledge can be discov-ered through selecting features. For instance, selecting fea-tures from genotype-cancer datasets helps accumulate theknowledge of cancer-related genetic variants. However, se-lecting the optimal subset of features is known to be NP-hard[Amaldi and Kann, 1998]. Instead, a large body ofcompromised methods for feature selection have been pro-posed. Amongst them, a line of representative methods in-cludes Lasso[Tibshirani, 1996]pursue sparse linear mod-els. Unfortunately, sparse linear models ignore the nonlin-ear input-output relations and interactions among features,both of which have been proved to be important in ex-plaining the missing heritability in phenotype prediction.

4 Al-though some attempts have been made to achieve nonlin-ear feature selection via kernel methods[Liet al., 2005;Yamadaet al., 2014]or gradient boosted tree[Xuet al.,2014], almost all of them address the curse of dimensionalityunder the blessing of large sample deep Neural Networks (DNN) methods light up newscientific discoveries, in particular, to understand biologi-cal processes from genotype to phenotype. Firstly, DNN hasachieved breakthroughs in modeling nonlinearity in wide ap-plications, such as image recognition[Heet al., 2015], ma-chine translation[Bahdanauet al., 2014], and speech recog-nition[Hintonet al., 2012]. The deeper architecture of a DNNis, the more complex relations it can model. Therefore, DNNis qualified to model mutual interactions among DNA, RNA,and proteins which are even more complex than those afore-mentioned applications[Leunget al.]

5 , 2016]. Secondly, thecentral dogma of biology states that the genotype decides thephenotype by following a hierarchical path, , from DNAto RNA and further to protein. DNN is born to mimic suchmulti-layer biological processes. Moreover, DNN has har-vested initial successes in bioinformatics for modeling splic-ing[Xionget al., 2015]and sequence specificity[Alipanahiet al., 2015].In the aforementioned applications, large sample sizegreatly contributes to the state-of-the-art performance ofDNN. Nevertheless, few efforts have been devoted to apply-ing DNN to the HDLSS problem. Estimating a huge amountof parameters for DNN using abundant samples may sufferfrom severe overfitting, not to mention the HDLSS address the challenges of the HDLSS data , we pro-pose an end-to-end DNN model calledDeep Neural Pur-suit(DNP).

6 DNP simultaneously selects features and learnsa classifier to alleviate severe overfitting caused by high di-Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)2287mensionality. By averaging over multiple dropouts, DNP isrobust and stable to high -variance gradients resulting fromthe small sample size. From the perspective of feature selec-tion, the DNP model selects features greedily and incremen-tally, similar to the matching pursuit[Patiet al., 1993]. Moreconcretely, starting from an empty subset of features and abias, the proposed DNP method incrementally selects an in-dividual feature according to the backpropagated , once more features are selected, DNP is updatedusing the backpropagation main contribution of this paper is to tailor the DNNfor the HDLSS setting using feature selection and multipledropouts.

7 On the synthetic and real-world HDLSS datasets,the proposed DNP performs comparably or significantlybetter than sparse linear models and kernel-based/gradient-boosted-tree-based nonlinear feature selection Related WorkIn this section, we discuss feature selection methods that areused to analyze the HDLSS data including linear, nonlinearand incremental the linear model with sparsity-inducing regular-izer is one of the dominating feature selection methods forthe HDLSS data . For instance, Lasso[Tibshirani, 1996]min-imizes the objective function penalized by thel1norm of fea-ture weights, leading to a sparse model. Unfortunately, Lassoconsiders only the linear input-output dependency but ignoresthe nonlinearity and interactions among methods are often used for nonlinear feature selec-tion. Feature Vector Machine (FVM)[Liet al.]

8 , 2005]nonlin-early transforms each feature and label using the kernel func-tion and it learns a sparse model using the new features and la-bels to achieve nonlinear feature selection. HSIC-Lasso[Ya-madaet al., 2014]improves FVM by allowing different ker-nel functions for features and labels. HSIC-Lasso also selectsless redundant features. LAND[Yamadaet al., 2016]furtheraccelerates HSIC-Lasso for data with large sample size viakernel approximation and distributed tree models are also qualified for modeling non-linear input-output relations. As an ensemble of decisiontrees, random forests[Breiman, 2001]select a feature accord-ing to its contribution to the model. One of the selection cri-teria is to measure how much the performance decreases bypermuting the specific feature. Gradient boosted feature se-lection (GBFS)[Xuet al.

9 , 2014]penalizes the usage of fea-tures that are not yet used during the construction of each early stopping of boosting, GBFS obtains an ensemble oftree models with only a subset of features , the aforementioned nonlinear methods, in-cluding FVM, random forests and GBFS, require trainingdata with large sample size. HSIC-Lasso and LAND fits theHDLSS setting. However, compared to the proposed DNPmodel which is end-to-end, HSIC-Lasso and LAND are two-stage algorithms which separate feature selection from DNP method, there exist other greedy and in-cremental feature selection algorithms. For example, SpAM[Ravikumaret al., 2007]sequentially selects an individualGradients Selected feature Candidate feature (3) Input weights (1) (2)Dropout multiple times and take the average to calculate Figure 1: (1) The selected features and the corresponding sub- network .

10 (2) The selection of a single feature. (3) Calculate gradientswith lower variance via multiple in an additive manner, thereby missing important in-teractions among features. For multilayer perceptron withone hidden layer, Grafting method[Perkinset al., 2003]in-crementally adds connections or hidden neurons based ongradient-related heuristics. Similarly, convex Neural network [Bengioet al., 2005]dynamically adds hidden neurons whichmaximize the correlation with negative gradients of the objec-tive function. For one thing, Grafting and convex Neural net-work only consider single hidden layer. For another, Graftingand convex Neural network differ from DNP in the motiva-tion. DNP aims at learning from the HDLSS data . In contrast,Grafting focuses on the acceleration of algorithms and con-vex Neural network focuses on the theoretical understandingof Neural feature selection (DFS)[Liet al.]