GSPL: A Succinct Kernel Model for Group-Sparse Projections Learning of Multiview Data

1 Introduction

Recently, a large amount of multiview data have emerged in real scenarios, in which the features are characterized from different sources, extractors and external environments. For example, a person can be described via iris, fingerprint and face features, a document can be narrated via multiple languages, an image can be described by different feature extractors, etc [Zhang et al., 2016; Nie et al., 2018; Wu et al., 2020]. Considering high dimensionality of multiview data and expensive cost of label acquisition, how to select discriminative features on multiview data with unsupervised paradigm has attracted more attentions in recent years.

∗Corresponding Author

Related works. The previous works can be simply divided into two categories, including serial models and parallel models. 1) The serial models directly concatenate multiview feature vectors into a long vector, and explore a whole sparse Projection Matrix (PM) via employing single view unsupervised feature selection models (SOCFS [Han and Kim, 2015], SOGFS [Nie et al., 2016], URAFS [Li et al., 2018] models are frequently used), in which the discriminative features can be selected from sparse PM. Except for directly utilizing single-view models, [Dong et al., 2019] proposed a ACSL model which learns both a unified projection and a collaborative graph to mine more discriminative information. 2) The parallel models explore a sparse PM for each view and integrate the selected features of different views artificially. The most exemplary works contain: ASVW [Hou et al., 2017], which collectively learns sparse PM for each view via ℓ2,p-norm regularization and a common graph from multiple views; MVUFS [Qian and Zhai, 2014], which performs joint local learning regularized orthogonal nonnegative matrix factorization and ℓ2,1-norm minimization; RMFS [Liu et al., 2016], which employs K-means to efficiently obtain labels for guiding ℓ2,1-norm regularized feature selection; CGMVUFS [Tang et al., 2018], which incorporates feature selection with ℓ2,1-norm constraint into non-negative matrix factorization (NMF) based clustering model.

Confronting problems. However, previous works suffer from several open flaws. In serial models, the inconsistency of multiple views cannot be captured completely, especially when concatenating multiview feature vectors. In parallel models, the number of selected features for each view depends on artificial settings, which is hard to apply in practice. Furthermore, both series and parallel works conventionally utilize ℓ2,1 or ℓ2,p-norm regularization to encourage the sparsity of PM, which cannot guarantee the group-sparsity of PM and leads to mismatched problem between the group-sparsity of PM and the number of selected features. More importantly, previous works contain several hyper-parameters for exploring the adaptive combination of different regularizations, including ℓ2,1 or ℓ2,p-norm regularization, which affects the applicability of model. Through the above analysis, we can conclude that a complete multiview feature selection model

̂

should handle the following 4 problems:

• IC Problem : How to capture the InConsistency among multiple views?
• SF Problem: How to allocate the number of Selected Features for multiple views based on a total number?
• GS Problem: How to guarantee the Group-Sparsity of learnt projection matrix (matrices)?
• SC Problem: How to guarantee the SuCcinctness of model?

Our proposals. To this goal, we propose a succinct kernel model for Group-Sparse Projections Learning (GSPL), to handle IC, SF, GS and SC problems simultaneously. The workflow is plotted into Fig. 1. Specifically, GSPL first learns a fused feature matrix, mapped and fused by sparse projection matrices and adaptive weights, and then encloses it to mutiview spectral embeddings based on Hilbert-Schmidt Independence Criterion (HSIC) on Reproducing Kernel Hilbert Spaces (RKHSs) adaptively. As aforementioned in Abstract, the proposed GSPL contains three useful functionalities, including Adaptivity, Strictness and Succinctness, wherein Adaptivity solves problems IC and SF via learning p and z in Fig. 1. Strictness solves problem GS via ℓ2,0-norm constraint of ̂W in Fig. 1, Succinctness means that that our model does not add any hyper-parameter except for the number of selected features and the number of reduced dimensionality brought by feature selection task, which handles the SC problem effectively. Except for the above three functionalities, the HSIC metric on RKHSs helps the learnt fused feature matrix to capture the high-order information from multiview spectral embeddings. To solve the optimization problem involved in GSPL, we propose a novel iterative algorithm with theoretical guarantees. Eventually, the effectiveness of GSPL and the convergent speed of proposed algorithm are evaluated. The experimental results demonstrate that the proposed GSPL model achieves SOTA performance and the proposed solver can converge rapidly. In a word, we concisely summarize the main contributions of this paper as follows:

• We propose a GSPL model to solve the IC, SF, GS and SC vital problems simultaneously and effectively.
• We propose a novel iterative algorithm to solve the optimization problem involved in GSPL.
• The proposed GSPL model has no extra hyperparameters, but achieves SOTA performance in several real datasets compared to previous works.

2 Preliminaries

Hilbert-Schmidt Independence Criterion (HSIC). Given two Reproducing Kernel Hilbert Spaces (RKHSs) F and G, and a joint measure p with (A×B,P ×J ), where A, B are separable spaces, P and J are Borel sets on A and B separately, HSIC is defined as the squared Hilbert-Schmidt norm with the cross-covariance. If there are n observations Z = {(a1, b1) , ..., (an, bn)} ⊆ A×B independently drawn from p, and the corresponding data matrices are A ∈ Rn×t1 and B ∈ Rn×t2 , an empirical HSIC [Gretton et al., 2005; Zhang et al., 2018] can be written as

where KA ∈ Rn×n and KB ∈ Rn×n are kernel matrices and H = In×n - 1n 1n1Tn is the centralized matrix. In theory, the larger the HSIC, the larger the dependence between A and B.

Majorize-Maximization (MM) framework. For a general problem maxx f(x), MM algorithm [Sun et al., 2016; Nie et al., 2020; Ham et al., 2018] aims at seeking a surrogate problem maxx ϕ(x) to help optimize the raw problem iteratively. Suppose x0 is a current solution, maxx ϕ(x|x0) should satisfy the following conditions:

Obviously, when ˜x = arg max ϕ (x), we have

which guarantees the ascent property.

3 Methodology

3.1 Proposed GSPLModel

Given a multi-view data X = {X1, . . . , Xs}, wherein Xv ∈ Rn×dv is the feature matrix of v-th view, n and dv are the numbers of samples and dimensions of Xv. Besides, we denote the v-th spectral embedding as Uv ∈ Rn×c generated via Laplacian eigenmap [Belkin and Niyogi, 2001], i.e., minUTv Uv=Ic×c Tr(UTv LSUv), on the similarity matrix Sv ∈ Rn×n constructed from Xv, where c is the number of clusters and LS ∈ Rn×n is the Laplacian matrix of S. Now we start the derivation of proposed GSPL model as Fig. 1 shows. At first, we map Xv ∈ Rn×dv as XvWv ∈ Rn×m, where m is the reduced dimensionality and Wv ∈ Rdv×m is the projection matrix. Then to integrate the information among multiple views, we explore a center ∑sv=1 pvXvWv of multiple XvWv ∈ Rn×m, where pv is the flip and scale operator variable of v-th view. Afterwards, we map ∑sv=1 pvXvWv and multiview spectral embeddings {Ug}sg=1 into Reproducing Kernel Hilbert Spaces (RKHSs), and enclose them with HSIC measure as follows:

where Mv is the sparse constraint of Wv, K¯X and KUg are kernel matrices, zg is the weight for the HSIC measure between ¯X = ∑sv=1 pvXvWv and Ug, and ‖z‖2 = 1, z ⩾ 0 is the normalized constraint. In this paper, we set the kernel as the inner product, i.e., K¯X = ¯X¯XT = (∑sv=1 pvXvWv)(∑sv=1 pvXvWv)T and KUg = UgUTg , then problem (4) can be written as

