Combining Statistical Depth and Fermat Distance for Uncertainty Quantification

First of all, thank you for your time and for this review. Here are our answers.

Q1. How computationally expensive is LD after the improvements? faster/slower to do inference than e.g. DDU?

The computational expense depends on the number n of points in the proposed reduced LD, and the number of classes C. The complexity is of order O(Cn^2). At inference, it is slower than DDU, as DDU uses Gaussian assumption, and an empirical covariance estimation. Hence it uses simple and standard matrix linear algebra, which is friendly for standard Deep Learning packages. With our method, we use non-standard operations, making it slower. We believe that there is much room for improvement using more native implementations, more parallelization etc.. especially when computing shortest paths for LD. But we considered this as not a priority. The objective of our paper is mainly to introduce an approach that is fairly new to Deep Learning community.

Q2. What dataset size does the method start to fail?

To respond to your question, we have added an experiment on the spiral dataset where we use only a certain percentage of the original data until LD fails to capture the original distribution. Please look at the figure in the pdf file attached in the global rebuttal to observe. Please note that we randomly sample a small portion of the original points. Hence, the sampled points can be concentrated in a small region instead of being distributed along the spiral. So, the sampled points can represent not very correctly the original distribution. With that being said, it is not surprising that $LD$ fails to capture the original support at around $5-6 \%$ of the original size. We hope that the figure will give you more insight about our method at small data regime. Finally, thank you for your recommendation and we will add that in the appendix.

Q3. Consider Figure D.1. What if two of the “blobs” belong to cluster A and the last to cluster B, so that there are two classes (C=2) but in three clusters. Would LD then still behave as desired? If LD then gives undesirable results, wouldn’t you say that there is at least some assumption about the shape of the distributions?

This is a very interesting remark. In this example, we intentionally make 3 clusters very far away from each other to see the effect of our method. In the extreme scenario that you propose, there is a class with 2 clusters. One could argue that in such case, these 2 clusters should not be too distinctive. This is because the main model in trained to well classify, so semantically similar inputs should be close to each other, leading to quite continuous cluster for each class. Hence, the "bad" effect could exist but should be very minimal.But in general, we agree that the cluster of each class should be sufficiently connected to have an ideal result. We will add that in our discussion.

Q4. How would the model perform if the two moons have more spread.

In the case you are mentioning, we argue this is not a case of OoD uncertainty but a case of decision uncertainty. For this, other metrics such as predictive entropy should be a good candidate as it's related to uncertainty in the decision. OoD on the other hand deals well with data scarcity. The aim of LD is to measure the Out-of-domain uncertainty, which is due to the zones where we do not have (or very little) data. As model is not trained in these zones, we would like that the model does not predict on these zones as it can behave very randomly due to scarcity of training data in these zones. This is unlike the case where the two moons have more spread (and even overlap), so we have enough data in the zone between the 2 classes. Finally, we agree with your remark and it's worth mentioning in the discussion.

Q5. In Figures 5.2b-5.2d the accuracy seems to plateau

We think that the plateau part corresponds to "difficult" regions where InD and OOD data are less distinctive, so the rejected data could contain both InD and OOD data. Such a phenomenon is not specific to LD and appears for other methods as well. (see DUQ for example.)

Q6. One important use case I’d consider for minimally invading the training process is OoD detection with pre-trained models:

Yes! This is indeed a point we have in mind, as SOTA models become often too large to retrain ourselves. But perhaps we did not insist enough on that. It will be added in the introduction. Thank you for your recommendation. Ideally this should be a good use case where we have no idea about the distribution of data and we want to keep the original model intact to make sure that its performance on the main task is not impacted.

Kind regards, The authors

First of all, thank you for your kind review. Here are our answers.

Weaknesses

1. Related work to include papers on OOD:

Thank you for your recommendation. We will add more references on OOD in related work.

2. An additional evaluation metric:

We do appreciate your kind recommendation, which is legitimate. However, our choice of sticking to AUROC is almost forced upon us because single-forward UQ methods like DDU and DUQ, unfortunately, do not report metrics such as FPR-95. Furthermore, the references we found such as [1] (and papers it cites) deal with ECE as a metric for OOD generalization but not OOD UQ (Uncertainty Quantification) Thus, it is difficult for us to include a fair comparison with these metrics.

[1] Wald, Yoav, et al. "On calibration and out-of-domain generalization." Advances in neural information processing systems 34 (2021): 2215-2227.

3. Large scale evaluation.

See next question.

Question:

This very legitimate question has been raised by another reviewer, and we reproduce the answer for your convenience.

Regarding the complexity of evaluation, we need a trained model on InD of size N and for every OoD example, the complexity is O(C N^2). Even if this is reasonable for a single example, which is relevant for applications, this can indeed become quite large for a full scale evaluation like ImageNet as InD. We estimate that would require approximately 60 hours on our hardware for a single run, which was not possible for this rebuttal, especially multiple runs are needed. We did CIFAR100 / Tiny-ImageNet over 5 independent runs as it required approx 10 hours of experiments. And the presence of C=100 hopefully shows that the method scales well with larger dataset. To have a fair comparision, we use model Wide-ResNet-28-10 and the same training scheme as in DDU paper to train models on CIFAR100. We see that performance of our method is better or on par with strong baseline methods.

Table. AUROC score with CIFAR100 as InD data and Tiny-Imaget as OOD data. Results of other methods are extracted from paper of DDU that were experimented on the same Wide-ResNet-28-10 model.

Conclusion

Given our answers, we sincerely hope you will consider raising your score.

Kind regards, The authors

Dear TY6a. The end of the discussion period is close. I would be grateful if you provide a feedback regarding authors’ answers to your review.

First of all, thank you for your kindly insightful reviews. Here are our answer. Many aspects of the discussion will be added to the paper.

Weaknesses

W1: Two disjoints clusters for data?

Very natural question. You are perfectly right that the population (ideal) Fermat distance in Eq. (3.4) would be infinite due to vanishing density $f$. However, the sample FD would remain finite -- of the order of the distance to the power $\alpha$. The finite size effect thus stabilizes the value. In fact, Theorem 2.3 in the reference [6] proves convergence of rescaled sample FD to population FD, with rescaling $n^\beta$ with $\beta = (\alpha-1)/d$. More precisely $n^\beta D_{Q_n, \alpha}(x,y) \rightarrow D_{f, \beta}(x,y)$ when the samples $Q_n = (X_1, X_2, \dots)$ are either $n$ iid with density $f$ or Poisson with intensity $n f$. It is crucial for $f$ to remain bounded from above and away from zero. As such, one could say that in between clusters, we need “very small density” but not “zero density”. Hence connectedness.

This purely mathematical answer is rather unsatisfying. A more practical take would be to argue that if a class is disconnected, there is a problem with the feature space. We agree that a better clustering would solve the issue. But, here the clustering is given by the labeling, as we are in a supervised setting for classification. For a focus on the clustering (unsupervised), we found the reference [1] on the use of FD for clustering.

[1] Sapienza et al. "Weighted geodesic distance following Fermat's principle."

[6] Groisman et al. Nonhomogeneous euclidean first-passage percolation and distance learning.

W2: Curse of dimensionality in the convergence sample FD to population FD.

In the previous convergence extracted from [6], the scaling does indeed depend on the dimension, thus reflecting a curse of dimensionality. However, one could argue that this dependence is not too bad. Moreover [Theorem 2.7, 6] tackles the case of data living in an embedded manifold of dimension $d$, much smaller than the embedding space $\mathbb{R}^D$. In this case, only $d$ matters and not $D$. This is a nice property for ML, where it is a common belief that data lives in much smaller dimensions that raw data points.

In the end, these are sensible arguments for the lack of a curse of dimensionality in using FD.

W3. “No trainable parameter”

