{'fraction_non_alphanumeric': 0.038933277263807124, 'fraction_numerical': 0.012125035043453882, 'mean_word_length': 4.960108604845447, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Uncertainty in Extreme Multi-label Classification

Uncertainty quantification is one of the most crucial tasks to obtain trustworthy and reliable machine learning models for decision making. However, most research in this domain has only focused on problems with small label spaces and ignored eXtreme Multi-label Classification (XMC), which is an essential task in the era of big data for web-scale machine learning applications. Moreover, enormous label spaces could also lead to noisy retrieval results and intractable computational challenges for uncertainty quantification. In this paper, we aim to investigate general uncertainty quantification approaches for tree-based XMC models with a probabilistic ensemble-based framework. In particular, we analyze label-level and instance-level uncertainty in XMC, and propose a general approximation framework based on beam search to efficiently estimate the uncertainty with a theoretical guarantee under long-tail XMC predictions. Empirical studies on six large-scale real-world datasets show that our framework not only outperforms single models in predictive performance, but also can serve as strong uncertainty-based baselines for label misclassification and out-of-distribution detection, with significant speedup. Besides, our framework can further yield better state-of-the-art results based on deep XMC models with uncertainty quantification.


Introduction
Extreme multi-label classification (XMC), or extreme multi-label learning, aims to find the relevant labels for a data input from an enormous label space. With increasingly growing information in the era of big data, XMC has become more and more important, and has been widely applied to various real-world applications, such as advertising [37], product search [9], and document retrieval [6]. However, for domains with potential high risks from mistakes like public health and medicine, it is crucial to model the predictive uncertainty for their downstream XMC applications like food classification [54] and medical diagnosis [2]. In particular, an input sometimes could have only few or even no matches in the label space, so the outputs could be noisy without uncertainty quantification. It is also insufficient to only model uncertainty for the entire input since XMC models could have different confidence for each label among the whole enormous space.
To estimate predictive uncertainty, Bayesian and probabilistic models [20] are inherently applicable because variance can intrinsically be viewed as an uncertainty measurement. However, although Bayesian approaches are mathematically grounded to model uncertainty, their computational costs are usually exorbitant for large-scale data. To address this issue, the most popular solution is to approximate Bayesian inference by sampling models as an ensemble [17]. Accordingly, ensemble-based Bayesian approximation has been applied to analyze the uncertainty in neural networks [13,18], gradient boosting based on decision trees [36], autoregressive structured prediction [34], and random forests [41]. Unfortunately, none of the existing studies has studied uncertainty quantification for XMC models.
Uncertainty quantification for XMC models is challenging. First, different from conventional classification models, XMC models usually focus on deriving a small subset of relevant labels from the enormous label space. In other words, for XMC models, we not only should consider how confident a model is for the entire input, but also need to model the uncertainty for each individual label. However, most of the existing uncertainty quantification studies only concentrate on instance-level uncertainty [1]. The enormous number of labels could also result in computational difficulty. Second, XMC models usually take extremely sparse input features [9,50] with distillation [51]. Moreover, many XMC models [37,51] conduct convex optimization for better computational efficiency, which are insensitive to initialization [39]. As a result, existing uncertainty quantification approaches that manipulate model weights, such as MC Dropout [18] and Deep Ensemble [27], could be ineffective.
To address these issues, in this work, we investigate ensemble-based uncertainty quantification for XMC models. We first present the concept of modeling label-level and instance-level uncertainty. To tackle the efficiency issue due to enormous labels, we propose a general framework to approximate uncertainty measurements by beam search with a theoretical guarantee under long-tail probability distributions. Our contributions can be summarized as: • We are the pioneer of uncertainty quantification for XMC models. Especially, we broaden the scope by simultaneously modeling label-level and instance-level uncertainty, which is an essence of XMC tasks. • We propose an efficient and general framework to approximate uncertainty in XMC. With the observation of long-tail distributions in predictions, beam search on tree-based XMC models can further mitigate the computational efficiency with mathematical guarantees on estimated uncertainty. • We conduct experiments on six benchmark XMC datasets. Our approaches can not only obtain satisfactory predictive performance, but also appropriately estimate both label-level and instance-level uncertainty. Besides, using XR-TRANSFORMER as deep base models, our framework can obtain better state-of-the-art results.

Ensemble-based Uncertainty Quantification
In this work, we focus on ensemble-based uncertainty quantification using Bayesian ensembles [17], which learns the ensemble of multiple individual models. The model parameters θ are considered as random variables from a posterior distribution p(θ | D), which can be computed by the Bayes' rule as: Wiki10-31K Figure 1: The mean and standard deviation of predicted probabilities over different rank positions on the testing data of Eurlex-4K and Wiki10-31K datasets.
such as active learning [25] and out-of-distribution detection [10]. To compute the knowledge uncertainty, we can decompose the total uncertainty by deriving the mutual information between the model parameters θ and the prediction y [13] as: is the mean predicted probability of all individual models in the ensemble. In this work, we examine three quantification approaches in our experiments, including total uncertainty (TU), knowledge uncertainty (KU), and probability variance (PV).

eXtreme Multi-label Classification (XMC)
Given a training dataet D of N instances, for an arbitrary testing instance x, an XMC model aims to estimate a probability Pr(y | x, D) for each label l ∈ L in an extreme label space L with L labels.
Training with Negative Example Selection. With the extreme label space, it is time-consuming for models to be trained with all negative examples. As a result, most of the state-of-the-art XMC models select appropriate negative examples during optimization. For example, Parabel [37] and PECOS [51] consider teacher forcing negatives [28] and matcher-aware negatives for better performance. For simplicity, we denote the adjusted training dataset with negative example selection as D so that the targets of those XMC models become Pr(y | x, D ) ≈ Pr(y | x, D).
Hierarchical Label Tree and Semantic Indexing. Due to the enormous labels, it can be inappropriate to have linear inference time complexity to the number of labels. To achieve acceptable efficiency, one of the most prominent methods is to partition the enormous label space into a hierarchical label tree [24,37,51]. Specifically, top-down B-ary clustering can recursively construct a depth-d hierarchical label tree with label representations like instance feature aggregation and additional label features. The cluster numbers K t are B t and L for the first d − 1 layers and the last d-th layer. The clustering assignment at each layer t can then be represented by an indexing matrix C (t) ∈ {0, 1} Kt×Kt−1 as : k is the corresponding cluster at the layer t − 1 for a cluster (or a label when t = d) at the layer t in the hierarchical label tree.
With the hierarchical label tree and the indexing matrix C (t) , tree-based XMC models can conduct semantic indexing with beam search [26] for efficient approximated inference in a sub-linear time. More precisely, for every clustering layer t − 1, tree-based models estimate Pr(y t | x, D (t) ) and encode top-b clusters into Y (t−1) ∈ {0, 1} Kt−1 , where D (t) is the induced training dataset for clusters at the layer t; Models can then focus on limited clusters or labels indicated by Y (t−1) C t ∈ {0, 1} Kt for inference at the clustering layer t. Finally, Pr(y | x, D ) can then be computed as: ) can be further recursively derived through clustering layers. In this paper, we denote a tree-based XMC model learn a parameter set θ from the dataset to recursively compute the predictions as: Challenges in XMC Uncertainty Quantification. Although the uncertainty measures introduced in Section 2.1 are tractable in most scenarios, a linear computational time over all enormous labels could still be unacceptable. Besides, uncertainty for XMC models can be examined in two levels, including (1) label-level for the predicted probability Pr(y | x, D) of each single label l, and (2) instance-level for the entire instance x. However, none of the existing studies has addressed any of these two uncertainty types for XMC models.

