Multi-view Feature Learning with Discriminative Regularization

1 Introduction

Nowadays, with the rapid development of information technology, a large number of data can be described by different kinds of features. These features usually are generated by various feature extraction ways. Taking the image data as an example, many heterogeneous visual features are widely used, which include SIFT [Lowe, 2004], HOG [Dalal and Triggs, 2005], LBP [Ojala et al., 2002], GIST [Oliva and Torralba, 2001], CMT [Yu et al., 2002] and CENT [Wu and Rehg, 2008]. They describe the rich content of image data from different viewpoints and capture their corresponding certain properties.

For processing such data, there are two challenges. The first is how to integrate different types of features effectively, which certainly can lead to more accurate and robust performance than by only using each individual type of features. The second is how to reduce dimensions of high dimensional heterogeneous features efficiently, which may lead to heavy complexity and curse of dimensionality.

A number of earlier efforts have been devoted to address these challenges. Focusing on the first challenge, many multi-view methods have been developed [Eaton et al., 2010; Kumar et al., 2011; Cai et al., 2011; Jiang et al., 2012; Cai et al., 2013a; 2013b; Wang et al., 2014] based on various techniques, such as Co-EM (which iteratively estimates the propagation with each view and transfers the constraints across views), Co-Regularized (which makes the clustering hypotheses on different views agree with each other), Minimax (which achieves multi-feature fusion via minimizing the maximum weighted disagreement costs) and so on. Although they can achieve heterogeneous features integration in a common space, there still exist some drawbacks, such as the lack of dimensionality reduction, which may result in the problems of heavy computational complexity, curse of dimensionality or over-fitting when dealing with high dimensional and complex data.

To address the second challenge, much progress based on multi-view setting has been made in recent years [Chaudhuri et al., 2009; Han et al., 2012; Tang et al., 2013; Wang et al., 2013; Zhao et al., 2014; Cao et al., 2015; Xu et al., 2016]. These algorithms adopt a variety of methods to reduce data dimensionality, like CCA (which maximizes the total correlations between any two views to obtain one common space), Co-training (which exploits label learned automatically in one view to learn discriminative subspaces in another), HSIC (as a diversity term to explore the complementary of multi-view representation), LDA (which maximizes the between-class scatter matrix and minimizes the within-class scatter matrix) and so on. Although these algorithms can learn low dimensional features to reduce heavy computational complexity and curse of dimensionality, their performance for subsequent multi-view tasks (i.e., clustering/classification) is still not satisfactory.

Most previous works perform the multi-view feature learning in the manner of unsupervised learning, thus the discriminant information, e.g., label information, is not explicitly taken into account. Actually, nowadays in many real applications, the label information of the data is available already on the web or can be acquired from sensors easily. For example, image data and their label information, which are publicly available and can be downloaded them from ImageNet 1 , CV

1 http://image-net.org/

Datasets 2 and UCI Machine Learning Repository 3 . Thus, a promising idea is to develop supervised feature learning methods which may infer more discriminative information with the help of data labels.

Recently, two works of [Kan et al., 2012] and [Arora and Livescu, 2014] were proposed by utilizing labeled data. The former, Multi-view Discriminative Analysis [Kan et al., 2012], forms a generalized Rayleigh quotient by combining the between-class and within-class variations. Through jointly optimizing multiple transforms, it learns single unified discriminant common space for multiple views. Unfortunately, original objective function of [Kan et al., 2012] in the form of trace ratio does not have the closed form solution, thus, authors reformulate their framework into a more tractable one: ratio trace. However, [Wang et al., 2007] pointed out that transforming trace ratio into the corresponding ratio trace form is inexact, thus its feature learning models may not achieve satisfactory performance for multi-view tasks. The latter [Arora and Livescu, 2014] is mainly applied to bottleneck features, which can be learned if the training set is phonetically labeled. It includes a series of combinations of LDA and CCA. However, this simple concatenation of LDA and CCA renders its framework to be more separate and cannot tackle high dimensional multi-view data efficiently.

