自動微分

数学とコンピュータ代数において、自動微分（自動微分、オートディフ、またはAD）は、アルゴリズム微分、計算微分とも呼ばれ、^{[1] [2]は、コンピュータプログラムによって指定された関数の}偏微分を評価するための一連の手法です。

自動微分法は、どんなに複雑なコンピュータ計算でも、一連の基本的な算術演算 (加算、減算、乗算、除算など) と基本的な関数 ( exp、log、sin、cosなど) を実行するという事実を利用します。これらの演算に連鎖律を繰り返し適用することで、任意の順序の偏導関数を、作業精度まで正確に、元のプログラムよりも最大で小さな定数倍の算術演算を使用して自動的に計算できます。

自動微分は、記号微分や数値微分とは異なります。記号微分では、コンピュータ プログラムを単一の数式に変換することが難しく、コードが非効率的になる可能性があります。数値微分 (有限差分法)では、離散化プロセスとキャンセルで丸め誤差が発生する可能性があります。これらの古典的な方法は両方とも、複雑性と誤差が増加する高次の導関数の計算に問題があります。最後に、これらの古典的な方法は両方とも、勾配ベースの最適化アルゴリズムに必要な、多くの入力に関する関数の偏導関数の計算が遅いです。自動微分は、これらの問題をすべて解決します。

自動微分は機械学習の分野で特に重要です。たとえば、手動で計算された導関数を使用せずに、ニューラル ネットワークで バックプロパゲーションを実装できます。

自動微分化の基本は、合成関数の偏微分の連鎖律によって提供される微分分解である。単純な合成の場合、 連鎖律は次式を与える。 $${\displaystyle {\begin{aligned}y&=f(g(h(x)))=f(g(h(w_{0})))=f(g(w_{1}))=f(w_{2})=w_{3}\\w_{0}&=x\\w_{1}&=h(w_{0})\\w_{2}&=g(w_{1})\\w_{3}&=f(w_{2})=y\end{aligned}}}$$$${\displaystyle {\frac {\partial y}{\partial x}}={\frac {\partial y}{\partial w_{2}}}{\frac {\partial w_{2}}{\partial w_{1}}}{\frac {\partial w_{1}}{\partial x}}={\frac {\partial f(w_{2})}{\partial w_{2}}}{\frac {\partial g(w_{1})}{\partial w_{1}}}{\frac {\partial h(w_{0})}{\partial x}}}$$

通常、自動微分化には 2 つの異なるモードが提示されます。

• 前方累積（ボトムアップ、前方モード、接線モードとも呼ばれる）
• 逆蓄積（トップダウン、逆モード、または随伴モードとも呼ばれる）

順方向累積は、連鎖律を内側から外側へ（つまり、最初に を計算し、次に 、最後に）走査することを指定します。一方、逆方向累積は、外側から内側へ（最初に を計算し、次に、最後に）走査することを指定します。より簡潔に言うと、 ${\displaystyle \partial w_{1}/\partial x}$${\displaystyle \partial w_{2}/\partial w_{1}}$${\displaystyle \partial y/\partial w_{2}}$${\displaystyle \partial y/\partial w_{2}}$${\displaystyle \partial w_{2}/\partial w_{1}}$${\displaystyle \partial w_{1}/\partial x}$

• 前方累積は、再帰関係を計算します。 、および、${\displaystyle {\frac {\partial w_{i}}{\partial x}}={\frac {\partial w_{i}}{\partial w_{i-1}}}{\frac {\partial w_{i-1}}{\partial x}}}$${\displaystyle w_{3}=y}$
• 逆累積は、の再帰関係を計算します。${\displaystyle {\frac {\partial y}{\partial w_{i}}}={\frac {\partial y}{\partial w_{i+1}}}{\frac {\partial w_{i+1}}{\partial w_{i}}}}$${\displaystyle w_{0}=x}$

