Automatic Differentiation of Programs with Discrete Randomness
Automatic Differentiation of Programs with Discrete Randomness
复制标题
DOI：
10.48550/arxiv.2210.08572
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
G. Arya;Moritz Schauer;Frank Schafer;Chris Rackauckas
中科院分区：
文献类型：
--
作者：
G. Arya;Moritz Schauer;Frank Schafer;Chris Rackauckas
自动微分（AD）是一种用于构建计算原始程序导数的新程序的技术，由于基于梯度的优化提供的性能改进，它在科学计算和深度学习中无处不在。然而，AD系统已被限制到具有对参数的连续依赖性的程序的子集。具有由分布参数控制的离散随机行为的程序，例如以正面概率$p$抛硬币，对这些系统构成了挑战，因为结果（正面与反面）和参数（$p$）之间的联系基本上是离散的。在本文中，我们开发了一种新的重新参数化为基础的方法，允许生成的程序的期望是原始程序的期望的衍生物。我们展示了这种方法如何提供一个无偏和低方差的估计，这是自动化的传统AD机制。我们证明了无偏的离散时间马尔可夫链，代理为基础的模型，如康威的游戏的生活，和无偏的反向模式AD的粒子滤波器。我们的代码包可在https://github.com/gaurav-arya/StochasticAD.jl上获得。
Automatic differentiation (AD), a technique for constructing new programs which compute the derivative of an original program, has become ubiquitous throughout scientific computing and deep learning due to the improved performance afforded by gradient-based optimization. However, AD systems have been restricted to the subset of programs that have a continuous dependence on parameters. Programs that have discrete stochastic behaviors governed by distribution parameters, such as flipping a coin with probability $p$ of being heads, pose a challenge to these systems because the connection between the result (heads vs tails) and the parameters ($p$) is fundamentally discrete. In this paper we develop a new reparameterization-based methodology that allows for generating programs whose expectation is the derivative of the expectation of the original program. We showcase how this method gives an unbiased and low-variance estimator which is as automated as traditional AD mechanisms. We demonstrate unbiased forward-mode AD of discrete-time Markov chains, agent-based models such as Conway's Game of Life, and unbiased reverse-mode AD of a particle filter. Our code package is available at https://github.com/gaurav-arya/StochasticAD.jl.