Self-weighted Multiple Kernel Learning for Graph-based Clustering and Semi-supervised Classification

1 Introduction

As a principled way of introducing non-linearity into linear models, kernel methods have been widely applied in many machine learning tasks [Hofmann et al., 2008; Xu et al., 2010]. Although improved performance has been reported in a wide variety of problems, the kernel methods require the user to select and tune a single pre-defined kernel. This is not user-friendly since the most suitable kernel for a specific task is usually challenging to decide. Moreover, it is time-consuming and impractical to exhaustively search from a large pool of candidate kernels. Multiple kernel learning (MKL) was proposed to address this issue as it offers an automatical way of learning an optimal combination of distinct base kernels [Xu et al., 2009]. Generally speaking, MKL method should yield a better performance than that of single kernel approach.

∗Corresponding author.

A key step in MKL is to assign a reasonable weight to each kernel according to its importance. One popular approach considers a weighted combination of candidate kernel matrices, leading to a convex quadratically constraint quadratic program. However, this method over-reduces the feasible set of the optimal kernel, which may lead to a less representative solution. In fact, these MKL algorithms sometimes fail to outperform single kernel methods or traditional non-weighted kernel approaches [Yu et al., 2010; Gehler and Nowozin, 2009]. Another issue is the inappropriate weights assignment. Some attempts aim to learn the local importance of features by assuming that samples may vary locally [G¨onen and Alpaydin, 2008]. However, they induce more complex computational problems.

To address these issues, in this paper, we model the differences among kernels by following two intuitive assumptions: (i) each kernel is a perturbation of the consensus kernel; and (ii) the kernel that is close to the consensus kernel should receive a large weight. As a result, instead of enforcing the optimal kernel being a linear combination of predefined kernels, this approach allows the most suitable kernel to reside in some kernels' neighborhood. And our proposed method can assign an optimal weight for each kernel automatically without introducing an additive parameter as existing methods do.

Then we combine this novel weighting scheme with graphbased clustering and semi-supervised learning (SSL). Due to its effectiveness in similarity graph construction, graph-based clustering and SSL have shown impressive performance [Nie et al., 2017a; Kang et al., 2017b]. Finally, a novel multiple kernel learning framework for clustering and semi-supervised learning is developed.

In summary, our main contributions are two-fold:

• We proposed a novel way to construct the optimal kernel and assign weights to base kernels. Notably, our proposed method can find a better kernel in the neighborhood of candidate kernels. This weight is a function of kernel matrix, so we do not need to introduce an additional parameter as existing methods do. This also eases the burden of solving the constraint quadratic program.

• A unified framework for clustering and SSL is developed. It seamlessly integrates the components of graph construction, label learning, and kernel learning by incorporating the graph structure constraint. This allows them to negotiate with each other to achieve overall optimality. Our experiments on multiple real-world datasets verify the effectiveness of the proposed framework.

2 RelatedWork

In this section, we divide the related work into two categories, namely graph-based clusteirng and SSL, and paremeterweighted multiple kernel learning.

2.1 Graph-based Clustering and SSL

Graph-based clustering [Ng et al., 2002; Yang et al., 2017] and SSL [Zhu et al., 2003] have been popular for its simple and impressive performance. The graph matrix to measure the similarity of data points is crucial to their performance and there is no satisfying solution for this problem. Recently, automatic learning graph from data has achieved promising results. One approach is based on adaptive neighbor idea, i.e., sij is learned as a measure of the probability that Xi is neighbor of Xj. Then S is treated as graph input to do clustering [Nie et al., 2014; Huang et al., 2018b] and SSL [Nie et al., 2017a]. Another one is using the so-called selfexpressiveness property, i.e., each data point is expressed as a weighted combination of other points and this learned weight matrix behaves like the graph matrix. Representative work in this category include [Huang et al., 2015; Li et al., 2015; Kang et al., 2018]. These methods are all developed in the original feature space. To make it more general, we develop our model in kernel space in this paper. Our purpose is to learn a graph with exactly c number of connected components if the data contains c clusters or classes. In this work, we will consider this condition explicitly.

2.2 Parameter-weightedMultiple Kernel Learning

It is well-known that the performance of kernel method crucially depends on the kernel function as it intrinsically specifies the feature space. MKL is an efficient way for automatic kernel selection and embedding different notions of similarity [Kang et al., 2017a]. It is generally formulated as follows:

