Polytree-Augmented Classifier Chains for Multi-Label Classification

1 Introduction

Unlike traditional single label classification problems where an instance is associated with a single-label, multi-label classification (MLC) attempts to allocate multiple labels to any input unseen instance by a multi-label classifier learned from a training set. Obviously, such a generalization greatly raises the difficulty of obtaining a desirable prediction accuracy at a tractable complexity. Nowadays, MLC has drawn a lot of attentions in a wide range of real world applications, such as text categorization, semantic image classification, music emotions detection and bioinformatics analysis. Fig. 1 1 shows a multi-label example, where Fig. 1(a) belongs to labels "fish" and "sea" and Fig. 1(b) is assigned with labels "windsock" and "sky." Note that both objects are fish, but the contexts (backgrounds), in other words, the label dependencies, distinguish them clearly.

1 http://www.yunphoto.net

(b) "windsock","sky"

Figure 1: A multi-label example to show label dependency for inference. (a) A fish in the sea; (b) carp shaped windsocks (koinobori) in the sky.

The existing MLC methods can be cast into two strategies: problem transformation and algorithm adaptation [Tsoumakas and Katakis, 2007]. A convenient and straightforward way for MLC is to conduct problem transformation in which a MLC problem is transformed into one or more single label classification problems. Problem transformation mainly comprises three kinds of methods: binary relevance (BR) [Zhang and Zhou, 2007], pairwise (PW) [F¨urnkranz et al., 2008] and label combination (LC) [Tsoumakas et al., 2011]. BR simply trains a binary classifier for each label, ignoring the label correlation, which is apprantly crucial to make accurate prediction for MLC. For example, it is quite difficult to distinguish the labels "fish" and "windsock" in Fig. 1 from the visual features, unless we consider the label correlations with "sea" and "sky." PW and LC are designed to capture label dependence directly. PW learns a classifier for each pair of labels, and LC transforms MLC into the possible largest single-label classification problem by treating each possible label combination as a metalabel. At the expense of their high ability on modeling label correlations, the complexity increases quadratically and exponentially with the number of labels for PW and LC, respectively, thus they typically become impracticable even for a small number of labels.

In the second strategy, algorithm adaptation, multi-label problems are solved by modifying conventional machine learning algorithms, such as support vector machines [Elisseeff and Weston, 2001], k-nearest neighbors [Zhang and Zhou, 2007], adaboost [Schapire and Singer, 2000], neural networks [Zhang and Zhou, 2006], decision trees [Comite et al., 2003] and probabilistic graphical models [Ghamrawi and McCallum, 2005; Qi et al., 2007; Guo and Gu, 2011; Alessandro et al., 2013]. They achieved competitive performances to those of problem transformation based methods. However, they have several limitations, such as difficulty of choosing parameters, high complexity on the prediction phase, and sensitivity on the statistics of data.

Recently, a BR based MLC method, namely classifier chains (CC) [Read et al., 2009], is proposed to overcome the intrinsic drawback of BR and to achieve higher predictive accuracy. It succeeded in modeling label correlations at low computational complexity, and produced furthermore two variants: probabilistic classifier chains (PCC) [Dembczynski et al., 2010] and Bayesian classifier chains (BCC) [Zaragoza et al., 2011]. PCC makes an attempt to avoid the problem of error propagation that was possessed by CC, however, its ability is greatly limited by the number of labels due to its high prediction cost resulting from the exhaustive search manner. Benefiting from mining marginal dependence between labels as a directed tree, BCC can establish classifier chains in particular chain orderings, but its performance is limited due to the modeling with only second-order correlations of labels. Moreover, these CC based methods cannot model label correlations in a reasonable way, since CC and PCC randomly establish fully connected Bayesian networks, which have a possible risk to lead to trivial label dependence. In addition, the expression ability of BCC is strongly restricted by the adopted tree structure.

