To Trust Or Not To Trust A Classifier

Introduction

Machine learning (ML) is a powerful and widely-used tool for making potentially important decisions, from product recommendations to medical diagnosis. However, despite ML’s impressive performance, it makes mistakes, with some more costly than others. As such, ML trust and safety is an important theme Varshney and Alemzadeh (2017); Lee and See (2004); Amodei et al. (2016). While improving overall accuracy is an important goal that the bulk of the effort in ML community has been focused on, it may not be enough: we need to also better understand the strengths and limitations of ML techniques.

This work focuses on one such challenge: knowing whether a classifier’s prediction for a test example can be trusted or not. Such trust scores have practical applications. They can be directly shown to users to help them gauge whether they should trust the AI system. This is crucial when a model’s prediction influences important decisions such as a medical diagnosis, but can also be helpful even in low-stakes scenarios such as movie recommendations. Trust scores can be used to override the classifier and send the decision to a human operator, or to prioritize decisions that human operators should be making. Trust scores are also useful for monitoring classifiers to detect distribution shifts that may mean the classifier is no longer as useful as it was when deployed. An open-source implementation of Trust Scores can be found here: https://github.com/google/TrustScore

A standard approach to deciding whether to trust a classifier’s decision is to use the classifiers’ own reported confidence or score, e.g. probabilities from the softmax layer of a neural network, distance to the separating hyperplane in support vector classification, mean class probabilities for the trees in a random forest. While using a model’s own implied confidences appears reasonable, it has been shown that the raw confidence values from a classifier are poorly calibrated (Guo et al., 2017; Kuleshov and Liang, 2015). Worse yet, even if the scores are calibrated, the ranking of the scores itself may not be reliable. In other words, a higher confidence score from the model does not necessarily imply higher probability that the classifier is correct, as shown in Provost et al. (1998); Goodfellow et al. (2014); Nguyen et al. (2015). A classifier may simply not be the best judge of its own trustworthiness.

In this paper, we use a set of labeled examples (e.g. training data or validation data) to help determine a classifier’s trustworthiness for a particular testing example. First, we propose a simple procedure that reduces the training data to a high density set for each class. Then we define the trust score—the ratio between the distance from the testing sample to the nearest class different from the predicted class and the distance to the predicted class—to determine whether to trust that classifier prediction.

Theoretically, we show that high/low trust scores correspond to high probability of agreement/disagreement with the Bayes-optimal classifier. We show finite-sample estimation rates when the data is full-dimension and supported on or near a low-dimensional manifold. Interestingly, we attain bounds that depend only on the lower manifold dimension and independent of the ambient dimension without any changes to the procedure or knowledge of the manifold. To our knowledge, these results are new and may be of independent interest.

Experimentally, we found that the trust score better identifies correctly-classified points for low and medium-dimension feature spaces than the model itself. However, high-dimensional feature spaces were more challenging, and we demonstrate that the trust score’s utility depends on the vector space used to compute the trust score differences.

Related Work

One related line of work is that of confidence calibration, which transforms classifier outputs into values that can be interpreted as probabilities, e.g. Platt (1999); Zadrozny and Elkan (2002); Niculescu-Mizil and Caruana (2005); Guo et al. (2017). In recent work, Kuleshov and Liang (2015) explore the structured prediction setting, and Lakshminarayanan et al. (2017) obtain confidence estimates by using ensembles of networks. These calibration techniques typically only use the the model’s reported score (and the softmax layer in the case of a neural network) for calibration, which notably preserves the rankings of the classifier scores. Similarly, Hendrycks and Gimpel (2016) considered using the softmax probabilities for the related problem of identifying misclassifications and mislabeled points.

Recent work explored estimating uncertainty for Bayesian neural networks and returning a distribution over the outputs (Gal and Ghahramani, 2016; Kendall and Gal, 2017). The proposed trust score does not change the network structure (nor does it assume any structure) and gives a single score, rather than a distribution over outputs as the representation of uncertainty.

The problem of classification with a reject option or learning with abstention Bartlett and Wegkamp (2008); Yuan and Wegkamp (2010); Cortes et al. (2016b); Grandvalet et al. (2009); Cortes et al. (2016a); Herbei and Wegkamp (2006); Cortes et al. (2017) is a highly related framework where the classifier is allowed to abstain from making a prediction at a certain cost. Typically such methods jointly learn the classifier and the rejection function. Note that the interplay between classification rate and reject rate is studied in many various forms e.g. (Chow, 1970; Dubuisson and Masson, 1993; Fumera et al., 2000; Santos-Pereira and Pires, 2005; Tortorella, 2000; Fumera and Roli, 2002; Landgrebe et al., 2006; El-Yaniv and Wiener, 2010; Wiener and El-Yaniv, 2011; Tax and Duin, 2008). Our paper assumes an already trained and possibly black-box classifier and learns the confidence scores separately, but we do not explicitly learn the appropriate rejection thresholds.

Whether to trust a classifier also arises in the setting where one has access to a sequence of classifiers, but there is some cost to evaluating each classifier, and the goal is to decide after evaluating each classifier in the sequence if one should trust the current classifier decision enough to stop, rather than evaluating more classifiers in the sequence (e.g. Wang et al. (2015); Parrish et al. (2013); Fan et al. (2002)). Those confidence decisions are usually based on whether the current classifier score will match the classification of the full sequence.