偏導関数の値はシードと呼ばれ、前方または後方に伝播され、最初はまたはです。前方累積は関数を評価し、1 つのパスで 1 つの独立変数に関する導関数を計算します。したがって、各独立変数について、その独立変数に関する導関数が 1 ( ) に設定され、その他すべての導関数が 0 ( ) に設定される個別のパスが必要です。対照的に、逆累積では、偏導関数に対して評価された部分関数が必要です。したがって、逆累積は最初に関数を評価し、追加のパスですべての独立変数に関する導関数を計算します。 ${\displaystyle {\frac {\partial x}{\partial x}}=1}$${\displaystyle {\frac {\partial y}{\partial y}}=1}$${\displaystyle x_{1},x_{2},\dots ,x_{n}}$${\displaystyle {\frac {\partial x_{1}}{\partial x_{1}}}=1}$${\displaystyle {\frac {\partial x_{2}}{\partial x_{1}}}=\dots ={\frac {\partial x_{n}}{\partial x_{1}}}=0}$

これら 2 つのタイプのどちらを使用するかは、スイープの数によって異なります。1回のスイープの計算の複雑さは、元のコードの複雑さに比例します。

• 関数f  : R ⁿ → R ^m （ n ≪ m）の場合、逆方向の累算よりも順方向の累算の方が効率的です。逆方向の累算ではm回のスイープが必要ですが、n 回のスイープだけで済むためです。
• 逆累積は、関数f  : R ⁿ → R ^m ( n ≫ m)の場合、順累積よりも効率的です。順累積の場合はn 回のスイープが必要ですが、逆累積の場合はm 回のスイープしか必要ないためです。

機械学習で使用される技術である多層パーセプトロンにおける誤差の逆伝播は、逆累積の特殊なケースである。^[2]

順方向蓄積は1964年にRE Wengertによって導入されました。^[3] Andreas Griewankによると、逆方向蓄積は1960年代後半から提案されていましたが、発明者は不明です。^[4] Seppo Linnainmaaは1976年に逆方向蓄積を発表しました。 ^[5]

順方向累積 AD では、まず、微分化を実行する独立変数を固定し、各部分式の導関数を再帰的に計算します。紙とペンによる計算では、連鎖律に 内部関数の導関数を繰り返し代入する必要があります。これは、ヤコビアン の行列積として複数の変数に一般化できます。 $${\displaystyle {\begin{aligned}{\frac {\partial y}{\partial x}}&={\frac {\partial y}{\partial w_{n-1}}}{\frac {\partial w_{n-1}}{\partial x}}\\[6pt]&={\frac {\partial y}{\partial w_{n-1}}}\left({\frac {\partial w_{n-1}}{\partial w_{n-2}}}{\frac {\partial w_{n-2}}{\partial x}}\right)\\[6pt]&={\frac {\partial y}{\partial w_{n-1}}}\left({\frac {\partial w_{n-1}}{\partial w_{n-2}}}\left({\frac {\partial w_{n-2}}{\partial w_{n-3}}}{\frac {\partial w_{n-3}}{\partial x}}\right)\right)\\[6pt]&=\cdots \end{aligned}}}$$

逆累積と比較すると、順累積は導関数情報の流れが評価の順序と一致するため、自然で実装が簡単です。各変数には、ドットで示されるように、導関数(記号式ではなく数値として保存) が追加されます 。次に、導関数は評価手順と同期して計算され、連鎖律によって他の導関数と結合されます。 ${\displaystyle w_{i}}$${\displaystyle {\dot {w}}_{i}}$$${\displaystyle {\dot {w}}_{i}={\frac {\partial w_{i}}{\partial x}}}$$

連鎖律を使用すると、計算グラフに先行要素がある場合、次のようになります。 ${\displaystyle w_{i}}$

${\displaystyle {\dot {w}}_{i}=\sum _{j\in \{{\text{predecessors of i}}\}}{\frac {\partial w_{i}}{\partial w_{j}}}{\dot {w}}_{j}}$

例として、次の関数を考えてみましょう。 わかりやすくするために、個々の部分式には変数 というラベルが付けられています。 $${\displaystyle {\begin{aligned}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{aligned}}}$$${\displaystyle w_{i}}$

