Adaptive Hierarchical Certification for Semantic Segmentation using Randomized Smoothing

Question: It seems that Theorem 1 is originally from (Fischer et al., 2021), not sure why put it in the main paper.

Answer: Yes, we clearly state that Theorem 1 is from (Fischer et al., 2021). We added it for convenience and completeness, as it is central to our work, and we refer to it multiple times.

Question: A problem of introducing class hierarchy is that when applied to a new dataset, for example, the ADE20k dataset, a new class hierarchy graph should be prepared. Not sure how to make the proposed method universal to different segmentation datasets.

Answer: For the purpose of our contribution, we assume a pre-defined class hierarchy. The class hierarchy is intrinsic to the class structure of each task/dataset. AdaptiveCertify can be used with any hierarchy, and can therefore be applied to any segmentation task. Automatically creating hierarchies from a set of classes is a very different problem, which is beyond the scope of this paper. How the hierarchy is created has no effect on our certification algorithm.

Question: More datasets, with more than 19 classes, should be used to evaluate the performance of the proposed method.

Reply: We agree that experiments on an additional dataset and investigating the effect of the number of classes will strengthen the submission. It is infeasible to run these experiments within the timeframe of the discussion, but we will add them for the final revision.

Question: I also think some segmentation results should be visualized to see in which cases the proposed adaptive hierarchical certification helps.

Reply: Thank you for the suggestion, we agree and provide additional qualitative examples in the Appendix Section A.3 of our updated submission. We include examples where our method shows large improvements over the baseline in Figure 9, as well as randomly selected samples in Figures 10 and 11.

Question: From the paper, we can see that 7/9 space of this paper is used describe the introduction, related work, and method. Less than 2/9 of the space in the main paper are used to do experiment evaluation. Though there is some experimental analysis in the supplementary material, this is not adequate to well evaluate the proposed method and metric as posted in the weaknesses part.

Reply: The core part of our method is that it guarantees the model’s robustness with respect to input perturbations. We therefore believe it is crucial to emphasize the method section and prove SegCertify’s soundness. As mentioned by the reviewer, there are additional experiments in the appendix, which explore different settings, parameters, and properties.

Question: Soundness: 2 fair

Reply: Why do you believe the method to be unsound? We propose a verification mechanism which proves robustness to adversarial perturbations, and prove this property in Section 4. Without detailed arguments, this statement is not helpful.

Dear reviewer,

Unfortunately, this review is very short and generic, which makes it difficult for us to provide a meaningful response. In our eyes, it is unsuitable to evaluate our paper in its current form. We kindly ask you to revise and improve your review.

Question: The technical contributions are not clear. There are some components combined together. What is the contribution of each component?

Answer: What do you mean by “There are some components combined together?” It is unclear what components you are referring to. We discuss our exact contributions in Section 1 in the paragraph titled Contributions, and the overall method in Section 4.

Question: The experiments are insufficient. The authors should compare with more baselines on more datasets.

Answer: Why do you think that the experiments are insufficient? There is only a single method for certification of semantic segmentation models, SegCertify, which we compare to. We are not aware of any additional baselines. Which methods are you asking to compare to?

With regards to using more datasets, is there a specific quality you seek to explore using other datasets than Cityscapes and ACDC?

Question: Soundness: 2 fair

Answer: Why do you believe the method to be unsound? We propose a verification mechanism which proves robustness to adversarial perturbations, and prove this property in Section 4. Without detailed arguments, this statement is not helpful.

(1) Technical Contribution

This work is largely based on SegCertify [Fischer et al.,2021]