XMC Uncertainty Quantification
In this section, we propose an efficient framework to approximate both label-level and instance-level uncertainty. We also suggest two approaches to generate model ensembles.

Uncertainty in XMC
Here we propose to model two different levels of uncertainty, including label-level and instance-level uncertainty. The former represents the confidence of the decision on each individual label, and the latter estimates how certain the model is for a given data instance.
Label-level Uncertainty. Label-level uncertainty quantification can be reduced to L subtasks of estimating uncertainty of binary classification for each label ∈ L. Specifically, given a model ensemble, we collect M predicted probabilities {Pr(y | x; θ (m) } M m=1 for each label , thereby estimating the uncertainty based on different approaches introduced in Equations (1), (2), and (3) in Section 2.1.
Instance-level Uncertainty. To estimate instance-level uncertainty, it is required to simultaneously consider the predictions over all labels ∈ L for an instance x. As a pioneer of this direction in XMC, we borrow the idea of JointEnergy [29,46] in the domain of conventional multi-label classification by adding up uncertainty metrics over all labels. Specifically, from the joint likelihood perspective, instance-level Total Uncertainty, which estimates the entropy for each label, can be decomposed into an explainable form under the assumption of conditional independence for p(y | x) as: is the normalized density for each label ∈ L.

Uncertainty Approximation via Beam Search
Even though we now have tractable approaches to estimate both label-level uncertainty and instance-level uncertainty, their linear computational time could still be too slow to address XMC tasks that usually have millions of labels. In this work, we propose to leverage the power of long-tail probabilistic distributions and variances in XMC problems.

Algorithm 1 Uncertainty Approximation via Beam Search
Input: a model ensemble {Pr(y | x; θ (m) )} M m=1 ; indexing matrices {C (t) } 1≤t≤d ; the testing instance x. Output: Approximated Uncertainty MetricsÛ . Hyper-parameters: the beam width b; the number of top-ranked labels k.
) end for end for ComputeÛ as approximated uncertainty with labelProb. returnÛ Figure 1 illustrates the statistics of predicted probabilities over different rank positions on the testing data of the Eurlex-4K and Wiki10-31K datasets. Both mean and standard deviation of predicted probabilities are long-tail over rank positions while most of the labels in the space are predicted with near-zero probabilities and variance. In other words, the label-level uncertainty of those labels and the corresponding components in the computations of instancelevel uncertainty would be also close to zero. Indeed, instances in XMC tasks tend to have very few labels, so the phenomenon is also intuitive. Based on this observation, we propose to approximate uncertainty based on beam search and retrieving top-ranked but limited labels.
As mentioned in Section 2.2, beam search [26] is a convenient tool to efficiently derive the top-ranked labels. We also notice that the long-tail phenomenon on intermediate probabilities is also consistent through all layers in the search. Hence, for uncertainty approximation, we propose to only consider the predicted probabilities of top-ranked labels returned by beam search and assign zero probabilities for the remaining labels. The computational time of uncertainty can then be improved from linear to sub-linear in the number of labels. In Algorithm 1, we present the pseudo code of the detail process for uncertainty approximation via beam search for a testing instance x.
Theoretical Analysis. In addition to the efficiency, the long-tail property also provides the theoretical guarantee on the accuracy of beam search results. Theorem 3.1. Suppose Pr(y t | x; θ) given by a tree-based model for each layer t is under a long tail distribution as shown in Figure 1. With a large enough beam size k t , the average regret of beam search in each layer t would satisfy the following inequality: where δ ≈ 0 is a small positive constant; o i and i are the oracle and predicted top-i label.
The proof of Theorem 3.1 is presented in Appendix A. The effectiveness of approximated total uncertainty can be also shown in Theorem 3.2 Theorem 3.2. SupposeÛ (x, ) is the approximated total uncertainty given by Algorithm 1 to estimate label-level total uncertainty for an instance x and each label ; Pr(y | x, θ (m) ) is under a long-tail distribution as shown in Figure 1.
With a large enough hyper-parameter k in beam search, for each individual model, the approximated uncertaintyÛ (x) andÛ (x, ) would satisfy the following inequality: Note that we show the proof of Theorem 3.2 in Appendix B. Other uncertainty metrics like knowledge uncertainty and probability variance can also reach similar properties.
Time Complexity Analysis. Suppose d is the depth of tree-based models in the ensemble; matrix multiplication is implemented with sparse matrices; with B-ary clustering, the cluster number K t is min(B t , L), where B is a small constant; T θ is the time to compute Pr(y | x; θ). For simplicity, we let k = b; T θ (m) = T θ for all individual models.
, the overall time complexity would be O(M vbT θ log L). Compared to the complexity of naïve approach to compute the predictions over all labels for each model O(M × L × T θ ), our algorithm significantly reduces the computational time from linear to sub-linear to the extremely large size of the label spaces L.