微分を行う独立変数の選択は、シード値ẇ ₁とẇ _{2に影響します。この関数の}x ₁に関する導関数に関心がある場合、シード値は次のように設定する必要があります。 $${\displaystyle {\begin{aligned}{\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{aligned}}}$$

シード値を設定すると、図に示すように、値は連鎖律に従って伝播します。図 2 は、このプロセスを計算グラフとして図示したものです。

この例の関数の勾配を計算するには、 だけでなく も必要であり、シード値 を使用して計算グラフ上で追加のスイープが実行されます。 ${\displaystyle {\tfrac {\partial y}{\partial x_{1}}}}$${\displaystyle {\tfrac {\partial y}{\partial x_{2}}}}$${\displaystyle {\dot {w}}_{1}=0;{\dot {w}}_{2}=1}$

前方累積は、関数と導関数（ただし、それぞれ独立変数 1 つずつ）を 1 回のパスで計算します。関連するメソッド呼び出しでは、式Z が変数Vに関して導出されることが想定されています。メソッドは、評価された関数とその導関数のペアを返します。メソッドは、変数に到達するまで式ツリーを再帰的にトラバースします。この変数に関する導関数が要求された場合、その導関数は 1 で、そうでない場合は 0 です。次に、部分関数と部分導関数が評価されます。^[6]

タプル< float 、float > assessAndDerive (式Z 、変数V ) { if isVariable ( Z ) if ( Z = V ) return { valueOf ( Z ), 1 }; else return { valueOf ( Z ), 0 }; else if ( Z = A + B ) { a 、a ' } = assessAndDerive ( A 、V ); { b 、b ' } = assessAndDerive ( B 、V ); return { a + b 、a ' + b ' }; else if ( Z = A - B ) { a 、a ' } = assessAndDerive ( A 、V ); { b 、b ' } = assessAndDerive ( B 、V ); return { a - b 、a ' - b ' }; else if ( Z = A * B ) { a 、a ' } = assessAndDerive ( A 、V ); { b 、b ' } = assessAndDerive ( B 、V );戻り値{ a * b 、b * a ' + a * b ' }; }     
    
            
         
         
          
          
            
         
          
          
            
         
          
          
                

#include <iostream> struct ValueAndPartial { float value , partial ; }; struct Variable ; struct Expression { virtual ValueAndPartial assessAndDerive ( Variable * variable ) = 0 ; }; struct Variable : public Expression { float value ; Variable ( float value ) : value ( value ) {} ValueAndPartial assessAndDerive ( Variable * variable ) { float partial = ( this == variable ) ? 1.0f : 0.0f ; return { value , partial }; } }; struct Plus : public Expression { Expression * a , * b ; Plus ( Expression * a , Expression * b ) : a ( a ), b ( b ) {} ValueAndPartial assessAndDerive ( Variable * variable ) { auto [ valueA , partialA ] = a -> assessAndDerive ( variable ); auto [ valueB , partialB ] = b -> evaluateAndDerive (変数); return { valueA + valueB , partialA + partialB }; } }; struct Multiply : public Expression { Expression * a , * b ; Multiply ( Expression * a , 
      
 
  
        

    
    
      
      
               
        
   

    
     
         
      
          
          
            
   

    
     
     Expression * b ) : a ( a ), b ( b ) {} ValueAndPartial assessAndDerive ( Variable * variable ) { auto [ valueA , partialA ] = a -> assessAndDerive ( variable ); auto [ valueB , partialB ] = b -> assessAndDerive ( variable ); return { valueA * valueB , valueB * partialA + valueA * partialB }; } }; int main () { // 例: (x, y) = (2, 3) における z = x * (x + y) + y * y の部分値を求めるVariable x ( 2 ), y ( 3 ); Plus p1 ( & x , & y ); Multiply m1 ( & x , & p1 ); Multiply m2 ( & y , & y ); Plus z ( & m1 , & m2 ); float xPartial = z .evaluateAndDerive ( & x ) . partial ; float yPartial = z .evaluateAndDerive ( & y ) . partial ; std :: cout << "∂z/∂x = " << xPartial << ", " << "∂z/∂y = " << yPartial << std :: endl ; // 出力: ∂z/∂x = 7, ∂z/∂y = 8 return 0 ; }    
      
          
          
                
   

   
   
     
              
      
      
         
                  
   
    

逆累積 AD では、微分する従属変数が固定され、各部分式に関して導関数が再帰的に計算されます。紙とペンによる計算では、外部関数の導関数が連鎖律に繰り返し代入されます。 $${\displaystyle {\begin{aligned}{\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 \end{aligned}}}$$

逆累積では、関心のある量はバーで示される随伴量であり、これは選択された従属変数の部分式に関する導関数です。 ${\displaystyle {\bar {w}}_{i}}$${\displaystyle w_{i}}$$${\displaystyle {\bar {w}}_{i}={\frac {\partial y}{\partial w_{i}}}}$$

連鎖律を使用すると、計算グラフに後続がある場合: ${\displaystyle w_{i}}$

${\displaystyle {\bar {w}}_{i}=\sum _{j\in \{{\text{successors of i}}\}}{\bar {w}}_{j}{\frac {\partial w_{j}}{\partial w_{i}}}}$

逆累積は、連鎖律を外側から内側へ、または図 3 の計算グラフの場合は上から下へ横断します。例の関数はスカラー値であるため、導関数計算のシードは 1 つだけであり、計算グラフのスイープは 1 回のみで (2 成分) 勾配を計算できます。これは、順方向累積と比較すると作業量が半分になりますが、逆累積では、中間変数 w i と、_それらを生成した命令を「テープ」または Wengert リスト^[7]と呼ばれるデータ構造に格納する必要があります(ただし、Wengert は逆累積ではなく、順方向累積を公開しました^[3] )。計算グラフが大きい場合は、メモリを大量に消費する可能性があります。中間変数のサブセットのみを保存し、評価を繰り返すことで必要な作業変数を再構築することで、この問題をある程度軽減できます。この手法は再マテリアライゼーションと呼ばれます。チェックポイントは、中間状態を保存するためにも使用されます。

逆累積を使用して導関数を計算するための操作を次の表に示します (逆の順序に注意してください)。

計算のデータフローグラフを操作して、元の計算の勾配を計算できます。これは、各主ノードに随伴ノードを追加することで行われます。随伴ノードは、主エッジと平行ですが、反対方向に流れる随伴エッジで接続されます。随伴グラフのノードは、主ノードで計算された関数の導関数による乗算を表します。たとえば、主ノードで加算を行うと随伴ノードでファンアウトが発生します。主ノードでファンアウトが発生すると随伴ノードで加算が発生します。^{[a]主ノードで}単項関数y = f ( x )を実行すると、随伴ノードでx̄ = ȳ f ′( x )が発生します。など。

逆累積には 2 つのパスが必要です。順方向パスでは、関数が最初に評価され、部分的な結果がキャッシュされます。逆方向パスでは、偏導関数が計算され、以前に導出された値が逆伝播されます。対応するメソッド呼び出しでは、式Zが導出され、親式の導出値でシードされることが想定されています。最上位の式、Z に関して導出された Z の場合、これは 1 です。メソッドは、変数に到達するまで式ツリーを再帰的にトラバースし、現在のシード値を導出式に追加します。^{[8] [9]}

void derive ( Expression Z 、float seed ) { if isVariable ( Z ) partialDerivativeOf ( Z ) += seed ; else if ( Z = A + B ) derive ( A 、seed ); derive ( B 、seed ); else if ( Z = A - B ) derive ( A 、seed ); derive ( B 、- seed ); else if ( Z = A * B ) derive ( A 、valueOf ( B ) * seed ); derive ( B 、valueOf ( A ) * seed ); }     
    
        
         
       
       
         
       
       
         
         
         

#include <iostream> struct Expression { float value ; virtual void assess () = 0 ; virtual void derive ( float seed ) = 0 ; }; struct Variable : public Expression { float partial ; Variable ( float value ) { this -> value = value ; partial = 0.0f ; } void assess () {} void derive ( float seed ) { partial += seed ; } }; struct Plus : public Expression { Expression * a , * b ; Plus ( Expression * a , Expression * b ) : a ( a ), b ( b ) {} void assess () { a -> assess (); b -> assess (); value = a -> value + b -> value ; } void derive ( float seed ) { a -> derive ( seed ); b -> derive ( seed ); } }; struct Multiply : public Expression { Expression * a , * b ;乗算(式* a 、式* b ) : a ( a )、b ( b ) {} void評価() { a -> 
  
    
       
        

    
    
     
        
        
   
     
      
        
   

    
     
         
     
      
      
          
   
      
      
      
   

    
     
         
     
      評価(); 
b ->評価(); value = a -> value * b -> value ; } void derive ( float seed ) { a -> derive ( b -> value * seed ); b -> derive ( a -> value * seed ); } }; int main () { // 例: (x, y) = (2, 3) における z = x * (x + y) + y * y の部分分布を求める変数x ( 2 ), y ( 3 );加算p1 ( & x , & y );乗算m1 ( & x , & p1 );乗算m2 ( & y , & y );加算z ( & m1 , & m2 ); z .評価(); std :: cout << "z = " << z . value << std :: endl ; // 出力: z = 19 z . derive ( 1 ); std :: cout << "∂z/∂x = " << x . partial << ", " << "∂z/∂y = " << y . partial << std :: endl ; // 出力: ∂z/∂x = 7, ∂z/∂y = 8 return 0 ; }      
          
   
      
        
        
   

   
   
     
              
   
         
   
   
         
                  
   
    

順方向累積と逆方向累積は、連鎖律を通過する 2 つの (極端な) 方法にすぎません。f : R n → R m の完全なヤコビアンを最小の算術演算で計算する問題は、最適 ヤコビアン累積⁽ OJA )^問題として知られており、 NP完全です。^[10]この証明の中心となるのは、グラフのエッジにラベルを付けるローカル部分の間に代数的な依存関係が存在する可能性があるというアイデアです。特に、2 つ以上のエッジ ラベルが等しいと認識される場合があります。すべてのエッジ ラベルが一意で代数的に独立していると仮定すると、問題の複雑さは依然として未解決のままです。

