Set-valued prediction in hierarchical classification with constrained representation complexity
This work addresses hierarchical classification challenges for applications requiring uncertainty-aware predictions, but it is incremental as it builds on existing set-valued prediction concepts with new complexity constraints.
The paper tackles the problem of set-valued prediction in hierarchical classification by relaxing the constraint that predicted sets must correspond to internal nodes, introducing representation complexity to allow more flexible sets, and proposes three optimization methods, with the recursive tree search method showing computational efficiency improvements over the others.
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.