Learning for Tail Label Data: A Label-Specific Feature Approach

1 Introduction

Tail label data (TLD) is prevalent in real-world applications. It follows a power-law distribution (as illustrated in Figure 1), and provides irreplaceable information in comparison with head label data (HLD). For instance, in web page categorization [Ioannis et al., 2015], there are thousands of labels from Wikipedia and more than 70% of them occur in at most 15 web pages. Little information is gained by predicting popular labels such as "Poems" for the Divine Comedy article as compared to predicting relatively infrequent labels such as "Epic poems in Italian" (which implies "Poems" and more); in recommender systems [McAuley et al., 2015], popular items are well-known by users and recommending long-tailed items can delight users and boost the sales. Similar applications can be found in image annotation [Deng et al., 2009], video classification [Sami et al., 2016] and so on.

The major learning scheme to model TLD is large-scale multi-label learning (LMLL) [Hsiang-Fu et al., 2014]. It attempts to annotate unseen data with the most relevant subset of labels out of a huge collection including both head labels and tail labels. In the past few years, LMLL has attracted considerable attention and a large number of LMLL algorithms have been proposed, such as FastXML [Prabhu and Varma, 2014], LEML [Hsiang-Fu et al., 2014] and so on.

Previous LMLL studies need to additionally take into account extensive HLD, and fail to directly guide the learning of TLD. Specifically, existing approaches train models leveraging the entire label set and evaluate their learning performance considering both head labels and tail labels. Due to the large population of HLD, the learning performance is primarily dominated by HLD rather than TLD [Wei and Li, 2018; 2019]. In many applications, however, the prediction of tail label is very necessary, since it provides very important supplementary information. The question of learning prediction for TLD has not been thoroughly studied, though it is widely stated that tail labels are rewarding if predicted correctly [Himanshu et al., 2016; Xu et al., 2016].

In this work, focusing on the learning performance of TLD, we evaluate LMLL approaches explicitly on TLD rather than HLD. That is, during the inference phase, only tail labels with

P@1 (%)

0 the top-ranked predictive score for each unseen instance are predicted as relevant. We call this kind of learning problem as tail label learning. The main difficulty lies in the scarcity of positive examples of TLD. That is, only a handful of examples are positive for each tail label and the rest are negative examples. Moreover, the raw feature representation in LMLL data is usually high-dimensional and sparse [Prabhu and Varma, 2014], which usually benefits HLD and may not be suitable for TLD (as illustrated in Figure 2).

To alleviate these issues, in this paper, we present an efficient algorithm named TAIL, i.e., learning for TAIL label data. Inspired by [Zhang and Wu, 2015], we consider constructing discriminative features specific to every tail label, i.e., label-specific features, with a low-dimensional feature space. Our basic idea is that different class labels usually carry specific characteristics of their own, and it could be beneficial to exploit different feature sets for the discrimination of different labels. Based on this recognition, TAIL induces classification learners TLD based on generated label-specific features rather than the original input features. Specifically, we construct label-specific features from two perspectives. First, to explore discriminative features, we construct label-specific features w.r.t instances through clustering analysis on its positive and negative instances for each tail label. Second, on the aspect of label correlations, we encode knowledge from HLD by exploiting the relationship between head labels and tail labels, i.e., label-specific features w.r.t labels, to enhance label-specific features. Concretely, we build a k-NN graph which characterizes the affinity among labels and aggregate the predictive information from head label classifiers into generated features for each tail label. Furthermore, to mitigate the class-imbalance problem, we leverage the negative sampling strategy to balance the population of positive and negative instances. Extensive experimental comparisons and studies verify the effectiveness of the proposed method.

The rest of this paper is organized as follows. We start by a brief review of related work. Then we present the proposed approach. After that, experimental results are reported followed by the conclusion of this work.

2 RelatedWork

This work is mostly related to tail label problem and feature construction in LMLL.

