RECTIFIED FACTOR NETWORKS FOR BICLUSTERING
Biclustering is evolving into one of the major tools for analyzing large datasets given as matrix of samples times features. Biclustering has several noteworthy applications and has been successfully applied in life sciences and e-commerce for drug design and recommender systems, respectively. FABIA is one of the most successful biclustering methods and is used by companies like Bayer, Janssen, or Zalando. FABIA is a generative model that represents each bicluster by two sparse membership vectors: one for the samples and one for the features. However, FABIA is restricted to about 20 code units because of the high computational complexity of computing the posterior. Furthermore, code units are sometimes insufficiently decorrelated. Sample membership is difficult to determine because vectors do not have exact zero entries and can have both large positive and large negative values. We propose to use the recently introduced unsupervised Deep Learning approach Rectified Factor Networks (RFNs) to overcome the drawbacks of existing biclustering methods. RFNs efficiently construct very sparse, non-linear, highdimensional representations of the input via their posterior means. RFN learning is a generalized alternating minimization algorithm based on the posterior regularization method which enforces non-negative and normalized posterior means. Each code unit represents a bicluster, where samples for which the code unit is active belong to the bicluster and features that have activating weights to the code unit belong to the bicluster. On 400 benchmark datasets with artificially implanted biclusters, RFN significantly outperformed 13 other biclustering competitors including FABIA. In biclustering experiments on three gene expression datasets with known clusters that were determined by separate measurements, RFN biclustering was two times significantly better than the other 13 methods and once on second place. On data of the 1000 Genomes Project, RFN could identify DNA segments which indicate, that interbreeding with other hominins starting already before ancestors of modern humans left Africa.
1 INTRODUCTION
Biclustering is widely-used in statistics (A. Kasim & Talloen, 2016), and recently it also became popular in the machine learning community (O´ Connor & Feizi, 2014; Lee et al., 2015; Kolar et al., 2011), e.g., for analyzing large dyadic data given in matrix form, where one dimension are the samples and the other the features. A matrix entry is a feature value for the according sample. A bicluster is a pair of a sample set and a feature set for which the samples are similar to each other on the features and vice versa. Biclustering simultaneously clusters rows and columns of a matrix. In particular, it clusters row elements that are similar to each other on a subset of column elements. In contrast to standard clustering, the samples of a bicluster are only similar to each other on a subset of features. Furthermore, a sample may belong to different biclusters or to no bicluster at all. Thus, biclusters can overlap in both dimensions. For example, in drug design biclusters are compounds which activate the same gene module and thereby indicate a side effect. In this example different chemical compounds are added to a cell line and the gene expression is measured (Verbist et al., 2015). If multiple pathways are active in a sample, it belongs to different biclusters and may
have different side effects. In e-commerce often matrices of costumers times products are available, where an entry indicates whether a customer bought the product or not. Biclusters are costumers which buy the same subset of products. In a collaboration with the internet retailer Zalando the biclusters revealed outfits which were created by customers which selected certain clothes for a particular outfit.
FABIA (factor analysis for bicluster acquisition, (Hochreiter et al., 2010)) evolved into one of the most successful biclustering methods. A detailed comparison has shown FABIA’s superiority over existing biclustering methods both on simulated data and real-world gene expression data (Hochreiter et al., 2010). In particular FABIA outperformed non-negative matrix factorization with sparseness constraints and state-of-the-art biclustering methods. It has been applied to genomics, where it identified in gene expression data task-relevant biological modules (Xiong et al., 2014). In the large drug design project QSTAR, FABIA was used to extract biclusters from a data matrix that contains bioactivity measurements across compounds (Verbist et al., 2015). Due to its successes, FABIA has become part of the standard microarray data processing pipeline at the pharmaceutical company Janssen Pharmaceuticals. FABIA has been applied to genetics, where it has been used to identify DNA regions that are identical by descent in different individuals. These individuals inherited an IBD region from a common ancestor (Hochreiter, 2013; Povysil & Hochreiter, 2014). FABIA is a generative model that enforces sparse codes (Hochreiter et al., 2010) and, thereby, detects biclusters. Sparseness of code units and parameters is essential for FABIA to find biclusters, since only few samples and few features belong to a bicluster. Each FABIA bicluster is represented by two membership vectors: one for the samples and one for the features. These membership vectors are both sparse since only few samples and only few features belong to the bicluster.
However, FABIA has shortcomings, too. A disadvantage of FABIA is that it is only feasible with about 20 code units (the biclusters) because of the high computational complexity which depends cubically on the number of biclusters, i.e. the code units. If less code units were used, only the large and common input structures would be detected, thereby, occluding the small and rare ones. Another shortcoming of FABIA is that units are insufficiently decorrelated and, therefore, multiple units may encode the same event or part of it. A third shortcoming of FABIA is that the membership vectors do not have exact zero entries, that is the membership is continuous and a threshold have to be determined. This threshold is difficult to adjust. A forth shortcoming is that biclusters can have large positive but also large negative members of samples (that is positive or negative code values). In this case it is not clear whether the positive pattern or the negative pattern has been recognized.
Rectified Factor Networks (RFNs; (Clevert et al., 2015)) RFNs overcome the shortcomings of FABIA. The first shortcoming of only few code units is avoided by extending FABIA to thousands of code units. RFNs introduce rectified units to FABIA’s posterior distribution and, thereby, allow for fast computations on GPUs. They are the first methods which apply rectification to the posterior distribution of factor analysis and matrix factorization, though rectification it is well established in Deep Learning by rectified linear units (ReLUs). RFNs transfer the methods for rectification from the neural network field to latent variable models. Addressing the second shortcoming of FABIA, RFNs achieve decorrelation by increasing the sparsity of the code units using dropout from field of Deep Learning. RFNs also address the third FABIA shortcoming, since the rectified posterior means yield exact zero values. Therefore, memberships to biclusters are readily obtained by values that are not zero. Since RFNs only have non-negative code units, the problem of separating the negative from the positive pattern disappears.
2 IDENTIFYING BICLUSTERS BY RECTIFIED FACTOR NETWORKS
2.1 RECTIFIED FACTOR NETWORKS
We propose to use the recently introduced Rectified Factor Networks (RFNs; (Clevert et al., 2015)) for biclustering to overcome the drawbacks of the FABIA model. The factor analysis model and the construction of a bicluster matrix are depicted in Fig. 1. RFNs efficiently construct very sparse, nonlinear, high-dimensional representations of the input. RFN models identify rare and small events in the input, have a low interference between code units, have a small reconstruction error, and explain the data covariance structure.
RFN learning is a generalized alternating minimization algorithm derived from the posterior regularization method which enforces non-negative and normalized posterior means. These posterior means are the code of the input data. The RFN code can be computed very efficiently. For nonGaussian priors, the computation of the posterior mean of a new input requires either to numerically solve an integral or to iteratively update variational parameters. In contrast, for Gaussian priors the posterior mean is the product between the input and a matrix that is independent of the input. RFNs use a rectified Gaussian posterior, therefore, they have the speed of Gaussian posteriors but lead to sparse codes via rectification. RFNs are implemented on GPUs.
The RFN model is a factor analysis model
v = Wh + ✏ , (1)
which extracts the covariance structure of the data. The prior h ⇠ N (0, I) of the hidden units (factors) h 2 Rl and the noise ✏ ⇠ N (0, ) of visible units (observations) v 2 Rm are independent. The model parameters are the weight (factor loading) matrix W 2 Rm⇥l and the noise covariance matrix 2 Rm⇥m. RFN models are selected via the posterior regularization method (Ganchev et al., 2010). For data {v} = {v1, . . . ,vn}, it maximizes the objective F :
F = 1 n
nX
i=1
log p(vi) 1
n
nX
i=1
DKL(Q(hi | vi) k p(hi | vi)), (2)
where DKL is the Kullback-Leibler distance. Maximizing F achieves two goals simultaneously: (1) extracting desired structures and information from the data as imposed by the generative model and (2) ensuring sparse codes via Q from the set of rectified Gaussians.
For Gaussian posterior distributions, and mean-centered data {v} = {v1, . . . ,vn}, the posterior p(hi | vi) is Gaussian with mean vector (µp)i and covariance matrix ⌃p:
(µp)i = I + W T 1W 1 W T 1 vi , ⌃p = I + W T 1W 1 . (3)
For rectified Gaussian posterior distributions, ⌃p remains as in the Gaussian case, but minimizing the second DKL of Eq. (2) leads to constrained optimization problem (see Clevert et al. (2015))
min
µi
1
n
nX
i=1
(µi (µp)i)T ⌃ 1p (µi (µp)i)
s.t. 8i : µi 0 , 8j : 1
n
nX
i=1
µ2ij = 1 , (4)
where “ ” is component-wise. In the E-step of the generalized alternating minimization algorithm (Ganchev et al., 2010), which is used for RFN model selection, we only perform a step of the gradient projection algorithm (Bertsekas, 1976; Kelley, 1999), in particular a step of the projected Newton method for solving Eq. (4) (Clevert et al., 2015). Therefore, RFN model selection is extremely efficient but still guarantees the correct solution.
2.2 RFN BICLUSTERING
For a RFN model, each code unit represents a bicluster, where samples, for which the code unit is active, belong to the bicluster. On the other hand features that activates the code unit belong to the bicluster, too. The vector of activations of a unit across all samples is the sample membership vector. The weight vector which activates the unit is the feature membership vector. The un-constraint posterior mean vector is computed by multiplying the input with a matrix according to Eq. (3). The constraint posterior of a code unit is obtained by multiplying the input by a vector and subsequently rectifying and normalizing the code unit (Clevert et al., 2015).
To keep feature membership vector sparse, we introduce a Laplace prior on the parameters. Therefore only few features contribute to activating a code unit, that is, only few features belong to a bicluster. Sparse weights Wi are achieved by a component-wise independent Laplace prior for the weights:
p(Wi) = ⇣
1p 2
⌘n nY
k=1
e p 2 |Wki| (5)
The weight update for RFN (Laplace prior on the weights) is
W = W + ⌘ U S 1 W
↵ sign(W ) . (6)
Whereby the sparseness of the weight matrix can be controlled by the hyper-parameter ↵ and U and S are defined as U = 1n Pn i=1 viµ T i and S = 1 n Pn i=1 µiµ T i +⌃, respectively. In order to enforce more sparseness of the sample membership vectors, we introduce dropout of code units. Dropout means that during training some code units are set to zero at the same time as they get rectified. Dropout avoids co-adaptation of code units and reduces correlation of code units — a problem of FABIA which is solved.
RFN biclustering does not require a threshold for determining sample memberships to a bicluster since rectification sets code units to zero. Further crosstalk between biclusters via mixing up negative and positive memberships is avoided, therefore spurious biclusters do less often appear.
3 EXPERIMENTS
In this section, we will present numerical results on multiple synthetic and real data sets to verify the performance of our RFN biclustering algorithm, and compare it with various other biclustering methods.
3.1 METHODS COMPARED
To assess the performance of rectified factor networks (RFNs) as unsupervised biclustering methods, we compare the following 14 biclustering methods:
(1) RFN: rectified factor networks (Clevert et al., 2015), (2) FABIA: factor analysis with Laplace prior on the hidden units (Hochreiter et al., 2010; Hochreiter, 2013), (3) FABIAS: factor analysis with sparseness projection (Hochreiter et al., 2010), (4) MFSC: matrix factorization with sparseness constraints (Hoyer, 2004), (5) plaid: plaid model (Lazzeroni & Owen, 2002; T. Chekouo & Raffelsberger, 2015), (6) ISA: iterative signature algorithm (Ihmels et al., 2004), (7) OPSM: orderpreserving sub-matrices (Ben-Dor et al., 2003), (8) SAMBA: statistical-algorithmic method for bicluster analysis (Tanay et al., 2002), (9) xMOTIF: conserved motifs (Murali & Kasif, 2003), (10) Bimax: divide-and-conquer algorithm (Prelic et al., 2006), (11) CC: Cheng-Church -biclusters
(Cheng & Church, 2000), (12) plaid t: improved plaid model (Turner et al., 2003), (13) FLOC: flexible overlapped biclustering, a generalization of CC (Yang et al., 2005), and (14) spec: spectral biclustering (Kluger et al., 2003).
For a fair comparison, the parameters of the methods were optimized on auxiliary toy data sets. If more than one setting was close to the optimum, all near optimal parameter settings were tested. In the following, these variants are denoted as method variant (e.g. plaid ss). For RFN we used the following parameter setting: 13 hidden units, a dropout rate of 0.1, 500 iterations with a learning rate of 0.1, and set the parameter ↵ (controlling the sparseness on the weights) to 0.01.
3.2 SIMULATED DATA SETS WITH KNOWN BICLUSTERS
In the following subsections, we describe the data generation process and results for synthetically generated data according to either a multiplicative or additive model structure.
3.2.1 DATA WITH MULTIPLICATIVE BICLUSTERS
We assumed n = 1000 genes and l = 100 samples and implanted p = 10 multiplicative biclusters. The bicluster datasets with p biclusters are generated by following model:
X = pX
i=1
i z T i + ⌥ , (7)
where ⌥ 2 Rn⇥l is additive noise; i 2 Rn and zi 2 Rl are the bicluster membership vectors for the i-th bicluster. The i’s are generated by (i) randomly choosing the number N i of genes in bicluster i from {10, . . . , 210}, (ii) choosing N i genes randomly from {1, . . . , 1000}, (iii) setting i components not in bicluster i to N (0, 0.22) random values, and (iv) setting i components that are in bicluster i to N (±3, 1) random values, where the sign is chosen randomly for each gene. The zi’s are generated by (i) randomly choosing the number Nzi of samples in bicluster i from {5, . . . , 25}, (ii) choosing Nzi samples randomly from {1, . . . , 100}, (iii) setting zi components not in bicluster i to N (0, 0.22) random values, and (iv) setting zi components that are in bicluster i to N (2, 1) random values. Finally, we draw the ⌥ entries (additive noise on all entries) according to N (0, 32) and compute the data X according to Eq. (7). Using these settings, noisy biclusters of random sizes between 10⇥5 and 210⇥25 (genes⇥samples) are generated. In all experiments, rows (genes) were standardized to mean 0 and variance 1.
3.2.2 DATA WITH ADDITIVE BICLUSTERS
In this experiment we generated biclustering data where biclusters stem from an additive two-way ANOVA model:
X = pX
i=1
✓i ( i zTi ) + ⌥ , ✓ikj = µi + ↵ik + ij , (8)
where is the element-wise product of matrices and both i and zi are binary indicator vectors which indicate the rows and columns belonging to bicluster i. The i-th bicluster is described by an ANOVA model with mean µi, k-th row effect ↵ik (first factor of the ANOVA model), and jth column effect ij (second factor of the ANOVA model). The ANOVA model does not have interaction effects. While the ANOVA model is described for the whole data matrix, only the effects on rows and columns belonging to the bicluster are used in data generation. Noise and bicluster sizes are generated as in previous Subsection 3.2.1.
Data was generated for three different signal-to-noise ratios which are determined by distribution from which µi is chosen: A1 (low signal) N (0, 22), A2 (moderate signal) N (±2, 0.52), and A3 (high signal) N (±4, 0.52), where the sign of the mean is randomly chosen. The row effects ↵ki are chosen from N (0.5, 0.22) and the column effects ij are chosen from N (1, 0.52).
3.2.3 RESULTS ON SIMULATED DATA SETS
For method evaluation, we use the previously introduced biclustering consensus score for two sets of biclusters (Hochreiter et al., 2010), which is computed as follows:
Step (3) penalizes different numbers of biclusters in the sets. The highest consensus score is 1 and only obtained for identical sets of biclusters.
Table 1 shows the biclustering results for these data sets. RFN significantly outperformed all other methods (t-test and McNemar test of correct elements in biclusters).
3.3 GENE EXPRESSION DATA SETS
In this experiment, we test the biclustering methods on gene expression data sets, where the biclusters are gene modules. The genes that are in a particular gene module belong to the according bicluster and samples for which the gene module is activated belong to the bicluster. We consider three gene expression data sets which have been provided by the Broad Institute and were previously clustered by Hoshida et al. (2007) using additional data sets. Our goal was to study how well biclustering methods are able to recover these clusters without any additional information. (A) The “breast cancer” data set (van’t Veer et al., 2002) was aimed at a predictive gene signature for the outcome of a breast cancer therapy. We removed the outlier array S54 which leads to a data set with 97 samples and 1213 genes. In Hoshida et al. (2007), three biologically meaningful subclasses were found that should be re-identified. (B) The “multiple tissue types” data set (Su et al., 2002) are gene expression profiles from human cancer samples from diverse tissues and cell lines. The data set contains 102 samples with 5565 genes. Biclustering should be able to re-identify the tissue types. (C) The “diffuse large-B-cell lymphoma (DLBCL)” data set (Rosenwald et al., 2002) was aimed at predicting the survival after chemotherapy. It contains 180 samples and 661 genes. The three classes found by Hoshida et al. (2007) should be re-identified.
For methods assuming a fixed number of biclusters, we chose five biclusters — slightly higher than the number of known clusters to avoid biases towards prior knowledge about the number of actual clusters. Besides the number of hidden units (biclusters) we used the same parameters as described in Sec. 3.1. The performance was assessed by comparing known classes of samples in the data sets with the sample sets identified by biclustering using the consensus score defined in Subsection 3.2.3 — here the score is evaluated for sample clusters instead of biclusters. The biclustering results are summarized in Table 2. RFN biclustering yielded in two out of three datasets significantly better results than all other methods and was on second place for the third dataset (significantly according to a McNemar test of correct samples in clusters).
3.4 1000 GENOMES DATA SETS
In this experiment, we used RFN for detecting DNA segments that are identical by descent (IBD). A DNA segment is IBD in two or more individuals, if they have inherited it from a common ancestor, that is, the segment has the same ancestral origin in these individuals. Biclustering is well-suited to detect such IBD segments in a genotype matrix (Hochreiter, 2013; Povysil & Hochreiter, 2014), which has individuals as row elements and genomic structural variations (SNVs) as column elements. Entries in the genotype matrix usually count how often the minor allele of a particular SNV is present in a particular individual. Individuals that share an IBD segment are similar to each other because they also share minor alleles of SNVs (tagSNVs) within the IBD segment. Individuals that share an IBD segment represent a bicluster.
For our IBD-analysis we used the next generation sequencing data from the 1000 Genomes Phase 3. This data set consists of low-coverage whole genome sequences from 2,504 individuals of the main continental population groups (Africans (AFR), Asians (ASN), Europeans (EUR), and Admixed Americans (AMR)). Individuals that showed cryptic first degree relatedness to others were removed, so that the final data set consisted of 2,493 individuals. Furthermore, we also included archaic human and human ancestor genomes, in order to gain insights into the genetic relationships between humans, Neandertals and Denisovans. The common ancestor genome was reconstructed from human, chimpanzee, gorilla, orang-utan, macaque, and marmoset genomes. RFN IBD detec-
tion is based on low frequency and rare variants, therefore we removed common and private variants prior to the analysis. Afterwards, all chromosomes were divided into intervals of 10,000 variants with adjacent intervals overlapping by 5,000 variants
In the data of the 1000 Genomes Project, we found IBD-based indications of interbreeding between ancestors of humans and other ancient hominins within Africa (see Fig. 2 as an example of an IBD segment that matches the Neandertal genome).
4 CONCLUSION
We have introduced rectified factor networks (RFNs) for biclustering and benchmarked it with 13 other biclustering methods on artificial and real-world data sets.
On 400 benchmark data sets with artificially implanted biclusters, RFN significantly outperformed all other biclustering competitors including FABIA. On three gene expression data sets with previously verified ground-truth, RFN biclustering yielded twice significantly better results than all other methods and was once the second best performing method. On data of the 1000 Genomes Project, RFN could identify IBD segments which support the hypothesis that interbreeding between ancestors of humans and other ancient hominins already have taken place in Africa.
RFN biclustering is geared to large data sets, sparse coding, many coding units, and distinct membership assignment. Thereby RFN biclustering overcomes the shortcomings of FABIA and has the potential to become the new state of the art biclustering algorithm.
Acknowledgment. We thank the NVIDIA Corporation for supporting this research with several Titan X GPUs.
The paper presents a repurposing of rectified factor networks proposed
earlier by the same authors to biclustering. The method seems
potentially quite interesting but the paper has serious problems in
the presentation.
Quality:
The method relies mainly on techniques presented in a NIPS 2015 paper
by (mostly) the same authors. The experimental procedure should be
clarified further. The results (especially Table 2) seem to depend
critically upon the sparsity of the reported clusters, but the authors
do not explain in sufficient detail how the sparsity hyperparameter is
determined.
Clarity:
The style of writing is terrible and completely unacceptable as a
scientific publication. The text looks more like an industry white
paper or advertisement, not an objective scientific paper. A complete
rewrite would be needed before the paper can be considered for
publication. Specifically, all references to companies using your
methods must be deleted.
Additionally, Table 1 is essentially unreadable. I would recommend
using a figure or cleaning up the table by removing all engineering
notation and reporting numbers per 1000 so that e.g. "0.475 +/- 9e-4"
would become "475 +/- 0.9". In general figures would be preferred as a
primary means for presenting the results in text while tables can be
included as supplementary information.
Originality:
The novelty of the work appears limited: the method is mostly based on
a NIPS 2015 paper by the same authors. The experimental evaluation
appears at least partially novel, but for example the IBD detection is
very similar to Hochreiter (2013) but without any comparison.
Significance:
The authors' strongest claim is based on strong empirical performance
in their own benchmark problems. It is however unclear how useful this
would be to others as there is no code available and the details of
the implementation are less than complete. Furthermore, the method
depends on many specific tuning parameters whose tuning method is not
fully defined, leaving it unclear how to guarantee the generalisation
of the good performance.