text:
PAC Confidence Sets for Deep Neural Networks via Calibrated Prediction

We propose an algorithm combining calibrated prediction and generalization bounds from learning theory to construct confidence sets for deep neural networks with PAC guarantees---i.e., the confidence set for a given input contains the true label with high probability. We demonstrate how our approach can be used to construct PAC confidence sets on ResNet for ImageNet, a visual object tracking model, and a dynamics model for the half-cheetah reinforcement learning problem.

INTRODUCTION
A key challenge facing deep neural networks is that they do not produce reliable confidence estimates, which are important for applications such as safe reinforcement learning (Berkenkamp et al., 2017), guided exploration (Malik et al., 2019), and active learning (Gal et al., 2017).
We consider the setting where the test data follows the same distribution as the training data (i.e., we do not consider adversarial examples designed to fool the network (Szegedy et al., 2014)); even in this setting, confidence estimates produced by deep neural networks are notoriously unreliable (Guo et al., 2017). One intuition for this shortcoming is that unlike traditional supervised learning algorithms, deep learning models typically overfit the training data (Zhang et al., 2017). As a consequence, the confidence estimates of deep neural networks are flawed even for test data from the training distribution since, by construction, they overestimate the likelihood of the training data.
A promising approach to addressing this challenge is temperature scaling (Platt, 1999). This approach takes as input a trained neural network fφ(y | x)-i.e., whose parametersφ have already been fit to a training dataset Z train -which produces unreliable probabilities fφ(y | x). Then, this approach rescales these confidence estimates based on a validation dataset to improve their "calibration". More precisely, this approach fits confidence estimates of the form fφ ,τ (y | x) ∝ exp(τ log fφ(y | x)), where τ ∈ R >0 is a temperature scaling parameter that is fit based on the validation dataset. The goal is to choose τ to minimize calibration error, which roughly speaking measures the degree to which the reported error rate differs from the actual error rate.
The key insight is that in the temperature scaling approach, only a single parameter τ is fit to the validation data-thus, unlike fitting the original neural network, the temperature scaling algorithm comes with generalization guarantees based on traditional statistical learning theory.
Despite the improved generalization guarantees, these confidence estimates still do not come with theoretical guarantees. We are interested in producing confidence sets that satisfy statistical guarantees while being as small as possible. Given a test input x ∈ X , a confidence set C T (x) ⊆ Y Published as a conference paper at ICLR 2020 |C(x)| = 1 5 ≤ |C(x)| ≤ 10 50 ≤ |C(x)| ≤ 100 |C(x)| ≥ 200 airship zebra Table 1: ImageNet images with varying ResNet confidence set sizes. The confidence set sizes are on the top. The true label is on the left-hand side. Incorrectly labeled images are boxed in red.
(parameterized by T ∈ R) should contain the true label y for at least a 1 − fraction of cases: Since we are fitting a parameter T to based on Z val , we additionally incur a probability of failure due to the randomness in Z val . In other words, given , δ ∈ R >0 , we aim to obtain probably approximately correct (PAC) confidence sets C T (x) ⊆ Y satisfying the guarantee P Zval∼D n P (x,y)∼D (y ∈ C T (x)) ≥ 1 − ≥ 1 − δ.
There are a number of reasons why confidence sets can be useful. First, they can be used to inform safety critical decision making. For example, consider a doctor who uses prediction tools to help perform diagnosis. Having a confidence set would both help the doctor estimate the confidence of the prediction (i.e., smaller confidence sets imply higher confidence), but also give a sense of the set of possible diagnoses. Second, having a confidence set can be useful for reasoning about safety since they contain the true outcome with high probability. For instance, robots may use a confidence set over predicted trajectories to determine whether it is safe to act with high probability. As a concrete example, consider a self-driving car that uses a deep neural network to predict the path that a pedestrian might take. We require that the self-driving car avoid the pedestrian with high probability, which it can do by avoiding all possible paths in the predicted confidence set.
Contributions. We propose an algorithm combining calibrated prediction and statistical learning theory to construct PAC confidence sets for deep neural networks (Section 3). We propose instantiations of this framework in the settings of classification, regression, and learning models for reinforcement learning (Section 3.6). Finally, we evaluate our approach on three benchmarks: ResNet (He et al., 2016) for ImageNet (Russakovsky et al., 2015), a model (Held et al., 2016) learned for a visual object tracking benchmark (Wu et al., 2013), and a probabilistic dynamics model (Chua et al., 2018) learned for the half-cheetah environment (Brockman et al., 2016) (Section 4). Examples of ImageNet images with different sized ResNet confidence sets are shown in Table 1. As can be seen, our confidence sets become larger and the images become more challenging to classify. In addition, we show predicted confidence sets for ResNet in Table 2, as well as predicted confidence sets for the visual object tracking model in Table 3.
Related work. There has been work on constructing confidence sets with theoretical guarantees. Oftentimes, these guarantees are asymptotic rather than finite sample (Steinberger & Leeb, 2016;2018). Alternatively, there has been work focused on predicting confidence sets with a given expected size (Denis & Hebiri, 2017).
More relatedly, there has been recent work on obtaining PAC guarantees. For example, there has been some work specific prediction tasks such as binary classification (Lei, 2014;Wang & Qiao, 1 ≤ |C(x)| < 5 5 ≤ |C(x)| < 10 10 ≤ |C(x)| < 20 king penguin Chihuahua, toy terrier, Italian greyhound, Boston bull, miniature pinscher banded gecko, common iguana, American chameleon, whiptail, agama, frilled lizard, alligator lizard, green lizard, African chameleon, Komodo dragon barber chair, hand blower, medicine chest, paper towel, plunger, shower curtain, soap dispenser, toilet seat, tub, washbasin, washer, toilet tissue Table 2: Confidence sets of ImageNet images with varying ResNet confidence set sizes. The predicted confidence set is shown to the right of the corresponding input image. The true label is shown in red, and the predicted label is shown with a hat. See Table 5 in Appendix D for more examples.  (Wu et al., 2013), including the ground truth bounding box (white), the bounding box predicted by the original neural network (Held et al., 2016) (red), and the bounding box produced using our confidence set predictor (green). We have overapproximated the predicted ellipsoid confidence set with a box. Our bounding box contains the ground truth bounding box with high probability. See Table 9 in Appendix D for more examples. 2018). There has also been work in the setting of regression (Lei et al., 2018;Barber et al., 2019). However, in this case, the confidence sets are fixed in size-i.e., they do not depend on the input x (Barber et al., 2019). Furthermore, they make stability assumptions about the learning algorithm (though they achieved improved rates by doing so) (Lei et al., 2018;Barber et al., 2019).
The most closely related work is on conformal prediction (Papadopoulos, 2008;Vovk, 2013). Like our approach, this line of work provides a way to construct confidence sets from a given confidence predictor, and provided PAC guarantees for the validity of these confidence sets. Indeed, with some work, our generalization bound Theorem 1 can be shown to be equivalent to Theorem 1 in Vovk (2013). In contrast to their approach, we proposed to use calibrated prediction to construct confidence predictors that can suitably be used with deep neural networks. Furthermore, our approach makes explicit the connections to temperature scaling and as well as to generalization bounds from statistical learning theory (Vapnik, 1999). In addition, unlike our paper, they do not explicitly provide an efficient algorithm for constructing confidence sets. Finally, we also propose an extension to the case of learning models for reinforcement learning.
Finally, we build on a long line of work on calibrated prediction, which aims to construct "calibrated" probabilities (Murphy, 1972;DeGroot & Fienberg, 1983;Platt, 1999;Zadrozny & Elkan, 2001;2002;Naeini et al., 2015;Kuleshov & Liang, 2015). Roughly speaking, probabilities are calibrated if events happen at rates equal to the predicted probabilities. This work has recently been applied to obtaining confidence estimates for deep neural networks (Guo et al., 2017;Kuleshov et al., 2018;Pearce et al., 2018), including for learned models for reinforcement learning (Malik et al., 2019). However, these approaches do not come with PAC guarantees.

PAC CONFIDENCE SETS
Our goal is to estimate confidence sets that are as small as possible, while simultaneously ensuring that they are probably approximately correct (PAC) (Valiant, 1984). Essentially, a confidence set is correct if it contains the true label. More precisely, let X be the inputs and Y be the labels, and let D be a distribution over Z = X × Y. A confidence set predictor is a function C : X → 2 Y such that C(x) ⊆ Y is a set of labels; we denote the set of all confidence set predictors by C. For a given example (x, y) ∼ D, we say C is correct if y ∈ C(x). Then, the error of C is (1) Finally, consider an algorithm A that takes as input a validation set Z val ⊆ Z consisting of n i.i.d. samples (x, y) ∼ D, and outputs a confidence set predictorĈ. Given , δ ∈ R >0 , we say that A is probably approximately correct (PAC) if Our goal is to design an algorithm A that satisfies (2) while constructing confidence sets C(x) that are as "small in size" as possible on average. The size of C(x) depends on the domain. For classification, we consider confidence sets that are arbitrary subsets of labels C(x) ⊆ Y = {1, ..., Y }, and we measure the size by |C(x)| ∈ N-i.e., the number of labels in C(x). For regression, we consider confidence sets that are intervals C(x) = [a, b] ⊆ Y = R, and we measure size by b − a-i.e., the length of the predicted interval. Note that there is an intrinsic tradeoff between satisfying (2) and average size of C(x)-larger confidence sets are more likely to satisfy (2).

