# Set-valued prediction in hierarchical classification with constrained representation complexity

arXiv: https://arxiv.org/abs/2203.06676 · HTML: https://mlsanity.com/paper/2203.06676/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 57 references that are in the map.
- First posted on arXiv 13 Mar 2022.

## Builds on (most cited first, 8 of 8)

- [MobileNetV2: Inverted Residuals and Linear Bottlenecks](https://mlsanity.com/paper/1801.04381/) (2018)
- [Least Ambiguous Set-Valued Classifiers with Bounded Error Levels](https://mlsanity.com/paper/1609.00451/) (2016)
- [DiSMEC - Distributed Sparse Machines for Extreme Multi-label Classification](https://mlsanity.com/paper/1609.02521/) (2016)
- [A no-regret generalization of hierarchical softmax to extreme multi-label classification](https://mlsanity.com/paper/1810.11671/) (2018)
- [Loss Functions for Top-k Error: Analysis and Insights](https://mlsanity.com/paper/1512.00486/) (2015)
- [Set-valued classification -- overview via a unified framework](https://mlsanity.com/paper/2102.12318/) (2021)
- [Learning Optimal Tree Models Under Beam Search](https://mlsanity.com/paper/2006.15408/) (2020)
- [Conditional Probability Tree Estimation Analysis and Algorithms](https://mlsanity.com/paper/1408.2031/) (2014)

## Built on by (most cited first, 3 of 3)

- [Conformal Structured Prediction](https://mlsanity.com/paper/2410.06296/) (2024)
- [Conformal Prediction in Hierarchical Classification with Constrained Representation Complexity](https://mlsanity.com/paper/2501.19038/) (2025)
- [Hierarchical Conformal Classification](https://mlsanity.com/paper/2508.13288/) (2025)

## Abstract (arXiv)

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.