To overcome these limitations of CC based methods, this paper proposes a novel polytree-augmented classifier chains (PACC). In contrast to CC and PCC, PACC seeks a reasonable ordering by a polytree that represents the underlying dependence among labels. Unlike BCC, PACC is derived from conditional dependence between labels and is able to model both low and high-order label correlations by virtue of polytrees. Polytree structure is ubiquitous in real world MLC problems, for example, we can readily observe such a structure on the popular Wikipedia 2 and Gene Ontology 3 data sets. In addition, the polytree structure makes it possible to perform exact inference in reasonable time, avoiding the problem of error propagation. Moreover, by introduction of causal basins, the directionality between labels is mostly determined, which further decreases the number of possible orderings.

The rest of this paper is organized as follows. Section 2 gives the mathematical definition of MLC. Section 3 presents related works of CC based methods. Section 4 illustrates an overview of PACC, and presents its implementation. Section 5 reports experimental results performed on both artificial and benchmark multi-label data sets. Finally, Section 6 concludes this paper and gives discussions for the future work.

2 Multi-label classification

In the scenario of MLC, given a finite set of labels L = {λ1, ..., λd}, an instance is typically represented by a pair

2 https://www.kaggle.com/c/lshtc

3 http://geneontology.org/

(x, y), which contains a feature vector x = (x1, ..., xm) as a realization of the random vector X = (X1, ...,Xm) drawn from the input feature space X = Rm, and the corresponding label vector y = (y1, ..., yd) drawn from the output label space Y = {0, 1}d , where yj = 1 if and only if label λj is associated with instance x, and 0 otherwise. In other words, y = (y1, ..., yd) can also be viewed as a realization of corresponding random vector Y = (Y1, ..., Yd), Y ∈ Y.

Assume that we are given a data set of N instances D = {(x(i) , y(i) )}Ni=1 , where y(i) is the label assignment of the ith instance. The task of MLC is to find an optimal classifier h : X → Y which assigns a label vector y to each instance x and meanwhile minimizes a loss function. Given a loss function L(Y, h(X)), the optimal h∗ is

In the BR context, a classifier h is comprised of d binary classifiers h1, ..., hd, where each hj predicts ˆ yj ∈ {0, 1}, forming a vector ˆy ∈ {0, 1}d . Fig. 2(a) shows the probabilistic graphical model of BR. Here, the model

means that the class labels are mututally independent.

3 Related works

3.1 Classifier chains (CC)

Classifier chains (CC) [Read et al., 2009] models label correlations in a randomly ordered chain based on (3).

Here pa(Yj) represents the parent labels for Yj. Obviously, |pa(Yj)| = p, where p denotes the number of labels prior to Yj following the chain order.

In the training phase, according to a predefined chain order, it bulids d binary classifiers h1, ..., hd such that each classifier predicts correctly the value of yj by referring to pa(yj) in addition to x. In the testing phase, it predicts the value of yj in a greedy manner:

The final prediction is the collection of the results, ˆy. The computational complexity of CC is O(d × T (m, N)), where T(m,N) is the complexity of constructing a learner for m attributes and N instances. Its complexity is identical with BR's, if a linear baseline learner is used. Fig. 2(b) shows the probabilistic graphical model of CC following the order of Y1 → Y2 → · · · → Yd.

CC suffers from two risks: if the chain is wrongly ordered in the training phase, then the prediction accuracy can be degraded, and if the previous prediction of labels was wrong in the testing phase, then such a mistake can be propagated to the succeeding prediction.

3.2 Probabilistic classifier chains (PCC)

In the light of risk minimization and Bayes optimal prediction, probabilistic classifier chains (PCC) [Dembczynski et al., 2010] is proposed. PCC approximates the joint distribution of labels, providing better estimates than CC at the cost of higher computational complexity.

The conditional probability of the label vector Y given the feature vector X is the same as CC. Accordingly, PCC shares the model (3) and Fig. 2(b) with CC.

Unlike CC which predicts the output in a greedy manner by (4), PCC examines all the 2d paths in an exhaustive manner:

PCC is a better method in accuracy, but the exponential cost limits its application even for a moderate number of labels, typically no more than 15.

3.3 Bayesian classifier chains (BCC)