Tail Label in LMLL

Recently, there are some discussions on the power law distribution in LMLL.Himanshu et al. [2016] explained that infrequently occurring tail labels are harder to predict than frequently occurring ones since they have little training examples. Xu et al. [2016] treated tail labels as outliers and decomposed the label matrix into a low-rank matrix which depicts label correlations and a sparse one capturing the influence of tail labels. Wang et al. [2017] cast the tail label problem as transfer learning by transferring knowledge from the data-rich head to the data-poor tail class labels. Babbar and Sch¨olkopf [2018] viewed the tail label problem as a setup in which an adversary is generating test examples such that the features of the test set instances are quite different from those in the training set. The tail label problem is also related to weakly supervised learning [Li and Liang, 2019; Li et al., 2016]. Most of these studies, learn from LMLL data by manipulating with the identical feature set, which may be not suitable for TLD, i.e., the original high-dimensional and sparse features are employed in training and inference processes of the entire label set.

LMLL Feature Construction

There are some studies about multi-label feature selection. For example, Zhang et al. [2009] adapted the classical naive Bayes classifiers. Ma et al. [2012] proposed to learn a feature subspace that is shared among multiple different classes. Jian et al. [2016] introduced a principled way of exploiting label correlations for feature selection in the presence of noisy and incomplete label information.

Existing approaches need to additionally take into account HLD and are unable to guide the learning of TLD. In addition, the performance of LMLL approaches on tail labels has not been investigated. To the best of our knowledge, this is the first time learning label-specific features for tail labels is studied.

3 The Proposed Approach

In the following, we first introduce the problem setup and then present the label-specific feature construction method.

3.1 Preliminary

Let X denote the input space and Y the output space, and the number of labels K := |Y|, where | · | represents the set cardinality. Labeled samples are pairs (x,P) with x ∈ X and P ∈ Y which denotes the set of correct labels for the instance x. We use the notation N := Y \ P to denote the set of negative labels for the example. Given a collection of N training samples {xi, Pi}Ni=1 , LMLL aims to learn a scoring function f : X →RK for a large output space Y.

Considering that, head label prediction could be done very well using off-the-shelf LMLL approaches [Hsiang-Fu et al., 2014; Bhatia et al., 2015; Babbar and Sch¨olkopf, 2017], for the inference concerning tail labels, we employ a specially designed model to achieve better performance than LMLL approaches. Such setting is feasible because, in LMLL systems, we could always separately predict a few head labels and tail labels as relevant. By splitting the label space into two parts, Yc ⊂ Y and Yt = Y \ Yc represent head labels and tail labels, respectively. Let Kc := |Yc| and Kt := |Yt|. Formally, we define the head label and tail label in Definition 1.

Definition 1 (Head Label & Tail Label). Let D = {xi, Pi}Ni=1 be a large-scale multi-label data set where labels follow a power-law distribution. Suppose labels {l1, · · · , lK} are organized by frequencies in descending order where ∑Nj=1 I(li ∈ Pj) >= ∑Nj=1 I(li+1 ∈ Pj), ∀1 ≤ i ≤ K - 1. Frequently occurring labels {l1, · · · , lKc } are referred to as head labels and infrequently occurring ones {lKc+1, · · · , lK} are referred to as tail labels.

3.2 Label-specific Feature Construction

Recently, many effective strategies are proposed to learn more discriminative features [Zhang and Wu, 2015; Jia and Zhang, 2019]. However, these studies typically focus on traditional multi-label learning problems, which do not finalize a systematical solution for tail label learning. Inspired by previous studies, we propose to improve the learning performance on TLD through constructing label-specific features.

Specifically, given a data set D = {xi, Pi}Ni=1 , TAIL constructs label-specific features for each tail label from D following two elemental steps, i.e., label-specific feature construction w.r.t instances and label-specific feature construction w.r.t labels. Then it induces classification models based on generated features instead of the original input features. In the following, we present details of the label-specific feature construction strategies.

