Does Tail Label Help for Large-Scale Multi-Label Learning

1 Introduction

Large-scale multi-label learning [Zhang and Zhou, 2014; Hsu et al., 2009] annotates data object with the relevant labels from an extremely large number of candidate labels, which recently owns many real applications. For example, in webpage categorization, millions of labels (categories) are collected in Wikipedia and one needs to annotate a new webpage with relevant labels from such a big candidate set; in image annotation, millions of people tags are in the repository and one wishes to tag each individual picture from such a big candidate tags; in recommendation system, millions of items are presented and one hopes to make informative personalized recommendation from the big candidate items.

An important statistical characteristic of large-scale multilabel learning is that labels follow a power law distribution (as illustrated in Figure 1). There are more than 70% labels which occur in at most 15 examples on each dataset. The infrequently occurring labels are referred as tail labels and the frequently occurring ones are referred as common labels.

∗Yu-Feng Li is the corresponding author.

How do tail labels impact the performance? It turns out that this intrinsic issue is persistently neglected in most large-scale multi-label learning studies, though tail label has recently attracted increasing attention [Babbar and Sch¨olkopf, 2018]. Most approaches usually believe that the final performance would benefit from leveraging tail labels [Bhatia et al., 2015; Xu et al., 2016; Jain et al., 2016].

To answer this question, in this paper we compute the impact of tail labels on popular performance metrics through analyzing the missing labels and the misclassified labels. Our analyses consistently show that tail labels impact much less than common labels in terms of commonly used performance metrics (Top-k precision and nDCG@k). This implies that simply optimizing the Top-k precision and nDCG@k metrics in large-scale multi-label learning does not need to take tail labels into account. We conduct a simple empirical study by trimming off 50% labels with fewest positive examples. As illustrated in Figure 2, both the prediction time and the model size are reduced without sacrificing much performance.

Based on the observations mentioned above, we develop a low-complexity large-scale multi-label learning algorithm with the goal of facilitating fast prediction and compact models through trimming tail labels adaptively. We simulate the training procedure and correlate the reduction in terms of predictive performance, prediction time and model size with the fraction of trimmed tail labels by polynomial functions of label set size. Through modelling such correlations, the objective function is optimized based on golden section search and parabolic interpolation [Forsythe et al., 1977; Brent, 2013]. Experiments verify the effectiveness of trimming tail labels in terms of prediction time and model size reduction, and promising predictive performance. In addition, the strategy mentioned above is a wrap of model and hence can be applicable to many large-scale multi-label models.

In the rest of the paper, we first briefly introduce related works. Then, we study the usefulness of tail labels in largescale multi-label learning, and propose to trim off tail label adaptively to facilitate fast prediction and compact models. Experimental results on a number of data sets are conducted to verify our idea, followed by discussion and conclusion.

2 RelatedWork

In previous large-scale multi-label learning, prediction time and model size are two crucial issues because fast prediction and compact models are desired for large label set, especially for real-time applications in portable devices.

Many approaches exploit structural assumptions to reduce prediction time. For example, embedding-based methods have been proposed to project label vectors onto a low dimensional space based on the assumption that label matrix is low-rank [Hsu et al., 2009; Zhang and Schneider, 2011; Chen and Lin, 2012; Tai and Lin, 2012; Cisse et al., 2013; Bi and Kwok, 2013; Lin et al., 2014; Yeh et al., 2017]. Another recent thread of research is tree-based methods that recursively divide the space of labels or features to achieve fast prediction speed [Prabhu and Varma, 2014; Choromanska and Langford, 2015; Daume III et al., 2016].

Several methods are proposed recently to yield sparse solutions explicitly or prune spurious weights to achieve sparse models. Yen et al. [2016] maximized the margin loss with ℓ1 penalty and yielded extremely sparse solution without sacrificing the expressive power of predictor. Babbar and Sch¨olkopf [2017] proposed an framework which controls the model size by filtering out the billions of stored spurious parameters by ad-hoc usage of the off-the-shelf solvers. By weeding out ambiguous parameters, one can obtain model sizes which are three orders of magnitude smaller.

