Bayesian Chain Classifiers for Multidimensional Classification

1 Introduction

In contrast with traditional (one-dimensional) classifiers, multidimensional classifiers (MDCs) assign each instance to a set of d classes. MDCs have gained a lot of attention in recent years, as several important problems can be seen as multidimensional classification [Zhang and Zhou, 2007; Vens et al., 2008], such as text classification (assigning a document to several topics), HIV drug selection (determining the optimal set of drugs), among others.

Two main types of approaches have been proposed for solving a MDC problem with binary classes: binary relevance and label power-set [Tsoumakas and Katakis, 2007]. In the binary relevance approach [Zhang and Zhou, 2007], an MDC problem is transformed into d binary classification problems, one for each class variable, C1, . . . ,Cd. A classifier is independently learned for each class variable, and the results are combined to determine the predicted class set. The main advantages of this approach are its low computational complexity, and that existing classification techniques can be directly applied. However, it is unable to capture the interactions between classes and, in general, the most likely class of each classifier will not match the most likely set of classes due to possible interactions among them.

The label power-set approach [Tsoumakas and Katakis, 2007] transforms the multidimensional problem into a singleclass scenario by defining a new compound class variable whose possible values are all of the possible combinations of values of the original classes. In this case the interactions between the different classes are implicitly considered. Thus, it can be effective for domains with a few class variables. But its main drawback is its computational complexity, as the size of the compound class variable increases exponentially with the number of classes.

To overcome the limitations of the previous methods, there are two main strategies: (i) to incorporate class interactions in binary relevance methods, in what are known as chain classifiers [Read et al., 2009; Dembczynski et al., 2010], and (ii) to explicitly represent the dependence structure between the classes, avoiding the combinatorial explosion of the label power-set approach, via multidimensional Bayesian network classifiers [van der Gaag and de Waal, 2006; Bielza et al., 2011].

Bayesian Chain Classifiers (see Fig. 1) combine the previous strategies, taking advantage of their strengths and at the same time avoiding their main limitations. The method for learning these classifiers consists of two main phases: (i) to obtain a dependency structure for the class variables, and (ii) based on the dependency structure, build a classifier chain. In the first phase, a Bayesian network (BN) that represents the dependency relations between the class variables is learned from data. This class structure serves as a guide for the second phase, as it restricts the possible variable orderings in the chain. In the second phase, a chain classifier is built, such that the order of the class variables in the chain is consistent with the graph of the previously learned BN (class BN). Although there are still many possible orderings, the number is reduced significantly with respect to all possible random orders. In this chain, previous classes are also incorporated as features along the chain, but only the parents variables in the class BN, as in a BN every variable is independent of its nondescendants given its parents. Thus, the number of additional features is restricted even for domains with a large number of classes. Finally, as for chain classifiers, the predicted class set is obtained by combining the outputs of all the classifiers in the chain.

In this paper we present the simplest version of a Bayesian Chain Classifier, as the dependency structure between class variables is restricted to a directed tree. Thus, each class variable in the tree has at most one parent, so only one additional feature is incorporated to each base classifier in the chain. Additionally, the base classifiers are na¨ıve Bayes. As in [Read et al., 2009], we combine several chain classifiers in a classifier ensemble, by changing the root node in the tree. This basic Bayesian Chain Classifier is highly efficient in terms of learning and classification times, and it outperforms other more complex MDCs as demonstrated in the experiments.

2 Multidimensional Classifiers

As previously introduced, in this contribution we will present an approach to classification problems with d class variables, C1, . . . ,Cd. In this framework, the multi-dimensional classification problem corresponds to searching for a function h that assigns to each instance represented by a vector of m features x = (x1, . . . , xm) a vector of d class values c = (c1, . . . , cd):

We assume that Ci and Xj for all i = 1, . . . , d and all j = 1, . . . ,m are discrete, and that ΩCi and ΩXj respectively represent their sample spaces.

Under a 0 - 1 loss function, the h function should assign to each instance x the most likely combination of classes, that is:

This assignment amounts to solving a total abduction inference problem and corresponds to the search for the most probable explanation (MPE), a problem that has been proved to be an NP-hard problem for Bayesian networks [Shimony, 1994].

3 RelatedWork

In this section we briefly review the main approaches for multidimensional classification. The review is organized into three subsections, discussing research in multi-label classification, multidimensional Bayesian networks classifiers, and chain classifiers, respectively.

