Reverse-Mode 自動微分を理解する
Hiromi ISHII

2023-03-12
Tsukuba Computer Mathematics Seminar 2023

Forward-Mode と Reverse-Mode 自動微分
Forward-Mode と Reverse-Mode 自動微分

自動微分とは？
自動微分：与えられた関数の値とその微分係数を，合成関数の微分公式（連鎖律）を使って効率的・厳密に計算する方法
関数の値を順に計算しながら，連鎖律を使って微分係数も計算する
深層学習で損失関数の最適化の際に用いる誤差逆伝播法で注目を集める

関連するが異なる計算方法：
記号微分：数式を記号的な構文木で表現し，微分法則に従い記号的に処理．
厳密だが項数が組合せ爆発して非効率になりがち．

𝑓(𝑥 + 𝛥𝑥) − 𝑓(𝑥)の 𝛥𝑥 を微小数で置き換えて近似．
→𝛥𝑥

数値微分：極限 lim

あくまで近似．𝛥𝑡 をどう近似するかで振る舞いが変わってくる．

Forward-Mode と Reverse-Mode 自動微分

1/15

連鎖律
皆さんお馴染の基本公式ℝ𝑓ℝ𝑔ℝdd𝑔 d𝑓(𝑔 ∘ 𝑓) =d𝒙d𝑓 d𝒙
統一性のため 𝒖 = 𝒙, 𝒖 = 𝑓(𝒖 ), 𝒖 = 𝑔(𝒖 ) = 𝑔(𝑓(𝒖 )) として並び換えれば，ℝ𝒖ℝ𝒖ℝ𝒖ℝd𝒖d𝒖 d𝒖=d𝒖d𝒖 d𝒖Forward-Mode と Reverse-Mode 自動微分2/15

連鎖律 （多変数）
多変数も同様（但し，各 ∂𝒖 / ∂𝒖 はヤコビ行列 𝐽 = [∂𝑢 / ∂𝑢 ] <ℝ𝒖

∂𝒖=∂𝒖

ℝ−𝒖 −

⋯𝒖ℝ𝒖<）ℝ∂𝒖 ∂𝒖 − ∂𝒖 ∂𝒖⋯∂𝒖 − ∂𝒖 − ∂𝒖 ∂𝒖Forward-Mode と Reverse-Mode 自動微分

3/15

連鎖律 （多変数）
多変数も同様（但し，各 ∂𝒖 / ∂𝒖 はヤコビ行列 𝐽 = [∂𝑢 / ∂𝑢 ] <ℝ𝒖ℝ−𝒖 −⋯𝒖ℝ𝒖<）ℝ∂𝒖∂𝒖 ∂𝒖 ∂𝒖 − ∂𝒖 ∂𝒖 ∂𝒖=⋯∂𝒖∂𝒖 ∂𝒖 − ∂𝒖 − ∂𝒖 ∂𝒖 ∂𝒖Forward-Mode と Reverse-Mode 自動微分

3/15

連鎖律 （多変数）
多変数も同様（但し，各 ∂𝒖 / ∂𝒖 はヤコビ行列 𝐽 = [∂𝑢 / ∂𝑢 ] <ℝ𝒖ℝ−𝒖 −⋯𝒖ℝ𝒖<）ℝ∂𝒖∂𝒖 ∂𝒖 ∂𝒖 − ∂𝒖 ∂𝒖 ∂𝒖=⋯∂𝒖∂𝒖 ∂𝒖 − ∂𝒖 − ∂𝒖 ∂𝒖 ∂𝒖Forward
これを前から計算するのが Forward-Mode 自動微分

Forward-Mode と Reverse-Mode 自動微分

3/15

連鎖律 （多変数）
多変数も同様（但し，各 ∂𝒖 / ∂𝒖 はヤコビ行列 𝐽 = [∂𝑢 / ∂𝑢 ] <ℝ𝒖ℝ−𝒖 −⋯𝒖ℝ𝒖<）ℝ∂𝒖∂𝒖 ∂𝒖 ∂𝒖 − ∂𝒖 ∂𝒖 ∂𝒖=⋯∂𝒖∂𝒖 ∂𝒖 − ∂𝒖 − ∂𝒖 ∂𝒖 ∂𝒖ForwardReverse
これを前から計算するのが Forward-Mode 自動微分
これを後から計算するのが Reverse-Mode 自動微分
Forward-Mode と Reverse-Mode 自動微分3/15

