Adaptive Collaborative Similarity Learning for Unsupervised Multi-view Feature Selection

1 Introduction

With the advent of big data, multi-view features with high dimensions are widely employed to represent the complex data in various research fields, such as multimedia computing, machine learning and data mining [Liu et al., 2016; 2017; Zhu et al., 2017b; 2015; Cheng and Shen, 2016; Cheng et al., 2016]. On the one hand, with multi-view features, the data could be characterized more precisely and comprehensively from different perspectives. On the other hand, highdimensional multi-view features will inevitably generate expensive computation cost and cause massive storage cost. Moreover, they may contain adverse noises, outlying entries, irrelevant and correlated features, which may be detrimental to the subsequent learning process [Zhu et al., 2016b; 2016a; 2017a]. Unsupervised multi-view feature selection [Wang et al., 2016; Li and Liu, 2017] is devised to alleviate the problem. It selects a compact subset of informative features from the original features by dropping irrelevant and redundant features with advanced unsupervised learning. Due to the independence on semantic labels, high computing efficiency and well interpretation capability, unsupervised multiview feature selection has received considerable attention in literature. It becomes a prerequisite component in various machine learning models [Li et al., 2017].

∗Corresponding Author

The key problem of multi-view feature selection is how to effectively exploit the diversity and consistency of multi-view features to collaboratively identify the feature dimensions, which could retain the key characteristics of the original features. Existing approaches can be categorized into two major families. The first kind of methods first concatenates multiview features into a vector and then directly imports it into the conventional single-view feature selection model. The candidate features are generally ranked based on spectral graph theory. Typical methods of this kind include Laplacian Score (LapScor) [He et al., 2005], spectral feature selection (SPEC) [Zhao and Liu, 2007] and minimum redundancy spectral feature selection (MRSF) [Zhao et al., 2010]. Commonly, the pipeline of these methods follows two separate processes: 1) Similarity structure is constructed with fixed graph parameters to describe the geometric structure of data. 2) Sparsity and manifold regularization are employed together to identify the most salient features. Although these methods are reported to achieve certain success, they treat features from different views independently and unfortunately neglect the important view correlations.

Another family of methods considers view correlation when performing feature selection. Representative works include adaptive multi-view feature selection (AMFS) [Wang et al., 2016], multi-view feature selection (MVFS) [Tang et al., 2013] and adaptive unsupervised multi-view feature selection (AUMFS) [Feng et al., 2013]. These methods first construct multiple view-specific similarity structures 1 and then perform the subsequent feature selection based on the collaborative (combined) similarity structure. These two processes are separate and independent. The collaborative similarity structure remains fixed during feature selection. The latently involved data noises and outlying entries in the view-specific similarity structures will adversely reduce the reliability of the ultimate collaborative similarity structure for feature selection. Furthermore, conventional approaches generally employ knearest neighbors assignment to construct the view-specific similarity structures and the simple weighted combination for ultimate similarity structure generation. This strategy can hardly achieve the ideal state for clustering that the number of connected components in the ultimate similarity structure is equal to the number of clusters [Nie et al., 2014]. Thus, suboptimal performance may be caused under such circumstance.

In this paper, we introduce an adaptive collaborative similarity learning (ACSL) for unsupervised multi-view feature selection. The main contributions of this paper can be summarized as follows:

• Different from existing solutions, we integrate the collaborative similarity structure learning and multi-view feature selection into a unified framework. The collaborative similarity structure and similarity combination weights could be learned adaptively by considering the ultimate feature selection performance. Simultaneously, the feature selection can preserve the dynamically adjusted similarity structure.
• We impose a reasonable rank constraint to adaptively learn an ideal collaborative similarity structure with proper neighbor assignment which could positively facilitate the ultimate feature selection. An effective alternate optimization approach guaranteed with convergence is derived to iteratively solve the formulated optimization problem.

2 RelatedWork

