Probabilistic Multi-Label Classification with Sparse Feature Learning

1 Introduction

Multi-label classification is a critical problem in many areas of data analysis, where each data instance can be assigned into multiple categories. For example, in image labeling [Zhou and Zhang, 2006] or video annotation [Qi et al., 2007], a given scene usually contains multiple objects of interests. In text categorization [Schapire and Singer, 2000], a given article or webpage can be assigned into multiple topic categories. In gene and protein function prediction [Elisseeff and Weston, 2002], multiple functions are typically associated with each gene and protein. Due to its complex nature, the labeling process of a multi-label data set is typically more expensive or time-consuming comparing to single-label cases, since the annotator needs to evaluate each class label even when the positive labels appear in a very sparse pattern. To mitigate the needs hence the cost of collecting labeled data, learning effective multi-label classifiers from a small number of training instances thus is important to be investigated.

One straightforward approach for multi-label classification is to cast the multi-label learning problem as a set of independent single label classification problems [Lewis et al., 2004; Chen et al., 2007]. This simple method has the obvious drawback of ignoring useful correlation information between the predictions of multiple labels. Developing methods to exploit the label dependency information and capture shared prediction structures among the multiple labels is critical in multi-label learning. In the literature, many approaches have been proposed to address multi-label learning by either exploiting label dependencies [Elisseeff and Weston, 2002; Godbole and Sarawagi, 2004; Guo and Gu, 2011; Schapire and Singer, 2000; Petterson and Caetano, 2011], or capturing the common prediction structures of the multiple binary prediction tasks associated with the individual classes [Yan et al., 2007; Zhang and Zhou, 2008; Yu et al., 2005; Ji et al., 2010]. But very few have taken both aspects into account for multi-label learning.

In this paper we propose a novel probabilistic multi-label classification model to simultaneously exploit both label dependency knowledge and shared prediction structures across labels based on sparse feature learning. Sparse feature learning has been effectively exploited in simultaneous multi-task learning problems by enforcing an ℓ2,1 norm [Argyriou et al., 2006; Liu et al., 2009; Obozinski et al., 2006]. Different from these works which consider only common input features, our model contains two types of features: structural label dependency features associated with each individual single-label prediction task, and common input features which are shared across the multiple single-label prediction tasks. We first propose to learn sparse label dependency structures by associating an ℓ1-norm regularization with the label dependency features, aiming to overcome possible overfitting issues. It induces a sparse conditional dependency network under probabilistic multi-label predictors. Then by adding another ℓ2,1-norm regularization over the input features, we formulate the overall probabilistic multi-label learning problem as a joint convex optimization problem with combined sparse norm regularizations, where an ℓ1-norm is used for the sparse structural feature selection, and an ℓ2,1-norm is used for selecting the discriminative input features shared across multiple binary predictors. We develop a fast proximal gradient algorithm to solve the proposed optimization problem for an optimal solution. Our empirical results on a number of multi-label data sets demonstrate the efficacy of the proposed approach when the number of training instances is small, comparing to a few related probabilistic methods.

The remainder of the paper is organized as follows. We introduce the related work on multi-label learning in Section 2. The proposed sparse multi-label learning method is presented in Section 3. We then report the experimental results in Section 4 and conclude the paper in Section 5.

2 Related work

Multi-label classification has received increasing attention from machine learning community in recent years, due to its wide applications in practice. There is a rich body of work on multi-label learning in the literature. We provide a review to the most related methods in this section.

One simple approach for multi-label classification is to cast the multi-label learning problem as a set of independent single label classification problems [Lewis et al., 2004; Chen et al., 2007]. Such an approach however is unsatisfactory, since the different labels occurring in a multi-label classification problem are not independent. On the contrary, they often exhibit strong correlations or dependencies. Capturing these correlations in different manners have led to many advanced developments in multi-label classification.