BCC [Zaragoza et al., 2011] introduces a Bayesian network to find a reasonable connection between labels before building classifier chains. Specifically, BCC constructs a Bayesian network by deriving a maximum-cost spanning tree from marginal label dependence.

The learning phase of BCC consists of two stages: learning of a tree-structured Bayesian network and building of d binary classifiers following a chain. The chain is determined by the directed tree, which is established by randomly choosing a label as its root and by assigning directions to the remaining edges.

BCC also shares the same model (3) with CC and PCC. Note that because of the tree structure, |pa(Yj)| ≤ 1 in BCC unlike |pa(Yj)| = p in CC and PCC, limiting its ability on modeling label dependence. Fig. 2(c) shows an example of the probabilistic graphical model of BCC with five labels.

4 Polytree-augmented classifier chains (PACC)

We propose a novel polytree-augmented classifier chains (PACC) based on the polytree and also sharing the model (3) with CC based methods. A polytree (Fig. 3(b)) is a singly connected causal network in which variables may arise from multiple causes [Rebane and Pearl, 1987], i.e., a node can have multiple parents unlike BCC. A causal basin is a subgraph which starts with a multi-parent node and continues following a causal flow to include all the descendants and their direct parents. Rebane and Pearl [Rebane and Pearl, 1987] demonstrated that a polytree is a directed acyclic graph whose underlying skeleton is an undirected tree (Fig. 3(a)).

4.1 Learning of the skeleton

In PACC, modeling of conditional label dependence is made by approximating the true distribution P(Y|X) by another distribution. Therefore, Kullback-Leibler (KL) divergence [Kullback and Leibler, 1951], a measure of distance between two distributions, is used to evaluate how close an alternative distribution PB(Y|X) is to P(Y|X), where B is a Bayesian network:

Using the empirical distribution ˆ PD(Y|X) instead of P (Y|X), we evaluate above as:

which is maximized if and only if PB(·) = ˆ PD(·),

where I ˆ PD (Yi; pa(Yj)|X) is the conditional mutual information between Yj and its parents pa(Yj) over X in B:

As a result, the optimal B∗ is obtained by maximizing ∑dj=1 I ˆ PD (Yj; pa(Yj)|X). Since learning of B∗ is NP-hard in general, we restrict our hypothesis B to satisfy |pa(Yj)| ≤ 1, indicating the tree skeleton is to be built. In practice, we carry out Chou-liu's algorithm [Chow and Liu, 1968] to obtain the maximum-cost spanning tree (Fig. 3(a)) with edge weights I ˆ PD (Yi; pa(Yj )|X).

However, it is quite difficult to get conditional probability ˆ PD(Y|X), especially when X is continuous. Recently some methods [Dembczynski et al., 2012; Zaragoza et al., 2011; Zhang and Zhang, 2010] have been proposed to solve this problem. In BCC [Zaragoza et al., 2011], as an approximation of conditional probability, marginal probability of labels Y is obtained by simply counting the frequency of occurrence. Similar with [Dembczynski et al., 2012], LEAD [Zhang and Zhang, 2010] directly obtains conditional dependence by estimating the dependence of errors in multivariate regression models.

In this paper, we use a generalized approach to estimate conditional probability. The data set D is splitted into two sets: a training set Dt and a hold-out set Dh. Probabilistic classifiers are learned from Dt to represent conditional probability of labels, and the probability is calculated based on the output of the learned classifiers over Dh. Assuming pa(Yj) = Yk, we can rewrite (8) as follows:

assuming an equal weight of every instance in Dh,

Hence we can train probabilistic classifiers hj, hk and hj|k on Dt and compute ˆ PD(yj|x), ˆ PD(yk|x) and ˆ PD(yj |yk, x) by utilizing the classifiers to make prediction on Dh, respectively. Lastly, I ˆ PD (Yj; Yk|X) is estimated according to (9).

4.2 Constructing of the PACC

First we assign directions to the skeleton by finding causal basins. This is implemented by finding multi-parent labels and the corresponding directionality. The detailed procedure is as follows.