Label-specific Feature Construction w.r.t Instances

In the first step, TAIL aims to generate distinguishing features which capture the specific characteristics of each tail label to facilitate its discrimination process. To this end, TAIL investigates data distribution properties by employing clustering analysis method which has been widely used [Zhang and Wu, 2015]. In particular, with respect to tail label li, ∀Kc < i ≤ K, the set of positive training instances ˜ Pi as well as the set of negative training instances ˜Ni are denoted as follows:

In other words, ˜ Pi and ˜Ni consist of the training instances in D with and without label li, respectively. Similar to [Zhang and Wu, 2015], we adopt the popular k-means algorithm to partition ˜ Pi into m+i disjoint clusters whose centers are denoted as {pi1 , pi2 , · · · , pim+i }. Similarly, ˜Ni is also partitioned into m-i disjoint clusters whose centers are denoted as {ni1 ,ni2 , · · · ,nim-i }. Following the setting in [Zhang and Wu, 2015], we choose to set equivalent number of clusters for ˜ Pi and ˜Ni, i.e. m+i = m-i = mi. In this way, clustering information gained from positive instances as well as negative instances are treated with equal importance. Specifically, the number of clusters retained for both positive and negative instances is set to be:

Here, γ ∈ [0, 1] is the ratio parameter controlling the number of clusters. Intuitively, the retained cluster centers characterize the underlying structure of input space and can be used as the bases for label-specific feature construction.

In detail, TAIL builds a mapping φi from the original ddimensional feature space X to the 2mi-dimensional labelspecific feature space as follows:

Here, d(·, ·) represents the distance metric and is set to the Euclidean metric following [Zhang and Wu, 2015].

Label-specific Feature Construction w.r.t Labels

In the second step, TAIL aims to enhance label-specific features by exploiting label correlations between head labels and tail labels. We leverage label cooccurrence statistics obtained from training data to build a connection between head labels and tail labels. Specifically, similarity is computed for each pair of tail label and head label (li, lj) by sim(li, lj) = | ˜ Pi ∩ ˜ Pj|, ∀1 ≤ j ≤ Kc < i ≤ K. After that, we construct a k-NN graph that is known for its good performance [Ebert et al., 2010; Maier et al., 2009] using dist(li, lj) = N - sim(li, lj) as the distance metric, i.e.,

To leverage the correlations between head labels and tail labels, for instance x, we apply Kc classifiers {f1, . . . , fKc } for head labels on x and take the predictive information as transferred knowledge. More precisely, for tail label li and head label lj, the predictive information of ¯ fj is filtered by Wi,j ⊙ fj(x). If Wi,j = 1, then fj(x) is selected as one of generated features, otherwise discarded. By doing this, the relationship between labels is encoded as augmented feature representations, which is proved beneficial for building classification models in our experiments.

In detail, TAIL builds a label correlation aware mapping ψi for tail label li from the original D-dimensional feature space X to the k-dimensional label specific feature space as follows:

Finally, TAIL induces a family of Kt = K - Kc classification models {fKc+1, . . . , fK} by aggregating feature mappings φ(·) and ψ(·). Specifically, for tail label li, a binary training set D∗ i with m examples is created from D by applying our two label-specific feature generation steps. Algorithm 1 lists the details of TAIL approach.

3.3 Computational Complexity Analysis

For each tail label, it first takes O(2minDT) and O(N ¯L2 + KtKc log k) to construct two types of label-specific features, respectively. Here, T is the number of iterations when performing k-means, k is set to 5 in k-NN search, ¯L is the averaged number of relevant labels per instance, and n ≪N is the total number of examples after negative downsampling. Subsequently, TAIL builds a linear classifier in O((2mi + k)n). Therefore the total computational cost to train TAIL for

Algorithm 1 The pseudo-code of TAIL

Input:

• D: LMLL training set D = {xi, Pi}Ni=1
• Kc: the number of head labels
• k: the number of nearest neighbors considered
• γ: the ratio parameter controlling the number of clusters
• L: the binary classification learner

Output:

{fi}Ki=Kc+1 : a family of tail label classifiers

Process:

• 1: for i =Kc +1, . . . ,K do
• 2: Construct ˜ Pi and ˜Ni based on D according to Eq. (1)
• 3: Perform k-means clustering on ˜ Pi and ˜Ni, each with mi clusters as defined by Eq. (2)
• 4: Construct the mapping φi for li according to Eq. (3)
• 5: Compute k-NN adjacent matrix according to Eq. (4)
• 6: Construct the mapping ψi for li according to Eq. (5)
• 7: Aggregate label-specific features by concatenating φi and ψi for li
• 8: Induce fi by invoking a binary learner L on the constructed label-specific features for li
• 9: end for
• 10: return {fi}Ki=Kc+1

each label is O(minDT + N¯L2 + KtKc log k) thanks to (2mi + k)n ≪ minDT. Note that, for the i-th tail label, 1 ≤ i ≤ Kt, the dimensionality of constructed feature representation in D∗ i is exactly 2mi +k ≪D. In the testing stage, the computational cost for TAIL to predict a new instance is O((2mi + k)D) per label. both the training and testing phase of multiple tail labels can be easily parallelized.

The analysis shows that the total computational complexities scale linearly with size of the data set. Thus, both methods are very suitable for the LMLL applications.

4 Experiments

We conduct comprehensive experiments on LMLL benchmark data sets to evaluate the efficacy of our proposal.

4.1 Experimental Setup

Experiments are conducted on four benchmark data sets with the number of labels ranging from 159 to 30K. Table 1 lists the detailed statistics. We report and compare the results using the same train/test splits of data sets. All the data sets as well as the code of compared methods are publicly available 1 . Notably, hundreds of labels on EUR-Lex data set do not have any positive example available in the training set, and thus we discard such labels. In all of our experiments, we fix the number of nearest neighbors considered to 5, i.e., k = 5. We set the ratio parameter γ during clustering to 0.1 following the setting in [Zhang and Wu, 2015]. For other comparison methods, we use the default parameter settings in the code.

Computational Device

All experimental comparisons are conducted on the same PC machine with an Intel i5-6500 3.20GHz CPU and 32GB RAM.

1 http://manikvarma.org/downloads/XC/XMLRepository.html

Compared Methods

We compare our method to Binary Relevance (BR) and seven state-of-the-art LMLL approaches.

• Binary Relevance [Zhang and Zhou, 2014] builds OvR SVM for each label using Liblinear [Fan et al., 2008].
• LEML [Hsiang-Fu et al., 2014] is an embedding method based on low-rank empirical risk minimization.
• FastXML [Prabhu and Varma, 2014] is a random forestbased LMLL approach.
• SLEEC [Bhatia et al., 2015] learns the embedding of labels by preserving the pairwise distances between a few nearest label neighbors.
• CoH [Shen et al., 2018] proposes a co-hashing method which jointly compresses the input and output into compact binary embeddings.
• DisMEC [Babbar and Sch¨olkopf, 2017] learns a 1vsA linear-SVM in a distributed fashion.
• PD-Sparse [Yen et al., 2016] proposes to solve ℓ1 regularized multi-class loss using Frank-Wolfe based algorithm.
• REML [Xu et al., 2016] proposes to decompose label matrix into a low-rank matrix and a sparse matrix to model head labels and tail labels respectively.

We build TAIL based on Liblinear using constructed labelspecific features. For comparison methods, we first obtain predictive scores over the entire label set and take top k tail labels with the highest predictive score for evaluation.

Performance Metrics

In LMLL applications, e.g., recommender systems, only the top k ranked labels are concerned, where P@k and nDCG@k are widely used [Himanshu et al., 2016]. Accordingly, P@k and nDCG@k are defined as