Generating XMC Model Enembles
Our framework is general for arbitrary methods of generating model ensembles. In this work, as examples, we adopt two ensemble generation approaches from data and model perspectives without manipulating model weights, including bagging and boosting.
From the data aspect, bootstrap aggregating (bagging) is one of the most popular ensemble meta-algorithms to enhance the stability of machine learning models [7]. In other words, individual models in the bagging ensemble can be representative of the diversity of model predictions so that the ensemble model can reduce variance [15,19]. In addition to deriving ensemble models from the data perspective, the model perspective could be also important, so boosting models [40] can also appropriately generate model ensembles. Specifically, we iteratively boost XMC models by leveraging earlier models to derive hard negatives as new training samples. Moreover, Bagging and Boosting can be combined as Boosted Bagging by deriving boosting models based on bootstrapped data and corresponding hard negatives.

Experimental Settings
Datasets. In this paper, we adopt six public benchmark extreme multi-label text classification datasets [50], including Eurlex-4k, Wiki10-31K, Amazon-670K, AmazonCat-13K, Wiki-500K, and Amazon-3M, as shown in Table 1. We use the sparse tfidf representations as features and training/testing data splits, which are consistent with existing studies in this field [8,23,50,53]. Base XMC Models. We first consider XR-LINEAR in PECOS [51] with sparse tfidf representations as our base model since XR-LINEAR is one of the most popular tree-based XMC models with high flexibility and scalability to enormous output spaces and applied to various domains like extreme text classification [33] and product search [9]. We then adopt XR-TRANSFORMER [53], one of the state-of-the-art text XMC models, to show the potential of our framework to be applied in deep XMC models.
Evaluation Tasks and Metrics. We consider three evaluation tasks: (1) predictive performance, (2) misclassification detection, and (3) out-of-distribution (OOD) deteciton. Task 1 evaluates prediction accuracy with precision and recall metrics on top-ranked labels. Task 2 assesses label-level uncertainty by detecting incorrectly ranked labels with uncertainty scores. Task 3 appraises instance-level uncertainty by identifying testing instances out of training distributions with uncertainty scores. Tasks 2 and 3 utilize area under the ROC curve (AUROC) [21] as the evaluation metric.
Baselines. We mainly compare with single models. For Tasks 2 and 3, we adopt Energy [32] and JointEnergy [46], the state-of-the-art OOD detection methods for conventional multi-class and multi-label classification, to derive baseline  . After training, model weights smaller than 1e − 3 are ignored for reducing disk space consumption, following the settings of XR-LINEAR [51]. For inference, the beam size b and the number of top-ranked labels k in beam search are set as 50 and 100. For the Bagging ensemble approach, we bootstrap datasets with the identical size to the training dataset for training individual models. For the Boosting ensemble approach, we set the hyper-parameter α = 0.5. For all ensemble-based approaches in the experiments (i.e., all methods except the single model), the number of model ensembles M is 10 for ensemble generation. All deep learning models using transformers use the bert-base-uncased model as the pretrained model [14]. Table 2 shows the predictive performance on six experimental datasets. Compared to the single model, MC Dropout does not improve the predictive accuracy. This could be because of sparse feature representations in XMC so that dropping model weights is less likely to affect inference. In contrast, our ensemble approaches outperform using only a single model in most of the metrics since we consider the uncertainty from both data and model perspectives. For example, Boosted Bagging outperforms both Single Model and MC Dropout by 1.5% and 4.8% in P@1 and R@1 for the Amazon-3M dataset. An interesting observation is: although Boosted Bagging performs better for smaller datasets, Boosting becomes the best while it comes to larger datasets, such as Wiki-500K and Amazon-3M. The reason could be fewer instances, i.e., less knowledge, in training data for each individual model, so those weak models could be incapable of constructing a strong ensemble.