Fig. 4 shows three possible graphical models among triplets A, B and C. Here Types 1 and 2 are indistinguishable because they share the same joint distribution, while Type 3 is different from Types 1 and 2. In Type 3, A and C are marginally independent, so that we have

In this case, B is a multi-parent node. More generally, we can do zero-mutual information (zero-MI) testing for a triplet, Yj with its two neighbors Ya and Yb: if I(Ya; Yb) = 0, then Ya and Yb are parents of Yj. By performing the zero-MI testing for every pair of Yj 's direct neighbors, pa(Yj ) would be determined. We can see that although PACC shares the model (3) with other CC based methods, it holds |pa(Yj)| ≤ p, demonstrating the flexibility on modeling label dependencies.

In order to build a classifier chain by the learned polytree, we rank the labels to form a chain and then train a classifier for every label following the chain. The ranking strategy is simple: the parents should be ranked higher than their descendants. Hence, learning of a label is not performed until the labels with higher ranks, including its parents, have been learned. In this paper, we choose logistic regression with L2 regularization as the baseline classifier. Therefore, d logistic regression classifiers are learned, each of which is trained by treating pa(yj) and x as new attributes, shown as follows:

where θj denotes the model parameters for Yj, which could be learned by maximizing the regularized log-likelihood given the training set:

where λ is a trade-off coefficient to avoid overfitting by generating sparse parameters θ. Then traditional convex optimization techniques can be used to learn the parameters.

4.3 Classification

Exact inference, as (5), is NP-hard in directed acyclic graphs, for instance, the computation cost of PCC on prediction increases exponentially in number of labels, with complexity O(2d ). Thanks to the max-sum algorithm [Pearl, 1988], despite the fact that the complexity of exact inference on the polytree is O(2d ) in the worst case (d - 1 roots with 1 common leaf), exact inference can be performed in reasonable time on polytrees by bounding the indegree of nodes.

Two phases are performed to make the exact inference. The first phase begins at the roots and propagates downwards to the leaves: the conditional probability table for each node is calculated based on its local graphical structure. In the second phase, message propagation starts upwards from the leaves to the roots, with each node Yj collecting all the incoming messages and finding the local maximum with its value ˆ yj. In this way, the Maximum a Posteriori (MAP) assignment ˆy = (ˆ y1, ..., ˆ yd) is obtained according to

where Yl represents a leaf and Yr a root, respectively.

5 Experiments

We compared the proposed PACC with seven state-of-the-art MLC methods, including BR, CC, PCC, BCC, multi-label knearest neighbours (MLkNN) [Zhang and Zhou, 2006], calibrated label ranking (CLR) [F¨urnkranz et al., 2008] and conditional dependency network (CDN) [Guo and Gu, 2011].

The methods were implemented based on Weka 4 , Mulan 5 and Meka 6 , and performed on one artificial data set and twelve benchmark data sets 5,6 including seven regular and five large data sets. For calculation of the accuracy, 10-fold and 3-fold cross validation were used for the regular and large data sets, respectively. In the experiments we chose logistic regression with L2 regularization as the baseline classifier, set the number of neighbors to k = 10 in MLkNN, and used 100 iterations as the burn-in time for CDN. To reduce the training cost, marginal probability, instead of conditional probability, was calculated in PACC for the large data sets.

For evaluation, two popular multi-label metrics were used.

1. Global accuracy (accuracy per instance):

where 1(·) represents the indicator function.

1. Macro-averaged F-measure (F measure averaged over labels)

5.1 Artificial data

Here we focused on the performances of BR and CC based methods to evaluate their ability on modeling label correlations. One artificial data set with two features X = (X1, X2) and five labels Y = (Y1, Y2, Y3, Y4, Y5) was introduced. The feature variables were uniformly sampled in a square, i.e., x ∈ [-0.5, 0.5]2 , and the label dependency was given by Px(y) = Px(y1)Px(y2)Px(y3|y1, y2)Px(y4|y3)Px(y5|y4). We defined Px(yj ) = 1/(1+exp(-fj (x))), where fj (x) was linear functions given as: f1(x) = x1 + x2, f2(x) = x1 - x2, f3(x) = -x1 -x2 -6y1 +6y2, f4(x) = -x1 +x2 -4y3 +2 and f5(x) = -2x1 + x2 + 2y4 - 1. According to this distribution, 10, 000 instances were generated.

