summaries: This paper proposes a policy evaluation and search method assisted by a counterfactual model, in contrast previous work using vanilla (non-causal) models. With “no model mismatch” assumption the policy evaluation estimator is unbiased. Empirically, the paper compares Guided Policy Search with counterfactual model (CF-GPS) with vanilla GPS, model based RL algorithm and show benefit in terms of (empirical) sample complexity.

summaries: Proposes Counterfactual Guided Policy Search (CF-GPS), which uses counterfactual inference from sampled trajectories to improve an approximate simulator that is used for policy evaluation. Counterfactual inference is formalized with structural causal models of the POMDP. The method is evaluated in partially-observed Sokoban problems. The dynamics model is assumed known, and a learned model maps observation histories to a conditional distribution on the starting state. CF-GPS outperforms model-based policy search and a "GPS-like" algorithm in these domains. GPS in MDPs is shown to be a particular case of CF-GPS, and a connection is also suggested between stochastic value gradient and CF-GPS.

abstractText: Learning policies on data synthesized by models can in principle quench the thirst of reinforcement learning algorithms for large amounts of real experience, which is often costly to acquire. However, simulating plausible experience de novo is a hard problem for many complex environments, often resulting in biases for modelbased policy evaluation and search. Instead of de novo synthesis of data, here we assume logged, real experience and model alternative outcomes of this experience under counterfactual actions, i.e. actions that were not actually taken. Based on this, we propose the Counterfactually-Guided Policy Search (CF-GPS) algorithm for learning policies in POMDPs from off-policy experience. It leverages structural causal models for counterfactual evaluation of arbitrary policies on individual off-policy episodes. CF-GPS can improve on vanilla model-based RL algorithms by making use of available logged data to de-bias model predictions. In contrast to off-policy algorithms based on Importance Sampling which re-weight data, CF-GPS leverages a model to explicitly consider alternative outcomes, allowing the algorithm to make better use of experience data. We find empirically that these advantages translate into improved policy evaluation and search results on a non-trivial grid-world task. Finally, we show that CF-GPS generalizes the previously proposed Guided Policy Search and that reparameterization-based algorithms such Stochastic Value Gradient can be interpreted as counterfactual methods.

authors:
Pieter Abbeel
Morgan Quigley
Andrew Y Ng

title: Using inaccurate models in reinforcement learning

venue: In Proceedings of the 23rd international conference on Machine learning,

authors:
Marcin Andrychowicz
Filip Wolski
Alex Ray
Jonas Schneider
Rachel Fong
Peter Welinder
Bob McGrew
Josh Tobin
OpenAI Pieter Abbeel
Wojciech Zaremba

title: Hindsight experience replay

venue: In Advances in Neural Information Processing Systems,

authors:
Onur Atan
William R Zame
Qiaojun Feng
Mihaela van der Schaar

title: Constructing Effective Personalized Policies Using Counterfactual Inference from Biased Data Sets with Many Features

venue: arXiv preprint arXiv:1612.08082,

authors:
Alexander Balke
Judea Pearl

title: Counterfactual probabilities: Computational methods, bounds and applications

venue: In Proceedings of the Tenth international conference on Uncertainty in artificial intelligence,

authors:
Léon Bottou
Jonas Peters
Joaquin Quiñonero-Candela
Denis X Charles
D Max Chickering
Elon Portugaly
Dipankar Ray
Patrice Simard
Ed Snelson

title: Counterfactual reasoning and learning systems: The example of computational advertising

venue: The Journal of Machine Learning Research,

authors:
Cameron B Browne
Edward Powley
Daniel Whitehouse
Simon M Lucas
Peter I Cowling
Philipp Rohlfshagen
Stephen Tavener
Diego Perez
Spyridon Samothrakis
Simon Colton

title: A survey of Monte Carlo tree search methods

venue: IEEE Transactions on Computational Intelligence and AI in games,

authors:
Lasse Espeholt
Hubert Soyer
Remi Munos
Karen Simonyan
Volodymir Mnih
Tom Ward
Yotam Doron
Vlad Firoiu
Tim Harley
Iain Dunning

title: IMPALA: Scalable distributed Deep-RL with importance weighted actor-learner architectures

venue: arXiv preprint arXiv:1802.01561,

authors:
Karol Gregor
Ivo Danihelka
Alex Graves
Danilo Jimenez Rezende
Daan Wierstra

title: Draw: A recurrent neural network for image generation

venue: arXiv preprint arXiv:1502.04623,

authors:
Karol Gregor
Frederic Besse
Danilo Jimenez Rezende
Ivo Danihelka
Daan Wierstra

title: Towards conceptual compression

venue: In Advances In Neural Information Processing Systems,

authors:
Zhaohan Guo
Philip S Thomas
Emma Brunskill

title: Using options and covariance testing for long horizon off-policy policy evaluation

authors:
Nicolas Heess
Gregory Wayne
David Silver
Tim Lillicrap
Tom Erez
Yuval Tassa

title: Learning continuous control policies by stochastic value gradients

authors:
Nan Jiang
Lihong Li

title: Doubly robust off-policy value evaluation for reinforcement learning

venue: arXiv preprint arXiv:1511.03722,

authors:
Nan Jiang
Alex Kulesza
Satinder Singh
Richard Lewis

title: The dependence of effective planning horizon on model accuracy

venue: In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems,

authors:
Fredrik Johansson
Uri Shalit
David Sontag

title: Learning representations for counterfactual inference

venue: In International Conference on Machine Learning,

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
Diederik P Kingma
Max Welling

title: Auto-encoding variational Bayes

venue: arXiv preprint arXiv:1312.6114,

authors:
Kevin B Korb
Lucas R Hope
Ann E Nicholson
Karl Axnick

title: Varieties of causal intervention

venue: In Pacific Rim International Conference on Artificial Intelligence,

authors:
Sergey Levine
Pieter Abbeel

authors:
Sergey Levine
Vladlen Koltun

title: Guided policy search

venue: In International Conference on Machine Learning, pp

authors:
Lihong Li
Shunbao Chen
Jim Kleban
Ankur Gupta

title: Counterfactual estimation and optimization of click metrics in search engines: A case study

venue: In Proceedings of the 24th International Conference on World Wide Web,

authors:
Yao Liu
Omer Gottesman
Aniruddh Raghu
Matthieu Komorowski
Aldo Faisal
Finale DoshiVelez
Emma Brunskill

title: Representation balancing mdps for off-policy policy evaluation

venue: arXiv preprint arXiv:1805.09044,

authors:
Rémi Munos
Tom Stepleton
Anna Harutyunyan
Marc Bellemare

title: Safe and efficient off-policy reinforcement learning

authors:
Thomas Nedelec
Nicolas Le Roux
Vianney Perchet

title: A comparative study of counterfactual estimators

venue: arXiv preprint arXiv:1704.00773,

title: Causality: Models, Reasoning and Inference

venue: USA, 2nd edition,

authors:
Judea Pearl
Dana Mackenzie

title: The Book of Why: The New Science of Cause and Effect

venue: Basic Books,

authors:
J. Peters
D. Janzing
B. Schölkopf

title: Elements of Causal Inference - Foundations and Learning Algorithms. Adaptive Computation and Machine Learning Series

title: Eligibility traces for off-policy policy evaluation

venue: Computer Science Department Faculty Publication Series, pp

authors:
Sébastien Racanière
Théophane Weber
David Reichert
Lars Buesing
Arthur Guez
Danilo Jimenez Rezende
Adrià Puigdomènech Badia
Oriol Vinyals
Nicolas Heess
Yujia Li

title: Imagination-augmented agents for deep reinforcement learning

authors:
Danilo Jimenez Rezende
Shakir Mohamed
Daan Wierstra

venue: arXiv preprint arXiv:1401.4082,

title: Counterfactual thinking

venue: Psychological bulletin,

authors:
Adith Swaminathan
Thorsten Joachims

title: Counterfactual risk minimization: Learning from logged bandit feedback

title: Model Regularization for Stable Sample Rollouts

venue: In UAI, pp

authors:
Philip Thomas
Emma Brunskill

title: Data-efficient off-policy policy evaluation for reinforcement learning

title: Robot trajectory optimization using approximate inference

venue: In Proceedings of the 26th annual international conference on machine learning,

title: The relative importance of heredity and environment in determining the piebald pattern of guinea-pigs

venue: Proceedings of the National Academy of Sciences,

authors:
Shi Xingjian
Zhourong Chen
Hao Wang
Dit-Yan Yeung
Wai-Kin Wong
Wang-chun Woo

title: Convolutional LSTM network: A machine learning approach for precipitation nowcasting

venue: In Advances in neural information processing systems,

heading: 1 INTRODUCTION

text:
Imagine that a month ago Alice had two job offers from companies a1 and a2. She decided to join a1 because of the larger salary, in spite of an awkward feeling during the job interview. Since then she learned a lot about a1 and recently received information about a2 from a friend, prodding her now to imagine what would have happened had she joined a2. Re-evaluating her decision in hindsight in this way, she concludes that she made a regrettable decision. She could and should have known that a2 was a better choice, had she only interpreted the cues during the interview correctly... This example tries to illustrate the everyday human capacity to reason about alternate, counterfactual outcomes of past experience with the goal of “mining worlds that could have been” (Pearl & Mackenzie, 2018). Social psychologists theorize that such cognitive processes are beneficial for improving future decision making (Roese, 1997). In this paper we aim to leverage possible advantages of counterfactual reasoning for learning decision making in the reinforcement learning (RL) framework.
In spite of recent success, learning policies with standard, model-free RL algorithms can be notoriously data inefficient. This issue can in principle be addressed by learning policies on data synthesized from a model. However, a mismatch between the model and the true environment, often unavoidable in practice, can cause this approach to fail (Talvitie, 2014), resulting in policies that do not generalize to the real environment (Jiang et al., 2015). Motivated by the introductory example, we propose the Counterfactually-Guided Policy Search (CF-GPS) algorithm: Instead of relying on data synthesized from scratch by a model, policies are trained on model predictions of alternate outcomes of past experience from the true environment under counterfactual actions, i.e. actions that had not actually been taken, while everything else remaining the same (Pearl, 2009). At the heart
of CF-GPS are structural causal models (SCMs) which model the environment with two ingredients (Wright, 1920): 1) Independent random variables, called scenarios here, summarize all aspects of the environment that cannot be influenced by the agent, e.g. the properties of the companies in Alice’s job search example. 2) Deterministic transition functions (also called causal mechanisms) take these scenarios, together with the agent’s actions, as input and produce the predicted outcome. The central idea of CF-GPS is that, instead of running an agent on scenarios sampled de novo from a model, scenarios are inferred in hindsight from given off-policy data, and then evaluate and improve the agent on these specific scenarios using given or learned causal mechanisms (Balke & Pearl, 1994). CF-GPS can be regarded as a meta-algorithm that extends a given model-base RL algorithm by “grounding” or “anchoring” model-based predictions in inferred scenarios. As a result, this approach explicitly allows to trade-off historical data for model bias. We show empirically in a conceptually simple setting, where unknown initial states are inferred in hindsight and re-used to evalute to counterfactual actions, that this can mitigate model mismatch. CF-GPS differs substantially from standard off-policy RL algorithms based on Importance Sampling (IS), where historical data is re-weighted with respect to the importance weights to evaluate or learn new policies (Precup, 2000). In contrast, CF-GPS explicitly reasons counterfactually about given off-policy data. Our main contributions are:
1. We formulate model-based RL in POMDPs in terms of structural causal models, thereby connecting concepts from reinforcement learning and causal inference.
2. We provide the first results, to the best of our knowledge, showing that counterfactual reasoning in structural causal models on off-policy data can facilitate solving non-trivial RL tasks.
3. We show that two previously proposed classes of RL algorithms, namely Guided Policy Search (Levine & Koltun, 2013) and Stochastic Value Gradient methods (Heess et al., 2015), can be interpreted as counterfactual methods, opening up possible generalizations.
The paper is structured as follows. We first give a self-contained, high-level recapitulation of structural causal models and counterfactual inference, as these are less widely known in the RL and generative model communities. In particular we show how to model POMDPs with SCMs. Based on this exposition, we first consider the task of policy evaluation and discuss how we can leverage counterfactual inference in SCMs to improve over standard model-based methods. We then generalize this approach to the policy search setting resulting in the CF-GPS algorithm. We close by highlighting connections to previously proposed algorithms and by discussing assumptions and limitations of the proposed method.