Experimentally we find that the vector space used to compute the distances in the trust score matters, and that computing trust scores on more-processed layers of a deep model generally works better. This observation is similar to the work of Papernot and McDaniel Papernot and McDaniel (2018), who use $k$-NN regression on the intermediate representations of the network which they showed enhances robustness to adversarial attacks and leads to better calibrated uncertainty estimations.

Our work builds on recent results in topological data analysis. Our method to filter low-density points estimates a particular density level-set given a parameter $\alpha$, which aims at finding the level-set that contains $1-\alpha$ fraction of the probability mass. Level-set estimation has a long history Hartigan (1975); Ester et al. (1996); Tsybakov et al. (1997); Singh et al. (2009); Rigollet et al. (2009); Jiang (2017a). However such works assume knowledge of the density level, which is difficult to determine in practice. We provide rates for Algorithm 1 in estimating the appropriate level-set corresponding to $\alpha$ without knowledge of the level. The proxy $\alpha$ offers a more intuitive parameter compared to the density value, is used for level-set estimation. Our analysis is also done under various settings including when the data lies near a lower dimensional manifold and we provide rates that depend only on the lower dimension.

Algorithm: The Trust Score

Our approach proceeds in two steps outlined in Algorithm 1 and 2. We first pre-process the training data, as described in Algorithm 1, to find the $\alpha$-high-density-set of each class, which is defined as the training samples within that class after filtering out $\alpha$-fraction of the samples with lowest density (which may be outliers):

In order to approximate the $\alpha$-high-density-set, Algorithm 1 filters the $\alpha$-fraction of the sample points with lowest empirical density, based on $k$-nearest neighbors. This data filtering step is independent of the given classifier $h$.

Then, the second step: given a testing sample, we define its trust score to be the ratio between the distance from the testing sample to the $\alpha$-high-density-set of the nearest class different from the predicted class, and the distance from the test sample to the $\alpha$-high-density-set of the class predicted by $h$, as detailed in Algorithm 2. The intuition is that if the classifier $h$ predicts a label that is considerably farther than the closest label, then this is a warning that the classifier may be making a mistake.

Our procedure can thus be viewed as a comparison to a modified nearest-neighbor classifier, where the modification lies in the initial filtering of points not in the $\alpha$-high-density-set for each class.

The distances can be computed with respect to any representation of the data. For example, the raw inputs, an unsupervised embedding of the space, or the activations of the intermediate representations of the classifier. Moreover, the nearest-neighbor distance can be replaced by other distance measures, such as $k$-nearest neighbors or distance to a centroid.

The method has two hyperparameters: $k$ (the number of neighbors, such as in $k$-NN) and $\alpha$ (fraction of data to filter) to compute the empirical densities. We show in theory that $k$ can lie in a wide range and still give us the desired consistency guarantees. Throughout our experiments, we fix $k=10$, and use cross-validation to select $\alpha$ as it is data-dependent.

We observed that the procedure was not very sensitive to the choice of $k$ and $\alpha$. As will be shown in the experimental section, for efficiency on larger datasets, we skipped the initial filtering step of Algorithm 1 (leading to a hyperparameter-free procedure) and obtained reasonable results. This initial filtering step can also be replaced by other strategies. One such example is filtering examples whose labels have high disagreement amongst its neighbors, which is implemented in the open-source code release but not experimented with here.

Theoretical Analysis

In this section, we provide theoretical guarantees for Algorithms 1 and 2. Due to space constraints, all the proofs are deferred to the Appendix. To simplify the main text, we state our results treating $\delta$, the confidence level, as a constant. The dependence on $\delta$ in the rates is made explicit in the Appendix.

We then analyze Algorithm 2, and establish the culminating result of Theorem 4: for labeled data distributions with well-behaved class margins, when the trust score is large, the classifier likely agrees with the Bayes-optimal classifier, and when the trust score is small, the classifier likely disagrees with the Bayes-optimal classifier. If it turns out that even the Bayes-optimal classifier has high-error in a certain region, then any classifier will have difficulties in that region. Thus, Theorem 4 does not guarantee that the trust score can predict misclassification, but rather that it can predict when the classifier is making an unreasonable decision.

We require the following regularity assumptions on the boundaries of $H_{\alpha}(f)$, which are standard in analyses of level-set estimation Singh et al. (2009). Assumption 1.1 ensures that the density around $H_{\alpha}(f)$ has both smoothness and curvature. The upper bound gives smoothness, which is important to ensure that our density estimators are accurate for our analysis (we only require this smoothness near the boundaries and not globally). The lower bound ensures curvature: this ensures that $H_{\alpha}(f)$ is salient enough to be estimated. Assumption 1.2 ensures that $H_{\alpha}(f)$ does not get arbitrarily thin anywhere.

Let $\beta>0$. There exists $\check{C}_{\beta},\hat{C}_{\beta},\beta,r_{c},r_{0},\rho>0$ s.t.

$\check{C}_{\beta}\cdot d(x,H_{\alpha}(f))^{\beta}\leq|\lambda_{\alpha}-f(x)|\leq\hat{C}_{\beta}\cdot d(x,H_{\alpha}(f))^{\beta}$ for all $x\in\partial H_{\alpha}(f)+B(0,r_{c})$.

