PaperlayerView exact revision on arXiv

Source-linked AI summary

A no-regret generalization of hierarchical softmax to extreme multi-label classification

Marek Wydmuch, Kalina Jasinska, Mikhail Kuznetsov, Róbert Busa-Fekete, Krzysztof Dembczyński

arXiv:1810.11671v1cs.LGstat.ML

TL;DR

Extreme multi-label classification must select a small set of relevant labels from an enormous label space, where tree-based HSM is commonly used for multi-class problems. This paper analyzes PLTs as a multi-label generalization of HSM and proves the pick-one-label heuristic is not generally consistent. Its XT implementation significantly outperforms FASTTEXT, LEARNED TREE, and XML-CNN, with competitive performance and efficiency for online prediction.

  • Problem

    Extreme multi-label classification must identify a small relevant-label subset from a very large label space, while one-vs-all approaches are too costly at this scale.

    Source: §1 · p. 1

  • Method

    The paper analyzes PLTs as a multi-label generalization of HSM and implements them as XT, built upon FASTTEXT.

    Source: §1 · p. 2, §7 · p. 7

  • Results

    XT significantly outperforms FASTTEXT, LEARNED TREE, and XML-CNN, while its results are close to those of expensive one-vs-all approaches and it outperforms other tree-based methods on many benchmarks.

    Source: §9 · p. 8

  • Takeaways & Limitations

    The online XT variant often produces much smaller models that can be used for fast online prediction.

    Source: §9 · p. 9

    The formal problem setup assumes i.i.d. examples with a large label set and far fewer relevant labels per instance.

    Source: §3 · p. 3

Abstract

from arXiv · show

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.

1 Introduction

Extreme classification must handle enormous label spaces, and XMLC assigns each instance a small subset of relevant labels. The paper examines tree-based approaches, showing PLTs provide a theoretically sound multi-label generalization of HSM and that XT performs strongly in experiments.

1 Introduction

  • XMLC assigns each instance a small subset of relevant labels from a potentially enormous label space.Examples include image and video annotation, document tagging, bid-word recommendation, and next-word prediction.Source: §1 · p. 1
  • Tree-based label organization can make large output spaces more efficient, and HSM is a prominent multi-class example.FASTTEXT and LEARNED TREE adapt HSM to XMLC using the pick-one-label heuristic, which randomly selects one relevant label per training example.Source: §1 · p. 1
  • PLTs generalize HSM to multi-label classification with zero regret for marginal probability estimation and precision@k, while pick-one-label reduction is not generally consistent.The paper also shows PLTs and HSM are identical in the multi-class case.Source: §1 · p. 2
  • XT significantly outperforms FASTTEXT, LEARNED TREE, and XML-CNN, while remaining competitive with state-of-the-art approaches in model size and prediction time.The authors describe XT as particularly efficient for online prediction.Source: §1 · p. 2

2 Related work

Prior extreme-classification methods include sparsity, low-rank, tree-based, and label-filtering approaches. This section distinguishes decision trees from label trees and situates the paper's focus among these methods.

2 Related work

  • Extreme-classification approaches include sparsity, low-rank approximation, tree-based search, and label filtering, alongside independent one-vs-all models for moderate label spaces.One-vs-all scales linearly with the number of labels, which is too costly for many applications.Source: §2 · p. 2
  • Decision-tree methods split feature space at internal nodes; FASTXML uses sparse linear classifiers, reshapes random splits by optimizing NDCG, and ensembles trees.FASTXML operates in batch mode, while Choromanska and Langford introduced a fully online decision-tree algorithm with linear node classifiers.Source: §2 · p. 2
  • In label trees, each label corresponds to exactly one root-to-leaf path; examples beyond PLTs and HSM include filter trees and label embedding trees.Related hierarchical methods also appear as nested dichotomies, conditional probability estimation trees, multi-stage classifiers, and probabilistic classifier chains.Source: §2 · p. 2
  • Label-tree structure learning remains open: FASTTEXT uses a frequency-based Huffman tree, while LEARNED TREE semi-online reassigns labels through hierarchical clustering.Prabhu et al. build a tree in batch mode using recursively balanced k-means over label profiles.Source: §2 · pp. 2–3
  • XML-CNN applies a deep convolutional network with a narrow final layer to XMLC, but the paper reports inferior predictive performance to its FASTTEXT-based PLTs.The paper characterizes XML-CNN as computationally expensive.Source: §2 · p. 3

3 Problem statement

The problem statement formalizes XMLC as predicting a sparse set of relevant labels from a large label space. It motivates marginal-probability estimation and precision@k as a way to assess prediction quality.

