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

Abstract

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.

Accepted at NIPS 2018

Cited by in corpus (22)

• The Emerging Trends of Multi-Label Learning
• Classifier Chains: A Review and Perspectives
• DECAF: Deep Extreme Classification with Label Features
• Pretrained Generalized Autoregressive Model with Adaptive Probabilistic Label Clusters for Extreme Multi-label Text Classification
• LightXML: Transformer with Dynamic Negative Sampling for High-Performance Extreme Multi-label Text Classification
• Taming Pretrained Transformers for Extreme Multi-label Text Classification
• Probabilistic Label Trees for Extreme Multi-label Classification
• LdSM: Logarithm-depth Streaming Multi-label Decision Trees
• Propensity-scored Probabilistic Label Trees
• Prototype Memory for Large-scale Face Representation Learning
• Top-K Pairwise Ranking: Bridging the Gap Among Ranking-Based Measures for Multi-Label Classification
• Unbiased Loss Functions for Extreme Classification With Missing Labels
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy
• Disentangling Sampling and Labeling Bias for Learning in Large-Output Spaces
• On the computational complexity of the probabilistic label tree algorithms
• Doubly-stochastic mining for heterogeneous retrieval
• Multilabel Classification by Hierarchical Partitioning and Data-dependent Grouping
• Online probabilistic label trees
• Active Refinement for Multi-Label Learning: A Pseudo-Label Approach
• Extreme Multi-label Learning for Semantic Matching in Product Search
• Learning with Holographic Reduced Representations
• CEAR: Cross-Entity Aware Reranker for Knowledge Base Completion