heading: 2 PRELIMINARIES

text: We denote random variables (RVs) with capital letters, e.g. X , and particular values with lower caps, e.g. x. For a distribution P over a vector-valued random variable X , we denote the marginal over Y ⊂ X by PY (and density pY ); however we often omit the subscript if it is clear from the context, e.g. as in Y ∼ P . We assume the episodic, Partially Observable Markov Decision Process (POMDP) setting with states St, actions At and observations Ot, for t = 1, . . . , T . For ease of notation, we assume that Ot includes the reward Rt. The undiscounted return is denoted by G = ∑T t=1Rt. We consider stochastic policies π(at|ht) over actions conditioned on observation histories Ht = (O1, A1, . . . , At−1, Ot). We denote the resulting distribution over trajectories T = (S1, O1, A1, . . . , AT−1, ST , OT ) induced by running π in the environment with T ∼ Pπ and the corresponding density by pπ(τ).

heading: 2.1 STRUCTURAL CAUSAL MODELS

text:
Definition 1 (Structural causal model). A structural causal model (SCM) M over X = (X1, . . . , XN ) is given by a DAG G over nodes X , independent noise RVs U = (U1, . . . , UN ) with distributions PUi and functions f1, . . . , fN such that Xi = fi(pai, Ui), where pai ⊂ X are the parents of Xi in G. An SCM entails a distribution P with density p over (X,U).
We also refer to U as scenarios and to fi as causal mechanisms. We give a (broad) definition of an intervention in an SCM. This also includes what is known as stochastic interventions or mechanism changes (Korb et al., 2004) which generalize atomic interventions (Pearl, 2009).
Definition 2 (Intervention in SCM). An intervention I in an SCMM consists of replacing some of the original fi(pai, Ui) with other functions f I i (pa I i , Ui) where pa I i are the parents in a new DAG GI . We denote the resulting SCM withMdo(I) with distribution P do(I) and density pdo(I).
SCM representation of POMDPs We can represent any given POMDP (under a policy π) by an SCMM over trajectories T in the following way. We express all conditional distributions, e.g. the transition kernel PSt+1|St,At , as deterministic functions with independent noise variables U , such as St+1 = fst(St, At, Ust). This is always possible using auto-regressive uniformization, see Lemma 2 in the appendix. The DAG G of the resulting SCM is shown in fig. 1. This procedure is closely related to the ‘reparameterization trick’ for models with location-scale distributions (Kingma & Welling, 2013; Rezende et al., 2014). We denote the distribution over T entailed by the SCM with Pπ and its density by pπ to highlight the role of π; note the difference to the true environment distribution Pπ with density pπ . Running a different policy µ instead of π in the environment can be expressed as an intervention I(π → µ) consisting of replacing At = fπ(Ht, Uat) by At = fµ(Ht, Uat). We denote the resulting model distribution over trajectories with P do(I(π→µ)) = Pµ (analogously pµ).
Intuition Here, we illustrate the main advantage of SCMs using the example of Alice’s job choice from the introduction. We model it as contextual bandit with feedback shown in fig. 1. Alice has some initial knowledge given by the context Uc that is available to her before taking action A of joining company A = a1 or A = a2. We model Alice’s decision as A = fπ(Uc, Ua), where Ua captures potential indeterminacy in Alice’s decision making. The outcome O = fo(A,Uc, Uo) also depends on the scenario Uo, capturing all relevant, unobserved and highly complex properties of the two companies such as working conditions etc. Given this model, we can reason about alternate outcomes fo(a1, uc, uo) and fo(a2, uc, uo) for same the scenario uo. This is not possible if we only model the outcome on the level of the conditional distribution PO|A,Uc .

heading: 2.2 COUNTERFACTUAL INFERENCE IN SCMS

text:
For an SCM over X , we define a counterfactual query as a triple (x̂o, I,Xq) of observations x̂o of some variablesXo ⊂ X , an intervention I and query variablesXq ⊂ X . The semantics of the query are that, having observed x̂o, we want to infer what Xq would have been had we done intervention I , while ‘keeping everything else the same’. Counterfactual inference (CFI) in SCMs answers the query in the following way (Balke & Pearl, 1994):
1. Infer the unobserved noise source U conditioned on the observations x̂o, i.e. compute p(U |x̂o) and replace the prior p(U) with p(U |x̂o). Denote the resulting SCM byMx̂o .
2. Perform intervention I on Mx̂o . This yields M do(I) x̂o
, which entails the counterfactual distribution pdo(I)|x̂o(x). Return the marginal pdo(I)|x̂o(xq).
Note that our definition explicitly allows for partial observations Xo ⊂ X in accordance with Pearl (2009). A sampled-based version, denoted as CFI, is presented in Algorithm 1. An interesting property of the counterfactual distribution pdo(I)|x̂o is that marginalizing it over observations x̂o yields an unbiased estimator of the density of Xq under intervention I . Lemma 1 (CFI for simulation). Let observations x̂o ∼ p come from a SCMM with density p. Then the counterfactual density pdo(I)|x̂o is an unbiased estimator of pdo(I), i.e.
Ex̂o∼p[pdo(I)|x̂o(x)] = pdo(I)(x)
The proof is straightforward and outlined in the Appendix A. This lemma and the marginal independence of the Ui leads to the following corollary; the proof is given in the appendix. Corollary 1 (Mixed counterfactual and prior simulation from an SCM). Assume we have observations x̂o ∼ p. We can simulate from M, under any intervention I , i.e. obtain unbiased samples from Mdo(I), by first sampling values uCF for an arbitrary subset UCF ⊂ U from the posterior p(uCF|x̂o) and the remaining UPrior := U\UCF from the prior p(uPrior), and then computing X with noise u = uCF ∪ uPrior.
The corollary essentially states that we can sample from the modelMI , by sampling some of the Ui from the prior, and inferring the rest from data x̂o (as long as the latter was also sampled fromM). We will make use of this later for running a POMDP model on scenariosUst inferred from data while randomizing the action noise Uat. We note that the noise variables UCF from the posterior PUCF|x̂o are not independent anymore. Nevertheless, SCMs with non-independent noise distributions arising from counterfactual inference, denoted here by Mx̂o , are commonly considered in the literature (Peters et al., 2017).
Intuition Returning to Alice’s job example from the introduction, we give some intuition for counterfactual inference in SCMs. Given the concrete outcome ô, under observed context ûc and having joined company â = a1, Alice can try to infer the underlying scenario uo ∼ p(uo|a1, ûc, ô) that she experiences; this includes factors such as work conditions etc. She can then reason counterfactually about the outcome had she joined the other company, which is given by fo(a2, ûc, uo). This can in principle enable her to make better decisions in the future in similar scenarios by changing her policy fπ(A,Uc, Ua) such that the action with the preferred outcome becomes more likely under ûc, uo. In particular she can do so without having to use her (likely imperfect) prior model over possible companies p(Uo). She can use the counterfactual predictions discussed above instead to learn from her experience. We use this insight for counterfactual policy evaluation and search below.

heading: 3 OFF-POLICY EVALUATION: MODEL-FREE, MODEL-BASED AND COUNTERFACTUAL

text:
To explain how counterfactual reasoning in SCMs can be used for policy search, we first consider the simpler problem of policy evaluation (PE) on off-policy data. The goal of off-policy PE is to determine the value of a policy π, i.e. its expected return Epπ [G], without running the policy itself. We assume that we have data D = {ĥiT }i=1,...,N consisting of logged episodes ĥiT = (ô i 1, â i 1, . . . â i T−1, ô i T ) from running a behavior policy µ. A standard, model-free approach
to PE is to use Importance sampling (IS): We can estimate the policy’s value as ∑ i w iĜi, where Ĝi is the empirical return of ĥiT and w i ∝ p π(ĥiT )
pµ(ĥiT ) are importance weights. However, if the trajectory
densities pπ and pµ are very different, then this estimator has large variance. In the extreme case, IS can be useless if the support of pµ does not contain that of pπ , irrespective of how much data from pµ is available.
If we have access to a model M, then we can evaluate the policy on synthetic data, i.e. we can estimate Epπ [G]. This is called model-based policy evaluation (MB-PE). However, any bias inM propagates from pπ to the estimate Epπ [G]. In the following, we assume thatM is a SCM and we
Algorithm 1 Counterfactual policy evaluation and search // Counterfactual inference (CFI)
1: procedure CFI(data x̂o, SCMM, intervention I , query Xq) 2: û ∼ p(u|x̂o) . Sample noise variables from posterior 3: p(u)← δ(u− û) . Replace noise distribution in p with û 4: fi ← fIi . Perform intervention I 5: return xq ∼ pdo(I)(xq|û) . Simulate from the resulting modelMIx̂o 6: end procedure
// Counterfactual Policy Evaluation (CF-PE) 7: procedure CF-PE(SCMM, policy π, replay buffer D, number of samples N ) 8: for i ∈ {1, . . . N} do 9: ĥiT ∼ D . Sample from the replay buffer 10: gi = CFI(ĥiT ,M, I(µ→ π), G) . Counterfactual evaluation of return 11: end for 12: return 1
N ∑N i=1 gi
13: end procedure
// Counterfactually-Guided Policy Search (CF-GPS) 14: procedure CF-GPS(SCMM, initial policy π0, number of trajectory samples N ) 15: for k = 1, . . . do 16: if sometimes then 17: µ← πk . Update behavior policy 18: end if 19: for i = 1, . . . , N do 20: ĥiT ∼ pµ . Get off-policy data from the true environment 21: τ i = CFI(ĥiT ,M, I(µ→ πλ), T ) . Counterfactual rollouts under planner 22: end for 23: πk ← policy improvement on trajectories τ i=1,...,N using eqn. 1 24: end for 25: end procedure
show that we can use counterfactual reasoning for off-policy evaluation (CF-PE). As the main result for this section, we argue that we expect CF-PE to be less biased than MB-PE, and we illustrate this point with experiments.