順方向モードの自動微分は、実数の代数を拡張して新しい算術式を取得することによって実現されます。すべての数に、その数での関数の導関数を表すための追加の要素が追加され、すべての算術演算子が拡張代数用に拡張されます。拡張代数は、双対数の代数です。

すべての数を数 で置き換えます。ここで、 は実数ですが、 はという特性を持つ抽象数です（無限小。 「滑らかな無限小解析」を参照）。これだけを使用すると、通常の演算では を使用します。 ${\displaystyle \,x}$${\displaystyle x+x'\varepsilon }$${\displaystyle x'}$${\displaystyle \varepsilon }$${\displaystyle \varepsilon ^{2}=0}$$${\displaystyle {\begin{aligned}(x+x'\varepsilon )+(y+y'\varepsilon )&=x+y+(x'+y')\varepsilon \\(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+(xy'+yx')\varepsilon \\(x+x'\varepsilon )/(y+y'\varepsilon )&=(x/y+x'\varepsilon /y)/(1+y'\varepsilon /y)=(x/y+x'\varepsilon /y)\cdot (1-y'\varepsilon /y)=x/y+(x'/y-xy'/y^{2})\varepsilon \end{aligned}}}$$${\displaystyle (1+y'\varepsilon /y)\cdot (1-y'\varepsilon /y)=1}$

これで、この拡張演算で多項式を計算できるようになりました。 の場合、 はの最初の引数に関する導関数を表し、 はシードと呼ばれ、任意に選択できます。 ${\displaystyle P(x)=p_{0}+p_{1}x+p_{2}x^{2}+\cdots +p_{n}x^{n}}$$${\displaystyle {\begin{aligned}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_{1}x'\varepsilon +2p_{2}xx'\varepsilon +\cdots +np_{n}x^{n-1}x'\varepsilon \\&=P(x)+P^{(1)}(x)x'\varepsilon \end{aligned}}}$$${\displaystyle P^{(1)}}$${\displaystyle P}$${\displaystyle x'}$

新しい演算は、 と書かれた要素の順序付きペアで構成され、前述のように、最初の要素には通常の演算が、2 番目の要素には 1 階微分演算が行われます。多項式に関する上記の結果を解析関数に拡張すると、新しい演算に対する基本的な演算といくつかの標準関数のリストが得られます。 一般に、原始関数 に対してとなります。 ここで、と は、それぞれ の最初の引数と 2 番目の引数に関する の 導関数です。${\displaystyle \langle x,x'\rangle }$$${\displaystyle {\begin{aligned}\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 uv,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\neq 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},u'ku^{k-1}\right\rangle \quad (u\neq 0)\\\left|\left\langle u,u'\right\rangle \right|&=\left\langle \left|u\right|,u'\operatorname {sign} u\right\rangle \quad (u\neq 0)\end{aligned}}}$$${\displaystyle g}$$${\displaystyle g(\langle u,u'\rangle ,\langle v,v'\rangle )=\langle g(u,v),g_{u}(u,v)u'+g_{v}(u,v)v'\rangle }$$${\displaystyle g_{u}}$${\displaystyle g_{v}}$${\displaystyle g}$