In problem (5), p considers the flip and scale transformation when integrating multiple XvWv, and z considers the differences when approximating ∑sv=1 pvXvWv to multiple spectral embeddings. These two variables capture the differences among multiple views comprehensively, which handles the IC problem effectively. Now we consider designing the sparse constraint Wv ∈ Mv. At first, we concentrate all projection matrices into ̂W = [W1; . . . ;Ws]T ∈ R̂d×m, where ̂d = ∑sv=1 dv, then constrain ̂W via ℓ2,0-norm for groupsparsity. By this way, problem (5) can be improved as

where 1k ⩾m is the number of selected features. In problem (6), according to ‖̂W‖2,0 = k, the group-sparsity of eachWv is also guaranteed and the number of 0 rows is determined adaptively from the perspective of the whole ̂W, which handles the SF and GS problems effectively. So far, the final version of GSPL model is obtained as problem (6), which handles the IC, SF and GS problems effectively. More importantly, it is obvious to observe that except for m and k brought by multiview feature selection task, the proposed GSPL model does not bring any extra hyper-parameter, then the SC problem is also handled thoroughly.

3.2 Optimization for GSPLModel

Since problem (6) contains three variables, including p, z and W, we consider optimizing them alternatively.

Update p and fix others. WhenW and z are fixed, problem (6) becomes

where ̂U = ∑sg=1 zgHTUgUTg H. Let Av = ̂UXvWv, Bv = XvWv, then problem (7) becomes

For convenience, we denote ̂A = [Vec(A1), . . . ,Vec(As)], ̂B = [Vec(B1), . . . ,Vec(Bs)] ∈ Rnm×s , where Vec(·) is the column-based matrix vectorization operator. Then problem (8) can be rewritten as the following form:

The solution p of problem (9) can be formed as the eigenvectors corresponding to the s largest eigenvalues of ̂BT ̂A.

Update z and fix others. WhenW and p are fixed, problem (6) becomes

Considering the term ‖UTg H ∑sv=1 pvXvWv‖2F ≥ 0, we have the following derivations according to Cauchy-Schwarz inequality [Steele, 2004]:

1 k and m are two intrinsic parameters brought by projectionbased feature selection task. In our model, we set m ⩽ k for the correction of the ℓ2,0-norm optimization.

Considering ‖z‖2 = 1, the equality in (a) holds when

which is the closet solution of problem (10).

Update {Wv}sv=1 and fix others. When p and q are fixed, problem (6) can be written as

where ̂X = [X1, . . .Xs] ∈ Rn×̂d , ˜P = diag(˜p) ∈ R̂d×̂d is a diagonal matrix and ˜p = [p11d1 ; . . . ; ps1ds ] ∈ R̂d is the diagonal vector of it, diag(·) is the vector-diagonal operator. Denote Eg = UTg ĤX˜P, problem (13) can be written as

Further, we denote SE = ∑sg=1 zgETg Eg + λIm×m, where λ guarantees that SE is positive semi-definite, then problem (14) can be written as

which is NP-hard, then we consider to solve it into two cases. At first, we consider the case rank(SE) ⩽ m. Since ‖̂W‖2,0 = k, suppose 2q ∈ Ind(k, ̂d) is the Rk indicator vector of non-sparse rows of ̂W, then ̂W can be decomposed into ̂W = BD. Wherein, B = Π(q) ∈ {0, 1}̂d×k , whose 〈u, v〉-th element buv = 1 only if u = qv, and Π(·) is the mapping function Ind(k, ̂d) → {0, 1}̂d×k ; D ∈ Rk×m and the u-th row of D is the qu-th row of ̂W, and naturally DTD = Im×m. Then problem (15) can be written as the following problem w.r.t. B and D:

where the optimal B = Π(˜q), where ˜q ∈ Ind(k, ̂d) is the indicate vector of the first k largest values of the diagonal vector of SE. Then in problem (16), the solution D can be formed by the eigenvectors corresponding to first-m largest eigenvalues of BTSEB. Finally, ̂W can be calculated as BD. More details about this solution can be referred to supplementary material. Then we consider the case rank(SE) > m. In this case, we consider utilizing the famous Majorize-Minimization (MM) framework. Suppose the current solution is ̂W0, via observing that ̂WT 0 SE ̂W0 = ̂WT 0 (SE ̂W0(̂WT 0 SE ̂W0)†̂WT 0 SE) ̂W0, where (·)† is the Algorithm 1: The Algorithm for Solving problem (6)