heading: 3.1 COUNTERFACTUAL OFF-POLICY EVALUATION

text:
Naive MB-PE with a SCMM simply consist of sampling the scenarios U ∼ PU from the prior, and then simulating a trajectory τ from the functions fi and computing its return. However, given data D from pµ, our discussion of counterfactual inference in SCMs suggests the following alternative strategy: Assuming no model mismatch, i.e. pµ = pµ, we can regard the task of off-policy evaluation of π as a counterfactual query with data ĥiT , intervention I(µ → π) and query variable G. In other words, instead of sampling from the prior as in MB-PE, we are free to the scenarios from the posterior ui ∼ pµ(·|ĥiT ). The algorithm is given in Algorithm 1. Lemma 1 guarantees that this results in an unbiased estimate: Corollary 2 (CF-PE is unbiased). Assuming no model mismatch, CF-PE is unbiased.
Furthermore, Corollary 1 allows us to also sample some of the noise variables from the prior instead of the posterior, we can e.g. randomize the counterfactual actions by re-sampling the action noise Ua.
Motivation When should one prefer CF-PE over the more straightforward MB-PE? Assuming a perfect model, Corollary 2 states that both yield the same answer in expectation for perfect models. For imperfect models however, these algorithms can differ substantially. MB-PE relies on purely synthetic data, sampled from the noise distribution p(U). In practice, this is usually approximated by a parametric density model, which can lead to under-fitting in case of complex distributions. This is a well-known effect in generative models with latent variables: In spite of recent research progress, e.g. models of natural images are still unable to accurately model the variability of the true data
(Gregor et al., 2016). In contrast, CF-PE samples from the posterior N−1 ∑N i=1 p
µ(U |ĥiT ), which has access to strictly more information than the prior p(U) by taking into account additional data ĥiT . This semi-nonparametric distribution can help to de-bias the model by effectively winnowing out parts of the domain of U which do not correspond to any real data. We substantiate this intuition with experiments below; a concrete illustration for the difference between the prior and posterior / counterfactual distribution is given in fig. 4 in the appendix and discussed in appendix D. Therefore, we conclude that we expect CF-PE to outperform MB-PE, if the transition and reward kernels fst are accurate models of the environment dynamics, but if the marginal distribution over the noise sources PU is difficult to model.

heading: 3.2 EXPERIMENTS

text:
Environment As an example, we use a partially-observed variant of the SOKOBAN environment, which we call PO-SOKOBAN. The original SOKOBAN puzzle environment was described in detail by Racanière et al. (2017); we give a brief summary here. The agent is situated in a 10 × 10 grid world and its five actions are to move to one of four adjacent tiles and a NOOP. In our variant, the goal is to push all three boxes onto the three targets. As boxes cannot be pulled, many actions result irreversibly in unsolvable states. Episodes are of length T = 50, and pushing a box onto a target yields a reward of 1, removing a box from a target yields −1, and solving a level results in an additional reward of 10. The state of the environment consists in a 10× 10 matrix of categorical variables taking values in {0, . . . , 6} indicating if the corresponding tile is empty, a wall, box, target, agent, or a valid combinations thereof (box+target and agent+target). In order to introduce partial observability, we define the observations as the state corrupted by i.i.d. (for each tile and time step) flipping each categorical variable to the “empty” state with probability 0.9. Therefore, the state of the game is largely unobserved at any given time, and a successful agent has to integrate observations over tens of time steps. Initial states Us1, also called levels, which are the scenarios in this environment, are generated randomly by a generator algorithm which guarantees solvability (i.e. all boxes can be pushed onto targets). The environment is visualized in fig. 3 in the appendix.
Given the full state of PO-SOKOBAN, the transition kernel is deterministic and quite simple as only the agent and potentially an adjacent box moves. Inferring the belief state, i.e. the distribution over states given the history of observations and actions, can however range from trivial to very challenging, depending on the amount of available history. In the limit of a long observed history, every tile is eventually observed and the belief state concentrates on a single state (the true state) that can be easily inferred. With limited observed history however, inferring the posterior distribution over states (belief state) is very complex. Consider e.g. the situation in the beginning of an episode (before pushing the first box). Only the first observation is available, however we know that all POSOKOBAN levels are initially guaranteed to be solvable and therefore satisfy many combinatorial constraints reflecting that the agent is still able to push all boxes onto targets. Learning a compact parametric model of the initial state distribution from empirical data is therefore difficult and likely results in large mismatch between the learned model and the true environment.
Results To illustrate the potential advantages of CF-PE over MB-PE we perform policy evaluation in the PO-SOKOBAN environment. We first generate a policy π that we wish to evaluate, by training it using a previously-proposed distributed RL algorithm (Espeholt et al., 2018). The policy is parameterized as a deep, recurrent neural network consisting of a 3-layer deep convolutional LSTM (Xingjian et al., 2015) with 32 channels per layer and kernel size of 3. To further increase computational power, the LSTM ticks twice for each environment step. The output of the agent is a value function and a softmax yielding the probabilities of taking the 5 actions. In order to obtain an SCM of the environment, for the sake of simplicity, we assume that the ground-truth transition, observation and reward kernels are given. Therefore the only part of the model that we need to learn is the distribution p(Us1) of initial states S1 = Us1 (for regular MB-PE), and the density p(Us1|ĥit) for inferring levels in hindsight for CF-PE. We vary the amount of true data t that we condition this inference on, ranging from t = 0 (no real data, equivalent to MB-PE) to t = T = 50 (a full episode of real data is used to infer the initial state Us1). We train a separate model for each t ∈ {0, 5, 10, 20, 30, 40, 50}. To simplify model learning, both models were given access to the unobserved state during training, but not at test time. The models are chosen to be powerful, multilayer, generative DRAW models (Gregor et al., 2015) trained by approximate maximum likelihood learning (Kingma & Welling, 2013; Rezende et al., 2014). The models take as input the (potentially
empty) data ĥit summarized by a backward RNN (a standard convolutional LSTM model with 32 units). The model is shown in fig. 3 in the appendix and additional details are given in appendix C. The data ĥiT was collected under a uniform random policy µ. For all policy evaluations, we use ≈> 105 levels ui from the inferred model. In order to evaluate policies of different proficiency, we derive from the original (trained) π three policies π0, π1, π2 ranging from almost perfect to almost random performance by introducing additional stochasticity during action selection.
The policy evaluation results are shown in fig. 2. We found that for t = 0, in spite of extensive hyper-parameter search, the model p(Us1) was unable to accurately capture the marginal distribution of initial levels in PO-SOKOBAN. As argued above, a solvable level satisfies a large number of complex constraints that span the entire grid world, which are hard for a parametric model to capture. Empirically, we found that the model mismatch manifested itself in samples from p(Us1) not being well-formed, e.g. not solvable, and hence the performance of the policies πi are very different on these synthetic levels compared to levels sampled form p. However, inferring levels from full observed episodes i.e. p(Us1|ĥi50) was reliable, and running π on these resulted in accurate policy evaluation. The figure also shows the trade-off between policy evaluation accuracy and the amount of off-policy data for intermediate amounts of the data ĥit. We also want to emphasize that in this setting, model-free policy evaluation by IS fails. The uniform behavior policy µ was too different from πi, resulting in a relative error > 0.8 for all i = 1, 2, 3.

heading: 4 OFF-POLICY IMPROVEMENT: COUNTERFACTUALLY-GUIDED POLICY SEARCH

text: In the following we show how we can leverage the insights from counterfactual policy evaluation for policy search. We commence by considering a model-based RL algorithm and discuss how we can generalize it into a counterfactual algorithm to increase its robustness to model mismatch. We chose a particular algorithm to start from to make a connection to the previously proposed Guided Policy Search algorithm (Levine & Koltun, 2013; Levine & Abbeel, 2014), but we think a larger class of MBRL algorithms can be generalized in an analogous manner.

heading: 4.1 STARTING POINT: VANILLA MODEL-BASED RL WITH RETURN WEIGHTED REGRESSION

text:
We start from the following algorithm. We assume we have a model M of the environment with trajectory distribution pπ . Our current policy estimate πk is improved at iteration k using returnweighted regression:
πk+1 = arg max π
∫ exp(G(τ))pπ k (τ) log pπ(τ) dτ,
where G(τ) is the return of trajectory τ . This policy improvement step can be motivated by the framework of RL as variational inference (Toussaint, 2009) and is equivalent to minimizing the KL divergence to a trajectory distribution ∝ exp(G)pπk which puts additional mass on high-return trajectories. Although not strictly necessary for our exposition, we also allow for a dedicated proposal distribution over trajectories pλ(τ), under a policy λ. We refer to λ as a planner to highlight that it could consist of a procedure that solves episodes starting from arbitrary, full states s1 sampled form the model, by repeatedly calling the model transition kernel, e.g. a search procedure such as MCTS (Browne et al., 2012) or an expert policy. Concretely, we optimize the following finite sample objective:
πk+1 = arg max π N∑ i=1 exp(Gi(τ i)) pπ k (τ i) pλ(τ i) log pπ(τ i), τ i ∼ pλ. (1)
We refer to this algorithm as model-based policy search (MB-PS). It is based on model rollouts τ i spanning entire episodes. An alternative would be to consider model rollouts starting from states visited in the real environment (if available). Both versions can be augmented by counterfactual methods, but for the sake of simplicity we focus on the simpler MB-PS version detailed above (also we did not find significant performance differences experimentally between both versions).

