Multi-Label Structure Learning with Ising Model Selection

1 Introduction

In Multi-Label (ML) classification a single data sample may belong to many classes at the same time, as opposed to an exclusive single label usually adopted in traditional multi-class classification problems. For example, an image which contains trees, sky, and mountain may belong to landscape and mountains categories simultaneously; a single gene may be related to a set of diseases; a music/movie may belong to a set of genres/categories; and so on. One can see that multi-label learning includes both binary and multi-class classification problems as specific cases. Thus, such general aspect makes it more challenging then traditional classification problems.

Common strategies to attack ML classification problems are [Madjarov et al., 2012]: (i) algorithm adaptation, and (ii) problem transformation. In the former, well-known learning algorithms such as SVM, neural networks, and decision trees are extended to deal with ML problems. In the latter strategy, the ML problem is decomposed into Q binary classification problems and each one is solved independently using traditional classification methods. This is known as Binary

Arindam Banerjee

Computer Science Dept. University of Minnesota, USA banerjee@cs.umn.edu

Relevance [Tsoumakas and Katakis, 2007] in ML literature. However, when solving each binary classification problem independently potential dependence among the labels are neglected. And this dependence tends to be very helpful particularly when a limited amount of training data is available.

There have been a number of attempts to incorporate label dependency information in ML algorithms, and they will be properly discussed in Section 4. We anticipate that in most of them, graphical models are used to model label dependence. However, these graphical models usually rely on inference procedures which are either intractable for general graphs or very slow in high-dimensional problems.

Building upon recent advances in structure learn in IsingMarkov Random Fields (I-MRF) [Ravikumar et al., 2010], we propose a multi-label classification method capable of estimating and incorporating the hidden label dependence structure into the classifier learning process. The method involves two steps: (i) label dependence modelling using I-MRF; and (ii) joint learning of all binary classifiers in a regularized sparse convex multi-task learning (MTL) [Caruana, 1997] formulation, where classifiers corresponding to dependent labels in I-MRF are encouraged to share information.

Class labels are modeled as binary random variables and the interaction structure as an I-MRF, so that the I-MRF captures the conditional dependence graph among the labels. The problem of learning the labels (tasks) dependence reduces to the problem of structure learning in the Ising model, on which considerable progress has been made in recent years [Ravikumar et al., 2010; Jalali et al., 2011; Bresler, 2015]. The conditional dependence undirected graph is plugged into a convex sparse MTL formulation, for which efficient optimization methods can be applied [Beck and Teboulle, 2009; Boyd et al., 2011]. The key contributions of this paper are:

• we propose a framework for multi-label classification problems that explicitly capture labels dependence employing a probabilistic graphical model (I-MRF) for which efficient inference procedures are available;
• we employed a stability selection procedure to identify persistent label dependencies (connections) in undirected graph associated with I-MRF;
• we impose sparsity in the coefficient vectors of the binary classifiers, so that the most important discriminative features are automatically selected;

• we have conducted extensive experiments on eight multi-label classification datasets and compared the effectiveness of the proposed formulation in terms of six performance measures.

The remaining of the paper is organized as follows. In Section 2, we cover background material, including the Ising model selection problem and the multi-task learning problems. Section 3 discusses the proposed method to multi-label classification with Ising model selection. Section 4 comments on related work in the literature. Section 5 outlines the experimental setup, describing the multi-label datasets, baseline algorithms, and performance metrics. We discuss experimental results in Section 6, and conclude in Section 7.

2 Background

In this section we provide some background on the relevant topics. We start describing the Ising model selection procedure for structure learning on binary data, followed by an introduction to the multi-task learning formulation.

2.1 Ising model selection

Ising model is a mathematical model originally proposed to study the behavior of atoms in ferro-magnetism. Each atom has a magnetic moment pointing either up or down, called spin. The atoms are arranged in a d-dimensional lattice, allowing only direct neighbors atoms to interact to each other.

From a probabilistic graphical model perspective, we can see atoms as binary random variables xi ∈ {-1,+1}. The interaction structure among the atoms can be seen as an undirected graphical model. Let G = (V,E) be a graph with vertex set V = {1, 2, ..., p} and edge set E ⊂ V × V , and a parameter θrs ∈ R. The Ising model on G is a Markov random field with distribution given by

where Θ is a matrix with all parameters for each variable r, θr, as columns. Thus, the graphical model selection problem becomes: Given n i.i.d samples x = (x1, x2, ..., xp) with distribution given by (1), estimate the edge set E. Such structural learning problem is difficult to solve due to computational intractability of the partition function Φ(·) [Welsh, 1993].

