Label-Sensitive Task Grouping by Bayesian Nonparametric Approach for Multi-Task Multi-Label Learning

1 Introduction

Recent years have witnessed the vast amount of interest and research in multi-label learning for various kinds of applications, such as image annotation [Gong et al., 2013], gene annotation [Li et al., 2012], sentiment classification [Liu and Chen, 2015] and so on. A common approach to multi-label classification is to transform the multi-label data set to one multi-class data set or multiple single-label data sets. In this Label-Sensitive Task Grouping

This work was partially supported by the National Key R&D Program of China (Grant No. 2017YFB1001801), the National Natural Science Foundation of China (Grant Nos. 61672278, 61473273, 61773361, 61373128, 61321491), the science and technology project from State Grid Corporation of China (Contract No. SGSNXT00YJJS1800031), the NSFC 91746301, the Collaborative Innovation Center of Novel Software Technology and Industrialization, and the Sino-German Institutes of Social Computing. The corresponding authors are Wenzhong Li (lwz@nju.edu.cn) and Fuzhen Zhuang (zhuangfuzhen@ict.ac.cn). Fuzhen Zhuang is also with University of Chinese Academy of Sciences, Beijing, 100049, China.

• (b) Multi-Task Multi-Label learning.

Figure 1: Example of context recommendation.

faction, single-label classifiers can be applied independently, such as the binary relevance method [Boutell et al., 2004], label powerset method [Tsoumakas et al., 2011], etc. Several works were proposed to exploit label correlations for multi-label classification. For example, the Classifier Chain model and its variants are utilized to depict the label correlations [Dembczynski et al., 2010; Read et al., 2011]. In addition, the label dependencies can be further represented based on Bayesian graphical model or conditional random field [Ghamrawi and McCallum, 2005; Zhang and Zhang, 2010; Guo and Gu, 2011]. Moreover, a Bayesian nonparametric approach was introduced to capture the feature-label correlation patterns for multi-label classification [Nguyen et al., 2016].

However, most existing multi-label learning models focus on single-task learning problems. They assume different tasks are independent and learn a classification model for each task individually. In practice, tasks could be highly correlated, and the performance of multiple classification tasks can be improved by learning them jointly. For example, in the spamfilter problem, each user receives only a portion of spams, and learning a model across multiple users (tasks) can obtain a stronger filter for spam detection. The Multi-task learning approach provides a good solution to explore similarities among multiple tasks [Bakker and Heskes, 2003; Xue et al., 2007; Kim and Xing, 2010; Chen et al., 2012], which can be incorporated with multi-label learning to learn knowledge from similar tasks to enhance the overall performance.

Taking the Context Recommendation Problem [Zheng et al., 2014] as an example: given a movie item information, we want to recommend suitable contexts (time, location, companion, etc) for a user to watch the movie. As shown in Fig. 1(a): the problem corresponds to learn a mapping {User, Item}→ {Context} that takes user(s) and movie item(s) as input to suggest a list of contexts for the user. Here user information includes the user ID, the user profile (e.g., gender), and movie item information includes the movie ID, the actors, the director, the ratings, etc. The suggested contexts to watch the movie could be the Day (e.g., "Weekend" or "Weekday"), the Location (e.g., "Cinema" or "Home"), the Companion (e.g., "Kids" or "Spouse"), etc. Traditionally, we can apply single-task learning to training a multi-label classification model for each user individually. However, when the data set is sparse (e.g., each user has very few items and contexts), the performance could be degraded due to the shortage of training instances. To overcome the drawback, we adopt the idea of multi-task learning to explore the correlations among similar tasks. Fig. 1 shows the idea of treating context recommendation as a multi-task multi-label learning problem. The tasks are latently related label-sensitively, which means the tasks can be clustered into different groups with respect to different labels, e.g., in Fig. 1(b), Task 1 and 3 are clustered into a group and Task 2 and M are grouped together according to the context of "Day", while Task 1, 3 and M are grouped together with respect to the context of "Location", etc. Intuitively, by grouping similar users/tasks together and learning their models jointly using a shared representation, the training data for each task is strengthened and the overall performance of multiple classification tasks can be improved.