PAC ALGORITHM FOR CONFIDENCE SET CONSTRUCTION
Our algorithm is formulated in the empirical risk framework. Typically, this framework refers to empirical risk minimization. In our setting, such an algorithm would take as input (i) a parametric family of confidence set predictors C = {C θ | θ ∈ Θ}, where Θ is the parameter space, and (ii) a training set Z val ⊆ Z of n i.i.d. samples (x, y) ∼ D, and output the confidence set predictor Cθ, whereθ minimizes the empirical risk: Here, I[φ] ∈ {0, 1} is the indicator function, and the empirical riskL in an estimate of the confidence set error (1) based on the validation set Z val .
However, our algorithm does not minimize the empirical risk. Rather, recall that our goal is to minimize the size of the predicted confidence sets given a PAC constraint on the true risk L(θ) based on the given PAC parameters , δ ∈ R >0 and the number of available validation samples n = |Z val |. Thus, the risk shows up as a constraint in the optimization problem, and the objective is instead to minimize the size of the predicted confidence sets: At a high level, the value α = α(n, , δ) ∈ R ≥0 is chosen to enforce the PAC constraint, and is based on generalization bounds from statistical learning theory (Valiant, 1984). Furthermore, following the temperature scaling approach (Platt, 1999), the parameter space Θ is chosen to be as small as possible (in particular, one dimensional) to enable good generalization. Finally, our choice of size metric S follows straightforwardly based on our choice of parameter space. In the remainder of this section, we describe the choices of (i) parameter space Θ, (ii) size metric S(θ), and (iii) confidence level α(n, , δ) in more detail, as well as how to solve (3) given these choices.

CHOICE OF PARAMETER SPACE Θ
Probability forecasters. Our construction of the parameteric family of confidence set predictors C θ assumes given a probability forecaster f : X → P Y , where P Y is a space of probability distributions over Y. Given such an f , we use f (y | x) to denote the probability of label y under distribution f (x). Intuitively, f (y | x) should be the probability (or probability density) that y is the true label for a given input For example, in classification, we can choose P Y to be the space of categorical distributions over Y, and f may be a neural network whose last layer is a softmax layer with |Y| outputs. Then, f (y | x) = f (x) y . Alternatively, in regression, we can choose P Y to be the space of Gaussian distributions, and f may be a neural network whose last layer outputs the values (µ, σ) ∈ R × R >0 of a Gaussian distribution. Then, , and N (·; µ, σ 2 ) is the Gaussian density function with mean µ and variance σ 2 .
Training a probability forecaster. To train a probability forecaster, we use a standard approach to calibrated prediction that combines maximum likelihood estimation with temperature scaling. 2 First, we consider a parametric model family Note that Φ can be high-dimensional-e.g., the weights of a neural network model. Given a training set We could now use fφ as the probability forecaster. However, the problem with directly usingφ is that becauseφ may be high-dimensional, it often overfits the training data Z train . Thus, the probabilities are typically overconfident compared to what they should be.
To reduce their confidence, we use the temperature scaling approach to calibrate the predicted probabilities (Platt, 1999;Guo et al., 2017). Intuitively, this approach is to train an MLE estimate using exactly the same approach used to trainφ, but using a single new parameter τ ∈ R >0 . The key idea is that this time, the model family is based on the parametersφ from (4). In other words, the "shape" of the probabilities forecast by fφ are preserved, but their exact values are shifted.
More precisely, consider the model family Then, we have the following MLE for τ : Note thatτ is estimated based on a second training set Z train . Because we are only fitting a single parameter, this training set can be much smaller than the training set Z train used to fitφ.
Parametric family of confidence set predictors. Finally, given a probability forecaster f , we consider one dimensional parameter space Θ = R; in an analogy to the temperature scaling technique for calibrated prediction, we denote this parameter by T ∈ Θ. In particular, we assume a confidence probability predictor f is given, and consider In other words, C T (x) is the set of y with high probability given x according to f . Considering this scalar parameter space, we denote the minimum of (3) byT .

CHOICE OF SIZE METRIC S(T )
To choose the size metric S(T ), we note that for our chosen parametric family of confidence set predictors, smaller values correspond to uniformly smaller confidence sets-i.e., T ≤ T ⇒ ∀x, C T (x) ⊆ C T (x). Thus, we can simply choose the size metric to be S(T ) = T.
(6) This choice minimizes the size of the confidence sets produced by our algorithm.

CHOICE OF CONFIDENCE LEVEL α(n, , δ)
Naive approach based on VC generalization bound. A naive approach to choosing α(n, , δ) is to do so based on the VC dimension generalization bound (Vapnik, 1999). It is not hard to show that the problem of estimatingT is equivalent to a binary classification problem, and that the VC dimension of Θ for this problem is 1. Thus, the VC dimension bound implies that for all T ∈ Θ, The details of this equivalence are given in Appendix B.2. Then, suppose we choose With this choice, for the solutionT of (3) with α = α(n, , δ), the constraint in (3) ensures that L(CT ; Z val ) ≤ α(n, , δ). Together with the VC generalization bound (7), we have P Zval∼D n L(CT ) > < δ, which is exactly desired the PAC constraint on our predicted confidence sets.
Direct generalization bound. In fact, we can get better choices of α by directly bounding generalization error. For instance, in the realizable setting (i.e., we always haveL(CT ; Z val ) = 0), we can get rates of n =Õ(1/ ) instead of n =Õ(1/ 2 ) (Kearns & Vazirani, 1994); see Appendix A.2 for details. We can achieve these rates by choosing α = 0, but then, the PAC guarantees we obtain may actually be stronger than desired (i.e., for < ). Intuitively, we can directly prove a bound that interpolates between the realizable setting and the VC generalization bound-in particular: Theorem 1. For any ∈ [0, 1], n ∈ N >0 , and k ∈ {0, 1, ..., n}, we have We give a proof in Appendix B.2. Based on Theorem 1, we can choose

THEORETICAL GUARANTEES
We have the following guarantee, which follows straightforwardly from Theorem 1: Corollary 1. LetT be the solution to (3) for α = α(n, , δ) chosen according to (8). Then, we have In other words, our algorithm is probably approximately correct.

PRACTICAL IMPLEMENTATION
Our algorithm for estimating a confidence set predictor CT is summarized in Algorithm 1. The algorithm solves the optimization problem (3) using the choices of Θ, S(T ), and α(n, , δ) described in the preceding sections. There are two key implementation details that we describe here.
Computing α(n, , δ). To compute α(n, , δ), we need to solve (8). A straightforward approach is to enumerate all possible choices of k ∈ {0, 1, ..., n}. There are two optimizations. First, the objective is monotone increasing in k, so we can enumerate k in ascending order until the constraint no longer holds. Second, rather than re-compute the left-hand side of the constraint k i=0 we can accumulate the sum as we iterate over k. We can also incrementally compute n i , i , and (1 − ) n−i . For numerical stability, we perform these computations in log space.

Solving (3). To solve (3), note that the constraint in (3) is equivalent to
Also, note that k * = n · α(n, , δ) is an integer due to the definition of α(n, , δ) in (8). Thus, we can interpret (9) as saying that E(x, y; T ) = 1 for at most k * of the points (x, y) ∈ Z val .
In addition, note that E(x, y; T ) decreases monotonically as fφ ,τ (y | x) becomes larger. Thus, we can sort the points (x, y) ∈ Z val in ascending order of fφ ,τ (y | x), and require that only the first k * points (x, y) in this list satisfy E(x, y; T ) = 1. In particular, letting (x k * +1 , y k * +1 ) be the (k * +1)st point, (9) is equivalent to In other words, this constraint says that T must satisfy y k * +1 ∈ C T (x k * +1 ). Finally, the solutionT to (3) is the smallest T that satisfies (10), which is the T that makes (10) hold with equality-i.e., We have assumed if not, we decrement k * until this holds.

PROBABILITY FORECASTERS FOR SPECIFIC TASKS
We briefly discuss the architectures we use for probability forecasters for various tasks. We give details, including how we measure the sizes of predicted confidence sets C T (x), in Appendix C. We consider three tasks: classification, regression, and model-based reinforcement learning. For classification, we use the standard approach of using a soft-max layer to predict label probabilities f (y | x). For regression, we also use a standard approach where the neural network predicts both the mean µ(x) and covariance Σ(x) of a Gaussian distribution N (µ(x), Σ(x)); then, f (y | x) = N (y; µ(x), Σ(x)) is the probability density of y according to this Gaussian distribution.
Finally, for model-based reinforcement learning, our goal is to construct confidence sets over trajectories predicted using a learned model of the dynamics. We consider unknown dynamics g * (x | x, u) mapping a state-action pair (x, u) to a distribution over states x , and consider a known (and fixed) policy π(u | x) mapping a given state x to a distribution over actions u ∈ U ⊆ R d U . Then , and our goal is to construct confidence sets for the predictions of f . However, we want to do so for not just for one-step predictions, but for predictions over a time horizon H ∈ N. In particular, given initial state x 0 ∈ X , we can sample x * 1: Then, our goal is to construct a confidence set that contains x * 1:H ∈ X H with high probability (over both the randomness in an initial state distribution x 0 ∼ d 0 and the randomness in f * ).
To do so, we construct and use a forecasterf (x 1:H | x 0 ) based on f . In principle, this task is a special case of multivariate regression, where the inputs are X (i.e., the initial state x 0 ) and the outputs are Y = X H (i.e., a predicted trajectory x 1:H ). However, the variance Σ(x) predicted by our probability forecaster is only for a single step, and does not take into account the fact that x is itself uncertain. Thus, we use a simple heuristic where we accumulate variances over time. More precisely, we construct (i) the predicted meanx 1: We use a probability forecasterf (x 1:H | x 0 ) = N (x 1:H ;x 1:H ,Σ 1:H ) to construct confidence sets.

