Adaptive Hierarchical Certification for Segmentation using Randomized
  Smoothing
Alaa Anani Tobias Lorenz Bernt Schiele Mario Fritz
Common certification methods operate on a flat pre-defined set of
fine-grained classes. In this paper, however, we propose a novel, more general,
and practical setting, namely adaptive hierarchical certification for image
semantic segmentation. In this setting, the certification can be within a
multi-level hierarchical label space composed of fine to coarse levels. Unlike
classic methods where the certification would abstain for unstable components,
our approach adaptively relaxes the certification to a coarser level within the
hierarchy. This relaxation lowers the abstain rate whilst providing more
certified semantically meaningful information. We mathematically formulate the
problem setup and introduce, for the first time, an adaptive hierarchical
certification algorithm for image semantic segmentation, that certifies image
pixels within a hierarchy and prove the correctness of its guarantees. Since
certified accuracy does not take the loss of information into account when
traversing into a coarser hierarchy level, we introduce a novel evaluation
paradigm for adaptive hierarchical certification, namely the certified
information gain metric, which is proportional to the class granularity level.
Our evaluation experiments on real-world challenging datasets such as
Cityscapes and ACDC demonstrate that our adaptive algorithm achieves a higher
certified information gain and a lower abstain rate compared to the current
state-of-the-art certification method, as well as other non-adaptive versions
of it.