One kind of unsupervised multi-view feature selection methods directly imports the concatenated features in multiple views into the single-view feature selection model. In [He et al., 2005], Laplacian score (LapScor) is employed to measure the capability of each feature dimension on preserving sample similarity. [Zhao and Liu, 2007] proposes a general spectral theory based learning framework to unify the unsupervised and supervised feature selection. [Zhao et al., 2010] adopts an embedding model to handle feature redundancy in the spectral feature selection. These methods generally rank the candidate feature dimensions with various graphs which characterize the manifold structure. They treat features from different views independently and unfortunately ignore the important correlation of different feature views. Another kind of methods directly tackles the multi-view feature selection. They consider view correlations when performing feature selection. Adaptive multi-view feature selection (AMFS) [Wang et al., 2016] is an unsupervised feature selection approach which is developed for human motion retrieval. It describes the local geometric structure of data in each view with local descriptor and performs the feature selection in a general trace ratio optimization. In this method, the feature dimensions are determined with trace ratio criteria. Adaptive unsupervised multi-view feature selection (AUMFS) [Feng et al., 2013] addresses the feature selection problem for visual concept recognition. It employs l2,1 norm [Nie et al., 2010] based sparse regression model to automatically identify discriminative features. In AUMFS, data cluster structure, data similarity and the correlations of different views are considered for feature selection. Multi-view feature selection (MVFS) [Tang et al., 2013] investigates the feature selection for multi-view data in social media. A learning framework is devised to exploit the relations of views and help each view select relevant features.

1 In this paper, view-specific similarity structure is constructed with the corresponding view-specific feature.

3 The ProposedMethodology

3.1 Notations and Definitions

Throughout the paper, all the matrices are written in uppercase with boldface. For a matrix M ∈ RN×d , its ith row is denoted by Mi′ ∈ RN×1 , its jth column is denoted by Mj ∈ Rd×1 . The element in the ith row and jth column is represented as Mij. The trace of the matrix M is denoted as Tr(M). The transpose of matrix M is denoted as M T . The l2,1 norm of the matrix M is denoted as ||M||2,1, which is calculated by ∑Ni=1 √∑dj=1 M 2 i,j . The Frobenius norm of M is denoted by ||M||F = √∑Ni=1 ∑dj=1 M 2 i,j . 1 denotes a column vector whose all elements are one. Ik×k denotes k × k identify matrix.

The feature matrix of data in the vth view is denoted as Xv = [xv1 , xv2 , ..., xvN ]T ∈ RN×dv , xv1 ∈ Rdv×1 , dv is the dimension of feature in the vth view, N is the number of data samples. We pack the feature matrices in V views {Xv }Vv=1 and the overall feature matrix of data can be represented as X = [X1 , X2 , ..., XV ] ∈ RN×d , ∑Vv=1 dv = d. The objective of unsupervised multi-view feature selection is to identify l most valuable features with only X.

3.2 Formulation

The importance of feature dimensions are primarily determined by measuring the their capabilities on preserving the similarity structures in multiple views. In this paper, we develop a unified learning framework to learn an adaptive collaborative similarity structure with automatic neighbor assignment for multi-view feature selection. In our model, the neighbors in the collaborative similarity structure could be adaptively assigned by considering the feature selection performance, and simultaneously the feature selection could preserve the dynamically constructed collaborative similarity structure. Given V similarity structures constructed in multiple views {Sv }Vv=1 , V is the number of views, we can automatically learn a collaborative similarity structure S by combining {Sv }Vv=1 with V weights.

where Sj ∈ RN×1 characterizes the similarities between any data points with j, it should be subjected to the constraint that 1 T Sj = 1, Sj ≥ 0, Wj = [w1 j , w2 j , ..., wV j ]T ∈ RV×1 is comprised of view weights for the jth column of similarities, it is constrained with W Tj 1V = 1, W = [W1,W2, ...,WN] ∈ RV×N is view weight matrix for all columns in the similarity structures. As indicated in recent work [Nie et al., 2014], a theoretically ideal similarity structure for clustering should have the property that the number of connected components is equal to the number of clusters. The similarity structure with such neighbor assignment could benefit the subsequent feature selection. Unfortunately, the similarity structure learned from Eq.(1) does not have such desirable property.

