Error Slice Discovery via Manifold Compactness

Thanks for your questions! We try to address your concerns below.

Q1: Does $\mathcal{Y}\times\mathcal{Y}$ represent the Cartesian product of two sets? If so, one should represent the predicted label, and the other should represent the true label. Why are both symbols $\mathcal{Y}$?

A1: Thanks for your question. Yes, it represents the Cartesian product of two sets, and they respectively represent the predicted label and the true label. In Line 73, we denote the prediction model as $f_{\theta}: \mathcal{X}\mapsto\mathcal{Y}$, so the symbol $\mathcal{Y}$ actually represents the predicted label space instead of the true label space. This does not contradict the notation in Line 71 $Y\in\mathcal{Y}$ since the true label space is a subset of the predicted label space. For example, for classification tasks of $K$ categories, the predicted label space is $\Delta^{K-1}=\\{(p_1, p_2,...,p_K)|\sum_{i=1}^k p_i=1, \forall p_i\geq 0, i=1,2,...,K\\}$, while the true label space is all $K$ dimensional one-hot vectors. For regression tasks, both the predicted label space and the true label space are $\mathbb{R}$. Meanwhile, such a notation is also employed in previous works that are influential in their own areas [1,2,3], including error slice discovery, domain generalization, and continual learning.

Q2-1: Why does the ACC of the error slices identified by MCSD outperform the SOTA methods by such a large margin?

A2-1: Thanks for your question. As we mentioned in Definition 1 and Line 312-318, although there are two evaluation metrics at the same time, since we put more emphasis on the coherence inside the identified slice for better interpretability, we only require the performance of the identified slice to be lower than the overall average performance by a certain threshold, while expecting the coherence metric to be as high as possible. Thus the higher accuracy of the error slices identified by MCSD than previous SOTA methods is not our concern, since the accuracies of error slices identified by both MCSD and previous SOTA methods are significantly lower than the overall performance.

Q2-2: Besides this specific similar feature, what other factors could lead to poor performance of the sliced subsets?

A2-2: Thanks for your question. We would like to clarify that we are not trying to find similar features thus to decrease the performance of the identified slices, but we are trying to find slices with similar features that are underperforming at the same time. Thus it might be hard to say there is a causal relationship between poor performance of slices and similar features.

Q3: Why does Table 4 only compare the MCSD method with the Spotlight method?

A3: Thanks for your question. Table 4 presents the results on a task of object detection. As stated in Line 490-491, we could not compare with Domino or PlaneSpot since neither of them is applicable to tasks other than classification. This is because they require the prediction probability as the input, thus only applicable to classification, while our algorithm takes the prediction loss as input, naturally more flexible and applicable to various tasks. Such flexibility is an advantage of our method, which is empirically demonstrated through experiments of various case studies.

Q4: The expected trend in the experimental data is that as ACC increases, the Comp result should also increase. Why do Tables 2, 3, and 5 not follow this trend?

A4: Thanks for your question. We would like to clarify that our goal is to find underperforming slices that are coherent and interpretable, and both the risk (reversely corresponding to "ACC") and coherence (corresponding to "Comp") of the slice are part of our optimization objective (Equation 2). They are simultaneously optimized, and there is no expected trend for one of them when the other increases or decreases.

References

[1] Eyuboglu et al. "Domino: Discovering Systematic Errors with Cross-Modal Embeddings." ICLR, 2022.

[2] Zhou et al. "Domain generalization: A survey." TPAMI, 2022.

[3] Lopez-Paz et al. "Gradient episodic memory for continual learning." NeurIPS, 2017.

Dear Reviewer Dag2,

We would like to thank you for your time and efforts in reviewing our paper! We really look forward to your response and we would be very glad to engage in any further discussion if there are remaining concerns in the last three days of the discussion period.

Meanwhile, we also sincerely hope that you might take the revisions mentioned in our common responses to all reviewers into account when evaluating our contributions, including the theoretical analyses of our optimization objective, the newly added comparisons with more metrics directly calculated in Euclidean space, and other modifications for better clarity.

Thanks again for your efforts during the reviewing process!

Dear Reviewer Dag2,

We greatly thank you for your time in the review! We would like to kindly remind that there is only about an hour left for reviewers and authors to exchange responses with each other, and we are really eager to receive your response. We always look forward to discussing with you and will try our best to address any of your concerns.

