PAC CONFIDENCE PREDICTIONS FOR DEEP NEURAL NETWORK CLASSIFIERS
Year: 2021

Abstract:
A key challenge for deploying deep neural networks (DNNs) in safety critical settings is the need to provide rigorous ways to quantify their uncertainty. In this paper, we propose a novel algorithm for constructing predicted classification confidences for DNNs that comes with provable correctness guarantees. Our approach uses Clopper-Pearson confidence intervals for the Binomial distribution in conjunction with the histogram binning approach to calibrated prediction. In addition, we demonstrate how our predicted confidences can be used to enable downstream guarantees in two settings: (i) fast DNN inference, where we demonstrate how to compose a fast but inaccurate DNN with an accurate but slow DNN in a rigorous way to improve performance without sacrificing accuracy, and (ii) safe planning, where we guarantee safety when using a DNN to predict whether a given action is safe based on visual observations. In our experiments, we demonstrate that our approach can be used to provide guarantees for state-of-the-art DNNs.

heading: 1 INTRODUCTION
text: Due to the recent success of machine learning, there has been increasing interest in using predictive models such as deep neural networks (DNNs) in safety-critical settings, such as robotics (e.g., obstacle detection (Ren et al., 2015) and forecasting (Kitani et al., 2012)) and healthcare (e.g., diagnosis (Gulshan et al., 2016; Esteva et al., 2017) and patient care management (Liao et al., 2020)).
One of the key challenges is the need to provide guarantees on the safety or performance of DNNs used in these settings. The potential for failure is inevitable when using DNNs, since they will inevitably make some mistakes in their predictions. Instead, our goal is to design tools for quantifying the uncertainty of these models; then, the overall system can estimate and account for the risk inherent in using the predictions made by these models. For instance, a medical decision-making system may want to fall back on a doctor when its prediction is uncertain whether its diagnosis is correct, or a robot may want to stop moving and ask a human for help if it is uncertain to act safely. Uncertainty estimates can also be useful for human decision-makers—e.g., for a doctor to decide whether to trust their intuition over the predicted diagnosis.
While many DNNs provide confidences in their predictions, especially in the classification setting, these are often overconfident. This phenomenon is most likely because DNNs are designed to overfit the training data (e.g., to avoid local minima (Safran & Shamir, 2018)), which results in the predicted probabilities on the training data being very close to one for the correct prediction. Recent work has demonstrated how to calibrate the confidences to significantly reduce overconfidence (Guo et al., 2017). Intuitively, these techniques rescale the confidences on a held-out calibration set. Because they are only fitting a small number of parameters, they do not overfit the data as was the case in the original DNN training. However, these techniques do not provide theoretical guarantees on their correctness, which can be necessary in safety-critical settings to guarantee correctness.
We propose a novel algorithm for calibrated prediction in the classification setting that provides theoretical guarantees on the predicted confidences. We focus on on-distribution guarantees— i.e., where the test distribution is the same as the training distribution. In this setting, we can build on ideas from statistical learning theory to provide probably approximately correctness (PAC) guarantees (Valiant, 1984). Our approach is based on a calibrated prediction technique called histogram
binning (Zadrozny & Elkan, 2001), which rescales the confidences by binning them and then rescaling each bin independently. We use Clopper-Pearson bounds on the tails of the binomial distribution to obtain PAC upper/lower bounds on the predicted confidences.
Next, we study how it enables theoretical guarantees in two applications. First, we consider the problem of speeding up DNN inference by composing a fast but inaccurate model with a slow but accurate model—i.e., by using the accurate model for inference only if the confidence of the inaccurate one is underconfident (Teerapittayanon et al., 2016). We use our algorithm to obtain guarantees on accuracy of the composed model. Second, for safe planning, we consider using a DNN to predict whether or not a given action (e.g., move forward) is safe (e.g., do not run into obstacles) given an observation (e.g., a camera image). The robot only continues to act if the predicted confidence is above some threshold. We use our algorithm to ensure safety with high probability. Finally, we evaluate the efficacy of our approach in the context of these applications.
Related work. Calibrated prediction (Murphy, 1972; DeGroot & Fienberg, 1983; Platt, 1999) has recently gained attention as a way to improve DNN confidences (Guo et al., 2017). Histogram binning is a non-parametric approach that sorts the data into finitely many bins and rescales the confidences per bin (Zadrozny & Elkan, 2001; 2002; Naeini et al., 2015). However, traditional approaches do not provide theoretical guarantees on the predicted confidences. There has been work on predicting confidence sets (i.e., predict a set of labels instead of a single label) with theoretical guarantees (Park et al., 2020a), but this approach does not provide the confidence of the most likely prediction, as is often desired. There has also been work providing guarantees on the overall calibration error (Kumar et al., 2019), but this approach does not provide per-prediction guarantees.
There has been work speeding up DNN inference (Hinton et al., 2015). One approach is to allow intermediate layers to be dynamically skipped (Teerapittayanon et al., 2016; Figurnov et al., 2017; Wang et al., 2018), which can be thought of as composing multiple models that share a backbone. Unlike our approach, they do not provide guarantees on the accuracy of the composed model.
There has also been work on safe learning-based control (Akametalu et al., 2014; Fisac et al., 2019; Bastani, 2019; Li & Bastani, 2020; Wabersich & Zeilinger, 2018; Alshiekh et al., 2018); however, these approaches are not applicable to perception-based control. The most closely related work is Dean et al. (2019), which handles perception, but they are restricted to known linear dynamics.