where f is the objective function, K is the consensus kernel, Hi is our artificial constructed kernel, θi represents the weight for kernel Hi , q > 0 is used to smoothen the weight distribution. Therefore, we frequently sovle θ and tune q. Though this approach is widely used, it still suffers the following problems. First, the linear combination of base kernels over reduces the feasible set of optimal kernels, which could result in the learned kernel with limited representation ability. Second, the optimization of kernel weights may lead to inappropriate assignments due to noise and carelessly designed algorithms. Indeed, contrary to the original intention of MKL, this approach sometimes obtains lower accuracy than that of using equally weighted kernels or merely single kernel method. This will hinder the practical use of MKL. This phenomenon has been observed for many years [Cortes, 2009] but rarely studied. Thus, it is vital to develop some new approaches.

3 Methodology

3.1 Notations

Throughout the paper, all the matrices are written as uppercase. For a matrix X, its ij-th element and j-th column is denoted as xij and Xj, respectively. The trace of X is denoted by T r(X). The i-th kernel of X is written as Hi . The p-norm of vector x is represented by ‖x‖p. The Frobenius norm of matrix X is denoted by ‖X‖F . I is an identity matrix with proper size. S ≥ 0 means all entries of S are nonnegative.

3.2 Self-weightedMultiple Kernel Learning

Aforementioned self-expressiveness based graph learning method can be formulated as:

where γ is the trade-off parameter. To recap the powerfulness of kernel method, we extend Eq. (2) to its kernel version by using kernel mapping φ. According to the kernel trick K(x, z) = φ(x)T φ(z), we have

Ideally, we hope to achieve a graph with exactly c connected components if the data contain c clusters or classes. In other words, the graph S is block diagonal with proper permutations. It is straightforward to check that S in Eq. (3) can hardly satisfy to such a constraint condition.

If the similarity graph matrix S is nonnegative, then the Laplacian matrix L = D-S, where D is the diagonal degree matrix defined as dii = ∑j sij, associated with S has an important property as follows [Mohar et al., 1991]

Theorem 1 The multiplicity c of the eigenvalue 0 of the Laplacian matrix L is equal to the number of connected components in the graph associated with S.

Theorem 1 indicates that if rank(L) = n - c, then the constraint on S will be held. Therefore, the problem (3) can be rewritten as:

Suppose σi(L) is the i-th smallest eigenvalue of L. Note that σi(L) ≥ 0 because L is positive semi-definite. The problem (4) is equivalent to the following problem for a large enough α:

According to the Ky Fan's Theorem [Fan, 1949], we have:

P can be cluster indicator matrix or label matrix. Therefore, the problem (5) is further equivalent to the following problem

This problem (7) is much easier to solve compared with the rank constrained problem (4). We name this model as Kernelbased Graph Learning (KGL). Note that this model's input is kernel matrix K. It is generally recognized that its performance is largely determined by the choice of kernel. Unfortunately, the most suitable kernel for a particular task is often unknown in advance. Although MKL as in Eq. (1) can be applied to resolve this issue, it is still not satisfying as we discussed in subsection 2.2.

In this work, we design a novel MKL strategy. It is based on the following two intuitive assumptions: 1) each kernel is a perturbation of the consensus kernel, and 2) the kernel that is close to the consensus kernel should receive a large weight. Motivated by these, we can have the following MKL form:

and

We can see that wi is dependent on the target variable K, so it is not directly available. But wi can be set to be stationary, i.e., after obtaining K, we update wi correspondingly [Nie et al., 2017b]. Instead of enforcing the optimal kernel being a linear combination of candidate kernels as in Eq. (1), Eq. (8) allows the most suitable kernel to reside in some kernels' neighborhood [Liu et al., 2009]. This enhances the representation ability of the learned optimal kernel [Liu et al., 2017; 2013]. Furthermore, we don't introduce an additive hyperparameter θ, which often leads to a quadratic program. The optimal weight wi for each kernel Hi is directly calculated according to kernel matrices. Then our Self-weighted Multiple Kernel Learning (SMKL) framework can be formulated

This model enjoys the following properties:

1. This unified framework sufficiently considers the negotiation between the process of learning the optimal kernel and that of graph/label learning. By iteratively updating S, P, K, they can be repeatly improved.
2. By treating the optimal kernel as a perturbation of base kernels, it effectively enlarges the region fromwhich an optimal kernel can be chosen, and therefore is in a better position than the traditional ones to identify a more suitable kernel.
3. The kernel weight is directly calculated from kernel matrices. Therefore, we avoid solving quadratic program.