EXPERIMENTS
We describe our experiments on ImageNet (a classification task), a visual object tracking benchmark (a regression task), and the half-cheetah environment (a model-based reinforcement learning task). We give additional results in Appendix D. We show the results in Figure 1. In (a), we compare our approach to an ablation. In particular, C refers to performing an initial temperature scaling step to calibrate the neural network predictor (i.e., using fφ instead of fφ ,τ ), and (ii) D refers to using Theorem 1 instead of the VC generalization bound. Thus, C + D refers to our approach. As can be seen, using calibrated predictor produces a noticeable reduction in the maximum confidence set size.
We also compared to the ablation C-i.e., using the VC generalization bound. However, we were unable to obtain valid confidence sets for our choice of and δ-i.e., (3) is infeasible. That is, using Theorem 1 outperforms using the VC generalization bound since the VC bound is too loose to satisfy the PAC criterion for our choice of parameters. In addition, in Table 6 in Appendix D, we show results for larger choices of and δ; these results show that our approach substantially outperforms the ablation based on the VC bound even when the VC bound produces valid confidence sets.
In (b), we show the confidence set sizes for images correctly vs. incorrectly labeled by ResNet. As expected, the sizes are substantially larger for incorrectly labeled images. Finally, in (c) and (d), we show how the sizes vary with and δ, respectively. As expected, the dependence on is much more pronounced (note that δ is log-scale).
Visual object tracking. We apply our confidence set prediction algorithm to a 2D visual singleobject tracking task, which is a multivariate regression problem. Specifically, the input space X consists of the previous image, the previous bounding box (in R 4 ), and the current image. The output space Y = R 4 is a current bounding box. We use the regression-based tracker from Held et al. (2016), and retrain the regressor neural network to predict the mean and variance of a Gaussian distribution. More precisely, our object tracking model predicts the mean and variance of each bounding box parameter-i.e., (x min , y min , x max , y max ). Given this bounding box forecaster fφ, we calibrate and estimate a confidence set predictor as described in Section 3.6.
We use the visual object tracking benchmark from Wu et al. (2013) to train and evaluate our confidence set predictor. This benchmark consists of 99 video sequences labeled with ground truth bounding boxes. We randomly split these sequences to form the training set for calibration, validation set for confidence set estimation, and test set for evaluation. For each sequence, a pair of two adjacent frames constitute a single example. Our training dataset contains 20,882 labeled examples, each consisting of of a pair of consecutive images and ground truth bounding boxes. The validation set for confidence set estimation and test set contain 22,761 and 22,761 labeled examples, respectively. Figure 2 shows the sizes of the predicted confidence sets; the sizes are measured as described in Section 3.6 for regression tasks. As for ResNet, we omit results for the VC bound ablation since n is too small to get a bound. The trends are similar to the ones for ResNet.
Half-cheetah. We use our algorithm to compute confidence sets for a probabilistic neural network dynamics model (Chua et al., 2018) for the half-cheetah environment (Brockman et al., 2016), for = 0.01, δ = 10 −5 , H = 20 time steps, and n = 5000 validation rollouts. When using temperature scaling to calibrate fφ to obtain fφ ,τ , we calibrate each dimension of time steps independently (i.e., we fit H parameters, where H is time horizon). We show the results in Figure 3. In (a), we compare to two ablations. The labels C and D are as for ResNet; in addition, A refers to using the accumulated varianceΣ t instead of the one-step predicted variances Σ t = Σ(x t−1 ). Thus, A + C + D is our approach. As before, we omit results for the ablation using the VC generalization bound since n is so small that the bound does not hold for any k for the given and δ. In (b), we show the same ablations over the entire trajectory until t = 20. As can be seen, using the calibrated predictor produces a large gain; these gains are most noticeable in the tails. Using the accumulated confidence produces a smaller, but still significant, gain. In (c) and (d), we show how the sizes vary with and δ, respectively. The trends are similar those for ResNet.

CONCLUSION
We have proposed an algorithm for constructing PAC confidence sets for deep neural networks. Our approach leverages statistical learning theory to obtain theoretical guarantees on the predicted confidence sets. These confidence sets quantify the uncertainty of deep neural networks. For instance, they can be used to inform safety-critical decision-making, and to ensure safety with highprobability in robotics control settings that leverage deep neural networks for perception. Future work includes extending these results to more complex tasks (e.g., structured prediction), and handling covariate shift (e.g., to handle policy updates in reinforcement learning).  In this section, we discuss why temperature scaling can help improve the predicted confidence sets. A concern is that temperature scaling does not change the ordering of label probabilities. Thus, we may expect that temperature scaling does not affect the predicted confidence sets. However, this fact only holds when considering a single input x-i.e., the ordering of the probabilities p(y | x) for y ∈ Y is not changed by temperature scaling. Indeed, the order of confidences for labels for different inputs can change. For a concrete example, consider two inputs x and x , and the case Y = {0, 1, 2}. Assume that the label probabilities are Now, if we take temperature τ very large, then the labels become roughly As a consequence, there are confidence sets that are achievable when using f τ that are not achievable when using f . In particular, the confidence sets can be achieved using f τ (e.g., with e −T = 2/5). However, it is impossible to achieve these confidence sets using f for any choice of T , since if 1 ∈ C T (x ), then it must be the case that C T (x) = {0, 1, 2}. Intuitively, we expect calibrated prediction to improve the ordering of probabilities across different inputs. Our experiments support this intuition, since they show that empirically, using calibrated predictors f τ produces confidence sets of smaller size.

A.2 USEFULNESS OF DIRECT BOUND
One key design choice is to use a specialized generalization bound that directly provides PAC guarantees on our confidence sets rather than simply applying the VC dimension bound. The easiest way to determine which bound is better is to examine which one produces a smaller confidence set. In our approach, the size of the confidence set decreases monotonically with the choice of α = α(n, , δ) in (3). Thus, the bound that produces larger α is better. Recall that the VC dimension bound produces α VC (n, , δ) = − log(2n) + 1 − log(δ/4) n , whereas our direct bound produces (for k = 0) Directly comparing these two choices of α is difficult, but our experiments show empirically that using the direct bound outperforms using the indirect bound.
A more direct way to compare the two approaches is to instead ask how large n needs to be to achieve α(n, , δ) = 0. For α VC , it is easy to check that we need n ≥ log(2n) + 1 + log(4/δ) 2 .
Thus, we need n to be at least O(log(1/δ)/ 2 ) (and possibly greater, to account for the log(2n) term). In contrast, for our direct bound, α = 0 corresponds to the case k = 0. To achieve k = 0, it suffices to have n satisfying (1 − ) n < δ. Using (1 − ) n ≤ e −n , it suffices to have n satisfying n ≥ log(1/δ) . In other words, n only needs to be O(log(1/δ)/ ). For small (e.g., = 0.01), we need 100× fewer samples to achieve the same size confidence set (i.e., with choice α(n, , δ) = 0). In Figure 4 (right), we compute the exact values of n needed to get α(n, , δ) = 0 as a function of for each bound (fixing δ = 10 −5 ). As expected, our bound requires substantially smaller n. Figure 4 (right), we compare the magnitude of n needed to achieve larger values of α using our direct bound; for simplicity, we actually consider larger values of k (where α = k/n), but the qualitative insights are the same. As can be seen, even for large k, (e.g., k = 50), the number of samples increases, but not substantially.

B THEORETICAL GUARANTEES B.1 ASSUMPTIONS
We make two additional technical assumptions in Theorem 1, both of which are standard. First, we assume that f is measurable; this assumption holds for all models used in practice, including neural networks (e.g., it holds as long as f is continuous).
Second, letting φ : Z → R, where Z = X × Y, be defined by φ((x, y)) = − log f (y | x), we assume that the distributionD induced by φ on R has continuous cumulative distribution function (CDF). More precisely, letting µ D be the measure defining D, thenD is defined by the measure where φ −1 : R → 2 Z is the inverse of φ in the sense that z ∈ φ −1 (φ(z)) for all z ∈ Z. Then, we assume that the CDF corresponding toD is continuous. This second assumption is standard in statistical learning theory (Kearns & Vazirani, 1994). Essentially, it says that for any t ∈ R, the probability that t = − log f (y | x) must equal zero. This assumption should hold unless p(x, y) or f (y | x) are degenerate in some way. Furthermore, we can detect this case. In particular, the failure mode corresponds to the case that we see multiple points with the same value − log f (y | x). Thus, choosingT = − log f (y | x) would include all these points, so the realized error rate α is larger than desired forT . In this case, we can simply choose a slightly largerT to avoid this problem.

B.2 PROOF OF THEOREM 1
At a high level, our proof proceeds in three steps. First, we show that a confidence set predictor C T can be encoded as a binary classifier M T . Second, we show that a PAC bound for M T implies a PAC bound for C T (where in both cases, the unknown parameter is T ∈ R). Third, we prove PAC bounds on the error of MT ; by the second step, these bounds complete our proof.
Encoding C T as a binary classifier M T . We begin by showing how the problem of learning a PAC confidence set predictor C T reduces to the problem of learning a PAC binary classifier M T . First, we show that for any T ∈ R, the confidence set predictor C T can be encoded as a binary classifier M T . Consider any parameter T ∈ Θ = R. Recall that we use the model f (y | x) to construct the confidence set predictor Here, I[s] is the indicator function, which returns one if a statement s is true and zero otherwise. We claim that To see this claim, note that as claimed.
PAC bound for M T implies PAC bound for C T . Next, we show that a PAC bound for M T implies a PAC bound for C T . More precisely, we design a data distributionD and loss˜ , and show that (i) the distribution ofT (trained to optimize M T ) is the same as the distribution ofT (constructed using our algorithm), and (ii) a PAC bound for MT (whereT is trained on data fromD) implies a PAC bound for CT . We show that as a consequence, a PAC bound on MT implies a PAC bound on CT .
We begin by constructingD and˜ . To this end, recall that D is a given distribution over X × Y.
We define a data distributionD overX ×Ỹ, whereX = R andỸ = {0, 1}, as follows. The first component ofD is the distribution overX induced by φ from D, and the second component is the distribution overỸ that places all probability mass on 1. Formally,D exists assuming φ is measurable, so the induced distribution exists; for all our choices of f (i.e., categorical or Gaussian), this property is satisfied. Then, where µD is the measure encodingD, and µ D is the measure encoding D. Now, we show (i) above. In particular, we claim thatT (Z) has the same distribution asT (Z), where Z ∼ D n andZ ∼D n are random datasets. To this end, define Φ : Z n →Z n by Φ ((z 1 , ..., z n )) = ((φ(z 1 ), 1), ..., (φ(z n ), 1)).

