Gradient Estimation Using Stochastic Computation Graphs

By John Schulman, Nicolas Manfred Otto Heess, Theophane Weber, Pieter Abbeel. 2015

426 citations recorded by the source corpus.

In a variety of problems originating in supervised, unsupervised, and reinforcement learning, the loss function is defined by an expectation over a collection of random variables, which might be part of a probabilistic model or the external world. Estimating the gradient of this loss function, using samples, lies at the core of gradient-based learning algorithms for these problems. We introduce the formalism of stochastic computation graphs—directed acyclic graphs that include both deterministic functions and conditional probability distributions—and describe how to easily and automatically derive an unbiased estimator of the loss function's gradient. The resulting algorithm for computing the gradient estimator is a simple modification of the standard backpropagation algorithm. The generic scheme we propose unifies estimators derived in variety of prior work, along with variance-reduction techniques therein. It could assist researchers in developing intricate models involving a combination of stochastic and deterministic operations, enabling, for example, attention, memory, and control actions.

Subfields: Artificial Intelligence, Reinforcement Learning, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Reinforcement Learning

In Optimization & Training

Citations in the corpus

Structured Attention Networks (2017, methodology): “Notably each step of this process (including inference) is differentiable, so the model can be trained end-to-end without having to resort to deep policy gradient methods (Schulman et al., 2015).”
Continuous control with deep reinforcement learning (2015, methodology): “The techniques we described here for scaling DPG are also applicable to stochastic policies by using the reparametrization trick (Heess et al., 2015; Schulman et al., 2015a).”
An Introduction to Probabilistic Programming (2018, background): “It can also be noted that, in this setting, any of the activations of the neural network trivially could be made stochastic, yielding a stochastic computation graph (Schulman et al., 2015), rather than a purely deterministic neural network.”
Seq2SQL: Generating Structured Queries from Natural Language using Reinforcement Learning (2017, background): “Schulman et al. (2015) show that sampling during the forward pass of the network can be followed by the corresponding injection of a synthetic gradient, which is a function of the reward, during the backward pass in order to compute estimated parameter gradient.”
Categorical Reparameterization with Gumbel-Softmax (2016, methodology): “Thus, by replacing categorical samples with GumbelSoftmax samples we can use backpropagation to compute gradients (see Section 3.1).”
Equivalence Between Policy Gradients and Soft Q-Learning (2017, methodology): “With an entropy cost added to the returns, the optimal policy has the form π(a | s) ∝ exp(Q(s, a)); hence policy gradient methods solve for the optimal Q-function, up to an additive constant (Ziebart [2010]).”
The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables (2016, background): “While these can be made to work with AD, they involve special casing and defining surrogate objectives [39], and even then they can have high variance.”
Efficient Neural Architecture Search via Parameter Sharing (2018, methodology): “Additionally, ENAS’s choice of representing computations using a DAG is inspired by the concept of stochastic computational graph (Schulman et al., 2015), which introduces nodes with stochastic outputs into a computational graph.”
Neural Text Summarization: A Critical Evaluation (2019, neutral): “Schulman et al. (2015) study the problems related to using ROUGE as an evaluation metric with respect to ﬁnding optimal solutions and provide proof of NP-hardness of global optimization with respect to ROUGE.”
MuProp: Unbiased Backpropagation for Stochastic Neural Networks (2015, methodology): “MuProp’s simple and general formulation allows a straightforward derivation of unbiased gradient estimators for arbitrary stochastic computational graphs – directed acyclic graph (DAG) with a mix of stochastic and deterministic computational nodes (see, e.g., Schulman et al. (2015)).”
Spatially Invariant Unsupervised Object Detection with Convolutional Neural Networks (2019, background): “| Backpropagating through this sampling process can be achieved using any of a large number of techniques that have been invented in recent years (Schulman et al. 2015).”
Learning Algorithms for Active Learning (2017, methodology): “For a clear review of optimization techniques for general stochastic computation graphs, see Schulman et al. (2016a).”
PIPPS: Flexible Model-Based Policy Search Robust to the Curse of Chaos (2019, background): “The algorithm is not limited to RL problems, but is applicable to general stochastic computation graphs (Schulman et al., 2015), and could be used for training probabilistic models, stochastic neural networks, etc.”
Attend, Infer, Repeat: Fast Scene Understanding with Generative Models (2016, methodology): “Variational auto-encoders [21, 9] and their discrete counterparts [18] made the important contribution of showing how the gradient computations for learning of amortized inference and generative models could be interleaved, allowing both to be learned simultaneously in an end-to-end fashion (see als”
Imagination-Augmented Agents for Deep Reinforcement Learning (2017, methodology): “The parameter θ v are updated with ∆ θ v towards bootstrapped k -step return: In our numerical implementation, we express the above updates as gradients of a corresponding surrogate loss [47].”
Learning Disentangled Representations with Semi-Supervised Deep Generative Models (2017, methodology): “To perform semi-supervised learning in this class of models, we need to i) define an objective that is suitable to general dependency graphs, and ii) define a method for constructing a stochastic computation graph [30] that incorporates both the conditional dependence structure in the generative mod”
Learning to Compose Domain-Specific Transformations for Data Augmentation (2017, methodology): “In order to work around this constraint, we now describe our model in the syntax of reinforcement learning (RL), which provides a convenient framework and set of approaches for handling computation graphs with non-differentiable or stochastic nodes [27].”
A Brief Survey of Deep Reinforcement Learning (2017, background): ““reparameterisation trick” [61, 108], allows neural networks to be treated as stochastic computation graphs that can be optimised over [121], which is a key concept in algorithms such as stochastic value gradients (SVGs) [46].”
Backpropagation through the Void: Optimizing control variates for black-box gradient estimation (2017, background): “In reinforcement learning, for example, the function being optimized is unknown to the agent and is treated as a black box (Schulman et al., 2015).”