To tackle the problem, in this paper, we impose a reasonable rank constraint on the Laplacian matrix of the collaborative similarity structure to enable it to have such property. Our idea is motivated by the following spectral graph theory.

Theorem 1. If the similarity structure S are nonnegative, the multiplicity of eigen-values 0 corresponding to its Laplacain matrix is equal to the number of components of S. [Alavi, 1991]

As mentioned above, the data points can be directly partitioned into k clusters if the number of components in the similarity structure S is exactly equal to k. Theorem 1 indicates that this condition can be achieved if the rank of Laplacian matrix is equal to n - k. With the analysis, we add a reasonable rank constraint in Eq.(1) to achieve the condition. The optimization problem becomes

where LS = DS - S T+S 2 is the Laplacain matrix of similarity structure S, DS = S1 is diagonal matrix. As shown in Eq.(2), directly imposing the rank constraint rank(LS) = n - k will make the above problem hard to solve. Fortunately, according to Ky Fan's Theorem [K., 1949], we can have ∑ki=1 δi(LS) = argminF∈Rn×k ,F T F=Ik Tr(F T LSF), where δi(LS) is the ith smallest eigen-values of LS and F ∈ RN×k is the relaxed cluster indicator matrix. Obviously, the rank constraint rank(LS) = n - k can be satisfied when ∑ki=1 δi(LS) = 0. To this end, we reformulate the Eq.(2) as the following simple equivalent form

As shown in the above equation, when α > 0 is large enough, the term Tr(F T LSF) is forced to be infinitely approximate 0 and the rank constraint can be satisfied accordingly. By simply transforming the rank constraint to trace in objective function, the problem in Eq.(2) can be tackled more easily.

The selected features should preserve the dynamically learned similarity structure. Conventional approaches separate the similarity structure construction and feature selection into two independent processes, which will potentially lead to sub-optimal performance. In this paper, we learn the collaborative similarity structure dynamically and further integrate it with feature selection into a unified framework. Specifically, based on the collaborative similarity structure learning in Eq.(3), we employ sparse regression model to learn a projection matrix P ∈ Rd×k , so that the projected lowdimensional data XP can approximate the relaxed cluster indicator F. To select the features, we impose l2,1 norm penalty on P to force it with row sparsity. The importance of features can be measured by the l2 norm of each row feature in P. The overall optimization formulation can be derived as

With P, the importance of features are measured by ||Pi′ ||2. The features with the l largest values can be finally determined.

3.3 Alternate Optimization

As shown in Eq.(4), the objective function is not convex to three variables simultaneously. In this paper, we propose an effective alternate optimization to iteratively solve the problem. Specifically, we optimize one variable by fixing the others.

Update P. By fixing the other variables, the optimization for P can be derived as

This equation is not differentiable. Hence, we transform it to following equivalent equation [Nie et al., 2010]

Γ ∈ Rd×d is diagonal matrix whose ith diagonal element is 1 2√Pi′P Ti′+ϵ . ϵ is small enough constant. It is used to avoid the condition that ||Pi′ ||2 is zero. By calculating the derivations of the objective function with P and setting it to zeros, we can obtain the updating rule for P as

Note that Γ is dependent on P. We develop an iterative approach to solve P and Γ until convergence. Specifically, we fix Γ to solve P, and vice versa.

Update F. By fixing the other variables, the optimization for F can be derived as

By substituting Eq.(7) into the objective function in Eq.(8), we arrive at

where Q = X T X + γΓ. With the transformation, the optimization for updating F can be solved by simple eigendecomposition on the matrix LS +βIN -βXQ-1X T . Specifically, the columns of F are comprised of the k eigenvectors corresponding to the k smallest eigenvalues.

