Set-valued prediction in hierarchical classification with constrained representation complexity

• URL: http://arxiv.org/abs/2203.06676v1
• Date: Sun, 13 Mar 2022 15:13:19 GMT
• Title: Set-valued prediction in hierarchical classification with constrained representation complexity
• Authors: Thomas Mortier, Eyke H\"ullermeier, Krzysztof Dembczy\'nski, Willem Waegeman
• Abstract summary: We focus on hierarchical multi-class classification problems, where valid sets correspond to internal nodes of the hierarchy. We propose three methods and evaluate them on benchmark datasets.
• Score: 4.258263831866309
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Set-valued prediction is a well-known concept in multi-class classification. When a classifier is uncertain about the class label for a test instance, it can predict a set of classes instead of a single class. In this paper, we focus on hierarchical multi-class classification problems, where valid sets (typically) correspond to internal nodes of the hierarchy. We argue that this is a very strong restriction, and we propose a relaxation by introducing the notion of representation complexity for a predicted set. In combination with probabilistic classifiers, this leads to a challenging inference problem for which specific combinatorial optimization algorithms are needed. We propose three methods and evaluate them on benchmark datasets: a na\"ive approach that is based on matrix-vector multiplication, a reformulation as a knapsack problem with conflict graph, and a recursive tree search method. Experimental results demonstrate that the last method is computationally more efficient than the other two approaches, due to a hierarchical factorization of the conditional class distribution.

Related papers

• Mitigating Word Bias in Zero-shot Prompt-based Classifiers [55.60306377044225]
  We show that matching class priors correlates strongly with the oracle upper bound performance. We also demonstrate large consistent performance gains for prompt settings over a range of NLP tasks.
  arXiv  Detail & Related papers  (2023-09-10T10:57:41Z)
• Class-Conditional Conformal Prediction with Many Classes [60.8189977620604]
  We propose a method called clustered conformal prediction that clusters together classes having "similar" conformal scores. We find that clustered conformal typically outperforms existing methods in terms of class-conditional coverage and set size metrics.
  arXiv  Detail & Related papers  (2023-06-15T17:59:02Z)
• Semi-supervised Predictive Clustering Trees for (Hierarchical) Multi-label Classification [2.706328351174805]
  We propose a hierarchical multi-label classification method based on semi-supervised learning of predictive clustering trees. We also extend the method towards ensemble learning and propose a method based on the random forest approach.
  arXiv  Detail & Related papers  (2022-07-19T12:49:00Z)
• Multi-class Classification with Fuzzy-feature Observations: Theory and Algorithms [36.810603503167755]
  We propose a novel framework to address a new realistic problem called multi-class classification with imprecise observations (MCIMO) First, we give the theoretical analysis of the MCIMO problem based on fuzzy Rademacher complexity. Then, two practical algorithms based on support vector machine and neural networks are constructed to solve the proposed new problem.
  arXiv  Detail & Related papers  (2022-06-09T07:14:00Z)
• Ensemble pruning via an integer programming approach with diversity constraints [0.0]
  In this paper, we consider a binary classification problem and propose an integer programming (IP) approach for selecting optimal subsets. We also propose constraints to ensure minimum diversity levels in the ensemble. Our approach yields competitive results when compared to some of the best and most used pruning methods in literature.
  arXiv  Detail & Related papers  (2022-05-02T17:59:11Z)
• A Top-down Supervised Learning Approach to Hierarchical Multi-label Classification in Networks [0.21485350418225244]
  This paper presents a general prediction model to hierarchical multi-label classification (HMC), where the attributes to be inferred can be specified as a strict poset. It is based on a top-down classification approach that addresses hierarchical multi-label classification with supervised learning by building a local classifier per class. The proposed model is showcased with a case study on the prediction of gene functions for Oryza sativa Japonica, a variety of rice.
  arXiv  Detail & Related papers  (2022-03-23T17:29:17Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  We propose a deep learning-based graph matching framework that works for the original QAP without compromising on the matching constraints. The proposed method is evaluated on three popularly tested benchmarks (Pascal VOC, Willow Object and SPair-71k) and it outperforms all previous state-of-the-arts on all benchmarks.
  arXiv  Detail & Related papers  (2022-01-05T13:37:27Z)
• Multiple Classifiers Based Maximum Classifier Discrepancy for Unsupervised Domain Adaptation [25.114533037440896]
  We propose to extend the structure of two classifiers to multiple classifiers to further boost its performance. We demonstrate that, on average, adopting the structure of three classifiers normally yields the best performance as a trade-off between the accuracy and efficiency.
  arXiv  Detail & Related papers  (2021-08-02T03:00:13Z)
• Binary Classification from Multiple Unlabeled Datasets via Surrogate Set Classification [94.55805516167369]
  We propose a new approach for binary classification from m U-sets for $mge2$. Our key idea is to consider an auxiliary classification task called surrogate set classification (SSC)
  arXiv  Detail & Related papers  (2021-02-01T07:36:38Z)
• 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)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  We study the problem of clustering a set of items from binary user feedback. We devise an algorithm with a minimal cluster recovery error rate. For adaptive selection, we develop an algorithm inspired by the derivation of the information-theoretical error lower bounds.
  arXiv  Detail & Related papers  (2019-10-14T09:18:26Z)

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.