summaries: The paper presents a method for learning agents to solve visual planning, in particular to navigate to a desired goal position in a maze, with a learned topological map, i.e. a graph, where nodes correspond to positions in the maze and edges correspond accessibility (reachability in a certain number of steps). The work extends previous work (semi parametric topological memory, ref. [22]) in several ways. It claims to address a shortcoming of [22], namely the fact that the graph is calculated offline from random rollouts, by using a conditional variational auto-encoder to predict a set of observed images which could lie between the current position and the goal position, and, most importantly from a context image which describes the layout of the environment. These predicted images are then arranged in a graph through a connectivity predictor, which is trained from rollouts through a contrastive loss. Training is performed on multiple environments, and the context vector provides enough information for this connectivity network to generalize to unseen environments.  At test time, the agent navigates using a planner and a policy. The planner calculates the shortest path on a graph where edges are connectivity probabilities, and the policy is an inverse model trained on the output of the planner.

summaries: The paper propose a novel visual planning approach which constructs explicit plans from "hallucinated" states of the environment. To hallucinate states, it uses a Conditional Variational Autoencoder (which is conditioned on a context image of the domain). To plan, it trains a Contrastive Predictive Coding (CPC) model for judging similarities between states, then applies this model to hallucinated states + start/end states, then runs Dijkstra on the edges weighted by similarities.

summaries: The paper presents HTM, an extension of the semiparametric topological memory method that augments the approach with hallucinated nodes and an energy cost function. The hallucination is enabled by a CVAE, conditioned on an image of the environment, and allows the method to generalize to unseen environments. The energy cost function is trained as a contrastive loss and acts as a robustness score for connecting the two samples. The underlying graph is then used to plan for several top view planning problems.

abstractText: In visual planning (VP), an agent learns to plan goal-directed behavior from observations of a dynamical system obtained offline, e.g., images obtained from selfsupervised robot interaction. VP algorithms essentially combine data-driven perception and planning, and are important for robotic manipulation and navigation domains, among others. A recent and promising approach to VP is the semiparametric topological memory (SPTM) method, where image samples are treated as nodes in a graph, and the connectivity in the graph is learned using deep image classification. Thus, the learned graph represents the topological connectivity of the data, and planning can be performed using conventional graph search methods. However, training SPTM necessitates a suitable loss function for the connectivity classifier, which requires non-trivial manual tuning. More importantly, SPTM is constricted in its ability to generalize to changes in the domain, as its graph is constructed from direct observations and thus requires collecting new samples for planning. In this paper, we propose Hallucinative Topological Memory (HTM), which overcomes these shortcomings. In HTM, instead of training a discriminative classifier we train an energy function using contrastive predictive coding. In addition, we learn a conditional VAE model that generates samples given a context image of the domain, and use these hallucinated samples for building the connectivity graph, allowing for zero-shot generalization to domain changes. In simulated domains, HTM outperforms conventional SPTM and visual foresight methods in terms of both plan quality and success in long-horizon planning.

authors:
Pulkit Agrawal
Ashvin V Nair
Pieter Abbeel
Jitendra Malik
Sergey Levine

title: Learning to poke by poking: Experiential learning of intuitive physics

venue: In Advances in Neural Information Processing Systems,

title: Unsupervised grounding of plannable first-order logic representation from images

venue: arXiv preprint arXiv:1902.08093,

authors:
Masataro Asai
Alex Fukunaga

title: Classical planning in deep latent space: Bridging the subsymbolic-symbolic boundary

venue: In Thirty-Second AAAI Conference on Artificial Intelligence,

authors:
Frederik Ebert
Chelsea Finn
Sudeep Dasari
Annie Xie
Alex Lee
Sergey Levine

title: Visual foresight: Model-based deep reinforcement learning for vision-based robotic control

venue: arXiv preprint arXiv:1812.00568,

authors:
Benjamin Eysenbach
Ruslan Salakhutdinov
Sergey Levine

title: Search on the replay buffer: Bridging planning and reinforcement learning

venue: arXiv preprint arXiv:1906.05253,

authors:
Chelsea Finn
Sergey Levine

title: Deep visual foresight for planning robot motion

venue: In Robotics and Automation (ICRA),

authors:
Tuomas Haarnoja
Aurick Zhou
Kristian Hartikainen
George Tucker
Sehoon Ha
Jie Tan
Vikash Kumar
Henry Zhu
Abhishek Gupta
Pieter Abbeel

title: Soft actor-critic algorithms and applications

venue: arXiv preprint arXiv:1812.05905,

authors:
Brian Ichter
Marco Pavone

title: Robot motion planning in learned latent spaces

venue: IEEE Robotics and Automation Letters,

authors:
Leslie Pack Kaelbling
Tomás Lozano-Pérez

title: Hierarchical planning in the now

venue: In Workshops at the Twenty-Fourth AAAI Conference on Artificial Intelligence,

title: Integrated task and motion planning in belief space

venue: The International Journal of Robotics Research,

authors:
Lukasz Kaiser
Mohammad Babaeizadeh
Piotr Milos
Blazej Osinski
Roy H Campbell
Konrad Czechowski
Dumitru Erhan
Chelsea Finn
Piotr Kozakowski
Sergey Levine

title: Modelbased reinforcement learning for atari

authors:
Diederik P Kingma
Max Welling

title: Auto-encoding variational bayes

venue: arXiv preprint arXiv:1312.6114,

authors:
Thanard Kurutach
Aviv Tamar
Ge Yang
Stuart J Russell
Pieter Abbeel

title: Learning plannable representations with causal infogan

authors:
Alex X Lee
Richard Zhang
Frederik Ebert
Pieter Abbeel
Chelsea Finn
Sergey Levine

title: Stochastic adversarial video prediction

venue: arXiv preprint arXiv:1804.01523,

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Andrei A Rusu
Joel Veness
Marc G Bellemare
Alex Graves
Martin Riedmiller
Andreas K Fidjeland
Georg Ostrovski

title: Human-level control through deep reinforcement learning

authors:
Ashvin Nair
Dian Chen
Pulkit Agrawal
Phillip Isola
Pieter Abbeel
Jitendra Malik
Sergey Levine

title: Combining self-supervised learning and imitation for vision-based rope manipulation

authors:
Aaron van den Oord
Yazhe Li
Oriol Vinyals

title: Representation learning with contrastive predictive coding

venue: arXiv preprint arXiv:1807.03748,

authors:
Lerrel Pinto
Abhinav Gupta

title: Supersizing self-supervision: Learning to grasp from 50k tries and 700 robot hours

venue: In 2016 IEEE international conference on robotics and automation (ICRA),

authors:
Ahmed H Qureshi
Anthony Simeonov
Mayur J Bency
Michael C Yip

title: Motion planning networks

venue: In 2019 International Conference on Robotics and Automation (ICRA),

authors:
Stuart J. Russell
Peter Norvig

title: Artificial Intelligence - A Modern Approach (3

venue: internat. ed.). Pearson Education,

authors:
Tim Salimans
Ian Goodfellow
Wojciech Zaremba
Vicki Cheung
Alec Radford
Xi Chen

title: Improved techniques for training gans

venue: In Advances in neural information processing systems,

authors:
Nikolay Savinov
Alexey Dosovitskiy
Vladlen Koltun

title: Semi-parametric topological memory for navigation

venue: arXiv preprint arXiv:1803.00653,

authors:
John Schulman
Sergey Levine
Pieter Abbeel
Michael Jordan
Philipp Moritz

title: Trust region policy optimization

venue: In International Conference on Machine Learning,

authors:
David Silver
Aja Huang
Chris J Maddison
Arthur Guez
Laurent Sifre
George Van Den Driessche
Julian Schrittwieser
Ioannis Antonoglou
Veda Panneershelvam
Marc Lanctot

title: Mastering the game of go with deep neural networks and tree

venue: search. nature,

authors:
Kihyuk Sohn
Honglak Lee
Xinchen Yan

title: Learning structured output representation using deep conditional generative models

authors:
Aravind Srinivas
Allan Jabri
Pieter Abbeel
Sergey Levine
Chelsea Finn

title: Universal planning networks

venue: arXiv preprint arXiv:1804.00645,

authors:
Siddharth Srivastava
Eugene Fang
Lorenzo Riano
Rohan Chitnis
Stuart Russell
Pieter Abbeel

title: Combined task and motion planning through an extensible planner-independent interface layer

authors:
Emanuel Todorov
Tom Erez
Yuval Tassa

title: Mujoco: A physics engine for model-based control

venue: In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems,

authors:
Angelina Wang
Thanard Kurutach
Kara Liu
Pieter Abbeel
Aviv Tamar

title: Learning robotic manipulation through visual planning and acting

heading: 1 INTRODUCTION