heading: 4.2 INCORPORATING OFF-POLICY DATA: COUNTERFACTUALLY-GUIDED POLICY SEARCH

text:
Now, we assume that the model M is an SCM. Based on our discussion of counterfactual policy evaluation, it is straightforward to generalize the MB-PS described above by anchoring the rollouts τ i under the model pλ in off-policy data D: Instead of sampling τ i directly from the prior pλ, we draw them from counterfactual distribution pλ|ĥ
i T with data ĥiT ∼ D from the replay buffer,
i.e. instead of sampling the scenarios U from the prior we infer them from the given data. Again invoking Lemma 1, this procedure is unbiased under no model mismatch. We term the resulting algorithm Counterfactually-Guided Policy Search (CF-GPS), and it is summarized in Algorithm 1. The motivation for using CF-GPS over MB-PS is analogous to the advantage of CF-PE over MB-PE discussed in sec. 3.1. The policy π in CF-GPS is optimized on rollouts τ i that are grounded in data ĥiT by sampling them from the counterfactual distribution p
λ|ĥiT instead of the prior pλ. If this prior is difficult to model, we expect the counterfactual distribution to be more concentrated in regions where there is actual mass under the true environment pλ.

heading: 4.3 EXPERIMENTS

text:
We evaluate CF-GPS on the PO-SOKOBAN environment, using a modified distributed actor-learner architecture based on Espeholt et al. (2018): Multiple actors (here 64) collect real data ĥT by running the behavior policy µ in the true environment p. As in many distributed RL settings, µ is chosen to be a copy of the policy π, often slightly outdated, so the data must be considered to be offpolicy. The distribution p(Us1|ĥT ) over levels Us1 is inferred from the data ĥT using from the model M. We sample a scenario Us1 for each logged episode, and simulate 10 counterfactual trajectories τ1,...,10 under the planner λ for each such scenario. Here, for the sake of simplicity, instead of using search, the planner was assumed to be a mixture between π and a pre-trained expert policy λe, i.e. λ = βλe + (1− β)π. The schedule β was set to an exponentially decaying parameter with time constant 105 episodes. The learner performs policy improvement on π using τ1,...,10 according to eqn. 1. M was trained online, in the same way as in sec. 3.2. λ and π were parameterized by deep, recurrent neural networks with the same architecture described in sec. 3.2.
We compare CF-GPS with the vanilla MB-PS baseline described in sec. 4.1 (based on the same number of policy updates). MB-PS differs from CF-GPS by just having access to an unconditional model p(Us1|∅) over initial states. We also consider a method which conditions the scenario model p(Us1|o1) on the very first observation o1, which is available when taking the first action and therefore does not involve hindsight reasoning. This is more informed compared to MB-PS; however due to the noise on the observations, the state is still mostly unobserved rendering it very challenging to learn a good parametric model of the belief state p(Us1|o1). We refer to this algorithm as Guided Policy Search-like (GPS-like), as it roughly corresponds to the algorithm presented by Levine & Abbeel (2014), as discussed in greater detail in sec. 5. Fig. 2 shows that CF-GPS outperforms these
two baselines. As expected from the policy evaluation experiments, initial states sampled from the models for GPS and MB-PS are often not solvable, yielding inferior training data for the policy π. In CF-GPS, the levels are inferred from hindsight inference p(U1|ĥT ), yielding high quality training data. For reference, we also show a policy trained by the model-free method of Espeholt et al. (2018) using the same amount of environment data. Not surprisingly, CF-GPS is able to make better use of the data compared to the model-free baseline as it has access to the true transition and reward kernels (which were not given to the model-free method).

heading: 5 RELATED WORK

text:
Bottou et al. (2013) provide an in-depth discussion of applying models to off-policy evaluation. However, their and related approaches (Li et al., 2015; Jiang & Li, 2015; Swaminathan & Joachims, 2015; Nedelec et al., 2017; Atan et al., 2016; Thomas & Brunskill, 2016) such as doubly-robust estimators, rely on Importance Sampling (IS), also called Propensity Score method. Although some of these algorithms are also termed counterfactual policy evaluation, they are not counterfactual in the sense used in this paper, where noise variables are inferred from logged data and reused to evaluate counterfactual actions. Hence, they are dogged by high variance in the estimators common to IS, although recent work aims to address this (Munos et al., 2016; Guo et al., 2017). Model-based methods for off-policy evaluation have recently been improved to account for the distribution shift between the data-collecting policy and the policy to be evaluated (Johansson et al., 2016; Liu et al., 2018). Recently (Andrychowicz et al., 2017) proposed the Hindsight Experience Replay (HER) algorithm for learning a family of goal directed policies. In HER one observes an outcome in the true environment, which is kept fixed, and searches for the goal-directed policy that should have achieved this goal in order to positively reinforce it. Therefore, this algorithm is complementary to CF-GPS where we search over alternative outcomes for a given policy. Our CF-GPS algorithm is inspired by and extends work presented by Abbeel et al. (2006) on a method for de-biasing weak models by estimating additive terms in the transition kernel to better match individual, real trajectories. The resulting model, which is a counterfactual distribution in the terminology used in our paper, is then used for model-based policy improvement. Our work generalizes this approach and highlights conceptual connections to causal reasoning. Furthermore, we discuss the connection of CF-GPS to two classes of RL algorithms in greater detail below.
Guided Policy Search (GPS) CF-GPS is closely related to GPS, in particular we focus on GPS as presented by Levine & Abbeel (2014). Consider CF-GPS in the fully-observed MDP setting where Ot = St. Furthermore, assume that the SCM M is structured as follows: Let St+1 = fs(St, At, Ust) be a linear function in (St, At) with coefficients given by Ust. Further, assume an i.i.d. Gaussian mixture model on Ust for all t. As the states are fully observed, the inference step in the CFI procedure simplifies: we can infer the noise sources ûst (samples or MAP estimates), i.e. the unknown linear dynamics, from pairs of observed, true states ŝt, ŝt+1. Furthermore assume that the reward is a quadratic function of the state. Then, the counterfactual distribution pλ(τ |û) is a linear quadratic regulator (LQR) with time-varying coefficients û. An appropriate choice for the planner λ is the optimal linear feedback policy for the given LQR, which can be computed exactly by dynamic programming.
Observation 1. In the MDP setting, CF-GPS with a linear SCM and a dynamic programming planner for LQRs λ is equivalent to GPS.
Another perspective is that GPS is the counterfactual version of the MB-PS procedure from sec. 4.1:
Observation 2. In the MDP setting with a linear SCM and a dynamic programming planner for LQRs λ, GPS is the counterfactual variant of the MB-PS procedure outlined above.
The fact that GPS is a successful algorithm in practice shows that the ‘grounding’ of model-based search / rollouts in real, off-policy data afforded by counterfactual reasoning massively improves the naive, ‘prior sample’-based MB-PS algorithm. These considerations also suggest when we expect CF-GPS to be superior compared to regular GPS: If the uncertainty in the environment transition Ust cannot be reliably identified from subsequent pairs of observations ôt, ôt+1 alone, we expect benefits of inferring Ust from a larger context of observations, in the extreme case from the entire history ĥT as described above.
Stochastic Value Gradient methods There are multiple interesting connections of CF-GPS to Stochastic Value Gradient (SVG) methods (Heess et al., 2015). In SVG, a policy π for a MDP is learned by gradient ascent on the expected return under a model p. Instead of using the scorefunction estimator, SVG relies on a reparameterization of the stochastic model and policy (Kingma & Welling, 2013; Rezende et al., 2014). We note that this reparameterization casts p into an SCM. As in GPS, the noise sources Ust are inferred from two subsequent observed states ŝt, ŝt+1 from the true environment, and the action noise Uat is kept frozen. As pointed out in the GPS discussion, this procedure corresponds to the inference step in a counterfactual query. Given inferred values u for U , gradients ∂θG of the return under the model are taken with respect to the policy parameters θ. We can loosely interpret these gradients as 2 dim(θ) counterfactual policy evaluations of policies π(θ ±∆θi) where a single dimension i of the parameter vector θ is perturbed.

heading: 6 DISCUSSION

text: Simulating plausible synthetic experience de novo is a hard problem for many environments, often resulting in biases for model-based RL algorithms. The main takeaway from this work is that we can improve policy learning by evaluating counterfactual actions in concrete, past scenarios. Compared to only considering synthetic scenarios, this procedure mitigates model bias. However, it relies on some crucial assumptions that we want to briefly discuss here. The first assumption is that off-policy experience is available at all. In cases where this is e.g. too costly to acquire, we cannot use any of the proposed methods and have to exclusively rely on the simulator / model. We also assumed that there are no additional hidden confounders in the environment and that the main challenge in modelling the environment is capturing the distribution of the noise sources p(U), whereas we assumed that the transition and reward kernels given the noise is easy to model. This seems a reasonable assumption in some environments, such as the partially observed grid-world considered here, but not all. Probably the most restrictive assumption is that we require the inference over the noise U given data ĥT to be sufficiently accurate. We showed in our example, that we could learn a parametric model of this distribution from privileged information, i.e. from joint samples u, hT from the true environment. However, imperfect inference over the scenario U could result e.g. in wrongly attributing a negative outcome to the agent’s actions, instead environment factors. This could in turn result in too optimistic predictions for counterfactual actions. Future research is needed to investigate if learning a sufficiently strong SCM is possible without privileged information for interesting RL domains. If, however, we can trust the transition and reward kernels of the model, we can substantially improve model-based RL methods by counterfactual reasoning on off-policy data, as demonstrated in our experiments and by the success of Guided Policy Search and Stochastic Value Gradient methods.

heading: A PROOFS

text:
A.1 PROOF OF LEMMA 1
Proof. We start from the fact that the density over noise sources U remains the same for every intervention I as U are root nodes in G:
pdo(I)(u) = p(u).
This leads to:
pdo(I)(x) = ∫ pdo(I)(x|u)pdo(I)(u) du
= ∫ pdo(I)(x|u)p(u) du
= ∫ pdo(I)(x|u) (∫ p(x̂o, u)dx̂o ) du
= ∫ ∫ pdo(I)(x|u) p(u|x̂o)p(x̂o) du dx̂o
= Ex̂o∼p[ ∫ pdo(I)(x|u)p(u|x̂o) du]
= Ex̂o∼p[pdo(I)|x̂0(x)].
A.2 PROOF OF COROLLARY 1
Proof. Given two sets CF ⊂ {1, . . . , N} and Prior ⊂ {1, . . . , N} with CF ∩ Prior = ∅ and CF∪Prior = {1, . . . , N}, we define uCF = (un)n∈CF and uPrior = (un)n∈Prior. By construction, the scenarios U are independent under the prior, i.e. p(u) = ∏N n=1 p(un). Therefore uCF and uPrior are independent. We can write:
p(u) = ( ∏ n∈CF p(un) )( ∏ n∈Prior p(un) ) = p(uCF)p(uPrior).
Following the arguments from Lemma 1, the averaged inference distribution is equal to the prior p(u) = Ex̂o∼p[p(u|x̂o)]. This also holds for any subset of the variables u, in particular for for p(uCF). Hence:
p(u) = p(uCF)p(uPrior)
= Ex̂o∼p[p(uCF|x̂o)]p(uPrior).

