On Multiple Kernel Learning with Multiple Labels

1 Introduction

With the proliferation of kernel-based methods like support vector machines (SVM), kernel learning has been attracting increasing attentions. As widely known, the kernel function or matrix plays an essential role in kernel methods. For practical learning problems, different kernels are usually prespecified to characterize the data. For instance, Gaussian kernel with different width parameters; data fusion with heterogeneous representations [Lanckriet et al., 2004b]. Traditionally, an appropriate kernel can be estimated through cross-validation. Recent multiple kernel learning (MKL) methods [Lanckriet et al., 2004a] manipulate the Gram (kernel) matrix directly by formulating it as a semi-definite program (SDP), or alternatively, search for an optimal convex combination of multiple user-specified kernels via quadratically constrained quadratic program (QCQP). Both SDP and QCQP formulations can only handle data of medium size and small number of kernels. To address large scale kernel learning, various methods are developed, including SMOlike algorithm [Bach et al., 2004], semi-infinite linear program (SILP) [Sonnenburg et al., 2007] and projected gradient method [Rakotomamonjy et al., 2007]. It is noticed that most existing works on MKL focus on binary classifications. In this work, MKL (learning the weights for each base kernel) for classification with multiple labels is explored instead.

Jieping Ye

Department of CSE Arizona State University Jieping.Ye@asu.edu

Classification with multiple labels refers to classification with more than 2 categories in the output space. Commonly, the problem is decomposed into multiple binary classification tasks, and the tasks are learned independently or jointly. Some works attempt to address the kernel learning problem with multiple labels. In [Jebara, 2004], all binary classification tasks share the same Bernoulli prior for each kernel, leading to a sparse kernel combination. [Zien, 2007] discusses the problem of kernel learning for multi-class SVM, and [Ji et al., 2008] studies the case for multi-label classification. Both works above exploit the same kernel directly for all classes, yet no empirical result is formally reported concerning whether the same kernel across labels performs better over a specific kernel for each label.

The same-kernel-across-tasks setup seems reasonable at first glimpse but needs more investigation. Mostly, the multiple labels are within the same domain, and naturally the classification tasks share some commonality. One the other hand, the kernel is more informative for classification when it is aligned with the target label. Some tasks (say recognize sunset and animal in images) are quite distinct, so a specific kernel for each label should be encouraged. Given these considerations, two questions rises naturally:

• Which approach could be better, the same kernel for all labels or a specific kernel for each label? To our best knowledge, no work has formally studied this issue yet.
• A natural extension is to develop kernels that capture the similarity and difference among labels simultaneously. This matches the relationship among labels more reasonably, but could it be effective in practice?

The questions above motivate us to develop a novel framework to model task similarity and difference simultaneously when handling multiple related classification tasks. We show that the framework can be solved via QCQP with proper regularization on kernel difference. To be scalable, an SILPlike algorithm is provided. In this framework, selecting the same kernel for all labels or a specific kernel for each label are deemed as two extreme cases. Moreover, this framework allows various degree of kernel sharing with proper parameter setup, enabling us to study different strategies of kernel sharing systematically. Based on extensive experiments on benchmark data, we report some interesting findings and explanations concerning the aforementioned two questions.

2 AUnified Framework

To systematically study the effect of kernel sharing among multiple labels, we present a unified framework to allow flexible degree of kernel sharing. We focus on the well-known kernel-based algorithm SVM, for learning k binary classification tasks {f t}kt=1 respectively, based on n training samples {(xi, yt i )}ni=1 , where t is the index of a specific label. Let HtK be the feature space, and φtK be the mapping function defined as φtK : φtK (x) → HtK , for a kernel function Kt . Let Gt be the kernel (Gram) matrix for the t-th task, namely Gt ij = Kt (xi, xj) = 〈φtK (xi) · φtK (xj)〉. Under the setting of learning multiple labels {f t}kt=1 using SVM, each label f t can be seen as learning a linear function in the feature space HtK , such that f t (x) = sign(〈wt , φtK (x)〉 + bt ) where wt is the feature weight and bt is the bias term.

Typically, the dual formulation of SVM is considered. Let D(αt , Gt ) denote the dual objective of the t-th task given kernel matrix Gt :