Note thatL
from which it follows that By construction of Φ, the random variablesZ and Φ(Z) have the same distribution; thus, it follows that the random variablesT (Z) andT (Φ(Z)) have the same distribution as well. SinceT (Z) = T (Φ(Z)), it follows thatT (Z) has the same distribution asT (Z), as claimed.
Next, we show (ii) above. In particular, we claim that a PAC bound for MT (Z) -i.e., implies a PAC bound for CT (Z) -i.e., where the true losses arẽ Note that it suffices to show that the true loss for C T equals the true loss for M T -i.e., since this equation (together with the PAC bound for MT (Z) ) implies Now, using the change of variables t → φ(z), we havẽ Then, using (12), we haveL as claimed.
Finally, combining (i) and (ii), we have where the first equality follows since (i) says thatT (Z) (where Z ∼ D n ) has the same distribution asT (Z) (whereZ ∼D n ), and the second inequality follows by (ii).
Generalization bound. Finally, we prove the PAC bound for MT , where δ 0 = k i=0 n i i (1 − ) n−i ; for conciseness, we have dropped the dependence ofT onZ. By the previous step, this bound implies the theorem statement. To this end, we first simplify the left-hand side of the inequality (13). In particular, let T * be the smallest T for which L(M T * ) = ; such a T * exists by our assumption thatD has continuous density function.
First, we claim that T < T * impliesL(M T ) >L(M T * ). Assuming T < T * , theñ Assuming T ≥ T * , we can similarly show thatL(MT ) ≤L(M T * ). It follows that As a consequence, (13) is equivalent to Next, recall thatT must satisfyL(MT ;Z) ≤ α, wherẽ AssumingT < T * , and using k = n · α, it follows that k ≥ As a consequence, we have By our definition of T * , the event in the final expression says that the sum of n i.i.d. Bernoulli random variables I[t > T * ] ∼ Bernoulli( ) is at most k. Thus, this event follows a distribution Binomial(n, ), so as claimed. The theorem statement follows.

C DETAILS ON PROBABILITY FORECASTERS FOR SPECIFIC TASKS
In this section, we describe architectures for probability forecasters for classification, regression, and model-based reinforcement learning.
Classification. For the case Y = {1, ..., Y }, we choose the probability forecaster f to be a neural network with a softmax output. Then, we can compute a given confidence set by explicitly enumerating y ∈ Y. We measure the size of C T (x) as |C T (x)|.
Regression. For the case Y = R, we choose the probability forecaster f to be a neural network that outputs the parameters (µ, σ) ∈ Y × R >0 of a Gaussian distribution. Then, we have

This choice generalizes to
We measure the size of C T (x) as Λ F , where · F is the Frobenius norm.
Model-based reinforcement learning. In model-based reinforcement learning, the goal is to predict trajectories based on a model of the dynamics. We consider an MDP with states X ⊆ R d X , actions U ⊆ R d U , an unknown distribution over initial states x 0 ∼ d 0 , and unknown dynamics g * (x | x, u) mapping a state-action pair (x, u) ∈ X × U to a distribution over states x ∈ X . We assume a fixed, known policy π(u | x), mapping a state x ∈ X to a distribution over actions u ∈ U. The (unknown) closed-loop dynamics are f * (x | x) = E π(u|x) [g * (x | x, u)].
Given initial state x 0 ∈ X and time horizon H ∈ N, we can sample a trajectory x * 1:H = (x * 1 , ..., x * H ) ∼ f * by setting x * 0 = x 0 and sequentially sampling x * t+1 ∼ f * ( · | x * t ) for t ∈ {0, 1, ..., H−1}. Our goal is to predict a confidence set C T (x 0 ) ⊆ X H that contains x * 1:H ∈ X H with high probability (according to both the randomness in initial states x 0 ∼ d 0 and in f ). This problem is a multivariate regression problem with inputs X and outputs Y = X H .
To account for the fact that the variances accumulate over time, we sum them together to obtain the predicted variancesΣ 1:H -i.e., Then, we use the probability forecastf (x 1:H ,Σ 1:H ) = N (x 1:H ,Σ 1:H ) (where we think ofx 1:H as a vector in R H·d X andΣ 1:H as a block diagonal matrix in R (H·d X )×(H·d X ) ) to construct confidence sets.
Finally, we describe how we measure the size of a predicted confidence set C T (x 0 ) ⊆ X H . In particular, note that C T (x 0 ) has the form i.e., C T,t (x 0 ) is the confidence set for the state x t reached after t time steps. Then, we measure the size of the confidence set for each component C T,t (x 0 ) (for t ∈ {1, ..., H}) individually, and take the average. As in the case of regression, C T,t (x 0 ) is an ellipsoid C T,t (x 0 ) =x t + Λ t S d X −1 ; then, the size of C T (x 0 ) is H −1 H t=1 Λ t F . An additional detail is that when we calibrate this forecaster, we calibrate each component C T,t (x 0 ) individually-i.e., we use H calibration parameters τ 1 , ..., τ H .

D.1 COMPARISON TO ADDITIONAL BASELINES
We compare to two baselines that do not have theoretical guarantees. We assume given a probability forecaster f (y | x). Then, given an input x ∈ X , we construct the confidence set to satisfy More precisely, we first rank the labels in decreasing order of f (y | x), to obtain a list (y 1 , y 2 , ..., y |Y| ). Then, we choose the smallest k such that (14) holds for C(x) = {y 1 , ..., y k }. Intuitively, if the probabilities f (y | x) are correct (i.e., f (y | x) is the true probability of y given x), then this confidence set should contain the true label y with high probability.
For regression, we cannot explicitly rank labels y ∈ Y ⊆ R d , but they are monotonically decreasing away from the mean. Then, assuming f (y | x) = N (y; µ(x), Σ(x)) is Gaussian, we take an ellipsoid of shape Σ(x) around µ(x) with minimum radius that captures 1 − of the probability mass of f (y | x). More precisely, we choose Conf. set size Figure 6: Confidence set sizes for two neural network architectures trained on ImageNet; for both, we use n = 20, 000, = 0.01 and δ = 10 −5 . Left: AlexNet (Krizhevsky, 2014); here, the empirical confidence set error of our approach C + D is 0.0066. Right: GoogLeNet (Szegedy et al., 2015); here, the empirical confidence set error of our approach is 0.0061.
where C T (x) = {y ∈ Y | f (y | x) ≥ e −T } as before. Note that unlike our algorithm, the threshold T (x) is not a learned parameter, but is computed independently for each new input x. We can solve forT (x) efficiently by changing basis to convert f (y | x) to a standard Gaussian distribution, and then using the error function to compute the cutoff that includes the desired probability mass.
In Figure 5, we compare the confidence sets constructed using this approach with (i) the forecaster fφ(y | x) without any calibration, and (ii) the calibrated forecaster fφ ,τ (y | x). We plot both the confidence set sizes and the empirical error rates. For the latter, recall that a confidence set predictor C is correct if L(C) < , where L(C) the true error rate. However, we cannot measure L(C); instead, we approximate it on a held-out test set Z test ⊆ X × Y-i.e., L(C) ≈L(C; Z test ), wherê Intuitively,L(C; Z test ) is the fraction of inputs (x, y) ∈ Z test such that the predicted confidence set for x does not contain y. We say a confidence set C is empirically valid whenL(C; Z test ) < . Recall that our algorithm guarantees correctness with probability at least 1 − δ, where δ = 10 −5 .
As can be seen, the baseline approaches are not empirically valid in all cases. In one case-namely, the baseline with the calibrated forecaster on ImageNet-the confidence sets are almost empirically valid. However, in this case, the confidence sets are much larger than those based on our approach, despite the fact that the error rate of our confidence sets are empirically valid. Thus, our algorithms outperform the baselines in all cases.

D.2 RESULTS ON ADDITIONAL IMAGENET NEURAL NETWORK ARCHITECTURES
We apply our approach to two additional neural network architectures for ImageNet: AlexNet (Krizhevsky, 2014) and GoogLeNet (Szegedy et al., 2015). Our results are shown in Figure 6. As can be seen, calibration reduces the confidence set sizes for AlexNet, but actually increases the confidence set sizes for GoogleNet. Thus, both calibrated and uncalibrated models may need to be considered when constructing confidence set predictors. Also, we find that confidence set sizes are correlated with classification error-the test errors for AlexNet, GoogleNet, and ResNet are 47.83%, 29.41%, and 21.34%, respectively, and their confidence set sizes decrease in the same order.

D.3 RESULTS ON ADDITIONAL CLASSIFICATION DATASETS
We apply our approach to three small classification datasets: an Arrhythmia detection dataset (Guvenir et al., 1997), a car evaluation dataset (Bohanec & Rajkovic, 1988), and a medical alarm dataset (Bonafide et al., 2017). The confidence set sizes are shown in Figure 7. We choose larger values of and δ since we cannot obtain confidence sets that satisfy the PAC criterion with smaller and δ when the number of validation examples n is too small. For all three datasets, the empirical confidence set error is smaller than the specified error ; thus, the constructed confidence sets are empirically valid. For these datasets, the confidence set sizes of our approach C + D and our approach without calibration D are similar, most likely due to the small number of class labels. We additionally ran our approach on a medical dataset where classification decisions are safety critical; thus, correct predicted confidence sets are required. In particular, we use the Children's Hospital of Philadelphia (CHOP) alarm dataset (Bonafide et al., 2017). This dataset consists of vital signs from 100 patients around one year of age. One of the vital signs is the oxygen level of the blood, and a medical device generates an alarm if the oxygen level is below a specified level. The labels indicate whether the generated alarm is true (y = 1) or false (y = 0). We use n = 1000, = 0.02, and δ = 10 −5 . The empirical confidence set error of our approach isL(C; Z test ) = 0.0159.
The key question is how many false alarms can be reliably detected using machine learning to help reduce alarm fatigue. We consider an approach where we use the predicted confidence sets to detect false alarms. In particular, we first train a probability forecaster f : X → P Y , where Y = {0, 1}, to predict the probability that an alarm is true, and then construct a calibrated confidence set predictor f : X → 2 Y based on this forecaster. We consider an alarm to be false if the predicted confidence set isf (x) = {0}-i.e., according to our confidence set predictor, the alarm is definitely false. Then, our PAC guarantee says that the alarm is actually false with probability at least 1 − . In summary, we suppress an alarm iff (x) = {0}. Using our approach, 176/630 (i.e., 27.94%) of false alarms are suppressed, while only 13/187 (i.e., 6.95%) true alarms are suppressed (see Figure 7 (d)).