Thanks again!

Dear Reviewer Dag2,

We sincerely apologize for sending another message.

We greatly appreciate your time and efforts in reviewing our work, and we look forward to your response very much! Meanwhile, we kindly wish to remind that there are less than 12 hours before Dec 2nd AOE, after which we could not exchange responses with each other, and we are really willing to engage in any further discussion to address your concerns.

Thank you again for taking time to review!

Thanks for your questions! We try to address your concerns below.

Q1: Use of monotonicity as a criterion for determining whether a measure of the semantics of slices is good.

A1: Thanks for your feedback. We would like to clarify that the monotonicity is one of the criteria for determining the coherence metric, but not the only one. Two implicit but necessary requirements are: being normalized by the sample size in the slice, and being intuitively reasonable. Both our proposed metric and variance satisfy these two requirements, so we did not emphasize these in our paper, and focused on the comparison in terms of monotonicity. The example that "uses the difference between the number of elements in the cluster and the total number of elements as the measure" might not be appropriate since it is not normalized by the sample size, and it is obviously not a reasonable metric to depict the coherence. Besides, in our revised version of paper, in Appendix A.1.2 on page 16, we also add comparisons with more coherence metrics that are directly calculated in the Euclidean space to further demonstrate the validity of our proposed metric. More details could be referred to in our first common response to all reviewers and the revised paper pdf.

Q2-1: The variables involved in the optimization objective appear to be w and the binary classifier g. How does this generate a new space?

A2-1: Thanks for your question. We would like to clarify that the space of the manifold is the constructed knn graph, and the "distance" between sample $i$ and $j$ is $q_{ij}$, i.e. whether there exists an edge between node $i$ and $j$ in the knn graph. In other words, the space has been pre-calculated and fixed when optimizing w or g.

Q2-2: How do you generate the picture that the authors show in Figure 2c?

A2-2: Thanks for your question. The details of generating Figure 2c have already been described in Appendix A.1.1. We employ features extracted by the image encoder of CLIP-ViT-B/32 and employ UMAP [1], a well-known dimension-reduction method that is manifold-based, to reduce the 512-dimension features into 2 dimensions and visualize them, with the blue dots represent correct samples and the red dots represent error samples. Besides Figure 2c, the result of Figure 2b also comes from a manifold-based dimension-reduction method t-SNE [2], while the result of Figure 2a comes from PCA that mainly preserves pairwise Euclidean distances between data points. We can see that the visualization of t-SNE and UMAP shows much clearer clustering structures than that of PCA, either having a larger number of clusters or exhibiting larger margins between clusters. This indicates that it could be better to measure coherence in the metric space of a manifold than in the original Euclidean space.

Q3: Why do we need to train the slicing function g when already obtaining the desired samples?

A3: Thanks for your question. In fact, the slicing function g is not really a necessary component of our algorithm. It is mainly designed to align with previous settings of evaluation and provide fair comparisons with previous methods. In the standard evaluation process of error slice discovery, an error slice discovery method is applied to validation data to obtain the slicing function, and then the slicing function is applied to test data to calculate evaluation metrics and conduct case analyses. Such practice is also adopted by dcbench [3], the benchmark of error slice discovery. If there is no test data and the evaluation metrics are calculated on validation data, which is already used to fit the slicing function, it is possible to achieve good performance via overfitting the validation data. To follow this practice, we additionally train a slicing function after we obtain the desired samples, so that we can compare fairly with previous methods. Since it is not a necessary component, for a better understanding of our algorithm, in our revised version of paper, we remove the training of the slicing function from our algorithm procedure on page 5, and put it into the section of experiments as a part of experimental details. It is worth noting that even without training this slicing function, our method can still produce meaningful results of case studies. We add the images sampled from the examples obtained before training the slicing function in Appendix A.11 on page 36 in our revised version of paper. We can see that our method is still capable of finding coherent slices.

Q3-2: Additionally, because distance variance lacks bounds, it is more sensitive to samples, especially if the sample features are not normalized. Therefore, the superiority of manifold compactness over variance may not be fully convincing. Consider adding a new distance-based measure. Different manifold constructions and distance calculations are also anticipated.

