Multi-Kernel Multi-Label Learning with Max-Margin Concept Network

1 Introduction

For many real-world applications, semantics richness requires multiple labels to sufficiently describe the data, thus one object ( image, video, text, etc.) might be related with more than one semantic concepts simultaneously. For example, in the image annotation task, an image that shows a bird flying in the sky is associated with two labels (concepts) bird and sky at the same time. Multi-label learning deals with the data associated with more than one concepts simultaneously and has already been applied to web page classification, text categorization, image annotation, bioinformatics etc. One strategy for multi-label learning is to deem multi-label problem with c labels as a classification problem with 2c classes, and standard multi-class algorithms can be applied straightforward [Tsoumakas and Katakis, 2007]. The main drawbacks of this strategy include: 1) high cost of computation; 2) most classes might have no positive training data [Hariharan et al., 2010]. An alternative strategy for multi-label learning is to independently decompose the task into c binary classification problems, one per label [Boutell et al., 2004; Li et al., 2009]; however, it would lose the correlations between labels, which is significant to the performance of multi-label classification. For example, the concepts bird and sky often cooccur in the same image, while bird and office may seldom co-occur. To exploit the correlations between labels, many algorithms have been introduced recently, such as CMLF (Collective Multi-Label with Features) [Ghamrawi and McCallum, 2005], M3N(Max-Margin Markov Network) [Tasker et al., 2003], SSVM(Structural SVM ) [Tsochantaridis et al., 2004], SMML (Structured Max-Margin Learning) [Xue et al., 2010] and CML(Correlative Multi-Label framework) [Qi et al., 2007]. Another strategy is to transform multi-label learning into a ranking problem(ranking the proper labels before others for each data) [Elisseeff and Weston, 2002]. The above existing algorithms all employ the same feature extractor for different concepts and ignore the similarity diversity, which might be unsuitable for the real applications. For example, suppose that there are two images: one contains the concepts sky and bird, the other contains the concepts sky and building. These two images are similar when the concept sky is concerned; however, they are dissimilar to each other when the concept bird or building is concerned.

It is well-accepted that extracting more suitable features and designing more accurate similarity functions play an essential role in achieving more precise classification [Sonnenburg et al., 2007]. With the proliferation of kernel-based methods such as SVM, kernel function or kernel matrix has been widely used to implement feature transformation or determine the data similarity. Many existing algorithms employ the same kernel for all the labels (concepts) and show that Gaussian kernel is powerful [Jebara, 2004]. However, the diverse data similarity cannot be characterized effectively by using one single kernel and multiple kernels are necessary [Tang et al., 2009; Bach et al., 2004]. To overcome the disadvantage of traditional one-kernel-fit-all setting, some algorithms learn multiple kernels for each label (concept) [Xiang et al., 2010; Rakotomamonjy et al., 2007]; however, the inter-label correlations are not leveraged sufficiently for achieving more effective multi-kernel learning.

In this paper, a novel method is developed for achieving Multi-Kernel Multi-Label Learning with Max-Margin Concept Network such that inter-label dependency and similarity diversity are sufficiently leveraged at the same time. The concept network is constructed for characterizing the inter-label correlations more effectively, so that we can leverage such inter-label correlations for classifier training and enhancing the discrimination power of the classifiers significantly. The site potentials encode the feature-label associations while the edge potentials actually capture the label-label correlations that are dependent on the features. A maximal margin approach is used to formulate the above site and the edge potentials. Based on the design of the potential functions in our model, we decouple our objective function label by label; nevertheless, the inter-label interactions remain to be captured, which differs in a crucial way from the state-ofart algorithms. In order to embed the label information and the inter-label (inter-concept) correlations, we learn specific kernels not only for each label but also for each pair of interrelated labels. On the other hand, those multiple kernels share the common basis which can be learned by spectral decomposition of a Gram kernel matrix. Furthermore, by learning the eigenfunctions of the kernels, the similarity between a new data point and the training samples can be computed in the online mode.

The rest of this paper is organized as follows: In Section 2 we formulate the proposed model for multi-kernel multilabel learning. We focus on the multi-kernel learning technique and model inference with eigenfunction in Section 3 and 4, respectively. Our experimental results on real datasets (web pages, images, music, and bioinformatics.) are given in Section 5. Finally, we conclude this paper in Section 6.

2 The ProposedModel

In a multi-label learning framework, multiple labels for each sample are represented as a c-dimensional binary vector y = [y1, . . . , yc], where yl = 1(l = 1, . . . , c) indicates that the sample belongs to the class l, and yl = 0 otherwise. We build a discriminative model θ⊤Φ(x, y) which scores the featurelabel pair (x, y), and the parameter vector θ can be learned from the labeled samples {(x1 , y1 ), . . . , (xn , yn )}. For any test sample x, the associated labels can be inferred by ˆy = arg maxy θ⊤Φ(x, y).