Table 1 reports the experimental results of the artificial data. The best accuracy is shown in bold face. Fig. 5

4 http://www.cs.waikato.ac.nz/ml/weka/

5 http://mulan.sourceforge.net/

6 http://meka.sourceforge.net/

shows the learned graphical models, from which we can see that only PACC successfully found the latent dependence (Fig. 5(c)). As shown in Fig. 5(a), CC and PCC seem to have modeled many trivial correlations. PACC outperformed the other methods in terms of global accuracy. In the light of exact inference, PCC performed better than CC although they share the same network. BCC modeled a wrong dependency network (Fig. 5(b)) over labels based on marginal dependence. BR was the worst since it totally ignores label correlations. Nevertheless, BR outperformed the others in macro-averaged F measure.

5.2 Benchmark data

Next, all the eight methods were compared on a collection of twelve multi-label data sets whose statistical properties are given in Table 2. The experimental results are reported in Tables 3 and 4. Note that PCC and CLR could not finish for large data sets due to their exponential and quadratic complexity in number of labels, respectively.

In the global accuracy, PACC was the best or comparable with the best methods on data sets except the Yeast, Birds and Language log sets. A possible explanation is that PACC is a global accuracy risk minimizer benefiting from its ability on modeling both low-order and high-order label correlations based on the polytree structure. PCC is comparable with PACC on all the data sets when it finished. This means that PCC also makes exact inference as PACC. BCC works worse than CC, especially on large data sets. This is probably because it models only second-order correlations. In consistent with our theoretical analysis, BR obtains the worst result compared with CC based methods, since it simply ignores label correlations. It is also worth noting that BR works better than CC based methods on Birds, indicating weak label correlations in that set. Among eight methods, MLkNN ranked first over four data sets, but it fails largely in the Genbase, Enron and Corel5k sets. It probably means that MLkNN is sensitive to the number of neighbors and noise. CLR was the worst, meaning that modeling pairwise relationship between labels is not enough in practice. It seems that, to extract the best performance of CDN with fully complicated dependency of labels, we need more samples.

In macro-averaged F measure, PACC performed the best. CLR ranked at the second, showing a good performance compared with the global accuracy. BCC ranked at the third, and was comparable with other CC based methods. The performance of MLkNN varied significantly over the data sets.

In terms of computational time 7 , PACC needed several minutes to hours for learning depending on the data sets size and seconds to minutes for prediction. We can say that PACC finds a better trade-off between computational complexity and prediction accuracy in contrast to other CC based methods by virtue of the polytree structure and max-sum algorithm. BR, CC, BCC paid similar prediction cost with PACC. PCC needs the same time with CC for learning, but needs O(2d ) complexity for prediction, for which reason it was applicable only on smallest data sets. As a lazy method, MLkNN could finish classification within minutes even in the largest data sets, demonstrating its high efficiency. CLR consumed hours or could not complete learning, due to its quadratic complexity in the number of labels. Since CDN employs Gibbs sampling to approximate inference, it cost much more time on prediction compared with other methods, typically several minutes on large data sets.

7 In a Intel Quad-Core CPU at 3.4 GHz with 8 GB RAM.

6 Conclusions and future work

In this paper, we have proposed a polytree-augmented classifier chains (PACC) method in order to achieve a better prediction accuracy compared with the state-of-the-art MLC methods by modeling the underlying label dependency as a polytree. The experimental results on one synthetic and twelve real data sets demonstrated its efficiency. As future work, it is interesting to see whether PACC can be further improved by incorporating feature selection into the construction step. Furthermore, introduction of ensemble methods and other baseline learners for PACC is also worth researching.

Acknowledgments

This work was partly supported by JSPS KAKENHI Grant Number 15H02719 and China Scholarship Council with Hokkaido University.