自動微分

自動微分やアルゴリズム微分とは、プログラムで定義された関数を解析し、関数の値と同時に偏導関数の値を計算するアルゴリズムである。

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

1. 他の微分方式との違い
-------------

自動微分は以下のどちらとも異なる。
記号微分・数式微分 - 原関数を表す数式から数式処理により導関数を導出する。数式処理システムで実装されている。
数値微分 - 原関数の値から数値的に微分係数を算出する記号微分は効率が悪くなりやすく、プログラムで定義された関数から微分表現を導くのは困難であるという問題がある。一方、数値微分では離散化の際の丸め誤差や桁落ちによる精度の低下が問題である。さらに、どちらの手法も計算量や誤差の関係で高次の微分係数を求めることが難しい。また、勾配を用いた最適化で必要となる、多くの入力変数を持つ関数に対する偏微分値の計算を行うには速度が遅い。自動微分はこれらの古典的手法の問題を解決する。

また、自動微分は計算フローを追いかけることで計算できるので、分岐やループや再帰を含むようなアルゴリズムでも偏微分できる。

2. 自動微分の導出
----------

2.1. 合成関数の偏微分の連鎖律
-----------------

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

合成関数の偏微分の連鎖律とは の時、下記が成立することである。

2.2. 2種類の自動微分
-------------

自動微分は2種類に分けられ、それぞれ

ボトムアップ型自動微分
トップダウン型自動微分と呼ばれる。

ボトムアップ型自動微分では連鎖律を内側から外側に計算し、トップダウン型自動微分では外側から内側に計算する。

使い分けは、入力が n 次元、出力が m 次元とした場合、以下の違いがある。

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

ボトムアップ型はR.E. Wengertが1964年に発表したが、2ページの論文で特に名前を付けていない。Andreas Griewank によると、トップダウン型を誰が最初に発明したのか判然としないが、計算量を減らす工夫として1960年代後半には提案されていた。

2.3. ボトムアップ型自動微分
----------------

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

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

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

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

連鎖律より、 が計算グラフで先行ノードを持つ場合、

, j ∈ {i の先行ノード}

例として次の関数を考える。

それぞれの部分式を中間変数 としてラベル付けした。最初に としている。

どの入力変数で偏微分するかによって や の初期値が異なる。 に関する偏微分を計算する場合の初期値は、

となる。初期値が決まったら下の表に示す連鎖律に従って各偏導関数値を順に計算していく。図2はこの処理を計算グラフとして表している。 が求めたい値である。

この関数 f に対する勾配を求めるためには だけではなく も求める必要がある。そのため、初期値を とした同様の計算を追加で行わなければならない。

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

2.4. トップダウン型自動微分
----------------

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

トップダウン型自動微分において、求める値はボトムアップ型の随伴date=2016年3月}}であり、上線 で表す。これは中間変数 に関する偏微分

である。連鎖律より、 が計算グラフで後続ノードを持つ場合、

, j ∈ {i の後続ノード}トップダウン型自動微分は連鎖律を外側から内側にたどっていく。

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

しかし、トップダウン型自動微分は、テープやWengert リストと呼ばれるサイズ変更が可能な配列に中間変数 の計算結果を追記していく必要があるためメモリ使用量の点で不利であり、計算グラフが巨大になるとメモリ使用量が問題となる可能性がある。この問題は保存する中間変数を限定し、必要な中間変数を再計算することによって軽減される。

トップダウン型自動微分を用いて偏導関数値を計算するための演算は以下の通りである。 と が求めたい値である。

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

テープを使用しない場合は、以下のように Python で実装できる。 import math

class Var: def __init__: self.value = value self.children = children or [] self.grad = 0

def __add__: return Var, ])

def __mul__: return Var, ])

def sin: return Var, [, self)])

def calc_grad: self.grad += grad for coef, child in self.children: child.calc_grad

例: f = x * y + sinx = Var y = Var f = x * y + x.sin

偏微分の計算f.calc_grad

print print print<WtXmlEndTag />

テープを使用する場合のアルゴリズムの実装の流れは以下の通りである。

テープをサイズ変更が可能な配列として用意する。テープの要素は中間変数 毎に作り、以下の5項目を記録する。
計算内容
計算グラフの入辺：計算に使用した引数のテープ上のインデックスのリスト。 なら と 。
計算グラフの出辺：この中間変数がどの計算で使われたかのテープ上のインデックスのリスト。計算しながら追記していく。 なら と 。
の値
の値
の値を計算していく。その際、上記の内容をテープに追記していく。また、テープには、どの中間変数の計算で、どの中間変数を使用したかも追記する。同一の中間変数を2回以上計算しないように注意が必要。
テープの最後の を 1 として、その1つ前から逆順に を計算していく。スカラー値ではなく NumPy のような多次元配列を扱う場合も処理すべき内容は同じである。 を1つの処理単位として実装する。これを vector-Jacobian product  や L-operator  と言う。行列積の VJP は行列積で実装できる。ただし、ある軸での和の VJP は、その軸で値を繰り返して の軸を復元する処理になるなど、直観的で無い物もある。ハーバード大学の HIPS が開発していた Autograd は、ほぼ全ての NumPy の関数の VJP を実装していて、簡潔に実装しているので参考になる。なお は Jacobian-vector product  や R-operator  と言い、ボトムアップ型で使用する。

3. 二重数を用いた自動微分
--------------

ボトムアップ型自動微分は実数の代数に添加して新しい算術を導入することによって可能である。全ての数に対して、その数における関数の微分を表現する追加の成分が足され、全ての算術演算がこの添加代数に拡張される。すなわち二重数の代数である。このアプローチはプログラミング空間上の演算子法の理論によって一般化される