自動微分のソースを表示

'''自動微分'''（じどうびぶん、{{lang-en-short|automatic differentiation, autodiff, AD}}）や'''アルゴリズム微分'''（{{lang-en-short|algorithmic differentiation}}）とは、[[プログラム (コンピュータ)|プログラム]]で[[定義]]された[[関数 (数学)|関数]]を[[解析]]し、関数の値と同時に[[偏導関数]]の値を計算する[[アルゴリズム]]である。

自動微分は複雑なプログラムであっても加減乗除などの基本的な算術演算や基本的な関数（[[指数関数]]・[[対数関数]]・[[三角関数]]など）のような基本的な演算の組み合わせで構成されていることを利用し、これらの演算に対して合成関数の偏微分の[[連鎖律]]を繰り返し適用することによって実現される。自動微分を用いることで偏導関数値を少ない計算量で自動的に求めることができる。

== 他の微分方式との違い ==
[[Image:AutomaticDifferentiationNutshell.png|right|thumb|300px|図1: 自動微分と記号微分の関係]]
自動微分は以下のどちらとも異なる。
* [[記号微分]]・[[数式微分]]（[[:en:symbolic differentiation|symbolic differentiation]]） - 原関数を表す数式から[[数式処理]]により導関数を導出する。数式処理システムで実装されている。
* [[数値微分]]（[[:en:numerical differentiation|numerical differentiation]]） - 原関数の値から数値的に微分係数を算出する