D.4 RESULTS ON ADDITIONAL REGRESSION DATASETS
We ran our algorithm on two small regression baselines-the Auto MPG dataset (Quinlan, 1993) and the student grade dataset (Cortez & Silva, 2008). We show results in Figure 8. The parameters we use are = 0.1 and δ = 0.05; as with the smaller classification datasets, we use larger choices of and δ since we cannot construct valid confidence sets for smaller choices. For the Auto MPG dataset, the empirical confidence set error of our final model C + D isL(C; Z test ) = 0.0597, so these are empirically valid. For the student grade dataset, the error isL(C; Z test ) = 0.1250, which is slightly larger than desired; this failure is likely due to the fact that the failure probability δ = 0.05 is somewhat large.   Table 6 shows results for varying , δ on ResNet. Tables 7 & 8 show results for varying , δ on the Half-Cheetah. Table 9 shows visualizations of the confidence sets predicted for our object tracking benchmark.
barber chair, hand blower, medicine chest, paper towel, plunger, shower curtain, soap dispenser, toilet seat, tub, washbasin, washer, toilet tissue vulture, great grey owl, bittern tiger cat, lynx, leopard, snow leopard, jaguar, tiger, cheetah amphibian, cassette player, fire engine, minibus, minivan, passenger car, pole, police van, puck, racer, radio, school bus, screwdriver, streetcar, trolleybus junco, water ouzel, water snake, drake, red-breasted merganser, goose, crayfish, little blue heron, European gallinule, ruddy turnstone, red-backed sandpiper, redshank, dowitcher, oystercatcher, albatross, otter indigo bunting, bee eater, hummingbird, jacamar   Table 5: Confidence sets of ImageNet images with varying ResNet confidence set sizes. The predicted confidence set is shown to the right of the corresponding input image. The true label is shown in red, and the predicted label is shown with a hat. Conf. set size Table 6: Confidence set sizes for ResNet trained on ImageNet, for varying , δ and for n = 20, 000. The plots are as in Figure 1  Conf. set size (log-scale) Table 7: Confidence set sizes for a neural network dynamics model trained on the half-cheetah environment, for varying , δ and for n = 5000. The plots are as in Figure 3 Figure 3 (b). , and the bounding box produced using our confidence set predictor (green). We have overapproximated the predicted ellipsoid confidence set with a box. Our bounding box contains the ground truth bounding box with high probability.


Improving Dialogue State Tracking by Discerning the Relevant Context

A typical conversation comprises of multiple turns between participants where they go back and forth between different topics. At each user turn, dialogue state tracking (DST) aims to estimate user’s goal by processing the current utterance. However, in many turns, users implicitly refer to the previous goal, necessitating the use of relevant dialogue history. Nonetheless, distinguishing relevant history is challenging and a popular method of using dialogue recency for that is inefficient. We, therefore, propose a novel framework for DST that identifies relevant historical context by referring to the past utterances where a particular slot-value changes and uses that together with weighted system utterance to identify the relevant context. Specifically, we use the current user utterance and the most recent system utterance to determine the relevance of a system utterance. Empirical analyses show that our method improves joint goal accuracy by 2.75% and 2.36% on WoZ 2.0 and Multi-WoZ restaurant domain datasets respectively over the previous state-of-the-art GLAD model.

Introduction
Dialog state tracking (DST) is a vital component in the task-oriented dialog systems which is used to estimate user's goals and requests in order to plan next action and respond accordingly. At each turn, DST aims to identify the set of goals that a user aims to achieve and requests that are represented as slot-value pairs. Typically, this decision is made by considering user utterance in the current turn or system actions in the previous turn. However, in many cases, the considered user utterance or system actions do not present enough information and refers to a previous utterance.
As shown through an example in Figure 1, while exploring different available options, user Figure 1: An example dialog from WoZ 2.0 dataset. A turn contains user utterance (blue), system utterance (red), system actions (yellow) and turn label (green). Each turn is separated by a line.
can go back-and-forth between the currently and previously discussed facts. For instance, when offered with two different restaurant options namely Nirala (food=indian) and Golden Wok (food=chinese) in the second turn, user first inquires about the details of Golden Wok. And after getting relevant details about the Golden Wok in the following two turns, user refers back to the second option provided in second turn and asks about Nirala restaurant. To predict the correct slot-value pair food=indian in the dialog state of the fifth turn, the system is required to refer back to the second turn again to find information about Nirala, as the context obtained from the current dialog turn is insufficient.
Identifying such implicitly referenced historical turns is challenging since implicit references are not local and most recent turns are often not informative. Therefore, the traditional approach of modeling dialogue recency  may not suffice. Instead, we propose to model implicit references by storing links to the past turn where each of the slots was modified. Then at each turn, we look up though the stored links to find the previous turn which may provide additional cues for predicting the appropriate slot-value.
Moreover, the dialogue system often asks polar questions with yes-no answers. For instance, the DST system should update the dialogue state with food=indian when a user replies Yes to a system utterance Do you want Indian food?. In such cases, neither the user utterance nor system acts (food in this example) contain any information about the actual slot-value. This makes utilization of both system and user utterance eminent for dialog state tracking. However, utilizing the previous system utterance together with the current user utterance always at each turn may add noise. Therefore, we use a gating mechanism based on both utterances to determine the relevance of the previous system utterance in the current turn.
The evaluation shows that identifying the relevant context is essential for dialogue state tracking. Our novel model that discerns important details in non-adjacent dialogue turns and the previous system utterance from a dialog history is able to improve the previous state-of-the-art GLAD (Zhong et al., 2018) model on all evaluation metrics for both WoZ and MultiWoZ (restaurant) datasets. Furthermore, we empirically show that a simple self-attention based biLSTM model, using only one-third of the number of parameters as GLAD, outperforms GLAD by identifying and incorporating the relevant context.

