Set-valued prediction in hierarchical classification with constrained representation complexity
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.
Code (0)
등록된 구현이 없습니다.
Tasks
ClassificationCombinatorial OptimizationMulti-class ClassificationvalidSimilar Papers 제목 키워드 기반
Time Series Classification through Diffeomorphic Time Warping (DiffTW)
Time series classification involves learning a mapping from a continuous, temporally ordered sequence of real-valued observations to discrete response variables, like class labels. This task is fundamental in domains, in…
Time Series ClassificationBidirectional Hierarchical Protein Multi-Modal Representation Learning
Protein representation learning is critical for numerous biological tasks. Recently, large transformer-based protein language models (pLMs) pretrained on large scale protein sequences have demonstrated significant succes…
PredictionRepresentation LearningAitchison Embeddings for Learning Compositional Graph Representations
Representation learning is central to graph machine learning, powering tasks such as link prediction and node classification. However, most graph embeddings are hard to interpret, offering limited insight into how learne…
Representation LearningNode ClassificationLink PredictionGraph EmbeddingDeep Hierarchical Classification for Category Prediction in E-commerce System
In e-commerce system, category prediction is to automatically predict categories of given texts. Different from traditional classification where there are no relations between classes, category prediction is reckoned as …
ClassificationGeneral ClassificationPrediction$(α,β)$-Stability for Boosting Vector-Valued Prediction
Despite the widespread use of boosting in structured prediction, a general theoretical understanding of aggregation beyond scalar prediction remains incomplete. We study vector-valued prediction under a target divergence…
Structured PredictionDensity Estimation