記号微分は効率が悪くなりやすく、プログラムで定義された関数から微分表現を導くのは困難であるという問題がある。一方、数値微分では離散化の際の[[丸め誤差]]や桁落ちによる精度の低下が問題である。さらに、どちらの手法も計算量や誤差の関係で高次の微分係数を求めることが難しい。また、勾配を用いた最適化で必要となる、多くの入力変数を持つ関数に対する偏微分値の計算を行うには速度が遅い。自動微分はこれらの古典的手法の問題を解決する。<ref name="jmlr17-468">[https://jmlr.org/papers/v18/17-468.html Automatic Differentiation in Machine Learning: a Survey]</ref>

また、自動微分は計算フローを追いかけることで計算できるので、分岐（if文）やループや再帰を含むようなアルゴリズムでも偏微分できる<ref name="jmlr17-468"/>。

== 合成関数の偏微分の連鎖律 ==
自動微分の基本原理は、合成関数の[[偏微分]]の[[連鎖律]]を用いた偏微分の分解である。

合成関数の偏微分の連鎖律とは <math>y = f(w_1, w_2), w_1 = g(x_1, x_2), w_2 = h(x_1, x_2)</math> の時、下記が成立することである<ref>[https://manabitimes.jp/math/1303 連鎖律（多変数関数の合成関数の微分） | 高校数学の美しい物語]</ref><ref>[https://mathlandscape.com/partial-derivative-composite/ 合成関数の偏微分における連鎖律(チェインルール)とその証明 | 数学の景色]</ref>。
:<math>
\frac{\partial y}{\partial x_1} = \frac{\partial y}{\partial w_1} \frac{\partial w_1}{\partial x_1} + \frac{\partial y}{\partial w_2} \frac{\partial w_2}{\partial x_1}
</math>

== 2種類の自動微分 ==
自動微分は2種類に分けられ、それぞれ
* '''ボトムアップ型自動微分'''（'''フォーワード・モード'''、'''フォーワード・アキュムレーション'''、'''タンジェント・モード'''、'''狭義の自動微分'''）
* '''トップダウン型自動微分'''（'''リバース・モード'''、'''リバース・アキュムレーション'''、'''随伴モード'''、'''高速自動微分'''）
と呼ばれる。

ボトムアップ型自動微分では連鎖律を内側から外側に計算し（{{math|''∂w''/''∂x''}}を計算した後で {{math|''∂y''/''∂w''}} を計算する）、トップダウン型自動微分では外側から内側に計算する。

使い分けは、入力が n 次元、出力が m 次元とした場合、以下の違いがある。
* n < m ならばボトムアップ型の方が計算量が少ない。ボトムアップ型の計算回数はn回。
* n > m ならばトップダウン型の方が計算量が少ない。トップダウン型の計算回数はm回。
[[機械学習]]において、評価値はほぼ常に m = 1 の実数なので、トップダウン型が使われる。機械学習で用いられる[[多層パーセプトロン]]の[[バックプロパゲーション]]はトップダウン型自動微分の特殊なケースである。

ボトムアップ型はR.E. Wengertが1964年に発表したが、2ページの論文で特に名前を付けていない<ref name="wengert1964"/>。Andreas Griewank によると、トップダウン型を誰が最初に発明したのか判然としないが、計算量を減らす工夫として1960年代後半には提案されていた<ref>{{Cite journal 
| author = Andreas Griewank
| year = 2012
| title = Who Invented the Reverse Mode of Differentiation
| url=https://www.math.uni-bielefeld.de/documenta/vol-ismp/52_griewank-andreas-b.pdf
| journal=Optimization Stories, Documenta Matematica 
| volume=Extra Volume ISMP 
| pages=389–400
}}</ref>。

== ボトムアップ型自動微分 ==
ボトムアップ型自動微分では最初に偏微分を行う入力変数を固定し、それぞれの部分式を再帰的に計算する。手計算においては連鎖律において内側の関数を繰り返し置き換えていくことに相当する。

:<math>\frac{\partial y}{\partial x}
= \frac{\partial y}{\partial w_1} \frac{\partial w_1}{\partial x}
= \frac{\partial y}{\partial w_1} \left(\frac{\partial w_1}{\partial w_2} \frac{\partial w_2}{\partial x}\right)
= \frac{\partial y}{\partial w_1} \left(\frac{\partial w_1}{\partial w_2} \left(\frac{\partial w_2}{\partial w_3} \frac{\partial w_3}{\partial x}\right)\right)
= \cdots</math>

多変数の場合は[[ヤコビ行列]]の積として一般化できる。

トップダウン型自動微分と比較すると、ボトムアップ型自動微分は自然であり、偏微分に関する情報の流れが計算の順序と一致するため簡単に実行できる。それぞれの変数にその偏導関数値 <math>\dot w_i</math>

:<math>\dot w_i = \frac{\partial w_i}{\partial x}</math>

の計算値を保存する領域を付け加えるだけで、変数値の計算と同時に偏導関数値を計算することができる。

連鎖律より、<math>w_i</math> が計算グラフで先行ノードを持つ場合、
:<math>\dot w_i = \sum_j \frac{\partial w_i}{\partial w_j} \dot w_j</math>, j ∈ {i の先行ノード}

[[Image:ForwardAccumulationAutomaticDifferentiation.png|right|thumb|300px|図2: ボトムアップ型自動微分の計算グラフの例]]

例として次の関数を考える。
:<math>\begin{align}
y
&= f(x_1, x_2) \\
&= x_1 x_2 + \sin x_1 \\
&= w_1 w_2 + \sin w_1 \\
&= w_3 + w_4 \\
&= w_5
\end{align}</math>

それぞれの部分式を中間変数 <math>w_i</math> としてラベル付けした。最初に <math>w_1 = x_1, w_2 = x_2</math> としている。

どの入力変数で偏微分するかによって <math>\dot w_1</math> や <math>\dot w_2</math> の初期値が異なる。<math>x_1</math> に関する偏微分を計算する場合の初期値は、

: <math>\begin{align}
\dot w_1 = \frac{\partial w_1}{\partial x_1} = \frac{\partial x_1}{\partial x_1} = 1 \\
\dot w_2 = \frac{\partial w_2}{\partial x_1} = \frac{\partial x_2}{\partial x_1} = 0
\end{align}</math>

となる。初期値が決まったら下の表に示す連鎖律に従って各偏導関数値を順に計算していく。図2はこの処理を計算グラフとして表している。<math>\dot w_5 = \tfrac{\partial y}{\partial x_1}</math> が求めたい値である。

:<math>\begin{array}{l|l}
\text{Operations to compute value} &
\text{Operations to compute derivative}
\\
\hline
w_1 = x_1 &
\dot w_1 = 1 \text{ (seed)}
\\
w_2 = x_2 &
\dot w_2 = 0 \text{ (seed)}
\\
w_3 = w_1 \cdot w_2 &
\dot w_3 = w_2 \cdot \dot w_1 + w_1 \cdot \dot w_2
\\
w_4 = \sin w_1 &
\dot w_4 = \cos w_1 \cdot \dot w_1
\\
w_5 = w_3 + w_4 &
\dot w_5 = 1 \cdot \dot w_3 + 1 \cdot \dot w_4
\end{array}</math>

この関数 f に対する[[勾配 (ベクトル解析)|勾配]]を求めるためには <math>\tfrac{\partial y}{\partial x_1}</math> だけではなく <math>\tfrac{\partial y}{\partial x_2}</math> も求める必要がある。そのため、初期値を <math>\dot w_1 = 0; \dot w_2 = 1</math> とした同様の計算を追加で行わなければならない。

勾配を求める場合に必要なボトムアップ型自動微分の実行回数は入力変数の個数と等しく、トップダウン型自動微分では出力変数の個数に等しい。ボトムアップ型やトップダウン型の自動微分を1回行うのに必要な計算量は、元のプログラムの計算量に比例する。そのため、偏微分する関数{{math|''f'' : ℝ<sup>''n''</sup> → ℝ<sup>''m''</sup>}} が {{math|''n'' ≪ ''m''}} を満たす場合、ボトムアップ型自動微分はトップダウン型自動微分よりも効率的である。

== トップダウン型自動微分 ==
トップダウン型自動微分では、はじめに偏微分される出力変数を固定して、それぞれの部分式に関する偏導関数値を再帰的に計算する。手計算においては部分式を連鎖律における外側の関数の偏微分で繰り返し置き換えていくことに相当する。

:<math>\frac{\partial y}{\partial x}
= \frac{\partial y}{\partial w_1} \frac{\partial w_1}{\partial x}
= \left(\frac{\partial y}{\partial w_2} \frac{\partial w_2}{\partial w_1}\right) \frac{\partial w_1}{\partial x}
= \left(\left(\frac{\partial y}{\partial w_3} \frac{\partial w_3}{\partial w_2}\right) \frac{\partial w_2}{\partial w_1}\right) \frac{\partial w_1}{\partial x}
= \cdots</math>

トップダウン型自動微分において、求める値はボトムアップ型の[[随伴]]{{訳語疑問点|date=2016年3月}}であり、上線 <math>\bar w_i</math> で表す。これは中間変数 <math>w_i</math> に関する偏微分
:<math>\bar w_i = \frac{\partial y}{\partial w_i}</math>
である。連鎖律より、<math>w_i</math> が計算グラフで後続ノードを持つ場合、以下のように計算できる。<math>\bar y</math> は1で、y以外のノードで後続ノードがなければ0になる。
:<math>\bar w_i = \sum_j \bar w_j \frac{\partial w_j}{\partial w_i}</math>, j ∈ {i の後続ノード}

<!--
原文は
In reverse accumulation, the quantity of interest is the ''adjoint'', denoted with a bar ({{math|''w̄''}}); it is a derivative of a chosen dependent variable with respect to a subexpression {{math|''w''}}:
-->
トップダウン型自動微分は連鎖律を外側から内側（図3の計算グラフでは上から下）にたどっていく。

偏微分する関数{{math|''f'' : ℝ<sup>''n''</sup> → ℝ<sup>''m''</sup>}} が {{math|''n'' ≫ ''m''}}を満たすとき、トップダウン型自動微分はボトムアップ型自動微分よりも効率的である。例示した関数は m = 1 のスカラー値関数（1つだけ値を返す関数）なので、勾配を計算するには計算グラフを一度たどるだけでよい。これは n = 2回計算グラフをたどる必要があったボトムアップ型自動微分の計算量の半分である。

しかし、トップダウン型自動微分は、テープやWengert リスト<ref>{{cite journal
|last=Bartholomew-Biggs
|first=Michael
|last2=Brown
|first2=Steven
|last3=Christianson
|first3=Bruce
|last4=Dixon
|first4=Laurence
|date=2000
|title=Automatic differentiation of algorithms
|url=https://www.sciencedirect.com/science/article/pii/S0377042700004222
|journal=Journal of Computational and Applied Mathematics
|volume=124
|issue=1-2
|pages=171-190
|doi=10.1016/S0377-0427(00)00422-2
}}</ref>（なお、Wengert はボトムアップ型を1964年に発表したが<ref name="wengert1964">{{cite journal
|author=R.E. Wengert
|title=A simple automatic derivative evaluation program
|journal=Comm. ACM
|volume=7
|year=1964
|pages=463–464
|doi=10.1145/355586.364791
|url=https://dl.acm.org/doi/10.1145/355586.364791
}}</ref>、トップダウン型を発表したわけではない）と呼ばれるサイズ変更が可能な配列に中間変数 <math>w_i</math> の計算結果を追記していく必要があるためメモリ使用量の点で不利であり、計算グラフが巨大になるとメモリ使用量が問題となる可能性がある。この問題は保存する中間変数を限定し、必要な中間変数を再計算することによって軽減される。

[[Image:ReverseaccumulationAD.png|right|thumb|300px|図3: トップダウン型自動微分の計算グラフの例]]

トップダウン型自動微分を用いて偏導関数値を計算するための演算は以下の通りである（関数値を求める時と順番が逆であることに注意）。<math>\bar w_1 = \tfrac{\partial y}{\partial x_1}</math> と <math>\bar w_2 = \tfrac{\partial y}{\partial x_2}</math> が求めたい値である。
:<math>\begin{array}{l}
\text{Operations to compute derivative}
\\ \hline
\bar w_5 = 1 \text{ (seed)}
\\
\bar w_4 = \bar w_5 \cdot 1
\\
\bar w_3 = \bar w_5 \cdot 1
\\
\bar w_2 = \bar w_3 \cdot w_1
\\
\bar w_1 = \bar w_3 \cdot w_2 + \bar w_4 \cdot \cos w_1
\end{array}
</math>

最後の <math>\bar{w_1}</math> は以下の理由で成立する。図3で <math>x_1 = w_1</math> から <math>w_3</math> と <math>w_4</math> に矢印が引かれていることより、<math>w_3</math> と <math>w_4</math> は <math>w_1</math> の後続ノードである。合成関数の偏微分の連鎖律より <math>
\bar{w_1} = \bar{w_3} \frac{\partial w_3}{\partial w_1} + \bar{w_4} \frac{\partial w_4}{\partial w_1}
</math> であり、後は <math>w_3</math> と <math>w_4</math> の定義を代入すれば良い。どの中間変数がどの中間変数に影響を及ぼすか記録する必要がある。

=== テープを使用しない場合 ===
テープを使用しない場合は、以下のように [[Python]] で実装できる。
<syntaxhighlight lang="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)

# 例: f(x, y) = x * y + sin(x)
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)
</syntaxhighlight>

=== テープを使用する場合 ===
テープを使用する場合のアルゴリズムの実装の流れは以下の通りである。
# テープをサイズ変更が可能な[[動的配列]]として用意する。テープの要素は中間変数 <math>w_i</math> 毎に作り、以下の5項目を記録する。
## 計算内容（足し算や掛け算など）
## 計算グラフの入辺：計算に使用した引数のテープ上のインデックスのリスト。<math>w_3</math> なら <math>w_1</math> と <math>w_2</math>。
## 計算グラフの出辺：この中間変数がどの計算で使われたかのテープ上のインデックスのリスト。計算しながら追記していく。<math>w_1</math> なら <math>w_3</math> と <math>w_4</math>。
## <math>w_i</math> の値
## <math>\bar w_i</math> の値（最初は未定）
# <math>w_i</math> の値を計算していく。その際、上記の内容をテープに追記していく。また、テープには、どの中間変数の計算で、どの中間変数を使用したかも追記する（上記の3番）。同一の中間変数を2回以上計算しないように注意が必要。
# テープの最後の <math>\bar w_i</math> を 1 として、その1つ前から逆順に <math>\bar w_i = \sum_j \bar w_j \frac{\partial w_j}{\partial w_i}</math> を計算していく。

=== 多次元配列（テンソル）の場合 ===
スカラー値ではなく [[NumPy]] のような多次元配列（テンソル）を扱う場合も処理すべき内容は同じである。<math>\bar w_j \tfrac{\partial w_j}{\partial w_i}</math> を1つの処理単位として実装する。これを vector-Jacobian product (VJP) や L-operator (Lop) と言う<ref>[https://github.com/HIPS/autograd/blob/master/docs/tutorial.md autograd/tutorial.md at master · HIPS/autograd]</ref><ref>[https://theano-pymc.readthedocs.io/en/latest/tutorial/gradients.html Derivatives in Theano — Theano 1.1.2+29.g8b2825658.dirty documentation]</ref><ref>[https://arxiv.org/abs/2104.00219 2104.00219 Fast Jacobian-Vector Product for Deep Networks]</ref><ref>{{Cite journal |last=Pearlmutter |first=Barak A. |date=1994-01-01 |title=Fast Exact Multiplication by the Hessian |url= |journal=Neural Computation |publisher= |volume=6 |issue=1 |pages=147-160 |doi=10.1162/neco.1994.6.1.147 |accessdate=2023-03-07}}</ref>。[[行列の乗法|行列積]]の VJP は行列積で実装できる。ただし、ある軸での和（NumPyのsum）の VJP は、その軸で値を繰り返して <math>\bar w_j</math> の軸を復元する処理になるなど、直観的で無い物もある。[[ハーバード大学]]の HIPS が開発していた Autograd<ref>[https://github.com/HIPS/autograd HIPS/autograd: Efficiently computes derivatives of numpy code.]</ref> は、ほぼ全ての NumPy の関数の VJP を実装していて、簡潔に実装しているので参考になる。なお <math>\tfrac{\partial w_i}{\partial w_j} \dot w_j</math> は Jacobian-vector product (JVP) や R-operator (Rop) と言い、ボトムアップ型で使用する。

==== 行列積 ====
行列積の vector-Jacobian product (VJP) は、以下のように求める。<math>Z = XY</math> を考え、<math>\bar{X}</math> を求める。行列積を行列の要素で表記する。
: <math>z_{ik} = \sum_j x_{ij} y_{jk}</math>
行列積はかけ算して足し算をするが、足し算のトップダウン型自動微分は <math>\bar{z}</math> を上から降ろし、かけ算の自動微分は相手側の項を <math>\bar{z}</math> とかけるということより、<math>\bar{x}_{ij}</math> が求まる。
: <math>\bar{x}_{ij} = \sum_k \bar{z}_{ik} y_{jk}</math>
これを要素表記から行列表記に直すと、[[転置行列]]との行列積になる。
: <math>\bar{X} = \bar{Z} Y^T</math>
同様に、<math>\bar{y}_{jk} = \sum_i x_{ij} \bar{z}_{ik}</math> より <math>\bar{Y} = X^T \bar{Z}</math> である。

==== 2次元畳み込み ====
[[畳み込みニューラルネットワーク]]のバイアス項無しの2次元畳み込み（Conv2d<ref>{{Cite web |title=Conv2d — PyTorch 2.3 documentation |author= |work=pytorch.org |date= |access-date=2 July 2024 |url= https://pytorch.org/docs/stable/generated/torch.nn.Conv2d.html}}</ref>）は、Hは縦、Wは横、Cはチャンネルとして、入力を <math>\mathbf{X}(H_\text{in},W_\text{in},C_\text{in})</math>、カーネルを <math>\mathbf{K}(H_\text{kernel},W_\text{kernel},C_\text{in},C_\text{out})</math>、出力を <math>\mathbf{Y}(H_\text{out},W_\text{out},C_\text{out})</math> とした場合、要素表記で下記式で表される。
: <math>\mathbf{Y}(i,j,n) = \sum_{k,l,m} \mathbf{K}(k,l,m,n) \mathbf{X}(i+k,j+l,m)</math>
行列積と同じくこれも積和演算なので、<math>\bar{\mathbf{K}}</math> は下記となる。
: <math>\bar{\mathbf{K}}(k,l,m,n) = \sum_{i,j} \bar{\mathbf{Y}}(i,j,n) \mathbf{X}(i+k,j+l,m)</math>
<math>\bar{\mathbf{X}}</math> は擬似コードを使い、<math>\bar{\mathbf{X}}=0</math> から始めて、下記の6重ループで計算できる。
 '''for''' <math>i,j,k,l,m,n</math> '''in''' それぞれの値域
     <math>\bar{\mathbf{X}}(i+k,j+l,m)</math> += <math>\mathbf{K}(k,l,m,n) \bar{\mathbf{Y}}(i,j,n)</math>
数式で書くと <math>\bar{\mathbf{X}}(p,q,m) = \sum_{i,j,k,l,n}\mathbf{K}(k,l,m,n)\bar{\mathbf{Y}}(i,j,n), \text{ where } i+k=p \land j+l=q</math> となる。

バイアス項 <math>\mathbf{B}</math> は <math>\mathbf{Y}(i,j,k) = \mathbf{X}(i,j,k) + \mathbf{B}(k)</math> であるが、<math>\bar{\mathbf{X}}(i,j,k) = \bar{\mathbf{Y}}(i,j,k)</math> と <math>\bar{\mathbf{B}}(k) = \sum_{i,j}\bar{\mathbf{Y}}(i,j,k)</math> となる。

==== 2次元最大値プーリング ====
[[畳み込みニューラルネットワーク]]のカーネルの大きさが(p,q)の2次元最大値プーリング（MaxPool2d<ref>{{Cite web |title=MaxPool2d — PyTorch 2.3 documentation |author= |work=pytorch.org |date= |access-date=6 July 2024 |url= https://pytorch.org/docs/stable/generated/torch.nn.MaxPool2d.html}}</ref>）は要素表記では下記となるが、
: <math>\mathbf{Y}(i,j,m) = \max_{k,l} \mathbf{X}(pi+k,qj+l,m)</math>
これの <math>\bar{\mathbf{X}}</math> は、最大値をとる所に <math>\bar{\mathbf{Y}}</math> を戻せば良いので下記となる。argmax が複数の k, l で最大となる場合は1つ選ぶ。
: <math>\bar{\mathbf{X}}(pi+k,qj+l,m) = \begin{cases}
\bar{\mathbf{Y}}(i,j,m) & \text{if }(k,l) = \mathop{\rm argmax}\limits_{k,l} \mathbf{X}(pi+k,qj+l,m) \\
0 & \text{otherwise}
\end{cases}</math>

==== ReLU ====
畳み込みニューラルネットワークの[[活性化関数]]の [[ReLU]] は要素表記では <math>\mathbf{Y}(i,j,k) = \max \{ 0, \mathbf{X}(i,j,k) \}</math> だが、これの <math>\bar{\mathbf{X}}</math> は、<math>\mathbf{X} \ge 0</math> の所に <math>\bar{\mathbf{Y}}</math> を戻せば良いので下記となる。
: <math>\bar{\mathbf{X}}(i,j,k) = \begin{cases}
\bar{\mathbf{Y}}(i,j,k) & \text{if }\mathbf{X}(i,j,k) \ge 0 \\
0 & \text{otherwise}
\end{cases}</math>

<!--
一段落削除
The data flow graph of a computation can be manipulated to calculate the gradient of its original calculation. This is done by adding an adjoint node for each primal node, connected by adjoint edges which parallel the primal edges but flow in the opposite direction. The nodes in the adjoint graph represent multiplication by the derivatives of the functions calculated by the nodes in the primal. For instance, addition in the primal causes fanout in the adjoint; fanout in the primal causes addition in the adjoint; a [[unary operation|unary]] function {{math|''y'' {{=}} ''f''(''x'')}} in the primal causes {{math|''x̄'' {{=}} ''ȳ'' ''f′''(''x'')}} in the adjoint; etc.
-->
<!--
節ごと削除
=== Beyond forward and reverse accumulation ===
-->
== 二重数を用いた自動微分 ==
ボトムアップ型自動微分は[[実数]]の[[代数]]に（元を）添加して新しい[[算術]]<!-- 訳注：拡張された数概念としての代数系を算術 arithmetic と表現しているものと思われる。-->を導入することによって可能である。全ての数（通常の実数）に対して、その数における関数の微分を表現する追加の成分が足され、全ての算術演算がこの添加代数に拡張される。すなわち[[二重数]]の代数である。このアプローチは{{仮リンク|プログラミング空間上の演算子法|en|Automatic differentiation#Operational calculus on programming spaces}}の理論（つまり[[双対空間]]の[[テンソル代数]]）によって一般化される（{{仮リンク|解析的プログラミング空間|en|Automatic differentiation#Analytic programming space}}を見よ)。

各数 <math>x</math> を数 <math>x + x'\varepsilon</math> に置き換える。ここで <math>x'</math> は実数だが、<math>\varepsilon</math> は <math>\varepsilon^2=0</math> を満たす{{仮リンク|抽象的数|en|abstract number}}である（[[無限小]]；[[滑らかな無限小解析]]も参照）。ちょうどこれだけを用いて通常の演算が得られる：
:<math>\begin{align}
      (x + x'\varepsilon) + (y + y'\varepsilon) &= x + y + (x' + y')\varepsilon \\
  (x + x'\varepsilon) \cdot (y + y'\varepsilon) &= xy + xy'\varepsilon + yx'\varepsilon + x'y'\varepsilon^2 = xy + (x y' + yx')\varepsilon
\end{align}</math>

引き算と割り算についても同様である。

いまやこの拡張算術のもとで[[多項式]]を計算できる。もし <math>P(x) = p_0 + p_1 x + p_2x^2 + \cdots + p_n x^n</math> ならば、

<math>\begin{align}
  P(x + x'\varepsilon) &= p_0 + p_1(x + x'\varepsilon) + \cdots + p_n (x + x'\varepsilon)^n \\
                       &= p_0 + p_1 x + \cdots + p_n x^n + p_1x'\varepsilon + 2p_2xx'\varepsilon + \cdots + np_n x^{n-1} x'\varepsilon \\
                       &= P(x) + P^{(1)}(x)x'\varepsilon
\end{align}</math>

ここで <math>P^{(1)}</math> は <math>P</math> の最初の引数に対する微分であり、<math>x'</math>（種と呼ばれる）は任意に取れる。

上に述べたように、この新しい算術は、[[順序対]]（<math>\langle x, x' \rangle</math> と書かれる元）と、最初の成分に対しては通常の算術を、第二の成分に対しては一階微分の算術を、それぞれ与えたものからなる。多項式に関する上の結果を[[解析関数]]に広げれば、新しい算術に対する、基本的な算術と幾つかの標準的な関数のリストが得られる：
:<math>\begin{align}
  \left\langle u,u'\right\rangle + \left\langle v,v'\right\rangle &= \left\langle u + v, u' + v' \right\rangle \\
  \left\langle u,u'\right\rangle - \left\langle v,v'\right\rangle &= \left\langle u - v, u' - v' \right\rangle \\
  \left\langle u,u'\right\rangle * \left\langle v,v'\right\rangle &= \left\langle u v, u'v + uv' \right\rangle \\
  \left\langle u,u'\right\rangle / \left\langle v,v'\right\rangle &= \left\langle \frac{u}{v}, \frac{u'v - uv'}{v^2} \right\rangle \quad ( v\ne 0) \\
                               \sin\left\langle u,u'\right\rangle &= \left\langle \sin(u) , u' \cos(u) \right\rangle \\
                               \cos\left\langle u,u'\right\rangle &= \left\langle \cos(u) , -u' \sin(u) \right\rangle \\
                               \exp\left\langle u,u'\right\rangle &= \left\langle \exp u , u' \exp u \right\rangle \\
                               \log\left\langle u,u'\right\rangle &= \left\langle \log(u) , u'/u \right\rangle \quad (u>0) \\
                                 \left\langle u,u'\right\rangle^k &= \left\langle u^k , k u^{k - 1} u' \right\rangle \quad (u \ne 0) \\
                    \left| \left\langle u,u'\right\rangle \right| &= \left\langle \left| u \right| , u' \mbox{sign} u \right\rangle \quad (u \ne 0)
\end{align}</math>
一般に、プリミティヴの関数 <math>g</math> に対して、
:<math>g(\langle u,u' \rangle , \langle v,v' \rangle ) = \langle g(u,v) , g_u(u,v) u' + g_v(u,v) v' \rangle</math>
ここで <math>g_u</math> と <math>g_v</math> はそれぞれ <math>g</math> の最初と2番目の引数に対する微分である。
<!-- 訳注：記号処理系で自動微分を実装する場合、解析関数を全部扱うわけにはいかない。「関数そのもの」を扱うことも出来ない。関数は全て記号として取り扱われなければならない。この際に初期記号が用意される諸関数が primitive と呼ばれている。Primitive の微分については a priori に規則として与えられる。ここでの primitive は不定積分（原始関数）のことではない。-->

基本的な二項算術演算を（実数と二重数の）混在した引数に対して、つまり順序対 <math>\langle u, u' \rangle</math> と実数 <math>c</math> に対して適用するとき、まずこの実数を <math>\langle c, 0 \rangle</math> に引き上げる（lifting）。関数 <math>f : \mathbb{R}\rightarrow\mathbb{R}</math> の <math>x_0</math> に於ける微分はいまや <math>f(\langle x_0, 1 \rangle)</math> に上の算術を使って計算することによって得られる。これは <math>\langle f ( x_0 ) , f' ( x_0 ) \rangle </math> を結果として与える。

===ベクトル引数と関数===
多変数関数は、方向微分作用素を用いることで、一変数関数の場合と同様の効率と仕組みで取り扱える。つまり、<math>f:\mathbb{R}^n\rightarrow\mathbb{R}^m</math> の <math>x \in \mathbb{R}^n</math> における <math>x' \in \mathbb{R}^n</math> 方向微分 <math>y' = \nabla f(x)\cdot x'</math> を計算したい場合、それは <math>(\langle y_1,y'_1\rangle, \ldots, \langle y_m,y'_m\rangle) = f(\langle x_1,x'_1\rangle, \ldots, \langle x_n,x'_n\rangle)</math> を上と同様の算術を使って計算すればよい。もし <math>\nabla f</math> の全ての要素が望みならば、<math>n</math> 個の関数評価が要求される。ここで、多くの最適化アプリケーションでは、実際には方向微分があれば十分である。

===高階・多変数===
上の算術は多変数関数の二階やもっと高階の微分の計算の為に一般化出来る。しかし、その算術規則は直ちに極めて複雑なものとなる：複雑性は最高次の微分の次数に対して二次関数的となる。その代わりに、途中で打ち切った（truncated）テイラー多項式の代数を使用できる。結果得られる算術（一般化された二重数の上で定義された）は、関数を新しいデータ型であるかのように<!-- 訳者メモ：意味不明 -->使って、効率的に計算することを可能にする。ひとたび関数のテイラー多項式が分かれば、その導関数たちは容易に抽出できる。
厳密で一般的な定式化は{{仮リンク|テンソル級数展開|en|Automatic differentiation#Tensor series expansion}}を通して{{仮リンク|プログラミング空間上の演算子法|en|Automatic differentiation#Operational calculus on programming spaces}}を用いることにより達成される。

== 実装 ==
自動微分の実装方法には大きく分けて、ソースコードの変換とオペレータオーバーローディングによる方法の2つがある。

=== ソースコード変換 ===
[[Image:SourceTransformationAutomaticDifferentiation.png|thumb|right|300px|図4: ソースコード変換の動作例]]

関数値を求める関数を記述した元のソースコードから、偏導関数値を計算する処理を含んだプログラムを自動的に生成する手法である。ソースコード変換はあらゆるプログラミング言語で実装でき、コンパイル時の最適化を行いやすいが、自動微分ツールの作成は難しい。

=== オペレータオーバーローディング ===
[[Image:OperatorOverloadingAutomaticDifferentiation.png|thumb|right|300px|図5: オペレータオーバーローディングの動作例]]
この手法は演算子のオーバーロードがサポートされているプログラミング言語で記述されたソースコードに対してのみ適用可能である。元のソースコードの流れを大きく変更することなく実現できるが、基本データ型の変更などの小さな変更は必要である。

ボトムアップ型自動微分をオペレータオーバーロードで実現するのは容易である。トップダウン型自動微分についても可能であるが、現状のコンパイラではボトムアップ型自動微分と比べると最適化の面で不利である。

== ソフトウェア ==
自動微分を実装したライブラリなどのソフトウェアが多数存在する。2010年代の第3次人工知能ブームの際に[[ディープラーニング]]に自動微分が必要なため、[[TensorFlow]]や[[PyTorch]]などトップダウン型の自動微分を含むライブラリが多数作られた。

== 脚注 ==
{{reflist}}

== 参考文献 ==
* {{cite book
  | last1 = 久保田
  | first1 = 光一
  | last2 = 伊理
  | first2 = 正夫
  | title = アルゴリズムの自動微分と応用
  | publisher = [[コロナ社 (出版社)|コロナ社]]
  | series = 現代非線形科学シリーズ
  | volume = 3
  | year = 1998
  | isbn = 978-4339026023
}}
* 伊理正夫、「[https://doi.org/10.11540/bjsiam.3.1_58 高速自動微分法(第2回年会特別講演)]」『応用数理』 1993年 3巻 1号 p.58-66, {{doi|10.11540/bjsiam.3.1_58}}, 日本応用数理学会
* {{cite book
  | last = Rall
  | first = Louis B.
  | title = Automatic Differentiation: Techniques and Applications
  | publisher = [[Springer Science+Business Media|Springer]]
  | series = Lecture Notes in Computer Science
  | volume = 120
  | year = 1981
  | isbn = 3-540-10861-0
}}
* {{cite book
  | last1 = Griewank
  | first1 = Andreas
  | last2 = Walther
  | first2 = Andrea
  | title = Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation
  | edition = 2nd
  | publisher = [[Society for Industrial and Applied Mathematics|SIAM]]
  | series = Other Titles in Applied Mathematics
  | volume = 105
  | year = 2008
  | isbn = 978-0-89871-659-7
  | url = http://www.ec-securehost.com/SIAM/OT105.html
<!--  | accessdate = 10-21-2009 -->
}}
*  {{cite journal
   |last=Neidinger
   |first=Richard
   |title=Introduction to Automatic Differentiation and MATLAB Object-Oriented Programming
   |journal=SIAM Review
   |year=2010|volume=52
   |issue=3
   |pages=545–563
   |doi=10.1137/080743627
   |url=http://academics.davidson.edu/math/neidinger/SIAMRev74362.pdf
   |accessdate=2013-03-15
}}

==外部リンク==
* [http://www.autodiff.org/ www.autodiff.org - Community Portal for Automatic Differentiation]

{{Normdaten}}

{{DEFAULTSORT:しとうひふん}}
[[Category:微分学]]
[[Category:計算モデル]]
[[Category:情報処理]]
[[Category:数学に関する記事]]