For all $0<r<r_{0}$ and $x\in H_{\alpha}(f)$, we have $\text{Vol}(B(x,r))\geq\rho\cdot r^{D}$.

where $\partial A$ denotes the boundary of a set $A$, $d(x,A):=\inf_{x^{\prime}\in A}||x-x^{\prime}||$, $B(x,r):=\{x^{\prime}:|x-x^{\prime}|\leq r\}$ and $A+B(0,r):=\{x:d(x,A)\leq r\}$.

Our statistical guarantees are under the Hausdorff metric, which ensures a uniform guarantee over our estimator: it is a stronger notion of consistency than other common metrics Rigollet et al. (2009); Rinaldo and Wasserman (2010).

$d_{H}(A,B):=\max\{\sup_{x\in A}d(x,B),\sup_{x\in B}d(x,A)\}$.

We now give the following result for Algorithm 1. It says that as long as our density function satisfies the regularity assumptions stated earlier, and the parameter $k$ lies within a certain range, then we can bound the Hausdorff distance between what Algorithm 1 recovers and $H_{\alpha}(f)$, the true $\alpha$-high-density set, from an i.i.d. sample drawn from $f$ of size $n$. Then, as $n$ goes to $\infty$, and $k$ grows as a function of $n$, the quantity goes to .

The condition on $k$ can be simplified by ignoring log factors: $\log n\lesssim k\lesssim n^{2\beta/(2\beta+D)}$, which is a wide range. Setting $k$ to its allowed upper bound, we obtain our consistency guarantee of

The first term is due to the error from estimating the appropriate level given $\alpha$ (i.e. identifying the level $\lambda_{\alpha}$) and the second term corresponds to the error for recovering the level set given knowledge of the level. The latter term matches the lower bound for level-set estimation up to log factors Tsybakov et al. (1997).

2 Analysis of Algorithm 1 on Manifolds

One of the disadvantages of Theorem 1 is that the estimation errors have a dependence on $D$, the dimension of the data, which may be highly undesirable in high-dimensional settings. We next improve these rates when the data has a lower intrinsic dimension. Interestingly, we are able to show rates that depend only on the intrinsic dimension of the data, without explicit knowledge of that dimension nor any changes to the procedure. As common to related work in the manifold setting, we make the following regularity assumptions which are standard among works in manifold learning (e.g. (Niyogi et al., 2008; Genovese et al., 2012; Balakrishnan et al., 2013)).

Let $0<\delta<1$. Suppose that density function $f$ is continuous and supported on $M$ and Assumptions 1 and 2 hold. Suppose also that there exists $\lambda_{0}>0$ such that $f(x)\geq\lambda_{0}$ for all $x\in M$. Then, there exists constants $C_{l},C_{u},C>0$ depending on $f$ and $\delta$ such that the following holds with probability at least $1-\delta$. Suppose that $k$ satisfies $C_{l}\cdot\log n\leq k\leq C_{u}\cdot(\log n)^{d(2\beta^{\prime}+d)}\cdot n^{2\beta^{\prime}/(2\beta^{\prime}+d)}$. where $\beta^{\prime}:=\max\{1,\beta\}$. Then we have

Setting $k$ to its allowed upper bound, we obtain (ignoring log factors),

The first term can be compared to that of the previous result where $D$ is replaced with $d$. The second term is the error for recovering the level set on manifolds, which matches recent rates Jiang (2017a).

3 Analysis of Algorithm 1 on Manifolds with Full Dimensional Noise

In realistic settings, the data may not lie exactly on a low-dimensional manifold, but near one. We next present a result where the data is distributed along a manifold with additional full-dimensional noise. We make mild assumptions on the noise distribution. Thus, in this situation, the data has intrinsic dimension equal to the ambient dimension. Interestingly, we are still able to show that the rates only depend on the dimension of the manifold and not the dimension of the entire data.

The above result is compelling because it shows why our methods can work, even in high-dimensions, despite the curse of dimensionality of non-parametric methods. In typical real-world data, even if the data lies in a high-dimensional space, there may be far fewer degrees of freedom. Thus, our theoretical results suggest that when this is true, then our methods will enjoy far better convergence rates – even when the data overall has full intrinsic dimension due to factors such as noise.

4 Analysis of Algorithm 2: the Trust Score

We now provide a guarantee about the trust score, making the same assumptions as in Theorem 3 for each of the label distributions. We additionally assume that the class distributions are well-behaved in the following sense: that high-density-regions for each of the classes satisfy the property that for any point $x\in\mathcal{X}$, if the ratio of the distance to one class’s high-density-region to that of another is smaller by some margin $\gamma$, then it is more likely that $x$’s label corresponds to the former class.

Experiments

In this section, we empirically test whether trust scores can both detect examples that are incorrectly classified with high precision and be used as a signal to determine which examples are likely correctly classified. We perform this evaluation across (i) different datasets (Sections 5.1 and 5.3), (ii) different families of classifiers (neural network, random forest and logistic regression) (Section 5.1), (iii) classifiers with varying accuracy on the same task (Section 5.2) and (iv) different representations of the data e.g. input data or activations of various intermediate layers in neural network (Section 5.3).