According to above mentioned analysis, considering that the cost of obtaining labeled data is no longer expensive and two challenges are not well addressed based on unsupervised framework, we design a novel framework, called Multi-View Feature Learning (MVFL). Concretely, the proposed MVFL method combines the regression-like objective function with discriminative regularization (utilizing training label information) to formulate a unified learning framework, where multiple view-specific projections (transformations) can be obtained and each projection learns much stronger discriminative features with very low dimensions for each view. The learned model has a good performance on test data for doing multi-view clustering.

The contributions of the proposed work can be summarized as follows. Firstly, as a feature learning framework, the proposed method simultaneously preserves the certain property of each view in its corresponding feature space and considers the view-wise consistency of multiple views via the discriminative regularization. The learned model realizes the integration of heterogeneous features and makes them complement with each other, which can generate a good performance in subsequent multi-view clustering. Secondly, the proposed method obtains multiple feature learning projections (transformations) for different views regularized by label information on training data, which has stronger discriminative ability to capture efficient and very low dimensional features, and then does well on test data. Thirdly, the proposed method can be rewritten as a trace optimization problem, which makes the original problem be solved in a closed form by using eigenvalue decomposition. Finally, experimental evaluations on four widely used datasets and comparisons with a number of state-of-the-art multi-view clustering algorithms demonstrate the superiority of the proposed work.

2 http://www.cvpapers.com/datasets.html

3 https://archive.ics.uci.edu/ml/datasets.html

2 RelatedWork

In the setting of clustering, given n data samples {xi}ni=1 , there is data matrix X = [x1,· · ·, xn] ∈ Rd×n , where each column xi ∈Rd is the input vector including all features. For a matrixW=[wij], we denote its i-th row as wi and its j-th column as wj .

Previous work [Nie et al., 2009] showed the following regression-like clustering objective, which is equivalent to the Discriminative K-Means [Ye et al., 2008], obtains better results than K-Means or spectral clustering methods:

where b∈Rc×1 is the intercept vector, 1n is n × 1 constant vector of all 1's, F=[f1,· · ·, fn]T ∈Rn×c is the cluster indicator matrix, and fi ∈Rc is the cluster indicator vector for data point xi with fij indicating how likely xi belongs to the j-th cluster.

Recently, the work [Wang et al., 2013] pointed out that although the traditional K-Means clustering or spectral clustering objectives can be extended for multi-view clustering, many multi-view clustering objectives still only learn one weight for all features from each sample. Thus, [Wang et al., 2013] designed proper regularizers and learned the weight for each feature to capture the feature-wise importance. Its objective function is as follows:

where xi ∈Rd is the input vector including all features from a total of K views and each view j has dj features such that d= ∑kj=1 dj. Upon solution, [Wang et al., 2013] learned the parameter matrix W= [w1 1 ,· · ·,w1 c ;· · ·,· · ·,· · ·;wk 1 ,· · ·, wk c ]∈ Rd×c , where wqp ∈ Rdq indicated the weights of all features in the q-th view with respect to the p-th. ‖W‖G1 and ‖W‖2,1 were defined as the group ℓ1-norm and the ℓ2,1norm, respectively, where ‖W‖G1 = ∑ci=1 ∑kj=1 ‖wj i ‖2 and

Although this recent work involves the interrelations among multi-view features, concatenating heterogeneous features (multiple views) directly ignores the view-specific information which has the certain property and denotes the specific physical significance and statistical property of each view. Thus it may lose their corresponding certain properties. Besides, this work is unsupervised, which may be lack of discriminative ability because of ignoring label information. Furthermore, the solution of problem (2) is not a closed form by iterative method and easily runs into the local extreme. In order to address above drawbacks, this paper proposes a novel multi-view framework to learn multiple feature weighting matrices (feature learning models) in a supervised way, which not only maintains the relative independence on heterogeneous view-specific properties but also keeps the consistency of multiple views through discriminative information.

3 The ProposedMethod