Recently, [Ravikumar et al., 2010] proposed a simple and efficient method for the graphical model selection problem. Basically, it involves performing an ℓ1-regularized logistic regression on each variable while considering the remaining variables as covariates. The sparsity pattern of the regression vector is then used to infer the underlying graphical structure. For all variables r = 1, ..., p, the corresponding parameter θr is obtained by

where logloss(·) is the logistic loss function and λ > 0 is a trade-off parameter. Note that it can be run in parallel for each label and can scale to problems with large number of labels.

To show the structure recovery capability of the method, a slightly different notion of edge recovery is studied, called signed edge recovery, where given a graphical model with parameter Θ, the signed edge set ¯E is

The signed edge set ¯E can be represented in terms of neighborhood sets. For a given vertex r, its neighborhood set is given by N(r) := {s ∈ V |(r, s) ∈ E} along with the correct signs sign(θrs), ∀s ∈ N(r). In other words, the neighborhood set of a vertex r will be those vertices s corresponding to variables whose parameter θrs is non-zero in the regularized logistic regression. [Ravikumar et al., 2010] showed that recovering the signed edge set ¯E of an undirected graph G is equivalent to recovering the neighborhood set for each vertex.

It is noteworthy that the method in [Ravikumar et al., 2010] can only handle pairwise interactions (clique factors of size c = 2). [Jalali et al., 2011] presented a structure learning method for a more general class of discrete graphical models (clique factors of size c ≥ 2). Block-ℓ1 regularization is used to select clique factors. [Ding et al., 2011] also considered high-order interactions (c ≥ 2) among random variables, but conditioned to another random vector (e.g. observed features), similar to the ideas of conditional random fields.

Since the local dependencies are stronger, these can be predominant when estimating the graph. Then the neighborhood dependence (short-range) possibly will hide other long-range dependencies. Most of the methods just mentioned can not get provable recovery under long-range dependencies [Montanari and Pereira, 2009]. Very recently, [Bresler, 2015] presented an algorithm for Ising model with pairwise dependencies and bounded node degree which can also capture longrange dependencies. However, while theoretically proven to be polynomial time, the constants associated with sample complexity and runtime can be quite large.

2.2 Multi-task learning

Multitask Learning (MTL) [Caruana, 1997] is a machine learning paradigm which seeks to improve the generalization capability of a learning task by using information from other related tasks. Suppose we are given a set of Q supervised learning tasks, such that all data for the q-th task come from the space X×Y, where xiq ∈ Rd and yiq ∈ R, i = 1, ..., nq. So, for each task q a set of nq data samples are available. The goal is to learn Q parameter vectors w1, ...,wQ ∈ Rd such that f(xiq ,wq) ≈ yiq , q = 1, ...,Q, and i = 1, ..., nq. Learning all tasks together we have the following cost function:

where ℓ(·) is the loss function corresponding to the task we are dealing with, which includes squared, logistic, and hinge loss as examples; W ∈ Rd×Q is the parameter matrix, where columns are vector parameters wq, q = 1, ...,Q, for the tasks; R(W) is a regularization function of W designed to allow information sharing between tasks. Hence, exploiting the underlying dependence structure may be advantageous. It is now clear that a fundamental step is to estimate the relationship structure among tasks, thus promoting a proper information sharing among related tasks while avoiding using information from unrelated tasks [Zhang and Yeung, 2010; Gonc¸alves et al., 2014].

3 Multi-task learning with Ising model selection

This section contains a technical exposition of the proposed I-MTSL (Ising Multi-task Structure Learning) algorithm, which consists of two main steps: (i) estimation of the graph representing the dependence among labels, and (ii) estimation of the parameters for all single-label classifier, where the problem is posed as a convex multi-task learning problem.

3.1 Label dependence estimation

Let the conditional random variables representing the labels given the input data, Zi = yi|X, i = 1, ...,Q, be binary random variables. We then assume that the joint probability distribution of Z = (Z1,Z2, ...,ZQ) follows an Ising Markov random field. So, given a collection of n i.i.d. samples {z(1) , ..., z(n) }, where each Q-dimensional vector z(i) ∈ {-1,+1}Q drawn from the distribution PΘ (Eq. (1)), the problem is to learn the undirected graph G = (V,E) associated with the binary Ising Markov random field. We then use the method described Section 2.1 to infer the edge set E. Recall that, in fact, the method estimates the signed set of edges ¯E, i.e., each edge takes either "-1" or "+1" value.

The undirected graph G encodes the conditional dependencies among the labels. The edge absence between two nodes indicates that the corresponding labels are conditionally independent. Such information is crucial in the multi-task learning, which tells with whom each task shares information.

