Probabilistic Label Trees for Extreme Multi-label Classification

• URL: http://arxiv.org/abs/2009.11218v1
• Date: Wed, 23 Sep 2020 15:30:00 GMT
• Title: Probabilistic Label Trees for Extreme Multi-label Classification
• Authors: Kalina Jasinska-Kobus, Marek Wydmuch, Krzysztof Dembczynski, Mikhail Kuznetsov, Robert Busa-Fekete
• Abstract summary: Problems of extreme multi-label classification (XMLC) are efficiently handled by organizing labels as a tree. PLTs can be treated as a generalization of hierarchical softmax for multi-label problems. We introduce the model and discuss training and inference procedures and their computational costs. We prove a specific equivalence between the fully online algorithm and an algorithm with a tree structure given in advance.
• Score: 8.347190888362194
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Semi-Supervised Hierarchical Multi-Label Classifier Based on Local Information [1.6574413179773761]
  Semi-supervised hierarchical multi-label classifier based on local information (SSHMC-BLI) SSHMC-BLI builds pseudo-labels for each unlabeled instance from the paths of labels of its labeled neighbors. Experiments on 12 challenging datasets from functional genomics show that making use of unlabeled along with labeled data can help to improve the performance of a supervised hierarchical classifier trained only on labeled data.
  arXiv  Detail & Related papers  (2024-04-30T20:16:40Z)
• Multi-Label Knowledge Distillation [86.03990467785312]
  We propose a novel multi-label knowledge distillation method. On one hand, it exploits the informative semantic knowledge from the logits by dividing the multi-label learning problem into a set of binary classification problems. On the other hand, it enhances the distinctiveness of the learned feature representations by leveraging the structural information of label-wise embeddings.
  arXiv  Detail & Related papers  (2023-08-12T03:19:08Z)
• Contrastive Meta-Learning for Few-shot Node Classification [54.36506013228169]
  Few-shot node classification aims to predict labels for nodes on graphs with only limited labeled nodes as references. We create a novel contrastive meta-learning framework on graphs, named COSMIC, with two key designs.
  arXiv  Detail & Related papers  (2023-06-27T02:22:45Z)
• Tree Learning: Optimal Algorithms and Sample Complexity [10.638365461509]
  We study the problem of learning a hierarchical tree representation of data from labeled samples taken from an arbitrary distribution. We present optimal sample bounds for this problem in several learning settings, including (agnostic) learning and online learning.
  arXiv  Detail & Related papers  (2023-02-09T08:35:17Z)
• Use All The Labels: A Hierarchical Multi-Label Contrastive Learning Framework [75.79736930414715]
  We present a hierarchical multi-label representation learning framework that can leverage all available labels and preserve the hierarchical relationship between classes. We introduce novel hierarchy preserving losses, which jointly apply a hierarchical penalty to the contrastive loss, and enforce the hierarchy constraint.
  arXiv  Detail & Related papers  (2022-04-27T21:41:44Z)
• Propensity-scored Probabilistic Label Trees [3.764094942736144]
  We introduce an inference procedure, based on the $A*$-search algorithm, that efficiently finds the optimal solution for XMLC problems. We demonstrate the attractiveness of this approach in a wide empirical study on popular XMLC benchmark datasets.
  arXiv  Detail & Related papers  (2021-10-20T22:10:20Z)
• Label Disentanglement in Partition-based Extreme Multilabel Classification [111.25321342479491]
  We show that the label assignment problem in partition-based XMC can be formulated as an optimization problem. We show that our method can successfully disentangle multi-modal labels, leading to state-of-the-art (SOTA) results on four XMC benchmarks.
  arXiv  Detail & Related papers  (2021-06-24T03:24:18Z)
• Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View [82.80085730891126]
  We provide the first modernally precise analysis of linear multiclass classification. Our analysis reveals that the classification accuracy is highly distribution-dependent. The insights gained may pave the way for a precise understanding of other classification algorithms.
  arXiv  Detail & Related papers  (2020-11-16T05:17:29Z)
• Online probabilistic label trees [5.694890215546457]
  OPLTs are characterized by low time and space complexity as well as strong theoretical guarantees. They can be used for online multi-label and multi-class classification, including the very challenging scenarios of one- or few-shot learning.
  arXiv  Detail & Related papers  (2020-07-08T21:45:00Z)
• Online Metric Learning for Multi-Label Classification [22.484707213499714]
  We propose a novel online metric learning paradigm for multi-label classification. We first propose a new metric for multi-label classification based on $k$-Nearest Neighbour ($k$NN)
  arXiv  Detail & Related papers  (2020-06-12T11:33:04Z)
• Interaction Matching for Long-Tail Multi-Label Classification [57.262792333593644]
  We present an elegant and effective approach for addressing limitations in existing multi-label classification models. By performing soft n-gram interaction matching, we match labels with natural language descriptions.
  arXiv  Detail & Related papers  (2020-05-18T15:27:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.