In this section, we propose a novel supervised multi-view learning framework, which can be obtained by exploring some heterogeneous training data, and then use this framework to learn multiple discriminative and low dimensional features by testing data, and further to improve multi-view clustering.

3.1 Formulation

Inspired by problem (1), we construct a multi-view framework from a new perspective, which considers the heterogeneous features from both view-wise and individual viewpoints. Thus, our framework can be formulated as follows:

where the index i of variable means the i-th view and there are K views. Xi ∈ Rdi×n is the data matrix, Wi ∈ Rdi×mi transforms original features from di-dimension to mi-dimension in each view, bi ∈ Rmi×1 is the intercept vector, Zi ∈ Rn×mi denotes the learned features of each view, C is defined as the cluster centroid in multiple discriminative feature spaces, and Y ∈ Rn×c is the cluster indicator matrix of all views. Because problem (3) is a supervised model, Y essentially is the label matrix, where each row of Y denotes the label vector of each sample and its c-th element is 1 and other elements are 0 if the sample belongs to the c-th class.

In this proposed model, we can achieve two goals. On one hand, for the residual term, we use current learned features Zi in the i-th discriminative subspace to approximate the regression-like objectiveXTi Wi+1nbTi . This maintains their own specific properties of different views. On the other hand, for the regularized term, we utilize the label information Y to keep the consistency of clustering results of different views. This regularization essentially is like a K-Means objective but the labeling knowledge is available here, which makes multiple feature weighting matrices (models) more discriminative (calculated by multiple discriminative features [Z1,· · ·,ZK] of training data), and can improve the performance of subsequent multi-view clustering.

3.2 Optimization

The problem (3) comprises two constraints for Zi, which requires Zi to be orthogonal and requires the sum of each column of Zi to be zero. Thus, directly solving problem (3) is difficult and we need a series of mathematical transformations as follows.

Theorem 1. Solving problem (3) is equivalent to solving the following objective function:

where H = I- 1n 1n1Tn is the centering matrix and Mi = HXTi (XiHXTi )-1XiH-H, andN=I-Y(YTY)-1YT are Laplacian-like matrices.

Proof. Using the properties of matrix trace, the objective of problem (3) can be rewritten as follows:

Due to solving the minimum, we get the derivative of Eq.(5) with respect to bi and C, respectively. Ignoring irrelevant terms and using the rules of matrix derivative, there is:

where C is the cluster centroid of multiple discriminative feature spaces. Through Eq.(7), the objective of problem (3) becomes:

where H= I- 1n 1n1Tn is the centering matrix and N= IY(YTY)-1YT are Laplacian-like matrices.

Along the similar way, taking derivative of Eq.(8) with respect toWi, we have:

SubstitutingWi into Eq.(8), we can achieve problem (4) and complete the proof.

In the analysis of transforming problem (3) to problem (4), it can be seen that Wi can be solved completely depending on Zi and H. Thus, solvingWi in problem (3) can be transformed into solving Zi in problem (4) which has only one variable Zi. In addition, problem (4) contains not only a datadriven term of Zi but also a regularization term of Zi. So, the proposed method will not lead to an over-fitting result and its solution can be calculated in a closed form by eigen decomposition to avoid running into the local extreme.

Furthermore, according to the optimization theory, it is known that min[A+B] equals to min[A]+min[B]. Thus, problem (4) can be decoupled to the following problem:

Algorithm 1 : The algorithm for solving MVFL.

• 1: Input: Training set
• 2: Multi-view data X={Xi}Ki=1 , Xi ∈Rdi×n , label information Y∈Rn×c , the number of clusters c, the reduced dimension mk and parameterλ.
• 3: for i ← 1,K do
• 4: Learn features Zi ∈Rn×mi of each view by solving problem (11).
• 5: CalculateWi,bi and C using Eq.(9) and Eq.(7).
• 6: end for
• 7: Output: Trained feature learning model {Wi,bi}Ki=1 .
• 8: Use trained model on testing set ˜X={˜Xi}Ki=1 , and obtain testing features ˜Z={˜Zi}Ki=1 .
• 9: Perform multi-view K-Means clustering on ˜Z to evaluate the accuracy of trained feature learning model {Wi,bi}Ki=1 .