Update S. By fixing the other variables, the optimization for S becomes

The above equation can be rewritten as

where Si,j denotes the element in the ith row and jth column of S. The optimization processes for the columns of S are independent with each other. Hence, they can be optimized separately. Formally, S can be solved by

Let Aj be row vector with N × 1 dimensions. Its ith element is ||fi - fj||22 . The above optimization formula can be transformed as

This problem can be solved by an efficient iterative algorithm [Huang et al., 2015].

UpdateW. Similar to S, the optimization processes for the columns of W are independent with each other. Hence, they can be optimized separately. Formally, its jth column Wj is solved by

The objective function in Eq.(14) can be rewritten as

where Bvj = Sj - Svj , Bj = [B1j , ..., Bvj , .., BVj ]. We can obtain the Lagrangian function of problem (14)

ψ is also Lagrangian multiplier. By calculating the derivative of (16) with Wj and setting it to 0, we obtain the updating rule of Wj as

The main steps for solving problem (4) are summarized in Algorithm 1.

Algorithm 1 Multi-view feature selection via collaborative similarity structure learning with adaptive neighbors.

Input:

The pre-constructed similarity structures in v views {Sv }Vv=1 , the number of clusters k, the parameters α, β, γ.

Output:

The collaborative similarity structure S, the projection matrix P for feature selection, l identified features.

• 1: InitializeWwith 1 V , the collaborative similarity structure S with the weighted sum of {Sv }Vv=1 . We also initialize F with the solution of problem (8) by substituting the Laplacian matrix calculated from the new S.
• 2: repeat
• 3: Update P with Eq.(7).
• 4: Update F by solving the problem in Eq.(8).
• 5: Update S with Eq.(13).
• 6: UpdateWwith Eq.(17).
• 7: until Convergence Feature Selection
• 8: Calculate ||Pi′ ||2, (i = 1, 2, ..., d) and rank them in descending order. The l features with the top rank orders are finally determined as the features to be selected.

3.4 Convergence Analysis

The convergence of solving problem (6) can be proven by the following theorem.

Theorem 2. The iterative optimization process for solving Eq.(5) will monotonically decrease the objective function value until convergence.

Proof. Let ̂P be the newly updated P, we can obtain the following inequality

By adding γ ∑di=1 ϵ 2√P Ti′Pi′+ϵ to the both sides of the inequality (18) and substituting Γ, the inequality can be rewritten as

On the other hand, according to the Lemma 1 in [Nie et al., 2010], we can obtain that for any positive number u and v, we can have √u-

Then, we can obtain that

By summing the above inequalities (19) and (21), we arrive at

We can derive that

The convergence of solving Algorithm 1 can be proven by the following theorem.

Theorem 3. The iterative optimization in Algorithm 1 can monotonically decrease the objective function of problem (4) until convergence.

Proof. As shown in Theorem 2, updating P will monotonically decrease the objective function in problem (4) (t is number of iterations).

By fixing other variables and updating F, the objective function in Eq.(8) is convex (The Hessian matrix of the Lagrangian function of Eq.(8) is positive semidefinite [Alavi, 1991]). Therefore, we can obtain that

By fixing other variables and updating S, optimizing the Eq.(13) is a typical Quadratic programming problem. The Hessian matrix of the Lagrangian function of problem (13) is also 1N1 TN that is positive semidefinite. Therefore, we can obtain that

By fixing other variables and updating W, the Hessian matrix of Eq.(16) is B Tj Bj. It is positive semidefinite as W Tj B Tj BjWj) = ||BjWj||2F ≥ 0. Hence, the objective function for optimizing W is also convex. Then, we arrive at

4 Experiments

4.1 Experimental Datasets

