自動微分

自動微分（じどうびぶん、）やアルゴリズム微分（）とは、プログラムで定義された関数を解析し、関数の値と同時に偏導関数の値を計算するアルゴリズムである。
自動微分は複雑なプログラムであっても加減乗除などの基本的な算術演算や基本的な関数（指数関数・対数関数・三角関数など）のような基本的な演算の組み合わせで構成されていることを利用し、これらの演算に対して合成関数の偏微分の連鎖律を繰り返し適用することによって実現される。自動微分を用いることで偏導関数値を少ない計算量で自動的に求めることができる。
他の微分方式との違い.
自動微分は以下のどちらとも異なる。
記号微分は効率が悪くなりやすく、プログラムで定義された関数から微分表現を導くのは困難であるという問題がある。一方、数値微分では離散化の際の丸め誤差や桁落ちによる精度の低下が問題である。さらに、どちらの手法も計算量や誤差の関係で高次の微分係数を求めることが難しい。また、勾配を用いた最適化で必要となる、多くの入力変数を持つ関数に対する偏微分値の計算を行うには速度が遅い。自動微分はこれらの古典的手法の問題を解決する。
また、自動微分は計算フローを追いかけることで計算できるので、分岐（if文）やループや再帰を含むようなアルゴリズムでも偏微分できる。
自動微分の導出.
合成関数の偏微分の連鎖律.
自動微分の基本原理は、合成関数の偏微分の連鎖律を用いた偏微分の分解である。
合成関数の偏微分の連鎖律とは formula_1 の時、下記が成立することである。
2種類の自動微分.
自動微分は2種類に分けられ、それぞれ
と呼ばれる。
ボトムアップ型自動微分では連鎖律を内側から外側に計算し（を計算した後で を計算する）、トップダウン型自動微分では外側から内側に計算する。
使い分けは、入力が n 次元、出力が m 次元とした場合、以下の違いがある。
機械学習において、評価値はほぼ常に m = 1 の実数なので、トップダウン型が使われる。機械学習で用いられる多層パーセプトロンのバックプロパゲーションはトップダウン型自動微分の特殊なケースである。
ボトムアップ型はR.E. Wengertが1964年に発表したが、2ページの論文で特に名前を付けていない。Andreas Griewank によると、トップダウン型を誰が最初に発明したのか判然としないが、計算量を減らす工夫として1960年代後半には提案されていた。
ボトムアップ型自動微分.
ボトムアップ型自動微分では最初に偏微分を行う入力変数を固定し、それぞれの部分式を再帰的に計算する。手計算においては連鎖律において内側の関数を繰り返し置き換えていくことに相当する。
多変数の場合はヤコビ行列の積として一般化できる。
トップダウン型自動微分と比較すると、ボトムアップ型自動微分は自然であり、偏微分に関する情報の流れが計算の順序と一致するため簡単に実行できる。それぞれの変数にその偏導関数値 formula_4
の計算値を保存する領域を付け加えるだけで、変数値の計算と同時に偏導関数値を計算することができる。
連鎖律より、formula_6 が計算グラフで先行ノードを持つ場合、
例として次の関数を考える。
それぞれの部分式を中間変数 formula_6 としてラベル付けした。最初に formula_10 としている。
どの入力変数で偏微分するかによって formula_11 や formula_12 の初期値が異なる。formula_13 に関する偏微分を計算する場合の初期値は、
となる。初期値が決まったら下の表に示す連鎖律に従って各偏導関数値を順に計算していく。図2はこの処理を計算グラフとして表している。formula_15 が求めたい値である。
この関数 f に対する勾配を求めるためには formula_17 だけではなく formula_18 も求める必要がある。そのため、初期値を formula_19 とした同様の計算を追加で行わなければならない。
勾配を求める場合に必要なボトムアップ型自動微分の実行回数は入力変数の個数と等しく、トップダウン型自動微分では出力変数の個数に等しい。ボトムアップ型やトップダウン型の自動微分を1回行うのに必要な計算量は、元のプログラムの計算量に比例する。そのため、偏微分する関数 が を満たす場合、ボトムアップ型自動微分はトップダウン型自動微分よりも効率的である。
トップダウン型自動微分.
トップダウン型自動微分では、はじめに偏微分される出力変数を固定して、それぞれの部分式に関する偏導関数値を再帰的に計算する。手計算においては部分式を連鎖律における外側の関数の偏微分で繰り返し置き換えていくことに相当する。
トップダウン型自動微分において、求める値はボトムアップ型の随伴であり、上線 formula_21 で表す。これは中間変数 formula_6 に関する偏微分
である。連鎖律より、formula_6 が計算グラフで後続ノードを持つ場合、
トップダウン型自動微分は連鎖律を外側から内側（図3の計算グラフでは上から下）にたどっていく。
偏微分する関数 が を満たすとき、トップダウン型自動微分はボトムアップ型自動微分よりも効率的である。例示した関数は m = 1 のスカラー値関数（1つだけ値を返す関数）なので、勾配を計算するには計算グラフを一度たどるだけでよい。これは n = 2回計算グラフをたどる必要があったボトムアップ型自動微分の計算量の半分である。
しかし、トップダウン型自動微分は、テープやWengert リスト（なお、Wengert はボトムアップ型を1964年に発表したが、トップダウン型を発表したわけではない）と呼ばれるサイズ変更が可能な配列に中間変数 formula_6 の計算結果を追記していく必要があるためメモリ使用量の点で不利であり、計算グラフが巨大になるとメモリ使用量が問題となる可能性がある。この問題は保存する中間変数を限定し、必要な中間変数を再計算することによって軽減される。
トップダウン型自動微分を用いて偏導関数値を計算するための演算は以下の通りである（関数値を求める時と順番が逆であることに注意）。formula_27 と formula_28 が求めたい値である。
最後の formula_30 は以下の理由で成立する。図3で formula_31 から formula_32 と formula_33 に矢印が引かれていることより、formula_32 と formula_33 は formula_36 の後続ノードである。合成関数の偏微分の連鎖律より formula_37 であり、後は formula_32 と formula_33 の定義を代入すれば良い。どの中間変数がどの中間変数に影響を及ぼすか記録する必要がある。
テープを使用しない場合は、以下のように Python で実装できる。
import math
class Var:
 def __init__(self, value, children=None):
 self.value = value
 self.children = children or []
 self.grad = 0
 def __add__(self, other):
 return Var(self.value + other.value, [(1, self), (1, other)])
 def __mul__(self, other):
 return Var(self.value * other.value, [(other.value, self), (self.value, other)])
 def sin(self):
 return Var(math.sin(self.value), [(math.cos(self.value), self)])
 def calc_grad(self, grad=1):
 self.grad += grad
 for coef, child in self.children:
 child.calc_grad(grad * coef)
