Extreme multi-label classification (XMLC) refers to the task of tagging
instances with small subsets of relevant labels coming from an extremely large
set of all possible labels. Recently, XMLC has been widely applied to diverse
web applications such as automatic content labeling, online advertising, or
recommendation systems. In such environments, label distribution is often
highly imbalanced, consisting mostly of very rare tail labels, and relevant
labels can be missing. As a remedy to these problems, the propensity model has
been introduced and applied within several XMLC algorithms. In this work, we
focus on the problem of optimal predictions under this model for probabilistic
label trees, a popular approach for XMLC problems. We introduce an inference
procedure, based on the $A^*$-search algorithm, that efficiently finds the
optimal solution, assuming that all probabilities and propensities are known.
We demonstrate the attractiveness of this approach in a wide empirical study on
popular XMLC benchmark datasets.

本研究提出一种基于 A * 搜索算法的推断过程，能够有效地解决了在极端多标签分类模型中标签分布不均、稀疏、缺失等问题，从而优化了分类预测效果。

倾向分数概率标签树

Propensity-scored Probabilistic Label Trees

Extreme multi-label classification (XMLC) is a learning task of tagging
instances with a small subset of relevant labels chosen from an extremely large
pool of possible labels. Problems of this scale can be efficiently handled by
organizing labels as a tree, like in hierarchical softmax used for multi-class
problems. In this paper, we thoroughly investigate probabilistic label trees
(PLTs) which can be treated as a generalization of hierarchical softmax for
multi-label problems. We first introduce the PLT model and discuss training and
inference procedures and their computational costs. Next, we prove the
consistency of PLTs for a wide spectrum of performance metrics. To this end, we
upperbound their regret by a function of surrogate-loss regrets of node
classifiers. Furthermore, we consider a problem of training PLTs in a fully
online setting, without any prior knowledge of training instances, their
features, or labels. In this case, both node classifiers and the tree structure
are trained online. We prove a specific equivalence between the fully online
algorithm and an algorithm with a tree structure given in advance. Finally, we
discuss several implementations of PLTs and introduce a new one, napkinXC,
which we empirically evaluate and compare with state-of-the-art algorithms.

本研究详细研究了概率标签树 (PLTs) 作为多标记问题中的分层 softmax 的一般化方法，考虑了在线学习的问题，证明了他们的相容性，提出了一种新的 PLTs 实现，并通过实验证明了它的有效性。

极端多标记分类的概率标记树

Probabilistic Label Trees for Extreme Multi-label Classification

Retrieving relevant targets from an extremely large target set under
computational limits is a common challenge for information retrieval and
recommendation systems. Tree models, which formulate targets as leaves of a
tree with trainable node-wise scorers, have attracted a lot of interests in
tackling this challenge due to their logarithmic computational complexity in
both training and testing. Tree-based deep models (TDMs) and probabilistic
label trees (PLTs) are two representative kinds of them. Though achieving many
practical successes, existing tree models suffer from the training-testing
discrepancy, where the retrieval performance deterioration caused by beam
search in testing is not considered in training. This leads to an intrinsic gap
between the most relevant targets and those retrieved by beam search with even
the optimally trained node-wise scorers. We take a first step towards
understanding and analyzing this problem theoretically, and develop the concept
of Bayes optimality under beam search and calibration under beam search as
general analyzing tools for this purpose. Moreover, to eliminate the
discrepancy, we propose a novel algorithm for learning optimal tree models
under beam search. Experiments on both synthetic and real data verify the
rationality of our theoretical analysis and demonstrate the superiority of our
algorithm compared to state-of-the-art methods.

通过发展 Bayes 最优方法和校准方法来理解和分析现有树模型中存在的训练 - 测试差异问题，并提出了一种新的算法来解决此问题，实验结果证明了该算法相较于现有方法具有更高的性能水平。

应用 Beam Search 学习最佳树模型

Learning Optimal Tree Models Under Beam Search

Extreme multi-label classification (XMLC) is a problem of tagging an instance
with a small subset of relevant labels chosen from an extremely large pool of
possible labels. Large label spaces can be efficiently handled by organizing
labels as a tree, like in the hierarchical softmax (HSM) approach commonly used
for multi-class problems. In this paper, we investigate probabilistic label
trees (PLTs) that have been recently devised for tackling XMLC problems. We
show that PLTs are a no-regret multi-label generalization of HSM when
precision@k is used as a model evaluation metric. Critically, we prove that
pick-one-label heuristic - a reduction technique from multi-label to
multi-class that is routinely used along with HSM - is not consistent in
general. We also show that our implementation of PLTs, referred to as
extremeText (XT), obtains significantly better results than HSM with the
pick-one-label heuristic and XML-CNN, a deep network specifically designed for
XMLC problems. Moreover, XT is competitive to many state-of-the-art approaches
in terms of statistical performance, model size and prediction time which makes
it amenable to deploy in an online system.

本文中，我们探究了处理极端多标记分类问题的概率标记树（PLTs），并通过实现 extremeText（XT）来证明 PLTs 在 precision@k 指标下是一个 HSM 的无遗憾多标签泛化。同时，我们证明了 pick-one-label 启发式算法在一般情况下不是一致的，我们的实现方法比使用 pick-one-label 的 HSM 和专门为 XMLC 问题设计的神经网络 XML-CNN 得到的结果更好。此外，XT 在统计性能、模型大小和预测时间等方面与许多最先进的方法相当，适合部署在在线系统中。