自動微分

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

自動微分(じどうびぶん、アルゴリズム微分とも)とは、プログラム定義された関数解析し、偏導関数の値を計算するプログラムを導出する技術である。自動微分は複雑なプログラムであっても加減乗除などの基本的な算術演算や基本的な関数(指数関数対数関数三角関数など)のような基本的な演算の組み合わせで構成されていることを利用し、これらの演算に対して連鎖律を繰り返し適用することによって実現される。自動微分を用いることで偏導関数値を少ない計算量で自動的に求めることができる。

自動微分は

図1: 自動微分と数式微分の関係

のどちらとも異なる。

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

英語では Automatic differentiation (あるいは単に AD) と呼ばれる。

自動微分の導出[編集]

自動微分の基本原理は連鎖律を用いた微分の分解である。たとえば、簡単な合成関数である y = g(h(x)) = g(w) に対して連鎖律を適用すると

\frac{dy}{dx} = \frac{dy}{dw} \frac{dw}{dx}

を得る。

自動微分は大きく2種類に分けられ、それぞれボトムアップ型自動微分(フォーワードモード、狭義の自動微分)とトップダウン型自動微分(リバースモード、高速自動微分)と呼ばれる。 ボトムアップ型自動微分では連鎖律を内側から外側に計算し(dw/dxを計算した後で dy/dw を計算する)、トップダウン型自動微分では外側から内側に計算する。

ボトムアップ型自動微分[編集]

図2: ボトムアップ型自動微分の計算グラフの例

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

\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

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

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

\dot w = \frac{\partial w}{\partial x}

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

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

\begin{align}
z
&= 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}

簡単のためそれぞれの部分式を wi としてラベル付けした。

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

\begin{align}
\dot w_1 = \frac{\partial x_1}{\partial x_1} = 1 \\
\dot w_2 = \frac{\partial x_2}{\partial x_1} = 0
\end{align}

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

\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 = \dot w_3 + \dot w_4
\end{array}

この関数に対する勾配を求めるためにはx1だけではなくx2に関する偏導関数値も求める必要がある。そのため、初期値を\dot w_1 = 0; \dot w_2 = 1 とした同様の計算を追加で行わなければならない。

ボトムアップ型自動微分を1回行うのに必要な計算量は、元のプログラムの計算量に比例する。

勾配を求める場合に必要なボトムアップ型自動微分の実行回数は入力変数の個数と等しく、トップダウン型自動微分では出力変数の個数に等しい。そのため、微分する関数f : ℝn → ℝmmn を満たす場合、ボトムアップ型自動微分はトップダウン型自動微分よりも効率的である。

トップダウン型自動微分[編集]

図3: トップダウン型自動微分の計算グラフの例

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

\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

トップダウン型自動微分において、求める値は随伴であり[訳語疑問点]、上線()で表す。これは選択された出力変数のwに関する微分

\bar w = \frac{\partial y}{\partial w}

である。

トップダウン型自動微分は連鎖律を外側から内側(図3の計算グラフでは上から下)にたどっていく。例示した関数は1変数関数なので、勾配を計算するには計算グラフを一度たどるだけでよい。これは2回計算グラフをたどる必要があったボトムアップ型自動微分の計算量の半分である。しかし、トップダウン型自動微分は中間変数wi を保存するための領域と、Wengert list[1] というデータ構造に中間変数を保存するための命令が必要となるためメモリ使用量の点で不利であり、計算グラフが巨大になるとメモリ使用量が問題となる可能性がある。この問題は保存する中間変数を限定し、必要な中間変数を再計算することによって軽減される。

トップダウン型自動微分を用いて偏導関数値を計算するための演算は以下の通りである(関数値を求める時と順番が逆であることに注意)

\begin{array}{l}
\text{Operations to compute derivative}
\\ \hline
\bar w_5 = 1 \text{ (seed)}
\\
\bar w_4 = \bar w_5
\\
\bar w_3 = \bar w_5
\\
\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}

微分する関数f : ℝn → ℝmmnを満たすとき、トップダウン型自動微分はボトムアップ型自動微分よりも効率的である。

機械学習で用いられる多層パーセプトロンのバックプロパゲーション はトップダウン型自動微分の特殊なケースである。

二重数を用いた自動微分[編集]

ボトムアップ型自動微分は二重数を用いることで計算できる。詳細は英語版を参照のこと。

実装[編集]

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

ソースコード変換[編集]

図4: ソースコード変換の動作例

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

オペレータオーバーローディング[編集]

図5: オペレータオーバーローディングの動作例

この手法は演算子のオーバーロードがサポートされているプログラミング言語で記述されたソースコードに対してのみ適用可能である。元のソースコードの流れを大きく変更することなく実現できるが、基本データ型の変更などの小さな変更は必要である。

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

ソフトウェア[編集]

自動微分を実装したライブラリなどのソフトウェアが存在する。詳細は英語版を参照のこと。

脚注[編集]

  1. ^ Bartholomew-Biggs, Michael; Brown, Steven; Christianson, Bruce; Dixon, Laurence (2000). “Automatic differentiation of algorithms”. Journal of Computational and Applied Mathematics 124 (1-2): 171-190. doi:10.1016/S0377-0427(00)00422-2. http://ac.els-cdn.com/S0377042700004222/1-s2.0-S0377042700004222-main.pdf?_tid=61070b3c-31f1-11e5-a550-00000aacb35f&acdnat=1437735029_c639352923bb07e65307eb75c420d42f. 

参考文献[編集]

  • 久保田, 光一; 伊理, 正夫 (1998). アルゴリズムの自動微分と応用. 現代非線形科学シリーズ. 3. コロナ社. ISBN 978-4339026023. 
  • (1991), 伊理 正夫, 久保田,光一, "高速自動微分法(I)", 応用数理 1(1), 17-35, 19910315, 日本応用数理学会.

外部リンク[編集]