First, we test if testing examples with high trust score corresponds to examples in which the model is correct ("identifying trustworthy examples"). Each method produces a numeric score for each testing example. For each method, we bin the data points by percentile value of the score (i.e. 100 bins). Given a recall percentile level (i.e. the $x$-axis on our plots), we take the performance of the classifier on the bins above the percentile level as the precision (i.e. the $y$-axis). Then, we take the negative of each signal and test if low trust score corresponds to the model being wrong ("identifying suspicious examples"). Here the $y$-axis is the misclassification rate and the $x$-axis corresponds to decreasing trust score or model confidence.

In both cases, the higher the precision vs percentile curve, the better the method. The vertical black dotted lines in the plots represent the omniscient ideal. For identifying trustworthy examples it is the error rate of the classifier and for identifying suspicious examples" it is the accuracy rate.

The baseline we use in Section is the model’s own confidence score, which is similar to the approach of Hendrycks and Gimpel (2016). While calibrating the classifiers’ confidence scores (i.e. transforming them into probability estimates of correctness) is an important related work Guo et al. (2017); Platt (1999), such techniques typically do not change the rankings of the score, at least in the binary case. Since we evaluate the trust score on its precision at a given recall percentile level, we are interested in the relative ranking of the scores rather than their absolute values. Thus, we do not compare against calibration techniques. There are surprisingly few methods aimed at identifying correctly or incorrectly classified examples with precision at a recall percentile level as noted in Hendrycks and Gimpel (2016).

Choosing Hyperparameters: The two hyperparameters for the trust score are $\alpha$ and $k$. Throughout the experiments, we fix $k=10$ and choose $\alpha$ using cross-validation over (negative) powers of $2$ on the training set. The metric for cross-validation was optimal performance on detecting suspicious examples at the percentile corresponding to the classifier’s accuracy. The bulk of the computational cost for the trust-score is in $k$-nearest neighbor computations for training and $1$-nearest neighbor searches for evaluation. To speed things up for the larger datasets MNIST, SVHN, CIFAR-10 and CIFAR-100, we skipped the initial filtering step of Algorithm 1 altogether and reduced the intermediate layers down to $20$ dimensions using PCA before being processed by the trust score which showed similar performance. We note that any approximation method (such as approximate instead of exact nearest neighbors) could have been used instead.

In this section, we show performance on five benchmark UCI datasets Friedman et al. (2001), each for three kinds of classifiers (neural network, random forest and logistic regression). Due to space, we only show two data sets and two models in Figure 1. The rest can be found in the Appendix. For each method and dataset, we evaluated with multiple runs. For each run we took a random stratified split of the dataset into two halves. One portion was used for training the trust score and the other was used for evaluation and the standard error is shown in addition to the average precision across the runs at each percentile level. The results show that our method consistently has a higher precision vs percentile curve than the rest of the methods across the datasets and models. This suggests the trust score considerably improves upon known methods as a signal for identifying trustworthy and suspicious testing examples for low-dimensional data.

In addition to the model’s own confidence score, we try one additional baseline, which we call the nearest neighbor ratio (1-nn ratio). It is the ratio between the 1-nearest neighbor distance to the closest and second closest class, which can be viewed as an analogue to the trust score without knowledge of the classifier’s hard prediction.

2 Performance as Model Accuracy Varies

In Figure 2, we show how the performance of trust score changes as the accuracy of the classifier changes (averaged over 20 runs for each condition). We observe that as the accuracy of the model increases, while the trust score still performs better than model confidence, the amount of improvement diminishes. This suggests that as the model improves, the information trust score can provide in addition to the model confidence decreases. However, as we show in Section 5.3, the trust score can still have added value even when the classifier is known to be of high performance on some benchmark larger-scale datasets.

3 Performance on MNIST, SVHN, CIFAR-10 and CIFAR-100 Datasets

The MNIST handwritten digit dataset LeCun (1998) consists of 60,000 28$\times$28-pixel training images and 10,000 testing images in 10 classes. The SVHN dataset Netzer et al. (2011) consists of 73,257 32$\times$32-pixel colour training images and 26,032 testing images and also has 10 classes. The CIFAR-10 and CIFAR-100 datasets Krizhevsky (2009) both consist of 60,000 32$\times$32-pixel colour images, with 50,000 training images and 10,000 test images. The CIFAR-10 and CIFAR-100 datasets are split evenly between 10 classes and 100 classes respectively.

We used a pretrained VGG-16 Simonyan and Zisserman (2014) architecture with adaptation to the CIFAR datasets based on Liu and Deng (2015). The CIFAR-10 VGG-16 network achieves a test accuracy of 93.56% while the CIFAR-100 network achieves a test accuracy of 70.48%. We used pretrained, smaller CNNs for MNIST and SVHN. The MNIST network achieves a test accuracy of 99.07% and the SVHN network achieves a test accuracy of 95.45%. All architectures were implemented in Keras Chollet et al. (2015).

One simple generalization of our method is to use intermediate layers of a neural network as an input instead of the raw $x$. Many prior work suggests that a neural network may learn different representations of $x$ at each layer. As input to the trust score, we tried using 1) the logit layer, 2) the preceding fully connected layer with ReLU activation, 3) this fully connected layer, which has 128 dimensions in the MNIST network and 512 dimensions in the other networks, reduced down to 20 dimensions from applying PCA.