Foward Mode 自動微分
Dual Number ℝ[𝑑]/(𝑑 ) を使って計算できる
𝑥 + 𝑦𝑑 の 𝑦 が一次微分係数を覚える役割を果す（𝑓(𝑥) + 𝑓 (𝑥)𝑑 と思う）

代数演算はそのまま延長，（区分的に）滑らかな関数についても Weil 環の標準的な 𝐶 - 環構造が入る
難しく聞こえるが，以下のような感じ：
sin(𝑥 + 𝑦𝑑) = sin(𝑥) + 𝑦 cos(𝑥)𝑑,cos(𝑥 + 𝑦𝑑) = cos(𝑥) − 𝑦 sin(𝑥)𝑑,𝑒( +)= 𝑒 + 𝑦𝑒 𝑑

Forward-Mode と Reverse-Mode 自動微分4/15

Forward Mode 計算例
次で定まる関数 𝑓 : ℝ → ℝ の 𝑥 に関する微分を求めてみよう：
𝑓(𝑥) = (sin(𝑥 + 1), 𝑒 , 𝑥 𝑒− )入口は 𝑥 + (d𝑥/d𝑥)𝑑 = 𝑥 + 𝑑 を入れて 𝑓(𝑥 + 𝑑) を評価してみる：
𝑓(𝑥 + 𝑑)= (sin((𝑥 + 𝑑) + 1), 𝑒( + ) , (𝑥 + 𝑑) 𝑒−( + ))= (sin(𝑥 + 2𝑥𝑑 + 1), 𝑒+, (𝑥 + 3𝑥 𝑑)(𝑒− − 𝑒− 𝑑))= (sin(𝑥 + 1) + 2𝑥 cos(𝑥 + 1)𝑑, 𝑒 + 2𝑥𝑒 𝑑, (𝑥 + 3𝑥 𝑑)(𝑒− − 𝑒− 𝑑))= (sin(𝑥 + 1), 𝑒 , 𝑥 𝑒 − ) + (2𝑥 cos(𝑥 + 1), 2𝑥𝑒 , −𝑥 𝑒− + 3𝑥 𝑒− )𝑑
一階微分係数

Forward-Mode と Reverse-Mode 自動微分5/15

Forward-Mode だけでいいのでは？
入力が一変数，出力が多変数の場合は Forward-Mode で十分効率的
しかし，機械学習のように 𝑓 : ℝ → ℝ で 𝑁 ≫ 0 の場合，Forward-Mode では効率がわるすぎる！
(a) 素朴にやると，ℝ[𝑑] を用意して，𝑖 < 𝑁 ごとに (0, …, 0, 𝑥 + 𝑑 , 0, …) みたいなのを何回も渡すことになる(b) これを組にして (ℝ[𝑑] ) について一挙に計算すると one-pass(c) いずれにせよ変数の数について自乗オーダーかかってしまい非効率！
d𝒙/d𝒙 = d𝒖 /d𝒖 ではなく d𝒖 /d𝒖 の側から辿ったらどうか？
これが Reverse-Mode 自動微分！

Forward-Mode と Reverse-Mode 自動微分

6/15

Reverse-Mode 自動微分いろいろ
Reverse-Mode 自動微分いろいろ

Reverse-Mode 自動微分
Reverse-Mode の概念図はこうだったℝ𝒖ℝ−𝒖 −⋯𝒖ℝ𝒖ℝd𝒖∂𝒖 ∂𝒖 ∂𝒖 − ∂𝒖 ∂𝒖 ∂𝒖=⋯d𝒖∂𝒖 ∂𝒖 − ∂𝒖 − ∂𝒖 ∂𝒖 ∂𝒖Reverse
問題：計算の入出力と逆順に辿る必要がある！
微分係数の計算には関数の値そのものが必要，往復する必要がある
機械学習で誤差逆伝播法 (back propagation) と呼ばれるもの

これを実現するためにいくつかやり方が知られている

Reverse-Mode 自動微分いろいろ

7/15