3 Problem statement

  • XMLC assumes a large label set, potentially at least 10^5 labels, with far fewer relevant labels per instance, and models examples as i.i.d. draws from a joint distribution.The label vector is binary, with y_j = 1 exactly when label j is relevant.Source: §3 · p. 3
  • The objective is to find a classifier mapping instances to label scores that minimizes expected task loss; regret measures its suboptimality against the optimal classifier.The paper aims for small, ideally zero, regret.Source: §3 · p. 3
  • Marginal probabilities η_j(x) are central to several measures, and label-wise log loss is presented as a surrogate for estimating them.The paper names Hamming loss, macro-F measure, and precision@k as measures for which marginal probabilities are key.Source: §3 · p. 3
  • For precision@k, the optimal prediction selects the k labels with the highest marginal probabilities, and the paper defines conditional regret for this metric.Precision@k is described as a standard extreme-classification measure, though it is criticized for favoring frequent labels.Source: §3 · p. 4
  • The paper motivates label trees as a more efficient alternative to one-vs-all, whose cost is too high in the extreme setting.The proposed alternative estimates marginal probabilities competitively and more efficiently.Source: §3 · p. 4

4 Hierarchical softmax approaches

Hierarchical softmax represents labels as paths in a tree and obtains label probabilities through node-level conditional decisions. The section describes its multi-class setup, training alternatives, and the search required for top-k prediction.

4 Hierarchical softmax approaches

  • HSM encodes each label as a unique codeword on a label tree, with each root-to-leaf path corresponding to a codeword.The code may be binary or use larger, potentially varying alphabets and node arities.Source: §4 · p. 4
  • A label probability is computed from the sequence of conditional decisions made by node classifiers along its code path.The paper derives this factorization using the chain rule of probability.Source: §4 · p. 4
  • Popular HSM uses logistic loss and a linear model at each node to estimate conditional probabilities.In the multi-class setting, normalization permits classifiers at internal nodes; alternatively, classifiers can be associated with non-root nodes with additional normalization.Source: §4 · pp. 4–5
  • A label's probability estimate is obtained by traversing its code path, but top-k prediction requires searching the tree.Popular search methods include beam search, uniform-cost search, and an approximate variant.Source: §4 · p. 5

5 Suboptimality of HSM for multi-label classification

The pick-one-label reduction does not generally preserve the marginal probabilities needed for precision@k, so HSM with this heuristic is not a consistent multi-label solution. Under conditional independence, however, it preserves marginal-probability ordering for precision@k.

5 Suboptimality of HSM for multi-label classification

  • Pick-one-label randomly selects one positive label and treats the resulting training instance as a multi-class example.At prediction time, the heuristic returns a multi-class distribution and its k most probable labels.Source: §5 · p. 5
  • The pick-one-label reduction is not consistent in general for precision@k because it can change the ordering of labels by marginal probability.The paper gives a counterexample with nonzero precision@k regret.Source: §5 · p. 5
  • For the example distribution, pick-one-label predicts label 3 instead of optimal label 1, producing regret 0.2 for precision@1.The respective marginal probabilities are 0.6, 0.5, and 0.4; the transformed probabilities are 0.35, 0.25, and 0.4.Source: §5 · p. 5
  • With conditionally independent labels, pick-one-label preserves marginal-probability ordering and is consistent for precision@k.The independence condition changes the general inconsistency result.Source: §5 · pp. 5–6

6 Probabilistic label trees

Probabilistic label trees (PLTs) extend hierarchical softmax by encoding whether a subtree contains a positive label and estimating conditional probabilities at tree nodes. Their marginal-probability error and precision@k regret are bounded through the regrets of the node classifiers.

6 Probabilistic label trees

  • A PLT encodes each positive label with an extended path code, including a root indicator for whether any label in the subtree is positive.The chain rule expresses each label's marginal probability through conditional probabilities along its path.Source: §6 · p. 6
  • PLTs estimate binary conditional probabilities at every tree node, including leaves, and may recalibrate estimates during prediction to normalize them.For a multi-class distribution, PLTs reduce to HSM.Source: §6 · p. 6
  • PLTs bound marginal-probability error by the regrets of node classifiers along the corresponding root-to-leaf path.The bound assumes a strongly proper composite loss; the node regret is conditioned on the parent node being reached.Source: §6 · p. 6
  • The precision@k regret is upper-bounded in terms of node-classifier regret, yielding an optimal precision@k solution when node-classifier regret is zero.The result applies to the PLT regret bound described for node classifiers.Source: §6 · pp. 6–7

7 Implementation details of PLTs

The XT implementation trains PLTs online with dense instance representations, building on FASTTEXT. Its tree is formed by recursively clustering label profiles, while the implementation also specifies regularization, feature weighting, and training behavior for positive-only nodes.

7 Implementation details of PLTs

  • XT builds on FASTTEXT to train PLTs online using dense input representations, producing a compressed model intended for fast online prediction.The paper contrasts small dense models with sparse models that can require decompression and more memory.Source: §7 · p. 7
  • The implementation uses L2 regularization and TF-IDF-weighted feature vectors, with feature and instance vectors of size 500 reported as competitive.Positive-only node tasks use a constant classifier predicting 1.Source: §7 · p. 7
  • XT constructs a balanced tree by recursively clustering label profile vectors with balanced k-means until clusters fall below a chosen size.Similar labels are grouped nearby, and the resulting tree has logarithmic depth in the number of labels.Source: §7 · p. 7
  • PLT tree structure affects the difficulty of node-learning problems in practice, although the stated vanishing-regret guarantees hold regardless of tree structure.The guarantees require node-classifier regret to vanish.Source: §7 · p. 7