x = Var(2)
y = Var(3)
f = x * y + x.sin()
f.calc_grad()
print("f =", f.value)
print("∂f/∂x =", x.grad)
print("∂f/∂y =", y.grad)
テープを使用する場合のアルゴリズムの実装の流れは以下の通りである。
スカラー値ではなく NumPy のような多次元配列（テンソル）を扱う場合も処理すべき内容は同じである。formula_52 を1つの処理単位として実装する。これを vector-Jacobian product (VJP) や L-operator (Lop) と言う。行列積の VJP は行列積で実装できる。ただし、ある軸での和（NumPyのsum）の VJP は、その軸で値を繰り返して formula_53 の軸を復元する処理になるなど、直観的で無い物もある。ハーバード大学の HIPS が開発していた Autograd は、ほぼ全ての NumPy の関数の VJP を実装していて、簡潔に実装しているので参考になる。なお formula_54 は Jacobian-vector product (JVP) や R-operator (Rop) と言い、ボトムアップ型で使用する。
二重数を用いた自動微分.
ボトムアップ型自動微分は実数の代数に（元を）添加して新しい算術を導入することによって可能である。全ての数（通常の実数）に対して、その数における関数の微分を表現する追加の成分が足され、全ての算術演算がこの添加代数に拡張される。すなわち二重数の代数である。このアプローチはの理論（つまり双対空間のテンソル代数）によって一般化される（を見よ)。
各数 formula_55 を数 formula_56 に置き換える。ここで formula_57 は実数だが、formula_58 は formula_59 を満たすである（無限小；滑らかな無限小解析も参照）。ちょうどこれだけを用いて通常の演算が得られる：
引き算と割り算についても同様である。
いまやこの拡張算術のもとで多項式を計算できる。もし formula_61 ならば、
formula_62
ここで formula_63 は formula_64 の最初の引数に対する微分であり、formula_57（種と呼ばれる）は任意に取れる。
上に述べたように、この新しい算術は、順序対（formula_66 と書かれる元）と、最初の成分に対しては通常の算術を、第二の成分に対しては一階微分の算術を、それぞれ与えたものからなる。多項式に関する上の結果を解析関数に広げれば、新しい算術に対する、基本的な算術と幾つかの標準的な関数のリストが得られる：
一般に、プリミティヴの関数 formula_68 に対して、
ここで formula_70 と formula_71 はそれぞれ formula_68 の最初と2番目の引数に対する微分である。
基本的な二項算術演算を（実数と二重数の）混在した引数に対して、つまり順序対 formula_73 と実数 formula_74 に対して適用するとき、まずこの実数を formula_75 に引き上げる（lifting）。関数 formula_76 の formula_77 に於ける微分はいまや formula_78 に上の算術を使って計算することによって得られる。これは formula_79 を結果として与える。
ベクトル引数と関数.
多変数関数は、方向微分作用素を用いることで、一変数関数の場合と同様の効率と仕組みで取り扱える。つまり、formula_80 の formula_81 における formula_82 方向微分 formula_83 を計算したい場合、それは formula_84 を上と同様の算術を使って計算すればよい。もし formula_85 の全ての要素が望みならば、formula_86 個の関数評価が要求される。ここで、多くの最適化アプリケーションでは、実際には方向微分があれば十分である。
高階・多変数.
上の算術は多変数関数の二階やもっと高階の微分の計算の為に一般化出来る。しかし、その算術規則は直ちに極めて複雑なものとなる：複雑性は最高次の微分の次数に対して二次関数的となる。その代わりに、途中で打ち切った（truncated）テイラー多項式の代数を使用できる。結果得られる算術（一般化された二重数の上で定義された）は、関数を新しいデータ型であるかのように使って、効率的に計算することを可能にする。ひとたび関数のテイラー多項式が分かれば、その導関数たちは容易に抽出できる。
厳密で一般的な定式化はを通してを用いることにより達成される。
実装.
自動微分の実装方法には大きく分けて、ソースコードの変換とオペレータオーバーローディングによる方法の2つがある。
ソースコード変換.
関数値を求める関数を記述した元のソースコードから、偏導関数値を計算する処理を含んだプログラムを自動的に生成する手法である。ソースコード変換はあらゆるプログラミング言語で実装でき、コンパイル時の最適化を行いやすいが、自動微分ツールの作成は難しい。
オペレータオーバーローディング.
この手法は演算子のオーバーロードがサポートされているプログラミング言語で記述されたソースコードに対してのみ適用可能である。元のソースコードの流れを大きく変更することなく実現できるが、基本データ型の変更などの小さな変更は必要である。
ボトムアップ型自動微分をオペレータオーバーロードで実現するのは容易である。トップダウン型自動微分についても可能であるが、現状のコンパイラではボトムアップ型自動微分と比べると最適化の面で不利である。
ソフトウェア.
自動微分を実装したライブラリなどのソフトウェアが多数存在する。2010年代の第3次人工知能ブームの際にディープラーニングに自動微分が必要なため、TensorFlowやPyTorchなどトップダウン型の自動微分を含むライブラリが多数作られた。