heading: B DETAILS ON CASTING A POMDP INTO SCM FORM

text:
Lemma 2 (Auto-regressive uniformization aka Reparametrization). Consider random variables X1, . . . , XN with joint distribution P . There exist functions fn for n ∈ {1, . . . , N} such that with independent random variables Un ∼ Uniform[0, 1] the random variables X ′ equal X in distribution, i.e. X ′ d= X , where X ′ = (X ′1, . . . , X ′ n) are defined as:
X ′n := fn(Un, X ′ <n).
Proof. We construct the functions fn by induction on n. Consider the conditional distribution PXn|X<n . For fixed X<n, denote its CDF with Fn,X<n . We construct a random variable X ′ := F−1n,X<n(Un) with Un ∼ Uniform[0, 1] independent from X<n and U<n. By virtue of the inverse-CDF method, we have X ′|X<n d = X|X<n. Therefore, fn(Un, X<n) := F−1n,X<n(Un) satisfies the above lemma.

heading: C MODEL ARCHITECTURE

text: We assume that we are given the true transition and reward kernels. As the transitions are deterministic in PO-SOKOBAN, the only part of the model that remains to be identified is the initial state distribution p(Us1). We learned this model from data using a the DRAW model (Gregor et al., 2015), which is a parametric, multi-layer, latent variable, neural network model for distributions. For our purposes we chose the convolutional DRAW architecture proposed by (Gregor et al., 2016). First, the observation data is summarized by a convolutional LSTM with 32 hidden units and kernel size of 3. The resulting final LSTM state is fed into a conditional Gaussian prior over the latent variables Zk=1,...,8 of the 8-layer conv-DRAW model. Each layer has 32 hidden layers and the canvas had 7 layers, corresponding to the 7 channels of the categorical Us1 ∈ {0, 1}10×10×7 that we wish to model. The model (together with the backward RNN) was trained with the ADAM optimizer (Kingma & Ba, 2014) on the ELBO loss using the reparametrization trick (Kingma & Welling, 2013; Rezende et al., 2014). The mini-batch size was set to 4 and the learning rate to 3e− 4. We want to emphasize that the DRAW latent variables Z are not directly the noise variables U of the SCM, but integrating out these variables yields this distribution p(Us1|ĥT ) = ∫ p(Us1|z, ĥT )p(z|ĥT )dĥT .

heading: D MODEL MISMATCH ANALYSIS

text:
Here we provide some analysis of the DRAW model over the initial state Us1, which is the learned part of the SCMM used for the policy evaluation experiments presented in 3.2. As detailed above, we trained a separate model p(Us1|ĥt) for each t = 1, . . . , 50 parameterizing the cardinality of the data the model is conditioned on. We analyze three particular models for t = 0, 1 and 50 which we term the unconditional / filtering / smoothing model, as they are conditioned on no data / on data that is available at test time / all data that is available in hindsight. Directly visualizing the distributions p(Us1|ĥt) for an analysis is difficult as the domain {0, . . . , 6}10×10 is high-dimensional and discrete. Instead we focus on the latent variables Z which are learned by DRAW to represent this distribution; by construction, these are jointly Normal, facilitating the analysis. In particular, we compare p(Z|ĥt) with the inference distribution q(Z|ûs1) conditioned on the true state Ûs1. We loosely interpret q(Z|ûs1) as the ”true” embedding of the datum ûs1, whereas p(Z|ĥt) is the learned
embedding. In a perfect model the prior matches the inference distribution on average:
Eĥt∼pµ [p(Z|ĥt)] ! = Eûs1∼pµ [q(Z|ûs1)],
i.e. every sample from the prior p(Z|ĥt) corresponds to real data and vice versa. We visualize the averaged prior Eĥt∼pµ [p(Z|ĥt)] and the averaged posterior Eûs1∼pµ [q(Z|ûs1)] in fig. 4. We show the two dimensions of Z where these distributions have the largest KL divergence. Also, the plots were whitened w.r.t. the averaged prior, i.e. the latter is a spherical Gaussian in the plots, represented by an iso-probability contour corresponding to one standard deviation. The inference distribution for each datum ûs1 is visualized by its mean (cross) and a level set corresponding the one standard deviation or less. For the unconditional model t = 0, we find that the distributions are not matched well. In particular, there is a lot of prior mass that sits in regions where there is no or little true data. In the RL setting this results in synthetic data from the model that is unrealistic and training a policy on this data leads to reduced test performance. Also, as apparent from the figure, there is structure in the embedding of the true data, that is not captured at all by the prior. This effect is markedly reduced in the filtering posterior, indicating that the conditional distribution p(Z|ĥ1) already captures the data distribution better. The smoothing model is a very good match to the data. With high probability, all tiles of the game are observed in ĥ50, enabling the model to perfectly learn the belief state, which collapses in this setting to a single state.


summaries: This paper argues that analyzing loss surfaces in parameter space for the purposes of evaluating adversarial robustness and generalization is ineffective, while measuring input loss surfaces is more accurate. By converting loss surfaces to decision surfaces (which denote the difference between the max and second highest logit), the authors show that all adversarial attack methods appear similar wrt the decision surface. This result is then related to the statistics of the input Jacobian and Hessian, which are shown to differ across adversarially sensitive and robust models. Finally, a regularization method based on regularizing the input Jacobian is proposed and evaluated. All of these results are shown through experiments on MNIST and CIFAR-10.

summaries: The authors demonstrated that the loss surface visualized in parameter space does not reflect its robustness to adversarial examples. By analyzing the geometric properties of the loss surface in both parameter space and input space, they find input space is more appropriate in evaluating the generalization and adversarial robustness of a neural network. Therefore, they extend the loss surface to decision surface. They further visualized the adversarial attack trajectory on decision surfaces in input space, and formalized the adversarial robustness indicator. Finally, a robust training method guided by the indicator is proposed to smooth the decision surface.

abstractText: One popular hypothesis of neural network generalization is that the flat local minima of loss surface in parameter space leads to good generalization. However, we demonstrate that loss surface in parameter space has no obvious relationship with generalization, especially under adversarial settings. Through visualizing decision surfaces in both parameter space and input space, we instead show that the geometry property of decision surface in input space correlates well with the adversarial robustness. We then propose an adversarial robustness indicator, which can evaluate a neural network’s intrinsic robustness property without testing its accuracy under adversarial attacks. Guided by it, we further propose our robust training method. Without involving adversarial training, our method could enhance network’s intrinsic adversarial robustness against various adversarial attacks.

authors:
Guillaume Alain
Nicolas Le Roux
Pierre-Antoine Manzagol

title: Negative eigenvalues of the hessian in deep neural networks. 2018

authors:
Sue Becker
Yann Le Cun

title: Improving the convergence of back-propagation learning with second order methods

venue: In Proceedings of the 1988 connectionist models summer school,

authors:
Nicholas Carlini
David Wagner

title: Towards evaluating the robustness of neural networks

venue: IEEE Symposium on Security and Privacy (SP),

authors:
P Chaudhari
Anna Choromanska
S Soatto
Yann LeCun
C Baldassi
C Borgs
J Chayes
Levent Sagun
R Zecchina

title: Entropy-sgd: Biasing gradient descent into wide valleys

venue: In International Conference on Learning Representations (ICLR),

authors:
Jeff Cheeger
David G Ebin

title: Comparison theorems in Riemannian geometry, volume 365

venue: American Mathematical Soc.,

authors:
Moustapha Cisse
Piotr Bojanowski
Edouard Grave
Yann Dauphin
Nicolas Usunier

title: Parseval networks: Improving robustness to adversarial examples

venue: In International Conference on Machine Learning,

authors:
Laurent Dinh
Razvan Pascanu
Samy Bengio
Yoshua Bengio

title: Sharp minima can generalize for deep nets

authors:
Harris Drucker
Yann Le Cun

title: Double backpropagation increasing generalization performance

venue: In Neural Networks,

authors:
Ian J Goodfellow
Oriol Vinyals
Andrew M Saxe

title: Qualitatively characterizing neural network optimization problems

title: Explaining and harnessing adversarial examples

venue: arXiv preprint arXiv:1412.6572,

authors:
Daniel Jiwoong Im
Michael Tao
Kristin Branson

title: An empirical analysis of deep network loss surfaces

venue: arXiv preprint arXiv:1612.04010,

authors:
Harini Kannan
Alexey Kurakin
Ian Goodfellow

title: Adversarial logit pairing

venue: arXiv preprint arXiv:1803.06373,

title: Deep learning without poor local minima

venue: In Advances in Neural Information Processing Systems,

authors:
Nitish Shirish Keskar
Dheevatsa Mudigere
Jorge Nocedal
Mikhail Smelyanskiy
Ping Tak Peter Tang

title: On large-batch training for deep learning: Generalization gap and sharp minima

authors:
Alexey Kurakin
Ian Goodfellow
Samy Bengio

title: Adversarial examples in the physical world

venue: arXiv preprint arXiv:1607.02533,

authors:
Hao Li
Zheng Xu
Gavin Taylor
Tom Goldstein

title: Visualizing the loss landscape of neural nets

venue: arXiv preprint arXiv:1712.09913,

authors:
Aleksander Madry
Aleksandar Makelov
Ludwig Schmidt
Dimitris Tsipras
Adrian Vladu

title: Towards deep learning models resistant to adversarial attacks

title: Deep learning via hessian-free optimization

authors:
II Ororbia
G Alexander
C Lee Giles
Daniel Kifer

title: Unifying adversarial training algorithms with flexible deep data gradient regularization

venue: arXiv preprint arXiv:1601.07213,

authors:
Nicolas Papernot
Patrick McDaniel
Somesh Jha
Matt Fredrikson
Z Berkay Celik
Ananthram Swami

title: The limitations of deep learning in adversarial settings

venue: In Security and Privacy (EuroS&P),