A significant number of multi-label learning approaches have been proposed to exploit label dependencies in classification model formulation, including ranking based methods [Elisseeff and Weston, 2002; Schapire and Singer, 2000; Shalev-Shwartz and Singer, 2006; Fuernkranz et al., 2008], pairwise label dependency methods [Zhu et al., 2005; Petterson and Caetano, 2011], probabilistic classifier chains [Dembczynski et al., 2010], large-margin methods [Guo and Schuurmans, 2011; Godbole and Sarawagi, 2004; Hariharan et al., 2010], and probabilistic graphical models [Ghamrawi and McCallum, 2005; de Waal and van der Gaag, 2007; Bielza et al., 2011; Zaragoza et al., 2011; Guo and Gu, 2011]. Most of these methods however involve resource-consuming optimization procedures or extensive model-structure learning processes. On the other hand, another set of methods attempt to exploit the relationships between multiple binary classification models in multi-label learning by capturing their common prediction structures [Yan et al., 2007; Zhang and Zhou, 2008; Yu et al., 2005; Ji et al., 2010]. These two types of multi-label prediction approaches have in general all achieved good empirical performance. However, very few methods have taken both aspects of label dependencies and shared model structures into account for multi-label learning. The Bayesian network models for multi-label learning [de Waal and van der Gaag, 2007; Bielza et al., 2011] although take steps in this direction by learning separate feature subnetwork, class subnetwork, and feature-class bridge subnetwork, they nevertheless are limited to problems with a small number of discrete feature variables.

The proposed approach in this paper aims to integrate the strengths of label dependency based methods and common prediction structure based methods within a novel convex sparse feature learning framework. From the perspective of capturing label dependency, our work is closely related to the simple multi-label learning methods in [Godbole and Sarawagi, 2004; Guo and Gu, 2011]. The work in [Godbole and Sarawagi, 2004] uses a very intuitive and simple procedure to exploit multi-label dependency information. It first trains a set of binary SVM classifiers, one for each of the K classes. Then it uses the K binary classifiers to produce K label features to augment the original features of each instance. Finally another set of K binary SVM classifiers are trained on the augmented instances. Its testing process follows a corresponding procedure. This work is simple and straightforward, but lacks of principled explanation. The work of [Guo and Gu, 2011] generalizes this intuitive idea into a principled probabilistic framework based on directed conditional dependency networks (CDNs), where each label variable takes all the other label variables as its parents. In a CDN model, the training of multiple binary prediction models can be interpreted as maximizing the approximated joint conditional distributions of the label variables. The training process is even simpler than the SVM method in [Godbole and Sarawagi, 2004]. It only requires training one set of K independent binary probabilistic classifiers, and a simple Gibbs sampling procedure is used for conducting inference in the testing phase. Nevertheless, the CDN model in [Guo and Gu, 2011] uses a fully connected directed graph as the label dependency structure, which can easily fall into the trap of overfitting, especially when there are a limited number of training instances. With sparse feature learning, the proposed approach in this paper aims to integrate the strength of the CDN model but overcome its drawbacks.

3 Multi-label Classification with Sparse Feature Learning

Assume we have a set of N multi-label training instances D = {(xi , yi1 , · · · , yiK )}Ni=1 , where xi ∈ IRd is a column feature vector, yik has value +1 when the kth label is assigned to instance i, and has value -1 otherwise. In this section, we present a sparse feature learning model for multi-label classification. We propose to first learn sparse label dependency features with ℓ1 norm under a probabilistic conditional dependency network framework, and then learn sparse discriminative common features shared among the multiple single-label predictors by conducting multi-task style learning. Together, these two steps of sparse feature learning contribute to a novel sparse multi-label optimization problem. We develop a fast proximal gradient algorithm to solve the formulated problem for a global solution.

3.1 Learning Sparse Label Dependency Features

Inspired by the CDN model, we plan to capture the label dependency information using the structural label dependency features within a probabilistic framework of conditional dependency networks. The fixed fully connected dependency structure used in [Guo and Gu, 2011] can capture arbitrary label interdependency relationships, but is prone to overfitting given a limited number of labeled training instances. It is important to identify the most informative structural label dependency features to use.

Let X denote all the feature variables and Y = {Y1, · · · , YK} denote the K label variables. The fully connected conditional dependency network assumes that each label variable Yk takes all the other label variables Yk = {Y1, · · · , Yk-1, Yk+1, · · · , YK} as its augmented parent features in addition to the input features X. Given the observation feature variables X and all label dependency feature variables Yk , a probabilistic prediction function is associated with each label variable Yk to define its local conditional probability distributions p(Yk|X,Yk ). Following the work [Guo and Gu, 2011], we use L2-norm regularized binary logistic regression classifiers as probabilistic predictors. For an instance (x, y1, · · · , yK), the conditional probability of each yk given all other variable values can be computed as follows using a logistic regression predictor