To see the effect of our proposed MKL method, we need to examine the approach with traditional kernel learning. For convenience, we denote it as Parameterized MKL (PMKL). It can be written as:

3.3 Optimization

We divide the problem in Eq. (10) into three subproblems, and develop an alternative and iterative algorithm to solve them.

For S, we fix P and K. The problem in Eq. (10) becomes:

Based on ∑ij 1 2 ‖Pi,: - Pj,:‖22 sij = Tr(P T LP), we can equivalently solve the following problem for each sample:

where Gi ∈ Rn×1 with gij = ‖Pi,: - Pj,:‖22 . By setting its first derivative w.r.t. Si to be zero, we obtain:

Thus S can be achieved in parallel.

For K, we fix S and P . The problem in Eq. (10) becomes:

Similar to (14), it yields:

From Eq. (16) and Eq. (14), we can observe that S and K are seamlessly coupled, hence they are allowed to negotiate with each other to achieve better results.

For P , we fix S and K. The problem in Eq. (10) becomes:

The optimal solution P is the c eigenvectors of L corresponding to the c smallest eigenvalues.

3.4 Extend to Semi-supervised Classification

Model (10) also lends itself to semi-supervised classification. Graph construction and label inference are two fundamental stages in SSL. Solving two separate problems only once is suboptimal since label information is not exploited when it learns the graph. SMKL unifies these two fundamental components into a unified framework. Then the given labels and estimated labels will be utilized to build the graph and to predict the unknown labels.

Based on a similar approach, we can reformulate SMKL for semi-supervised classification as:

where Yl = [y1, · · · , yl]T denote the label matrix and l is the number of labeled points. yi ∈ Rc×1 is one-hot and yij = 1 indicates that the i-th sample belongs to the j-th class. P = [Pl; Pu] = [Yl; Pu], where the unlabeled u points in the back. (18) can be solved in the same procedure as (10), the difference lies in updating P .

To solve P, we take the derivative of (18) with respect to P , we have LP = 0, i.e.,

It yields:

Finally, the class label for unlabeled points could be assigned according to the following decision rule:

ALGORITHM 1: The Proposed Framework SMKL

Input: Kernel matrices {Hi }ri=1, parameters α, β, γ. Initialize: Random matrix S, K = ∑i Hi /r. REPEAT

• 1: For each i, update the i-th column of S according to (14).
• 2: Calculate K by (16).
• 3: Update w by (9).
• 4: For clustering, calculte P as the c smallest eigenvectors of L = D - S correspond to the c smallest eigenvalues. For SSL, calculte P according to (19).

UNTIL stopping criterion is met.

4 Clustering

In this section, we conduct clustering experiments to demonstrate the efficacy of our method.

4.1 Data Sets

We implement experiments on six publicly available data sets. We summarize the information of these data sets in Table 1. In specific, the first two data sets YALE and JAFFE consist of face images. YEAST is microarray data set. Tr11, Tr41, and Tr45 are derived from NIST TREC Document Database.

We design 12 kernels. They are: seven Gaussian kernels of the form K(x, y) = exp(-‖x - y‖22 /(td2max )), where dmax is the maximal distance between samples and t varies over the set {0.01, 0.05, 0.1, 1, 10, 50, 100}; a linear kernel K(x, y) = xT y; four polynomial kernels K(x, y) = (a + xT y)b with a ∈ {0, 1} and b ∈ {2, 4}. Besides, all kernels are rescaled to [0, 1] by dividing each element by the largest pairwise squared distance.

4.2 ComparisonMethods

We compare with a number of single kernel and multiple kernel learning based clustering methods. They include: Spectral Clustering (SC) [Ng et al., 2002], Simplex Sparse Representation (SSR) [Huang et al., 2015], Multiple Kernel kmeans (MKKM) [Huang et al., 2012b], Affinity Aggregation for Spectral Clustering (AASC) [Huang et al., 2012a], Robust Multiple Kernel k-means (RMKKM) 1 [Du et al., 2015]. Among them, SC, SSR, AASC are graph based methods, while the others are k-means variants. Although there are much recent work focused on multiview [Huang et al., 2018a] and deep learning based clustering [Peng et al., 2016], they are not our focus in this paper.

4.3 Performance Evaluation

