久保田 光一、伊理 正夫：アルゴリズムの自動微分と応用

概要

計算の品質を確保するための一方法である高速自動微分について、その基礎と応用を述べる。

感想

アルゴリズム・数値微分・グラフ理論の美しい出合い（シュールレアリズム宣言みたい）。 でも、実際のプログラムに応用されるのはまだ先なのではないか。

式の難しさ

どうにもこうにも、式が難しい。たとえば、4.3.2 項「ノルム問題の解決」では、 4.2.1 項の誤差評価値を用いた方法が提案されている。 この誤差評価値とは次の式であらわされる(式の表記を変えているが、意味は同じ)。

`Delta_A v_r = (sum_(k=1)^r|((delf)/(delv_k))_(H_(v_k)^(v_r))M(tildev_k)|)epsilon_M`

これを見ただけで頭がくらくらしてくる。解読できるだろうか。 左辺は、関数 `f` を計算するときに得られる値 `v` の絶対(absolute)誤差である。 `v` の添字は、`r` が最終ステップを、`k` が途中ステップを表す。 右辺はどうか。`v_k`と`tildev_k`が出てくるが、`v_k`は式としての`v`の`k`ステップを表すのに対し、 `tildev_k`は計算によって得られた`v_k`を表している。 そして、`H_(v_k)^(v_r)`は`v_k`を極小頂点、`v_r`を極大頂点とする部分計算グラフである(p.130)。 上の式の`((delf)/(delv_k))_(H_(v_k)^(v_r))`は、`f`を`v_k`で偏微分した式に、部分計算グラフ `H_(v_k)^(v_r)` を代入した値、と読めばいいのだろうか。 その値に、`M(tildev_k)` をかけて得られた値の絶対値を`k=1, cdots, r` にかけて足し合わせる、という意味である。 最後に、機械エプシロン `epsilon_M`を乗じれば必要な誤差評価値が得られる。

誤植など

誤植は次の通り。

サンプルプログラム

実際に計算に応用するときには、C++ では演算子オーバローディングの機能を使うと実装が楽である。 そこで、5.5 節「オペレーターオーバローディングの機能を用いた実現」では、 サンプルプログラムが掲載されている。このプログラムは WEB からでもアクセスできて、 http://warbler.ise.chuo-u.ac.jp/AD/ を参照するようにとの指示がある。

なお、もし ADBlock Plus などをお使いの場合は、ハイパーリンクが表示できず「アクセスできて、を参照するように」という表示になっているかもしれない。 この場合は直接 http://warbler.ise.chuo-u.ac.jp/AD/ をコピーペーストして行ってもらいたい。 表示できない原因は AD という文字列がハイパーリンクに含まれているためで、ここの AD は ADvertisement の意味ではなく、 Automatic Differentiation の意味である。

上記ページにはクラスFBU（ボトムアップ）の定義例とクラスFTD（トップダウン）の定義例がある。 bu2.cpp と td2.cpp はともに本に掲載されているリストであるが、現在の C++ コンパイラではコンパイルが異常終了する。 そのため、現在の C++ ではそれぞれ bu2a.cpp と td2a.cpp を使うのがよい。 このうち、bu2a.cpp は問題なくコンパイルできるが、td2a.cpp は異常終了する。td2a.cpp で make すると、 GCC 4.2.1 では次のエラーメッセージが出る。

$ /usr/bin/c++	-c diff.cpp
diff.cpp: In function 'void rdfs(Node*)':
diff.cpp:52: error: 'spread_derivatives' was not declared in this scope
diff.cpp: In function 'void h_rdfs(Node*)':
diff.cpp:55: error: 'h_spread_derivatives' was not declared in this scope
*** Error code 1

第1行から第2行は、ファイルdiff.cpp の関数 'void rdsf(Node*)'における 52 行目のエラーであり、「'spread_derivatives' はこのスコープでは宣言されていない」という意味である。 このエラーを回避するには、50 行に次の宣言を追加する。

同様に、第3行から第4行のエラーを回避するには、53 行に次の宣言を追加する。

関数の作成

丸め誤差の評価のためには、指数部が同じ正の最小の数を与える関数 M(x) を作成する必要がある。 ところが、この関数は具体的な記載がない。C++ プログラムの一例を掲げる。

#include <cmath>
#include "ftd.h" // define ADFLT 

ADFLT M(ADFLT x)
{
	ADFLT man; // mantissa 
	ADFLT norm;
	int exp;	 // exponential
	
	man = frexp(x, &exp);
	man = 0.5; // normalized
	norm = ldexp(man, exp);
	
	return norm;
}

意図は、浮動小数点数 x を指数部と仮数部に分ける関数 frexp と、指数部と仮数部から浮動小数点数を合成する関数 ldexp を使うことにある。 frexp で得られる指数部 man は 0.5 以上 1 未満であることがわかっている。この仮数を 0.5 にすることが M(x) の仕様に合致する。 なお、ADFLT は float, double, long double のいずれもとりうる。 しかし、C++ では多重定義により引数の型を区別すればそれぞれの型に対応した関数が呼び出されるので問題はない。

計算グラフ

計算グラフについては、 ゼロから作るDeep Learning 3 フレームワーク編 で詳しく述べられている。

数式の記述

数式は ASCIIMathML を、 数式表記は MathJax を用いている。

書誌情報

まりんきょ学問所 ＞ コンピュータの部屋 ＞ 久保田 光一、伊理 正夫：アルゴリズムの自動微分と応用