  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.