where for the task f t , Gt ∈ S n+ denotes the kernel matrix and S n+ is the set of semi-positive definite matrices; ◦ denotes element-wise matrix multiplication; αt ∈ Rn denotes the dual variable vector. Mathematically, multi-label learning with k labels can be formulated in the dual form as:

Here, C is the penalty parameter for allowing the misclassification. Given {Gt}kt=1 , optimal {αt }kt=1 in Eq. (2) can be found by solving a convex problem.

Note that the dual objective is the same as the primal objective of SVM due to its convexity (equal to the empirical classification loss plus model complexity). Following [Lanckriet et al., 2004a], multiple kernel learning with k labels and p base kernels G1, G2, · · · , Gp can be formulated as:

where Ω({Gt }kt=1) is a regularization term to represent the cost associated with kernel differences among labels. To capture the commonality among labels, Ω should be a monotonic increasing function of kernel difference. λ is the trade-off parameter between kernel difference and classification loss.

Clearly, if λ is set to 0, the objective goal is decoupled into k sub-problems, with each selecting a kernel independently (Independent Model); When λ is sufficiently large, the regularization term dominates and forces all labels to select the same kernel (Same Model). In between, there are infinite number of Partial Model which control the degrees of kernel difference among tasks. The larger λ is, the more similar the kernels of each label are.

3 Regularization on Kernel Difference

Here, we develop one regularization scheme such that formula (3) can be solved via convex programming. Since the optimal kernel for each label is expressed as a convex combination of multiple base kernels as in eq. (4) and (5), each θt essentially represents the kernel associated with the t-th label. We decouple the kernel weights of each label into two non-negative parts:θt i = ζi + γ t i , ζi, γ t i ≥ 0 (6)

where ζi denotes the shared kernel across labels, and γ t i is the label-specific part. So the kernel difference can be defined as:

For presentation convenience, we denote

It follows that the MKL problem can be solved via QCQP 1 .

Theorem 3.1. Given regularization as presented in (6) and (7), the problem in (3) is equivalent to a Quadratically Constrained Quadratic Program (QCQP):

The kernel weights of each label (ζi, γ t i ) can be obtained via the dual variables of the constraints.

The QCQP formulation involves nk+2 variables, (k+1)p quadratic constraints and O(nk) linear constraints. Though this QCQP can be solved efficiently by general optimization software, the quadratic constraints might exhaust memory resources if k or p is large. Next, we'll show a more scalable algorithm that solves the problem efficiently.

4 Algorithm

The objective in (3) given λ is equivalent to the following problem with a proper β and other constraints specified in (3):

1 Please refer to the appendix for the proof.

Compared with λ, β has an explicit meaning: the maximum difference among kernels of each label. Since ∑pi=1 θt i = 1, the min-max problem in (9), akin to [Sonnenburg et al., 2007], can be expressed as:

Note that the max operation with respect to αt is transformed into a constraint for all the possible αt in the set S(t) defined in (13). An algorithm similar to cutting-plane could be utilized to solve the problem, which essentially adds constraints in terms of αt iteratively. In the J-th iteration, we perform the following:

1). Given θt i and gt from previous iteration, find out new αtJ in the set (13) which violates the constraints (12) most for each label. Essentially, we need to find out αt such that ∑pi=1 θt i D(αt ,Gi) is maximized, which boils down to an SVM problem with fixed kernel for each label:

Here, each label's SVM problem can be solved independently and typical SVM acceleration techniques and existing SVM implementations can be used directly.

2). Given αtJ obtained in Step 1, add k linear constraints:

and find out new θt and gt via the problem below:

Note that both the constraints and the objective are linear, so the problem can be solved efficiently by general optimization package.

3). J = J + 1. Repeat the above procedure until no α is found to violate the constraints in Step 1.

So in each iteration, we interchangeably solve k SVM problems and a linear program of size O(kp).

5 Experimental Study

5.1 Experiment Setup

4 multi-label data sets are selected as in Table 1. We also include 5 multi-class data sets as they are special cases of multi-label classification and one-vs-all approach performs reasonably well [Rifkin and Klautau, 2004]. We report average AUC and accuracy for multi-label and multi-class data, respectively. A portion of data are sampled from USPS, Letter and Yaleface, as they are too large to handle directly. Various type of base kernels are generated. We generate 15 diffusion kernels with parameter varying from 0.1 to 6 for Ligand [Tsuda and Noble, 2004]; The 8 kernels of Bio are generated following [Lanckriet et al., 2004b]; 20news uses diverse text representations [Kolda, 1997] leading to 62 different kernels; For other data, Gaussian kernels with different widths are constructed. The trade-off parameter C of SVM is set to a sensible value based on cross validation. We vary the number of samples for training and randomly sample 30 different subsets in each setup. The average performance are recorded.