heading: 2 PAC CONFIDENCE PREDICTION
text: In this section, we begin by formalizing the PAC confidence coverage prediction problem; then, we describe our algorithm for solving this problem based on histogram binning.
Calibrated prediction. Let x ∈ X be an example and y ∈ Y be one of a finite label set, and let D be a distribution over X × Y . A confidence predictor is a model f̂ : X → PY , where PY is the space of probability distributions over labels. In particular, f̂(x)y is the predicted confidence that the true label for x is y. We let ŷ : X → Y be the corresponding label predictor—i.e., ŷ(x) := arg maxy∈Y f̂(x)y—and let p̂ : X → R≥0 be corresponding top-label confidence predictor— i.e., p̂(x) := maxy∈Y f̂(x)y . While traditional DNN classifiers are confidence predictors, a naively trained DNN is not reliable—i.e., predicted confidence does not match to the true confidence; recent work has studied heuristics for improving reliability (Guo et al., 2017). In contrast, our goal is to construct a confidence predictor that comes with theoretical guarantees.
We first introduce the definition of calibration (DeGroot & Fienberg, 1983; Zadrozny & Elkan, 2002; Park et al., 2020b)—i.e., what we mean for a predicted confidence to be “correct”. In many cases, the main quantity of interest is the confidence of the top prediction. Thus, we focus on ensuring that the top-label predicted confidence p̂(x) is calibrated (Guo et al., 2017); our approach can easily be extended to providing guarantees on all confidences predicted using f̂ . Then, we say a confidence predictor f̂ is well-calibrated with respect to distribution D if
P(x,y)∼D [y = ŷ(x) | p̂(x) = t] = t (∀t ∈ [0, 1]).
That is, among all examples x such that the label prediction ŷ(x) has predicted confidence t = p̂(x), ŷ(x) is the correct label for exactly a t fraction of these examples. Using a change of variables (Park
et al., 2020b), f̂ being well-calibrated is equivalent to
p̂(x) = c∗ f̂ (x) := P(x′,y′)∼D [y ′ = ŷ(x′) | p̂(x′) = p̂(x)] (∀x ∈ X ). (1)
Then, the goal of well-calibration is to make p̂ equal to c∗ f̂ . Note that f̂ appears on both sides of the equation p̂(x) = c∗
f̂ (x)—implicitly in p̂—which is what makes it challenging to satisfy.
Indeed, in general, it is unlikely that (1) holds exactly for all x. Instead, based on the idea of histogram binning (Zadrozny & Elkan, 2001), we consider a variant where we partition the data into a fixed number of bins and then construct confidence coverages separately for each bin. In particular, consider K bins B1, . . . , BK ⊆ [0, 1], where B1 = [0, b1] and Bk = (bk−1, bk] for k > 1. Here, K and 0 ≤ b1 ≤ · · · ≤ bK−1 ≤ bK = 1 are hyperparameters. Given f̂ , let κf̂ : X → {1, . . . ,K} to denote the index of the bin that contains p̂(x)—i.e., p̂(x) ∈ Bκf̂ (x).
Definition 1 We say f̂ is well-calibrated for a distribution D and bins B1, . . . , BK if
p̂(x) = cf̂ (x) := P(x′,y′)∼D
[ y′ = ŷ(x′) ∣∣∣ p̂(x′) ∈ Bκf̂ (x)] (∀x ∈ X ), (2) where we refer to cf̂ (x) as the true confidence. Intuitively, this definition “coarsens” the calibration problem across the bins—i.e., rather than sorting the inputs x into a continuum of “bins” p̂(x) = t for each t ∈ [0, 1] as in (1), we sort them into a finite number of bins p̂(x) ∈ Bk; intuitively, we have c∗
f̂ ≈ cf̂ if the bin sizes are close to zero. It may not be obvious what downstream guarantees
can be obtained based on this definition; we provide examples in Sections 3 & 4.
Problem formulation. We formalize the problem of PAC calibration. We focus on the setting where the training and test distributions are identical—e.g., we cannot handle adversarial examples or changes in covariate distribution (e.g., common in reinforcement learning). Importantly, while we assume a pre-trained confidence predictor f̂ is given, we make no assumptions about f̂—e.g., it can be uncalibrated or heuristically calibrated. If f̂ performs poorly, then the predicted confidences will be close to 1/|Y|—i.e., express no confidence in the predictions. Thus, it is fine if f̂ is poorly calibrated; the important property is that the confidence predictor f̂ have similar true confidences.
The challenge in formalizing PAC calibration is that quantifying over all x in (2). One approach is to provide guarantees in expectation over x (Kumar et al., 2019); however, this approach does not provide guarantees for individual predictions.
Instead, our goal is to find a set of predicted confidences that includes the true confidence with high probability. Of course, we could simply predict the interval [0, 1], which always contains the true confidence; thus, simultaneously want to make the size of the interval small. To this end, we consider a confidence coverage predictor Ĉ : X → 2R, where cf̂ (x) ∈ Ĉ(x) with high probability. In particular, Ĉ(x) outputs an interval [c, c] ⊆ R, where c ≤ c, instead of a set. We only consider a single interval (rather than disjoint intervals) since one suffices to localize the true confidence cf̂ .
We are interested in providing theoretical guarantees for an algorithm used to construct confidence coverage predictor Ĉ given a held-out calibration set Z ⊆ X × Y . In addition, we assume the algorithm is given a pretrained confidence predictor f̂ . Thus, we consider Ĉ as depending on Z and f̂ , which we denote by Ĉ(·; f̂ , Z). Then, we want Ĉ to satisfy the following guarantee:
Definition 2 Given δ ∈ R>0 and n ∈ N, Ĉ is probably approximately correct (PAC) if for any D,
PZ∼Dn [ ∧ x∈X cf̂ (x) ∈ Ĉ(x; f̂ , Z) ] ≥ 1− δ. (3)
Note that cf̂ depends on D. Here, “approximately correct” technically refers to the mean of
Ĉ(x; f̂ , Z), which is an estimate of cf̂ (x); the interval captures the bound on the error of this estimate; see Appendix A for details. Furthermore, the conjunction over all x ∈ X may seem strong. We can obtain such a guarantee due to our binning strategy: the property cf̂ (x) ∈ Ĉ(x; f̂ , Z) only depends on the bin Bκf̂ (x), so the conjunction is really only over bins k ∈ {1, ...,K}.
Algorithm. We propose a confidence coverage predictor that satisfies the PAC property. The problem of estimating the confidence interval Ĉ(x) of the binned true confidence cf̂ (x) is closely related to the binomial proportion confidence interval estimation; consider a Bernoulli random variable b ∼ B := Bernoulli(θ) for any θ ∈ [0, 1], where b = 1 denotes a success and b = 0 denotes a failure, and θ is unknown. Given a sequence of observations b1:n := (b1, . . . , bn) ∼ Bn, the goal is to construct an interval Θ̂(b1:n) ⊆ R that includes θ with high probability—i.e.,
Pb1:n∼Bn [ θ ∈ Θ̂(b1:n) ] ≥ 1− α, (4)
where α ∈ R>0 is a given confidence level. In particular, the Clopper-Pearson interval
Θ̂CP(b1:n;α) := [ inf θ { θ ∣∣∣ Pθ [S ≥ s] ≥ α 2 } , sup
θ
{ θ ∣∣∣ Pθ [S ≤ s] ≥ α
2
}] ,
guarantees (4) (Clopper & Pearson, 1934; Brown et al., 2001), where s = ∑n i=1 bi is the number of observed successes, n is the number of observations, and S is a Binomial random variable S ∼ Binomial(n, θ). Intuitively, the interval is constructed such that the number of observed success falls in the region with high-probability for any θ in the interval. The following expression is equivalent due to the relationship between the Binomial and Beta distributions (Hartley & Fitch, 1951; Brown et al., 2001)—i.e., Pθ[S ≥ s] = Iθ(s, n− s+ 1), where Iθ is the CDF of Beta(s, n− s+ 1):
Θ̂CP(b1:n;α) = [α
2 quantile of Beta(s, n− s+ 1),
( 1− α
2
) quantile of Beta(s+ 1, n− s) ] .
Now, for each of the K bins, we apply Θ̂CP with confidence level α = δK—i.e.,
Ĉ(x; f̂ , Z, δ) := Θ̂CP ( Wκf̂ (x); δ
K
) where Wk := { 1(ŷ(x) = y) ∣∣∣ (x, y) ∈ Z s.t. κf̂ (x) = k} . Here, Wk is the set of observations of successes vs. failures corresponding to the subset of labeled examples (x, y) ∈ Z such that p̂(x) falls in the bin Bk, where a success is defined to be a correct prediction ŷ(x) = y. We note that for efficiency, the confidence interval for each of the K bins can be precomputed. Our construction of Ĉ satisfies the following; see Appendix B for a proof:
Theorem 1 Our confidence coverage predictor Ĉ is PAC for any δ ∈ R>0 and n ∈ N.
Note that Clopper-Pearson intervals are exact, ensuring the size of Ĉ for each bin is small in practice. Finally, an important special case is when there is a single bin B = [0, 1]—i.e.,
Ĉ0(x; f̂ , Z ′, δ) := Θ̂CP(W ; δ) where W := {1(ŷ(x′) = y′) | (x′, y′) ∈ Z ′}.
Note that Ĉ0 does not depend on x, so we drop it—i.e., Ĉ0(f̂ , Z ′, δ) := Θ̂CP(W ; δ)—i.e., Ĉ0 computes the Clopper-Pearson interval over Z ′, which is a subset of the original set Z.