text:
For robots to operate in unstructured environments such as homes and hospitals, they need to manipulate objects and solve complex tasks as they perceive the physical world. While task planning and object manipulation have been studied in the classical AI paradigm [20, 9, 30, 10], most successes have relied on a human-designed state representation and perception, which can be challenging to obtain in unstructured domains. While high-dimensional sensory input such as images can be easy to acquire, planning using raw percepts is challenging. This has motivated the investigation of datadriven approaches for robotic manipulation. For example, deep reinforcement learning (RL) has made impressive progress in handling high-dimensional sensory inputs and solving complex tasks in recent years [7, 4, 15, 23].
One of the main challenges in deploying deep RL methods in human-centric environment is interpretability. For example, before executing a potentially dangerous task, it would be desirable to visualize what the robot is planning to do step by step, and intervene if necessary. Addressing both data-driven modeling and interpretability, the visual planning (VP) paradigm seeks to learn a model of the environment from raw perception and then produce a visual plan of solving a task before actually executing a robot action. Recently, several studies in manipulation and navigation [13, 29, 5, 22] have investigated VP approaches that first learn what is possible to do in a particular environment by self-supervised interaction, and then use the learned model to generate a visual plan from the current state to the goal, and finally apply visual servoing to follow the plan.
One particularly promising approach to VP is the semi-parametric topological memory (SPTM) method proposed by Savinov et al. [22]. In SPTM, images collected offline are treated as nodes in a graph and represent the possible states of the system. To connect nodes in this graph, an image classifier is trained to predict whether pairs of images were ‘close’ in the data or not, effectively
learning which image transitions are feasible in a small number of steps. The SPTM graph can then be used to generate a visual plan – a sequence of images between a pair of start and goal images – by directly searching the graph. SPTM has several advantages, such as producing highly interpretable visual plans and the ability to plan long-horizon behavior.
However, since SPTM builds the visual plan directly from images in the data, when the environment changes – for example, the lighting varies, the camera is slightly moved, or other objects are displaced – SPTM requires recollecting images in the new environment; in this sense, SPTM does not generalize in a zero-shot sense. Additionally, similar to [5], we find that training the graph connectivity classifier as originally proposed by [22] requires extensive manual tuning.
In this work, we propose to improve both the robustness and zero-shot generalization of SPTM. To tackle the issue of generalization, we assume that the environment is described using some context vector, which can be an image of the domain or any other observation data that contains enough information to extract a plan (see Figure 1 top left). We then train a conditional generative model that hallucinates possible states of the domain conditioned on the context vector. Thus, given an unseen context, the generative model hallucinates exploration data without requiring actual exploration. When building the connectivity graph with these hallucinated images, we replace the vanilla classifier used in SPTM with an energy-based model that employs a contrastive loss. We show that this alteration drastically improves planning robustness and quality. Finally, for planning, instead of connecting nodes in the graph according to an arbitrary threshold of the connectivity classifier, as in SPTM, we cast the planning as an inference problem, and efficiently search for the shortest path in a graph with weights proportional to the inverse of a proximity score from our energy model. Empirically, we demonstrate that this provides much smoother plans and barely requires any hyperparameter tuning. We term our approach Hallucinative Topological Memory (HTM). A visual overview of our algorithm is presented in Figure 1.
We evaluate our method on a set of simulated VP problems of moving an object between obstacles, which require long-horizon planning. In contrast with prior work, which only focused on the success of the method in executing a task, here we also measure the interpretability of visual planning, through mean opinion scores of features such as image fidelity and feasibility of the image sequence.
In both measures, HTM outperforms state-of-the-art data-driven approaches such as visual foresight [4] and the original SPTM.

heading: 2 BACKGROUND

text:
Context-Conditional Visual Planning and Acting (VPA) Problem. We consider the contextconditional visual planning problem from [13, 29]. Consider deterministic and fully-observable environments E1, ..., EN that are sampled from an environment distribution PE . Each environment Ei can be described by a context vector ci that entirely defines the dynamics oit+1 = m(o i t, a i t|ci), where oit, a i t are the observations and actions, respectively, at timestep t from context ci. For example, in the illustration in Figure 1, the context could represent an image of the obstacle positions, which is enough to predict the possible movement of objects in the domain.1 As is typical in VP problems, we assume our data D = {oi1, ai1, ..., oiTi , ci}i∈{1,...,N} is collected in a self-supervised manner, and that in each environment Ei, the observation distribution is defined as Po(·|ci). At test time, we are presented with a new environment, its corresponding context vector c, and a pair of start and goal observations ostart, ogoal. Our goal is to use the training data to build a planner Qh(ostart, ogoal, c) and an h-horizon policy πh. The planner’s task is to generate a sequence of observations between ostart and ogoal, in which any two consecutive observations are reachable within h time steps. The policy takes as input the image sequence and outputs a control policy that transitions the system from ostart to ogoal. As the problem requires a full plan given only a context image in the new environment, the planner must be capable of zero-shot generalization. Note that the planner and policy form an interpretable planning method that allows us to evaluate their performance separately. For simplicity we will omit the subscript h for the planner and the policy.
Semi-Parametric Topological Memory (SPTM) [22] is a visual planning method that can be used to solve a special case of VPA. where there is only a single training environment, E and no context image. SPTM builds a memory-based planner and an inverse-model controller. At training, a classifier R is trained to map two observation images oi, oj to a score ∈ [0, 1] representing the feasibility of the transition, where images that are ≤ h steps apart are labeled positive and images that are ≥ l are negative. The policy is trained as an inverse model L, mapping a pair of observation images oi, oj to an appropriate action a that transitions the system from oi to oj .
Given an unseen environment E∗, new observations are manually collected and organized as nodes in a graph G. Edges in the graph connect observations oi, oj if R(oi, oj) ≥ sshortcut, where sshortcut is a manually defined threshold. To plan, given start and goal observations ostart and ogoal, SPTM first usesR to localize, i.e., find the closest nodes inG to ostart and ogoal. A path is found by running Dijkstra’s algorithm, and the method then selects a waypoint owi on the path which represents the farthest observation that is still feasible under R. Since both the current localized state oi and its waypoint owi are in the observation space, we can directly apply the inverse model and take the action ai where ai = L(oi, owi). After localizing to the new observation state reached by ai, SPTM repeats the process until the node closest to ogoal is reached.
Conditional Variational Auto-Encoder (CVAE) [25] is a deep generative model that can be used for learning a high-dimensional conditional distribution Po(·|c). The CVAE is trained by maximizing the evidence lower bound (ELBO): LCV AE = −DKL (qθ(z|o, c)|rψ(z|c)) + Eqφ(z|o,c) [log pθ(o|z, c)] , where qθ(z|o, c) is the encoder that maps observations and contexts to the latent distribution, pθ(o|z, c) is the decoder that maps latents and contexts to the observation distribution, and rψ(z|c) is the prior that maps contexts to latent prior distributions. Together pθ, qφ, rψ are trained to maximize the variational lower bound above. We assume that the prior and the encoder are Gaussian, which allows the DKL term to be computed in closed-form. Monte-Carlo sampling and the reparametrization trick [12] are used to approximate the gradient of the loss.
Contrastive Predictive Coding (CPC) [17] extracts compact representations that maximize the causal and predictive aspects of high-dimensional sequential data. A non-linear encoder genc encodes the observation ot to a latent representation zt = genc(ot). We maximize the mutual information between the latent representation zt and future observation ot+k with a log-
1We used such a context image in our experiments. We assume that in a practical application, observing the domain without the robot would be feasible, making this setting relevant to applications.
bilinear model2 fk(ot+k, ot) = exp(zTt+kWkzt). This model is trained to be proportional to the density ratio p(ot+k|zt)/p(ot+k) by the CPC loss function: the cross entropy loss of correctly classifying a positive sample from a set X = {o1, ..., oN} of N random samples with 1 positive sample from p(ot+k|zt) and N − 1 negative samples sampled from p(ot+k): LCPC =
−Eot,ot+k [ log fk(ot+k,ot)∑
oj∈X fk(oj ,ot)
] .

heading: 3 HALLUCINATIVE TOPOLOGICAL MEMORY

text:
SPTM has been shown to solve long-horizon planning problems such as navigation from first-person view [22]. However, SPTM is not zero-shot: even a small change to the training environment requires collecting substantial exploration data for building the planning graph. This can be a limitation in practice, especially in robotic domains, as any interaction with the environment requires robot time, and exploring a new environment can be challenging (indeed, [22] applied manual exploration). In addition, similarly to [5], we found that training the connectivity classifier as proposed in [22] requires extensive hyperparameter tuning.
In this section, we propose an extension of SPTM to overcome these two challenges by employing three ideas – (1) using a CVAE [25] to hallucinate samples in a zero-shot setting, (2) using contrastive loss for a more robust score function and planner, and (3) planning based on an approximate maximum likelihood formulation of the shortest path under uniform state distribution. We call this approach Hallucinative Topological Memory (HTM), and next detail each component in our method.