It can be seen that the problem (10) is equivalent to the following problem for a large enough value of λ:

When parameter λ is large enough, for every i, the optimal solution Zi to the problem (11) will make the second term Tr(ZTi 11T Zi) be zero, and thus the constraint ZTi 1 = 0 in problem (10) could be satisfied.

Compared with the original problem (10), the problem (11) is much easier to be solved. For a large enough value of λ, the optimal solution Zi of problem (11) is formed by mi eigenvectors of Mi +γN+λ11T corresponding to mi smallest eigenvalues. Besides, because of (Mi +γN)1 = 0, mi smallest eigenvectors ofMi+γN+λ11T from the first to the mi-th are actually mi smallest eigenvectors of Mi+γN from the second to the mi+1-th.

Thus, we further calculate Wi, bi and C according to Eq.(9) and Eq.(7), respectively, which makes us obtain K feature learning models for K views.

To sum up, the whole procedure of our work can be described as follows. Given the training data {Xi}Ki=1 and its corresponding label Y, we can obtain the feature learning model for K views, i.e., feature weighting matrix {Wi}Ki=1 and intercept vector {bi}Ki=1 . Such model will be evaluated on testing data. That is to say, we use the trained model to learn some low dimensional features based on testing data and utilize the multi-view K-Means clustering to verify the effectiveness of the trained model. Concretely, we learn new features {˜Zi}Ki=1 on testing data { ˜Xi}Ki=1 using the model {Wi,bi}Ki=1 , and then cluster these features {˜Zi}Ki=1 by performing multi-view K-Means clustering according to [Xu et al., 2016]. We describe this process in Algorithm 1.

3.3 Convergence Analysis

As mentioned above, it is obvious that problem (3) can be transformed into problem (4) which is further equivalent to problem (11) for a large λ, which makes the original problem be solved by a trace optimization problem and obtains the global optimal solution in a closed form.

4 Experiments

In this section, we evaluate the proposed framework through clustering task on four widely used datasets in terms of four standard clustering evaluation metrics, namely Accuracy (ACC) [Cai et al., 2005], Normalized Mutual Information (NMI) [Cai et al., 2005], Jaccard Index (Jaccard) [Varshavsky et al., 2005] and Purity [Varshavsky et al., 2005].

4.1 Datasets

In our experiments, by following [Cai et al., 2013b; Cao et al., 2015; Xu et al., 2016], four datasets including MSRCv1 [Lee and Grauman, 2009; Cai et al., 2013b], Caltech101-7 [Dueck and Frey, 2007], Handwritten [Asuncion and Newman, 2007] and Yale [Cao et al., 2015] datasets are adopted for evaluations. Tabel 1 summarizes the information of each dataset including the number of samples and classes, heterogeneous features and the dimensionality of each type of feature in the parenthese. Besides, we need to normalize and center all data values before experiments.

4.2 Experiment Setup

Following [Cai et al., 2013b; Xu et al., 2016], firstly, we applied the proposed MVFL (Multi-view Feature Learning) on each type of features to form a baseline SVFL (Singleview Feature Learning) to demonstrate that the multi-view method MVFL has advantages of multi-view with respect to the single-view method SFL. Next, we compared MVFL with AVFL (All-view Feature Learning), where AVFL concatenates all heterogeneous features directly as one view and performs the proposed feature learning algorithm. However, AVFL dose not consider specific properties of different views and relationships between them. Thus, AVFL is not as good as the proposed MVFL method.

Furthermore, we compared MVFL method with some state-of-the-art multi-view clustering methods: NMVKM (Naive Multi-view K-Means), RMVKM (Robust Multi-view K-Means) [Cai et al., 2013b] and DEKM (Discriminatively Embedded K-Means) [Xu et al., 2016]. Besides, we compared our method with MvDA (Multi-view Discriminant Analysis) [Kan et al., 2012] which projects multi-view data into a discriminative common space by using multiple transformations and performs multi-view K-Means clustering on this space.

