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.