Related Work
Early work for DST relied on separate Spoken Language Understanding (SLU) module (Henderson et al., 2012) to extract relevant information from user utterances in a pipelined approach. Such systems are prone to error accumulation from a separate SLU module, in absence of necessary dialog context required to interpret the user utterance. Thus, later work on DST moved away from separate SLU modules and inferred the dialog state directly from user utterance and dialog history (Henderson et al., 2014b,c;Zilka and Jurcicek, 2015). These models depend on delexicalization, using generic tags to replace specific slot types and values, and handcrafted semantic dictionaries. In practice, it is difficult to scale these models for every slot type and recent state-of-the-art models for DST use deep learning based methods to learn general representations for user and system utterances and previous system actions, and predict the turn state (Henderson et al., 2013(Henderson et al., , 2014bMrkšić et al., 2015Hori et al., 2016;Liu and Lane, 2017;Dernoncourt et al., 2017;Chen et al., 2016). However, these systems are found to perform poorly on rare and unknown slot-value pairs which was recently addressed through local slot-specific encoders (Zhong et al., 2018) and pointer network (Xu and Hu, 2018).
A crucial limitation to all these approaches lies in the modeling of appropriate historical context, which is simply ignored in most of the works. Since user's goal may change back-and-forth between previous values, incorporating relevant historical context is useful in monitoring implicit goal references. In a recent work, El  discussed on similar limitations of current DST task and introduced a new task of frame tracking that explicitly tracks every slot-values that were introduced during the dialogue. However, that significantly complicates the task by maintaining multiple redundant frames that are often left unreferenced. Our proposed model, that explicitly track relevant historical user and system utterances, can be easily incorporated into any known DST or frame tracking systems such as  to replace the recency encoding.

Discerning Relevant Context for DST
Similar to previous works, we decompose the multi-label classification problem to binary classification where we score each slot-value pair and select the ones that receive a score above a threshold to be included in the current dialog state. To predict the score for a candidate slot-value pair, the model uses the relevant past user utterance (referential utterance), a fused utterance composed using the current user utterance and the system utterance of the previous turn, as well as previous system actions as evidence. Shown in Figure 2, our model comprises of: Lookup module: retrieves a link to the turn where each of the slots changes. At each step, our system refers to the lookup module that returns the past user utterance (the "antecedent user utterance")  where the candidate slot-type was modified as well as outputs the previous slot-value.
GLE modules: Each of the five green modules in Figure 2 is a global-locally self-attentive encoder (GLE module) (Zhong et al., 2018) that encodes each type of evidence into a vector representation (c). Each input is represented as a sequence of words which is encoded to a vector representation via global-local self-attentive encoder (GLE) module (Zhong et al., 2018). Specifically, GLE employs local slot-specific bidirectional LSTMs and a global bidirectional LSTM (Hochreiter and Schmidhuber, 1997) that is shared across all slots for encoding the input sequence into a sequence of hidden states (H), followed by a self-attention layer (Lin et al., 2016) to obtain a fixed dimension vector representation (c). The GLE modules are used to encode the antecedent user utterance (H u p , c u p ), the current user utterance (H u , c u ), the previous system utterance (H s , c s ), each of the system acts (H a i , c a i ), as well as the previous slot-value (H v p , c v p ) and the candidate (H v , c v ) slot-value.
Referential Context Scorer: uses the candidate slot value (c v ), the antecedent user utterance as well as the previous slot-value to determine if the candidate slot value was referenced in the antecedent utterance. Specifically, the scorer uses the representation of the candidate slot value c v to attend over hidden states of the antecedent user utterance and the previous slot-value, H u p and H v p , and then computes attention weights for each of the hidden states. Next, the scorer sums up the hidden states weighed with the calculated attentions to get the summary context (Equation 1). Finally, the scorer applies a linear neural layer to calculate the scores y v p and y u p representing the likelihoods that the candidate slot-value is differ-ent from the previous slot-value and the candidate slot-value was unreferenced in the antecedent utterance (Equation 2).
Fusion Scorer: leverages necessary details in the previous system utterance to enrich the current user utterance. First, we use a gating mechanism based on c s and c u that determines the relevance of the previous system utterance in the current turn. We concatenate c s and c u and use a linear layer with sigmoid activation to calculate the score α (Equation 3). Then, we use attention from c v over H s and H u to calculate context summaries (l s , l u ), and combine the summary vectors by taking their normalized weighted sum based on α. We finally apply a single linear layer to calculate the score y f that determines the likelihood of the candidate slot-value based on both the current user utterance and the previous system utterance (Equation 4).
System Act Scorer: is the same as the action scorer proposed by (Zhong et al., 2018). Specifically, The scorer uses attention from c u over C a to calculate action summary followed by a linear layer with sigmoid activation to calculate the score y a that determines the relevance of the candidate slot-value based on the previous system actions (Equation 5).
It then calculates the final score of the candidate slot-value by taking weighted sum of the four scores (y u p , y v p , y f , y a ) followed by a sigmoid layer, where weights are learned in the network.

Experimental Setup
We primarily use WoZ 2.0 (Wen et al., 2017) restaurant reservation task dataset that consists of 1200 dialogues for training and evaluation. Each dialogue has an average of eight turns, where each turn contains system utterance transcript, user utterance transcript, turn label and belief state. All the dialogue states and actions are based on a task ontology that supports three different informable slot-types namely price range with 4 values, food with 72 values, area with 7 values, and requests of 7 different types like address and phone. Following the standard settings, we use 600 dialogues for training, 200 for validation and the remaining 400 for testing.
We also use dialogues from restaurant domain in MultiWoZ 2.0 dataset (Budzianowski et al., 2018) for secondary evaluation. It banks on a significantly complex ontology covering seven informable slot types with 276 different values (food, price range, restaurant name, area, book time, book day and book people with 97, 6,105,8,43,8 and 9 values respectively). We use standard training, validation and test splits of 1199, 50 and 61 dialogues respectively.
All the models on WoZ 2.0 are evaluated on the two standard metrics introduced in Henderson et al. (2014a). First, Joint Goal Accuracy is the percentage of turns in a dialogue where the user's informed joint goals are identified correctly. Joint goals are accumulated turn goals up to the current dialog turn. Second, Turn Request Accuracy calculates the percentage of turns in a dialogue where the user's requests were correctly identified. Models on MultiWoZ 2.0 dataset are evaluated using joint goal and turn inform accuracies, as used by Nouri and Hosseini-Asl (2018).

Implementation Details
We use pretrained GloVe word embeddings (Pennington et al., 2014) Table 1: Test accuracy of baselines and proposed models on WoZ 2.0 restaurant reservation dataset. †Retrained using docker container provided by the authors with exactly same hyper-parameters. We also experimented with different versions of PyTorch and cuDNN and found that results had high variance. Therefore, we report the average performance over 5 runs with different initializations for GLAD and all our models.  ter n-gram embeddings (Hashimoto et al., 2017) which are kept fixed during the training. Each of bi-LSTMs use 200 hidden dimensions. All the models are trained using ADAM optimizer (Kingma and Ba, 2014) with the initial learning rate of 0.001. Dropout rate (Srivastava et al., 2014) is set to 0.2 for all biLSTM modules and the embedding layer. The models are trained for a maximum of 100 epochs with a batch size of 50. The validation data was used for early stopping and hyperparameter tuning. Table 1 compares the performance of our proposed models with different baselines, including delexalisation-based model + SD , DNN and CNN variants of neural belief tracker  and the previous state-of-the-art GLAD systems (Zhong et al., 2018) on WoZ 2.0 dataset. We also implement a simplified variant of GLAD, Global BiLSTM  based GLE, by removing slot-specific local biL-STMs from the GLE encoder. We then successively combine it with referential context (Global biLSTM based GLE + RC) and the fused previous system utterance (Global biLSTM based GLE + RC + FS). Finally, we directly incorporate the referential context and gate selected system utterance into the GLAD system (GLAD + RC + FS).

Results
Irrespective of the underlying system, utilizing appropriate context from the previous turns improves the overall performance of a dialogue state tracker on both joint goal and turn request accuracies on WoZ 2.0 dataset. First, incorporating relevant referential utterances to identify implicitly mentioned slot-value improves the accuracy of global biLSTM based GLE model on joint goal task by 2.4%. Then, gating based mechanism to augment user utterance with relevant information from the previous system utterance further improves the joint goal accuracy by 1.0%. Together, they improve joint goal and request accuracy of the global biLSTM based GLE model by 3.4% and 0.2% respectively. Furthermore, as evident from the results in Table 2, both referential context and fused system utterance proportionally improve performance on MultiWoZ 2.0 dataset as well with overall improvement of 2.36% and 1.77% on joint goal and turn inform accuracies respectively. Performances of all models on Mul-tiWoZ 2.0 are significantly inferior compared to WoZ 2.0 owing to higher complexity, with richer and longer utterances and considerably more slotvalues in the former dataset.

Analysis
The utilization of relevant context results in significant reduction in the number of learnable parameters in the model as shown in Table 3. Relevant context with the baseline model is able to outperform GLAD while using only one third of the number of learnable parameters. The parameters added due to using relevant context are the parameters for encoding the antecedent referential user utterance and the previous system utterance as well as the past utterance and past slot-value scorers. However, we also observe high variance in the joint goal accuracy. Since joint goal is calculated by accumulating turn goals, an error in predicting a turn goal is propagated to all the downstream turns.

Conclusion
We have presented a novel method for identifying the relevant historical user utterance as well as determining the relevance of the system utterance from the last turn to enrich the current user utterance and improve goal tracking in dialogue systems. The experimental results show that discerning relevant context from the dialog history is crucial for tracking dialog states.


extfieldsofstudy:
Computer Science
Mathematics

text:
Adversarial Examples Target Topological Holes in Deep Networks

It is currently unclear why adversarial examples are easy to construct for deep networks that are otherwise successful with respect to their training domain. However, it is suspected that these adversarial examples lie within some small perturbation from the network's decision boundaries or exist in low-density regions with respect to the training distribution. Using persistent homology, we find that deep networks effectively have ``holes'' in their activation graphs, making them blind to regions of the input space that can be exploited by adversarial examples. These holes are effectively dense in the input space, making it easy to find a perturbed image that can be misclassified. By studying the topology of network activation, we find global patterns in the form of activation subgraphs which can both reliably determine whether an example is adversarial and can recover the true category of the example well above chance, implying that semantic information about the input is embedded globally via the activation pattern in deep networks.

Introduction
Sophisticated machine learning systems with impressive performance can be induced to make errors on inputs that are surprisingly similar to examples the learned system handles correctly (Gilmer et al., 2018a;Serban & Poll, 2018), termed adversarial examples. Adversarial examples have become an important issue in machine learning research due to the potential risks to security and robustness of machine learning systems, spawning efforts to design optimization procedures with robustness guarantees (Kolter & Wong, 2018;J.D. et al., 2018), and theoretical work on the robustness and the cost landscape . Despite the intense research, there is substantial controversy about why adversarial attacks work, with hypotheses ranging from optimization, to generic properties of deep networks (e.g. the linearity hypothesis, to intrinsic characterizations of the data manifold (Serban & Poll, 2018)).
Recently, Gilmer et al (Gilmer et al., 2018b) have shown that adversarial examples are close in input space to correctly classified points, suggesting a complex manifold geometry for non-adversarial examples in the input space that might result from approximating the input distribution by a limited set of training examples. Alternatively, complex manifold structure could be created through the interaction between network topology and the input data distribution. Deep feedforward networks apply a composition of functions on the input that transform the input through a sequence of homomorphisms. This sequence of transformations has the potential to induce a complex partition structure on the input space, including "holes" where class-critical information can be lost. Here we explore this possibility using methods from topological data analysis to analyze the structure of network activations due to adversarial examples. We show that topological analyses may be used to both identify adversarial examples and extract the correct labels from the subgraph structure of the learned network's activations.

Related Work
Various defense methods for adversarial examples have been proposed, such as defensive distillation (Papernot et al., 2016), feature squeezing (Xu et al., 2017), gradient masking or obfuscated gradient (Buckman et al., 2018;Ma et al., 2018;Samangouei et al., 2018), and adversarial training (Madry et al., 2017). Recent works have also focused on the detection of adversarial examples as a substitute for outright robustness. These methods look to classify adversarial examples based on features extracted from different layers of a deep network. Recent detection schemes include classifiers based on activation geometry via k-nearest neighbors (Katzir & Elovici, 2018), a detector based on the PCA projection of filters (Li & Li, 2017), or a learning framework that covers unexplored space in vulnerable models (Rouhani et al., 2018).
In addition to the numerous defense methods that have recently been proposed, recent insights have emerged, providing progress towards a fundamental understanding of adversarial examples. Most notably, Katz et al. (Katz et al., 2017) and Weng et al. (Weng et al., 2018)  LG] 28 Jan 2019 that computing a provably secure region of the input space is approximately computationally hard. Mahloujifar et al. (Mahloujifar et al., 2018) explain the prevalence of adversarial examples by making a connection to the "concentration of measure" in metric spaces. Recently, Zhange et al. (Zhang et al., 2019) found that adversaries are more dense sufficiently far from the manifold of training data.

Persistent Homology
Persistent homology provides a method for computing topological features of a space across arbitrarily many resolutions of the space. The topological features that persist across multiple spatial scales may be interpreted as being "true" topological features of the space under study. The decomposition, or filtration, of the space corresponds to a choice of metric between points in the space. In the discrete setting, the space is typically represented by a simplicial complex with the filtration describing how the space is constructed based on the chosen metric.