heading: 3.1 HALLUCINATING SAMPLES WITH CVAE

text: We propose a zero-shot learning solution for automatically building the planning graph using only a context vector of the new environment. Our idea is that, after seeing many different environments and corresponding states of the system during training, given a new environment we should be able to effectively hallucinate possible system states. We can then use these hallucinations in lieu of real samples from the system in order to build the planning graph. To generate images conditioned on a context, we implement a CVAE as depicted in Figure 1. During training, we learn the prior latent distribution rψ(z|c), modeled as a Gaussian with mean µ(c) and covariance matrix Σ(c), where µ(·) and Σ(·) are learned non-linear neural network transformations. During testing, when prompted with a new context vector c, we can sample latent vectors z1, ..., zN | c ∼ N (µ(c),Σ(c)), and pass them through the decoder pθ(x|z, c) for hallucinating samples in replacement of exploration data.

heading: 3.2 LEARNING THE CONNECTIVITY VIA CONTRASTIVE LOSS

text:
A critical component in the SPTM method is the connectivity classifier that decides which image transitions are feasible. False positives may result in impossible short-cuts in the graph, while false negatives can make the plan unnecessarily long. In [22], the classifier was trained discriminatively, using observations in the data that were reached within h steps as positive examples, and more than l steps as negative examples, where h and l are chosen arbitrarily. In practice, this leads to three important problems. First, this method is known to be sensitive to the choice of positive and negative labeling [5]. Second, training data are required to be long, non-cyclic trajectories for a high likelihood of sampling ‘true’ negative samples. However, self-supervised interaction data often resembles random walks that repeatedly visit a similar state, leading to inconsistent estimates on what constitutes negative data. Third, since the classifier is only trained to predict positively for temporally nearby images and negatively for temporally far away images, its predictions of medium-distance images can be arbitrary. This creates both false positives and false negatives, thereby increasing shortcuts and missing edges in the graph.
To solve these problems, we propose to learn a connectivity score using contrastive predictive loss [17]. Similar to CVAE, we initialize a CPC encoder genc that takes in both observation and context, and a density-ratio model fk that does not depend on the context. Through optimizing the CPC objective, fk of positive pairs are encouraged to be distinguishable from that of negative pairs. Thus, it serves as a proxy for the temporal distance between two observations, leading to a connectivity score for planning. Theoretically, CPC loss is better motivated than the classification loss in SPTM
2The original CPC model has an additional autoregressive memory variable [17]. We drop it in our formulation as our domains are fully observable and do not require memory.
as it structures the latent space on a clear objective: maximize the mutual information between current and future observations. In practice, this results in less hyperparameter tuning and a smoother distance manifold in the representation space. Finally, instead of only sampling from the same trajectory as done in SPTM, our negative data are collected by sampling from the latent space of a trained CVAE or the replay buffer. Without this trick, we found that the SPTM classifier fails to handle self-supervised data.

heading: 3.3 PLANNING AS INFERENCE

text:
Planning Algorithm. Given a start observation ostart, a goal observation ogoal sampled from a potentially new environment E∗, and the context vector c, we propose a 4-step planning algorithm. First, we hallucinate exploration data by sampling from the latent space Po(·|c) of the CVAE. Second, we build a fully-connected weighted graph G(V,E) by forming connections between all i generated image samples ôi = pθ(·|zi, c), where pθ is the trained CVAE decoder and zi is the vector sampled from the CVAE prior. We choose our edge weight between nodes i and j as one of two choices: (1) an energy model, i.e., the inverse of fk(i, j), or (2) a density ratio, i.e., the inverse of normalized fk between two nodes, ie. fk(i, j)/ ∑ l(fk(i, l)). This score reflects the difficulty in transitioning to the next state from the current state by self-supervised exploration. The learned connectivity graph G can be viewed as a topological memory upon which we can use conventional graph planning methods to efficiently perform visual planning. In the third step, we find the shortest path using Dijkstra’s algorithm on the learned connectivity graph G between the start and end node. In the fourth step, we apply our policy to follow the visual plan, reaching the next node in our shortest path and replan every fixed number of steps until we reach ôgoal. For the policy, we train an inverse model which predicts actions given two observations that are within h steps apart.
Maximum likelihood trajectory with Dijkstra’s. We show that the CPC loss can be utilized to cast the planning problem as an inference problem, and results in an effective planning algorithm. After training the CPC objective to convergence, we have fk(ot+k, ot) ∝ p(ot+k|ot)/p(ot+k) [17]. To estimate p(ot+k|ot)/p(ot+k), we compute the normalizing factor ∑ o′∈V [fk(o
′, ot)] for each ot by averaging over all nodes in the graph. Let’s define our non-negative weight from ot to ot+k as ω(ot+k, ot) = ∑ o′∈V [fk(o ′, ot)]/fk(ot+k, ot) ≈ p(ot+k)/p(ot+k|ot).
A shortest-path planning algorithm finds T, o0, ..., oT that minimizes ∑T−1 t=0 ω(ot, ot+1) such that o0 = ostart, oT = ogoal. By Jensen’s inequality and the Markovian property of o0, ..., oT we have that, log 1T ∑T−1 t=0 ω(ot, ot+1) ≥ 1 T ∑T−1 t=0 logω(ot, ot+1) = 1 T ∑T−1 t=0 (log p(ot+1) −
log p(ot+1|ot)) = 1T ∑T−1 t=1 p(ot) − log p(o1, ..., oT−1|o0 = ostart, oT = ogoal), Thus, assuming that the self-supervised data distribution is approximately uniform, the shortest path algorithm with proposed weight ω maximizes a lower bound on the trajectory likelihood given the start and goal states. In practice, this leads to a more stable planning approach and yields more feasible plans.

heading: 4 RELATED WORK

text:
Reinforcement Learning. Most of the study of data-driven planning has been under the model-free RL framework [23, 15, 24]. However, the need to design a reward function, and the fact that the learned policy does not generalize to tasks that are not defined by the specific reward, has motivated the study of model-based approaches. Recently, [11, 8] investigated model-based RL from pixels on Mujoco and Atari domains, but did not study generalization to a new environment. [6, 4] explored model-based RL with image-based goals using visual model predictive control (visual MPC). These methods rely on video prediction, and are limited in the planning horizon due to accumulating errors. In comparison, our method does not predict full trajectories but only individual images, mitigating this problem. Our method can also use visual MPC as a replacement for the visual servoing policy.
Self-supervised learning. Several studies investigated planning goal directed behavior from data obtained offline, e.g., by self-supervised robot interaction [1, 18]. Nair et al. [16] used an inverse model to reach local sub-goals, but require human demonstrations of long-horizon plans. Wang et al. [29] solve the visual planning problem using a conditional version of Causal InfoGAN [13]. However, as training GAN is unstable and requires tedious model selection [21], we opted for the CVAE-based approach, which is much more robust.
Classical planning and representation learning. In classical planning literature, task and motion planning also separates the high-level planning and the low-level controller [30, 27, 10]. In these works, domain knowledge is required to specify preconditions and effects at the task level. Our approach only requires data collected through self-supervised interaction.
Other studies that bridge between classical planning and representation learning include [13, 3, 2, 5]. These works, however, do not consider zero-shot generalization. While Srinivas et al. [26] and Qureshi et al. [19] learn representations that allow goal-directed planning to unseen environments, they require expert training trajectories. Ichter and Pavone [8] also generalizes motion planning to new environments, but require a collision checker and valid samples from test environments.

heading: 5 EXPERIMENTS