2 Ind(k, ̂d) is a Rk indicator vector, which selectes k elements from {1, . . . , ̂d} as ascending order and the elements are not duplicated. For example, Ind(2, 3) can be {1, 2}, {1, 3}, {2, 3}.

Input: X ∈ Rn×̂d , {Ug}sg=1 , ̂d, k, m Initialization: p, q, ̂W= [W1; . . . ;Ws]T. while not converge do Update p via solving problem (9). Update z via Eq. (12). if rank(SE) ⩽ m then Update B and D via solving problem (16). Update ̂W via ̂W = BD. else while not converge do Set ̂W0 by current ̂W. Update ̂W via solving problem (17).

Moore-Penrose inverse operator, and considering the conditions of MM framework, we guess the following surrogate problem of problem (15) based on MM framework:

with the vital property as the following remark:

Remark 1. Suppose that the objective functions of problem (15) and problem (17) are JR(̂W) and JS(̂W) respectively, at any point ̂WT ̂W = Im×m, ‖̂W‖2,0 = k, we have JR(̂W) ⩾ JS(̂W) and JR(̂W0) = JS(̂W0).

Then we can conclude that problem (17) can be a surrogate problem for problem (15). The proof of Remark 1 is provided into supplementary material. Afterwards, we focus on the surrogate problem, i.e., problem (17), and propose the following two observations: 1) Since rank(̂W0) ⩽ m, we have rank (SE ̂W0(̂WT 0 SE ̂W0)†̂WT 0 SE) ⩽ m. 2) Considering SE is positive semi-definite so that SE = GGT, and the fact that A† = A†AA† , we have

where ̂G = SE ̂W0(̂WT 0 SE ̂W0)†̂WT 0 G, then we have SE ̂W0(̂WT 0 SE ̂W0)†̂WT 0 SE is positive semi-definite. Then problem (17) can be solved as the same way of problem (15) in the case of rank(SE) ⩽ m. For simplicity of expression, we do not provide the detailed optimization procedures. The algorithm to solve problem (6) is summarized in Algorithm 1.

Convergence guarantee. Algorithm 1 optimizes p, z and ̂W via solving the subproblems iteratively, wherein psubproblem and z-problem contain closed solutions. For ̂W, when rank(SE) ⩽ m, ̂W has closed solution; when rank(SE) > m, the convergence of the subproblem (15) is guaranteed by MM framework. Therefore, the objective value of problem (6) will increase when optimizing any one of the subproblems, which means the objective value of problem (6) will monotonically increase per iteration until convergence.

Computational cost. Update p and z: O(n2 (m+ c)s + nkms); Update ̂W: O((n2 + n̂d + ̂d2 )cs + (k3 + ̂dkm)t1); The whole computational cost can be calculated by: O(((n2 c + ̂d2 c + n2m + nkm)s + (̂dkm + k3 )t1)t2) where t1, t2 are the iterations of the inner and outer loops separately.

4 Experiments

Evaluations on synthetic dataset. This part aims to answer the following questions intuitively: Can GSPL model select the discriminative features on the multiview data with noise features and noise views? To this end, we carefully design a synthetic dataset which contains 4 views, each of which has 600 samples with 3 clusters. As Table 1 shows, in view 1-3, the 1-3 features are discriminative and the other features are noisy. View 4 is chaotic in which all the features are noisy. Fig. 2 intuitively shows the discriminative and noisy features, where (b) and (d) are respectively the projections of the data in (a) and (c). In Fig. 2-(a) and -(b), all the three features are discriminative, and in Fig. 2-(c) and -(d), all the three features are not discriminative. On the designed synthetic dataset, we run GSPL algorithm to select 9 features from 20 features via setting m as 3, and the visualization of the the learnt projections {Wv}sv=1 are plotted into Fig. 3. From the results, we can find that the non-sparse rows of eachWv correspond to the discriminative features of this view. Particularly in chaotic view 4, GSPL ignores all the features, which means GSPL can resist noisy views. Besides, we record the learnt z, i.e., z1 = 0.5065, z2 = 0.6165, z3 = 0.6041, z4 = 0.0013, which satisfies the designed criterion that views 1-3 are normal and view 4 is chaotic. Thus we can conclude that the variable z has the ability to resist noisy views.