Recently, there are some discussions on the power law distribution in multi-label learning. Bhatia et al. [2015] represented tail labels by learning a embedding, which captures non-linear label correlations by preserving the pairwise distances between label vectors. For prediction, a k-nearest neighbor classifier is used in the embedding space, leveraging the preserved nearest neighbors in the training phrase. Jain 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 datapoor tail classes. Li et al. [2017] handled the long-tail recommendation problem. They decomposed the recommendations into two part, a low-rank part to address short-head items and a sparse part to handle long-tail items. Due to the scarcity of positive training instances for tail labels, Babbar and Sch¨olkopf [2018] viewed this phenomenon as a setup in which an adversary is generating test examples such that the features of the test set instances is quite different from those in the training set. Most of these studies, believe that the final performance would benefit from leveraging tail labels.

3 Usefulness of Tail Labels in Large-Scale Multi-Label Learning

In this section, focusing on large-scale multi-label learning, we study the usefulness of tail labels for the final performance. We first briefly introduce the setup of large-scale multi-label learning and its commonly used evaluation metrics. Then, we compute the impact of tail labels on popular performance metrics through analyzing the missing and the misclassification of labels, respectively.

3.1 Preliminaries

Let D = {(x1, y1) . . . (xN, yN)} be the given training set, where xi ∈ Rd is the input feature of the i-th example and yi ∈ {0, 1}L is the corresponding label vector. Yij = 1 if example xi is relevant with the j-th label, and 0 otherwise. Large-scale multi-label learning aims to learn a classifier f : Rd → {0, 1}L that predicts the label vector for unseen data. Unlike traditional multi-label learning, the label set size is very large and the labels usually follows a long tail distribution. Detail notations are summarized in Table 1.

3.2 Commonly Used Performance Metrics

Top-k precision

Top-k precision is a commonly used ranking based performance measure in large-scale multi-label learning and has been widely adopted for ranking tasks [Prabhu and Varma, 2014; Bhatia et al., 2015]. In Top-k precision, only a few top predictions of an instance will be considered. For each instance x, the Top-k precision is defined for a predicted score vector ˆy ∈ RL and ground truth label vector y ∈ {-1, 1}L as

where rankk(ˆy) returns the indices of k largest value in ˆy ranked in descending order.

nDCG@k

nDCG@k is another commonly used ranking based performance measure and is defined as

where DCG@k := ∑l∈rankk(ˆy) yl log(l+1) and ||y||0 returns the 0-norm of the true-label vector.

3.3 For Labels are RandomlyMissing

Due to the large number of labels, human annotators may not be able to go through every label and make out all the relevant labels. We first consider the impact of tail labels under the scenario that relevant labels go missing randomly with probability ϵ [Lim et al., 2015], and compute the expectation of performance for discussion.

Proposition 1. Under the assumption that relevant labels are randomly missing with probability ϵ, common labels have more impact than tail labels in terms of P@k and nDCG@k.

Proof. (a) P@k: In this analysis, for simplicity we suppose that each instance associates with a constant c number of labels in the ground-truth label vector, that is, v = (1 - ϵ)c relevant labels are observed for each instance. As only k out of v relevant labels are considered in the calculation of P@k, we choose a random subset of size k from v relevant labels which has (vk) distinct ways for each instance and compute the expected number of times for the j-th label is chosen as

As we can see, the value of Eq. (3) increases as uj becomes larger. Since Eq. (3) only depends on uj for the j-th label, we can compute the contribution of each label separately. By considering the contribution to P@k of tail labels (referred as TP@k) and common labels (referred as CP@k) respectively, we have TP@k = b ∑Lt j=1 uj and CP@k = b ∑Lj=Lt+1 uj, where b = (1-ϵ) kv and labels are sorted according to their occurrences in ascending order beforehand with tail labels at the front.

Then, we get

In practical cases, tail labels only occur with a handful of examples while there can be as many as hundreds or even thousands of examples having common labels (as shown in Figure 1). Therefore, CP@k is significantly larger than TP@k, which evidently discloses that common labels impact much more importantly than tail labels in terms of Top-k precision.

• (b) nDCG@k: Note that every observed label has the same rank, hence ∑kl=1 1 log(l+1) is a constant. The analysis for nDCG@k is reduced to the one in P@k, and we get the same conclusive remark in terms of nDCG@k, i.e., common labels impact much more importantly than tail labels.

3.4 For Labels are RandomlyMisclassified