The trust score results on various layers are shown in Figure 3. They suggest that for high dimensional datasets, the trust score may only provide little or no improvement over the model confidence at detecting trustworthy and suspicious examples. All plots were made using $\alpha=0$; using cross-validation to select a different $\alpha$ did not improve trust score performance. We also did not see much difference from using different layers.

In this paper, we provide the trust score: a new, simple, and effective way to judge if one should trust the prediction from a classifier. The trust score provides information about the relative positions of the datapoints, which may be lost in common approaches such as the model confidence when the model is trained using SGD. We show high-probability non-asymptotic statistical guarantees that high (low) trust scores correspond to agreement (disagreement) with the Bayes-optimal classifier under various nonparametric settings, which build on recent results in topological data analysis. Our empirical results across many datasets, classifiers, and representations of the data show that our method consistently outperforms the classifier’s own reported confidence in identifying trustworthy and suspicious examples in low to mid dimensional datasets. The theoretical and empirical results suggest that this approach may have important practical implications in low to mid dimension settings.

References

Appendix A Supporting results for Theorem 1 Proof

We need the following result giving guarantees on the empirical balls.

where $C_{\delta,n}=16\log(2/\delta)\sqrt{D\log n}$

For the rest of the paper, many results are qualified to hold with probability at least $1-\delta$. This is precisely the event in which Lemma 1 holds.

If $\delta=1/n$, then $C_{\delta,n}=O((\log n)^{3/2})$.

To analyze Algorithm 1, we use the $k$-NN density estimatorDevroye et al. (1994), defined below.

We will use bounds on the $k$-NN density estimator from Dasgupta and Kpotufe (2014), which are repeated here.

Define the following one-sided modulus of continuity which characterizes how much the density increases locally:

provided $k$ satisfies $v_{D}\cdot\hat{r}(x,\epsilon)^{D}\cdot(f(x)+\epsilon)\geq\frac{k}{n}+C_{\delta,n}\frac{\sqrt{k}}{n}$.

Analogously, define the following which characterizes how much the density decreases locally:

provided $k$ satisfies $v_{D}\cdot\check{r}(x,\epsilon)^{D}\cdot(f(x)-\epsilon)\geq\frac{k}{n}-C_{\delta,n}\frac{\sqrt{k}}{n}$.

Appendix B Proof of Theorem 1

In this section, we assume the conditions of Theorem 1. We first show that $\lambda_{\alpha}$, that is the density level corresponding to the $\alpha$-high-density-set, is smooth in $\alpha$.

There exists constants $C_{1},r_{1}>0$ depending on $f$ such that the following holds for all $0<\epsilon<r_{1}$ such that

where the first equality holds by definition. Choosing $\epsilon$ sufficiently small such that Assumption 1 holds, we have

and the result for the first part follows by taking $C_{1}\leq\widehat{C}_{\beta}\cdot(\lambda_{\alpha-r_{1}}\cdot C^{\prime})^{-\beta/D}$ and $r_{1}<\alpha$. Showing that $0<\lambda_{\alpha+\epsilon}-\lambda_{\alpha}\leq C_{1}\epsilon^{\beta/D}$ can be done analogously and is omitted here. ∎

The next result gets a handle on the density level corresponding to $\alpha$ returned by Algorithm 1.

Let $0<\delta<1$. Let $\widehat{\varepsilon}$ be the $\varepsilon$ setting chosen by Algorithm 1. Define

Then, with probability at least $1-\delta$, we have there exist constant $C_{1}>0$ depending on $f$ such that for $n$ sufficiently large depending on $f$, we have

Then it follows that choosing $\alpha_{U}:=\alpha+C^{\prime}\sqrt{\frac{\log(1/\delta)}{n}}$ we get

Similarly, choosing $\alpha_{L}=\alpha-C^{\prime}\sqrt{\frac{\log(1/\delta)}{n}}$ gives us

where $\epsilon>0$ will be chosen later in order for $\widehat{H_{\alpha}}(f)\subseteq H^{upper}_{\alpha}(f)$. By Lemma 4, there exists $C_{2},r_{1}>0$ depending on $f$ such that for $\widehat{\varepsilon}<r_{1}$ (which holds for $n$ sufficiently large depending on $f$ by Lemma 1), we have $\lambda_{\alpha}-C_{2}\left(\sqrt{\frac{\log(1/\delta)}{n}}\right)^{\beta/D}\leq\lambda_{\alpha_{L}}$. As such, it suffices to choose $\epsilon$ such that for all $x\in\mathcal{X}$ such that if $f(x)\geq\lambda_{\alpha}-C_{2}\left(\sqrt{\frac{\log(1/\delta)}{n}}\right)^{\beta/D}$ then $f_{k}(x)\geq\lambda_{\alpha}-\epsilon$. This is because $\{x\in X:f_{k}(x)\geq\lambda_{\alpha}-\epsilon\}$ would contain $H_{\alpha_{L}}(f)\cap X$, which we showed earlier contains at least $1-\alpha$ fraction of the samples. Define $\epsilon_{0}$ such that $\epsilon=C_{2}\left(\sqrt{\frac{\log(1/\delta)}{n}}\right)^{\beta/D}+\epsilon_{0}$ We have by Assumption 1,

Then, there exists constant $C^{\prime\prime}>0$ sufficiently large depending on $f$ such that if