1) MSRC-v1 [Winn and Jojic, 2005]. The dataset contains 240 images in 8 class as a whole. Following the setting in [Grauman and Darrell, 2006], we select 7 classes composed of tree, building, airplane, cow, face, car, bicycle and each class has 30 images. We extract 5 visual features from each image: color moment with dimension 48, GIST with 512 dimension, SIFT with dimension 1230, CENTRIST feature with 210 dimension, and local binary pattern (LBP) with 256 dimension. 2) Handwritten Numeral [van Breukelen et al., 1998]. This dataset is comprised of 2,000 data points from 0 to 9 digit classes. 6 features are used to represent each digit. They are 76 dimensional Fourier coefficients of the character shapes, 216 dimensional profile correlations, 64 dimensional Karhunen-love coefficients, 240 dimensional pixel averages in 2 × 3 windows, 47 dimensional Zernike moment and 6 dimensional morphological features. 3) Youtube [Liu et al., 2009]. This real-world dataset is collected from Youtube. It contains intended camera motion, variations of the object scale, viewpoint, illumination and cluttered background. The dataset is comprised of 1,596 video sequences in 11 actions. 4) Outdoor Scene [Monadjemi et al., 2002]. The outdoor scene dataset contains 2,688 color images that belong to 8 outdoor scene categories. 4 visual features are extracted from each image: color moment with dimension 432, GIST with dimension 512, HOG with dimension 256, and LBP with dimension 48.

Table 2: NMI of different methods with different numbers of selected features by using K-means for clustering.

4.2 Experimental Setting

Baselines. We compare ACSL with several representative unsupervised multi-view feature selection methods on clustering performance. The compared methods include, three single view feature selection approaches (Laplacian score (LapScor) [He et al., 2005], spectral feature selection (SPEC) [Zhao and Liu, 2007] and minimum redundancy spectral feature selection (MRSF) [Zhao et al., 2010]), and three multiview feature selection approach (adaptive multi-view feature selection (AMFS) [Wang et al., 2016], multi-view feature selection (MVFS) [Tang et al., 2013] and adaptive unsupervised multi-view feature selection (AUMFS) [Feng et al., 2013]). Evluation Metrics. We employ standard metrics: clustering accuracy (ACC) and normalized mutual information (NMI), for performance comparison. Each experiment is performed 50 times and the mean results are reported. Parameter Setting. In implementation of all methods, the neighbor graph is adopted to construct the initial affinity matrices. The number of neighbors is set to 10 in all methods. In ACSL, α, β, γ are chosen from 10-4 to 104 . The parameters in all compared approaches are carefully adjusted to report the best results.

4.3 Comparison Results

The comparison results measured by ACC and NMI are reported in Table 1 and Table 2, respectively. For these metrics, the higher value indicates the better feature selection performance. Each metric penalizes or favors different properties in feature selection. Hence, we report results on these diverse measures to perform a comprehensive evaluation. The obtained results demonstrate that ACSL can achieve superior or at least comparable performance than the compared approaches. The promising performance of ACSL is attributed to the reason that the proposed collaborative similarity structure learning with proper neighbor assignment could positively facilitate the ultimate multi-view feature selection.

4.4 Parameter and Convergence Experiment

We investigate the impact of parameters α, β and γ in Eq.(4) on the performance of ACSL. Specifically, we vary one parameter by fixing the others. Figure 1 presents the main results on MSRC-V1. The obtained results clearly show that ACSL is robust to the involved three parameters. Figure 2 records the variations of the objective function value in Eq.(4) with the number of iterations on MSRC-V1 and Handwritten Numeral. We can easily observe that the convergence curves become stable within about 5 iterations. The fast convergence ensures the optimization efficiency of ACSL.

5 Conclusion

In this paper, we propose an adaptive collaborative similarity structure learning for multi-view feature selection. Different from existing approaches, we integrate collaborative similarity learning and feature selection into a unified framework. The collaborative similarity structure with the ideal neighbor assignment and similarity combination weights are adaptively learned to positively facilitate the subsequent feature selection. Simultaneously, the feature selection can supervise the similarity learning process to dynamically construct the desirable similarity structure. Experiments show the superiority of the proposed approach.