Along this line, in this paper, we propose a LABel-sensitive TAsk Grouping framework (LABTAG for short) by Bayesian nonparametric approach for multi-task multi-label classification. The reason for adopting the Bayesian nonparametric approach is that it can estimate the unknown number of featurelabel patterns and the different unknown number of task clusters under different labels. To this end, we place one Dirichlet process (DP) prior on the distributions of features and labels to capture the feature-label patterns, and another DP prior on parameters of features to clustering similar tasks under different labels, respectively. Therefore, the proposed LABTAG model not only explores the label correlations but also takes the advantage of label-sensitive task grouping. For the model solution, we utilize the variational inference to estimate the parameters in the graphical model to form a learning algorithm. Finally, we conduct extensive experiments on three public data sets to demonstrate the effectiveness of the proposed model compared with various of baseline approaches.

2 RelatedWork

Multi-label Learning. A straightforward approach to multilabel learning is to transform the multi-label data set to one or multiple single label data sets, which is called the problem transformation methods [Zhang and Zhou, 2014]. Normally, label powerset method [Tsoumakas et al., 2011] transforms the multi-label data set to a multi-class classification problem, in which each class is a unique set of labels that exist in a multi-label training set. Apparently, label powerset method could face the problem of exponential explosion when the label space is too large. In contrast, binary relevance [Boutell et al., 2004] is to transform the multi-label data sets to k binary classification data sets, where k is the number of labels. However, it ignores the fact that some labels are more likely to co-exist in the instances. To parameterize the label co-occurrences, Ghamrawi et al. [Ghamrawi and McCallum, 2005] proposed a conditional random field based multi-label classification model. Zhang et al. [Zhang and Zhang, 2010] utilized a Bayesian network structure to encode the conditional dependencies of the labels and the features. Nguyen et al. [Nguyen et al., 2016] proposed a Bayesian nonparametric approach to learn the number of label-feature correlation patterns automatically. However, the most previous multi-label classification models focus on single-task learning problems while ignoring modeling the similarity among tasks.

Multi-task Learning. The multi-task learning approach try to solve multiple learning tasks at the same time, while exploiting commonalities and differences across tasks. The main purpose of the multi-task learning is to capture the similarity information or shared structures among multiple tasks to enhance the learning performance [Zhou et al., 2012]. Typical shared structures include fully connected structure (all tasks are related) [Lawrence and Platt, 2004; Evgeniou and Pontil, 2004], clustered structure [Bakker and Heskes, 2003], tree structure [Kim and Xing, 2010], network structure [Chen et al., 2012], etc. Particularly, Xue et al. [Xue et al., 2007] proposed a multi-task learning model with Dirichlet process prior to identify groups of related tasks automatically. Different from their works, in this paper, we adopt the multi-task learning to jointly learn several related multi-label classification tasks based on the Bayesian nonparametric approach in a generalized framework.

3 Multi-taskMulti-label ClassificationModel

3.1 ProblemDescription

Given M tasks with multi-label classification problem, let X = {X1,X2, · · · ,XM} denote all domains of data, Y = (0, 1)C be the labels, C be the number of labels, Nm be the number of instances in the m-th task, where Xm = {xmn, ymn}|Nm n=1 and ymn ∈ Y , the goal of the multi-task multi-label learning is to explore the label correlation and task correlation to learn a function that maps xmn to multi-label vector ymn: f(xmn) → ymn.

3.2 Model Overview

We build a multi-task multi-label model with Dirichlet process priors to jointly learn the multiple multi-label classification problems. The graphical model is shown in Fig. 2, which consists of two parts:

• Firstly, a Dirichlet process prior is placed on parameters φ and ψ. {φmk, ψmk} are feature-label pattern pairs, which is similar with literature [Nguyen et al., 2016].

For different tasks, different feature-label patterns are captured. The number of feature-label patterns can be determined automatically after training due to the nonparametric setting;

• Then we place another Dirichlet process prior on the parameters {wct} to implement label-sensitive task grouping. Under different labels, the tasks can be clustered into different groups according to the between-task similarity. The variable {smc} indicates which cluster task m belongs to under label c.

3.3 Generative Process

The generative process of the proposed multi-task multilabel model is shown as follows. Given the context recommendation as an example. For each task (e.g., user) m, we utilize the stick-breaking view [Ishwaran and James, 2001] of the Dirichlet process to capture the feature-label patterns firstly. Therefore, We sample vmk from the Beta dis-

Then we sample ψmk, φmk from the base Dirichlet distribution Dir(δ), Dir(ϖ) respectively, k = 1, · · · ,∞. In addition, the tasks are latently related label-sensitively, which means the parameters may be shared between different tasks under different labels. Therefore, we place another Dirichlet process prior on the parameter {wct} for each label c. Similarly, we draw θct from the Beta distri-