then the conditions in Lemma 3 are satisfied for $n$ sufficiently large. Thus, we have for all $x\in\mathcal{X}$ with $f(x)\geq\alpha-C_{2}\left(\sqrt{\frac{\log(1/\delta)}{n}}\right)^{\beta/D}$, then $f_{k}(x)\geq\alpha-\epsilon$. Hence, $\widehat{H_{\alpha}}(f)\subseteq H^{upper}_{\alpha}(f)$.

We now do the same in the other direction. Define

where $\epsilon$ will be chosen such that $H^{lower}_{\alpha}(f)\subseteq\widehat{H_{\alpha}}(f)$. By Lemma 4, it suffices to show that if $f_{k}(x)\geq\lambda_{\alpha}+\epsilon$ then $f(x)\geq\lambda_{\alpha}+C_{2}\left(\sqrt{\frac{\log(1/\delta)}{n}}\right)^{\beta/D}$. This direction follows a similar argument as the previous.

Thus, there exists a constant $C_{1}>0$ depending on $f$ such that for $n$ sufficiently large depending on $f$, we have:

The next result bounds $\widehat{H_{\alpha}}(f)$ between two level sets of $f$.

Let $0<\delta<1$. There exists constant $C_{1}>0$ depending on $f$ such that the following holds with probability at least $1-\delta$ for $n$ sufficiently large depending on $f$. Define

To simplify notation, let us define the following:

By Lemma 5, there exists $C_{2}>0$ such that defining

It suffices to show that there exists a constant $C_{1}>0$ such that

We start by showing $H^{L}_{\alpha}(f)\cap X\subseteq\widehat{H^{L}}_{\alpha}(f)$. To do this, show that for any $x\in\mathcal{X}$ satisfying $f(x)\geq\lambda_{\alpha}+C_{1}\cdot K(n,k,\delta)+\epsilon$ satisfies $f_{k}(x)\geq\lambda_{\alpha}+C_{1}\cdot K(n,k,\delta)$, where $\epsilon>0$ will be chosen later. By a similar argument as in the proof of Lemma 5, we can choose $\epsilon\geq C^{\prime}\cdot K(n,k,\delta)$ for some constant $C^{\prime}>0$ and the desired result holds for $n$ sufficiently large. Similarly, there exists $C^{\prime\prime}>0$ such that $f_{k}(x)\leq\lambda_{\alpha}-(C_{1}+C^{\prime\prime})\cdot K(n,k,\delta)$ implies that $f(x)\leq\lambda_{\alpha}-C_{1}\cdot K(n,k,\delta)$. The result follows by taking $C_{2}=C_{1}+\max\{C^{\prime},C^{\prime\prime}\}$. ∎

We are now ready to prove Theorem 5, a more general version of Theorem 1 which makes the dependence on $\delta$ explicit. Note that if $\delta=1/n$, then $\log(1/\delta)=\log(n)$.

Again, to simplify notation, let us define the following:

There are two directions to show for the Hausdorff distance result. That (i) $\max_{x\in\widehat{H_{\alpha}}(f)}d(x,H_{\alpha}(f))$ is bounded, that is none of the high-density points recovered by Algorithm 1 are far from the true high-density region; and (ii) that $\sup_{x\in H_{\alpha}(f)}d(x,\widehat{H_{\alpha}}(f))$ is bounded, that Algorithm 1 recovers a good covering of the entire high-density region.

We first show (i). By Lemma 6, we have that there exists $C_{1}>0$ such that

contains $\widehat{H_{\alpha}}(f)$. Thus,

where the second inequality holds by Assumption 1. Now for the other direction, we have by triangle inequality that

The first term can be bounded by using Assumption 1:

Now for the second term, we see that by Lemma 6, $\widehat{H_{\alpha}}(f)$ contains all of the sample points of $H^{L}_{\alpha}(f)$. Thus, we have

By Assumption 1, for $r<r_{0}$, and $x\in H^{L}_{\alpha}(f)$ we have $\mathcal{F}(B(x,r))\geq\rho r^{D}$, where $\mathcal{F}$ is the distribution corresponding to $f$. Choosing $r\geq\left(\frac{C_{\delta,n}}{\rho}\frac{\sqrt{D\log n}}{n}\right)^{1/D}$ gives us that by Lemma 1 that $\mathcal{F}_{n}(B(x,r))>0$ where $\mathcal{F}_{n}$ is the distribution of $X$ and thus, we have

which is dominated by the error contributed by the other error and the result follows. ∎

Appendix C Supporting results for Theorem 2 Proof

In this section, we note that we will reuse some notation from the last section for the manifold case.

Let $\mathcal{F}$ be the true distribution and $\mathcal{F}_{n}$ be the empirical distribution w.r.t. sample $X$. Let $\mathcal{N}$ be a minimal fixed set such that each point in $M$ is at most distance $1/n$ from some point in $\mathcal{N}$. There exists a universal constant $C_{0}$ such that the following holds with probability at least $1-\delta$. For all $x\in X\cup\mathcal{N}$,

where $C_{\delta,n}=C_{0}\log(2/\delta)\sqrt{d\log n}$, $\mathcal{F}_{n}$ is the empirical distribution, and $k\geq C_{\delta,n}$.

Define the following which charaterizes how much the density increases locally in $M$:

Fix $\lambda_{0}>0$ and $\delta>0$ and suppose that $k\geq C_{\delta,n}^{2}$. Then there exists constant $C_{1}\equiv C_{1}(\lambda_{0},d,\tau)$ such that if