Reverse-Mode 概説 （説明は[1] を参考にした）計算グラフをつくって，最後から手繰っていく
𝑓(𝑥, 𝑦, 𝑧) = sin(𝑥 + 𝑦 )𝑒
𝑥+𝑦𝑧sin××𝑒∙𝑤

Reverse-Mode 概説 （説明は[1] を参考にした）計算グラフをつくって，最後から手繰っていく
𝑓(𝑥, 𝑦, 𝑧) = sin(𝑥 + 𝑦 )𝑒
𝑥+𝑦𝑧sin×∂𝑤=1∂𝑤×𝑒∙𝑤

Reverse-Mode 概説 （説明は[1] を参考にした）計算グラフをつくって，最後から手繰っていく
𝑓(𝑥, 𝑦, 𝑧) = sin(𝑥 + 𝑦 )𝑒𝑥+sin
1𝑦𝑧××𝑒∙∂𝑤=1∂𝑤𝑤Reverse-Mode 概説 （説明は[1] を参考にした）計算グラフをつくって，最後から手繰っていく
𝑓(𝑥, 𝑦, 𝑧) = sin(𝑥 + 𝑦 )𝑒𝑥𝑒 ⋅1+sin
1𝑦××sin(𝑥 + 𝑦 ) ⋅ 1𝑧𝑒∙∂𝑤=1∂𝑤𝑤Reverse-Mode 概説 （説明は[1] を参考にした）計算グラフをつくって，最後から手繰っていく
𝑓(𝑥, 𝑦, 𝑧) = sin(𝑥 + 𝑦 )𝑒𝑥𝑒 cos(𝑥 + 𝑦 )+𝑒 ⋅1sin
1𝑦sin(𝑥 + 𝑦 )𝑒𝑧××sin(𝑥 + 𝑦 ) ⋅ 1𝑒∙∂𝑤=1∂𝑤𝑤Reverse-Mode 概説 （説明は[1] を参考にした）計算グラフをつくって，最後から手繰っていく
𝑓(𝑥, 𝑦, 𝑧) = sin(𝑥 + 𝑦 )𝑒𝑒 ⋅ cos(𝑥 + 𝑦 )𝑥𝑒 cos(𝑥 + 𝑦 )+𝑒 ⋅1sin
1𝑦××𝑒 cos(𝑥 + 𝑦 )sin(𝑥 + 𝑦 )𝑒𝑧sin(𝑥 + 𝑦 ) ⋅ 1𝑒∙∂𝑤=1∂𝑤𝑤Reverse-Mode 概説 （説明は[1] を参考にした）計算グラフをつくって，最後から手繰っていく
𝑓(𝑥, 𝑦, 𝑧) = sin(𝑥 + 𝑦 )𝑒𝑒 ⋅ cos(𝑥 + 𝑦 )𝑥𝑒 cos(𝑥 + 𝑦 )+𝑒 ⋅1sin
1𝑦𝑒 cos(𝑥 + 𝑦 )𝑦𝑦𝑒 cos(𝑥 + 𝑦 )sin(𝑥 + 𝑦 )𝑒𝑧

××𝑒 cos(𝑥 + 𝑦 )sin(𝑥 + 𝑦 ) ⋅ 1𝑒∙

∂𝑤
=1∂𝑤𝑤

Reverse-Mode 概説 （説明は[1] を参考にした）計算グラフをつくって，最後から手繰っていく
𝑓(𝑥, 𝑦, 𝑧) = sin(𝑥 + 𝑦 )𝑒𝑒 ⋅ cos(𝑥 + 𝑦 )𝑥𝑒 cos(𝑥 + 𝑦 )+𝑒 ⋅1sin
12𝑦𝑒 cos(𝑥 + 𝑦 )𝑦××𝑒 cos(𝑥 + 𝑦 )sin(𝑥 + 𝑦 )𝑒𝑧sin(𝑥 + 𝑦 ) ⋅ 1𝑒∙

∂𝑤
=1∂𝑤𝑤

テープに記録していく
一番メジャーなやりかた（Wengert Tape や Wengert List などと呼ばれる）式が出て来た順にテープに変数や部分式を記録していく
最後までいったら先程手繰ってノードの上に書いたような係数を，受け取り先のテープに書き込む
全部終わったら適宜読み出して結果を返す
実装の正当性・気にすべき点が職人芸

Reverse-Mode 自動微分いろいろ

9/15

