---
title: "Learning for Tail Label Data: A Label-Specific Feature Approach"
authors:
  - "Tong Wei"
  - "Wei-Wei Tu"
  - "Yu-Feng Li"
doi: "10.24963/ijcai.2019/533"
url: "https://ijcai.org/proceedings/2019/533"
pdf: "https://ijcai.org/proceedings/2019/0533.pdf"
venue: "Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence"
year: 2019
pages: "3842-3848"
track: "Main track"
keywords:
  - "Machine Learning: Multi-instance;Multi-label;Multi-view learning"
  - "Machine Learning: Classification"
---

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

Tong Wei, Wei-Wei Tu, Yu-Feng Li

*Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence*, pages 3842-3848. DOI: [10.24963/ijcai.2019/533](https://doi.org/10.24963/ijcai.2019/533)

## Abstract

Tail label data (TLD) is prevalent in real-world tasks, and large-scale multi-label learning (LMLL) is its major learning scheme. Previous LMLL studies typically need to additionally take into account extensive head label data (HLD), and thus fail to guide the learning behavior of TLD. In many applications such as recommender systems, however, the prediction of tail label is very necessary, since it provides very important supplementary information. We call this kind of problem as \emph{tail label learning}. In this paper, we propose a novel method for the tail label learning problem. Based on the observation that the raw feature representation in LMLL data usually benefits HLD, which may not be suitable for TLD, we construct effective and rich label-specific features through exploring labeled data distribution and leveraging label correlations. Specifically, we employ clustering analysis to explore discriminative features for each tail label replacing the original high-dimensional and sparse features. In addition, due to the scarcity of positive examples of TLD, we encode knowledge from HLD by exploiting label correlations to enhance the label-specific features. Experimental results verify the superiority of the proposed method in terms of performance on TLD.

## Full text

## 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.

Figure 1: The number of examples for each label is presented on Wiki10 data set. The horizontal axis indicates the indices of labels, while the vertical axis indicates the number of associated examples in the training data. The vertical red line indicates that labels to the left of it (more than 70%) occur in at most 15 examples.

![Image](https://ijcai.org/proceedings/2019/fulltext/533/image_000000_affd1f4ba169aac39afca9e4a7cd8fd23d14e9bd82d0da533d79dedee47ecc54.png)

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

Figure 2: Performance (P@1) of Binary Relevance approach on Bibtex and Delicious data sets with the raw feature representation and the constructed label-specific features respectively. As can be seen, raw features usually benefit HLD rather than TLD. With labelspecific features, the performance on TLD is clearly increased.

![Image](https://ijcai.org/proceedings/2019/fulltext/533/image_000001_da45d7a502522d63eb830133d2ccd8a24ebfab5f0c0f85cb126c2ca8ab889e01.png)

## 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:

<!-- formula-not-decoded -->

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:

<!-- formula-not-decoded -->

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:

<!-- formula-not-decoded -->

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 &lt; 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.,

<!-- formula-not-decoded -->

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:

<!-- formula-not-decoded -->

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

Table 1: Data set statistics

| Data set   |   Train N |   Features D |   Labels K |   Test M |   Avg. labels per point |   Avg. points per label |
|------------|-----------|--------------|------------|----------|-------------------------|-------------------------|
| Bibtex     |     4,880 |        1,836 |        159 |    2,515 |                    2.40 |                  111.71 |
| Delicious  |    12,920 |          500 |        983 |    3,185 |                   19.03 |                  311.61 |
| EUR-Lex    |    15,539 |        5,000 |      3,993 |    3,809 |                    5.31 |                   25.73 |
| Wiki10     |    14,146 |      101,938 |     30,938 |    6,616 |                   18.64 |                    8.52 |

## 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

<!-- formula-not-decoded -->

<!-- formula-not-decoded -->

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.

Table 2: Performance comparison between the proposed TAIL and BR in terms of P@k and nDCG@k with the number of tail labels Kt = K 10 for small data sets (Bibtex, Delicious) and Kt = K2 for large ones (EUR-Lex, Wiki10). The best results in terms of each metric are in bold.

| Data set   |         | P@1 (%)   | P@3 (%)   | P@5 (%)   | nDCG@1 (%)   | nDCG@3 (%)   | nDCG@5 (%)   |
|------------|---------|-----------|-----------|-----------|--------------|--------------|--------------|
| Bibtex     | BR TAIL | 8.95 9.18 | 4.04 4.04 | 2.54 2.54 | 8.95 9.18    | 10.29 10.37  | 10.52 10.58  |
| Delicious  | BR TAIL | 1.85 4.71 | 1.55 2.69 | 1.41 1.92 | 1.85 4.71    | 2.98 5.87    | 3.83 6.41    |
| EUR-Lex    | BR TAIL | 6.98 6.30 | 3.68 3.57 | 2.49 2.28 | 2.68 3.06    | 8.01 8.62    | 8.47 8.31    |
| Wiki10     | BR TAIL | 5.34 5.52 | 4.10 5.10 | 4.09 4.46 | 4.36 4.60    | 4.12 5.12    | 4.17 5.57    |

Table 3: Comparison with state-of-the-art approaches in terms of PSP@k and PSnDCG@k with Kt = K 10 for small data sets and Kt = K2 for large data sets. The best and second best results are in bold.

| Data set   |            |   FastXML |   LEML |   SLEEC |   CoH |   DiSMEC |   PD-Sparse |   REML |   TAIL |
|------------|------------|-----------|--------|---------|-------|----------|-------------|--------|--------|
| Bibtex     | P@1 (%)    |      5.90 |   5.57 |    8.97 |  6.53 |     8.43 |        4.34 |   5.72 |   9.18 |
| Bibtex     | P@3 (%)    |      1.97 |   1.86 |    3.93 |  2.20 |     3.90 |        2.77 |   2.03 |   4.04 |
| Bibtex     | P@5 (%)    |      1.18 |   1.11 |    1.50 |  1.59 |     2.54 |        1.93 |   1.24 |   2.54 |
| Bibtex     | nDCG@1 (%) |      6.17 |   5.61 |    2.21 |  6.58 |     8.60 |        4.34 |   2.01 |   9.18 |
| Bibtex     | nDCG@3 (%) |      2.28 |   1.86 |    6.99 |  3.62 |    10.30 |        4.49 |   2.76 |  10.37 |
| Bibtex     | nDCG@5 (%) |      2.11 |   1.67 |    8.46 |  2.06 |    10.32 |        5.72 |   4.58 |  10.58 |
| Delicious  | P@1 (%)    |      2.38 |   2.24 |    3.11 |  1.24 |     2.02 |        1.22 |   2.77 |   4.71 |
| Delicious  | P@3 (%)    |      0.79 |   0.75 |    2.21 |  1.82 |     1.78 |        1.03 |   1.26 |   2.69 |
| Delicious  | P@5 (%)    |      0.48 |   0.45 |    1.53 |  0.11 |     1.50 |        0.85 |   0.93 |   1.92 |
| Delicious  | nDCG@1 (%) |      1.27 |   1.92 |    1.11 |  1.43 |     1.85 |        1.22 |   1.55 |   4.71 |
| Delicious  | nDCG@3 (%) |      1.71 |   0.64 |    2.50 |  2.16 |     2.96 |        1.80 |   1.82 |   5.87 |
| Delicious  | nDCG@5 (%) |      2.62 |   0.55 |    3.41 |  2.20 |     3.87 |        2.61 |   3.00 |   6.41 |
| EUR-Lex    | P@1 (%)    |      6.15 |   0.21 |    6.24 |  3.87 |     7.22 |        2.28 |   5.79 |   6.30 |
| EUR-Lex    | P@3 (%)    |      2.72 |   0.07 |    2.09 |  1.98 |     3.54 |        2.00 |   2.54 |   3.57 |
| EUR-Lex    | P@5 (%)    |      1.63 |   0.04 |    1.76 |  1.89 |     2.83 |        1.89 |   1.20 |   2.28 |
| EUR-Lex    | nDCG@1 (%) |      2.24 |   0.23 |    2.25 |  3.78 |     2.62 |        1.27 |   1.91 |   3.06 |
| EUR-Lex    | nDCG@3 (%) |      5.95 |   0.07 |    5.35 |  1.49 |     8.30 |        1.96 |   4.20 |   8.62 |
| EUR-Lex    | nDCG@5 (%) |      6.83 |   0.06 |    6.30 |  1.92 |     8.90 |        2.44 |   5.41 |   8.31 |
| Wiki10     | P@1 (%)    |      4.34 |   4.82 |    5.14 |  3.03 |     4.61 |        3.98 |   3.48 |   5.52 |
| Wiki10     | P@3 (%)    |      1.45 |   1.61 |    4.86 |  1.56 |     4.10 |        1.60 |   1.27 |   5.10 |
| Wiki10     | P@5 (%)    |      0.87 |   0.96 |    3.40 |  1.09 |     4.80 |        1.19 |   0.43 |   4.46 |
| Wiki10     | nDCG@1 (%) |      5.06 |   4.46 |    5.14 |  3.41 |     5.00 |        1.01 |   4.28 |   4.60 |
| Wiki10     | nDCG@3 (%) |      1.48 |   1.47 |    4.87 |  3.25 |     5.27 |        1.90 |   1.59 |   5.12 |
| Wiki10     | nDCG@5 (%) |      1.29 |   1.25 |    3.46 |  3.09 |     5.36 |        1.96 |   1.30 |   5.57 |

## 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.

Figure 3: Studies on different values of Kt on data sets Bibtex (left) and Delicious (right). X-axis: value of Kt(%). Y-axis: P@5 (%).

![Image](https://ijcai.org/proceedings/2019/fulltext/533/image_000002_8dfce3c7e00ea4b1fa07b00608913c4ca73b2b341a02954bb57374f5d3d6c0e3.png)

Table 4: Experimental results of employing only label-specific features w.r.t. instances.

| Data set   |   P@1 (%) |   P@3 (%) |   P@5 (%) |
|------------|-----------|-----------|-----------|
| Bibtex     |      7.12 |      2.20 |      1.61 |
| Delicious  |      3.82 |      2.07 |      0.88 |
| EUR-Lex    |      4.50 |      2.00 |      0.42 |

## 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.

Table 5: Experimental results of employing only label-specific features w.r.t. labels.

| Data set   |   P@1 (%) |   P@3 (%) |   P@5 (%) |
|------------|-----------|-----------|-----------|
| Bibtex     |      6.30 |      1.32 |      0.66 |
| Delicious  |      3.02 |      1.96 |      0.38 |
| EUR-Lex    |      4.83 |      2.43 |      1.13 |

## 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&amp;D Program of China (2017YFB1002201), the National Natural Science Foundation of China (61772262) and the Fundamental Research Funds for the Central Universities (020214380053).

## References

1. [Babbar and Schölkopf, 2017] Rohit Babbar and Bernhard Schölkopf. Dismec: Distributed sparse machines for ex- treme multi-label classification. In Proceedings of the 10th ACM International Conference on Web Search and Data Mining, pages 721-729, Cambridge, UK, 2017.
2. [Babbar and Schölkopf, 2018] Rohit Babbar and Bernhard Schölkopf. Adversarial extreme multi-label classification. arXiv preprint arXiv:1803.01570, 2018.
3. [Bhatia et al., 2015] Kush Bhatia, Himanshu Jain, Purushot- tam Kar, Manik Varma, and Prateek Jbabain. Sparse local embeddings for extreme multi-label classification. In Ad- vances in Neural Information Processing Systems 28, pages 730-738. Montreal, Canada, 2015.
4. [Deng et al., 2009] Jia Deng, Wei Dong, Richard Socher, Li- Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In Proceedings of the 22nd IEEE Conference on Computer Vision and Pattern Recog- nition, pages 248-255, Miami, FL, 2009.
5. [Ebert et al., 2010] Sandra Ebert, Diane Larlus, and Bernt Schiele. Extracting structures in image collections for ob- ject recognition. In Proceedings of European Conference on Computer Vision, pages 720-733, Heraklion, Greece, 2010.
6. [Fan et al., 2008] Rong-En Fan, Kai-Wei Chang, Cho-Jui Hsieh, Xiang-Rui Wang, and Chih-Jen Lin. Liblinear: A library for large linear classification. Journal of Machine Learning Research, 9:1871-1874, 2008.
7. [Himanshu et al., 2016] Jain Himanshu, Prabhu Yashoteja, and Manik Varma. Extreme multi-label loss functions for recommendation, tagging, ranking & other missing label applications. In Proceedings of the 22nd ACM SIGKDD In- ternational Conference on Knowledge Discovery and Data Mining, pages 935-944, San Francisco, CA, 2016.
8. [Hsiang-Fu et al., 2014] Yu Hsiang-Fu, Jain Prateek, Kar Pu- rushottam, and Dhillon Inderjit S. Large-scale multi-label learning with missing labels. In Proceedings of the 31st International Conference on Machine Learning, pages 593- 601, Beijing, China, 2014.
9. [Ioannis et al., 2015] Partalas Ioannis, Kosmopoulos Aris, Baskiotis Nicolas, Artieres Thierry, Paliouras George, Gaussier Eric, Androutsopoulos Ion, Amini Massih-Reza, and Galinari Patrick. Lshtc: A benchmark for large-scale text classification. arXiv preprint arXiv:1503.08581, 2015.
10. [Jia and Zhang, 2019] Bin-Bin Jia and Min-Ling Zhang. Multi-dimensional classification via knn feature augmen- tation. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, Honolulu, HI, 2019.
11. [Jian et al., 2016] Ling Jian, Jundong Li, Kai Shu, and Huan Liu. Multi-label informed feature selection. In Proceedings of the 25th International Joint Conference on Artificial Intelligence, pages 1627-1633, New York City, NY, 2016.
12. [Li and Liang, 2019] Yu-Feng Li and De-Ming Liang. Safe semi-supervised learning: a brief introduction. Frontiers of Computer Science, 13(4):669-676, 2019.
13. [Li et al., 2016] Yu-Feng Li, Shao-Bo Wang, and Zhi-Hua Zhou. Graph quality judgement: A large margin expedition. In Proceedings of the 25th International Joint Conference on Artificial Intelligence, pages 1725-1731, New York City, NY, 2016.
14. [Ma et al., 2012] Zhigang Ma, Feiping Nie, Yi Yang, Jasper R. Uijlings, and Nicu Sebe. Web image annota- tion via subspace-sparsity collaborated feature selection. IEEE Transactions on Multimedia, 14(4):1021-1030, 2012.
15. [Maier et al., 2009] Markus Maier, Ulrike von Luxburg, and Matthias Hein. Influence of graph construction on graph- based clustering measures. In Advances in Neural Informa- tion Processing Systems 22, pages 1025-1032, Vancouver, Canada, 2009.
16. [McAuley et al., 2015] Julian McAuley, Rahul Pandey, and Jure Leskovec. Inferring networks of substitutable and complementary products. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discov- ery and Data Mining, pages 785-794, Sydney, Australia, 2015.
17. [Prabhu and Varma, 2014] Yashoteja Prabhu and Manik Varma. Fastxml: A fast, accurate and stable tree-classifier for extreme multi-label learning. In Proceedings of the 20th ACM SIGKDD International Conference on Knowl- edge Discovery and Data Mining, pages 263-272, New York City, NY, 2014.
18. [Sami et al., 2016] Abu-El-Haija Sami, Kothari Nisarg, Lee Joonseok, Natsev Paul, Toderici George, Varadarajan Bal- akrishnan, and Vijayanarasimhan Sudheendra. Youtube- 8m: A large-scale video classification benchmark. arXiv preprint arXiv:1609.08675, 2016.
19. [Shen et al., 2018] Xiaobo Shen, Weiwei Liu, Ivor W. Tsang, Quan-Sen Sun, and Yew-Soon Ong. Compact multi-label learning. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pages 4066-4073, New Orleans, LA, 2018.
20. [Wang et al., 2017] Yu-Xiong Wang, Deva Ramanan, and Martial Hebert. Learning to model the tail. In Advances in Neural Information Processing Systems 30, pages 7032- 7042, Long Beach, CA, 2017.
21. [Wei and Li, 2018] Tong Wei and Yu-Feng Li. Does tail label help for large-scale multi-label learning. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 2847-2853, Stockholm, Sweden, 2018.
22. [Wei and Li, 2019] Tong Wei and Yu-Feng Li. Learning com- pact model for large-scale multi-label data. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, Hon- olulu, HI, 2019.
23. [Xu et al., 2016] Chang Xu, Da-Cheng Tao, and Chao Xu. Robust extreme multi-label learning. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowl- edge Discovery and Data Mining, pages 1275-1284, San Francisco, CA, 2016.
24. [Yen et al., 2016] Ian E.-H. Yen, Xiangru Huang, Kai Zhong, Pradeep Ravikumar, and Inderjit S. Dhillon. Pd-sparse: A primal and dual sparse approach to extreme multiclass and multilabel classification. In Proceedings of the 33rd Interna- tional Conference on Machine Learning, pages 3069-3077, New York City, NY, 2016.
25. [Zhang and Wu, 2015] Min-Ling Zhang and Lei Wu. Lift: Multi-label learning with label-specific features. IEEE Transactions on Pattern Analysis and Machine Intelligence, 37(1):107-120, 2015.
26. [Zhang and Zhou, 2014] Min-Ling Zhang and Zhi-Hua Zhou. A review on multi-label learning algorithms. IEEE Trans- actions on Knowledge and Data Engineering, 26(8):1819- 1837, 2014.
27. [Zhang et al., 2009] Min-Ling Zhang, José M. Peña, and Vic- tor Robles. Feature selection for multi-label naive bayes classification. Information Sciences, 179(19):3218-3229, 2009.