SMKL is compared with other techniques. We show the clustering results in terms of accuracy (Acc), NMI in Table 2. For SC and KGL, we report its best performance achieved from those 12 kernels. It can clearly be seen that SMKL achieves the best performance in most cases. Compared to PMKL, SMKL 2 works better. As shown in Eq. (10) and (11), this is attributed to our new MKL scheme. Note that, KGL outperforms PMKL in several experiments. This is consistent with previous work's claim that MKL may degrade the performance. However, our proposed SMKL can beat KGL in all cases. This also demonstrates the effectiveness of our MKL strategy. With respect to recently developed methods SSR and RMKKM, we also observe considerable improvement. Remember that SSR is based on self-expressiveness in the original space. Compared to traditional methods SC, MKKM, AASC, our advantages become more obvious.

1 https://github.com/csliangdu/RMKKM

2 https://github.com/sckangz/IJCAI2018

4.4 Parameter Analysis

There are three parameters in our model (10). Figure 1 shows the clustering accuracy of YALE data set with varying α, β, and γ. We can observe that the performance is not so sensitive to those parameters. This conclusion is also true for NMI.

5 Semi-supervised Classification

In this section, we assess the effectiveness of SMKL on semisupervised classification task.

5.1 Data Sets

1. Evaluation on Face Recognition: We examine the effectiveness of our graph learning for face recognition on two frequently used face databases: YALE and JEFFE. The YALE face data set contains 15 individuals, and each person has 11 near frontal images taken under different illuminations. Each image is resized to 32×32 pixels. The JAFFE face database consists of 10 individuals, and each subject has 7 different facial expressions (6 basic facial expressions +1 neutral). The images are resized to 26×26 pixels.
2. Evaluation on Digit/Letter Recognition: In this experiment, we address the digit/letter recognition problem on the BA database. The data set consists of digits of "0" through "9" and letters of capital "A" to "Z". Therefore, there are 39 classes and each class has 39 samples.
3. Evaluation on Visual Object Recognition: We conduct visual object recognition experiment on the COIL20 database. The database consists of 20 objects and 72 images for each object. For each object, the images were taken 5 degrees apart as the object is rotating on a turntable. The size of each image is 32×32 pixels.

Similar to clustering experiment, we construct 7 kernels for each data set. They include: four Gaussian kernels with t varies over {0.1, 1, 10, 100}; a linear kernel K(x, y) = xT y; two polynomial kernels K(x, y) = (a + xT y)2 with a ∈ {0, 1}.

5.2 ComparisonMethods

We compare our method with several other state-of-the-art algorithms.

• Local and Global Consistency (LGC) [Zhou et al., 2004]: LGC is a popular label propagation method. For this method, kernel matrix is used to compute L.
• Gaussian Field and Harmonic function (GFHF) [Zhu et al., 2003]: Different from LGC, GFHF is another mechanics to infer those unknown labels as a process of propagating labels through the pairwise similarity.
• Semi-supervised Classification with Adaptive Neighbours (SCAN) [Nie et al., 2017a]: Based on adaptive neighbors method, SCAN shows much better performance than many other techniques.
• A Unified Optimization Framework for SSL [Li et al., 2015]: Li et al. propose a unified framework based on self-expressiveness approach. By using low-rank and sparse regularizer, they have S2LRR and S3R method, respectively.

5.3 Performance Evaluation

We randomly choose 10%, 30%, 50% portions of samples as labeled data and repeat 20 times. Classification accuracy and deviation are shown in Table 3. More concretely, for GFHF and LGC, the constructed seven kernels are tested and the best performance is reported. Unlike them, SCAN, S2LRR, S3R, and SMKL, the label prediction and graph learning are conducted in a unified framework.

As expected, the classification accuracy for all methods monotonically increase with the increase of the percentage of labeled samples. As can be observed, our SMKL method outperforms other state-of-the-art methods in most cases. This confirms the effectiveness of our proposed method on SSL task.

6 Conclusion

This paper proposes a novel multiple kernel learning framework for clustering and semi-supervised classification. In this model, a more flexible kernel learning strategy is developed to enhance the representation ability of the learned optimal kernel and to assign weight for each base kernel. An iterative algorithm is designed to solve the resultant optimization problem, so that graph construction, label learning, kernel learning are boosted by each other. Comprehensive experimental results clearly demonstrates the superiority of our method.

Acknowledgments

This paper was in part supported by two Fundamental Research Funds for the Central Universities of China (Nos. ZYGX2017KYQD177, ZYGX2016Z003), Grants from the Natural Science Foundation of China (No. 61572111) and a 985 Project of UESTC (No. A1098531023601041) .