text:
Recent work in visual planning (e.g., [13, 29, 4]) focused on real robotic tasks with visual input. While impressive, such results can be difficult to reproduce or compare. For example, it is not clear whether manipulating a rope with the PR2 robot [29] is more or less difficult than manipulating a rigid object among many visual distractors [4]. In light of this difficulty, we propose a suite of simulated tasks with an explicit difficulty scale and clear evaluation metrics. Our domains consider moving a rigid object between obstacles using Mujoco [28], and by varying the obstacle positions, we can control the planning difficulty. For example, placing the object in a cul-de-sac would require non-trivial planning compared to simply moving around an obstacle along the way to the goal. We thus create two domains, as seen in Figure 2:
1. Block wall:: A green block navigates around a static red obstacle, which can vary in position. 2. Block wall with complex obstacle: Similar to the above, but here the wall is a 3-link object
which can vary in position, joint angles, and length, making the task significantly harder.
With these domains, we aim to asses the following attributes:
• Does HTM improve visual plan quality over state-of-the-art VP methods [22, 4]? • How does HTM execution success rate compare to state-of-the-art VP methods? • How well does HTM generalize its planning to unseen contexts?
We discuss our evaluation metrics for these attributes in Section 5.1. To fully assess success of HTM relative to other state-of-the-art VP methods, we run these evaluation metrics on SPTM [22] and Visual Foresight [4]. In the first baseline, since vanilla SPTM cannot plan in a new environment, we use the same samples generated by the same CVAE as HTM, and then build the graph by assigning edge weights in the graph proportional to their exponentiated SPTM classifier score. 3 We also give it the same negative sampling proceedure as HTM. The same low-level controller is also used to follow the plans. In the second baseline, Visual Foresight trains a video prediction model, and then performs model predictive control (MPC) which finds the optimal action sequence through random shooting. For the random shooting, we used 3 iterations of the cross-entropy method with 200 sample sequences. The MPC acts for 10 steps and replans, where the planning horizon T is 15. We use the state-of-the-art video predictor as proposed by Lee et al. [14] and the public code provided by the authors. For evaluating trajectories in random shooting, we studied two cost functions that are suitable for our domains: pixel MSE loss and green pixel distance. The pixel MSE loss computes the
3We found that negative exponential weighting, which requires no tuning, performed slightly better in results than our best tuned version of the original SPTM edge weighting through thresholding.
pixel distance between the predicted observations and the goal image. This provides a sparse signal when the object pixels in the plan can overlap with those of the goal. We also investigate a cost function that uses prior knowledge about the task – the position of the moving green block, which is approximated by calculating the center of mass of the green pixels. As opposed to pixel MSE, the green pixel distance provides a smooth cost function which estimates the normalized distance between the estimated block positions of the predicted observations and the goal image. Note that this assumes additional domain knowledge compared to HTM.

heading: 5.1 EVALUATION METRICS

text:
We design a set of tests that measure both qualitative and quantitative performance of an algorithm. To motivate the need for qualitative metrics, we reiterate the importance of planning interpretability; it is highly desirable that the generated plan visually make sense so as to allow a human to approve of the plan prior to execution.
Qualitative Visual plans have the essential property of being intuitive, in that the imagined trajectory is perceptually sensible. Since these qualities are highly subjective, we devised a set of tests to evaluate plans based on human visual perception. For each domain, we asked 5 participants to visually score 5 randomly generated plans from each model by answering the following questions: (1) Fidelity: Does the pixel quality of the images resemble the training data?; (2) Feasibility: Is each transition in the generated plan executable by a single action step?; and (3) Completeness: Is the goal reachable from the last image in the plan using a single action? Answers were in the range [0,1], where 0 denotes No to the proposed question and 1 means Yes. The mean opinion score were calculated for each model.
Quantitative In addition to generating visually sensible trajectories, a planning algorithm must also be able to successfully navigate towards a predefined goal. Thus, for each domain, we selected 20 start and goal images, each with an obstacle configuration unseen during training. Success was measured by the ability to get within some L2 distance to the goal in a n steps or less, where the distance threshold and n varied on the domain but was held constant across all models. A controller specified by the algorithm executed actions given an imagined trajectory, and replanning occurred every r steps. Specific details can be found in the Appendix D.

heading: 5.2 RESULTS

text:
As shown in Table 5.2, HTM outperforms all baselines in both qualitative and quantitative measurements across all domains. In the simpler block wall domain, Visual Foresight with green pixel distance only succeeds under the assumption of additional state information of the object’s location. the other algorithms do not have. However, in the complex obstacle domain, Visual Foresight fails to perform comparably to our algorithm, regardless of the additional assumption. We also compared our method with SPTM, using the same inverse model and CVAE to imagine testing samples. However, without a robust classification loss and improved method of weighting the graph’s edges, SPTM often fails to find meaningful transitions.
In regards to perceptual evaluation, Visual Foresight generates realistic transitions, as seen by the high participant scores for feasibility. However, the algorithm is limited in creating a visual plan within the optimal T = 15 timesteps. 4 Thus, when confronted with a challenging task of navigating around a convex shape where the number of timesteps required exceeds T , Visual Foresight fails to construct a reliable plan (see Figure 3), and thus lacks plan completeness. Conversely, SPTM is able to imagine some trajectory that will reach the goal state. However, as mentioned above and was confirmed in the perceptual scores, SPTM fails to select feasible transitions, such as imagining a trajectory where the block will jump across the wall or split into two blocks. Our approach, on the other hand, received the highest scores of fidelity, feasibility, and completeness. Finally, we show in Figure 3 the results of our two proposed improvements to SPTM in isolation. The results clearly show that a classifier using contrastive loss outperforms that which uses Binary Cross Entropy (BCE) loss, and furthermore that the inverse of the score function for edge weighting is more successful than the best tuned version of binary edge weights.
4For plans require > T steps, we found that error across the image translations accumulate and the predicted image drastically decreases in interpretability. This optimal value of T is consistent with that of [4].

heading: 6 DISCUSSION

text: We propose a method that is visually interpretable and modular – we first hallucinate possible configurations, then compute a connectivity between them, and then plan. Our HTM can generalize to unseen environments and improve visual plan quality and execution success rate over state-of-the-art VP methods. Our results suggest that combining classical planning methods with data-driven perception can be helpful for long-horizon visual planning problems, and takes another step in bridging the gap between learning and planning. In future work, we plan to combine HTM with Visual MPC for handling more complex objects, and use object-oriented planning for handling multiple objects. Another interesting aspect is to improve planning by hallucinating samples conditioned on the start and goal configurations, which can help reduce the search space during planning.

heading: A DISCRIMINATIVE MODELS: CLASSIFIER VS. ENERGY MODEL

text:
In this section, we assume the dataset as described in VPA, D = {oi1, ..., oiTi} n i=1. There are two ways of learning a model to distinguish the positive from the negative transitions.
Classifier: As noted above, SPTM first trains a classifier which distinguishes between an image pair that is within h steps apart, and the images that are far apart using random sampling. The classifier is used to localize the current image and find possible next images for planning. In essence, the classifier contains the encoder gθ that embeds the observation x and the the score function f that takes the embedding of each image and output the logit for a sigmoid function. The binary cross entropy loss of the classifier can be written as follows:
LSPTM (θ, ψ;D) = − ∑
(zt,zt+k)∼D
[ log f(z, zt+k)
1 + f(zt, zt+k) + log
1
1 + f(zt, z − t )
]
= − ∑
(zt,zt+1)∼D
log
[ fψ(zt, zt+k)
1 + fψ(zt, zt+k) + fψ(zt, z − t ) + fψ(zt, zt+k) ∗ fψ(zt, z−t )
] ,
where z−t is a random sample from D. Energy model: Another form of discriminating the the positive transition out of negative transitions is through an energy model. Oord et al. [17] learn the embeddings of the current states that are predictive of the future states. Let g be an encoder of the input x and z = gθ(x) be the embedding. The loss function can be described as a cross entropy loss of predicting the correct sample from N + 1 samples which contain 1 positive sample and N negative samples:
LCPC(θ, ψ;D) = − ∑
(zt,zt+k)∼D
log
[ fψ(zt, zt+k)
fψ(zt, zt+k) + ∑N i=1 fψ(zt, z i− t )
] ,
where fψ(u, v) = exp (uTψv) and z1−t , ..., z N− t are the random samples from D.
Note that when the number of negative samples is 1 the loss function resembles the SPTM.

heading: B MUTUAL INFORMATION (MI)

text: This quantity measures how much knowing one variable reduces the uncertainty of the other variable. More precisely, the mutual information between two random variables X and Y can be described as I(X,Y ) = H(X)−H(X|Y ) = H(Y )−H(Y |X) = EX,Y [ pX,Y pXpY ] .

heading: C ADDITIONAL PROOF

text: Lemma C.1. For any random variable X,Y and a deterministic function g, I(X,Y ) ≥ I(X, g(Y )).5 Proof. I(X,Y ) = H(X) − H(X|Y ) = H(X) − H(X|Y, g(Y )) ≥ H(X) − H(X|g(Y )) = I(X, g(Y ))

heading: D ADDITIONAL RESULTS AND HYPERPARAMETERS

text: 5This is also known as the data processing inequality.


summaries: This paper proposes to learn a subset of a given dataset that acts as an adversary, that hurts the model performance when used as a training dataset. The central claim of the paper is that existing datasets on which models are trained are potentially biased, and are not reflective of real world scenarios. By discarding samples that add to this bias, the idea is to make the model perform better in the wild. The authors propose a method to do so, and then refine it so that the resulting solution is tractable. They implement the method on several datasets and show that by finding these adversarial samples, they indeed hurt model performance.

summaries: This paper hypothesizes that even though we are able to achieve very impressive performance on benchmark datasets as of now (e.g. image net), it might be due to the fact that benchmarks themselves have biases. They introduce an algorithm that selects more representative data points from the dataset that allow to get a better estimate of the performance in the wild. The algorithm ends up selecting more difficult/confusing instances.

