Logo Logo
Hilfe
Hilfe
Switch Language to English

Mortier, Thomas ORCID logoORCID: https://orcid.org/0000-0001-9650-9263; Hüllermeier, Eyke ORCID logoORCID: https://orcid.org/0000-0002-9944-4108; Dembczyński, Krzysztof und Waegeman, Willem ORCID logoORCID: https://orcid.org/0000-0002-5950-3003 (August 2022): Set-valued prediction in hierarchical classification with constrained representation complexity. 38th Conference on Uncertainty in Artificial Intelligence, Eindhoven, Netherlands, 1-5 August 2022. Cussens, James und Zhang, Kun (Hrsg.): In: Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, Bd. 180 PMLR. S. 1392-1401 [PDF, 600kB]

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ïve 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.

Dokument bearbeiten Dokument bearbeiten