3.1 Multi-label Classification

In multi-label classification domains each instance is associated with a subset of labels (present in the instance) from a set of d labels. Taking the notation introduced in previous sections into account, this multi-label classification problem can be seen as a particular case of a multidimensional classification problem where all class variables are binary, that is |ΩCi | = 2 for i = 1, . . . , d.

An overview of multi-label classification is given in [Tsoumakas and Katakis, 2007], where two main categories are distinguished: (a) problem transformation methods, and (b) algorithm adaptation methods. Methods in (a) transform the multi-label classification problem into either one or more single-label classification problems. Methods in (b) extend specific learning algorithms to handle multi-label data directly. For example, decision trees [Vens et al., 2008], support vector machines [Boutell et al., 2004], k-nearest neighbor [Zhang and Zhou, 2007], neural networks [Zhang and Zhou, 2006], and a hybrid of logistic regression and k-nearest neighbor [Cheng and Hullermeier, 2009] have been proposed.

3.2 Multidimensional Bayesian Network Classifiers

A multidimensional Bayesian network classifier (MBC) over a set V = {Z1, . . . , Zn}, n ≥ 1, of discrete random variables is a Bayesian network B = (G,Θ), where G is an acyclic directed graph with vertexes Zi and Θ is a set of parameters θz|pa(z) = p(z|pa(z)), where pa(z) is a value for the set Pa(Z), parents variables of Z in G. B defines a joint probability distribution pB over V given by:

The set V of vertexes is partitioned into two sets VC = {C1, . . . ,Cd}, d ≥ 1, of class variables and VX = {X1, . . . ,Xm}, m ≥ 1, of feature variables (d +m = n). The set A of arcs is also partitioned into three sets, AC, AX , ACX , such that AC ⊆ VC × VC is composed of the arcs between the class variables, AX ⊆ VX × VX is composed of the arcs between the feature variables and finally, ACX ⊆ VC × VX is composed of the arcs from the class variables to the feature variables. The corresponding induced subgraphs are GC = (VC,AC), GX = (VX ,AX) and GCX = (V,ACX), called respectively class, feature and bridge subgraphs.

Different graphical structures for the class and feature subgraphs may lead to different families of MBCs. [van der Gaag and de Waal, 2006] learn trees for both subgraphs by searching for the maximum weighted undirected spanning tree and transforming it into a directed tree using Chow and Liu's algorithm [1968]. The bridge subgraph is greedily learnt in a wrapper way, trying to improve the percentage of correctly classified instances. [de Waal and van der Gaag, 2007] is a theoretical work for finding the conditions for the optimal recovery of polytree structures in both subgraphs.

[Rodr´ıguez and Lozano, 2008] extend polytrees to k-DB structures for class and features subgraphs. Learning these structures is carried out using a multi-objective genetic algorithm where the individuals are permitted structures coded with three substrings, one per subgraph. Simpler models are used in an application for heart wall motion prediction [Qazi et al., 2007]: a directed acyclic graph for the class subgraph, an empty graph for the features, and a bridge subgraph where features receive arcs from some class variables, without sharing any of them.

Finally, [Bielza et al., 2011] present the most general models since any Bayesian network structure is allowed in the three subgraphs. Learning from data algorithms cover all the possibilities: wrapper, filter and hybrid score+search strategies. Moreover, since the computation of the MPE involves a high computational cost, several contributions are designed to alleviate it.

3.3 Chain Classifiers

Read and others [2009] introduce chain classifiers as an alternative method for multi-label classification that incorporates class dependencies, while it tries to keep the computational efficiency of the binary relevance approach. Chain classifiers consist of d binary classifiers which are linked in a chain, such that each classifier incorporates the class predicted by the previous classifiers as additional attributes. Thus, the feature vector for each binary classifier, Li, is extended with the labels (0/1) of all previous classifiers in the chain. Each classifier in the chain is trained to learn the association of label li given the features augmented with all previous binary predictions in the chain, l1, l2, . . . , li-1. For classification, it starts at L1, and propagates along the chain such that for i ∈ L (where L = {l1, l2, . . . , ld}) it predicts p(li | x, l1, l2, . . . , li-1). As in the binary relevance approach, the class vector is determined by combining the outputs of all the binary classifiers in the chain.

[Read et al., 2009] combine several chain classifiers by changing the order for the labels, building an ensemble of chain classifiers. Thus, m chain classifiers are trained, by varying the training data and the order of the classes in the chain (both are set randomly). The final label vector is obtained using a voting scheme; each label li receives a number of votes from the m chain classifiers, and a threshold is used to determine the final predicted multi-label set.