then the following holds with probability at least $1-\delta$ uniformly in $\epsilon>0$ and $x\in X$ with $f(x)+\epsilon\geq\lambda_{0}$:

provided $k$ satisfies $v_{d}\cdot\hat{r}(\epsilon,x)^{d}\cdot(f(x)+\epsilon)\geq\frac{k}{n}-C_{\delta,n}\frac{\sqrt{k}}{n}$.

Define the following which charaterizes how much the density decreases locally in $M$:

Fix $\lambda_{0}>0$ and $0<\delta<1$ and suppose $k\geq C_{\delta,n}$. Then there exists constant $C_{2}\equiv C_{2}(\lambda_{0},d,\tau)$ such that if

then with probability at least $1-\delta$, the following holds uniformly for all $\epsilon>0$ and $x\in X$ with $f(x)-\epsilon\geq\lambda_{0}$:

provided $k$ satisfies $v_{d}\cdot\check{r}(\epsilon,x)^{d}\cdot(f(x)-\epsilon)\geq\frac{4}{3}\left(\frac{k}{n}+C_{\delta,n}\frac{\sqrt{k}}{n}\right)$.

Appendix D Proof of Theorem 2

The proof essentially follows the same structure as the full-dimensional case, with the primary difference in the density estimation bounds.

There exists constants $C_{1},r_{1}>0$ depending on $f$ such that the following holds for all $0<\epsilon<r_{1}$ such that

The proof follows the same structure as the proof of Lemma 4, with the difference being the change in dimension, and is omitted here. ∎

Let $0<\delta<1$. Let $\widehat{\varepsilon}$ be the $\varepsilon$ setting chosen by Algorithm 1 after the binary search procedure. Define

Then, with probability at least $1-\delta$, we have there exist constant $C_{1}>0$ depending on $f$ and $M$ such that for $n$ sufficiently large depending on $f$ and $M$, we have

The proof is essentially the same as that of Lemma 5. The only difference is that instead of applying the full-dimensional versions of the uniform $k$-NN density estimate bounds (Lemma 2 and 3), we instead apply the manifold analogues (Lemma 8 and 9). Asides from constant factors, the major difference is in the allowable range for $k$. In the full-dimensional case, we only need $k\lesssim n^{2\beta/(2\beta+d)}$ for the density estimation bounds to hold. However, here we require $k\lesssim\min\{n^{2/(2+d)},n^{2\beta/(2\beta+d)}\}=n^{2\max\{1,\beta\}/(2\beta^{\prime}+d)}$. ∎

Let $0<\delta<1$. There exists constant $C_{1}>0$ depending on $f$ and $M$ such that the following holds with probability at least $1-\delta$ for $n$ sufficiently large depending on $f$ and $M$. Define

Same comment as the proof for Lemma 11. ∎

[Extends Theorem 2] Let $0<\delta<1$. Suppose that density function $f$ is continuous and supported on $M$ and Assumptions 1 and 2 hold. Suppose also that there exists $\lambda_{0}>0$ such that $f(x)\geq\lambda_{0}$ for all $x\in M$. Then, there exists constants $C_{l},C_{u},C>0$ depending on $f$ such that the following holds with probability at least $1-\delta$. Suppose that $k$ satisfies,

where $\beta^{\prime}:=\max\{1,\beta\}$. Then we have

Proof is the same as the full-dimensional case given the contributed Lemmas of this section and is omitted here. ∎

Appendix E Supporting Results for Theorem 3 Proof

Next, we need the following on the volume of the intersection of the Euclidean ball and $M$; this is required to get a handle on the true mass of the ball under $\mathcal{F}_{M}$ in later arguments. The upper and lower bounds follow from Chazal (2013) and Lemma 5.3 of Niyogi et al. (2008). The proof can be found e.g. in Jiang (2017a).

If $0<r<\min\{\tau/4d,1/\tau\}$, and $x\in M$ then

The next is a bound uniform convergence of balls:

where $\beta_{n}=8d\log(1/\delta)\sqrt{\log n/n}$.

Appendix F Proof of Theorem 3

The first result says that within the manifold, the vast majority of the probability mass is attributed to the manifold distributions.

There exists $C_{1},r_{1}>0$ depending on $\mathcal{F}_{M},\mathcal{F}_{E},M$ such that the following holds uniformly over $x\in M$ and $0<r<r_{1}$.

where the second inequality holds by Lemma 13 for $r$ sufficiently small. On the other hand, we have

Thus, we have there exists $C_{1}>0$ depending on $f_{M}$, $M$, and $f_{E}$ such that

We next show that points far away from $H_{\widetilde{\alpha}}(f_{M})$ do not get selected as high-density points by Algorithm 1.

There exists $\omega_{0}>0$ such that for any $0<\omega<\omega_{0}$ and $n$ sufficiently large depending on $\mathcal{F}_{M},\mathcal{F}_{E},M$ and $\omega$, with probability at least $1-\delta$, Algorithm 1 will not select any points outside of $H_{\widetilde{\alpha}-\omega}(f_{M})$.

