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

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 和反向累积）