限定継続
限定継続：ある点から特定の点までの続きの計算を表す
ここでは shift / reset という一組のオペレータを使った定式化を使う
例： 1 + reset( 10 + shift ( \ k -> k ( k 100) + 1000 ) * 2 )shift から見て reset にブチ当るまでの続きの計算が k に束縛される．
今回の場合は k = \n -> 10 + n * 2
上式は 1 + (\k -> k (k 100)+1000) (\n -> 10 + n*2) と同値
評価を進めれば， 1 + ((10+(10+100*2)*2)+1000) = 1431 となる．

shift がネストしている場合，外側の shift は reset の役割もする．

Wang et al.[2] では限定継続による Reverse-Mode 自動微分を提案している
Reverse-Mode 自動微分いろいろ
10/15

限定継続による Reverse-Mode 自動微分の実装
アイデア：順方向の計算結果から継続を逆に辿って微分係数を伝播させる
D x dx + D y dy =shift { fun k ->z <- D (x + y) 0.0
k zdx += z.ddy += z.dreturn z}

D x dx * D y dy =shift { fun k ->z <- D (x * y) 0.0k zdx += y * z.ddy += x * z.dreturn z}

Reverse-Mode 自動微分いろいろ

11/15

限定継続による Reverse-Mode 自動微分の実装 II
微分係数を求めるところで reset を噛ませて出口の自明な微分係数を渡してやる．
grad f x = {z <- D x 0.0
reset { w <- f z; w.d = 1.0 }return z.d}Multi-Prompt 限定継続を使えば変数の操作を減らせる
やってるひとが見当たらなかったので実験中（ [3]）Reverse-Mode 自動微分いろいろ

12/15

正当性の証明「うまくいきそう」以上をどう証明するか？
Krawiec et al. [4] ではプログラム変換として捉え， プログラミング言語意味論の手法を使ってその正当性を証明している．
実数値とその有限直和・直積を含む簡単な単純型付き 𝜆- 計算の体系を定義
自動微分をその体系に対するプログラム変換として定式化
様々な計算体系の正規化定理の証明などに用いられる logical relation の論法を応用して，その正当性を示している
線型型などを使って空間・時間計算量の漸近最適性も示している

最終的にはより Wengert Tape に近い手法になるが， よりシステマティッ
クな方法で導出され，正当性がきちんと証明されている．
Reverse-Mode 自動微分いろいろ

13/15

まとめ
まとめ

まとめ
自動微分：合成関数の微分公式 （連鎖律） を使って， 関数の値とその微分係数を効率的に求める手法
Forward-Mode：入力の自明な微分係数を順方向に伝播させていって解く
Reverse-Mode：出力の自明な微分係数を逆方向に伝播させていって解く(入力次元) ≪ (出力次元) のときは Forward-Mode が効率的
(入力次元) ≫ (出力次元) のときは Reverse-Mode が効率的深層学習で誤差逆伝播法と呼ばれているものReverse-Mode は往復する必要があるので実装が複雑，複数の手法がある
本講演では目についたものについて説明した
Krawiec et al. [4] の説明が数学的にも厳密で， 実装の導出方法がわかりやす
いのでおすすめ
まとめ
14/15

参考文献
[1] 岡谷貴之 , “深層学習 ,” 改訂第 2 版 ed., ser. 機械学習プロフェッショナルシリーズ . 講談社 , January 2022,
ISBN: 978-4-06-513332-3.
[2] F. Wang et al., “Backpropagation with Continuation Callbacks: Foundations for Efficient and Expressive Differentiable Programming,” in NIPS'18: Proceedings of the 32nd International Conference on Neural Information
Processing Systems, Association for Computing Machinery. New York, NY, USA: Association for Computing
Machinery, December 2018, doi: 10.5555/3327546.3327682.
[3] Hiromi ISHII, ad-delcont-primop, URL: https://github.com/konn/ad-delcont-primop, January 2023.
[4] F. Krawiec et al., “Provably Correct, Asymptotically Efficient, Higher-Order Reverse-Mode Automatic Differentiation,” in Proceedings of the ACM on Programming Languages, Volume 6, Issue POPL, Association for Computing
Machinery. New York, NY, USA: Association for Computing Machinery, January 2022, ISBN: 9784797341379;
doi: 10.1145/3498710.