Perturbation confusion in forward automatic differentiation of higher-order functions
Perturbation confusion in forward automatic differentiation of higher-order functions
复制标题
DOI：
10.1017/s095679681900008x
复制
发表时间：
2012-11
影响因子：
1.1
通讯作者：
Oleksandr Manzyuk;Barak A. Pearlmutter;Alexey Radul;David R. Rush;J. Siskind
中科院分区：
文献类型：
--
作者：
Oleksandr Manzyuk;Barak A. Pearlmutter;Alexey Radul;David R. Rush;J. Siskind
自动微分(AD)是一种扩充计算机程序以计算导数的技术。AD在其正向累加模式中的本质是将扰动附加到每个数字，并通过重载算术运算符来在计算中传播这些扰动。当导数嵌套时，必须区分不同的导数计算及其相关的扰动。这通常是通过为每个导数计算创建唯一标记并标记扰动来实现的。我们展示了一个微妙的错误，存在于支持高阶函数导数的现场实现中，其中的扰动被混淆，尽管有标记机制，导致不正确的结果。该错误的本质如下：每个导数计算都需要一个唯一的标记，但在现有的实现中，当在某一点取函数的导数时，会创建唯一的标记。当取高阶函数的导数时，这些不需要对应！我们给出一个简单的例子：一个高阶函数f，它在点x的导数，即f‘(X)，本身就是一个计算导数的函数。当取咖喱函数的导数时，这种情况自然会出现。提出了两种可能的解决方案，并讨论了它们的不足之处。一种是使用ETA扩展来延迟新标签的创建，以便将它们与导数计算一一对应。另一种是用标签替换机制包装导数运算符的输出。这两种解决方案似乎都很难在不违反前向AD所要求的复杂性保证的情况下实现。
Abstract Automatic differentiation (AD) is a technique for augmenting computer programs to compute derivatives. The essence of AD in its forward accumulation mode is to attach perturbations to each number, and propagate these through the computation by overloading the arithmetic operators. When derivatives are nested, the distinct derivative calculations, and their associated perturbations, must be distinguished. This is typically accomplished by creating a unique tag for each derivative calculation and tagging the perturbations. We exhibit a subtle bug, present in fielded implementations which support derivatives of higher-order functions, in which perturbations are confused despite the tagging machinery, leading to incorrect results. The essence of the bug is as follows: a unique tag is needed for each derivative calculation, but in existing implementations unique tags are created when taking the derivative of a function at a point. When taking derivatives of higher-order functions, these need not correspond! We exhibit a simple example: a higher-order function f whose derivative at a point x, namely f′(x), is itself a function which calculates a derivative. This situation arises naturally when taking derivatives of curried functions. Two potential solutions are presented, and their deficiencies discussed. One uses eta expansion to delay the creation of fresh tags in order to put them into one-to-one correspondence with derivative calculations. The other wraps outputs of derivative operators with tag substitution machinery. Both solutions seem very difficult to implement without violating the desirable complexity guarantees of forward AD.