It's a common practice to consider the probability of misclassification [Schapire, 1990; Bartlett, 1998]. We further consider the impact of tail labels under the scenario that labels are randomly misclassified with probability ϵ, and similar to Section 3.3, we compute the expectation of performance for discussion.

Proposition 2. Under the assumption that labels are randomly misclassified with probability ϵ, common labels have more impact on P@k and nDCG@k than tail labels.

Proof. (a) P@k: Similar to the proof of the previous proposition, we suppose that each instance associates with a constant c number of labels in the ground-truth label vector. Hence, there will be v = (1 - ϵ)c + ϵ(L - c) relevant labels in the predicted label vector. By choosing a random subset of size k from v relevant labels, the expected number of times the j-th label is chosen can be computed as

Since Eq. (5) only depends on uj for the j-th label, we can compute the contribution of each label separately. By considering contribution of tail labels and common labels respectively, we have TP@k = b ∑Lt j=1 uj + ϵNLt kv and CP@k = b ∑Lj=Lt+1 uj + ϵN(L - Lt) kv , where b = (1 - 2ϵ) kv . Therefore, we have

As tail labels only occur in a handful of examples and common labels can associate with as many as hundreds or even thousands of examples in practical cases, similarly, disclosing that common labels impact much more importantly than tail labels in terms of Top-k precision.

• (b) nDCG@k: Similar with the reason in the proposition 1, The analysis for nDCG@k is reduced to the one in P@k, and we obtain a same conclusive remark in terms of nDCG@k.

With the analysis above, in both label-missing and labelmisclassified scenarios, we conclude that common labels have a significant larger impact compared with that of tail labels in terms of P@k and nDCG@k. This analysis motivates us to trim off tail labels, which may have little impact on popular performance metrics.

4 Adaptively Trimming off Tail Labels

A straightforward way to trim off tail labels is to remove a constant proportion of labels. However, due to variety of data, it may result in performance deterioration in case too many tail labels are pruned. Therefore, a crucial issue is to adaptively select a cut-off threshold for tail labels, taking the predictive performance, prediction time and model size into account simultaneously.

In this section, we present the proposed Adaptively Trimming off Tail Labels (ADATTL) method which selects a threshold λ adaptively on a variety of data where λ represents a fraction of tail labels to be trimmed, to trade off the predictive performance, prediction time and model size. Since it is hard to foresee the influence of different value of λ, we consider to build a regressor using different label set size and different training set size, to predict the potential reduction of predictive performance, prediction time and model size, respectively, and thus determine an appropriate threshold.

Our approach is data-driven and achieved by sampling technique. We start collecting data for regressors by trimming off a random fraction λτ of tail labels resulting in the remaining label set Lτ and sampling a subset of training examples Dτ uniformly at random. Then, we train an large-scale multi-label classifier fτ on (Dτ ,Lτ ) and compute P@k, nDCG@k, prediction time and model size. This process is repeated multiple times. We fit the obtained set of triplets {(|Dτj|, λτj, perfj )}Tj=1 , {(|Dτj|, λτj, timej)}Tj=1 and {(|Dτj|, λτj, sizej)}Tj=1 with polynomial functions, where T is sample size, perf is the testing performance vector, time is the prediction time vector and size is the model size vector calculated during the simulation. From this, regression functions can predict the potential reduction in testing performance, prediction time and model size given the training set size and λ. After building the regressors, we formalize ADATTL as

where α, β are trade-off parameters, Ntr is the training set size and functions f, g, h are regressors for testing performance, prediction time and model size, respectively. To maximize Eq. (7), functions g and h are desired to be as small as possible which indicates a large reduction in prediction time and model size respectively, whereas function f is preferred to be as large as possible which means losing less testing performance. We obtain the final threshold λ by optimizing L based on golden section search and parabolic interpolation [Forsythe et al., 1977; Brent, 2013]. The steps discussed above are summarized in Algorithm 1.

Algorithm 1 ADATTL

Input: feature vectors X ∈ RN×d ; label vectors Y ∈ RN×L; hyper-parameters α, β and sample size T Output: the fraction λ of tail labels

• 1: for t = 1, 2, · · · , T do
• 2: trim a randomly selected fraction λτt of tail labels resulting in the remaining label set Lτt
• 3: sample a subset of training examples Dτt randomly
• 4: train large-scale multi-label model ft on (Dτt, Lτt)
• 5: compute perft , timet and sizet
• 6: end for
• 7: fit {(|Dτj|, λτj, perfj )}Tj=1 , {(|Dτj|, λτj, timej)}Tj=1 and {(|Dτ j |, λτ j , sizej )}Tj=1 with polynomial surfaces
• 8: optimize Eq. (7) and obtain λ
• 9: return λ