Stability selection

To find stable connections in the undirected graph associated with the I-MRF, a stability selection procedure is applied. We used the sub-sampling based technique proposed by [Meinshausen and B¨uhlmann, 2010]. With it, we eliminate possible spurious label dependencies due to noise and/or random data fluctuation. If such spurious connections are incorporated directly into the multi-task learning formulation, it can mislead the algorithm to share information among non-related tasks, which may adversely affect the performance of the classifiers.

The stability selection algorithm proceeds as follows: (1) sub-samples of size ⌊n/2⌋ are generated without replacement from the training data; (2) for each sub-sample the structure learning algorithm is applied; and (3) we then select the persistent connections, which are those that appeared in a large fraction of the resulting selection sets. For this, a cutoff threshold 0 < πthr < 1 is needed. In our experiments we set πthr = 0.8, then a connection is said to be consistent if it appears in 80% of graphs constructed from the sub-samples.

To the best of authors' knowledge, the use of stability selection procedure to obtain the undirected graph of label dependence is a novelty of our paper.

3.2 Task parameters estimation

Once estimated the graph G, we turn our attention now to the joint learning of all single-label classifiers.

In I-MTSL, we use the learned dependence structure among labels in an inductive bias regularization term which enforces related tasks to have similar task parameters w. Tasks coefficients in I-MTSL are estimated by solving:

where ¯L is the signed Laplacian matrix computed from the signed edge set ¯E [Kunegis et al., 2010], tr(·) is the trace operator, and γ > 0 is a penalization parameter. ¯L is computed as ¯L = ¯D - ¯E, where ¯D ∈ RQ×Q is a diagonal matrix ¯Dii = ∑i∼j | ¯Eij|. As matrix ¯L is positive semi-definite (see [Kunegis et al., 2010]) the problem (5) is (non-smooth) convex. The signed Laplacian is an extension of the ordinary Laplacian matrix when negative edges are present. Allowing negative edges, the multitask learning method is then capable of modeling positive and negative tasks relationships, which is not always the case in existing MTL formulations [Argyriou et al., 2008; Obozinski et al., 2010].

The first term in the minimization problem (5) refers to any binary classification loss function, such as logistic and hinge loss. The second term is the bias inductive term which favors related tasks' weights to be similar. The third term induces sparsity on W matrix, which automatically selects the most relevant features, setting to zero weights of non-relevant ones.

The I-MTSL algorithm is outlined in 1. Note that no iterative process is required.

Algorithm 1 I-MTSL algorithm.

Require: X, Y, λ > 0, γ > 0

• 1: for q = 1 to Q do
• 2: Θ(q,:) = argmin θq {logloss( ¯Y\k, yk, θq) + λ‖θq‖1};
• 3: end for
• 4: ¯L = ¯D- ¯E;
• 5: ComputeWby solving (5);
• 6: return W, ¯E.

3.3 Optimization

For both optimization problems (2) and (5), an accelerated proximal gradient method was used. In such class of algorithms the cost function h(x) is decomposed as h(x) = f(x) + g(x), where f(x) is a convex and differentiable function and g(x) is convex and typically non-differentiable. Thus, the accelerated proximal gradient iterates as follows

where ωt ∈ [0, 1) is an extrapolation parameter and ρt is the step size. The ωt parameter is chosen as ωt = (ηt -1)/ηt+1, with ηt+1 = (1+√1 + 4η2 t )/2 in [Beck and Teboulle, 2009] and ρt can be computed by a line search.

The g(x) term in both problems corresponds to the ℓ1norm, which has a cheap proximity operator defined as

which is known as soft-threshold operator and is interpreted element-wise. It is a simple application of a function that can even be done in parallel. The convergence rate of the algorithm is O(1/k2 ) [Beck and Teboulle, 2009]. Defining logistic loss as the cost function ℓ(·) and writing (5) in the form of vec(W) ∈ RdQ×1 , the gradient of the function f(·) is computed as

where σ(·) is the sigmoid function, P is a permutation matrix that converts the column stacked arrangement of vec(W) to a row stacked arrangement, and ⊗ is the Kronecker product. ¯X is a block diagonal matrix where the main diagonal blocks are the task input data matrices Xq, ∀q = 1, ...,Q, and the off-diagonal blocks are zero matrices. The gradient of (2) is simply the derivative of the logistic loss function w.r.t. θr.

4 Related work