where DCG@k(z,P) := ∑l∈rankk(z) I(l∈P) log(l+1) . Here, z is the predicted score vector of instance x and P is the true label set. The indicator function I(·) returns 1 if the condition is true, otherwise 0.

4.2 Comparison with Baseline Approach

We first study the effectiveness of TAIL at improving performance in comparison to Binary Relevance (BR) using raw features. Table 2 depicts the comparison results. On relatively small data set Bibtex, TAIL achieves competitive results across six different metrics. Considering the relatively balanced label distribution due to the small label set, it might be inaccurate to capture label relationship between head labels and tail labels.

On the other three larger data sets with high-dimensional label space, TAIL improves the prediction accuracy with a relatively large margin in most cases. This justifies the superiority of constructed label-specific features to raw features.

4.3 Comparison with State-of-the-art Approaches

In this experiment, we compare the performance of TAIL with state-of-the-art methods: FastXML, LEML, SLEEC, DiS- MEC, CoH, PD-Sparse, and REML. As demonstrated in Table 3, TAIL achieves better performance compared to stateof-the-art approaches, which demonstrates the merit of labelspecific features. Specifically, TAIL achieves the best or second best performance on TLD in 23 out of 24 cases. Sophisticated solvers, such as FastXML, LEML, and SLEEC, does not achieve as good performance on tail labels as on head labels. The reason may owe to the fact of population bias among the training set. Note that, the predictive accuracy on TLD is very limited especially on larger data sets because scarce positive examples are not sufficient to learn satisfactory models. Specifically, there are more than 20% of labels have no more than 1 associated instance on Wiki10 and EUR-Lex data sets. In order to gain better learning performance on tail labels, it is necessary to leverage side information, such as the semantic meaning of each class label or the underlying structure among labels.

4.4 Influences of Two Feature Construction Steps

To study the effectiveness of label-specific features w.r.t. instances and labels separately, we report performance by employing only label-specific features w.r.t. instances in Table 4 and label-specific features w.r.t. instances in Table 5. As depicted in Table 4, in comparison with the results in Table 2, it results in more than 30% performance degradation depicting the importance of label relationship. Conversely, performance degrades when only label-specific features w.r.t. labels are employed, which is in line with the observations of Table 4. The case study justifies that both label-specific feature construction steps are vital to the learning performance of TLD.

4.5 Parameter Sensitivities Analysis

We further investigate the influence of the number of tail labels Kt to the performance of TAIL in comparison with LEML, FastXML, and SLEEC. We vary the percentage of tail labels ranging from {10%, 20%, 30%, 40%} for comparison. Figure 3 demonstrates that the performance is getting better as the value of Kt grows, which is very intuitive because it is easier to model head labels compared with tail ones and richer information can be leveraged and make knowledge transferring feasible. For different values of Kt, TAIL consistently outperforms competing methods. It can be seen that TAIL can capture label relationships as good as leading LMLL approach SLEEC when extra HLD is available.

5 Conclusion

In this paper, for the first time, we attempt to improve the learning performance on tail label data and we call this kind of learning problem as tail label learning. A data-level solution named TAIL is proposed to directly guide the learning of tail label data through extracting label-specific features. It replaces the original high-dimensional and sparse feature representation which may not be suitable for tail label data. Specifically, TAIL constructs label-specific features concerning each tail label through exploring data distribution and leveraging label correlations. Extensive empirical studies on benchmark data sets demonstrate that the learning performance of tail label data is clearly improved and validate the effectiveness of the proposed approach. In the sequel, it is interesting to investigate the sample generation mechanism of tail label learning.

Acknowledgments

This research was supported by the National Key R&D Program of China (2017YFB1002201), the National Natural Science Foundation of China (61772262) and the Fundamental Research Funds for the Central Universities (020214380053).