authors:
Nicolas Papernot
Patrick McDaniel
Xi Wu
Somesh Jha
Ananthram Swami

title: Distillation as a defense to adversarial perturbations against deep neural networks

venue: In 2016 IEEE Symposium on Security and Privacy (SP),

authors:
Andrew Slavin Ross
Finale Doshi-Velez

title: Improving the adversarial robustness and interpretability of deep neural networks by regularizing their input gradients

venue: In AAAI,

authors:
Christian Szegedy
Wojciech Zaremba
Ilya Sutskever
Joan Bruna
Dumitru Erhan
Ian Goodfellow
Rob Fergus

title: Intriguing properties of neural networks

venue: arXiv preprint arXiv:1312.6199,

authors:
Hongyi Zhang
Moustapha Cisse
Yann N Dauphin
David Lopez-Paz

title: mixup: Beyond empirical risk minimization

venue: arXiv preprint arXiv:1710.09412,

heading: 1 INTRODUCTION

text:
It is commonly believed that a neural network’s generalization is correlated to its geometric properties of the loss surface, i.e. the flatness of the local minima in parameter space (Kawaguchi (2016); Im et al. (2017)). For example, Keskar et al. (2017) showed that a sharp local minima brings poorer neural network generalization. Li et al. (2017) visualized and demonstrated that the outstanding performance of ResNet comes from its “wide valley” of the local minima on the loss surface. Chaudhari et al. (2017) then proposed Entropy-SGD, which utilizes the “wide valleys” property to guide the neural network training for better generalization.
However, such a generalization estimation approach is challenged by adversarial examples recently (Szegedy et al. (2013)): even models with good generalization may still suffer from adversarial examples, resulting in extremely low accuracy. For example, ResNet model usually converges to a wide and flat local minima on loss surface in parameter space as visualized in Fig. 1(a), which indicates good test accuracy according to the mentioned evaluation approach. When testing adversarial examples, the model’s accuracy is significantly defected by the adversarial noises, which are small, but can cause dramatically loss increments. Therefore, the conventional generalization estimation in parameter space fails under adversarial settings, and how to estimate the generalization over adversarial examples, i.e. the adversarial robustness, remains a significant challenge.
Fortunately, the loss increments introduced by adversarial noises can be well reflected in the loss surface in input space as visualized in Fig. 1(b), where the non-smoothness indicates high sensitivity
to the adversarial noises. The differences in Fig. 1 suggest the ineffectiveness of generalization estimation in parameter space and the potential in input space. Therefore, different from prior works focusing on parameter space, we will explore the robustness estimation mainly in input space.
In this work, we have the following contributions:
• We analyze the geometric properties of the loss surface in both parameter and input space. We demonstrate that the input space is more essential in evaluating the generalization and adversarial robustness of a neural network;
• We reveal the shared mechanisms of various adversarial attack methods. To do so, we first extend the concept of loss surface to decision surface for clearer geometry visualization. By visualizing the adversarial attack trajectory on decision surfaces in input space, we reveal that various adversarial attacks are all utilizing the decision surface geometry properties to cross the decision boundary within least distance.
• We then formalize the adversarial robustness indicator by involving the geometric properties of Jacobian and Hessian’s eigenvalues. Such an indicator can effectively evaluate a neural network’s intrinsic robustness property against various adversarial attacks without field accuracy testing of massive adversarial examples; It also concludes that the wide and flat plateau of decision surface in input space enables better generalization and robustness.
• We also propose a robust training method guided by our adversarial robustness indicator, which aims to smooth the decision surfaces and enhances adversarial robustness by regulating the Jacobian in training process.
Our robustness estimation approach has provable relationship with neural network’s robustness performance and geometry properties in input space. This enables us to evaluate adversarial robustness of a neural network, without conducting massive adversarial attacks for field test. Guided by such an estimation approach, our robust training method could also effectively enhance the neural network against various adversarial attacks without involving the time-consuming adversarial training.

heading: 2 INEFFECTIVENESS OF ADVERSARIAL ROBUSTNESS ESTIMATION FROM THE LOSS SURFACE IN PARAMETER SPACE

text: In this section, we compare the effectiveness of the adversarial robustness estimation from the loss surface in both parameter and input space with an effective visualization method.

heading: 2.1 VISUALIZATION NEURAL NETWORK LOSS SURFACE BY PROJECTION

text:
Given a neural network with a loss function F (θ, x), where θ is neural network parameters (weight and bias) and x is the input. As the function inputs are usually in high-dimensional space, direct visualization analysis on the loss surface is impossible. Therefore, following the methods proposed by Goodfellow et al. (2015) and Li et al. (2017), we project the high-dimensional loss surface into a low-dimensional space, e.g. 2D hyperplane to visualize it. In such methods, two projection vectors α and β are chosen and normalized as the base vectors for x and y axes. Then given an starting point o, the points around it are interpolated and corresponding loss values can be calculated:
V (i, j, α, β) = F (o+ i · α+ j · β) (1)
Here, the original point o in function F could be either in parameter space, which is mostly studied by prior work (e.g. Li et al. (2017); Im et al. (2017)), or in input space, which is our major focus in this paper. The coordinate (i, j) denotes how far the original point moves along α and β direction. After calculating enough points’ loss values, the function F with high-dimensional inputs could be projected to the chosen hyperplane formed by vector α and β.
Fig. 1 has already shown two visualized loss surface examples in both parameter space and input space, which give an intuition of the dramatic difference between the two approaches. In the next section, we will further demonstrate that the loss surface geometry in input space is more essential regarding the neural network robustness properties.

heading: 2.2 THE LOSS SURFACE IN PARAMETER SURFACE VS. INPUT SPACE