Evaluations on real datasets. In this part, we evaluate the clustering performance of proposed method GSPL on 4 real multi-view datasets, including ORL 3 , Caltech101-7 [Li et al., 2004], Reuters 4 , COIL20 5 . The details are available in Table 2. Moreover, We employ 8 SOTA models as competitors, including 3 series models (i.e., SOCFS [Han and Kim, 2015], SOGFS [Nie et al., 2016], URAFS [Li et al., 2018]), and 5 parallel models (i.e., MVUFS [Qian and Zhai, 2014], RMFS [Liu et al., 2016], ASVW [Hou et al., 2017], CGMV-UFS [Tang et al., 2018], ACSL [Dong et al., 2019]). We evaluate the clustering performance via K-means on the selected features of original data, and the performance is measured by ACCuracy (ACC) and Normalized Mutual Information (NMI) [Strehl and Ghosh, 2002]. For fair comparison, all the parameters are set according to the suggestions in original articles, and the total reduced dimensionality m in our GSPL is empirically selected around 2k/3 to k, and the number of selected features is set to ̂d ∗ r, where r is the rate of the selected features, traversed from 0.1 to 0.5 with 0.05 as interval. To alleviate the random effect caused by K-means, we run it for 30 times and report the mean in Fig. 4.

3 http://www.uk.research.att.com/facedatabase.html

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

5 http://www.cs.columbia.edu/CAVE/software/softlib/

Performance evaluation. In Fig. 4: 1) GSPL achieves over 4.84%, 4.58%, 1.28% and 7.51% higher ACC than the second highest results on the 4 datasets, and obtains around 2.39%, 3.41% and 3.40% larger NMI than the best results of competitors on ORL, Reuters and COIL20 datasets; 2) GSPL outperforms others when the rate of the selected features is small (i.e. 10% or 15%) in all the cases, which indicates that GSPL can achieve better performance than others with fewer selected features and select more discriminative features.

TSNE visualization. In this part, we visualize the original concentrated feature matrix ̂X = [X1, . . .Xs] and learnt ˜X ∈ Rn×k via T-SNE on them to obtain the low-dimensional representations of them. The results are plotted in Fig. 5. It is obvious that via group-sparse projection and adaptive fusion, the separability of data has superb improvement.

Convergence analysis. In this part, we empirically show the convergence behavior of Algorithm 1. For all the datasets, we set k and m to 0.5 ∗ ̂d and 2k/3, respectively. The convergent curves are plotted in Fig. 6, from which we can see that Algorithm 1 can converge rapidly (within 10 iterations).

5 Conclusion

This paper proposed a GSPL model for multi-view feature selection. The three properties of our model, including Strictness, Adaptivity and Succinctness, effectively handle the four key problems of multiview feature selection task, including IC, SF, GS, SC. Moreover, an efficient algorithm with rigorous convergence guarantee is innovatively proposed to optimize GSPL model. Sufficient experimental results verify the promising performance of the proposed method.

Acknowledgments

This work was supported in part by the National Key Research and Development Program of China under Grant 2018AAA0101902, in part by the Natural Science Basic Research Program of Shaanxi (Program No. 2021JM-071), in part by the National Natural Science Foundation of China under Grant 61936014 and Grant 61772427, and in part by the Fundamental Research Funds for the Central Universities under Grant G2019KY0501.