Deep Multi-View Concept Learning

1 Introduction

Multi-view data is prevalent in many real-world applications. For instance, the same news can be obtained from various language sources; an image can be described by different low level visual features. These views often represent diverse and complementary information of the same data. Integrating multiple views is helpful to boost the performance of data mining tasks. We are concerned with representation learning by synthesizing multi-view data. In recent years, a lot of multi-view representation learning algorithms were proposed based on different techniques (e.g. matrix factorization [Guan et al., 2015; Deng et al., 2015], transfer learning [Xu and Sun, 2012]).

∗Corresponding author

As a particularly useful family of techniques in data analysis, matrix factorization is a successful representation learning technique over a variety of areas, e.g. recommendation [Wang et al., 2016a; 2016b], image clustering [Trigeorgis et al., 2017]. Recently, Nonnegative Matrix Factorization (NMF), a specific form of matrix factorization, has received significant attention in multi-view representation learning [Zong et al., 2017; Guan et al., 2015; Liu et al., 2015] due to its intuitive parts-based interpretation [Lee and Seung, 2001]. Given a data matrix X ∈ RD×N + for N items, NMF seeks two nonnegative matrices U ∈ RD×K + and V ∈ RK×N + such that X ≈ UV. U/V is called the basis/encoding matrix. The Multi-view Concept Learning (MCL) algorithm proposed in [Guan et al., 2015] is a typical semi-supervised method which explicitly discerns consistent and complementary information in multi-view data to generate conceptual representations. However, a common drawback of the above methods is that they fail to capture complex hierarchical structures of real-world data.

In order to learn a better representation by capturing the hierarchical structures, different deep matrix factorization techniques were proposed recently. Trigeorgis et al. [Trigeorgis et al., 2017] proposed the Deep Semi-NMF method for representation learning. It has an interpretation of clustering according to different attributes of a given dataset. Nevertheless, it only deals with the single view case. Zhao et al. [Zhao et al., 2017] extended Deep Semi-NMF to the multiview case. Although it is a multi-view deep factorization method, it neither considers label information of data nor explicitly models consistent and complementary information.

In this paper, we propose a new multi-view deep factorization method, named Deep Multi-view Concept Learning (DMCL). As shown in Figure 1, the deep model factorizes the data matrices (X(v) ) iteratively to get the final representation VM. For each view, each layer is a NMF which takes the representation obtained from the previous layer as its data matrix. The final representation VM is shared across different views. We impose graph embedding regularization [Yan et al., 2007] on VM to capture data conceptual structures. We also require the basis matrices ({U(v) M }) of the final layer to be sparse in term of columns to explicitly model consistency and complementarity among different views.