By Assumption 1, we can choose $\omega$ sufficiently small so that for the density $f_{M}$, $|\lambda_{\widetilde{\alpha}-\omega}-\lambda_{\widetilde{\alpha}}|\leq\check{C}_{\beta}\cdot(r_{c}/3)^{\beta}$. Then, at the $(\widetilde{\alpha}-\omega)$-density level, we will be within the area where the regularity assumptions hold.

Next, by Hoeffding’s inequality, we have that there exist constant $C^{\prime}>0$ such that for $\bar{\alpha}>0$:

Choosing $\bar{\alpha}=\alpha-C^{\prime}\sqrt{\frac{\log(1/\delta)}{n}}$, then it follows that with probability at least $1-\delta/3$,

satisfies $|H_{0}\cap X|>(1-\alpha)\cdot n$. Next let

Let $r$ be the value of $\varepsilon$ used by Algorithm 1. Now, it suffices to show that for $n$ sufficiently large depending on $f_{M}$:

where $\mathcal{F}_{n}$ is the empirical distribution. This is because Algorithm 1 filters out sample points whose $\varepsilon$-ball has less than $k$ sample points for its final $\varepsilon$ value, which is the value which allows it to filter $\alpha$-fraction of the points.

where $\mathcal{F}_{M,n}(A)$ denote the fraction of samples drawn from $\mathcal{F}_{M}$ which lie in $A$ w.r.t. our entire sample $X$.

Then, by Lemma 14, it will be enough to show that

where $\beta_{n}=8d\log(1/\delta)\sqrt{\log n/n}$.

for some $C_{2},C_{3}>0$ and $\iota$ is the modulus of continuity, that is $\iota(f_{M},r):=\sup_{x,x^{\prime}\in M:|x-x^{\prime}|\leq r}|f_{M}(x)-f_{M}(x^{\prime})|$ (i.e. $f_{M}$ is uniformly continuous since it is continuous over a compact support, so $\iota(f_{M},r)\rightarrow 0$ as $r\rightarrow 0$).

Similarly, for the RHS, we can show for some constants $C_{4},C_{5}$ that

The result follows since $r\rightarrow 0$ as $n\rightarrow\infty$ (since by Lemma 1, $r$ is a $k$-NN radius so $r\lesssim(k/n)^{1/D}\rightarrow 0$ given the conditions on $k$ of Theorem 3) and the fact that $\lambda_{\widetilde{\alpha}-\omega}<\lambda_{\widetilde{\alpha}-C^{\prime}\sqrt{\log(1/\delta)}/\sqrt{n}}$ for $n$ sufficiently large. As desired. ∎

where the former is simply the $k$-NN radius we’ve been using thus far and the latter is the $k$-NN radius if we were to restrict the samples to only those that came from $M$. Then likewise, define the analogous density estimators:

where again, the former is the usual $k$-NN density estimator on manifolds. Then, there exists $C_{1}$ such that the following holds with high probability.

By Lemma 14, there exists $C_{2}>0$ depending on $\mathcal{F}$ and $\mathcal{F}_{M}$ such that

where $\mathcal{F}_{M,n}$ is the empirical distribution w.r.t. $X\cap M$. Next, by Lemma 15, we have for some constant $C_{3}>0$:

where the second last inequality holds for some constant $C_{4}>0$ by Lemma 7 and $C_{5}>0$ is some constant depending on $\mathcal{F}$ and $\mathcal{F}_{M}$ and $M$. Then it follows that for some constant $C_{6}>0$, we have

In the other direction, we trivially have $\widetilde{r_{k}}(x)\geq r_{k}(x)$, so

where $\beta^{\prime}:=\max\{1,\beta\}$. Then we have

The proof follows in a similar way as that of Theorem 6, except with the complexity of having added full-dimensional noise. We will only highlight the difference and provide a sketch of the proof here.

Lemma 16 and 17 give us a handle on the additional complexity when having separate noise distribution, compared to the earlier manifold setting of Theorem 2.

Lemma 16 guarantees that the points in $\widehat{H_{\alpha}}$ lie in the inside of $M$ with margin. In particular, that means the noise points are filtered out by the algorithm and thus, we are reduced to reasoning about the $\widetilde{\alpha}$-high-density-set of $f_{M}$.

Then, Lemma 17 ensures that the $k$-NN density estimator used for our analysis for the entire sample $X$ is actually quite close to the $k$-NN density estimator with respect to $M\cap X$ within $M$. In other words, we can use the $k$-NN density estimator to estimate $f_{M}$ without knowing which samples of $X$ were in $M$. Lemma 17 shows that the additional error in density estimation we obtain is $\approx(k/n)^{D/d-1}\lesssim(k/n)^{1/d}\lesssim(\log n)/\sqrt{k}$, where the first inequality holds since $D>d$ and the latter holds from the conditions on $k$. It turns out that this error term can be absorbed as a constant in the previous result of Theorem 6. ∎

Appendix G Proof of Theorem 4

where the first inequality holds by Theorem 3. This, along with the condition on $\gamma$ and $\varepsilon(h,x)$ fromo the theorem statement, implies that

which implies that $h(x)\neq h^{*}(x)$. For the second inequality, we have

where the first inequality holds by Theorem 3. Thus, if the condition of the theorem statement holds, then

for all $c\neq h(x)$, which implies that $h(x)=h^{*}(x)$ ∎

Appendix H Additional UCI Experiments

H.2 When to not trust: Precision for misclassification predictions by percentile

H.3 High dimensional Datasets