SIMPLICIAL HOMOLOGY
Let K be a simplicial complex. Under Z 2 coefficients, a p-chain is a subset of p-simplices of K. The set of p-chains, together with addition, forms a free abelian group C p called the p-th chain group of K. The boundary ∂ p (σ) of a ksimplex σ is the set of its (p − 1)-faces, and that of a pchain is the addition of the boundaries of its simplices. The boundary operator defines a homomorphism ∂ p : C p → C p−1 .
Define a p-cycle to be a p-chain with empty boundary and a p-boundary to be a p-chain in the image of ∂ p+1 . The collection of p-cycles and p-boundaries are called the pth cycle group Z p = ker ∂ p and the p-th boundary group B p = im ∂ p+1 , respectively. Both are subgroups of C p . The p-th homology group is the quotient group H p (K) = Z p /B p . Elements of H p are the homology classes α+B p = {α + b | b ∈ B p } for p-cycles α. We refer to α as the generating cycle of the homology class [α] = α + B p . Two p-cycles α and γ are homologous if [α] = [γ], that is, α + γ ∈ B p is the boundary of some (p + 1)-chain.
The rank of H p is called the p-th Betti number of K, denoted by β p . A basis of H p is a minimal set of homology classes that generates H p . A set of p-cycles A = {α 1 , α 2 , . . . , α n } generates H p , if the set of generators {[α i ]} forms a basis for H p where |A| = β p .

PERSISTENT HOMOLOGY
Let K be a simplicial complex. A filtration is a nested sequence of subcomplexes ∅ = K 0 ⊂ K 1 ⊂ · · · ⊂ K n = K. In other words, the filtration is a description of how we want to construct K by adding arbitrary-sized chunks at a time. With persistent homology, we are interested in the topological evolution of K as it is deconstructed, which is expressed by the corresponding sequence of homology groups. Since K i ⊂ K i−1 , the inclusion of each subcomplex into the larger complex induces a homomorphism between homology groups, f p : H p (K i−1 ) → H p (K i ). The nested sequences of complexes shown above thus corresponds to a sequence of homology groups connected by homomorphisms, There exists this sequence of homology groups for each dimension p. The filtration defines a partial ordering on the simplices with σ ⊂ K i − K i−1 preceding τ ⊂ K j − K j−1 if i < j. This extends to a total ordering for appropriate choice for how simplices are ordered for each K i − K i−1 .
The rank of im f p is the number of p-dimensional homology classes that are born at or before K i and are still alive at K j . We can encode each h ∈ im f p as a point in the half plane where the x-axis encodes the level in the filtration i where h first has a preimage in H p (K i ), and the y-axis encodes the earliest level in the filtration j where the image of h in H p (K j ) is trivial. This half-plane representation is called a persistence diagram, denoted Dgm(f p ).
For two functions f p and g p , we can compare their persistence diagrams using the Wasserstein distance which is defined as the q-th root of the infimum, over all matchings between the points, of the sum of q-th powers of the distance between matchings: where q is a positive, real number. In the limit for q going to infinity, we get the bottleneck distance which is the length of the longest edge in the best matching. Persistence diagrams are stable with respect to the bottleneck distance (Cohen-Steiner et al., 2007).

Neural Network Topology
By viewing a neural network as an undirected graph-a topological space-we can use persistent homology to investigate its invariant topological properties across all edge weight resolutions. We consider only forward architectures in this construction, but a similar approach may be used to investigate more complex architectures with, for example, recurrent structure.
There are two ways to construct a graph representation of a neural network. These are the static network consisting of (possibly trained) weight matrices connecting each layer's nodes to the next layer's, and the induced network consisting of this same structure augmented by the activation functions and an input applied to the neural network. In this paper, we are concerned with the latter induced graphical structure, but both structures may be used to provide insight into the function of neural networks. Fix a feedforward neural network architecture with L layers. Let G I = (V, E, φ) be the network's graphical representation induced by input I. Here V is the set of nodes in the network including input, hidden, and output nodes, E is the set of edges between nodes, and φ : E → R is a function assigning weights to edges. G I is a multipartite graph where each node in a given layer may share an edge only with the previous and next layers' nodes. In other words, Define h l ∈ R |V l | to be the activation values for each node in layer l. Define h l u to be the u'th entry in vector h l . For notational simplicity, we will drop the layer l superscript when the layer is obvious. Let W l be the weight matrix connecting the node set V l to V l+1 . This weight matrix is either the true weight matrix if layer l is fully-connected, or if l is a convolutional layer, the unrolled filter matrix described below. Let the entry in W l corresponding to the v'th row and u'th column be denoted by w l u→v . Again, we will drop this layer superscript unless otherwise necessary. With this information, we define the edge weighting for We use the absolute value of the hidden activation times the corresponding weight parameter to align the ordering of simplices in the filtration with the corresponding relationship to network semantics where (high activation or high suppression) are more important to classification decisions, whereas activation values close to 0 are negligible in their semantic role.
The filtration of G I is defined via filtration on φ. We have N = |E| values of φ which can be ordered by ≥ such that max is defined by adding the corresponding edge (1-simplex) and vertices (0-simplices) of each ω i into the graph. In other words, G I 0 is the graph consisting of only the highest weight edge (the 1-simplex given by max E φ) along with the vertices (0-simplices) connected by that edge, G I 1 is the (potentially disjoint) graph consisting of the previously described edge and vertices along with the edge and vertices associated to ω 1 , etc.
The intuition for constructing the input-induced graph from a neural network is as follows. For each fully-connected layer, we connect each hidden node of layer l to each hidden node in layer l + 1 with an edge. The weight of this edge is the activation value of the hidden node multiplied by the corresponding element in weight matrix W l . The graphical construction for convolutional layers is similar but requires slightly more preprocessing. For each incoming channel, unroll the convolution operation into a (sparse) matrix multiplication operation. This multiplication operation operation then induces a graphical representation like in the fully-connected case. Because this operation is sparse, most of the edges have weight 0, indicating a stride of the filter whose preimage did not include that neuron. This sparsity can be easily filtered out as it does not affect the persistence calculation. Although not discussed in the paper, other forward architecture layer options like max pooling or bias weights can be translated to this graphical construction.

Persistent Subgraphs
With a filtration on G I , we can compute its persistent homology. We say a homology class α is born at G I i if it is not in the image of the map induced by the inclusion We call j −i the lifetime or persistence of the topological feature generated by α. The filtration on G I induces the sequence of homology groups The lifetime of a feature born at level i in the filtration and dying at level j in the filtration is precisely the rank of the persistent homology group H i,j p (G I ). For each dimension p, these persistent topological features can be represented as vectors in the half-plane via a persistence diagram ( Figure  2) where more persistent features are located farther off the diagonal, while features that may be considered topological noise are associated to points near or along the diagonal.
We are interested in zero-dimensional (p = 0) topological information within this paper. Higher-dimensional topological features like holes and voids can be analyzed using a similar formulation, but the interpretation of these features with respect to neural network classification performance is less clear. By contrast, zero-dimensional topological features in this network space correspond to connected components, with the homology sequence describing how various components are created and merged with larger structures across various weight scales within the filtration. As we will see, these connected components capture important semantic information within the feature space of the neural network.
Each α homology feature represents an equivalence class of some non-boundary cycle, so we can only pick a representative subgraph for a particular persistent connected component. However, because each of a typical neural network's (non-zero) weights are unique, we are nearly guaranteed that each equivalence class will contain only one element, namely the generator itself. In fact, a trained network that reliably contains non-trivial equivalence classes would only be optimal in a domain with high symmetry in input space. With stochastic weight updates and random initialization, the probability of encountering such a network is extremely low. If such a network is encountered, the persistent subgraphs corresponding to these generators can still be captured through the representative, but information on the number of connected components represented by this symmetric feature in input space is lost.
With identification of the nodes and edges associated with each simplex in the filtration, we can reconstruct the subgraphs within the neural network that represent these persistent topological features. Let A I = {α 1 , α 2 , . . . α n } be the set of 0-cycle generators for H 0 (G I ). Each α i is a simplicial complex that may be represented as some subgraph of G I . Equivalently, and under a slight abuse of notation,

Origins of Holes in Network Activations
One of the critical reasons for introducing the induced graph network topology is that it reveals holes in network sensitivity to the input space. Local holes arise from input activations being mapping into the kernel (null-space) of a neuron in the network, and these holes can propagate through subsequent processing layers. In general, activations mapped into a null-space at a layer i create deaths of a subgraph feature. An analysis of topological persistence under function composition shows that the kernels of mappings generally stably persist with respect to the bottleneck distance under function composition (Cohen-Steiner et al., 2009). Thus, activations mapping into a null-space at a node-level can create persistent loss of information that can be adversarially exploited (by perturbing class-diagnostic image features into local null-spaces). However, persistence diagrams over the induced network graph capture these holes in the birth-death structure.
The general conclusion that holes persist can be better appreciated by examining the conditions under which it fails. At a layer i − 1 the vector of activations a across nodes k in the layer span a space X i−1 . A local hole is created if a is in the null-space of a downstream neuron u in layer i, h u = 0. The zero component will be propagated to subsequent layers unless compensated for. Let f v represent the activation function (ReLU, Sigmoid, identity, etc.) applied to each hidden node v in layer i + 1. The activation value for node v is where w u→v is the weight parameter learned by the network connecting node u to node v. In this case, the edge weighting φ(u, v) goes to zero, which removes the edge. For a to survive along some other edge, there needs to be other neurons u which collectively span ker u. Unless each layer's mapping is injective, this is not possible to guarantee.
Although holes are likely to persist for topological reasons, the conditions for holes to be "covered over" could be created as a byproduct of network optimization. Experiments show that the essential characteristics predicted do in fact occur and can be used to both identify and classify adversarial examples.