Recently, Dembczynski et al. [2010] present probabilistic chain classifiers (PCCs), by basically putting chain classifiers under a probabilistic framework. Using the chain rule, the probability of the vector of d class values C = (C1, . . . , Cd) given the feature vector x can be written as:

Given a function fi that provides an approximation of the probability of Ci = 1, they define a probabilistic chain classifier as:

PCC estimates the joint probability of the classes, providing better estimates than the chain classifiers, but with a much higher computational complexity. In fact, the experiments reported by [Dembczynski et al., 2010] are limited to 10 classes.

As shown by [Dembczynski et al., 2010], a method that considers class dependencies under a probabilistic framework can have a significant impact on the performance of multidimensional classifiers. However, both MBCs and PCCs have a high computational complexity, which limits their applicability to high dimensional problems. In the following section we describe an alternative probabilistic method which also incorporates class dependencies but at the same time is very efficient.

4 Bayesian Chain Classifiers

Given a multidimensional classification problem with d classes, a Bayesian Chain Classifier (BCC) uses d classifiers, one per class, linked in a chain. The objective of this problem can be posed as finding a joint distribution of the classes C = (C1, C2, . . . , Cd) given the attributes x = (x1, x2, . . . , xl):

where pa(Ci) represents the parents of class Ci. In this setting, a chain classifier can be constructed by inducing first the classifiers that do not depend on any other class and then proceed with their sons. A Bayesian framework allows us to:

• Create a (partial) order of classes in the chain classifier based on the dependencies between classes given the features. Assuming that these dependencies can be represented as a Bayesian network (directed acyclic graph), the chain structure is defined by the structure of the BN, such that we can then start building classifiers for the classes without parents, and continue with their children classes, and so on.
• Consider conditional independencies between classes to create simpler classifiers. In this case, construct d classifiers considering only the parent classes of each class. For a large number of classes this can be a huge reduction as normally we can expect to have a limited number of parents per class.

In general, when we induce a Bayesian network to represent the above joint distribution, it is not always possible to find directions for all the links. In that case we can have different orders depending on the chosen directions. In the worst case the number of possible directions grows exponentially with the number of links (2k for k undirected links). In practice we expect to have only a limited number of undirected links. In that case we can obtain (a subset of) the possible orders and build an ensemble of chain classifiers with different orders. Given a new instance, we determine p(Ci|pa(Ci), x)∀i ∈ D with each chain classifier, and use a voting scheme to output a set of classes.

We can simplify the problem by considering the marginal dependencies between classes (as a first approximation) to obtain an order in the chain classifier and then induce classifiers considering such order. Additionally, we can simplify even further the problem by considering only one parent per class. This can be solved by obtaining the skeleton of a treestructured BN for the classes using Chow and Liu's algorithm (1968), that is, a maximum weight undirected spanning tree (MWST) (see Fig. 2).

Chow and Liu's algorithm does not give us the directions of the links, however, we can build d directed trees by taking each class (node) as root of a tree and assigning directions to the arcs starting from this root node to build a directed tree (Fig. 3). The chaining order of the classifiers is given by traversing the tree following an ancestral ordering.

For d classes we build d classifiers in the order given by the different trees and then combine them in an ensemble (if d is very large we can limit the number of chains by selecting a random subset of trees).

There are many different choices for representing each classifier, one of the simplest and fastest to build is the na¨ıve Bayes classifier (NBCs); although other classifiers could be used as well. With na¨ıve Bayes classifiers in the chain, we need to consider only the class parent, pa(Ci), and the feature vector, x, as attributes for each NBC, see Fig. 1.

We can summarize our algorithm as follows. Given a multidimensional classification problem with d classes:

1. Build an undirected tree to approximate the dependency structure among class variables.
2. Create d orders for the chain classifiers by taking each class as the root of the tree and assigning the rest of the links in order.
3. For each classifier in each chain, build an NBC with the class Ci as root and only the parents pa(Ci) and all the

attributes x as children, taking advantage of conditional independence properties.

To classify a new instance combine the output of the d chains, using a simple voting scheme.

This is a very fast and easy to build ensemble of chain classifiers, which represents the simplest alternative for a BCC. Other, more complex alternatives can be explored by: (i) considering conditional dependencies between classes, (ii) building more complex class dependency structures, and (iii) using other base classifiers.