A number of papers have explored ways of incorporating label dependence into ML algorithms. The early work of [McCallum, 1999] used a mixture model trained via ExpectationMaximization to represent the correlations between class labels. In [Read et al., 2011] information from other labels are stacked as features, in a chain fashion, for the binary classifier corresponding to a specific label. Then, high importance will be given to those features associated with correlated labels. None of these, however, explicitly model labels dependence.

Among the explicit modeling approaches, [Rai and Daume, 2009] present a sparse infinite cannonical correlation analysis to capture label dependence, where a non-parametric Bayesian prior is used to automatically determine the number of correlation components. Due to the model complexity, the parameters estimation relies on sampling techniques which may be very slow for high-dimensional problems.

Somewhat similar in spirit to our approach, many papers have employed probabilistic graphical models to explicitly capture label dependence. Bayesian networks were used to model label dependence in [de Waal and van der Gaag, 2007; Zhang and Zhang, 2010], and [Bielza et al., 2011]. However, the structure learning problem associated with Bayesian networks is known to be NP-hard [Chickering, 1996]. Markov networks formed from random spanning trees are considered in [Marchand et al., 2014]. Conditional random field (CRF) was used in [Ghamrawi and McCallum, 2005], where the binary classifier for a given label not only considered its own data, but also information from neighboring labels determined by the undirected graphical model encoded into the CRF model. [Bradley and Guestrin, 2010] also proposed a method for efficiently learning tree structures for CRFs. For general graphs, however, the inference problems in CRF are intractable, and efficient exact inference is only possible for more restricted graph structures such as chains and trees [Sutton and McCallum, 2011]. [Shahaf and Guestrin, 2009] also present a structure learning method for a more restrict class of models known as low-treewidth junction trees. We use a more general undirected graph, I-MRF, that can capture any pairwise label dependence and for which efficient (and highly parallelizable) structure learn procedures have been recently proposed. These new approaches including [Ravikumar et al., 2010] avoid the explicit reliance of the classical structure learning approaches on inference in the graphical model, making them computationally efficient and statistically accurate. We have discussed recent developments on Ising model structure learning in Section 2.1. Here, the dependence graph is plugged into a regularized MTL formulation, a paradigm which has shown improvements in predictive performance relative to traditional machine learning methods.

5 Experimental design

In this section we present a set of experiments on multi-label classification to assess the performance of the proposed IMTSL algorithm.

5.1 Datasets

For the experiments we have chosen eight well-known datasets in the multi-label classification literature. Those datasets are from different application domains and have different number of samples, labels, and dimensions. Table 1 shows a basic description of the datasets. For a detailed characterization, refer to [Madjarov et al., 2012]. All datasets were downloaded from Mulan webpage 1 .

5.2 Baselines

Five well known methods were considered in the comparison: three state-of-the-art MTL algorithms: CMTL [Zhou et al., 2011a], Low rank MTL (LowRank) [Ji and Ye, 2009], and MTL-FEAT [Argyriou et al., 2008]; besides two popular ML algorithms: Binary Relevance (BR) [Tsoumakas and Katakis, 2007] and Classifier Chain (CC) [Read et al., 2011]. CC algorithm incorporates other labels information as covariates in a chain fashion, then label dependence information is explored in the classifier parameter estimation process. For CMTL, LowRank, and MTL-FEAT we used the MALSAR [Zhou et al., 2011b] package. The remaining methods were implemented by the authors (I-MTSL code will be released).

1 http://mulan.sourceforge.net/datasets-mlc.html

5.3 Experimental setup

Logistic regression was used as the base classifier for all algorithms. Z-score normalization was applied to all datasets, then covariates have zero mean and standard deviation one.

For all methods, parameters were chosen following the same procedure. We selected 20% of the training set to act as validation set (holdout cross-validation) and tested the parameters on a grid containing ten equally spaced values in the interval [0,5]. The parameter with the best average accuracy over all binary classification problems in the validation set was used in the test set. The results presented in the next sections are based on ten independent runs of each algorithm.

5.4 Evaluation measures

To assess the performance of multi-label classifiers is essential to consider multiple and contrasting evaluation measures due to the additional degrees of freedom that the multi-label setting introduces [Madjarov et al., 2012]. Thus, six different measures were used: accuracy, 1 - Hamming loss (1-HL), macro-F1, precision, recall, and F1-score. For a detailed description of those measures, refer to [Madjarov et al., 2012]. In essence, all the measures produce a number in the interval [0,1], with higher values indicating better performance. We show the complement of HL for easy of exposition.

6 Results and Discussion

The results for all datasets and evaluation measures are shown in Figure 1. As expected, the performance of the algorithms varies as we look at different evaluation measures.