Finally, we performed a simple version of the proposed MVFL method, gMVFL (γ=0), to evaluate the effectiveness of its regularized term in multi-view framework. Obviously, we only use the first term of problem (3), which is equivalent to linear regression to learn features, and then performed multi-view K-Means clustering on these learned features.

4.3 Experiment Results

The comparison results measured by ACC, NMI, Jaccard and Purity are reported in Tables 2 to 5, respectively. For these metrics, the higher value indicates better clustering quality. Each metric penalizes or favors different properties in the clustering, and hence we report results on these diverse measures to perform a comprehensive evaluation.

The experimental results, in Tables 2 and 3, show that the proposed method (MVFL) performs generally better than that on each view (SVFL), which validates the superiority of heterogeneous features integration. For example, for MSRCv1 and Caltech101-7 datasets shown in Table 2, the results of SVFL method (for each view) are lower than that of MVFL method. Because in multi-view setting, each view of the data may contain some knowledge that other views do not have. It is straightforward to demonstrate the superiority of multiview.

In Tables 4 and 5, MVFL method on multiple views outperforms AVFL on the concatenation of all views. Taking Handwritten dataset as an example, the performance of AVFL is not as good as that of MVFL. Because MVFL not only preserves the certain property of each view but also considers the intercoordinations of different views while the simple features concatenation does not have such capability. Sometimes, AVFL is unable to appropriately cope with multiple views, and may even degrade the performance of multi-view clustering compared with some single views.

Moreover, compared with other four multi-view methods (NMVKM, RMVKM, DEKM and MvDA), the proposed MVFL method can achieve the best performance. This is consistent with our theoretical analysis in the above sections. Concretely, compared with NMVKM and RMVKM, MVFL method obtains the low dimensional and discriminative learning model by feature weighting matrices (projections), such as the results of Handwritten dataset in Table 5. In addition, although DEKM also can achieve feature projections using dimensionality reduction, without help of training data label information, the learned features of DEKM are lack of discriminative ability. Besides, compared with MvDA which is a supervised method, MVFL obtains better results on different datasets. It is because althoughMvDA utilizes the label information in training stage, its original objective function dose not have the closed form and its approximate objective function is inexact, which affects the performance of MvDA to some extent. In contract, MVFL can be solved analytically in a closed form. Finally, we implement a simple version of the proposed method, i.e., gMVFL, which only has a regressionlike objective function. Actually, gMVFL is actually an unsupervised method and its performance is degenerated without the discriminative regularization.

4.4 Parameters Setup

For comparison methods, we performed them according to their corresponding original works and selected their optimal parameters by using grid search. For the proposed method, we set the regularized parameter γ =1 in (3), and tuned the dimension parameters {mi}Ki=1 (mi < min(di, n)) heuristically by searching the grid with proper step-size. Besides, if XiHXTi is nearly singular, we can regularize it asXiHXTi + ϵIdi by introducing a small perturbation ϵ(ϵ = 10-4 ). It is demonstrated that if ϵ → 0, minimizing the perturbation version is reduced to problem (3). Besides, we compared total dimensions of different multi-view methods (NMVKM, RMVKM, DEKM, gMVFL, MvDA and MVFL) which is shown in Figure 1. It is observed that the proposed MVFL method only learns a few of discriminative features to achieve satisfactory experimental results.

5 Conclusion

In this paper, we proposed a novel supervised multi-view learning framework, which efficiently learns multiple discriminative feature weighting matrices for different views with the help of label information. In this framework, the regression-like objective and discriminative regularization were utilized to yield multiple feature learning models with stronger discriminative abilities, and then learned low dimensional features for subsequent processing. Besides, our method can be transformed into a trace optimization problem, which obtains the global solution in a closed form. Comparisons with existing state-of-the-art multi-view clustering methods, our framework captured the efficient features and achieved better performance in multi-view clustering tasks.

Acknowledgments

This work was supported in part by the National Science Foundation of China under Grants 61522207 and 61473231.