In the next section we present the experimental results where we compare BCCs with other state of the art multidimensional classifiers.

5 Experiments and Results

The proposed method was tested on 9 different benchmark multidimensional datasets 1 ; each of them with different dimensions ranging from 6 to 983 labels, and from about 600 examples to more than 40, 000. All class variables of the datasets are binary, however, in some of the datasets the feature variables are numeric. In these cases we used a static, global, supervised and top-down discretization algorithm [Cheng-Jung et al., 2008]. The details of the datasets are summarized in Table 1.

First, we compared BCCs against 9 different state-of-theart methods (shown in Table 2) using the Emotions, Scene and Yeast datasets. Algorithm 1 is the basic Binary Relevance method [Tsoumakas and Katakis, 2007]. Algorithms 2 to 6 are methods explicitly designed for learning MBCs. Algorithms 7 and 8 use greedy search approaches that learn a general Bayesian network, one guided by the K2 metric [Cooper and Herskovits, 1992] (filter approach), and the other guided by a performance evaluation metric, as defined in [Bielza et al., 2011] (wrapper approach). Algorithm 9 is a multi-label lazy learning approach named ML-KNN [Zhang and Zhou, 2006], derived from the traditional K-nearest neighbor algorithm. In this experiment for the ML-KNN method K was set to 3 in the Emotions and Scene data sets, and 5 in the Yeast data set. Since it is unfeasible to compute the mutual information of two features given all the class variables, as required in [de Waal and van der Gaag, 2007], the implementation of the polytree-polytree learning algorithm uses the marginal mutual information of pairs of features. Algorithm 10 from Table 2 is our Bayesian Chain Classifier.

1 The data sets can be found at mulan.sourceforge.net/datasets.html, mlkd.csd.auth.gr/multilabel.html and www.cs.waikato.ac.nz /jmr30/#-datasets.

For the purpose of comparison we used two different multidimensional performance measures [Bielza et al., 2011]:

1. Mean accuracy (accuracy per label or per class) over the d class variables:

where δ(c′ij , cij) = 1 if c′ij = cij and 0 otherwise. Note that c′ij denotes the Cj class value outputted by the model for case i and cij is its true value.

1. Global accuracy (accuracy per example) over the ddimensional class variable:

where ci is the d-dimensional vector of class values and δ(c′i , ci) = 1 if c′i = ci and 0 otherwise. Therefore, we call for a total coincidence on all of the components of the vector of predicted classes and the vector of real classes.

The estimation method for performance evaluation is 10fold cross-validation. Results for accuracy and a comparison of the different methods are shown in Table 3. Table 4 shows the average rankings of the 9 algorithms used for comparison and that of our method. As can be seen from this table, in general, the performance of our method is better that the other methods used in these experiments.

Secondly, we performed experiments with the TMC2007, Medical, Enron, MediaMill, Bibtex and Delicious datasets. Given the complexity of these datasets, in particular in the number of classes, they can not be tested with the other methods; so in this case we compared Bayesian Chain Classifiers and Ensembles of BCCs (EBCCs). In Table 5 we show the Mean and Global accuracies per dataset for BCCs and EBCCs, respectively. We observe that for most of the datasets there is a significant improvement in mean and global accuracy with the ensemble. The number of iterations on the ensembles were set to 10. A class is determined whether positive or negative by taking the value with the higher number of votes in the ensemble.

In terms of computational resources, the training and classification times for the small data sets (Emotions, Scene and Yeast) are less than one minute; and for the more complex datasets are in the order of hours 2 .

6 Conclusions and FutureWork

In this paper we have introduced Bayesian Chain Classifiers for multidimensional classification. The proposed approach is simple and easy to implement, and yet is highly competitive against other Bayesian multidimensional classifiers. We experimented with the simplest model for a BCC, considering a tree structure for the class dependencies and a simple na¨ıve Bayes classifier as base classifier. In the future we will explore alternative models considering more complex dependency structures and other more powerful base classifiers. We also plan to compare our approach with other classifier chains using different metrics and datasets.

7 Acknowledgments

The authors wish to acknowledge FONCICYT for the support provided through Project No. 95185 (DyNaMo).

Also, this research has been partially supported by the Spanish Ministry of Science and Innovation, projects TIN2010-20900-C04-04, Consolider Ingenio 2010CSD2007-00018 and Cajal Blue Brain.