5.2 Experiment Results

Due to space limit, we can only report some representative results in Table 3-5. The details are presented in an extended technical report [Tang et al., 2009]. Tr Ratio in the first row denotes the training ratio, the percentage of samples used for training. The first column denotes the portion of kernels shared among labels via varying the parameter β in (10), with Independent and Same model being the extreme. The last row (Diff ) represents the performance difference between the best model and the worst one. Bold face denotes the best in each column unless there is no significant difference. Below, we seek to address the problems raised in the introduction.

Does kernel regularization yield any effect?

The maximal difference of various models on all data sets are plotted in Figure 1. The x-axis denotes increasing training data and y-axis denotes maximal performance difference. Clearly, when the training ratio is small, there's a difference between various models, especially for USPS, Yaleface and Ligand. For instance, the difference could be as large as 9% when only 2% USPS data is used for training. This kind of classification with rare samples are common for applications like object recognition. Data Bio and Letter demonstrate medium difference (between 1 - 2%). But for other data sets like Yeast, the difference (< 1%) is negligible.

The difference diminishes as training data increases. This is common for all data sets. When training samples are moderately large, kernel regularization actually has no much effect. It works only when the training samples are few.

Which model excels?

Here, we study which model (Independent, Partial or Same) excels if there's a difference. In Table 3-5, the entries in bold AUC

denote the best one in each setting. It is noticed that Same Model tends to be the winner or a close runner-up most of the time. This trend is observed for almost all the data. Figure 2 shows the average performance and standard deviation of different models when 10% of Ligand data are used for training. Clearly, a general trend is that sharing the same kernel is likely to be more robust compared with Independent Model. Note that the variance is large because of the small sample for training. Actually, Same Model performs best or close in 25 out of 30 trials.

So it is a wiser choice to share the same kernel even if binary classification tasks are quite different. Independent Model is more likely to overfit the data. Partial model, on the other hand, takes the winner only if it is close to the same model (sharing 90% kernel as in Table 4). Mostly, its performance stays between Independent and Same Model.

Why is Same Model better?

As have demonstrated, Same Model outperforms Partial and Independent Model. In Table 2, we show the average kernel weights of 30 runs when 2% of USPS data is employed for training. Each column stands for a kernel. The weights for kernel 8-10 are not presented as they are all 0. The first 2 blocks represents the kernel weights of each class obtained via Independent and Partial Model sharing 50% kernel, respectively. The row follows are the weights produced by Same Model. All the models, no matter which class, prefer to choose K5 and K6. However, Same Model assigns a very large weight to the 6-th kernel. In the last row, we also present the weight obtained when 60% of data is used for training, in which case Independent Model and Same Model tend to select almost the same kernels. Compared with others, the weights of Same Model obtained using 2% data is closer to the solution obtained with 60% data. In other words, forcing all the binary classification tasks to share the same kernel is tantamount to increasing data samples for training, resulting in a more robust kernel.

Which model is more scalable?

Regularization on kernel difference seems to affect marginally when the samples are more than few. Thus, a method requiring less computational cost is favorable.

Our algorithm consists of multiple iterations. In each iteration, we need to solve k SVMs given fixed kernels. For each binary classification problem, combining the kernel matrix costs O(pn2 ). The time complexity of SVM is O(nη ) with η ∈ [1, 2.3] [Platt, 1999]. After that, a LP with O(pk) variables (the kernel weights) and increasing number of constraints needs to be solved. We notice that the algorithms terminates with dozens of iterations and SVM computation dominates the computation time in each iteration if p << n. Hence, the total time complexity is approximately O(Ikpn2 ) +O(Iknη ) where I is the number of iterations.

As for Same Model, the same kernel is used for all the binary classification problems and thus requires less time for kernel combination. Moreover, compared with Partial Model, only O(p), instead of O(pk) variables (kernel weights), need to be determined, resulting less time to solve the LP. With Independent Model, the total time for SVM training and kernel combination remains almost the same as Partial. Rather than one LP with O(pk) variables, Independent needs to solve k LP with only O(p) variables in each iteration, potentially saving some computation time. One advantage of Independent Model is that, it decomposes the problem into multiple independent kernel selection problem, which can be paralleled seamlessly with a multi-core CPU or clusters.

