Du+'23 Generalizing Backpropagation for Gradient-Based Interpretability (ACL 2023)

まとめ

• Backpropagation を半環の概念を使って一般化。出力y の 入力x に関する微分値だけではなく、一番勾配が流れる最大のパスなど勾配に関するを様々な量を Backpropagation と同様の計算量 (O(|E|) = 計算グラフのエッジ数に対して線形時間) で計算可能なことを示した。

• 出力y の 入力x に関する微分値: 愚直に計算すると 入力x→出力y の全てのパスを列挙 ➛ それぞれのパスをトラバースして微分値を計算（積部分の計算） ➛ 計算したパスごとの微分値を最後に足し合わせ（和部分の計算）が必要
• これは Edge 数に対して指数時間かかって遅い

• これを解決するのが Backpropagation．和積の性質から共通計算部分を保存していけば効率的に計算できる．（PyTorch とかの自動微分と同じ） Edge 数に対して線形時間
• 本質は積計算が和に対して分配可能であること → 半環として一般化される

• 半環が定義できるような演算子（と集合）を元の和・積計算の部分に置き換えることで，O(|E|) で勾配に関する様々な統計量げ計算可能に
• 例：(+,x) → (max, x) に置き換えると勾配が流れる最大のパス（の勾配の量）が O(|E|) で計算可能