By "trainable param", one refers to params that are optimized (based on gradient descend for example) in the process. Here, $\alpha$ is chosen a priori and fixed during the process. And as you point out, it is not very important. Also, perhaps there is a misunderstanding, but we point out (as in W1) that the clustering is part of the data. It is given by the classes in our supervised classification problem, which we want to make more robust thanks to OOD.

W4. Focus on "non-intrusive" and "NNs", ignoring that the method applies beyond NNs.

Yes we agree with your remark. A comprehensive answer is given with the related Question 2.

W5: Section 4.5 seem like they would rather seriously break the connection between the estimated LD and the true LD

Yes your remark is correct. This could lead to some change in the original density. However, at the end, our objective is to measure how "central" a point is w.r.t. our data and only LD matters. So, our motivation for using reduced methods is to find a config of points that cover well the support of the original data. If this is the case, even if there is change in density, the change of LD is minimal and the ordering of points by LD is not really impacted. That is, points that are "central" will remain with large LD and points near the the frontier of the original support should still have small value of LD.

W6: LL ratio

In this method, instead of using directly the main model, one needs to train two supplementary generative models to estimate distributions. A first model is trained on ID data and a second one is trained on perturbed inputs. So that, the second model captures only the background statistics. Under suitable assumptions, authors show that the ratio between these two likelihoods cancels out the background information. Consequently, the LL ratio focuses on the semantic part of the input and so can be used as a score to distinguish ID from OOD data. This method needs an adequate noise in the way that the perturbed inputs contain only background information. This process itself is complicated as we need some supplementary dataset to choose the noise. Moreover, one needs to really carefully train these 2 generative models so that they can reflect the true underlying input density. This is quite complex. We will add this in the appendix.

W7: Fig 5.2 on the monotonicity.

We made the figure because similar ones appear in the literature. We agree it is not fundamental. Nevertheless, we believe that this monotonicity is a reasonable sanity/reality check, which is nice to observe.

Questions

Q1. $\alpha$ in Fig 4.1?

We used alpha=3 in this experiment and it is the same for all panels.

Q2 (and W4). Beyond NNs, and feature space? Why not raw data points?

You are perfectly right that the combination LD+FD can be used for outlier detection in a more general context than NNs. This is what we had in the mind in the very last sentence in the conclusion. We were perhaps not insisting enough in the paper.

Regarding other literature, we cited the works of Cholaquidis et al. from statistics on LD and the works of Groisman et al. from probability of FD. We are unaware of any works combining the two, aside from ours, for any outlier detection.

Regarding the use of raw data points directly, this indeed possible as in [1] for clustering. However, in the context of NNs and vision, working on pixels is not a good idea. Feature spaces are more efficient in this context as they extract the low dimensionality of the data more efficiently at a semantic level.

Kind regards

The authors

Comment on weakness

We believe that in [3], one uses GDA and not Gaussian Mixture Model (GMM). More precisely, GMM consists in calculating density for a point x as $p(x) = \sum_{i=1}^{C} w_i p_i(x)$, and so one needs to fit both $w_i$ (weight) and params $\theta_i$ of each $p_i$. (Here $\theta_i$ is the mean and covariance matrix). While, GDA consists in only fitting $\theta_i$ and then $p(x)$ is considered as $\max_{i} p_i(x)$. As both approaches lead to a mixture of gaussian, in some ML litterature, one usually confuse GDA with GMM. The most notable difference between these 2 approaches is that GMM has a smoothing effect of density value between the clusters , so larger value in these zones.

We did mention non-Gaussianity as a desirable feature of our method, as the method [1]. Yet it is not the main selling point: See Q1-Q2 below for synergies of LD+FD. We shall cite [1], but we believe that density estimation by kernels

• is not a far departure from GDA
• it does not provide a natural measure of centrality like Lens Depth
• needs bandwidth tuning

Thus instead of adding that benchmark, we chose to focus on Q4.

Answers to questions