summaries: the paper proposes an algorithm that adversarially filters out examples to reduce dataset-specific spurious bias. the key intuition is that the datasets are curated in a way that easy to obtain samples have higher probability to be admitted to the dataset. however, not all real world samples are easy to obtain. in other words, real world samples may follow a completely different distribution than curated samples with easy-to-obtain ones.

abstractText: Large-scale benchmark datasets have been among the major driving forces in AI, supporting training of models and measuring their progress. The key assumption is that these benchmarks are realistic approximations of the target tasks in the real world. However, while machine performance on these benchmarks advances rapidly — often surpassing human performance — it still struggles on the target tasks in the wild. This raises an important question: whether the surreal high performance on existing benchmarks are inflated due to spurious biases in them, and if so, how we can effectively revise these benchmarks to better simulate more realistic problem distributions in the real world. In this paper, we posit that while the real world problems consist of a great deal of long-tail problems, existing benchmarks are overly populated with a great deal of similar (thus non-tail) problems, which in turn, leads to a major overestimation of true AI performance. To address this challenge, we present a novel framework of Adversarial Filters to investigate model-based reduction of dataset biases. We discuss that the optimum bias reduction via AFOPTIMUM is intractable, thus propose AFLITE, an iterative greedy algorithm that adversarially filters out data points to identify a reduced dataset with more realistic problem distributions and considerably less spurious biases. AFLITE is lightweight and can in principle be applied to any task and dataset. We apply it to popular benchmarks that are practically solved — ImageNet and Natural Language Inference (SNLI, MNLI, QNLI) — and present filtered counterparts as new challenge datasets where the model performance drops considerably (e.g., from 84% to 24% for ImageNet and from 92% to 62% for SNLI), while human performance remains high. An extensive suite of analysis demonstrates that AFLITE effectively reduces measurable dataset biases in both the synthetic and real datasets. Finally, we introduce new measures of dataset biases based on K-nearest-neighbors to help guide future research on dataset developments and bias reduction.

authors:
Michael A Alcorn
Qi Li
Zhitao Gong
Chengfei Wang
Long Mai
Wei-Shinn Ku
Anh Nguyen

title: Strike (with) a pose: Neural networks are easily fooled by strange poses of familiar objects

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Matej Balog
Nilesh Tripuraneni
Zoubin Ghahramani
Adrian Weller

title: Lost relatives of the gumbel trick

venue: In ICML,

authors:
Samuel R. Bowman
Gabor Angeli
Christopher Potts
Christopher D. Manning

title: A large annotated corpus for learning natural language inference

venue: In EMNLP,

authors:
Qian Chen
Xiao-Dan Zhu
Zhen-Hua Ling
Si Wei
Hui Jiang
Diana Inkpen

title: Enhanced lstm for natural language inference

authors:
Ekin D Cubuk
Barret Zoph
Dandelion Mane
Vijay Vasudevan
Quoc V Le

title: Autoaugment: Learning augmentation strategies from data

authors:
Jacob Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova

title: BERT: Pre-training of deep bidirectional transformers for language understanding

venue: In NAACL-HLT,

authors:
Kevin Eykholt
Ivan Evtimov
Earlence Fernandes
Bo Li
Amir Rahmati
Chaowei Xiao
Atul Prakash
Tadayoshi Kohno
Dawn Xiaodong Song

title: Robust physical-world attacks on deep learning models

authors:
David F Fouhey
Wei-cheng Kuo
Alexei A Efros
Jitendra Malik

title: From lifestyle vlogs to everyday interactions

authors:
Robert Geirhos
Patricia Rubisch
Claudio Michaelis
Matthias Bethge
Felix A Wichmann
Wieland Brendel

title: Imagenet-trained cnns are biased towards texture; increasing shape bias improves accuracy and robustness

authors:
Mor Geva
Yoav Goldberg
Jonathan Berant

title: Are we modeling the task or the annotator? An investigation of annotator bias in natural language understanding

authors:
Max Glockner
Vered Shwartz
Yoav Goldberg

title: Breaking NLI systems with sentences that require simple lexical inferences. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), Melbourne, Australia, July 2018

venue: Association for Computational Linguistics. doi: 10.18653/v1/P18-2103. URL https: //www.aclweb.org/anthology/P18-2103

authors:
Yash Goyal
Tejas Khot
Douglas Summers-Stay
Dhruv Batra
Devi Parikh

title: Making the v in vqa matter: Elevating the role of image understanding in visual question answering

authors:
Emil Julius Gumbel
Julius Lieblein

title: Statistical theory of extreme values and some practical applications: A series of lectures, volume 33

venue: US Government Printing Office Washington,

authors:
Suchin Gururangan
Swabha Swayamdipta
Omer Levy
Roy Schwartz
Samuel Bowman
Noah A. Smith

title: Annotation artifacts in natural language inference data

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Eric Jang
Shixiang Gu
Ben Poole

title: Categorical reparameterization with gumbel-softmax

venue: In ICLR,

authors:
Robin Jia
Percy Liang

title: Adversarial examples for evaluating reading comprehension systems

authors:
Carolyn Kim
Ashish Sabharwal
Stefano Ermon

title: Exact sampling with integer linear programs and random perturbations

venue: In AAAI,

authors:
Wouter Kool
Herke van Hoof
Max Welling

title: Stochastic beams and where to find them: The gumbel-top-k trick for sampling sequences without replacement

authors:
Yi Ci Li
Nuno Vasconcelos

title: REPAIR: Removing representation bias by dataset resampling

authors:
Yingwei Li
Yi Li
Nuno Vasconcelos

title: RESOUND: Towards action recognition without representation bias

venue: In ECCV,

authors:
Nelson F. Liu
Roy Schwartz
Noah A. Smith

title: Inoculation by fine-tuning: A method for analyzing challenge datasets. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)

authors:
Yinhan Liu
Myle Ott
Naman Goyal
Jingfei Du
Mandar S. Joshi
Danqi Chen
Omer Levy
Mike Lewis
Luke S. Zettlemoyer
Veselin Stoyanov

title: RoBERTa: A robustly optimized BERT pretraining approach

authors:
Chris J. Maddison
Andriy Mnih
Yee Whye Teh

title: The concrete distribution: A continuous relaxation of discrete random variables

authors:
Tom McCoy
Ellie Pavlick
Tal Linzen

title: Right for the wrong reasons: Diagnosing syntactic heuristics in natural language inference

venue: In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics. Association for Computational Linguistics,

authors:
Aakanksha Naik
Abhilasha Ravichander
Norman Sadeh
Carolyn Rose
Graham Neubig

title: Stress test evaluation for natural language inference

venue: In Proceedings of the 27th International Conference on Computational Linguistics. Association for Computational Linguistics,

authors:
Yixin Nie
Adina Williams
Emily Dinan
Mohit Bansal
Jason Weston
Douwe Kiela

title: Adversarial NLI: A new benchmark for natural language understanding

authors:
Jeffrey Pennington
Richard Socher
Christopher D. Manning

title: Glove: Global vectors for word representation

authors:
Matthew E. Peters
Mark Neumann
Mohit Iyyer
Matt Gardner
Christopher Clark
Kenton Lee
Luke S. Zettlemoyer

title: Deep contextualized word representations

authors:
Adam Poliak
Jason Naradowsky
Aparajita Haldar
Rachel Rudinger
Benjamin Van Durme

title: Hypothesis only baselines in natural language inference

venue: In Proceedings of the Seventh Joint Conference on Lexical and Computational Semantics,

authors:
Pranav Rajpurkar
Jian Zhang
Konstantin Lopyrev
Percy Liang

title: Squad: 100, 000+ questions for machine comprehension of text

authors:
Keisuke Sakaguchi
Ronan Le Bras
Chandra Bhagavatula
Yejin Choi

title: Winogrande: An adversarial winograd schema challenge at scale

authors:
Mingxing Tan
Quoc Le

title: Efficientnet: Rethinking model scaling for convolutional neural networks

authors:
Antonio Torralba
Alexei A. Efros

title: Unbiased look at dataset bias

title: Performance impact caused by hidden bias of training data for recognizing textual entailment

venue: In Proceedings of the 11th Language Resources and Evaluation Conference,

title: Gumbel-max trick and weighted reservoir sampling, 2014

venue: Blog post

authors:
Alex Wang
Amanpreet Singh
Julian Michael
Felix Hill
Omer Levy
Samuel R. Bowman

title: Glue: A multi-task benchmark and analysis platform for natural language understanding

authors:
Adina Williams
Nikita Nangia
Samuel Bowman

title: A broad-coverage challenge corpus for sentence understanding through inference

