Edge pushing is equivalent to vertex elimination for computing Hessians
Edge pushing is equivalent to vertex elimination for computing Hessians
复制标题
推边相当于计算 Hessians 的顶点消除
DOI：
10.1137/1.9781611974690.ch11
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Mu Wang, Alex Pothen
中科院分区：
文献类型：
--
作者：
Mu Wang, Alex Pothen
我们证明了两种不同的Hessian评估算法在AD中的等价性。第一种是Gower和Mello的Edge Pushing算法，其可以被视为用于计算Hessian的二阶反向模式算法。在早期的工作中，我们已经推导出的边缘推算法，利用反向模式不变的基础上，在编译器理论中的活变量的概念。第二种算法基于消除梯度计算图中的顶点，在该算法中，中间变量从图中连续地被消除，并且适当地更新边的权重。我们证明，如果顶点被消除在一个反向的拓扑顺序，同时保持对称性的计算图的梯度，然后顶点消除算法和边缘推算法执行相同的计算。在这个意义上，这两种算法是等价的。这种将两种看似不同的海森计算方法统一起来的见解可能会导致改进的算法和实现来计算海森。
We prove the equivalence of two different Hessian evaluation algorithms in AD. The first is the Edge Pushing algorithm of Gower and Mello, which may be viewed as a second order Reverse mode algorithm for computing the Hessian. In earlier work, we have derived the Edge Pushing algorithm by exploiting a Reverse mode invariant based on the concept of live variables in compiler theory. The second algorithm is based on eliminating vertices in a computational graph of the gradient, in which intermediate variables are successively eliminated from the graph, and the weights of the edges are updated suitably. We prove that if the vertices are eliminated in a reverse topological order while preserving symmetry in the computational graph of the gradient, then the Vertex Elimination algorithm and the Edge Pushing algorithm perform identical computations. In this sense, the two algorithms are equivalent. This insight that unifies two seemingly disparate approaches to Hessian computations could lead to improved algorithms and implementations for computing Hessians.