The major contribution of this work is a novel semisupervised deep NMF method for conceptual representation learning from multi-view data. Conceptual features can reflect semantic relationships between data items; they are connected to different views in a flexible fashion, i.e. some conceptual features are described by all the views (consistency), while others may only be associated with some of the views (complementarity). We design the optimization problem to encourage VM and ({U(v) M } to comply with these properties. The second contribution is that we propose a block coordinate decent algorithm to optimize DMCL. We also design a pretraining scheme for DMCL. Thirdly, we empirically evaluate DMCL on two real world datasets and show its superiority over state-of-art baseline methods.

2 RelatedWork

Our work falls into the area of multi-view representation learning, which is concerned with how to embed inputs from different views of the same set of data items to a new common latent space for better data representation. A recent survey for this area can be found in [Li et al., 2016]. One direction stemmed from Canonical Correlation Analysis (CCA) [Chaudhuri et al., 2009] is based on the principle of maximizing correlations in the common latent space. However, it is nontrivial to extend those methods to deal with multiple views. Another popular idea is to find a shared latent representation across different views. Many methods in this direction were based on (nonnegative) matrix factorization, e.g. [Zong et al., 2017; Liu et al., 2015; Guan et al., 2015]. However, researchers were mainly focused on consistency among different views, while complementarity is rarely explicitly modeled. There were some works that explicitly considered complementarity. Guan et al.

proposed a NMF-based flexible method where group sparseness constraints were imposed on basis matrices to learn flexible association patterns between encoding dimensions and views [Guan et al., 2015].

Nevertheless, traditional models are intrinsically shallow models and may not well handle intricate natural data. Inspired by deep learning [Bengio and others, 2009], different deep models were proposed recently for multi-view representation learning. Srivastava and Salakhutdinov [Srivastava and Salakhutdinov, 2012] proposed to learn joint representation of images and texts by Deep Boltzmann Machines. Ngiam et al. [Ngiam et al., 2011] explored extracting shared representations by training a bimodal deep autoencoder. Deep matrix factorization techniques that factorize complex natural data into multiple levels of factors will also increase representational and modeling power [Sharma et al., 2017; Trigeorgis et al., 2017]. Those methods can be viewed as a decoder network that produces a reconstruction X = g(VM). Compared to deep matrix factorization, deep neural networks are harder to approximate global optima and lack interpretability. A closely related work is [Zhao et al., 2017] where multi-layer matrix factorization is performed for multiview data clustering. Our DMCL is different from their method in that we not only incorporate label information but also explicitly learn consistency and complementarity among multiple views, trying to capture conceptual features hidden in the data.

3 The Method

Our DMCL is a deep extension of the MCL method. In this section, we review MCL briefly and then present DMCL, together with its optimization algorithm.

3.1 A Brief Review of MCL

We use X(v) ∈ RDv×N + to denote the v-th view of data, where Dv is the dimensionality of the v-th view. The dataset is described by H views: {X(v) }Hv=1 . The basis matrix U(v) ∈ RDv×K + denotes the linear connection between X(v) and V, the common encoding matrix. The data matrix of each view is separated into labeled and unlabeled parts: X(v) = [X(v),l X(v),u ]. Correspondingly, the encoding matrix becomes V = [Vl Vu ]. We use N l /N u to denote the number of labeled/unlabeled items, respectively. The optimization problem of MCL is formualted as [Guan et al., 2015]

The upper bound 1 for Vkj is used to guarantee the problem is well lower bounded [Guan et al., 2015]. The first term is the reconstruction criterion. The second term contains the group sparseness constraints imposed on the basis matrix of each view. For view v, it is defined as

It means we encourage some basis vectors of U(v) to be completely 0, so that the corresponding dimensions in V are not associated with this view. These dimensions could represent complementary information in multi-view data.

The third term is the graph embedding criterion for regularizing V where tr(·) denotes matrix trace. La and Lp represent the graph Laplacian matrices of within-class affinity graph Ga and between-class penalty graph Gp with their weighted adjacency matrices defined as

where ci denotes the label of item i, N l ci is the total number of items with label ci. The graph embedding term intrinsically forces within-class items to be near while keeps betweenclass items away from ecah other. With simple algebra transformation, we have ∑i,j W a ij ‖vli - vlj ‖22 = tr[VlLa (Vl )T ] and ∑i,j W p ij ‖vli - vlj ‖22 = tr[VlLp (Vl )T ].

The fourth term is a simple L1 norm regularizer on V since an item should not have too many conceptual features.

MCL not only tries to capture semantic structures of the data by semi-supervision, but also models consistency and complementarity among different views by group sparsity constraints. However, the shallow computation (i.e. one-step factorization) in MCL may not be able to well handle complex real world data.

3.2 DeepMulti-viewConcept Learning

In order to obtain a more expressive representation, DMCL decomposes each of the data matrices {X(v) }Hv=1 iteratively to obtain the high-level representation:

where U(v) 1 ∈ RDv×p1 + ,· · · ,U(v) m ∈ Rpm-1×pm + ,· · · ,U(v) M ∈ RpM-1×pM + denote M basis matrices and VM ∈ RpM×N + denotes the final common encoding. The optimization problem of DMCL is

Here we only apply the graph embedding constraints and the encoding sparseness constraint to VM, since the intermediate encodings are near low-level features, so they would not well represent high-level conceptual features. The group sparseness constraints used to learn the structures of consistency and complementarity are only imposed on {U(v) M }, since they can only be used where a common encoding (VM ) is reached. Note although the overall factorization is equivalent to a linear operation, as in [Zhao et al., 2017], the multi-layer computation can still help to better represent data items hierarchically by seeking a better local optimum [Zhao et al., 2017].

3.3 Optimization

(6) is not convex in both {U(v) m } and VM. Therefore, we can only find its local minima. To improve the quality of the solution and speedup learning, we initialize the model parameters using unsupervised greedy pre-training, similar to layerwise pre-training in deep learning [Hinton and Salakhutdinov, 2006]. Specifically, for each view v we first decompose X(v) as X(v) = U(v) 1 V(v) 1 using NMF. Then, we treat the learned V(v) 1 as the "data matrix" for layer 2 and continue to factorize it iteratively until the final layer. An exception is VM. For layer M, we obtain a set of encoding matrices {V(v) M } from the above initialization scheme. However, it is difficult to use them to initialize VM since elements in the same position of the encoding vectors for an item may represent different meanings in different views and so they are not comparable. Hence, we choose to initialize VM randomly. Preliminary experiments also confirmed its effectiveness.

Afterwards, the variables of (6) are separated into three groups: {U(v) m }m̸=M, {U(v) M }Hv=1 and VM. (6) is convex in one group when the other two are fixed. Therefore, we solve DMCL by block coordinate descent [Lin, 2007] which each time optimizes one group of variables while keeping the other groups fixed. The procedure is depicted in Algorithm 1. At line 2, we have V(v) 0 :=X(v) . Next, we describe the detailed ideas for addressing the three subproblems.

Updating VM

Since VM is randomly initialized, we optimize it firstly. The subproblem for VM is:

We can decompose (7) into two subproblems in which the variables are VlM and VuM , labeled part and unlabeled part of VM, respectively. The update rules can be similarly derived as in [Guan et al., 2015]. Here we only give the equations due to space limitation:

where P, Qu , Akj , Bkj and Ckj are

Here vlj and ¯vlk denote the j-th column vector and the k-th row vector of VlM , respectively. Da and Dp are diagonal matrices with Da ii = ∑N l j=1 W a ij , Dp ii = ∑N l j=1 W p ij .

Updating {U(v) m }m̸=M

Fixing other variables, we get the subproblem for {U(v) m }

For m = 1, the updating is similar as in NMF. Otherwise, the gradient of U(v) m is derived as:

where ξ (v) m = ∏m-1 i=1 U(v) i and Φ(v) m = ∏Mi=m+1 U(v) i VM. Thus the additive update for U(v) m can be given as:

Inspired by [Lee and Seung, 2001], to obtain a multiplicative update rule, η is set as (U(v) m )ik ((ξ(v) m )T ξ(v) m U(v) m Φ(v) m (Φ(v) m )T )ik . Meanwhile, the convergence is guaranteed. Correspondingly, the multiplicative update rule is:

When other variables are fixed, the U(v) M of different views are independent with each other and their subproblems are identical. For clarity, we just focus on one view and omit the superscript (v) temporally:

where ˜UM-1 = ∏M-1 m=1 Um.

φ(UM) is the sum of a differentiable function and a general closed convex function. It can be solved using composite gradient mapping [Nesterov, 2013] which was proposed for minimizing such composite functions. The central idea is to iteratively minimize an auxiliary function mL(UM) and adjust the guess of the Lipschitz constant of the first term of φ(UM) so that φ(UM) decreases by the minimizer of mL(UM). Denote f(UM) = 1 2 ∥∥∥X- ˜UM-1UMVM ∥∥∥2 F and UtM as the value of UM at the t-th iteration. The auxiliary function is set as

where L is the guess of Lf , the Lipschitz constant of f(UM), and ∇f(UtM ) is the gradient of f(UM) at UtM :

Then we minimize (19) to get a candidate for Ut+1 M :

We have φ(UtM ) = mL(UtM ;UtM ) ≥ mL(UtM ; ̂Ut+1 M ) from (20). Furthermore, it has been proved that for L ≥ Lf we havemL(UtM ; ̂Ut+1 M ) ≥ φ( ̂Ut+1 M ) [Nesterov, 2013], leading to an acceptable ̂Ut+1 M . Meanwhile, L is inversely proportional to the step size (i.e. ‖̂Ut+1 M -UtM ‖), so it cannot be set to too large values. Now the problem is to find a suitable L in each iteration. We starts with an estimate L0 such that 0 < L0 ≤ Lf , and in each iteration adjusts L until we get φ( ̂Ut+1 M ) ≤ mL(Ut ; ̂Ut+1 M ). The algorithm for optimizing UM is shown in Algorithm 2.

The remaining problem is how to optimize (20) efficiently. The solution is similar to that in [Guan et al., 2015]. We omit the details due to space limitation.

3.4 Time Complexity

The DMCL model is composed of pre-training and fineturning stages, so we analyze them separately. For simplify, we set the input feature dimensionalities for all views to D; the dimensionalities of all layers are set to p. We use τ to denote the number of iterations for all iterative procedures.

The computational cost for the pre-training stage is O(τH(DNp+MNp2 )). For fine-turning, the time complexity consists of three subparts. For optimizing {U(v) m }m̸=M, the cost is O(τHM(Dp2 +Np2 +DNp +Mp3 )). For optimizing {U(v) M }Hv=1 , we need to run Algorithm 2. Here we give the result: O(HD((2(τ + 1) + log2 Lf L0 )P + τK2 + Mp3 +Dp2 )). Here τ denotes the number iterations of the outer loop of Algorithm 2. For VM, the time complexity is O(τ(Np +Np2 + (N l )2p) +H(Mp3 +Dp2 )). The time cost of DMCL is linear in feature dimension D, item number N and view number H. However, it it not linear in layer number M and layer size p. Therefore, it is essential to set layer number and layer sizes of DMCL properly for high performance and low time consumption.

4 Experiments

We evaluate the performance of DMCL on document and image datasets in terms of classification and clustering metrics. Important statistics are summarized in Table 1 and a brief introduction of the datasets is presented below.

Reuters [Amini et al., 2009]. It consists of 111740 documents written in five languages of 6 categories represented as TFIDF vectors. We utilize documents written in English and Italian as two views. For each categories, we randomly choose 200 documents. Totally 1200 documents are used.

ImageNet [Deng et al., 2009]. It is a well known realworld image database that contains roughly 15 million images organized according to the WordNet hierarchy. We randomly select 50 leaf synsets in the hierarchy as categories and sample 240 images from each one. Three kinds of features are extracted as different views, i.e., 64D HSV histogram, 512D GIST descriptors, and 1000D bag of SIFT visual words.

We compare DMCL with the following baseline algorithms: Deep NMF (DNMF) [Song et al., 2015] is a deep matrix factorization method for single view data. We apply it on each view and report the best performance. Concatenation DNMF (ConcatDNMF) concatenates feature vectors of different views and then applies DNMF. Deep Multiview Semi-NMF (DMSNMF) [Zhao et al., 2017] is an unsupervised matrix factorization method synthesizing multiview data to capture a uniform representation. Multi-view Concept Learning (MCL) [Guan et al., 2015] is a semisupervised shallow method for multi-view data.

We use the holdout method [Han et al., 2011] for evaluation and tune model parameters by cross-validation on the training set. For each dataset, we randomly split the data items for each category and use 50% for training while the remaining 50% are reserved for test. We use the learned representation of these methods for classification and clustering. Note that the label information of the training set is utilized in semi-supervised methods, i.e., MCL and DMCL. For classification, the training items are fed into the kNN classifier (k=9) and Accuracy is calculated using the test set. For clustering, k-means is applied to the test set with k set to the actual number of classes. Accuracy and Normalized Mutual Information(NMI) are used to evaluate clustering performance [Trigeorgis et al., 2017]. To account for runtime randomness in evaluation, we run each test case 10 times and calculate the averaged performance and standard derivation.

4.1 Results

Table 2 and Figure 2 show the classification and clustering performance of DMCL and baseline methods. First, DNMF is the worst. It is outperformed by all the other methods. This reveals the importance of using multiple views. Second, semi-supervised methods outperforms unsupervised ones. This is intuitive since by exploiting the partial label information we can build a more discriminative representation. Third, our proposed DMCL consistently outperforms MCL on the two datasets, which indicates that the deep model could generate better representation by hierarchical modeling. We use t-test with significance level 0.05 to test the significance of performance difference. Results show that DMCL significantly outperforms all the baseline methods.

4.2 Analysis

In this subsection, we will analyze DMCL from two perspectives, i.e., parameter setting and convergence analysis.

Parameter analysis. Parameters of DMCL include α, β, γ, and layer number and sizes. Here we explore their impact to performance by cross-validation on the training set and only show representative results due to space limitation. We first focus on the former three parameters. α and γ control the degree of sparseness, while β controls the impact of the graph embedding regularization. We vary one parameter each time and fix the other two to explore its influence. Fig

3 shows the results on Reuters. We find a general pattern: the performance curves first go up and then go down when increasing the parameters. This means the sparseness and graph embedding terms are useful for learning good representations. Based on the results, we set α = 100, β = 0.015 and γ = 0.005 in other experiments.

Regarding layer sizes, previous work on multi-view deep factorization [Zhao et al., 2017] has found that pM, the size of the final layer, usually plays a more important role than the sizes of the other layers. Hence, we vary pM under different layer numbers and fix the sizes of the other layers empirically. Fig 4 shows the NMI results on ImageNet under 3 layer number settings. The full settings are {[200 pM], [300 200 pM], [500 300 200 pM]}. As can be seen, the performance increases with the layer number, which indicates deep factorization really helps to find better representations. Considering both performance and efficiency, we choose 3 layers for all the experiments. The layer sizes are set to [300 200 125].

Convergence analysis. Fig 5 shows the curves of objective function value and NMI against the number of iterations for DMCL and MCL. We find at the beginning the objective function value drops and the performance increases rapidly. The optimization procedure of DMCL typically converges in around 40 iterations on the ImageNet dataset.

5 Conclusion

In this paper, we developed a Deep Multi-view Concept Learning (DMCL) method to seek a common high-level representation for multi-view partially labeled data. DMCL tries to capture data semantic structures by graph embedding guided by label information. It also tries to learn the consistent and complementary information of multi-view data by group sparseness constraints. Experimental results on document/image datasets for both classification and clustering tasks confirmed the effectiveness of DMCL compared to competitive multi-view factorization models.

Acknowledgments

This research was supported by the National Natural Science Foundation of China (Grant Nos. 61522206, 61373118, 61672409), the Major Basic Research Project of Shaanxi Province (Grant No. 2017ZDJC-31), the Science and Technology Plan Program in Shaanxi Province of China (Grant No. 2017KJXX-80), the Fundamental Research Funds for the Central Universities, and the Innovation Fund of Xidian University.