A3-2: Thanks for your valuable suggestion! Indeed variance could be sensitive to outliers, but it is not appropriate to normalize sample features here since they are extracted by pretrained models and the scale difference across feature dimensions could be meaningful, unlike in tabular data where normalization is standard practice. To mitigate the issue of sensitivity to outliers, we add the comparison with Mean Absolute deviation (MeanAD), Median Absolute Deviation (MedianAD), and Interquartile Range (IQR), which are less sensitive to outliers in Appendix A.1.2 on page 16 in our revised version of paper. We can see that these metrics that are directly calculated in the Euclidean space show similar phenomenons to variance, i.e. the metric value of the more coarse-grained slice is sometimes even smaller than that of the more fine-grained slice, which contradicts our expectation. As for manifold constructions, we choose knn graph not only because it is popular and relatively efficient [3,4,5], but also because a graph learning method is convenient when formulating the optimization objective (Equation 2) as a standard optimization problem.

Q4: The algorithm is divided into multiple parts, and an end-to-end model would be more desirable.

A4: Thanks for your suggestion! Our algorithm was divided into these parts: extracting image features, building a knn graph, solving the non-convex quadratic programming problem, and training a slicing function. For the training of the slicing function, the main reason of requiring it is to follow the standard setting of the error slice discovery benchmark dcbench [6] and provide fair comparisons with previous methods. In our revised version of paper, we remove this part from our algorithm procedure on page 5 and put it into the section of experiments as a part of experimental details. We also add a new subsection of Appendix A.11 on page 36 to demonstrate that our method is still effective without additionally training the slicing function. As for extracting image features, it is common practice employed in previous error slice discovery literature [6,7,8]. As for building a knn graph, we would leave the development of an end-to-end algorithm that incorporates manifold learning and error slice discovery for future work.

References

[1] Lee et al. "Smooth manifolds". Springer New York, 2012.

[2] Do Carmo, Manfredo P. "Differential geometry of curves and surfaces". Courier Dover Publications, 2016.

[3] Zemel et al. "Proximity graphs for clustering and manifold learning." NeurIPS, 2004.

[4] Pedronette et al. "Unsupervised manifold learning through reciprocal kNN graph and Connected Components for image retrieval tasks." Pattern Recognition, 2018.

[5] Dann et al. "Differential abundance testing on single-cell data using k-nearest neighbor graphs." Nature Biotechnology, 2022.

[6] Eyuboglu et al. "Domino: Discovering Systematic Errors with Cross-Modal Embeddings." ICLR, 2022.

[7] Jain et al. "Distilling Model Failures as Directions in Latent Space." ICLR, 2023.

[8] Plumb et al. "Towards a More Rigorous Science of Blindspot Discovery in Image Classification Models." TMLR, 2023.

Thanks for your valuable feedback! We try to address your concerns below.

Q1: The lack of theoretical analysis is regrettable.

A1: Thanks for pointing this out. Our formulated optimization objective (Equation 2) is a non-convex quadratic programming problem. In our revised version of paper, we conduct some theoretical analyses of it. First, we theoretically prove that our optimization objective not only explicitly considers the manifold compactness inside the identified slice, but also implicitly considers the separability between samples in and out of the identified slice. Second, we theoretically prove that the final optimization objective, where optimized variables are continuous, is equivalent to the original discrete version of sample selection with proper assumptions. This confirms the validity of our transformation of the problem from the discrete version into the continuous version, which is more convenient for optimization. For detailed formulations and proof, please refer to Appendix A.10 on page 34-35 in our revised version of paper.

Q2: There is no analysis of time and space complexity. For a dataset of size $n$, constructing a graph requires at least O($n^2$) and solving Equation 2 takes O($n^3$). In fact, as seen in Table 8, efficiency is indeed a drawback. The authors might consider explaining why this efficiency loss is worthwhile.

A2: Thanks for your feedback. For constructing the knn graph, the time complexity is $O(dn{\rm log}n)$ instead of $O(n^2)$, where $d$ denotes the feature dimension and $n$ denotes the sample size, since it can be constructed based on k-d tree. We can see in Table 8 that its construction is fast and only takes up a small proportion of running time. For solving Equation 2, as we stated at the beginning of Appendix A.5, since our optimization objective is a non-convex quadratic programming problem, and we employ Gurobi, a powerful and popular mathematical optimization solver designed for such problems, it is hard to analyze the time complexity. Therefore, we directly conduct empirical time comparisons between different methods in Table 8. Considering that error slice discovery serves as extra analyses instead of traditional model training or inference that sometimes poses a high demand on efficiency, and that our time cost is still generally low within only several minutes, we believe such an increase of time cost is acceptable and worthwhile given the effectiveness and flexibility of our method, which we have demonstrated through comprehensive experiments.

