python - 实现二阶导数的自动微分：遍历计算图的算法？

Question

我正在尝试为 Python 统计包实现自动微分（问题公式类似于优化问题公式）。

计算图是使用运算符重载和工厂函数生成的，用于 sum()、exp() 等操作。我已经使用反向累积实现了梯度的自动微分。但是，我发现实现二阶导数（Hessian）的自动微分要困难得多。我知道如何进行单独的第二部分梯度计算，但是我很难想出一种智能的方法来遍历图形并进行累积。有谁知道为二阶导数或开源库提供自动微分算法的好文章，这些算法实现了我可能会尝试学习的相同功能？

Answer 1

首先，您必须决定是否要计算稀疏 Hessian 或更接近完全密集 Hessian 的东西。

如果您想要稀疏，那么目前有两种竞争方式可以做到这一点。只有巧妙地使用计算图，对计算图进行一次反向扫描，您就可以使用 edge_pushing 算法计算 Hessian 矩阵：

http://www.tandfonline.com/doi/full/10.1080/10556788.2011.580098

或者您可以尝试图形着色技术将您的 Hessian 矩阵压缩成一个列数较少的矩阵，然后使用反向累积来计算每一列

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.66.2603

如果您想要的是密集的 Hessian 矩阵（在实践中不常见），那么您最好使用反向累积一次计算一列 Hessian 矩阵（搜索 BRUCE CHRISTIANSON 和反向累积）

Answer 2

在 3 维中近似 Hessian 的常用方法是BFGS

L-BFGS方法类似。

在这里，您可以找到多种语言（C#、C++、VBA 等）的 L-BFGS（计算 Hessian 作为求解 ODE 的中间结果）的源代码，尽管 Python 中没有。我认为翻译并不容易。

如果您要从另一种语言翻译 alg，请特别注意数值错误并进行敏感性分析（您需要计算 Hessian 矩阵的逆矩阵）