我对自动微分的内部工作不熟悉，并且遇到了一些论文和幻灯片，这些论文和幻灯片指出可以使用自动微分在线性时间内计算矢量雅可比积。具体写：
$e^\top ( \frac{\partial f}{\partial x} )$
可以计算任何 e in O(N)。雅可比是N-by-N。我认为是N^2，但我不完全理解自动微分如何降低时间复杂度。
问问题
169 次
2 回答
1
我不完全理解自动微分如何降低时间复杂度。
我假设您了解反向传播和/或反向模式自动微分如何适用于标量函数 y = f(x)，其中 f : R^n -> R。假设计算 f 需要时间 O(1)。
如果您还记得反向传播，您首先设置 dy/dy = 1，然后使用链式法则计算 dy/dx。您在这里所做的是计算向量 [1.0] 与作为行向量的雅可比行列式的乘积，以获得作为列向量的向量-雅可比行积。所以你正在计算 VJP，你的向量只是一个长度为 1 的向量。您在 O(1) 时间内完成此操作。
现在假设我正在计算多元函数 y = f(x) 的导数，其中 f : R^n -> R^m。那么 Jacobian 确实是 mxn，并且使用反向模式 AD 计算完整的 Jacobian 将花费时间 O(m)。但是，您可以通过设置 dy_i/dy_i = v_i 的值来计算向量 v 在时间 O(1) 内的向量-雅可比积，其中 i={1,...,m}。然后你像往常一样反向传播，并在一次反向传播中获得 VJP。
于 2020-05-31T19:24:32.353 回答
0
如果您有一个基本假设，即隐藏空间是固定的，那么它是线性的。假设您的函数 f 是矩阵变换的组合，其中固定矩阵 f1 是 H×N，f2 是 H×H，f3 是 N×H。然后对于 N 维向量 e，我们可以将计算计算为 f1*e，然后应用 f2，然后应用 f3。这与 N 成线性关系，但与隐藏空间 H 不成线性关系。
于 2020-04-30T16:35:32.307 回答