Our method is based on SegCertify. However. we don't have the same problem definition. We show that by introducing the concept of a semantic hierarchy and adapting a formal certification setup to it that we can abstain less while providing meaningful certified output. We introduce significant advances over the base method, which makes it applicable to the hierarchical certification setting and improves its CIG.. The major differences are: (i) We introduce and mathematically formulate the hierarchical certification for segmentation problem, as discussed in Section 4.1, (ii) Due to the hierarchical nature, we have to sample from multiple hierarchy levels, as opposed to the flat hierarchy setup in SegCertify. We therefore introduce adaptive sampling in 4.3, particularly HSample in Algorithm 2., (iii) Our implementation of AdaptiveCertify in 4.4 is largely different from SegCertify as we employ our novel functions that adapt to the hierarchical setup such as GetComponentsLevels and HSample, (iv) All of these changes have to be done in a statistically sound manner, to ensure we compute sound guarantees. We show the soundness of AdaptiveCertify, which maintains the i.i.d assumptions in the sampling process, in Section 4.4.

As for the CIG, there are no insights why we should use that form

The insights behind using the CIG metric is that it accounts for the trades-off between class granularity and certified accuracy, as discussed in Section 4.6.

(2) Insufficient experiments

Question: As a typical vision task, should the authors provide reuslts with the mIoU, mAP, etc?

Answer: This paper is not a typical computer vision paper. It discusses certification for a computer vision problem: segmentation. Therefore, only certified metrics (e.g., CIG) are relevant for comparison.

Second, from the results in Tab.1, there are no significant differences in the performance (the gaps < 2%).

The 0.02 improvement is the average over the test subset. For some, especially the challenging examples, it is higher reaching up to 0.04. Moreover, our improvement goes beyond CIG to also decreasing the abstain rate consistently (up to > 11%), and hence, providing more certified output (Table. 1). We have added visual examples highlighting the CIG performance increase and abstain rate decrease in the Appendix section A.3.

Third, there are no enough examples to clarify the final conclusion.

We ran our experiments further to include 200 images from each dataset, and have updated Table. 1 accordingly. However, please not that certifying a subset of 100 images is common for certification work due to the high computational cost (Fischer et. al, 2021) and (Singh et. al, 2019).

Finally, there are no visual examples for the failure cases

Thank you for the suggestion! We provide additional examples for images where the samples are picked randomly in the Appendix Figures 10 and 11 under section A.3. On our test subset, we have not encountered failure cases where our certified information gain is lower than the baseline. Moreover, we discuss that our abstain rate will always be lower than the baseline in Section 4.5, as it also shows in the mentioned visual examples.

(3) Unclear details

Question: For examples, what is the meaning of IP in Eq.1?

$\mathbb{P}$ in Eq.1 means probability, as explained in the surrounding paragraph and all prior work on the topic.

Question: What are the type I and type II errors?

Answer: Type I and type II errors correspond to the two standard error types of statistical hypothesis testing, which are basic concepts from the statistics literature. They are briefly mentioned in Sections 4.4 and 4.5. To further clarify, Type I and Type II errors occur when the null hypothesis is either wrongly rejected or wrongly accepted, respectively. Our hypothesis test is conducted per component/pixel, and the null hypothesis is that the top vertex class probability is $< \tau$. There are two cases:

• (Type I error) Rejecting the null hypothesis while it is true: In our algorithm, this means that we certify a component, while its top class probability is $<\tau$. We bound the probability of this error by $\alpha$.

• (Type II error) Accepting the null hypothesis while it is false. In our algorithm, this means that we abstain from a component while in fact its top class probability is $\geq \tau$, which means it should have been certified.

Question: How do the SAMPLEPOSTERIORS and HSAMPLE operate?

SAMPLEPOSTERIORS computes $n$ samples of $f_\mathrm{seg}(x + \epsilon)$, as defined in Section 4.3. HSample is defined in Algorithm 2.

What is the effect of using different hierarchical structure for semantic classes?

Thank you for suggesting this! Given the limited time frame, we plan on including a different hierarchical structure in the final revision.

$\mathbb{P}$ in Eq.1 means probability, as explained in the surrounding paragraph and all prior work on the topic. We give an overview of the most central concepts to understand our contribution and the related work in Section 2. However, it is beyond the scope of a background section in a 9-page conference paper to introduce the entire field of certification from the ground up.