then draw wct from Gaussian distribution N(µ0,Σ0), t = 1, · · · ,∞, c = 1, · · · ,C. In the next step, we sample the indicator variable smc ∼ Mult(1; π∗ c1 , · · · πc∞∗). Then we record the parameters wm = {wc,smc }|Cc=1 . Finally, for each instance n in task m, we draw the indicator variable zmn ∼ Mult(1; πm1, · · · πm∞). Next we generate the feature xmn (e.g., the item content information): xmn ∼ Mult(φzm,mn ), and the corresponding label ymn (e.g., the contexts information) : ymn ∼ Mult(ψm,zmn . ∗ σ(xTmn ∗ wm)), where σ(·) is the sigmoid function. The details of the generative process can be found in Alg. 1.

3.4 Learning Algorithm

In the Bayesian approach, the calculation of the posterior distribution of the latent variables given the observed variable and the hyper-parameters is critical. However, the posterior distribution does not have an analytic form in most cases [Xue et al., 2007]. Variational inference and Monte Carlo Markov

Algorithm 1 The generative process of the proposed LABTAG model

• 1: for each task mdo
• 2: Draw vmk independently from Beta distribution Beta(1, α), k = 1, · · · ,∞,m= 1, · · · ,M.
• 3: πmk = vmk k-1 ∏ i=1 (1- vik), k = 1, · · · ,∞.
• 4: Draw ψmk independently from Dirichlet distribution Dir(δ), k = 1, · · · ,∞,m= 1, · · · ,M.
• 5: Draw φmk independently from Dirichlet distribution Dir(ϖ), k = 1, · · · ,∞,m= 1, · · · ,M.
• 6: for each label c do
• 7: Draw θct independently from Beta distribution Beta(1, β), t = 1, · · · ,∞, c = 1, · · · ,C.

• 9: Drawwct independently fromGaussian distribution N(µ0,Σ0), t = 1, · · · ,∞, c = 1, · · · ,C.
• 10: smc ∼ Mult(1; π∗ c1 , · · · π∗ c∞),m= 1, · · · ,M. 11: wm = {wc,smc }|Cc=1 .
• 12: end for
• 13: for each instance n in task m do

• 15: xmn ∼ Mult(φm,zmn ).
• 16: ymn ∼ Mult(ψm,zmn . ∗ σ(xTmn . ∗ wm)).
• 17: end for
• 18: end for

chain (MCMC) sampling are two widely used methods for Bayesian inference. However, when faced with Dirichlet process prior, MCMC method is slow and difficult to converge while variational inference methods are deterministic compared with MCMC sampling methods [Ishwaran and James, 2001; Blei et al., 2006].

Generally, variational inference method is to approximate the posterior distribution p of interest using a variational distribution q [Jordan et al., 1999; Ghahramani and Beal, 2001]. By minimizing the Kullback-Leibler (KL) divergence between p and q, the calculation of the posterior distribution can be transformed to an optimization problem. Particularlly, by assuming that the variational distribution could be factorized with different parts in the exponential family, the analytic form of the variational distribution q could be obtained. Under this assumption, the factorized variational distribututions of the LABTAG model are as follows:

where q(vmk) are Beta distributions with parameter (rm 1k , rm 2k ); q(ψmk) are dirichlet distributions with parameter ∼ ψmk; q(φmk) are dirichlet distributions with parameter ∼ φmk ;

q(zmn) are multinomial distributions with parameter ∼ zmn; q(θct) are Beta distributions with parameter (τ c 1t , τ c 2t ); q(wct) are normal distributions with parameters ( ∼ µct, ∼ Σct); q(smc) are multinomial distributions with parameter ∼ smc. It is worth noting that we utilize truncated stick-breaking representations here [Blei et al., 2006]. In the proposed model, K and T ∗ are all truncation levels which could be set freely. Next, the estimations of the parameters of the variational distribution will be introduced in detail.

Estimating the parameters of q(vmk):

From the Bayesian nonparametric setting, q(vmk) is the same distribution type as P(vmk|z, α), in which the difference is the parameter. According to Bayes' theorem [Rosen, 2007], the posterior distribution can be written in exponential family as follows:

According to the principle of the variational inference [Blei et al., 2006], the parameters of the variational distribution q(vmk) equals to the expectation of the natrual parameter of the posterior distribution under the variational distribution and can be calculated as following equations:

Estimating the parameters of q(φmk):

Again, the posterior distribution P (φmk|z, X, ϖ) is a Dirichlet distribution which is also in the exponential family. Hence, the parameters ∼ φmk of variational distribution q(φmk) can be obtained as follows:

Estimating the parameters of q(ψmk):

As disscussed before, in different tasks, different feature-label patterns can be captured by (φmk, ψmk). Similar with the estimation of ∼ φmk, ψmk also has a Dirichlet process prior, therefore, ∼ ψk can be estimated similarly:

Estimating the parameters of q(zmn):

The posterior of zmn is a multinomial distribution as follows:

Hence ∼ zimn equals to the expectation of the natural parameter of the posterior distribution under the variational distribution q:∼

in which Ψ(·) is the digmma function, which is the first derivative of the log Gamma function. C is the number of the labels and D is the number of the features.

Estimating the parameters of q(θct):

Similar with estimating r, τ is calculated as follows:

Estimating the parameters of q(wct):

Since the sigmoid function is not in the exponential family, it is difficult to transform the the posterior distribution of P(wtc|·) to a exponential expression. Hence, we utilize a variational approximation to calculate the posterior distribution [Jaakkola and Jordan, 1997; Xue et al., 2007], which is shown as follows.

Estimating the parameters of q(smc):

smc is another indicator variable which reveals which cluster each task belongs under different labels. Similar with estimat-

3.5 Prediction

Given the learned parameters Θ = {z, s, v, φ, ψ, θ, w} and a new test sample xm,n∗, we need to predict the corresponding label vector ym,n∗ ∈ (0, 1)C . We assume ym,n∗

is drawn from a multinomial distribution with parameters [ς 1m,n∗, . . . , ς Cm,n∗], in which ς cm,n∗ can be calculated as: ς cm,n∗ ∝ P(ycm,n∗ = 1|xm,n∗, ∼µ, ∼Σ, ∼s) × P(ycm,n∗ = 1| ∼z , ∼φ, ∼ ψ). Particularly, since P(ycm,n∗ = 1|xm,n∗, ∼µ, ∼Σ, ∼s) does not have a accurate analytic form, we utilize the approx-

imation form as follows: T ∗∑ t=1 ∼ stmc σ( ∼ µct xm,n∗ √1+ P I 8 xTm,n∗ ∼ Σct xm,n∗ )

according to literature [Xue et al., 2007].

4 Experimental Evaluation

4.1 Data Preparation

We use three public data sets for the performance evaluation, including TripAdvisor, LDOS-CoMoDa and Enron Corpus data sets, to evaluate the performance of all compared algorithms. TripAdvisor and LDOS-CoMoDa are two context-aware data sets, which are used for context recommendation systems [Zheng et al., 2014]. TripAdvisor is a hotel rating data set, in which the content information includes user country, rating, etc. and the context is the trip type. LDOS-CoMoDa [Adomavicius and Tuzhilin, 2015] is a movie rating data set, which utilizes the movie contents including movie year, genre, actor, etc. to recommend the contexts consisting of time, location, day and companion. Finally, the Enron Email Corpus contains email information (email content and recipients) from Enron [Klimt and Yang, 2004; Carvalho and Cohen, 2007]. The statistics of three data sets are shown in Table 2. These three data sets contain different number of tasks ranging from 10 to 46, different numbers of labels and features, which are able to prove the robustness of the proposed model.

4.2 Baselines and EvaluationMetrics

Baselines. We compare our model LABTAG with the following baselines,

• Binary Relevance (BR) transforms the multi-label data set to k single label data sets, then adopts some basic algorithms on each data set, such as Decision Tree, SVM, Logistic Regression, etc., finally combines the results to

form the prediction. In our experiment setting, the Decision Tree is used as the basic algorithm.

• ML-kNN [Zhang and Zhou, 2007] is from the traditional KNN algorithm, which utilizes k nearest neighbors in the training data to predict the instances in the test data.
• Conditional Dependency Networks (CDN) [Guo and Gu, 2011] is a cyclic directed graphical model by considering the label dependency, in which Gibbs sampling is utilized for inference.
• Bayesian Nonparametric Multi-label Classification (BNMC) [Nguyen et al., 2016] is a Bayesian nonparametric framework which can learn the unknown number of label correlations automatically and handle the missing label samples naturally.