Task 2: Misclassification Detection
The task of misclassification detection aims to evaluate the quality of estimated label-level uncertainty. Table 3 demonstrates the performance of all methods in average AUROC over six experimental datasets. All ensemble-based models outperform Energy using single model using only entropy as the uncertainty indicator, showing the importance of sampling different model parameters in the manner of Bayesian ensembles [17,34,36]. Our ensemble approaches still outperform all baseline methods over all datasets in misclassification detection. For instance, PV using Boosted Bagging outperforms Energy and MC Dropout by 2.5% and 3.4%. The observation on performance among our ensemble approaches over different dataset sizes as described in the task of predictive performance still holds here. We also notice that PV performs better than TU and KU for smaller datasets while TU and KU work better for larger ones. It can be because the predicted probabilities could be more accurate and less likely to require calibration with more training data.

Task 3: Out-of-Distribution (OOD) Detection
In the task of OOD detection, we evaluate the quality of estimated instance-level uncertainty.  detection, ensemble-based methods outperform JointEnergy using single models in most cases. Another similar observation is: with the smaller training dataset like Wiki10-31K and smaller model sizes, MC Dropout and Bagging perform better. On the other hand, Boosting and Boosted Bagging are the best methods when it comes to using Amazon-670K as the training dataset. Moreover, general performance on distinguishing AmazonCat-13K and Amazon-3M from Amazon-670K is lower because of similar dataset distributions. However, our proposed methods can still outperform baseline methods. We further found that variance-based quantification methods (i.e., MC Dropout and PV) generally perform better than entropy-based approaches. Table 5 states the execution time with the performance of Tasks 2 and 3 for Boosted Bagging based on the naïve approach and our beam search approximation for uncertainty quantification. As a result, beam search approximation is significantly faster than the naïve approach. For example, in misclassification detection, our approximation obtains 110.39x and 30.32x speedups with only 1.7% and 3.0% drop in AUROC using PV on Wiki10-31K and Eurlex-4K datasets . In OOD detection, after training XMC models with the Wiki10-31K dataset, beam search is 61.66x and 39.78x faster than the naïve method with only 0.1% and 0.5% performance loss in AUROC using PV to identify Eurlex-4K and Amazon-670K as OOD datasets.