Questions Q1-Q2. Why Lens depth vs Tuckey depth aka Half-plane depth or Simplicial depth? Fermat distance vs Typical manifold learning eg Shortest paths after local kNNs?

Thank you for these questions, which we answer jointly, in order to stress that while the choice in (1) is for convenience, the choice for (2) is more fundamental. Moreover the choice (1)+(2) is synergistic and not independent. The main idea of our method is the combination of a notion of depth or centrality w.r.t a distribution, and a measure of length that gives shorter distances for high density areas. Furthermore, it is highly desirable that the notion of depth adapts to the chosen distance.

Q1. As you relevantly point out, there are many notions of depth. And we chose not to delve on them. But indeed, it is easy to give a panorama of pros and cons:

• Tukey depth aka half-plane depth. Pros: Computationally simple, Naturally normalized. Cons: Euclidean, hence less synergy with Fermat distance. Half-place separation is very Euclidean.
• Simplicial depth. It counts the number of simplices of sample points that contain a given point. Cons: Not normalized into a probability, potentially exponential growth of number of simplices. Computationally complex / expensive as while there exists algorithms in 2D plane, it is not trivial in higher dimension.
• LD. Pros: Takes into account any distance. Normalized. Computationally middle complexity. In summary, we can structure this discussion into the table.

LD is a well-rounded choice. And among these, it is the only one which can leverage the Fermat distance. If you think this is important, we could turn this explanation into an additional paragraph in the paper.

Q2. Indeed manifold learning is the logical tool for evaluating distances in a latent space. However typical methods such as those suggested do not have this extra feature of “shorter distances in high density areas”. Indeed, in the Fermat distance, the sum $\sum |q_i - q_{i+1}|^\alpha$ is small if the q_i’s are close and alpha is high. And the idea of Fermat distance, inspired from percolation theory in statistical physics, is to use high parameter $\alpha$. This point is subtle yet important for us. Perhaps we should insist more on that.

All in all, we believe that we have made a sensible choice in combining LD for notion of depth, and Fermat for notion of distance.

Q3.

GDA method: please see our comment on weakness above. The result is a mixture of Gaussians, as illustrated in Fig. 1.1 in our main paper.

Q4. “Experiments with more complex datasets? High computational of LD + FD approach?” With being relatively lightweight, it is not clear why not to consider CIFAR-100/ImageNet as in-distribution with corresponding OOD choices.

As per the weakness you raised, we added CIFAR100 (InD) vs. TIny-ImageNet (OoD). Regarding the complexity of evaluation, we need a trained model on InD of size N and for every OoD example, the complexity is O(C N^2). Even if this is reasonable for a single example, which is relevant for applications, this can indeed become quite large for a full scale evaluation like ImageNet as InD. We estimate that would require approximately 60 hours on our hardware for a single run, which was not possible for this rebuttal, especially multiple runs are needed. We did CIFAR100 / Tiny-ImageNet over 5 independent runs as it required approx 10 hours of experiments. And the presence of C=100 hopefully shows that the method scales well with larger dataset. To have a fair comparision, we use model Wide-ResNet-28-10 and the same training scheme as in DDU paper.

Table. AUROC score with CIFAR100 as InD data and Tiny-Imaget as OOD data. Results of other methods are extracted from paper of DDU that were experimented on the same Wide-ResNet-28-10 model.

Q5. “Reduced LD on more complex dataset than MNIST?”

Yes, this was done. Indeed the results summarized in tables 5.1 and 5.2 in the paper do use reduced LD. This is mentioned in the details provided in the Appendix A “Experiment details”. And while the reduction is sizable, the results’ AUROC do not degrade. Finally, let us mention that the details of experiment CIFAR100/Tiny-Imagenet will be added to appendix.

Conclusion

Given our answers, we sincerely hope you will consider raising your score.

Kind regards, The authors

Dear exfg. The end of the discussion period is close. I would be grateful if you provide a feedback regarding authors’ answers to your review.