In Figure 3, we plot the average computation time of various models on Ligand data on a PC with Intel P4 2.8G CPU and 1.5G memory. We only plot Partial model sharing 50% kernel to make the figure legible. All the models yield simi-

Table 4: Bio Result

Table 5: USPS Result

lar magnitude with respect to number of samples, as we have analyzed. But Same Model takes less time to arrive at a solution. Similar trend is observed for other data sets as well.

Same Model, with more strict constraints, is indeed more efficient than Independent and Partial model if parallel computation is not considered. So in terms of both classification performance and efficiency, Same model should be preferred. Partial Model, seemingly more reasonable to match the relationship between labels, should not be considered given its marginal improvement and additional computational cost. This conclusion, as we believe, would be helpful and suggestive for other practitioners.

A special case: Average Kernel

Here we examine one special case of Same Model: average of base kernels. The first block of Table 6 shows the performance of MKL with Same Model compared with average kernel on Ligand over 30 runs. Clearly, Same Model is almost always the winner. It should be emphasized that simple average actually performs reasonably well, especially when base kernels are good. The effect is mostly observable when samples are few (say only 10% training data). Interestingly, as training samples increases to 60%-80%, the performance with Average Kernel decreases. However, Same Model's performance improves consistently. This is because Same Model can learn an optimal kernel while Average does not consider the increasing label information for kernel combination.

A key difference between Same Model and Average Kernel is that the solution of the former is sparse. For instance, Same Model on Ligand data picks 2-3 base kernels for the final solution while Average has to consider all the 15 base kernels.

For data like microarray, graphs, and structures, some specialized kernels are computationally expensive. This is even worse if we have hundreds of base kernels. Thus, it is desirable to select those relevant kernels for prediction. Another potential disadvantage with Average Kernel is robustness. To verify this, we add an additional linear kernel with random noise. The corresponding performance is presented in the 2nd block of Table 6. The performance of Average Kernel deteriorates whereas Same Model's performance remains nearly unchanged. This implies that Average Kernel can be affected by noisy base kernels whereas Same Model is capable of picking the right ones.

6 Conclusions

Kernel learning for multi-label or multi-class classification problem is important in terms of kernel parameter tuning or heterogeneous data fusion, whereas it is not clear whether a specific kernel or the same kernel should be employed in practice. In this work, we systematically study the effects of different kernel sharing strategies. We present a unified framework with kernel regularization such that flexible degree of kernel sharing is viable. Under this framework, three different models are compared: Independent, Partial and SameModel. It turns out that the same kernel is preferred for classification even if the labels are quite different.

When samples are few, Same Model tends to yield a more robust kernel. Independent Model, on the contrary, is likely to learn a 'bad' kernel due to over-fitting. Partial Model, occasionally better, lies in between most of the time. However, the difference of these models vanishes quickly with increasing training samples. All the models yield similar classification performance when samples are large. In this case, Independent and Same are more efficient. Same Model, a little bit surprising, is the most efficient method. Partial Model, though, asymptotically bears the same time complexity, often needs more computation time.

It is observed that for some data, simply using the average kernel (which is a special case of Same Model) with a proper parameter tuning for SVM occasionally gives reasonable good performance. This also confirms our conclusion that selecting the same kernel for all labels is more robust in reality. However, this average kernel is not sparse and can be sensitive to noisy kernels. In this work, we only consider kernels in the input space. It could be interesting to explore the construction of kernels in the output space as well.

Acknowledgments

This work was supported by NSF IIS-0612069, IIS-0812551, CCF-0811790, NIH R01-HG002516, and NGA HM1582-081-0016. We thank Dr. Rong Jin for helpful suggestions.

A Proof for Theorem 3.1

Proof. Based on Eq. (4), (5) and (6), we can assume

Let Gt (α) = [αt ]T (Gt ◦ yt [y]T ) αt and Gti (α) as in Eq. (8). Then Eq. (3) can be reformulated as:

It follows that the 2nd term can be further reformulated as

By adding constraints as

We thus prove the Theorem.