稀疏自动微分

阐述

稀疏自动微分是对自动微分的扩展。一般来说，Jacobian 在矩阵形势下可能会表现出一定的稀疏性，而

• 前向自动微分总是计算矩阵-向量乘积，也等价于矩阵中几列的加权和
• 后向自动微分总是计算向量-矩阵乘积，也等价于矩阵中几行的加权和

如果矩阵是稀疏的，那么几列（或者几行）的内容可以一次性计算完成，大大节约计算次数；例如，下图是前向自动微分按列压缩的情况：

稀疏性检测

如果稀疏性不是已知的，那么就需要用检测算法来获得一定的稀疏性模式。

图染色

将一个有 $m$ 列的稀疏 Jacobian 矩阵转化为一个具有 $m$ 个节点的图，且若 $j,j'$ 列有处于同一行的非零元素，则在节点 $j,j'$ 之间连一条线；然后对这个图染色，且相邻节点不能具有同一种颜色。

虽然图染色问题要找到最优解是 NP-complete 的，但是一些启发式算法可以达到不错的效果。

染好色之后，设颜色一共有 $k$ 种，记 $c_1,\cdots,c_k$ 为由 0 和 1 构成的 $m$ 维向量，如果节点 $j$ 是颜色 $i$ 则 $c_i[j]$ 为 1，否则为 0。对应的 Jacobian 可以用以下的种子算出：

$$d=x+\sum_ic_i\varepsilon_i$$

实例

ADTypes 用一个三元组来抽象稀疏自动微分算法：

1. 底层的稠密微分
2. 稀疏检测算法：对 jacobian_sparsity 和 hessian_sparsity 都能返回一个抽象 Bool 矩阵
3. 矩阵着色算法：对 column_coloring, row_coloring 和 symmetric_coloring 都能返回一个着色向量

性质

相关内容

参考文献