authors:
Rowan Zellers
Yonatan Bisk
Roy Schwartz
Yejin Choi

title: SWAG: A large-scale adversarial dataset for grounded commonsense inference

authors:
Rowan Zellers
Ari Holtzman
Yonatan Bisk
Ali Farhadi
Yejin Choi

title: HellaSwag: Can a machine really finish your sentence

heading: 1 INTRODUCTION

text:
Large-scale neural networks have achieved superhuman performance across many popular AI benchmarks, for tasks as diverse as image recognition (ImageNet; Russakovsky et al. (2015)), natural language inference (SNLI; Bowman et al. (2015)), and question answering (SQuAD; Rajpurkar et al. (2016)). Yet these deep models struggle when taken out of these dataset environments and evaluated on adversarial data or problems in the wild (Eykholt et al., 2018; Jia & Liang, 2017). This raises a key question: Does high model performance on today’s benchmark datasets indicate the underlying task is solved, or do those datasets overestimate the true capabilities of current AI systems?
Answering this question is key because benchmarks serve important roles in the community. Not only do they direct progress on core tasks, they also make it easier to tackle the lofty target tasks such as image recognition in the wild through a more practically-scoped dataset such as ImageNet. However, the closed-world assumption of most existing datasets is subject to significant bias (Torralba & Efros, 2011). Much of the data that is easy to obtain and label isn’t necessarily representative of the task we seek to measure. Thus, if left unchecked, artifacts from data collection (Fouhey et al., 2018) or human labeling (Gururangan et al., 2018; Poliak et al., 2018; Tsuchiya, 2018; Geva et al., 2019) can significantly inflate model performance. Though there exist task- and dataset-specific ap-
proaches for addressing these biases (Goyal et al., 2017; Geirhos et al., 2018), the complex artifacts that emerge from large-scale dataset creation are challenging to exhaustively identify and remove.
In this paper, we present AFLITE – a computationally efficient dataset reduction algorithm, aimed at systematically reducing spurious artifacts in a dataset. AFLITE is general and can be applied to any task and dataset. Our approach leverages a high capacity model to learn dataset specific biases on a small subset, then uses it to identify and filter artifact-prone instances in the remainder of the dataset to yield a final dataset that is possibly closer to the intended task.
We first evaluate the effectiveness of our method on synthetic data and show that AFLITE lowers the performance of models relying on annotation artifacts while preserving the performance of models whose representation captures the underlying tasks. In addition, while AFLITE aims to retain the more challenging, confusing instances, our experiments show that it can successfully remove biased instances that are adversarial to the correct representation of the data.
Finally, we apply the method to several benchmark datasets across various tasks and domains. In language understanding, we apply AFLITE to the SNLI (Bowman et al., 2015) and MNLI (Williams et al., 2018) datasets for natural language inference, and to QNLI (Wang et al., 2018) for question answering. We show a 30% absolute gap in performance in the current state-of-art methods before and after AFLITE. In computer vision, AFLITE reduces the performance of image classification neural methods on ImageNet (Russakovsky et al., 2015), showing a 49% absolute gap.

heading: 2 DATASET REDUCTION FOR REPRESENTATION-BIAS MINIMIZATION

text:
In this section, we introduce AFLITE, a general approach for reducing the scope of bias in datasets. Large datasets run the risk of prioritizing performance on the data-rich head of the distribution, where examples are plentiful, and discounting the tail. Our goal is to minimize the ability of a model to exploit biases in the head of the distribution, while preserving the inherent complexity of the tail.
Let Φ represent a feature representation, defined over a datasetD = (X,Y ). With AFLITE, we seek a subset S ⊂ D of size |S| ≥ n that is maximally resilient to the features uncovered by Φ. For any identically-distributed train-test split of D, the features extracted by Φ should not generalize to the held-out set. Our approach allows for any choice of feature representation.
Formalization More formally, let M denote a family of classification models (e.g., logistic regression, SVM, or a particular neural architecture) that can be trained on subsets S of D = (X,Y )
using features Φ(X). We define the representation bias of Φ in S w.r.tM, denotedR(Φ, S,M), as the best possible out-of-sample classification accuracy achievable by models inM when predicting the true labels Y using features Φ(X). For a given target reduced dataset size of at least n, the goal is to find a subset S ⊂ D, |S| ≥ n that minimizes this representation bias in S w.r.t.M:
min S⊂D, |S|≥n
R(Φ, S,M) (1)
Eq. (1) corresponds to the optimum bias reduction, referred to as AFOPTIMUM. R(Φ, S,M) can be formulated as the expected classification accuracy resulting from the following process. Let q : 2S → [0, 1] be a probability distribution over subsets T = (XT , Y T ) of D. The process is to randomly choose a subset T with probability q(T ), train a bias estimator MT ∈ M on D \ T , and evaluate its classification accuracy fMT (Φ(X
T ), Y T ) on T . Note that the resulting classification accuracy on T itself is a random variable, since the training set D \ T is random. We define the expected value of this classification accuracy to be the representation bias:
R(Φ, S,M) , ET∼q [ fMT (Φ(X T ), Y T ) ]
(2)
While this expression formalizes the intended objective function, it involves a large summation over subsets T ⊂ S just to compute the representation bias present in a single set S. It does not suggest a practical way to compute the minimization in Eq. (1) without further considering each of the exponentially many subsets S ⊂ D individually – thus an optimal solution for Equation (2) is intractable. To get around this difficulty, we reformulate the representation bias in S as a sum factored over the |S| individual instances i ∈ S. This will allow us to efficiently decide whether or not to include i in the targeted, reduced subset we are constructing.
The idea is to aggregate the contribution of each i towards the representation bias expression across all random choices of the training set D \ T . We call this the predictability score p(i) for i: on average, how reliably can the label yi be predicted using features Φ(xi) when a model fromM is trained on a randomly chosen training set D \ T not containing i. The higher the value of p(i), the easier it is to correctly classify the instance (xi, yi) using model familyM. This is the signal we will use to decide whether to include i in the reduced subset S we are constructing.
With some abuse of notation, for i ∈ D, let q(i) , ∑
T3i q(T ) denote the marginal probability of choosing a subset T that contains i. The ratio q(T )q(i) is then the probability of T conditioned on it containing i. Let fMT (Φ(xi), yi) be the classification accuracy of MT on i. The reformulation of representation bias in terms of predictability scores of individual instances works as follows:
ET∼q [ fMT (Φ(X T ), Y T ) ] = ∑ T⊂S q(T ) · 1|T | ∑ i∈T fMT (Φ(xi), yi)
= ∑ T⊂S ∑ i∈T q(T ) · fMT (Φ(xi), yi)|T |
= ∑ i∈S ∑ T⊂S T3i q(T ) · fMT (Φ(xi), yi)|T |
= ∑ i∈S q(i) ∑ T⊂S T3i q(T ) q(i) fMT (Φ(xi), yi) |T |
= ∑ i∈S q(i)ET⊂S, T3i [ fMT (Φ(xi), yi) |T | ] = ∑ i∈S p(i)
where p(i) is the predictability score of i defined as: p(i) , q(i)ET⊂S, T3i [ fMT (Φ(xi), yi)
|T |
] (3)
While the method works for any probability distribution q with non-zero support on all samples, for simplicity of exposition, we restrict q to be the uniform distribution over all subsets T ⊂ S of a fixed size. This makes both |T | and q(i) fixed constants; in particular, q(i) = (|S|−1 |T |−1 ) / (|S| |T | )
= |T ||S| . This reduces the predictability score expression of Eq. (3) to the simplified variant p̃(i):
p̃(i) , 1
|S| ET⊂S, T3i [fMT (Φ(xi), yi)] (4)
Putting the pieces together, we have a factored reformulation of the representation bias in Eq. (2): R(Φ, S,M) = ∑ i∈S p̃(i) (5)
Armed with this factored representation, we return to the task of identifying an S ⊂ D, |S| ≥ n that minimizes the representation bias. We use the simplified predictability scores (henceforth simply referred to as predictability scores) as a heuristic metric to decide which i ∈ D to include in S. We consider three approaches that iteratively filter out the most predictable instances fromD to arrive at S. In all cases, we use a fixed training set size |S \ T | = t < n. Further, since a larger filtered set is generally desirable, we terminate the filtering process early (i.e., while |S| > n) if the predictability score for every i falls below a pre-specified early stopping threshold τ ∈ [0, 1]. The three approaches are as follows. (A) A simple greedy approach starts with the full set S = D, identifies an i ∈ S with the highest predictability score, removes it from S, and repeats up to |D|−n times. (B) A greedy slicing approach identifies the instances with the k highest predictability scores, removes all of them from S, and repeats the process up to b |D|−nk c times. (C) A slice sampling approach where, instead of greedily choosing the top k instances, it randomly samples k instances with probabilities proportional to their predictability scores.1 In this paper, we use the greedy slicing approach in our experiments and refer to it as AFLITE. While the optimum bias reduction via AFOPTIMUM is intractable, its light-weight version, AFLITE, is applicable in practice.
The slice sampling approach can be efficiently implemented using what is known as the Gumbel method or Gumbel trick (Gumbel & Lieblein, 1954; Maddison et al., 2014), which uses random perturbations to turn sampling into a simpler problem of optimization. This has recently found success in several probabilistic inference applications (Kim et al., 2016; Jang et al., 2016; Maddison et al., 2016; Balog et al., 2017; Kool et al., 2019). Starting with the log-predictability scores log p̃(i) for various i, the idea is to perturb them by adding an independent random noise γi drawn from the standard Gumbel distribution. Interestingly, the maximizer i∗ of γi+log p̃(i) turns out to be an exact sample drawn from the (unnormalized) distribution defined by p̃. Note that i∗ is a random variable since the γi are drawn at random. This result can be generalized (Vieira, 2014) for slice sampling: the k highest values of Gumbel-perturbed log-predictability scores correspond to sampling, without replacement, k items from the probability distribution defined by p̃. The Gumbel method is typically applied to exponentially large combinatorial spaces, where it is challenging to scale up. In our setting, however, the overhead is minimal since the cost of drawing a random γi is negligible compared to computing p̃(i).
Implementation Algorithm 1 provides an implementation of AFLITE. The algorithm takes as input a dataset D = (X,Y ), a representation Φ(X) we are interested in minimizing the bias in, a model family M (e.g., linear classifiers), a target dataset size n, size m of the support of the expectation in Eq. (4), training set size t for the classifiers, size k of each slice, and an early-stopping filtering threshold τ . Importantly, for efficiency, Φ(X) is provided to AFLITE in the form of precomputed embeddings for all of X . To obtain Φ(X) in practice, we train a first model on a small fraction of the data based on the learning curve in low-data regime, and do not reuse this data for the rest of our experiments. Moreover, this fraction corresponds to the training size t for AFLITE and it remains unchanged across iterations. We follow the iterative filtering approach, starting with S = D and iteratively removing some instances with the highest predictability scores using the
1All of these approaches can be improved further by considering not only the predictability score of the top-k instances i but also (via retraining without these instances) how their removal would influence the predictability scores of other instances in the next step. We found our computationally lighter approaches to work well even without the additional overhead of such look-ahead.
Algorithm 1: AFLITE Input: dataset D = (X,Y ), pre-computed representation Φ(X), model familyM, target dataset size n, number of random partitions m, training set size t < n, slice size k ≤ n, early-stopping threshold τ Output: reduced dataset S
1 S = D 2 while |S| > n do // Filtering phase 3 forall i ∈ S do 4 Initialize a multi-set of out-of-sample predictions E(i) = ∅ 5 for iteration j : 1..m do 6 Randomly partition S into (Tj , S \ Tj) s.t. |S \ Tj | = t 7 Train a classifier L ∈M on {(Φ(x), y) | (x, y) ∈ S \ Tj} (L is typically a linear classifier) 8 forall i = (x, y) ∈ Tj do 9 Add the prediction L(Φ(x)) to E(i)
10 forall i = (x, y) ∈ S do 11 Compute the predictability score p̃(i) = |{ŷ ∈ E(i) s.t. ŷ = y}| / |E(i)| 12 Select up to k instances S′ in S with the highest predictability scores subject to p̃(i) ≥ τ 13 S = S \ S′ 14 if |S′| < k then 15 break 16 return S
greedy slicing strategy. Slice size k and number of partitions m are determined by the available computation budget.
At each filtering phase, we train models (linear classifiers in our implementation) on m different random partitions of the data, and collect their predictions on their corresponding test set. For each instance i, we compute its predictability score as the ratio of the number of times its label yi is predicted correctly, over the total number of predictions for it. We rank the instances according to their predictability score and use the greedy slicing strategy of removing the top-k instances whose score is not less than the early-stopping threshold τ . We repeat this process until fewer than k instances pass the τ threshold in a filtering phase or fewer than n instances remain.