5 Experiments

We conduct experiments with a leading embedding-based method LEML [Yu et al., 2014] and a state-of-the-art treebased method FastXML [Prabhu and Varma, 2014] to validate our theoretical findings and effectiveness of ADATTL. Experiments are carried out on multi-label datasets including Bibtex (159 labels), Delicious (983 labels), EUR-Lex (3993 labels) and Wiki10 (30K labels). All the datasets and implementation of LEML and FastXML are publicly available and can be downloaded from the Extreme Classification Repository 1 . To demonstrate that ADATTL selects threshold properly, we trim tail labels with varying fractions ranging from [10%, 20%, . . . , 90%] for comparison. As the fraction of trimmed tail labels increases at each time, we decrease the number of trees trained in FastXML by two. We use quartic polynomial functions to model functions f, g and h. When modelling function f , we use the sum of P@k and nDCG@k, k = {1, 2, 3}, as the whole testing performance. Default value of parameters for LEML and FastXML are used and hyper-parameters α and β in Eq. (7) are set to 1.

5.1 For Embedding-BasedMethods

We compare the performance of ADATTL with LEML. The classification performance in terms of P@k and nDCG@k is presented in Figure 3, while Table 2 presents the results of prediction time and model size. It can be seen that ADATTL selects threshold properly which do not result in performance deterioration, while stably performs better than LEML on all datasets in terms of prediction time and model size. For example, ADATTL improves over LEML by as much as 92.1% and 20% in terms of prediction time and model size on Wiki10 dataset. This is because that the success of LEML mainly depends on the low-rank assumption, which tends to be violated due to the presence of tail labels. Therefore, tail labels make very limited contribution to the performance of LEML. ADATTL provides an appropriate approach to preserve the validity of low-rank assumption by elegantly trimming off the tail labels. Hence, ADATTL is able to achieve comparable results.

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

5.2 For Tree-BasedMethods

We next conduct experiments with FastXML, which is a leading tree-based method. Figure 4 and Table 3 show the comparison results and we have the following observations. Compared with FastXML, ADATTL achieves highly competitive performance in terms of P@k and nDCG@k, meanwhile saves considerable prediction time and model size in all cases. The reason lies in the fact that, the number of split partitions and the depth of trees during the training process are both reduced as the number of labels decreases, therefore the size of tree model and the prediction time spent on leaf nodes are cut down consequently.

From the experimental results, we conclude that the proposed strategy selects threshold adaptively and yield fast prediction speed as well as compact models. Moreover, the effectiveness is valid for both embedding-based and tree-based approaches, which validates the applicability of our strategy.

6 Discussion

Our analysis and empirical studies suggest that, in order to evaluate the performance of large-scale multi-label methods on tail labels, the choice of performance metric is critical due to the power-law distribution. Jain et al. [2016] claimed that existing performance metrics, such as the Hamming loss, are unsuitable for performance evaluation. They developed propensity scored variants of top-k precision, nDCG@k and

other popular performance metrics which treat tail labels as

65

Table 2: Prediction Time (s) and Model Size (MB) with comparison embedding-based method LEML.

65

Table 3: Prediction Time (s) and Model Size (MB) with comparison tree-based method FastXML.

being more important than common ones. Nonetheless, the weights for labels were set in an ad hoc fashion and unavailable for general cases. To make tail labels have great merit, more preferable performance metrics need to be designed.

7 Conclusion

In this paper, we propose to study how tail labels make impact on the commonly used performance metrics in largescale multi-label learning. Through examining the missing labels and the misclassified labels, our analysis discloses that tail labels consistently impact much less than common labels on popular performance metrics. We then develop a low-complexity large-scale multi-label algorithm to facilitate fast prediction and compact models by trimming tail labels adaptively. Experiments verify the effectiveness of trimming tail labels in terms of prediction time and model size reduction, and promising predictive performance. The contribution of this work is that we provide a different aspect for largescale multi-label learning, revealing that significant attention should be paid to the design of performance metrics, to fully exploit the great merit of tail labels.

Acknowledgments

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