BR shows the worst performance among the algorithms for almost all datasets/metrics, except for Emotions dataset, which has the smallest number of labels/attributes. However, the difference is more pronounced as we have more labels, low performance seen on Medical, Enron, and CAL500 datasets. It indicates that the information regarding dependence among labels, indeed, helps to improve performance.

The use of several performance measures is intended to show the distinct characteristics of the algorithms. As we can see in the plots, many algorithms do well for some metrics, while do poorly in others. To have an overall performance investigation we propose the use of a metric to compare all algorithms' relative performance. To do so, we use a measure inspired in a well-known metric in the literature of learn to rank, Discounted Cumulative Gain (DCG) [J¨arvelin and Kek¨al¨ainen, 2002]. Such measure we referred to here as relative performance (RP).

To obtain RP, first we compute the ranking r of all algorithms for a specific dataset/metric, then for a given algorithm a, RP(a) is obtained as: RP(a) = 1 if ra = 1 and RP(a) = 1/log2 r(a), otherwise. It basically gives higher values to algorithms at the top with a logarithm discount as the rank goes down. Similar to the definition DCG [J¨arvelin and Kek¨al¨ainen, 2002], RP also gives equal importance to the first and second best algorithms. RP can be seen as a special case of DCG metric used to measure learn to rank algorithms, where only one relevant (1) document is returned at position r and all other are non-relevant (0), given a query. RP value ranges from 0 to 1, with 1 representing that the algorithm figured at the top. The logarithm discount in RP induces a smoother penalization to algorithm's rank than when considering the ranks directly. Table 2 shows the RP values computed over all datasets for all pairs algorithm/metric.

I-MTSL obtained better accuracy when compared to the remaining methods, as it figures at the top of all the datasets. In essence, the accuracy computes the Jaccard similarity coefficient between the set of labels predicted by the algorithm and the observed labels. The algorithm is also at the top for the majority of the datasets regarding 1-HL, macro-F1, precision, and F1-score. Thus, I-MTSL obtained more balanced solutions, figuring at the top for the most of the analyzed metrics, except for recall. CMTL, LowRank, andMTF-FEAT, on the other hand, yielded the highest recall, but the lowest precision. Notice that it is easy to increase recall by predicting more 1's, however it may hurt accuracy, precision and F1score. As the class imbalance problem is recurrent in multilabel classification, it may deceive the algorithm to polarize the prediction to a certain class.

In terms of macro-F1, I-MTSL also outperforms the contenders. Macro-F1 evaluates the algorithm performance across the labels not across samples. It shows how good is an algorithm to classify labels independently. BR clearly has the worst result, which was expected, as BR is the only algorithm that does not use label dependence information.

Figure 2 presents examples of signed Laplacian matrices computed from the graph associated with the Ising model structure learned by I-MTSL for four of the datasets considered in the experiments. It is interesting to note the high sparsity of the matrices, showing that only a few tasks are conditionally dependent on each other and that structure led to a better classification performance. For some datasets, such as Enron, Medical, and Genbase we can clearly see a group of labels which are mutual dependent. Such matrix can be very useful in a posterior investigation regarding the reasons underlying those dependent labels.

7 Conclusion

We presented a method for multi-label classification problems that is capable of estimating the inherent label dependence structure. Such information is incorporated into the classifier learning process through a convex multi-task learning formulation. We model class labels as binary random variables and the interaction among the labels as an Ising Markov Random Field (I-MRF), so that the structure of the I-MRF captures the conditional dependence graph among the labels. We propose the use of a stability selection procedure to choose only stable label dependencies (graph connections). The problem of learning the labels dependence then reduces to the problem of structure learning in the Ising model, to which efficient methods have been recently proposed.

A comprehensive set of experiments on multi-label classification were carried out to demonstrate the effectiveness of the algorithm. Results showed its superior performance in several datasets and multiple evaluation metrics, when compared to already proposed multi-label and MTL algorithms. The algorithm exhibits the best compromise considering all performance metrics. Also, the learned graph associated with the I-MRF can be used in a posterior investigation regarding the reasons behind the relationship between labels.

Learning label dependence using more general graphical models (such as the ones described in Section 2.1) and embedding it into the binary relevance classifiers learning process will be the subject of future work.

Acknowledgments. ARG and FJVZ thank CNPq for the financial support. AB was supported by NSF grants IIS1447566, IIS-1422557,CCF-1451986, CNS-1314560, IIS0953274, IIS-1029711, NASA grant NNX12AQ39A, and gifts from Yahoo and IBM. Access to computing facilities were provided by University of Minnesota Supercomputing Institute (MSI).