where θk = [wk; vk; bk] are the model parameters, wk is the weight vector for the input features x, vk is the classdependent weight vector for augmenting features yk , and bk is a bias term. Given the labeled training data D, K logistic regression predictors can be trained independently by minimizing the regularized log-loss of the training instances

for all k = 1 · · ·K. Here ‖ · ‖ denotes the Euclidean norm of a vector, λ1 and λ2 are tradeoff parameters that control the degree of regularization.

The objective function in (2) assumes each label variable Yk depends on all the other label dependency feature variables Yk . It corresponds to a fully connected directed graph over all the label variables Y1, · · · , YK. However, in practice, label dependencies often exhibit sparse patterns, and each Yk may only have dependency relationships with a subset label variables Yπk ⊆ Yk . Thus a fully connected structural dependency can easily capture spontaneous label correlation relationships and suffer from overfitting, especially when the training set is small. To tackle this problem and expose the sparse structure of conditional dependency networks, we add an ℓ1-norm regularization on parameters vk in each independent logistic regression training to learn sparse label dependency features:

As one of the simplest sparsity inducing norm, ℓ1-norm has been widely used for feature selection [Ng, 2004; Zou and Hastie, 2005]. The ℓ1-norm regularization here can push many elements of vk to zeros, which correspondingly will drop some Yt ⊂ Yk features and remove the directed edges from Yt to Yk. Moreover, with both ℓ1-norm and squared ℓ2norm over vk, it forms an elastic-net regularization [Zou and Hastie, 2005], which can lead to stabilized feature selection even when the data exhibits strong correlations among Yk .

3.2 Learning Common Predictive Features Shared Across Prediction Models

The sparse learning with ℓ1-norm above captures sparse structural label dependency features. We next consider the input features X. With a large set of input features available for use in a prediction task, it is often beneficial to use only an informative small subset of input features to reduce overfitting and improve generalization performance, especially when the labeled training set is small. Moreover, the multiple binary prediction tasks, one for each label variable prediction, are closely related within the same input feature space. It is thus essential to select the common predictive features shared across the multiple binary prediction models, with the expectation of improving the generalization performance of multi-label classification. This naturally forms a group feature selection problem over the model parameters associated with the common input features in the multiple binary prediction models. We employ a group sparsity inducing ℓ2,1-norm to conduct group feature selection and train K logistic regression classifiers in one joint minimization problem

where W = [w1, · · · ,wK] is a d ×K matrix, W:k denotes its kth column containing the parameter vector wk used for the kth logistic regression classifier; V = [v1, · · · , vK] is a (K - 1) × K matrix, V:k denotes its kth column containing the parameter vector vk used for the kth logistic regression classifier; b = [b1, · · · , bK]⊤ is a K × 1 vector containing the bias terms for the K logistic regression classifiers; ‖ · ‖F denotes the Frobenius norm, and the ℓ2,1-norm is defined as ‖W‖2,1 = ∑dj=1 ‖Wj:‖. This optimization problem encodes both sparse label dependency feature learning by the ℓ1-norm regularizers, ∑Kk=1 ‖V:k‖1, and common predictive feature learning by the ℓ2,1-norm regularizer, ‖W‖2,1.

ℓ2,1-norm has been frequently used for robust group feature selections in multi-task learning scenarios [Obozinski et al., 2006; Liu et al., 2009; Nie et al., 2010; Yang et al., 2011]. The multi-label learning problem can be viewed as a very special multi-task problem, where each task is the binary prediction problem associated with each class label. It is thus reasonable to use ℓ2,1-norm to induce robust common feature selections here. Although optimization problems with ℓ2,1norm regularizations have been addressed in different ways in the literature, the joint optimization problem we formulated above in (4) is unique from any previous work by containing three different types of norms: ℓ2-norm, ℓ1-norm, and ℓ2,1-norm. We will present a fast proximal gradient descent algorithm to solve this novel optimization problem.

3.3 Fast Proximal Gradient Descent

Although the minimization problem (4) is a convex optimization problem, the objective function is non-smooth due to the non-smoothness of the ℓ1-norm regularization terms and the ℓ2,1-norm regularization term. We develop a fast proximal gradient algorithm to solve this non-smooth optimization problem for a global optimal solution.

For simplicity of presentation, we use θ to denote the parameter column vector formed by combing all parameters

{W, V, b} together in a vector form, and use the notations θ and {W, V, b} in an interchangeable manner. Then (4) can be re-expressed as

where