8 Empirical results

Across synthetic and benchmark tests, PLTs outperform HSM on dependent-label data and benchmarks, while XT compares favorably with competing XMLC methods. XT also offers strong prediction speed and an ablation study finds its components work best in combination.

First experiment

  • PLTs significantly outperform HSM on synthetic data with conditionally dependent labels and perform better on benchmark data.On synthetic data, HSM and PLTs are on par when labels are independent, and their models are the same for multi-class data.Source: §8 · p. 8

Second experiment

  • XT outperforms FASTTEXT and LEARNED TREE by a large margin, and exceeds XML-CNN in predictive performance with computational costs an order of magnitude smaller.XT is also reported to be 10000x faster than DISMEC and 100x faster than PPD-SPARSE during prediction.Source: §8 · p. 8

Third experiment

  • Top-down clustering, TF-IDF-based weighting, and L2 regularization together produce the best XT results in the ablation analysis.Top-down clustering alone performs worse than Huffman trees combined with TF-IDF weighting and L2 regularization.Source: §8 · p. 8

9 Conclusions

The paper establishes PLTs as a no-regret multi-label generalization of HSM and finds the pick-one-label heuristic inconsistent in general. Its XT implementation performs strongly against several baselines, with online prediction and model-size advantages.

9 Conclusions

  • PLTs are a no-regret generalization of HSM for multi-label classification, while the pick-one-label heuristic is inconsistent for marginal probability estimation and precision@k.XT, built upon FASTTEXT, is significantly better than FASTTEXT, LEARNED TREE, and XML-CNN; its results are close to those of expensive 1-vs-All methods.Source: §9 · p. 8
  • The online variant often produces much smaller models that can be used for fast online prediction.The conclusion also describes XT as close to the best known results from expensive 1-vs-All approaches.Source: §9 · pp. 8–9

A Regret for precision@k

The section connects PLT node-classifier regrets to marginal-probability and precision@k regret, then examines a conditional-independence case for pick-one-label, tree-cost criteria, and PLT prediction. Its guarantees distinguish general multi-label behavior from special cases such as conditionally independent labels.

A Regret for precision@k

  • PLT marginal-probability estimation error is bounded by the regrets of node classifiers along the label’s root-to-leaf path; zero-regret node classifiers yield optimal marginal estimates and precision@k predictions.The precision@k bound follows by combining the marginal-probability bound with the result that selecting the k highest true marginals is optimal.Source: A Regret for precision@k · p. 14

B Hierarchical softmax with the pick-one-label heuristic

  • For conditionally independent labels, pick-one-label preserves the ordering of marginal probabilities, so choosing the k highest resulting scores has zero precision@k regret.This is a special-case guarantee for conditionally independent labels.Source: B Hierarchical softmax with the… · pp. 14–15

C Huffman codes for PLTs

  • Huffman coding minimizes expected computational cost among binary codes in the multi-class case, but this result does not carry over to multi-label PLTs.For multi-label PLTs, an inner node’s score cannot be represented as the sum of its children’s scores.Source: C Huffman codes for PLTs · p. 16

D Pseudocode of PLTs

  • PLT inference uses uniform-cost search with a priority queue, expanding the highest-probability node estimate until k labels are found or the queue is empty.A leaf adds its label to the prediction; an internal node adds its children’s probability estimates to the queue.Source: D Pseudocode of PLTs · p. 17

E.1 Comparison of PLTs and HSM on synthetic data

PLTs outperform HSM on benchmark data and, on synthetic data, significantly outperform it when labels are conditionally dependent. XT’s strongest ablation combines top-down clustering, TF-IDF weighting, and L2 regularization.

E.1 Comparison of PLTs and HSM on synthetic data

  • On synthetic data, PLTs match HSM on multiclass and independent-label cases, but significantly outperform it with conditionally dependent labels.The experiments report precision@1 across the three synthetic data types.Source: §E.1 · pp. 17, 19, Table 2 · p. 19

E.2 Comparison of PLTs and HSM on benchmark data

  • PLTs outperform HSM on benchmark datasets.The comparison used Vowpal Wabbit sparse-representation and FASTTEXT dense-representation implementations.Source: §E.2 · p. 19, Table 3 · p. 19

E.3 The ablation analysis on benchmark datasets

  • The best XT ablation usually combines top-down clustering, TF-IDF weighting, and L2 regularization.Top-down clustering alone performs worse than Huffman trees combined with TF-IDF weighting and L2 regularization.Source: §E.3 · p. 20, Table 4 · p. 20

E.4 Tuning of hyperparameters

  • Tuning covers tree arity and learning rate for HSM and PLT; XT also uses L2 regularization and a k-means stopping parameter.For FASTTEXT-based methods, the learning rate decreases linearly during training; XT’s balanced k-means stopping parameter defaults to 0.001.Source: §E.4 · p. 20, Table 5 · p. 20

F Information about the benchmark datasets

The benchmark datasets used in the experiments are drawn from the Extreme Classification Repository, and their basic statistics are reported in Table 8.

F Information about the benchmark datasets

Related papers

Loading 1810.11671v1…