heading: 3 APPLICATION TO FAST DNN INFERENCE
text: A key application of predicted confidences is to perform model composition to improve the running time of DNNs without sacrificing accuracy. The idea is to use a fast but inaccurate model when it is confident in its prediction, and switch to an accurate but slow model otherwise (Bolukbasi et al., 2017); we refer to the combination as the composed model. To further improve performance, we can have the two models share a backbone—i.e., the fast model shares the first few layers of the slow model (Teerapittayanon et al., 2016). We refer to the decision of whether to skip the slow model as the exit condition; then, our goal is to construct confidence thresholds for exit conditions in a way that provides theoretical guarantees on the overall accuracy.
Problem setup. The early-stopping approach for fast DNN inference can be formalized as a sequence of branching classifiers organized in a cascading way—i.e.,
ŷC(x; γ1:M−1) :=
{ ŷm(x) if ∧m−1 i=1 (p̂i(x) < γi) ∧ (p̂m(x) ≥ γm) (∀m ∈ {1, ...,M − 1})
ŷM (x) otherwise,
where M is the number of branches, f̂m is the confidence predictor, and ŷm and p̂m are the associated label and top-label confidence predictor, respectively. For conciseness, we denote the exit condition of the mth branch by dm (i.e., dm(x) := 1( ∧m−1 i=1 (p̂i(x) < γi) ∧ (p̂m(x) ≥ γm))) with thresholds γ1, . . . , γm ∈ [0, 1]. The f̂m share a backbone and are trained in the standard way; see Appendix F.4 for details. Figure 1 illustrates the composed model for M = 4; the gray area represents the shared backbone. We refer to an overall model composed in this way as a cascading classifier.
Desired error bound. Given ξ ∈ R>0, our goal is to choose γ1:M−1 := (γ1, . . . , γM−1) so the error difference of the cascading classifier ŷC and the slow classifier ŷM is at most ξ—i.e.,
perr := P(x,y)∼D [ŷC(x) 6= y]−P(x,y)∼D [ŷM (x) 6= y] ≤ ξ. (5) To obtain the desired error bound, an example x exits at the mth branch if ŷm is likely to classify x correctly, allowing for at most ξ fraction of errors total. Intuitively, if the confidence of ŷm on x is sufficiently high, then ŷm(x) = y with high probability. In this case, ŷM either correctly classifies or misclassifies the same example; if the example is misclassified, it contributes to decrease perr; otherwise, we have ŷm(x) = y = ŷM (x) with high probability, which contributes to maintain perr.
Fast inference. To minimize running time, we prefer to allow higher error rates at the lower branches—i.e., we want to choose γm as small as possible at lower branches m.
Algorithm. Our algorithm takes prediction branches f̂m (for m ∈ {1, . . . ,M}), the desired relative error ξ ∈ [0, 1], a confidence level δ ∈ [0, 1], and a calibration set Z ⊆ X × Y , and outputs γ1:M−1 so that (5) holds with probability at least 1 − δ. It iteratively chooses the thresholds from γ1 to γM−1; at each step, it chooses γm as small as possible subject to perr ≤ ξ. Note that γm implicitly appears in perr in the constraint due to the dependence of dm(x) on γm. The challenge is enforcing the constraint since we cannot evaluate it. To this end, let
em := P(x,y)∼D [ŷm(x) 6= y ∧ ŷm(x) 6= ŷM (x) ∧ dm(x) = 1] e′m := P(x,y)∼D [ŷM (x) 6= y ∧ ŷm(x) 6= ŷM (x) ∧ dm(x) = 1] ,
then it is possible to show that perr = ∑M−1 m=1 em − e′m (see proof of Theorem 2 in Appendix C). Then, we can compute bounds on em and e′m using the following:
P [ŷm(x) = y | ŷm(x) 6= ŷM (x) ∧ dm(x) = 1] ∈ [cm, c̄m] := Ĉ0 ( f̂m, Zm,
δ
3(M − 1) ) P [ŷM (x) = y | ŷm(x) 6= ŷM (x) ∧ dm(x) = 1] ∈ [c′m, c̄′m] := Ĉ0 ( f̂M , Zm, δ
3(M − 1) ) P [ŷm(x) 6= ŷM (x) ∧ dm(x) = 1] ∈ [rm, r̄m] := Θ̂CP ( Wm; δ
3(M − 1)
) ,
where Zm := {(x, y) ∈ Z | ŷm(x) 6= ŷM (x) ∧ dm(x) = 1} Wm := {1(ŷm(x) 6= ŷM (x) ∧ dm(x) = 1) | (x, y) ∈ Z}. Thus, we have em ≤ c̄mr̄m and e′m ≥ c′mrm, in which case it suffices to sequentially solve
γm = arg min γ∈[0,1] γ subj. to m∑ i=1 c̄ir̄i − c′iri ≤ ξ. (6)
Here, c̄m, r̄m, cm, and rm are implicitly a function of γ, which we can optimize using line search. We have the following guarantee; see Appendix C for a proof:
Theorem 2 We have perr ≤ ξ with probability at least 1− δ over Z ∼ Dn.
Moreover, the proposed greedy algorithm (6) is actually optimal in reducing inference speed when M = 2. Intuitively, we are always better off in terms of inference time by classifying more examples using a faster model. In particular, we have the following theorem; see Appendix D for a proof:
Theorem 3 If M = 2, γ∗1 minimizes (6), and the classifiers ŷm are faster for smaller m, then the resulting ŷC is the fastest cascading classifier among cascading classifiers that satisfy perr ≤ ξ.

heading: 4 APPLICATION TO SAFE PLANNING
text: Robots acting in open world environments must rely on deep learning for tasks such as object recognition—e.g., detect objects in a camera image; providing guarantees on these predictions is critical for safe planning. Safety requires not just that the robot is safe while taking the action, but that it can safely come to a stop afterwards—e.g., that a robot can safely come to a stop before running into a wall. We consider a binary classification DNN trained to predict a probability f̂(x) ∈ [0, 1] of whether the robot is unsafe in this sense.1 If f̂(x) ≥ γ for some threshold γ ∈ [0, 1], then the robot comes to a stop (e.g., to ask a human for help). If the label 1(f̂(x) ≥ γ) correctly predicts safety, then this policy ensures safety as long as the robot starts from a safe state (Li & Bastani, 2020). We apply our approach to choose γ to ensure safety with high probability.
Problem setup. Given a performant but potentially unsafe policy π̂ (e.g., a DNN policy trained to navigate to the goal), our goal is to override π̂ as needed to ensure safety. We assume that π̂ is trained in a simulator, and our goal is to ensure that π̂ is safe according to our model of the environment, which is already a challenging problem when π̂ is a deep neural network over perceptual inputs. In particular, we do not address the sim-to-real problem.
Let x ∈ X be the states, Xsafe ⊆ X be the safe states (i.e., our goal is to ensure the robot stays in Xsafe), o ∈ O be the observations, u ∈ U be the actions, g : X × U → X be the (deterministic) dynamics, and h : X → O be the observation function. A state x is recoverable (denoted x ∈ Xrec) if the robot can use π̂ in state x and then safely come to a stop using a backup policy π0 (e.g., braking).
Then, the shield policy uses π̂ if x ∈ Xrec, and π0 otherwise (Bastani, 2019). This policy guarantees safety as long as an initial state is recoverable—i.e., x0 ∈ Xrec. The challenge is determining whether x ∈ Xrec. When we observe x, we can use model-based simulation to perform this check. However, in many settings, we only have access to observations—e.g., camera images or LIDAR scans—so this approach does not apply. Instead, we propose to train a DNN to predict recoverability—i.e.,
ŷ(o) := { 1 (“un-recoverable”) if f̂(o) ≥ γ 0 (“recoverable”) otherwise
where o = h(x),
with the goal that ŷ(o) ≈ y∗(x) := 1(x 6∈ Xrec), resulting in the following the shield policy πshield:
πshield(o) := { π̂(o) if ŷ(o) = 0 π0(o) otherwise.
Safety guarantee. Our main goal is to choose γ so that πshield ensures safety with high probability— i.e., given ξ ∈ R>0 and any distribution D over initial states X0 ⊆ Xrec, we have
punsafe := Pζ∼Dπshield [ζ 6⊆ Xsafe] ≤ ξ, (7)
where ζ(x0, π) := (x0, x1, . . . ) is a rollout from x0 ∼ D generated using π—i.e., xt+1 = g(xt, π(h(xt))).2 We assume the rollout terminates either once the robot reaches its goal, or once it switches to π0 and comes to a stop; in particular, the robot never switches from π0 back to π̂.
Success rate. To maximize the success rate (i.e., the rate at which the robot achieves its goal), we need to minimize how often πshield switches to π0, which corresponds to maximizing γ.
1Since |Y| = 2, f̂ can be represented as a map f̂ : X → [0, 1]; the second component is simply 1− f̂(x). 2We can handle infinitely long rollouts, but in practice rollouts will be finite (but possibly arbitrarily long).
and Dπshield is an induced distribution over rollouts ζ(x0, πshield).
Algorithm. Our algorithm takes the confidence predictor f̂ , desired bound ξ ∈ R>0 on the unsafety probability, confidence level δ ∈ [0, 1], calibration set W ⊆ X∞ of rollouts ζ ∼ Dπ̂ , and calibration set Z ⊆ O of samples from distribution D̃ described below; see Appendix F.5 for details on sampling ζ and constructing W , Z, and D̃. We want to maximize γ subject to punsafe ≤ ξ, where punsafe is implicitly a function of γ. However, we cannot evaluate punsafe, so we need an upper bound.
To this end, consider a rollout that the first unsafe state is encountered on step t (i.e., xt 6∈ Xsafe but xi ∈ Xsafe for all i < t), which we call an unsafe rollout, and denote the event that the unsafe rollout is encountered by Et; we exploit the unsafe rollouts to bound punsafe. In particular, let pt := Pζ∼Dπ̂ [Et], and let p̄ := ∑∞ t=0 pt be the probability that a rollout is unsafe. Then, consider a new
distribution D̃ overO with a probability density function pD̃(o) := ∑∞ t=0 pDπ̂ (o | Et) ·pt/p̄, where pDπ̂ is the original probability density function of Dπ̂; in particular, we can draw an observation o ∼ D̃ by sampling the observation of the first unsafe state from a rollout sample (and rejecting if the entire rollout is safe). Then, we can show the following (see a proof of Theorem 4 in Appendix E):
punsafe ≤ Po∼D̃[ŷ(o) = 0] · p̄ =: p̄unsafe. (8)
We use our confidence coverage predictor Ĉ0 to compute bounds on p̄unsafe—i.e., Po∼D̃ [ŷ(o) = 1] ∈ [c, c̄] := Ĉ0 ( f̂ , Z ′, δ
2
) where Z ′ := {(o, 1) | o ∈ Z}
p̄ ∈ [r, r̄] := Θ̂CP ( W ′, δ
2
) where W ′ := {1(ζ 6⊆ Xsafe) | ζ ∈W}.
Here, Z ′ is a labeled version of Z, where “1” denotes “un-recoverable”, n := |W |, and n′ := |Z|, where n ≥ n′. Then, we have p̄unsafe ≤ r̄ · (1− c), so it suffices to solve the following problem:
γ := arg max γ′∈[0,1]
γ′ subj. to r̄ · (1− c) ≤ ξ (9)
Here, c is implicitly a function of γ′; thus, we use line search to solve this optimization problem. We have the following safety guarantee, see Appendix E for a proof:
Theorem 4 We have punsafe ≤ ξ with probability at least 1− δ over W ∼ Dnπ̂ and Z ∼ D̃n ′ .

heading: 5 EXPERIMENTS
text: We demonstrate that how our proposed approach can be used to obtain provable guarantees in our two applications: fast DNN inference and safe planning. Additional results are in Appendix G.

heading: 5.1 CALIBRATION
text: We illustrate the calibration properties of our approach using reliability diagrams, which show the empirical accuracy of each bin as a function of the predicted confidence (Guo et al., 2017). Ideally, the accuracy should equal the predicted confidence, so the ideal curve is the line y = x. To draw our predicted confidence intervals in these plots, we need to rescale them; see Appendix F.3.
Setup. We use the ImageNet dataset (Russakovsky et al., 2015) and ResNet101 (He et al., 2016) for evaluation. We split the ImageNet validation set into 20, 000 calibration and 10, 000 test images.
Baselines. We consider three baselines: (i) naïve softmax of f̂ , (ii) temperature scaling (Guo et al., 2017), and (iii) histogram binning (Zadrozny & Elkan, 2001); see Appendix F.2 for details. For histogram binning and our approach, we use K = 20 bins of the same size.
Metric. We use expected calibration error (ECE) and reliability diagrams (see Appendix F.3).
Results. Results are shown in Figure 2. The ECE of the naïve softmax baseline is 4.79% (Figure 2a), of temperature scaling enhances this to 1.66% (Figure 2b), and of histogram binning is 0.99% (Figure 2c). Our approach predicts an interval that include the empirical accuracy in all bins (solid red lines in Figure 2c); furthermore, the upper/lower bounds of the ECE over values in our bins is [0.0%, 3.76%], which includes zero ECE. See Appendix G.1 for additional results.

heading: 5.2 FAST DNN INFERENCE
text: Setup. We use the same ImageNet setup along with ResNet101 as the calibration task. For the cascading classifier, we use the original ResNet101 as the slow network, and add a single exit branch (i.e., M = 2) at a quarter of the way from the input layer. We train the newly added branch using the standard procedure for training ResNet101.
Baselines. We compare to naïve softmax and to calibrated prediction via temperature scaling, both using a threshold γ1 = 1 − ξ ′ , where ξ ′ is the sum of ξ and the validation error of the slow model; intuitively, this threshold is the one we would use if the predicted probabilities are perfectly calibrated. We also compare to histogram binning—i.e., our approach but using the means of each bin instead of the upper/lower bounds. See Appendix F.2 for details.
Metrics. First, we measure test set top-1 classification error (i.e., 1 − accuracy), which we want to guarantee this lower than a desired error (i.e., the error of the slow model and desired relative error ξ). To measure inference time, we consider the average number of multiplication-accumulation operations (MACs) used in inference per example. Note that the MACs are averaged over all examples in the test set since the combined model may use different numbers of MACs for different examples.
Results. The comparison results with the baselines are shown in Figure 3a. The original neural network model is denoted by “slow network”, our approach (6) by “rigorous”, and our baseline by “(1 − ξ′)-softmax”, “(1 − ξ′)-temp.”, and “hist. bin.”. For each method, we plot the classification error and time in MACs. The desired error upper bound is plotted as a dotted line; the goal is for the classification error to be lower than this line. As can be seen, our method is guaranteed to achieve the desired error, while improving the inference time by 32% compared to the slow model. On the other hand, the histogram baseline improves the inference time but fails to satisfy the desired error. Asymptotically, histogram binning is guaranteed to be perfectly calibrated, but it makes mistakes due to finite sample errors. The other baselines do not improve inference time. Next, Figure 3b shows the classification error as we vary the desired relative error ξ; our approach always achieves the desired error on the test set, and is often very close (which maximizes speed). However, the
baselines often violate the desired error bound. Finally, the MACs metric is only an approximation of the actual inference time. To complement MACs, we also measure CPU and GPU time using the PyTorch profiler. In Figure 3c, we show the inference times for each method, where trends are as before; our approach improves running time by 54%, while only reducing classification error by 1%. The histogram baseline is faster than our approach, but does not satisfy the error guarantee. These results include the time needed to compute the intervals, which is negligible.

heading: 5.3 SAFE PLANNING
text: Setup. We evaluate on AI Habitat (Savva et al., 2019), an indoor robot simulator that provides agents with observations o = h(x) that are RGB camera images. The safety constraint is to avoid colliding with obstacles such as furniture in the environment. We use the learned policy π̂ available with the environment. Then, we train a recoverability predictor, trained using 500 rollouts with a horizon of 100. We calibrate this model on an additional n rollouts.
Baselines. We compare to three baselines: (i) histogram binning—i.e., our approach but using the means of each bin rather than upper/lower bounds, (ii) a naïve approach of choosing γ = 0.5, and (iii) a naïve but adaptive approach of choosing γ = ξ, called “ξ-naïve”.
Metrics. We measure both the safety rate and the success rate; in particular, a rollout is successful if the robot reaches its goal state, and a rollout is safe if it does not reach any unsafe states.
Results. We show results in Figure 4a. The desire safety rate ξ is shown by the dotted line—i.e., we expect the safety rate to be above this line. As can be seen, our approach achieves the desired safety rate. While it sacrifices success rate, this is because the underlying learned policy π̂ is frequently unsafe; in particular, it is only safe in about 30% of rollouts. The naïve approach fails to satisfy the safety constraint. The ξ-naïve approach tends to be optimistic, and also fails when ξ = 0.03 (Figure 4b). The histogram baseline performs similarly to our approach. The main benefit of our approach is providing the absolute guarantee on safety, which the histogram baseline does not provide. Thus, in this case, our approach can provide this guarantee while achieving similar performance. Figure 4b shows the safety rate as we vary the desired safety rate ξ. Both our approach and the baseline satisfy the desired safety guarantee, whereas the naive approaches do not always do so.

heading: 6 CONCLUSION
text: We have proposed a novel algorithm for calibrated prediction that provides PAC guarantees, and demonstrated how our approach can be applied to fast DNN inference and safe planning. There are many directions for future work—e.g., leveraging these techniques in more application domains and extending our approach to settings with distribution shift (see Appendix F.1 for a discussion).

heading: ACKNOWLEDGMENTS
text: This work was supported in part by AFRL/DARPA FA8750-18-C-0090, ARO W911NF-20-1-0080, DARPA FA8750-19-2-0201, and NSF CCF 1910769. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the Air Force Research Laboratory (AFRL), the Army Research Office (ARO), the Defense Advanced Research Projects Agency (DARPA), or the Department of Defense, or the United States Government.

heading: A CONNECTION TO PAC LEARNING THEORY
text: We explain the connection to PAC learning theory. First, note that we can represent Ĉ as a confidence interval around the empirical estimate of cf̂ (x)—i.e., ĉf̂ (x) := ∑ (x′,y′)∈Sx 1(y
′ = ŷ(x′))/|Sx|, where Sx = {(x′, y′) | p̂(x′) ∈ Bκf̂ (x)}. Then, we can write
Ĉ(x) = [ĉf̂ (x)− x, ĉf̂ (x) + ̄x].
In this case, (3) is equivalent to
PZ∼Dn [ ∧ x∈X ĉf̂ (x)− κf̂ (x) ≤ cf̂ (x) ≤ ĉf̂ (x) + ̄κf̂ (x) ] ≥ 1− δ, (10)
for some 1, ̄1, . . . , K , ̄K . In this bound, “approximately” refers to the fact that the empirical estimate ĉf̂ (x) is within of the true value cf̂ (x), and “probably” refers to the fact that this error bound holds with high probability over the training data Z ∼ Dn. By abuse of terminology, we refer to the confidence interval predictor Ĉ as PAC rather than just ĉf̂ (x).
Alternatively, we also have the following connection to PAC learning theory:
Definition 3 Given , δ ∈ R>0 and n ∈ N, Ĉ is probably approximately correct (PAC) if, for any distribution D, we have
PZ∼Dn [ Px∼D [ cf̂ (x) ∈ Ĉ(x; f̂ , Z) ] ≥ 1− ] ≥ 1− δ. (11)
The following theorem shows that the proposed confidence coverage predictor Ĉ satisfies the PAC guarantee in Definition 3.
Theorem 5 Our confidence coverage predictor Ĉ satisfies Definition 3 for all , δ ∈ R>0, and n ∈ N.
Proof. We exploit the independence of each bin for the proof. Let θκf̂ (x) := cf̂ (x), which is the parameter of the Binomial distribution of the κf̂ (x)th bin, the following holds:
P Z∼Dn [ P x∼D [ cf̂ (x) ∈ Ĉ(x; f̂ , Z, δ) ] ≥ 1− ] = P Z∼Dn [ P x∼D [ cf̂ (x) ∈ Ĉ(x; f̂ , Z, δ) ∧ K∨ k=1 p̂(x) ∈ Bk ] ≥ 1− ]
= P Z∼Dn [ K∑ k=1 P x∼D [ cf̂ (x) ∈ Ĉ(x; f̂ , Z, δ) ∧ p̂(x) ∈ Bk ] ≥ 1− ]
= P Z∼Dn [ K∑ k=1 P x∼D [ cf̂ (x) ∈ Ĉ(x; f̂ , Z, δ) ∣∣∣ p̂(x) ∈ Bk] P x∼D [p̂(x) ∈ Bk] ≥ 1− ]
= P Z∼Dn [ K∑ k=1 P x∼D [ θk ∈ Θ̂CP ( Wk; δ K ) ∣∣∣∣ p̂(x) ∈ Bk] P x∼D [p̂(x) ∈ Bk] ≥ 1− ]
= P Z∼Dn [ K∑ k=1 1 [ θk ∈ Θ̂CP ( Wk; δ K )] P x∼D [p̂(x) ∈ Bk] ≥ 1− ]
≥ P Z∼Dn [ K∑ k=1 1 [ θk ∈ Θ̂CP ( Wk; δ K )] P x∼D [p̂(x) ∈ Bk] ≥ 1−
∧ K∧ k=1 1 [ θk ∈ Θ̂CP ( Wk; δ K )] = 1 ]
= P Z∼Dn [ K∑ k=1 1 [ θk ∈ Θ̂CP ( Wk; δ K )] P x∼D [p̂(x) ∈ Bk] ≥ 1− ∣∣∣∣∣ K∧ k=1 1 [ θk ∈ Θ̂CP ( Wk; δ K )] = 1 ]
P Z∼Dn [ K∧ k=1 1 [ θk ∈ Θ̂CP ( Wk; δ K )] = 1 ]
= P Z∼Dn [ K∑ k=1 P x∼D [p̂(x) ∈ Bk] ≥ 1− ∣∣∣∣∣ K∧ k=1 1 [ θk ∈ Θ̂CP ( Wk; δ K )] = 1 ]
P Z∼Dn [ K∧ k=1 1 [ θk ∈ Θ̂CP ( Wk; δ K )] = 1 ]
= P Z∼Dn
[ 1 ≥ 1− ∣∣∣∣∣ K∧ k=1 1 [ θk ∈ Θ̂CP ( Wk; δ K )] = 1 ] P Z∼Dn [ K∧ k=1 1 [ θk ∈ Θ̂CP ( Wk; δ K )] = 1 ]
= P Z∼Dn [ K∧ k=1 1 [ θk ∈ Θ̂CP ( Wk; δ K )] = 1 ]
= P Z∼Dn [ K∧ k=1 θk ∈ Θ̂CP ( Wk; δ K )] ≥ 1− δ,
where the last inequality holds by the union bound.

heading: B PROOF OF THEOREM 1
text: We prove this by exploiting the independence of each bin. Recall that Ĉ(x) := [ĉf̂ (x)− x, ĉf̂ (x) + ̄x], and the interval is obtained by applying the Clopper-Pearson interval with confidence level δK at each bin. Then, the following holds due the Clopper-Pearson interval for all k ∈ {1, 2, . . . ,K}:
P [ |cf̂ ,k − ĉf̂ ,k| > k ] ≤ δ K
where cf̂ ,k := cf̂ (x) and ĉf̂ ,k := ĉf̂ (x) for x such that κf̂ (x) = k, and k := max( x, ̄x). By applying the union bound, the following also holds:
P [ K∧ k=1 |cf̂ ,k − ĉf̂ ,k| > k ] ≤ δ,
Considering the fact that X is partitioned into K spaces due to the binning and the equivalence form (10) of the PAC criterion in Definition 3, the claimed statement holds.

heading: C PROOF OF THEOREM 2
text: We drop probabilities over (x, y) ∼ D. First, we decompose the error of a cascading classifier P [ŷC(x) 6= y] as follows:
P [ŷC(x) 6= y] = P [ ŷC(x) 6= y ∧ ( ŷC(x) = ŷM (x) ∨ ŷC(x) 6= ŷM (x) )] = P [( ŷC(x) 6= y ∧ ŷC(x) = ŷM (x) ) ∨ ( ŷC(x) 6= y ∧ ŷC(x) 6= ŷM (x)
)] = P [ŷC(x) 6= y ∧ ŷC(x) = ŷM (x)] +P [ŷC(x) 6= y ∧ ŷC(x) 6= ŷM (x)] ,
where the last equality holds since the events of ŷC(x) = ŷM (x) and of ŷC(x) 6= ŷM (x) are disjoint. Similarly, for the error of a slow classifier P [ŷM (x) 6= y], we have:
P [ŷM (x) 6= y] = P [ŷM (x) 6= y ∧ ŷC(x) = ŷM (x)] +P [ŷM (x) 6= y ∧ ŷC(x) 6= ŷM (x)] .
Thus, the error difference can be represented as follows:
P [ŷC(x) 6= y]−P [ŷM (x) 6= y] = P [ŷC(x) 6= y ∧ ŷC(x) 6= ŷM (x)]−P [ŷM (x) 6= y ∧ ŷC(x) 6= ŷM (x)] . (12)
To complete the proof, we need to upper bound (12) by ξ. Define the following events:
Dm := m−1∧ i=1 (p̂i(x) < γi) ∧ p̂m(x) ≥ γm (∀m ∈ {1, ...,M − 1})
DM := M−1∧ i=1 (p̂i(x) < γi)
EC := ŷC(x) 6= ŷM (x) Em := ŷm(x) 6= ŷM (x) (∀m ∈ {1, ...,M − 1}) FC := ŷC(x) 6= y Fm := ŷm(x) 6= y (∀m ∈ {1, ...,M − 1}) G := ŷM (x) 6= y,
where D1, D2, . . . , DM form a partition of a sample space. Then, we have: P [ŷC(x) 6= y ∧ ŷC(x) 6= ŷM (x)] = P [FC ∧ EC ]
= P [ FC ∧ EC ∧
M∨ m=1 Dm
]
= P [ M∨ m=1 (FC ∧ EC ∧Dm) ]
= M∑ m=1 P [FC ∧ EC ∧Dm]
= M∑ m=1 P [Fm ∧ Em ∧Dm]
= M∑ m=1 P [Fm | Em ∧Dm] ·P [Em ∧Dm] ,
Similarly, we have:
P [ŷM (x) 6= y ∧ ŷC(x) 6= ŷM (x)] = M∑ m=1 P [G | Em ∧Dm] ·P [Em ∧Dm] .
Thus, (12) can be rewritten as follows: P [ŷC(x) 6= y]−P [ŷM (x) 6= y]
= M∑ m=1 (P [Fm | Em ∧Dm] ·P [Em ∧Dm]−P [G | Em ∧Dm] ·P [Em ∧Dm])
= M∑ m=1 (em − e′m)
= M−1∑ m=1 (em − e′m)
≤ ξ, where the last equality holds since eM − e′M = 0, and the last inequality holds due to (6) with probability at least 1− δ, thus proves the claim.

heading: D PROOF OF THEOREM 3
text: Suppose there is γ ′ 1 which is different to γ ∗ 1 and produces a faster cascading classifier than the cascading classifier with γ∗1 . Since γ ∗ 1 is the optimal solution of (6), γ ′ 1 > γ ∗ 1 . This further implies that the less number of examples exits at the first branch of the cascading classifier with γ′1, but these examples are classified by the upper, slower branch. This means that the overall inference speed of the cascading classifier with γ′1 is slower then that with γ ∗ 1 , which leads to a contradiction.

heading: E PROOF OF THEOREM 4
text: For clarity, we use r to denote a state x is “recoverable” (i.e., y∗(x) = 0) and u to denote a state x is “un-recoverable” (i.e., y∗(x) = 1). Now, note that a rollout ζ(x0, πshield) := (x0, x1, . . . ) is unsafe if (i) at some step t, we have y∗(xt) = u (i.e., xt is not recoverable), yet ŷ(ot) = r, where ot = h(xt) (i.e., ŷ predicts xt is recoverable), and furthermore (ii) for every step i ≤ t − 1, y∗(xi) = ŷ(oi) = r—i.e.,
punsafe = Pξ∼Dπshield [ ∞∨ t=0 ( t−1∧ i=0 ( y∗(xi) = r ∧ ŷ(oi) = r ) ∧ ( y∗(xt) = u ∧ ŷ(ot) = r ))] . (13)
Condition (i) is captured by the second parenthetical inside the probability; intuitively, it says that ŷ(ot) is a false negative. Condition (ii) is captured by the first parenthetical inside the probability; intuitively, it says that ŷ(oi) is a true negative for any i ≤ t− 1. Next, let the event Et be
Et := t−1∧ i=0 y∗(xi) = r ∧ y∗(xt) = u,
then the following holds:
Pξ∼Dπshield [ ∞∨ t=0 ( t−1∧ i=0 ( y∗(xi) = r ∧ ŷ(oi) = r ) ∧ ( y∗(xt) = u ∧ ŷ(ot) = r ))]
= Pξ∼Dπshield [ ∞∨ t=0 ( t−1∧ i=0 ( y∗(xi) = r ∧ y∗(xt) = u ) ∧ ( t−1∧ i=0 ŷ(oi) = r ∧ ŷ(ot) = r ))]
= Pξ∼Dπshield [ ∞∨ t=0 ( Et ∧ t−1∧ i=0 ŷ(oi) = r ∧ ŷ(ot) = r )]
≤ Pξ∼Dπshield [ ∞∨ t=0 ( Et ∧ ŷ(ot) = r )] .
Recall that p̄ := ∑∞ t=0Pξ∼Dπ̂ [Et] and pD̃(o) := ∑∞ t=0 pDπ̂ (o | Et) · Pξ∼Dπ̂ [Et]/p̄; then we can upper-bound (13) as follows:
punsafe ≤ Pξ∼Dπshield [ ∞∨ t=0 ( Et ∧ ŷ(ot) = r )]
= ∞∑ t=0 Pξ∼Dπshield [Et ∧ ŷ(ot) = r]
= ∞∑ t=0 Pξ∼Dπshield [ŷ(ot) = r | Et] ·Pξ∼Dπshield [Et]
= ∞∑ t=0 Pξ∼Dπshield [ŷ(o) = r | Et] ·Pξ∼Dπshield [Et]
= ∞∑ t=0 ∫ 1(ŷ(o) = r) · pDπshield (o | Et) ·Pξ∼Dπshield [Et] do
= ∫ 1(ŷ(o) = r) ∞∑ t=0 pDπshield (o | Et) ·Pξ∼Dπshield [Et] do
≤ ∫ 1(ŷ(o) = r) ∞∑ t=0 pDπ̂ (o | Et) ·Pξ∼Dπ̂ [Et] do
= ∫ 1(ŷ(o) = r)pD̃(o)p̄ do
= p̄ ·Po∼D̃[ŷ(o) = r],
where we use the fact that Et are disjoint by construction for the first equality, and we use o without time index t for the third equality since it clearly represents the last observation if it is conditioned on Et. Moreover, the last inequality holds due to the following: (i) pDπshield (o | Et) = pDπ̂ (o | Et), since Et implies that the backup policy of πshield isn’t activated up to the step t, so πshield = π̂, and (ii) Pξ∼Dπshield [Et] ≤ Pξ∼Dπ̂ [Et], since πshield is less likely to reach unsafe states by its design than π̂. Thus, the constraint in (9) implies punsafe ≤ ξ with probability at least 1− δ, so the claim follows.

heading: F ADDITIONAL DISCUSSION
text: F.1 LIMITATION TO ON-DISTRIBUTION SETTING
Our PAC guarantees (i.e., Theorems 1 & 5) transfer to the test distribution if it is identical to the validation distribution. We believe that providing theoretical guarantees for out-of-distribution data is an important direction; however, we believe that our work is an important stepping stone towards this goal. In particular, to the best of our knowledge, we do not know of any existing work that provides theoretical guarantees on calibrated probabilities even for the in-distribution case. One possible direction is to use our approach in conjunction with covariate shift detectors—e.g., (Gretton et al., 2012). Alternatively, it may be possible to directly incorporate ideas from recent work on calibrated prediction with covariate shift (Park et al., 2020b) or uncertainty set prediction with covariate shift (Cauchois et al., 2020; Tibshirani et al., 2019). In particular, we can use importance weighting q(x)/p(x), where p(x) is the training distribution and q(x) is the test distribution, to reweight our training examples, enabling us to transfer our guarantees from the training set to the test distribution. The key challenge is when these weights are unknown. In this case, we can estimate them given a set of unlabeled examples from the test distribution (Park et al., 2020b), but we then need to account for the error in our estimates.
F.2 BASELINES
The following includes brief descriptions on baselines that we used in experiments.
Histogram binning. This algorithm calibrates the top-label confidence prediction of f̂ by sorting the calibration examples (x, y) into bins Bi based on their predicted top-label confidence—i.e., (x, y) is associated with Bi if p̂(x) ∈ Bi. Then, for each bin, it computes the empirical confidence p̂i := 1 |Si| ∑
(x,y)∈Si 1(ŷ(x) = y), where Si is the set of labeled examples that are associated with bin Bi—i.e., the empirical counterpart of the true confidence in (2). Finally, during the test-time, it returns a predicted confidence p̂i for all future test examples x if p̂(x) ∈ Bi.
(1 − ξ′)-softmax. In fast DNN inference, a threshold can be heuristically chosen based on the desired relative error ξ and the validation error of the slow model. In particular, when a cascading classifier consists of two branches—i.e., M = 2, the threshold of the first branch is chosen by γ1 = 1 − ξ ′ , where ξ ′ is the sum of ξ and the validation error of the slow model. We call this approach (1− ξ′)-softmax.
(1 − ξ′)-temperature scaling. A more advanced approach is to first calibrate each branch to get better confidence. We consider using temperature scaling to do so—i.e., we first calibrate each branch using the temperature scaling, and then use the branch threshold by γ1 = 1 − ξ ′ when M = 2. We call this approach (1− ξ′)-temperature scaling.
F.3 CALIBRATION: INDUCED INTERVALS FOR ECE AND RELIABILITY DIAGRAM
ECE. The expected calibration error (ECE), which is one way to measure calibration performance, is defined as follows:
ECE := J∑ j=1 |Sj | |S| ∣∣∣∣∣∣ 1|Sj | ∑
(x,y)∈Sj
p̂(x)− 1 |Sj | ∑ (x,y)∈Sj 1(ŷ(x) = y) ∣∣∣∣∣∣ , where J is the total number of bins for ECE, S ⊆ X × Y is the evaluation set, and Sj is the set of labeled examples associated to the jth bin—i.e., (x, y) ∈ Sj if p̂(x) ∈ Bj .
A confidence coverage predictor Ĉ(x) outputs an interval instead of a point estimate p̂(x) of the confidence. To evaluate the confidence coverage predictor, we remap intervals using the ECE formulation. In particular, we equivalently represents Ĉ(x) by a mean confidence ĉf̂ (x) and differences from the mean—i.e., Ĉ(x) = [c(x), c(x)] = [ĉf̂ (x) − x, ĉf̂ (x) + x] (see Appendix A for a description on this equivalent representation). Then, we sort each labeled example into
bins using ĉf̂ (x) to form Sj . Next, we consider an interval instead of p̂(x) to compute ECE— i.e., ECEinduced := [ ECE,ECE ] , where
ECE := J∑ j=1 |Sj | |S| inf p̂j∈Confj ∣∣∣∣∣∣p̂j − 1|Sj | ∑
(x,y)∈Sj
1(ŷ(x) = y) ∣∣∣∣∣∣ , ECE :=
J∑ j=1 |Sj | |S| sup p̂j∈Confj ∣∣∣∣∣∣p̂j − 1|Sj | ∑
(x,y)∈Sj
1(ŷ(x) = y) ∣∣∣∣∣∣ , and Confj := [ Confj ,Confj ] := [ min
(x,y)∈Sj c(x), max (x,y)∈Sj c(x)
] .
Reliability diagram. This evaluation technique is a pictorial summary of the ECE, where the xaxis represents the mean confidence 1|Sj | ∑ (x,y)∈Sj p̂(x) for each bin, and the y-axis represents the
mean accuracy 1|Sj | ∑
(x,y)∈Sj 1(ŷ(x) = y) for each bin. If an interval from a confidence coverage predictor is given, then the mean confidence is replaced by Confj , resulting in visualizing an interval instead of a point.
F.4 FAST DNN INFERENCE: CASCADING CLASSIFIER TRAINING
We describe a way to train a cascading classifier with M branches. Basically, we consider to independently train M different neural networks with a shared backbone. In particular, we first train the M th branch using a training set by minimizing a cross-entropy loss. Then, we train the (M − 1)th branch, which consists of two parts: a backbone part from the M th branch, and the head of the (M − 1)th branch. Here, the backbone part is already trained in the previous stage, so we do not update the backbone part and only train the head of this branch using the same training set by minimizing the same cross-entropy loss (with the same optimization hyperparameters). This step is done repeatedly down to the first branch.
F.5 SAFE PLANNING: DATA COLLECTION FROM A SIMULATOR
We collect required data from a simulator, where a given policy π̂ is already learned over the simulator. We describe how we form the necessary data from rollouts sampled from the simulator.
First, to sample a rollout ζ, we use π̂ from a random initial state x0 ∼ D; we denote the sequence of states visited as a rollout ζ(x0, π̂) := (x0, x1, . . . ). We denote the induced distribution over rollouts by ζ ∼ Dπ̂ . Note that the ζ contains unsafe states since π̂ is potentially unsafe. However, when constructing our recoverability classifier, we only use the sequence of safe states, followed by a single unsafe state. In particular, we let W be a set of i.i.d. sampled rollouts ζ ∼ Dπ̂ . Next, for a given rollout, we consider the observation in the first unsafe state in that rollout (if one exists); we denote the distribution over such observations by D̃. Finally, we take Z to be a set of sampled observations o ∼ D̃.

heading: G ADDITIONAL EXPERIMENTS
text: G.1 CALIBRATION
G.2 FAST DNN INFERENCE
G.3 SAFE PLANNING

Review summaries:
This paper proposes a method for obtaining probably-approximately correct (PAC) predictions given a pre-trained classifier. The PAC intervals are connected to calibration, and take the form of confidence intervals given the bin a prediction falls in. They demonstrate and explore two use cases: applying this technique to get faster inference in deep neural networks, and using the PAC predictor to do safe planning. Experiments in both of these cases show improvements in speed-accuracy or safety-accuracy tradeoffs, as compared to baselines.