text:
To prove our statement, we examine the robustness of a pair of neural networks with the same ResNet model setting, but trained with natural process and Min-Max robust training scheme respectively. Both neural networks could achieve optimal accuracy (∼ 90%) on CIFAR10 dataset. However, their adversarial robustness degrees are significantly different: 0.0% and 44.71% accuracy under `∞ = 8 adversarial attacks. To analyze such a difference, the loss surfaces and corresponding contour maps are visualized in both parameter space (as shown in Fig. 2) and input space (as shown in Fig. 3). Here the z-axis of 3D visualization denotes the loss values (as well as the numbers on contour lines in 2D visualization), and the x and y axes are the corresponding projection vectors α and β.
When illustrated in parameter space, both neural networks’ loss surfaces on local minima are wide and flat, which align well with their high accuracy as stated in (Li et al. (2017)). But comparing Fig. 2 (a) and (b), even though the two neural networks have distinct degrees of robustness, there is no obvious difference between their loss surfaces in parameter space. More examples could be found in Appendix 8.5, which also indicates the limitations of parameter space loss to describe robustness.
However when illustrated in input space as shown in Fig. 3, obvious differences emerge between the natural and robust neural networks: (1) Based on the 3D surface visualization, the natural neural network’s loss surface in input space has a deep and sharp bottom, while the local minima one the loss surface of the robust neural network is much flatter; (2) Based on the contour map visualization, we show that the original inputs in the natural neural network’s surface locate in a very small valley, while the robust one shows a wide area. Thus, in the natural neural network’s case, once some small perturbations are injected into the inputs and move the inputs out of the small valley, the function loss will significantly increase and the prediction result could be easily flipped.
By comparison of parameter space and input space loss surfaces, we demonstrate the potential advantages of using loss surfaces in input space than in parameter space. Therefore, we clarify that in terms of generalization and adversarial robustness, we should not only focus on the so-called “wide valley” of loss surfaces in parameter space, but also in input space. In the next section, we will visualize the adversarial attack trajectory and further demonstrate the close relation between adversarial vulnerability and decision surface geometry in input space.

heading: 3 REVEALING ADVERSARIAL ATTACKS’ MECHANISM THROUGH DECISION SURFACE ANALYSIS

text: Previously, we showed the potential of adversarial robustness estimation in input space. In this section, we further explore the adversarial attacks’ mechanism with input space decision surface.

heading: 3.1 EXTEND LOSS SURFACE TO DECISION SURFACE

text:
Directly visualizing loss surfaces in input space has certain disadvantages: The major issue is that there is no explicit decision boundary for the correct or wrong prediction for a given input image; Another deficiency of cross entropy based loss surface is that it cannot well demonstrate the geometry, especially when the loss is relatively low 1. This usually causes large blank regions with no useful information in visualization. To resolve these problems, we extend the concept of loss surface to decision surface, which enriches the geometry information and offers clear decision boundary.
Here, we introduce the definition of neural network decision boundary and decision surface. For one input image x with label yt, the decision boundary of a neural network is defined as following:
L(x) = Z(x)t − max{Z(x)i, i 6= t} = 0. (2)
Z(x) is the logit layer output before softmax layer, and t is the true class of input x. The decision function L(x) evaluates the confidence of prediction, i.e. how much correct logit output exceeds the max incorrect logit. In correct prediction cases, L(x) should always be positive and higher value is often better (different from cross-entropy loss that lower is better). L(x) = 0 indicates the equal confidence in correct and wrong class, and thus is the decision boundary between correct and wrong prediction. The surface formed by function L(x) is called the decision surface to distinguish from cross entropy based loss surface, also because it contains the explicit decision boundary.
Fig. 4 compares the cross entropy based loss surface visualization (first row) and the decision surface visualization (second row). The decision surfaces can well resemble the loss surfaces in their informative areas but also include the confidence information in the blank area of the loss surfaces. Meanwhile, the explicit decision boundary, i.e. contour line L(x) = 0, enables us to clearly see when network decision changes, which is very useful in analyzing adversarial examples as we will show next. In the following paper, we will use decision surface visualization as default settings.

heading: 3.2 SHARED MECHANISM OF VARIOUS ADVERSARIAL ATTACKS

text:
As shown in Eq. 1, we could project the decision surface to a hyperplane composed of two base vectors – α and β. Therefore, using adversarial attacking direction δ as the projection vector β (y-axis), we could visualize the adversarially projected decision surfaces and the corresponding attack trajectory along the y-axis direction.
For generality, we compare four cases with different projection vector β: The first one is random direction, but the other three are produced from three representative adversarial attack objective functions: cross-entropy non-targeted loss, cross-entropy targeted loss (least-likely class) (Kurakin
1For the same input image, neural network prediction with high confidence can have similar loss with low confidence prediction due to the non-linear operations. Detailed analysis could be find in the Appendix.
et al. (2016)), and C&W loss (Carlini & Wagner (2017)):
β = sign(∇x loss(x)), where loss(x) ∈ { ytlog(softmax(Z)), yllog(softmax(Z)) , max{Z(x)i, i 6= t} − Z(x)t. },
(3)
where yt is the true class label, yl is least likely class label (both one-hot).
The decision surface and adversarial trajectory visualization results are shown in Fig. 4. The length of blue and green arrows denote the distance needed to cross the decision boundary. In random projection (a), the length of green arrows is long. This indicates that towards a random direction, the original input is far from neural network’s decision boundary or wrong classification regions with L(x) < 0. This explains the common sense that natural images with random noises won’t degrade neural network accuracy significantly. However, in adversarially projected hyperplane (b-d), wrong regions are much closer indicated by extremely short arrows: Towards y-axis adversarial direction, adversarial examples could be easily found and even within `inf(δ) = 1.
Comparing different adversarial attack trajectories in Fig. 4(b)-(d), we could find that they all demonstrate similar behaviors even though their objective functions are designed differently: All y-axis attack directions show extremely dense contour lines. This denotes the steepest descent direction to cross decision boundary L = 0 and to enter wrong classification regions. Therefore, we can conclude the shared mechanism by different adversarial attacks, which is to utilize the decision surface geometry information to cross the decision boundary within shortest distance.
Meanwhile, our visualization results reveal the nature of adversarial examples: Although a neural network’s training loss in parameter space seems to converge well after model training, there still exist large regions of points that the neural network fails to classify correctly (proved by the large negative regions on the adversarial projected hyperplane). And some of these regions are extremely close to the original input points (some even within `inf(δ) = 1 distance). Since the data points in such regions are in the close neighborhood of the natural input images, they seem no difference by human vision, which is conventionally recognized as adversarial examples.
Therefore, we conclude that rather than being "crafted" by adversarial attacks, adversarial examples are "naturally existed" points. Rather than defending "adversarial attacks", the essential solution of robustness enhancement is to solve the "neighborhood under-fitting" issue of neural networks. We then propose an adversarial robustness evaluation approach, which uses decision surface’s differential geometry property to interpret and evaluate the neural network robustness.

heading: 4 ADVERSARIAL ROBUSTNESS INDICATOR WITH DECISION SURFACE GEOMETRY

heading: 4.1 THEORETICAL ROBUSTNESS BOUND BASED ON SECOND-ORDER TAYLOR EXPANSION

text:
Suppose neural network decision function L(θ, x) is second-order differentiable. We have noticed that the neural network decision surface in input space captures more information about adversarial vulnerability. Since L(θ, x) has no explicit formulation, we could utilize the second-order Taylor Approximation w.r.t input x to approximate it within x′s neighborhood:
L(θ, x+ ∆x) = L(θ, x) + J∆x+ 1
2! ∆xTH∆x, (4)
where θ is the parameters of the neural network. The Jacobian vector J is of the same dimension with x , and x is the input feature vector. And Hessian matrix H is a square matrix of second-order partial derivatives of F (θ, x) with regard to x.
Given a correctly classified input x with confidence L(θ, x) = t (t > 0). In adversarial settings, the adversarial robustness of neural network means that given a feasible set S, e.g. `∞ constraints, all perturbations in this set cannot change the decision. Formally, it can be defined as following:
sign(L(θ, x+ δ)) = sign(L(θ, x)), ∀δ ∈ S. (5)
To connect this objective function with our decision surface, we enforce a new constraint:
|L(θ, x+ δ)− L(θ, x)| < t, ∀δ ∈ S. (6)
This leads to L(θ, x+ δ) ∈ (0, 2t), thus L(θ, x+ δ) has the same sign with L(θ, x). Clearly, Eq. 5 is strictly guaranteed. Meanwhile, this formulation enforces stronger constraints: it means when neural network predicts, its neighborhood points should not only share the same decision but also have similar confidence bounded by absolute difference t, similar with mixup (Zhang et al. (2017)).
Then, combining Taylor Approximation in Eq. 4 and Eq. 6, the following inequality can be derived:
max δ∈S ( |J · δ + 1 2 δTHδ| ) < t. (7)
Since Hessian matrix H is orthogonally diagonalizable, it could be decomposed by eigendecomposition: H = EΛET . E is the eigenvector matrix [e0, e1, · · · , en] composed of H’s eigenvectors ei, and Λ is the diagonal eigenvalue matrix with only H’s eigenvalues in the diagonal as the non-zero entries. Let y = ET δ, we have:
δTHδ = δTEΛET δ = (ET δ)TΛ(ET δ) = yTΛ y. (8)
Therefore, we could show that the upper bound of Eq. 7 is:
|J · δ + 1 2 δTHδ| ≤ |J · δ|+ 1 2 |yTΛ y| ≤ n∑ i=1 |Ji| · |δi|+ 1 2 n∑ i=1 |λi| · |y2i |. (9)
Here δi and yi are the entries of vector δ and y, which depend on the choice of perturbation δ. Ji is the entry of Jacobian vector, and λi is the eigenvalue of Hessian H . Intuitively, given the constraints on δ (e.g. `∞ constraints), the upper bound highly depends on the Jacobian and Hessian matrix. As long as the magnitude of every Ji and eigenvalue λi of Hessian H could be controlled to the minimum, e.g. near zeros, the influence of perturbation δ can be constrained to a certain range, i.e. robust to any noises. Therefore, the average magnitude of these two parameter sets of a neural network could be defined as its robustness indicator.

heading: 4.2 THE GEOMETRIC EXPLANATION OF ROBUSTNESS INDICATOR

text:
As shown in Eq. 9, model robustness highly relies on the magnitude of Jacobian entries and eigenvalues of Hessian. In differential geometry, these parameters has their specific geometry meaning:
For a multi-variable function F (x), Jacobian entry Ji measures the slope of the tangent vector at point x along xi axis, where low value denotes flat neighborhood. Therefore, it’s easy to understand that smaller Jacobian leads to a flat minima. Meanwhile, magnitude of eigenvalues λi of Hessian denotes the curvature (Alain et al. (2018); Cheeger & Ebin (2008)), which is defined as:
κ = 1/r. (10)
κ is the reciprocal of the radius R of osculating circle at current point. The conception in simple 1-d case is shown in Fig. 5. Clearly, lower curvature (small eigenvalues) means that the hyperplane bends less, leading to a wider neighborhood of original point.
Based on the differential geometry meaning of Jacobian and Hessian, we could conclude that both constraints on Jacobian and Hessian in Eq. 9 appeal for a wider and flatter local neighborhood of input space decision surface (not parameter space). This is consistent with our preliminary visualization results in Fig. 3. Next, we will qualitatively and quantitatively demonstrate the effectiveness of our neural network robustness indicator.

heading: 4.3 ROBUSTNESS INDICATOR EVALUATION: A CASE STUDY

text:
Decision Surface of Natural Model vs. Robust Model In this section, we compare two pairs of robust and natural models on MNIST and CIFAR10. The two pair of models are released in MNIST/CIFAR adversarial challenges (Madry et al. (2018)) with same structure and comparable accuracy in natural test settings but different degree of robustness. The robust MNIST model is trained by Min-Max optimization and could achieve ∼88% accuracy under all attacks with the `∞ < 0.3 constraints on a (0, 1) pixel range, which is believed to be the currently most robust model
on MNIST dataset. By contrast, the natural model can be totally broken with 0.0% accuracy within same constraints. CIFAR models are same as Sec. 2. To prove our geometric robustness theory, we first visualize two pair of models’ decision surfaces in Fig. 6 (MNIST), and Fig. 7 (CIFAR10).
From Fig. 6, we can find significant difference between natural and robust decision surface: On robust decision surfaces (c) and (d), whether we choose random or adversarial projection, all neighborhood points around the original input point locates on the high plateau with L(x) > 0. The surface in the neighborhood is rather flat with minimum slopes until it reaches `∞ < 0.3 constraints, which is the given adversarial attack constraint. This explains its exceptional robustness against all adversarial attacks. By contrast, natural decision surfaces shows sharp peaks and large slopes, on which decision confidence could quickly drop to negative along the y-axis. For CIFAR10 models as shown in Fig. 7, similar conclusions could be drawn that the degree of adversarial robustness depends on how well models could fit the neighborhood of input points, and a flat and wide plateau around the original points on decision surface is one of the most desired properties of a robust model 2.
Jacobian and Hessian Statistics Analysis We also analyze the statistics of previous natural and robust MNIST model’s Jacobian and Hessian matrix. We randomly take 100 input images from test set and calculate their Jacobian and Hessian using natural and robust model, respectively. The data distribution and visualization results are shown in Fig. 8.
First, the `1 norm of robust model’s Jacobian is much smaller than natural models: average `1 norm of robust model’s Jacobian is about ∼ 50, ten times less than ∼ 500 of natural model’s. And `1 norm of robust model’s Hessian are 0.53, two times less than 1.26 of natural models’. Therefore, the statistics
2More examples could be found in Appendix.
of Jacobian and Hessian also verifies our robustness indicator theory in Eq. 9. Another significant difference is that compared to natural model, robust model’s Jacobian and Hessian are more sparse. For natural and robust models, the ratio of zeros in Jacobian are 1.1% and 54.0% respectively. As for Hessian, the ratio of zeros in eigenvalues for natural and robust models are 65.6% and 97.1% respectively3. One intuitive explanation of the relationship between robustness with Jacobian sparsity is that natural model’s Jacobian contains many un-meaningful but noisy gradients, while most of robust model’s Jacobian non-zero entries concentrate on the main trace of the digits, or so-called main features. This assumption is based on our observation that for most input images, robust model’s Jacobian could precisely capture the main trace of digits or main patterns of the object, as shown in Fig. 8. In such ways, if adversarial noise is uniformly injected into every pixel of the input image, only a small portion of them will be likely to influence decision, thus more robust to perturbations.

heading: 5 TOWARD ROBUSTNESS ENHANCEMENT AGAINST ADVERSARIAL ATTACKS

heading: 5.1 ROBUST TRAINING FOR SMOOTHING DECISION SURFACE IN INPUT SPACE

text:
As shown in Eq. 9, better robustness of neural networks needs lower magnitude or zero Jacobian and Hessian. Here, we use Jacobian of our decision function L(θ, x) w.r.t x. Therefore to improve the network robustness and flatten the local minima, we propose a simple yet effective approach: add a regularizer on the Jacobian of decision loss L(x) in network training process. This could be done through double backpropagation (Drucker & Le Cun (1991)). As for Hessian eigenvalue, calculating the Hessian eigenvalues takes Θ(k3) complexity (k is parameter space dimension). Currently there is no efficient way to regulate it in neural network context. Possible techniques to use are Hessian diagonal approximation (Martens (2010); Becker et al. (1988)), which we leave as future work.
To regulate the Jacobian of decision function L(θ, x), we could add a regularization term on ∂L(θ, x)/∂x to network training loss Lossθ(x):
Lossθ(x) = Lce + c · Lnorm( ∂L(θ, x)
∂x ), (11)
where Lce is cross-entropy loss, and hyper parameter c is the factor of penalty strength. For the regulation term Lnorm(·), we can choose `1, `2 or `∞. As aforementioned, introducing the gradient loss into the training loss needs us to solve a second-order gradient computing problem. To solve this problem, double backpropagation (Drucker & Le Cun (1991)) is needed. The cross-entropy loss are first computed by forward-propagation, with the gradients then being calculated by backpropagation. Note here we need to calculate both ∂Lce/∂θ and ∂L(θ, x))/∂x as required in Eq. 12. Then, to minimize the gradient loss, the second-order mixed partial derivative of gradient loss w.r.t θ is calculated. Note this mixed partial derivative is different from Hessian (which is pure secondorder derivative of x or w), and thus is calculable (Ororbia et al. (2016)). After this, a second
3Jacobian and Hessian matrix entries are mostly near zero but non-zero values, therefore we consider values below 10e-3 (Jacobian) and 10e-10 (Hessian) as zeros.
backpropagation operation is performed, and the weights of neural networks are updated according to gradient descent algorithm:
θ ′ = θ − lr · (∂Lce ∂θ )− lr · c (∂Lnorm(∂L(θ, x)/∂x) ∂θ ). (12)
Compared to adversarial training based defense techniques, our proposed robust training method doesn’t rely on adversarial example generation method, and thus is capable to defend against different adversarial attacks. The main extra computation overhead is the doubled backpropagation computation time, which we will show in the following experiments.

heading: 5.2 ROBUST TRAINING PERFORMANCE EVALUATION

text:
For comparison of the effect of robustness enhancement, we conduct different previous techniques: adversarial training (Kurakin et al. (2016)), cross-entropy gradient regularization (Ross & DoshiVelez (2018)), Min-Max training (Madry et al. (2018)), our method, and etc. Evaluated adversarial attacks include Fast Gradient Sign Method (FGSM), Basic Iterative Method (BIM) and C&W attack. Detailed experiment settings could be found in Appendix. Final results are shown in Table. 1 and 2.
On MNIST dataset, our proposed gradient regularization method can achieve ∼ 90% accuracy under all considered attacks within `∞ = 0.1 constraints. Cross entropy gradient regularization (Ross & Doshi-Velez (2018)) achieves similar robustness as ours within `∞ = 0.1, but their robustness performance drops very fast when adversarial attacking strengths increases, e.g. under `∞ = 0.2, 0.3 attacks. The reason is that the softmax and cross entropy operation introduces unnecessary nonlinearity, in which case the gradients from cross entropy loss is already very small.
Improving robustness on CIFAR10 dataset is much harder than MNIST. State-of-the-art MinMax training achieves ∼ 40% accuracy under strongest attacks in considered settings. But this method highly relies on huge amounts of adversarial data augmentation methods, which takes over 10 times of overhead during training process. By contrast, our method doesn’t need adversarial example generation and can achieves comparable robustness under `∞ = 3 constraints. We test the average time of each epoch for both natural training and gradient regularized training. Our time consumption is average 2.1 times than natural training per epoch. Notice that the robustness enhancement of our method becomes lower when `∞ becomes larger. This shows one limitation of gradient regularization methods: Our gradient regularization approach is based on Taylor approximation in a small neighborhood. When the adversarial examples exceeds the reasonable approximating range, the gradient regularization effect also exhausts. Empirically, we found robust training usually takes more epochs to converge: On CIFAR10, natural training takes about 30 epochs, our method usually need 100 epochs, and MinMax robust training takes over 400 epochs to converge in our implementation.

heading: 5.3 ANALYZING THE INPUT SPACE DECISION SURFACE AND STATISTICS

text:
To test if our robust training method flattens the loca minima of decision surfaces, we also visualize and comapre natural and our model’s decision surface, as shwon in Fig. 9. Compared to natural model’s surface, our model clearly has wider local neighborhood and lower slopes as expected. Meanwhile, the statistics of Jacobian and Hessian on MNIST models also align well with our previous robustness indication: The average `1 norm of Jacobian and Hessian of our models are 10 and 3 times less than natural model, respectively.
Fig. 10 shows several examples and their Jacobian visualization of both natural and robust models (normalized to 0 ∼ 255 range for visualization). The robust model’s Jacobian demonstrates better capability to capture the main feature of images on both MNIST and CIFAR10, as mentioned before.

heading: 6 RELATED WORK

text: Previous one popular hypothesis is that neural network’s good generalization comes from flat local minima of the loss function in parameter space (Im et al. (2017); Keskar et al. (2017); Dinh et al. (2017); Kawaguchi (2016)). For example, Li et al. (2017) propose a visualize technique which establishes good connections between the minima geometry and generalization on ResNet. However, recently adversarial examples were introduced, which challenges the above generalization theory. Many adversarial attack methods are proposed (Szegedy et al. (2013); Kurakin et al. (2016); Carlini & Wagner (2017); Papernot et al. (2016a)). As for defense techniques, current defense techniques include adversarial training (Ian J. Goodfellow (2014)), defensive distillation (Papernot et al. (2016b)), parseval network (Cisse et al. (2017)), Min-Max robustness optimization (Madry et al. (2018)), adversarial logit pairing (Kannan et al. (2018)), and etc. Original adversarial training techniques augment the natural training samples with corresponding adversarial examples together with correct labels. Recently proposed Min-Max robustness optimization (Madry et al. (2018)) augments the training dataset with large amount of adversarial examples which cause the maximum loss increments within a `∞-norm ball, which is currently the strongest defense.

heading: 7 CONCLUSION

text: In this work, through visualizing network loss surface in parameter and input space, we point out the ineffectiveness of previous generalization theory under adversarial settings. Meanwhile, we show that adversarial examples are essentially the neighborhood under-fitting issue of neural networks in input space. We then derive the connection between network robustness and decision surface geometry as an indicator of the neural network’s adversarial robustness. Guided by the indicator, we propose a practical robust training method, which involves no adversarial example generation. Extensive visualization results and experiments verify our theory and demonstrate the effectiveness of our proposed robustness enhancement method.

heading: 8 APPENDIX

heading: 8.1 THE EXPLANATION OF INEFFECTIVENESS OF LOSS SURFACE WITH BLANKS

text: In Sec. 3, we mentioned that loss surfaces often demonstrate large regions of blanks. The reason is that the exponential and log operation involved in the cross entropy calculation. In this section, we give a simple case to show the ineffectiveness and demonstrate how blank regions produce. Consider a 10-class neural network and one input image of label 0. Suppose we have ten different logit output as [0, 1, · · · , 1], [1, 1, · · · , 1] · · · [9, 1, · · · , 1] with confidence score ranged from -1 to 8. The corresponding cross entropy loss for ten different predictions are [3.23, 2.30, 1.46, 0.79, 0.37, 0.15, 0.05, 0.02, 0.01, 0.01]. We could see that in low confidence cases, cross entropy loss demonstrate informative trends with the increase of confidence. But when neural network prediction confidence reaches or above 5, the loss hardly changes, which causes certain large blank regions when visualizing the loss surfaces, which is consistent with Fig. 11.

heading: 8.2 DECISION SURFACE VISUALIZATION WITH MORE INPUT POINTS

heading: 8.2.1 COMPARISONS OF LOSS SURFACE AND DECISION SURFACE WITH MNIST INPUT IMAGES

text: 8.2.2 COMPARISONS OF ROBUST AND NATURAL MODELS WITH CIFAR INPUT IMAGES

heading: 8.3 EXPERIMENT SETTINGS

text: In the evaluation on MNIST dataset, a four-layer neural network model with two convolutional layers and two fully connected layers is adopted. After natural training, the baseline model achieves 99.17% accuracy. And for CIFAR10, we use a regular ConvNet with five convolutional layers and one global average pooling layer. For iterative methods BIM and C&W attack, we use 10 iterations and step size = 0.1 on MNIST and 1 on CIFAR. In adversarial training method, we use C&W attack to generate adversarial examples: For MNIST, we use 10 iterations, step size = 0.1, `∞ = 0.3 on pixel range 0 ∼ 1. For CIFAR10, we use 10 iterations, step size = 1, `∞ = 8 on pixel range 0 ∼ 255. The gradient regularization coefficient c (in Eq. 12) is set to 500 for gradient regularization.

heading: 8.4 INTERPRETABILITY OF JACOBIAN OF OUR ROBUST MODELS

heading: 8.5 MORE PARAMETER SPACE EXAMPLES OF NATURAL VS. ROBUST MODELS

text:
In this section, we provide more parameter space loss surface examples of natural and robust models (Madry et al. (2018)). Specifically, there are four possible combinations of parameter space settings: 1. natural model surface on natural input; 2. natural model surface on adversarial input; 3. robust model surface on natural input; 4. robust model surface on adversarial input. Here we show more examples of parameter space in the above four situations. Here natural input is one random batch (10 images from CIFAR10 test set), and adversarial input are FGSM (Kurakin et al. (2016)), Least-Likely attack (Kurakin et al. (2016)), and C&W (Carlini & Wagner (2017)) adversarial examples with eps=3 (Least-Likely and C&W use 10 iterations with step=1). All parameter space cross-entropy loss visualization results are shown in Fig. 16.
As expected, in parameter space, natural model’s loss surface on adversarial inputs has a larger base height than the robust model, i.e. the average loss values are much higher than robust models. But the gap is only obvious on weak attacks, like FGSM, as shown in Fig. 16 (b). When we use strong attacks like C&W in Fig. 16 (d), the loss surfaces of the natural model and robust model become similar again: Both models’ surfaces demonstrate high cross-entropy loss.
Therefore, we can use the loss surface in weight space to show their robustness difference if they are both plotted with weak adversarial inputs. But when we are facing stronger iterative attacks, the loss surface in weight space can no longer show any difference, thus cannot indicate the model robustness. By contrast, our input space loss surfaces can explicitly show the model robustness difference with no such restrictions, and the robustness difference can also be more obviously demonstrated, as shown in main paper Fig.3. And thus we believe these are the advantages of using input space loss surface to indicate the model robustness.

heading: 8.6 ADDITIONAL MNIST AND CIFAR10 EXPERIMENTAL RESULTS

text: Due to space limit, we add the left MNIST and CIFAR10 experimental results in Table. 3 and Table. 4 here.