For the space complexity, the main increment compared with previous methods is the knn graph. Although the brute-force implementation requires space of $O(n^2)$ , with the help of k-d tree, which avoids storing all pairwise distances, the storage becomes $O(nd)$ (storage of the k-d tree) plus $O(nk)$ (storage of the sparse knn graph). Such a cost of space is also acceptable.

Q3-1: The paper suggests that Euclidean distance is inferior to manifold, but this may be misleading. In fact, constructing the k-nearest neighbors graph still depends on Euclidean distance.

A3-1: Thanks for your feedback. A basic assumption of manifold learning is that it shares similar local properties with the Euclidean space, i.e. it can be approximated by Euclidean space locally or in small regions [1,2]. Thus it is reasonable to use connections between close points to depict the manifold. Meanwhile, the construction of knn graph is popular and widely adopted in manifold learning [3,4,5].

Thanks for your valuable feedback! We try to address your concerns below.

Q1-1: The paper is difficult to understand and follow as the source code is not provided.

A1-1: Thanks for your reminder. Now we add the anonymous link to our code in our second common response.

Q1-2: The dimensions of all variables are not provided clearly, making the paper difficult to understand.

A1-2: Thanks for your feedback. We would like to clarify that the dimensions of the main variables have been provided in Appendix A.1 in both versions of our paper, e.g. the feature dimension in our main experiments is 512, corresponding to $z_i$ in our main paper. For other variables without mentioning the dimensions, e.g. $X\in\mathcal{X}$ and $Y\in\mathcal{Y}$, we believe that they do not affect the understanding of our paper. We are willing to provide further explanations if there are remaining concerns on this.

Q2-1: What’s the physical meaning of the second term in (2)?

A2-1: Thanks for your question. The second term is our proposed manifold compactness (Definition 1) on a set of weighted samples. As stated in Line 255-257, for the convenience of optimization, we assign a sample weight $w_i$ for each data point and treat the sample weights as the variable to be optimized. Thus the first term in (2) $\sum_{i=1}^n w_il_i$ becomes the weighted loss, and the second term $\sum_{i=1}^n\sum_{j=1}^n w_iw_jq_{ij}$ in (2) becomes the manifold compactness on a set of weighted samples.

Q2-2: What’s the optimization solution for (2)?

A2-2: Thanks for your question. To optimize it, since it formulates a non-convex quadratic programming problem, as stated in Line 270-271, we employ the mathematical optimization solver Gurobi, which is one of the most popular and widely used solvers for standard mathematical programming problems like (2). Meanwhile, in the revised version of our paper, we add some theoretical analyses of its solution, which could be referred to in our first common response.

Q3: There are not enough comparison methods.

A3: Thanks for your feedback. We would like to remind that the problem of error slice discovery is relatively new and less investigated, which does not have many comparable methods. As stated in the section of related work (Appendix B), there are now two paradigms of error slice discovery methods, and we compare with methods of the first paradigm, which separates error slice discovery and the later interpretation. Methods of the second paradigm incorporate the discovery and interpretation of error slices together and their effectiveness heavily relies on the usage of large multi-modal models and text-to-image models, which may not be realiable sometimes. Thus they are inappropriate to be compared with methods of the first paradigm, which our method belongs to.

Q4: What are the main advantages of the proposed method compared with the existing works?

A4: Thanks for your question. First, the effectiveness of our method is directly associated with the validity of our proposed metric, which is inspired by the data geometry property and whose validity has been demonstrated in our preliminary studies in Section 3. Second, unlike previous methods that indirectly incorporate the constraint of coherence into their design, our method directly treats the constraint of coherence as a part of the optimization objective. Besides, most previous methods require prediction probability as input while our method only requires prediction loss, so our method is naturally flexible to be applied to different tasks while most previous methods can be only applied to classification. The superiority and flexibility of our method are empirically shown in our experiments on the benchmark and the case studies of various tasks.

We thank all reviewers again for their valuable feedback and responses!

As suggested by Reviewer q2Dt, to be rigorous, we make minor modifications in terms of expressions related to Euclidean distance/space in our second revision of paper, which we mark in orange on page 2-4 and 15-16.