We utilize MEKA toolbox [Read et al., 2016] for the implementation of BR and CDN, and download the Matlab code from the author's website for BNMC and ML-KNN.

Evaluation Metrics. We adopt five widely used metrics for performance evaluation [Zhang and Zhou, 2014], including Accuracy, F1-score, Hamming loss, One-error and Rank loss. For Accuracy and F1-score, larger value indicates the better performance, while for Hamming loss, One-error and Rank loss, smaller value indicates the better performance.

The hyper-parameter settings of LABTAG model are as follows: α = 1, δ = 0.01, ϖ = 0.07, β = 1, µ0 = 0, Σ0 = 10I. The truncation threshold is set as 0.001×#Train and the learning rate is set as 0.01. In each task, 50% data are used for training and the remaining 50% for test.

4.3 Numerical Results

The comparison of the classification performance between the proposed model and the baseline methods is shown in Table 1, and the best results w.r.t each evaluation metric are marked in bold. Besides, Fig. 5 shows the mean Accuracy and

(a) Label 6 in Enron dataset.

(c) Label 47 in Enron dataset.

(d) Label 1 in LDOS dataset.

Figure 4: Hinton diagram for the between-task similarity in TripAdvisor dataset.

Hamming Loss under different training dataset sizes. From the results in Table 1 and Fig. 5, we have the following insightful observations,

• Our model LABTAG can achieve the best performance compared with all baselines on three data sets in term of all five metrics, except that on LDOS-CoMoDa data set, BNMC obtains a better result in term of Hamming loss and ML-kNN obtains a better result in term of One-error.
• LABTAG outperforms BR, CDN, BNMC, and MLkNN, which shows the importance of applying multitask learning to handling multi-label classification problem. The reason is that the small number of instances in each task can lead to under-fitting if each task is trained separately, while LABTAG can learn multiple tasks jointly to enhance performance. Similar tasks can share the same model parameters under different labels, in which one task could benefit the knowledge from other similar tasks.
• The success of LABTAG also attribute to the adoption of Bayesian nonparametric approach, based on which we do not need to specify the number of clusters.
• The proposed LABTAG model can also perform better than all baselines under different sizes of training data, even when the size of training data is small.

4.4 Model Analysis

To explain the cluster structures of multiple tasks under different labels in each data set, we calculate the between-task similarity as follows: (1) We obtain the results of 10 random trials; (2) In each random run, we output { ∼ stmc }T ∗ t=1 which indicates the probability that task m belongs to cluster t under label c. Hence we utilize argmaxt ∼ stmc as the cluster index of task m under label c; (3) We construct a task similarity matrix, in which the element (i, j) records the number of occurrences that task i and task j are grouped into the same cluster among the total 10 random runs. The Hinton diagram for the between-task similarity matrices of different data sets is shown in Fig. 3 and Fig. 4, in which the larger size of blocks brings to higher between-task similarity. Specifically, we introduce three different cluster patterns of tasks under different labels (label 6, 46, 47) from the Enron data set as displayed in Figs. 3(a), 3(b), 3(c). Task 5 shares the same parameters with tasks 6∼11 under label 6 and label 47, while task 5 has high similarity with tasks 2∼4 under label 46. The same with task 15, task 15 is clustered differently under label 6 and label 46. We can observe the similar results from the TripAdvisor data set as shown in Figs. 4. Tasks 1∼11 and tasks 14∼15 form a large cluster together under label 2 while tasks 1∼5 and tasks 6∼15 form two clusters respectively under label 3. This reveals the motivation of the proposed LABTAG model that one task could belong to different clusters with other tasks under different labels. However, on LDOS-CoMoDa data set shown in Fig. 3(d), all tasks are grouped together and share the same parameters. This is the reason why LABTAG performs relatively worse performance on this data set.

5 Conclusion

In this paper, we addressed the problem of multi-task multilabel learning, which is particular suitable to deal with the applications of multiple highly correlated tasks with sparse training instances. Specifically, we proposed a label-sensitive task grouping framework (LABTAG) by Bayesian nonparametric approach for multi-task multi-label classification. In this framework, LABTAG took advantages of both the label correlations and similar task grouping under different labels to enhance the performance of classification. We evaluated the performance of the proposed model on three public multi-label data sets, which validated the superiority of the proposed model over the state-of-the-arts.