heading: 3 EXPERIMENTAL ANALYSIS

text: We evaluate AFLITE across various domains (synthetic, natural language processing, computer vision), different tasks in a given domain (language inference and question answering in NLP), different datasets for a given task (SNLI and MNLI in natural language inference), and different representations for a given dataset (pre-computed embeddings from ESIM+GLoVe, BERT, RoBERTa for the SNLI dataset).

heading: 3.1 SYNTHETIC EXPERIMENTS

text:
We demonstrate the utility of AFLITE in a synthetic data setting. Our dataset consists of twodimensional data, arranged in concentric circles, at four different levels of separation, as shown in the Figure 2. As is evident, a linear function might not be adequate for separating the two classes; it requires a more complex non-linear model such as an SVM with an RBF kernel. 2
We add class-specific artificially constructed features (artifacts) sampled from two different Gaussian distributions. These features are only added to 75% of the data in each class, while for the rest of the data, we insert random (noise) features. These artifacts make the task solvable through a linear function. Furthermore, for the first dataset, with the largest separation, we flipped the labels of some examples with artifacts, making the data slightly adversarial even to the RBF. Both models can clearly leverage the artifacts, and demonstrate improved performance over a baseline without artifacts.
2We use standard implementations from scikit-learn: https://scikit-learn.org/stable/.
Once we apply AFLITE, as expected, the number of examples with artifacts is reduced considerably, making the task hard once again for the linear model, but still solvable for the non-linear one. The filtered dataset is shown in the bottom half of Fig. 2, and the captions indicate the performance of a linear and an SVM model. For the first dataset, we see that AFLITE removes most of those examples with flipped labels.

heading: 3.2 NLP EXPERIMENTS

text:
We evaluate AFLITE on two NLP tasks, namely NLI and question answer sentence selection. We use two popular NLI large-scale datasets – SNLI (Bowman et al., 2015) and MNLI (Wang et al., 2018). For the answer sentence selection task, we use QNLI which is a transformed version of the SQuAD question answering dataset (Rajpurkar et al., 2016) converted to binary classification where systems determine whether a sentence contains the answer to a question.
SNLI Each instance in the SNLI dataset consists of a premise-hypothesis pair that belongs to one out of three possible categories (entailment, contradiction, or neutral) based on the relationship between the premise and the hypothesis.
For SNLI, we experiment with three different feature representations derived from strong baseline models: ΦBERT and ΦRoBERTa which are based on BERT (Devlin et al., 2019) and RoBERTa (Liu et al., 2019b), large-scale pretrained masked language models, plus ΦESIM+GLoVe which uses the
ESIM model (Chen et al., 2016) with GLoVe word embeddings (Pennington et al., 2014). In all cases, feature representation Φ is trained on a random sample of 10% of the original training instances, and feature representations are extracted from the final layer before the output layer. These features are pre-computed for all remaining instances while we discard the instances (10% of training) used for training the embeddings in the subsequent steps of our algorithm. Additionally, to measure the ability of a weaker adversary to filter biases only learned by a stronger model, we evaluate the filtered datasets (for SNLI) with three different models: (i) ESIM with ELMo embeddings (Peters et al., 2018), (ii) BERT-large, and (iii) RoBERTa-large models.
Table 1 shows the results for SNLI. In all cases, applying AFLITE substantially reduces overall model accuracy, with typical drops of 15-35% depending on the models used for learning the feature representations and those used for evaluation of the filtered dataset. In general, performance is lowest when using the strongest model (RoBERTa) for learning feature representations. Results also highlight the ability of weaker adversaries to produce datasets that are still challenging for much stronger models with a drop of 13.7% for RoBERTa using ΦESIM+GLoVe as feature representation. We also include a model that uses Point-wise Mutual Information (PMI) between words in a given instance and the target label as a feature. The baseline captures the extent to which datasets exhibit word-association artifacts. While this baseline is relatively weaker than other models, we still show that its performance reduce from 54.5% on D to 41.9% on the D(φRoBERTa) dataset.
It might seem unsurprising that reducing the size of the training set results in lower performance. To control for the confounding factor of the dataset size, we create another filtered dataset D92k, sampled randomly from D such that its size is approximately equal to the size of D(φRoBERTa) dataset. All models achieve nearly the same performance as their performance on the full dataset – even when trained on just one-fifth the original dataset size. This result further points to the fact that current benchmark datasets contain significant redundancy within its instances.
Finally, to demonstrate the value of the iterative, ensemble-based AFLITE algorithm, we compare with a baseline where using a single model, we filter out the most predictable examples in a single iteration — a non-iterative, single-model version of AFLITE. A RoBERTa-large model trained on this subset (of the same size as D(φRoBERTa)) achieves a dev accuracy of 72.1%. Compared to the performance of RoBERTa on D(φRoBERTa) (62.6%, see Table 1), it makes this baseline a sensible yet less effective approach. In particular, this illustrates the need for an iterative procedure involving models trained on multiple partitions of the remaining data in each iteration.
We also report the k-nearest neighbors distances between examples in the train and heldout data in Table 3. We consider distances for examples within each class, as well as examples across classes. The distances are computed using cosine similarity between pooled features from BERT-based model (features for the [CLS] token, indicating a sentence-pair feature) trained on the original SNLI dataset. Distances are measured between samples from the heldout data, and their nearest neighbors in the training data, before and after filtering. Distances generally increase after filtering, indicating that AFLITE promotes selecting a diverse set of examples from the dataset. The only exception to the rule is the neutral class, where distances to other classes decrease – this is not surprising since the neutral class is known to be associated with the least number of artifacts (Gururangan et al., 2018).
MNLI and QNLI Following the same procedure described above, we apply AFLITE on the MNLI and QNLI datasets. Since RoBERTa resulted in the largest drops in performance across the board in SNLI, we only experiment with RoBERTa as adversary for MNLI and QNLI. While RoBERTa achieves over 90% on both original datasets, its performance drops to 66.2% for MNLI and to 77.7% for QNLI on the reduced datasets. Similarly, partial input baseline performance also decreases substantially on both dataset compared to their performance on the original dataset. Table 2 shows these results. We show that AFLITE consistently result in reduced accuracy on the filtered datasets across multiple NLP benchmark datasets, even after controlling for the size of the training set.