Experiments
We implement the ideas provided in the previous sections using four neural network architectures of reasonable size across two datasets. We see that our topological approach is useful in analyzing the global activation graph of neural networks and can be used to both detect and recover from adversarial inputs.
We train four architectures on the MNIST and Fashion MNIST datasets. All networks are trained for 20 epochs on each dataset using stochastic gradient descent with learning rate 0.01. The first architecture is a simple three-layer linear network with layer sizes 784x256, 256x50, and 50x10. We refer to this network as the FFF network. The second architecture is a three layer network consisting of a single convolutional layer with 5, 5x5 filters and ReLU activations followed by two fully-connected layers of size 2880x50 and 50x10 also with ReLU activations. We refer to this network as the CFF-Relu network. The third architecture is identical to the previous but substitutes sigmoid for ReLU activations. We refer to this network as the CFF-Sigmoid network. The final network is a two-layer convolutional network followed by two fully-connected layers. The first convolutional layer has 3, 5x5 filters. The second convolutional layer consists of 3, 3x3 filters. The fully-connected layers are of size 1452x256 and 256x10. All layers of this network use ReLU activations. We call this the CCFF-Relu network.

Adversaries
For each network and dataset combination, we create a set of adversaries based off of the test set of each dataset. We create adversaries through four different methods. The first set of adversaries were created using box-constrained L-BFGS as in (Szegedy et al., 2013) to minimize the distance between the image and the adversarial as well as the crossentropy between the predictions for the adversarial and the target class. We set = 10 −5 . The second adversarial algorithm is the L 2 version of the Carlini Wagner adversaries described in (Carlini & Wagner, 2017) which we refer to as C&W L 2 . The third adversarial generation algorithm is the Projected Gradient Descent Attack as described in (Madry et al., 2017) with = 0.001 and step size 0.01. We refer to this algorithm as PGD. The final adversarial generation algorithm consists of the repeated addition of Gaussian noise to the original image until it is misclassified by the network.

Subgraph Spectra
If adversaries do exploit holes in deep network activation graphs, we would expect to see artifacts of this within the structure of persistent subgraphs induced by adversaries when compared to the subgraphs of unaltered inputs. In particular, the initial fragmentation of the subgraph structure leaves room for adversarial examples to further fragment the network activations, resulting in changes in the final layer predictions. We expect that fragmentation will be diagnostic for adversarial inputs. By analyzing the subgraph connectivity using spectral methods, we will see below that the structure of the persistent subgraphs differs significantly both between unaltered and adversarial inputs and across architectures.
Recall from Section 2.1 that for each image I fed into the network, persistent homology provides us with a set of generators A I = {α 1 , α 2 , . . . α n } where each α i may be represented as a subgraph of G I .
For each dataset and network, we take the first 2,000 images of the test sets and create a corresponding adversary for each method described in Section 4.1, leaving us with 2,000 adversarial and 2,000 unaltered test images. We then feed each of these images into their respective network-capturing the hidden activations and parameters-and compute each image's induced persistent subgraphs A I as described in Section 2 along with their persistence diagrams. We then take the graph union S I = αi∈A I α i across all generating subgraphs, leaving us with a single graph object S I for each input. Unioned subgraphs for the top ten and bottom ten most persistent subgraphs for the CFF-Relu network can be seen in Figure 3.
Persistent subgraphs represent the paths of highest activation flow through the network induced by a given input, potentially spanning multiple layers. One may also view the induced persistent subgraphs as partial transformations performed by the neural network on the input. Inspired by this idea, we assess the connectivity structure of these subgraphs by computing the weighted graph Laplacian matrix for each S I and compute its eigenvalues. The graph Laplacian yields critical information about the connectivity structure of the subgraphs. Fully connected subgraphs are dominated by a few large eigenvalues, while highly fragmented graphs have many small eigenvalues more similar in value. The mean of the subgraph eigenvalues is a simple measure of this structure. We compute the expected value of the average Laplacian subgraph eigenvalue across adversarial and unaltered inputs, as well as the size of the subgraphs (Fragment Size) given by the number of vertices in the subgraph. These results are shown in Table 1 for each dataset and adversarial algorithm.
We hypothesized that adversarial examples would be more likely to map to holes, which predicts smaller average eigenvalues, higher variance in eigenvalues across exemplars, and a larger number of distinct subgraphs. As is evident from Table 1, these predictions are confirmed.

Subgraph Classification
We can see from Figure 4 that even when restricted to only information within the persistence diagram (number of generators and their lifetimes), persistent homology still captures information about the input through the network activation graph. We see even for the more sophisticated C&W L 2 attack a nearly linear relationship between L ∞ distance in image space and Wasserstein distance between persistence diagrams, implying that persistent homology is able to capture information about the input space from the activation graph, even when the network itself misclassifies the input. In this section, we make use of this observation by vectorizing each persistent subgraph S I and training a classifier to predict the true class of an input I given each S I .
As in Section 4.2, we create a set of adversaries from 2,000 test images for each adversary generation algorithm, dataset, and network architecture. Fix a network architecture, dataset, and adversary generation method. Let U be the set of unaltered images and A the set of adversarial images. Also define U = {S I | I ∈ U} as the set of persistent subgraphs computed from each unaltered image. Let Λ = {S I | I ∈ A} be the persistent subgraphs for each adversarial image. Define U train ⊂ U as a training subset of unaltered induced subgraphs. Let N = |U train | be the size of the training set. Each training set image has a corresponding class label representing the true class of the input image.
We create a simple one-hot edge occupancy vectorization for the entire training set U train , where each unique edge in U train is represented by a dimension in the vectorization, and induced subgraphs S I train ∈ U train have value 1 along a dimension if they contain that edge. Let We train a simple one-versus-one Support Vector Machine (SVM) (Cortes & Vapnik, 1995) with linear kernel. Using this classifier, we perform two classification tasks. For the first, we investigate the extent to which these subgraphs represent class-specific information encoded by the network activation structure. For this, we segment U into training and test sets U train and U test , and compute the associated vectorization X train . We then vectorize the test set according to the edges corresponding to the dimensions of X train , resulting in matrix X test . For each dataset, architecture, and adversarial generation method, we train an SVM to predict the class of each input represented by X test . The mean accuracy across 10-fold cross-validation is reported in Table  2.
For the second classification task, we are interested in the extent to which the network activation structure is able to retain information about adversarial inputs, despite misclassification. We take U train = U and take A to be the test set. We again vectorize the subgraphs through the training edge set. For each dataset, architecture, and adversary method, we train an SVM to predict the class of the input based only off of the persistent subgraph information. The accuracy of the original network on U, the accuracy of the SVM in recovering the true class from an adversarial input (Recovery Accuracy) and percentage of inputs classified by the SVM as being of the class of the accuracy (Adversary Retention Rate) are shown in Table 3. All networks have Network Accuracy of 0% on their adversary test set A.
As expected, the persistent subgraphs capture information about the input that is otherwise obfuscated by adversarial alterations in the original image that change the activation structure enough to cause the network to misclassify. The Recovery Accuracy follows from our observations in 4. Gaussian Noise and L-BFGS are the least precise adversarial generation methods of the group, meaning they generate adversaries with larger differences between the original input and the adversary than PGD and C&W L 2 . We see that more sophisticated adversarial algorithms that produce images that are not noticeably different than the original image are more likely to be recoverable using persistent subgraphs than algorithms that distort the image more severely.
Also note that the Subgraph SVM classification method performs better than the original FFF-Relu network when classifying unaltered images. In this scenario, the original network acts as a "feature preprocessor" for the Subgraph SVM. It is likely that adding more layers-thus adding more capacity-to the network would shrink this disparity between the Network Accuracy and Subgraph SVM Accuracy.

Discussion
We have shown that persistent homology is a useful tool for analyzing the activation structure of deep networks, providing a way to both detect strucutral changes introduced by adversarial inputs and to recover the correct class of the input despite its adversarial nature.  robustness focus primarily on training procedures (adversarial training, normalization, compression, label smoothing).
Here we show that neural network architectures themselves are inherently susceptible to adversarial attacks based on the prevalence of holes in activation space that are readily exploited by adversaries to change the classification decisions of the network. Our ability to diagnose and correctly classify adversarial examples from the activations structure alone is surprising, but opens new possibilities and principles for designing robust neural systems.
Exploring other architectures and robustness procedures would be an important avenue of further research related to adversarial targeting of holes in network activation space. For example, how might adversarial training affect the subgraph structure of the networks? We anticipate that a network with adversarial training would admit fewer holes. However, the kernel space of any given neuron is quite large, so to what extent these holes may be filled through adversarial training is an open question. Our results im-ply architectural decisions that compress the kernel space of each hidden node may be better suited to maximize adversarial robustness. We expect networks like ResNet (He et al., 2016) with multiple connections between layers to be more robust to adversaries than their counterparts without pass-through connections.
However, our analysis in its current state faces many limitations. Computing persistent homology for a deep network requires one to capture the activation record across layers and to reconstruct this information within the filtration. A 100x10 fully-connected layer has potentially 1,110 simplices, and a similarly-sized convolutional layer with numerous channels can be even larger. Expectedly, this approach scales neither in memory nor computation. Better sampling strategies over the network and filtration could solve some of these computational limitations. For example, replacing our full network simplicial complex by a variant of the Witness Complex (De Silva & Carlsson, 2004) could reduce memory and computational burdens significantly. As well, computing the entire subgraph structure is likely overkill for most practical applications. In Section 4.3, the networks with ReLU activations reached an equivalent Recovery Accuracy using only the union of the top 3 generators.

Conclusion
The brittleness of machine learning systems to adversarial attacks poses major challenges for security and robustness of large scale systems. Here we show that susceptibility to adversarial attack is partly attributable to the network architecture per se. Using persistent homology we show that adversarial examples map into topological holes in the induced network graph, both explaining which examples are adversarial and providing new methods to correctly classify them using the same network, because class information is still embedded in higher-order information contained in the activation subgraphs. These results provide new principles for understanding adversarial attacks and the possibility of improved architectures and meta-learning approaches to robust, interpretable, and safe learning.