Performance on Deep XMC Models
To further demonstrate the potential of our proposed approach with deep learning, we adopt XR-TRANSFORMER, which is the state-of-the-art XMC model based text data and transformers [14,44], as the base XMC model. Table 6 shows the predictive performance with XR-TRANSFORMER as the base XMC model on three datasets. Our ensemblebased method using Boosted Bagging outperforms the single XR-TRANSFORMER model across all metrics. For evaluating the quality of estimated uncertainty, Table 7 provides the performance on misclassification detection. All uncertainty metrics based on Boosted Bagging are better than Energy using a single model. Besides, XR-TRANSFORMER with uncertainty quantification using our approach can actually further yield better state-of-the-art results. Table 8 shows the predictive performance of various XMC models and our approach Boosted Bagging with XR-TRANSFORMER as the base XMC model, where comparative methods do not consider uncertainty quantification. As a result, after applying our ensemble-based uncertainty quantification approach to XR-TRANSFORMER, we can obtain state-of-the-art performance in most of the metrics. This further demonstrate the benefits of modeling uncertainty in the XMC task.  Table 8: Predictive performance of various XMC models and our approach using XR-TRANSFORMER as the base XMC model on Eurlex-4K and Wiki10-31K. P@k represents precision with top-k predicted labels.

Related Work
Ensemble-based Uncertainty Quantification. Uncertainty quantification aims at characterizing (and reducing) uncertainties in computational applications [45]. Instead of using a single model capturing only data uncertainty (or aleatoric uncertainty) [16,17,34], ensemble-based approaches generate ensembles of models so that the overall estimated uncertainty can be decomposed into data uncertainty and knowledge uncertainty (or epistemic uncertainty) [13]. For example, Gal and Ghahramani [18] collect model ensembles by dropping model weights of neural networks during training; Malinin et al. [36] generate ensembles of gradient boosting decision trees with intermediate individual models; Malinin and Gales [35] apply the entropy chain rule and sampling to collect an ensemble for autoregressive structured prediction; Deep Ensemble [27] derives the model ensemble by varying initial weights of neural models. These ensemble-based uncertainty quantification methods have been applied to real-world applications in various domains, such as medicine diagnosis [12,38] and computer vision [31,52]. In addition, ensemble models are also usually capable of improving predictive performance. However, although ensemble-based approaches have obtained many successes in different fields, none of the previous studies focuses on the XMC task due to the challenges introduced in Section 1.
Partition-based Extreme Multi-label Classification. Computational challenge is always the hurdle of the XMC problem. Even with sparse linear XMC models [4] comparatively more lightweight, naïve one-versus-rest (OVR) methods [49] with a linear inference time could be still too slow to be applied in real-world applications. Partition-based methods are one of the most popular approaches to addressing the efficiency and scalability of XMC models [9]. By introducing different partitioning techniques, the enormous label spaces can be reduced into hierarchical label trees so that the exhausting process on examining all labels can be replaced by efficient semantic indexing as mentioned in Section 2.2. Parabel [37] first establishes balanced 2-means label trees with instance-induced label features. Accordingly, various successors propose diverse partitioning and indexing methods for improvements, such as eXtremeText [48], Bonsai [24], and PECOS [51]. Moreover, with longer training and inference time, partition-based methods can obtain state-of-the-art accuracy by utilizing deep neural encoders, such as AttentionXML [50], LightXML [23], and XR-TRANSFORMER [53], for time-insensitive applications. In particular, XR-LINEAR in PECOS and XR-TRANSFORMER are the state-of-the-art sparse linear and deep XMC models, and treated as the base XMC models in our experiments. For simplicity, partition-based methods are called tree-based methods in this work.