In real world, semantic concepts usually do not appear independently but occur correlatively. A concept network is constructed to characterize the inter-label correlations more precisely and to learn the inter-related classifiers in the feature space. Each concept (label) l corresponds to one certain node (site) in the concept network. If concepts l and t are inter-related, there is an edge between the corresponding two nodes, denoted by l ∼ t. Given n labeled training samples {(x1 , y1 ), . . . , (xn , yn )}, we can define empirical conditional probabilities p(t|l) = ∑ ni=1 yi l yit ∑ ni=1 yi l and p(l|t) = ∑ ni=1 yi l yit ∑ ni=1 yit , and then connect an edge between l and t if p(t|l)p(l|t) p(t|l)+p(l|t) > 0, where 0 is a predefined threshold. ℙ ℙ

The concept network consists of two components: concepts (labels) and the inter-concept correlations. To capture the feature-concept associations and the inter-concept correlations in a unified framework, our model is formulated as:

where σ is a trade-off parameter, πl = 1(yl=1) - ϵ1(yl=0) and π′ lt = 1(yl=yt=1) - ϵ′1(yl̸=yt). (1(·) is an indicator taking on value 1 if the predication is true and 0 otherwise.

0 < ϵ, ϵ′ < 1 are used to deal with class-imbalance by biasing toward the positive samples.) vl and wlt are the subvectors of θ associated with the node (label) l and the edge (label-label pair) l ∼ t on the concept network, respectively. ϕl(x) and ϕlt(x) are (nonlinear) functions mapping sample features x to kernel spaces with respective to the node l and the edge l ∼ t, respectively. Since there exists a gap between the similarity for observations and the similarity for semantic concepts in many applications, different concepts (labels) concern different features and it is better to learn different mapping functions for different concepts. We would employ multi-kernel technique to implement both the concept specific and the pairwise concept specific feature mappings (for detail see Section 3) such that similarity diversity can be effectively characterized.

The first part of Eq. (1) is the site potential of the concept network, which captures the association between the labels and the features, and maximizing the site potential is equivalent to maximizing the margin between sample x and the hyperplane for each concept in the kernel space. Meanwhile, the second part of Eq. (1) is the edge potential taking into account label-label correlations, where yl = yt = 1 means that semantic concepts l and t co-occur while yl ̸= yt indicates that one of these two concepts is present and the other is absent, so maximizing such edge potential is equivalent to maximizing the margin between the samples and the hyperplane which cuts the kernel feature space into two halves (one corresponding to yl = yt = 1 while the other yl ̸= yt). By considering both site and edge potentials in a unified framework, we sufficiently leverage the associations between features and labels, and the correlations among labels and their dependence on the features. To learn the proposed model, the objective function is defined as:

where ξ i is a slack variable, and θ⊤[Φ(xi , yi ) - Φ(xi , y)] can be viewed as the margin between the prediction and the true label. Δ(yi , y) = ∑cl=1 1(yi l ̸=yl) represents the multilabel loss scaling with the number of wrong labels in y.There are n × 2c constraints and the optimization problem is too complex to be solved directly. Based on the design of our model, we factor the proposed global model formulation as the sum of local models:

and each local model with respect to concept l is as follows:

where ϑl is the parameter sub-vector of θ corresponding to concept l, and Nl = {t|t ∼ l} denotes the set of related concepts for l. yl is the lth component of multilabel vector y, and yNl is the subvector of y corresponding the related concepts for l. Like [Xiang et al., 2010; Sontag et al., 2010], our optimization can be approximately decoupled into c interdependent subproblems. For each l ∈ {1, . . . , c},

Since yl, yi l ∈ {1, 0}, there are only two cases: either yl = yi l or yl = 1 -yi l . If yl = yi l , the constraints in (6) always hold; so, we can only focus on the case yl = 1 - yi l and the constraints in (6) can be further written as:

ϑ⊤l Ψl(xi , yi l , yiNl ) is the local model score based on the observation xi and the completely true labels, while ϑ⊤l Ψl(xi , 1 - yi l , yiNl ) is the local model score based on the observation xi and the almost true labels. In the decoupled formulation, the model parameter sub-vector ϑl can be learned with ease. Although the model parameter sub-vectors are learned label by label, the correlations between labels are still be taken into account due to the second item in the rightside of Eq. (4). Now, there are only n constraints in the optimization problem (5) s.t. (7) for each l ∈ {1, . . . , c}, which is similar to 2-class SVM. The dual of the optimization problem is as follows:

where αi l denotes the dual variable, and

The primal variable ϑl can be computed from the dual variables: ϑl = ∑ni=1 αi l ΔΨil . According to (4) and (9), we have:

where Kl(xi , xj ) = ϕ⊤l (xi )ϕl(xj ), Klt(xi , xj ) = ϕ⊤lt (xi )ϕlt(xj ). The coefficients βl and β′ lt can easily be derived from (4) and (9). (For saving space, we do not present them here.)

3 Multi-Kernel Learning

Similarity is important to the classification performance and Gaussian (RBF) kernel actually characterizes the similarity between samples. We first define an original kernel regardless of label information as: K(xi , xj ) = ϕ⊤(xi )ϕ(xj ) = exp{-ρd(xi , xj )}, where d(xi , xj ) denotes the distance between xi and xj , and ρ is a scaling parameter. K(xi , xj ) measures the similarity between samples xi and xj . For all samples in the training set {x1 , ..., xn }, the pairwise similarities consist a Gram kernel matrix K with K(i, j) = K(xi , xj ), which is symmetric and can be decomposed as: K = ∑nk=1 ηkuku⊤k , where uk is the eigenvector with respective to eigenvalue ηk. Let uk(i) and uk(j) denote the ith and jth components of the eigenvector uk respectively, we get K(i, j) = ∑nk=1 ηkuk(i)uk(j). It has been shown that the eigenvalue spectrum of the Gram matrix decays rapidly when the RBF kernel is employed [Williams and Seeger, 2000]. Thus, to reduce the complexity, we can also just select m dominant eigenvectors with large eigenvalues: K ≈ ∑mk=1 ηkuku⊤k and K(i, j) ≈ ∑mk=1 ηkuk(i)uk(j), (m < n).

In order to incorporate the label information, we learn the concept-specific kernel matrix for the l-th label, denoted as Kl, by maximizing the similarities between data with the same label. Meanwhile, inspired by [Liu et al., 2009; Sun et al., 2010; Yan et al., 2007], we require Kl to be in the neighborhood of the original Gram matrix K. The cost function is as follows:

where Y·l is the l-th column of the matrix Y ∈ {0, 1}n×c . Y·l corresponds to the labels with respect to the l-th concept for all samples and the quadratic form Y ⊤ ·l KlY·l measures the sum of the similarities between data with the label l, the Frobenius matrix norm ∥∥Kl -K∥∥2F measures the divergence between Kland K, and γl is the controlling parameter. Assume that the concept-specific kernel matrix Kl shares the common basis as K: Kl = ∑mk=1 ωlkuku⊤k , then the cost function (11) can be expressed as:

Similarly, to sufficiently leverage the correlations among the semantic concepts and their dependence on the input features, the pairwise label specific kernel matrix Klt can be learned by maximizing the following cost function:

where Υlt is also the controlling parameter and the quadratic form Y ⊤ ·l KlY·t measures the sum of the similarities between data with the label l and t. Maximizing Y ⊤ ·l KlY·t means that two images should be similar in the kernel space if they are associated with two inter-related labels l and t respectively. It will enhance the discrimination power of the classifiers by learning from the samples associated with other related labels on the concept network. Again, we let Klt share the common basis as K: Klt = ∑mk=1 ζltkuku⊤k , and the cost function (13) is rewritten as:

Both (12) and (14) are optimization problems of quadratic functions and can be solved directly.

4 Model Inference by Eigenfunction: Online Mode

For any new image xnew , the inference problem is to find the optimal label configuration ˆynew = argmaxy θ⊤Φ(xnew , y). The size of multi-label space is exponential to the number of classes, and it is intractable to enumerate all possible label configurations to find the best one. Therefore we employ an approximate inference technique called Iterated Conditional Modes (ICM) [Winkler, 1995] due to its effectiveness. First, we initialize a multi-label configuration (e.g., determine each label by maxyl πlv⊤ l ϕl(x) without allowing for inter-label dependency initially ). Then, in each iteration, given yNl , we sequentially update yl using the local model: if ϑ⊤l Ψl(xnew , yl = 1, yNl ) is larger than ϑ⊤l Ψl(xnew , yl = 0, yNl ) then yl = 1; otherwise yl = 0. Since ϑl = ∑ni=1 αi l ΔΨil , the prediction rule actually uses kernels and dual variables as well. To get Kl(xnew , xi ) and Klt(xnew , xi ), we first calculate: K(xnew , xi ) = exp{-ρd(xnew , xi )}. According to [Williams and Seeger, 2000], the eigenfunctions of kernel K satisfy:

where φk(.) is a eigenfunction and p(x) is the probability density in the input space. p(x) can be estimated by empirical distribution, and Eq. (15) can be approximated as:

Then 1n K[φk(x1 ), ..., φk(xn )]⊤ = k[φk(x1 ), ..., φk(xn )]⊤ because K(i, j) = K(xi , xj ). We can find k = 1n ηk and φk(xi ) = uk(i), where ηk is the eigenvalue of the Gram matrix K and uk(i) is the ith component of the eigenvector uk. Using Eq. (16), for any new data

Thus Kl(xnew , xi ) and Klt(xnew , xi ) can be computed as follows:

5 Experiments

In the experiments, we compare our method ′Ours′ with the state-of-the-art methods: 1) RML [Petterson and Caetano, 2010]; 2) ML-KNN [Zhang and Zhou, 2007]; 3) Tang's method [Tang et al., 2009]; and 4) RankSVM [Elisseeff and Weston, 2002]. We consider four real applications: web page classification, image annotation, music emotion tagging, and gene categorization.

Web Page Classification. We first conduct the experiment on a collection of eleven datasets 1 for real Web pages linked from the domain yahoo.com. Each dataset contains 5000 documents (2,000 for training and 3,000 for testing), and about 15% ∼ 45% of them belong to multiple categories simultaneously. Each Web page uses the "Bag-of-Words" representation [Dumais et al., 1998]. The detailed description of these datasets is given in Table 1.

Image Annotation. The experiments are conducted on two image datasets: MSRC (MicroSoft Research Cambridge) and Scene. 1) MSRC dataset contains 591 images (300 for training and 291 for testing) with 23 concepts in total. There are about 3 tags on average per image. We ignore the concepts horse and mountain since they have few positive samples. Thus there are totally 21 concepts. For each MSRC image, we first extract 44-dim features including RGB histogram, HSV histogram, HUE histogram, SAT histogram, mean texture response, and texture response histogram. 2) The Scene dataset [Boutell et al., 2004] contains 2407 images (1211 for training and 1196 for testing) with totally 6 labels. In the LUV space, each image is divided into the 7×7 grids and the mean and variance of each band are computed. Thus, each Scene image is described by 294-dim feature vector.

Music Emotion Tagging. The dataset Emotion 2 used for this task consists of 593 songs (391 for training and 202 for test). Each sample is represented by a 72-dimensional feature vector. There are 6 types of emotions in total: amazed-surprised, happy-pleased, relaxing-calm, quiet-still, sad-lonely, and angry-fearful.

Gene Categorization. The final experiment is to predict the gene functional classes, which is conducted on the microarray expression dataset called Yeast 3 with 2,417 samples (

1 http://www.kecl.ntt.co.jp/as/members/ueda/yahoo.tar.gz

2 http://mulan.sourceforge.net/datasets.html

3 http://mips.gsf.de/proj/yeast

1,500 for training and 917 for testing). Each sample is represented by a 103-dimensional vector. The average number of labels per gene in the training set is about 4, and the total number of labels is 14.

Table 2 shows the experimental results of our method in comparison with other related methods on yahoo.com Web Pages Datasets. Table 3 and 4 give the results on MSRC, Scene, Music-Emotion, and Yeast datasets. We use multilabel classification criteria Micro-F1, Macro-F1, and Hamming Loss to evaluate the performance: Micro-F1 computes the F1 measure on the predictions of different labels as a whole; Macro-F1 averages the F1 measure on the predictions of different labels; Hamming Loss calculates how many times an instance-label pair is misclassified [Zhang and Zhou, 2010; Sun et al., 2010]. On each evaluation criterion, the best result is highlighted in boldface. Best parameters are chosen by tuning in experiments. In our method, the threshold 0 is concerned with the concept network construction and the parameter σ in Eq. (1) controls the influence of label-label correlation on multi-label learning. γl in Eq. (11) and Υlt in Eq. (13) are the trade-off between the common kernel and the multiple specific kernels. From the results, we find that our method performs better than other methods in most cases. Our method sufficiently leverages feature-label association, inter-label dependency, and similarity diversity at the same time, which inherits all merits of the state-of-the-art methods. ℙ

6 Conclusions

Inter-label dependency and similarity diversity are simultaneously leveraged in the proposed multi-kernel multi-label learning method. A concept network is first constructed for characterizing the inter-label correlations effectively, and the maximal margin technique effectively captures the featurelabel associations and the label-label correlations. By decoupling the multi-label learning task into inter-dependant subproblems label by label, the proposed method learns multiple interrelated classifiers jointly. Specific kernels not only for each label but also for each pair of inter-related labels are learned to embed the label information and the inter-label (inter-concept) correlations. Similarity between a new data point and the training samples can be computed easily via the eigenfunctions of the kernels.

Acknowledgments

We would like to thank the anonymous reviewers for their helpful comments. This work was supported in part by the 973 Program (No.2010CB327906), the NSF of China (No.60903077 and No.60873178), the STCSM's Innovation Program(No. 10511500703), and the Shanghai Leading Academic Discipline Project (No.B114).