The objective function F (θ) is a sum of two functions, where the first function f(θ) is a convex and smooth function, and the second function as a sum of ℓ1-norms and ℓ2,1 norm is convex but non-smooth. To develop a proximal optimization method, we consider the second order approximation of the objective function F (θ). For any L > 0, at a given point θ(t) , we define

where ∇f(θ(t) ) denotes the gradient function of f(·) regarding θ at point θ(t) .

Proposition 1 [Beck and Teboulle, 2009] Let L(f) denote the Lipschitz constant of ∇f(θ). Then for any L ≥ L(f), one has

It is straightforward to prove the Proposition based on the definition of Lipschitz constant and the convexity and smoothness of f(θ). From now on, we assume L ≥ L(f). According to Proposition 1, we have QL(θ, θ(t) ) ≥ F(θ). By minimizing QL(θ, θ(t) ), a unique solution can be returned,

where ̂ θ = (θ(t) - 1L ∇f(θ(t) )). The minimization in (10) can be equivalently decomposed into a set of separate minimization problems over W, {V:k}, b respectively, such as

Algorithm 1 Fast Proximal Gradient Algorithm

which have closed-form solutions. The closed-form solutions of the convex optimization problems with sparsityinducing norms in (11) and (12) can be computed by applying group soft-thresholding and direct soft-thresholding operators [Bach et al., 2011] respectively, such as

where the operator (·)+ = max(·, 0). The closed-form solution of (13) is

By conducting iterative updates according to Equation (10), we can obtain a sequence of points, θ(0) , θ(1) , . . ., to minimize the objective function F(θ). But to achieve an optimal convergence rate, we further adopt a fast convergence update scheme of FISTA [Beck and Teboulle, 2009]. The overall fast proximal gradient algorithm is given in Algorithm 1. With the fast update scheme, the iterative algorithm has a convergence rate of O( 1 t2 ), under the condition of QL(θ(t+1) , θ(t) ) ≥ F(θ(t+1) ). To find L values in each iteration guaranteeing QL(θ(t+1) , θ(t) ) ≥ F (θ(t+1) ), we use a step search procedure.

Testing After the training process, K logistic regression classifiers will be returned to define the conditional probabilistic distributions associated with each label variable given its parents. The sparse structure of the conditional dependency network is determined according to the V parameter matrix. Then given new instances, the prediction can be conducted using a Gibbs sampling inference algorithm, which is similar but more efficient than in the CDN model of [Guo and Gu, 2011].

4 Experiments

To evaluate the effectiveness and robustness of the proposed method on learning multi-label classification models from a small set of labeled training instances, we conducted experiments on six multi-label data sets, comparing the proposed approach to a number of alternative approaches. In this section, we report our experimental setting and results.

4.1 Experimental Setting

Data Sets We conducted experiments on six commonly used multi-label data sets, Corel 5k, IAPR TC12, MIR Flickr, Enron, Medical, and Bibtex. The first three data sets come from INRIA feature data sets, 1 which are benchmarks for computer vision tasks. The rest three data sets are for text categorizations, and can be found at mulan website. 2 For the three image data sets, we used SIFT descriptors as features. Each instance in these data sets is represented as a 1000-dimensional SIFT feature vector. The three text data sets, are represented in terms of 0-1 indicator features, in the size of 1001, 1449 and 1836 respectively. One key measure of multi-label data sets is their label cardinality [Tsoumakas and Katakis, 2007], which is defined as the average number labels assigned to each instance. Thus it should be a value between 1 and K, where K is the number of classes. The label cardinality of most existing multi-label data sets is small. However, if the label cardinality of a data set is close to 1, the multi-label classification task will be close to a standard single labeled multi-class task, and it does not make much sense to capture label dependencies on such a data set. The effectiveness of multi-label learning can most likely be demonstrated on data sets whose label cardinality is reasonably large. We thus chose ten most popular labels, i.e., labels most frequently appeared, from each of the six data sets to use, aiming to produce multi-label data sets with reasonable label cardinality values. According to these labels, we extract subsets from these data sets by eliminating instances not labeled with any one of the selected ten labels. Table 1 shows the statistics, data size and label cardinality information of these constructed data sets.

Methods We compared the following six probabilistic multi-label learning methods in the experiments:

1. LR, the baseline method that decomposes multi-label classification into a set of binary classification problems using 1-vs-all scheme, and uses binary logistic regression as classifiers;
2. PCC, the probabilistic multi-label chain classifiers developed in [Dembczynski et al., 2010];