Conclusions
In this paper, we are the pioneer of studying uncertainty quantification for eXtreme Multi-label Classification (XMC). We first propose to generate ensembles with the techniques of bootstrapping and boosting for estimating uncertainty from different perspectives.. Besides, we also come up with two different uncertainty levels, including label-level and instance-level uncertainty. To overcome the computational issues over the enormous label spaces, we further suggest to approximating uncertainty with beam search under long-tail probability distribution in XMC problems. In experiments, we demonstrate our proposed approaches not only obtain superior predictive performance, but also result in high-quality uncertainty estimation in both label-level and instance-level uncertainty, compared to baseline methods. Moreover, our framework can deliver better state-of-the-art XMC results after considering uncertainty quantification and using deep XMC models as base models.
Proof. Without loss of generality, we assume a pair of (o i , i ) resulting a positive regret, where o i is out of beam search results; P (y t oi | x; θ) > P (y t i | x; θ). Based on Equation (4), we have: P (y t oi | x; θ) = P (y t oi | x, c t oi ; θ) × P (c t oi | x; θ), where c t oi is the corresponding cluster in the previous layer. Since o i is out of beam search results, o i is ranked after the k t−1 -th position among P (y t−1 | x; θ). As mentioned in Section 2.2, P (c t | x; θ) represents P (y t−1 | x; θ) in the recursive manner of tree-based XMC models, so P (c t | x; θ) is also under a long-tail distribution. Hence, if the beam size k t−1 is large enough, we would have: P (c t oi | x; θ) ≤ δ , where δ ≈ 0 is a small positive constant. Moreover, the probability P (y t oi | x; θ) is also bounded as: P (y t oi | x; θ) ≤ P (y t oi | x, c t oi ; θ) × δ ≤ δ . Based on the assumption , we then have: By extending Equation (5) to all positions, we would have:
Here we start from proving the following Lemma B.1.
Based on Lemma B.1, we can prove Theorem 3.2 accordingly. Proof. |U