heading: 3.2.1 OUT-OF-DISTRIBUTION NLI

text:
We measure the performance of AFLITE on three other benchmarks for NLI evaluation, which provide out-of-distribution examples to challenge reliance on dataset biases in the original SNLI data (Glockner et al., 2018; Naik et al., 2018). Such benchmarks approximate the performance of NLI models in the wild. NLI Diagnostics (Wang et al., 2018) is a set of hand-crafted examples designed to demonstrate model performance on several fine-grained semantic categories, such as logical reasoning and commonsense knowledge. HANS (McCoy et al., 2019) contains evaluation examples designed to avoid common structural heuristics (such as word overlap) which could be used by models to correctly predict NLI inputs, without true inferential reasoning. Adversarial NLI (Nie et al., 2019) consists of premises collected from Wikipedia and other news corpora, and human generated hypotheses, arranged at different tiers of the challenge they present to a model, using a human and model in-the-loop procedure. Given that these benchmarks are collected independently of the original SNLI task, the biases from SNLI are less likely to carry over; however these benchmarks might contain their own biases (Liu et al., 2019a).
AFLITE assigns a predictability score to all samples in a dataset, resulting in an ordering of the data. Filtering out examples from the head of the data distribution based on this order yields more accurate benchmarks for measuring true model performance. On the other hand, transferability to out-of-distribution data would involve a greater balance between examples from the head and the tail ends of the data distribution. Hence we evaluate AFLITE for generalization using a larger filtered subset, amounting to only a third of the full training data. We present these results on all the above benchmarks in Table 4. On the two diagnostic datasets (HANS and NLI-Diagnostics), we perform a zero-shot evaluation of the two models. Adversarial NLI allows to test for transfer
capabilities, by finetuning these models on each of the three training datasets (Rd1, Rd2 and Rd3). On each of the benchmarks above, the model trained on the AFLITE data consistently outperforms the model trained on the full SNLI data. challenging examples in the HANS benchmark, which targets models purely relying on lexical and syntactic cues. Similarly, our model performs better on the instances in NLI-Diagnostics that require logical reasoning and commonsense knowledge, as opposed to instances that can be solved through lexical entailment alone.

heading: 3.3 IMAGENET EXPERIMENTS

text:
We evaluate AFLITE on image classification through ImageNet (ILSVRC2012) classification. On ImageNet, we use the state-of-the-art EfficientNet-B7 model as our core feature extractor Φ (Tan & Le, 2019). The EfficientNet model is learned from scratch on a fixed 20% sample of the ImageNet training set, using AutoAugment data augmentation (Cubuk et al., 2019). We then use the 2560- dimensional features extracted by EfficientNet-B7 as then underlying representation for AFLITE to use to filter the remaining dataset.
In Table 5, we evaluate the robustness of the filtered dataset by considering ImageNet accuracy across the EfficientNet and ResNet model families (He et al., 2016). When lowering the size of the training set – down to 20% of the original, we find a large drop in performance. The EfficientNet models seem to suffer less – from 84% to 73% on EfficientNet-B7 versus 80.6% to 56.5% on ResNet-152. However, the biggest performance drop comes from training and evaluating on the AFLITE-filtered dataset: the top performer is still EfficientNet-B7, but its accuracy drops to 24.5% top-1. This is despite controlling for dataset size, as well as discrepancy between the training and validation sets.
Overall, these results suggest that image classification – even within a subset of the closed world of ImageNet – is far from solved. These results echo other findings that suggest that common biases that naturally occur in web-scale image data, such as towards canonical poses (Alcorn et al., 2019) or towards texture rather than shape (Geirhos et al., 2018), are problems for ImageNet-trained classifiers. Indeed, the randomly-selected ImageNet images in Figure 1 suggest that the AFLITE algorithm learns to identify subsets of the data that are particularly challenging.

heading: 4 RELATED WORK

text:
Our proposed framework for artifact reduction is related to the adversarial filtering (AF) algorithm in Zellers et al. (2018), yet distinct in two key ways: our approach is (i) much more broadly applicable (by not requiring over generation of data instances), and (ii) considerably more lightweight (by not requiring re-training a model at each iteration of AF). Variants of this AF approach have recently been used to create other datasets such as HellaSwag (Zellers et al., 2019) and ANLI (Bhagavatula
et al., 2019) by iteratively perturbing dataset instances until a target model cannot fit the resulting dataset. While effective, these approaches run into three main pitfalls. First, dataset curators need to explicitly devise a strategy of collecting or generating perturbations of a given instance. Second, the approach runs the risk of distributional bias where a discriminator can learn to distinguish between machine generated instances and human-generated ones. Finally it requires re-training a model at each iteration, which is computationally expensive especially when using a large model such as BERT (Devlin et al., 2019) as the adversary. In contrast, AFLITE focuses on addressing dataset biases from existing datasets instead of adversarially perturbing instances. AFLITE was earlier proposed by Sakaguchi et al. (2019) to create the Winogrande dataset. This paper presents more thorough experiments, theoretical justification and results from generalizing the proposed approach to multiple popular NLP and Vision datasets.
AFLITE is also inspired by Gururangan et al. (2018), who study lexical biased prevalent in the SNLI dataset (Bowman et al., 2015) and use point-wise mutual information (PMI) between a word and an inference class to determine the words that are highly indicative of the target label. Instead of lexical features, we adopt a deeper representation of the instances using their pre-computed dense feature representations. We use an ensemble of linear classifiers trained on random subsets of the data to determine whether the dense feature representations are highly indicative of the target label. If so, we discard the corresponding instances and proceed iteratively.
Li & Vasconcelos (2019) recently proposed REPAIR, a method to remove representation bias by dataset resampling. While resampling is a common technique for balancing datasets, the motivation in REPAIR is to learn a probability distribution over the dataset that favors instances that are hard for a given representation. This approach targets how to train better, less-biased models as opposed to creating datasets with fewer artifacts. In addition, the implementation of REPAIR relies on intraining classification loss as opposed to out-of-sample generalization accuracy. RESOUND (Li et al., 2018) is another method that quantifies the representation biases of datasets. It uses the representation biases to assemble a new K-class dataset with smaller biases by sampling an existing C-class dataset (C > K).
Arjovsky et al. (2019) argue that unstable, spurious correlations in the data would generalize poorly to novel test environments. Thus, they propose Invariant Risk Minimization as an objective that promotes learning representations of the data which are stable across environments. Instead of learning optimal classifiers, our aim is to remove instances that exhibit artifacts in a dataset.

heading: 5 CONCLUSION

text: We presented AFLITE – a novel iterative greedy algorithm that adversarially filters out data points to arrive at a reduced dataset with more realistic problem distributions and considerably fewer spurious biases. We apply AFLITE to four widely-used datasets, including SNLI and ImageNet, where reported performance is extremely high – and show that state-of-the-art performance on the resulting filtered dataset drops by 30 points for SNLI and drops from 84.4% to 24.5% Top-1 accuracy for ImageNet. In extensive analysis we show that AFLITE is effective on real as well as synthetic datasets. We hope that dataset creators will employ AFLITE to identify unobservable artifacts before releasing new challenge datasets for the research community in order to have a more reliable estimate of model performance on future AI benchmarks.