1 http://lear.inrialpes.fr/people/guillaumin/data.php

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

1. CDN, the conditional dependency network method developed in [Guo and Gu, 2011];
2. ℓ1-CDN, the sparse CDN with an ℓ1-norm regularizer. This is the optimization problem we constructed in Eq. (3), which can be solved using a modified version of the proximal gradient algorithm in Algorithm 1;
3. ℓ2,1-LR, a variant of our proposed method by dropping the structural dependency features, which captures only the shared features among the multiple binary LR classifiers using a ℓ2,1-norm regularizer;
4. Sparse, the proposed sparse feature learning method, which is a combination of ℓ1-CDN and ℓ2,1-LR and captures both label interdependency and shared predictive features of multi-label learning.

EvaluationMeasures In our experiments, we used two F1 measures, Micro-F1 measure and Macro-F1 measure, to evaluate the multi-label prediction performance. The two F1 measures take both the precision and recall into accounts in different ways. The precision and recall, Pk and Rk, for each label k, are defined as follows:

where yik and ˆ yik are the true label value and predicted label value respectively for the ith instance on the k-th class; and (·)+ = max(·, 0). Then we have Micro-F1 and Macro-F1 measure as

4.2 Experimental Results

When there are sufficiently large number of training instances, good classification performance can be achieved even with simple binary classifiers. However, it is costly and time consuming to obtain labeled data and thus it is beneficial to develop methods that can learn good multi-label classification models with a small number of training instances. The purpose of our experiments is to investigate the performance of the proposed methods when the number of training instances is small. In particular, we conducted two sets of experiments on the constructed data sets using two different training sizes, |D| = {200, 400}.

In each set of experiments, with the given training size, we randomly divided each data set into partitions containing training set and test set, with a test size of 1000 when possible. The trade-off parameters for the comparison methods are pre-selected using one random training and test partition. The parameters are selected to maximize the average value of the two F1 measures. The methods, LR, CDN, ℓ1-CDN, ℓ2,1-LR, and Sparse, all involve some or all of the following trade-off parameters: λ1, λ2, γ, and µ. We set λ1 = λ2 = 0.1. γ and µ are selected from the following sets of values,

{1e-4 , 1e-3 , 1e-2 , 1e-1} and {1e-5 , 1e-4 , 1e-3 , 1e-2}, respectively.

With the selected parameters, we then repeatedly run each method 10 times on 10 sets of randomly partitioned training and test data. The average results for the six methods on the six data sets are presented in Table 2 and Table 3 in terms of Macro-F1 measure and Micro-F1 measure respectively. We can see that the PCC method, with an ensemble of different label interdependencies, has a clear win over LR except on the Bibtex data. With the small training sizes, although the CDN method still outperforms the baseline LR method in many cases, it has inferior performance on two data sets, Corel 5k and Bibtex. With an additional ℓ1-norm to induce sparse dependency structure, the resulted ℓ1-CDN can improve CDN in all cases except on the Mir Flicker data set. On the other hand, with only ℓ2,1-norm regularization, the ℓ2,1LR outperforms all the previous four methods on Corel 5k, Mir Flicker, and IAPR TC12 for both training sizes, and on Medical for training size 400. But on Enron, it demonstrates similar performance as ℓ1-CDN, and on Bibtex, it produces inferior performance even comparing to the baseline LR. By integrating the two types of sparse feature learning together, the proposed Sparse method, with both ℓ1-norm and ℓ2,1norm regularizations, outperforms all the other five methods on almost every data set of different training sizes, except only on the Medical with training size 400 where its performance is still competitive to the best. These results suggest that the two types of sparse feature learning over label dependency features and common input features respectively can complement each other in most cases, and our proposed sparse learning method provides an effective framework for integrating their strengths on multi-label classification.

5 Conclusions

In this paper we proposed a novel probabilistic multi-label classification model based on sparse feature learning. By employing an individual sparsity inducing ℓ1-norm and a group sparsity inducing ℓ2,1-norm together, the proposed model can induce both a sparse dependency network structure over the label variables, and a common set of predictive features across the multiple binary predictors associated with the multiple classes. The resulted optimization problem is a convex but non-smooth optimization problem. We developed a fast proximal gradient algorithm to solve the proposed problem for a global optimal solution. Our empirical results on a number of multi-label data sets show the proposed sparse learning approach can outperform a set of related probabilistic multi-label learning methods and produce effective results even when the number of training instances is small.