エキサイト公式　エンジニアブログ

こんにちは、TS部の藤田です。
さて、本日は12/24ということで、俗に言うクリスマスイブであります。
クリスマスイブというのは、

リア充な人々が集まり、KFCのチキンと不二家のホールケーキを食べながら、酒をのみ、いつもより浮かれてハイになる日の前日。もしくは、恋人同士がいつも以上にいちゃつく日。神の子とされるキリストが馬小屋で生まれた日の前日でもある。

と、私の中の辞書には書いてあります。
そんなんでありますから、本日このブログを見ている方はリア充でないか、よっぽどなにか特別な理由があってこのプログを閲覧されているのかと思います。
いずれにせよ、見ている人などほとんどいないのですから、どうせなら最低PVを獲得してやれ！ってことで、たぶん誰も関心のないネタを書きます。
ちなみに、私にとって24、２５日は普通の日なので、特段なにかするわけでもなく、特別な感情があるわけでもなく、いたってニュートラルです。

さて、タイトルにある内容を説明するにあたって、まず自動微分について軽く触れたいと思います。

自動微分(Automatic Differentiation: AD)とは、計算グラフ中の変数の微分値を求める計算機科学的な数値計算手法のことです。
何を言っているのか自分でも分からないので例をあげると、
以下のような式において、\(x_1\)、\(x_2\)についての微分を行うケースを考えます。
\[ y = x_{1}x_{2} + sin(x_{1}) \]
これら２つの変数の微分値は単純な式であることから直ちに以下のように解析的に求めることができるかと思います。
\[\frac{\partial y}{\partial x_1} = x_2 + cos(x_1) \\\frac{\partial y}{\partial x_2} = x_1\]
しかし、あえてここで微分の連鎖率(Chain Rule)の観点から解を得る方法を説明してみます。
Wikipediaによい解説が載っているので、そちらの内容ベースに話しを進めます。(WikipediaではForward, Backward型２種類の自動微分について述べていますが、本記事ではBackward型の説明だけになります。)

\( y\)についての微分は中間変数\(w_i\)を用いることにより、以下のように展開できます。展開された式にあるとおり、より上位の中間変数から下位の中間変数へ(下の式では、右から左へ)それぞれの微分値を順番に掛けていき、最下位の変数までたどり着くと、すべての変数の微分が完了していることになります。これが微分の連鎖率です。
\[\frac{\partial y}{\partial x} = \frac{\partial y}{\partial w_{1}} \frac{\partial w_{1}}{\partial x} = \biggl(\frac{\partial y}{\partial w_{2}}\frac{\partial w_{2}}{\partial w_{1}} \biggr) \frac{\partial w_{1}}{\partial x} = \biggl(\biggl(\frac{\partial y}{\partial w_3} \frac{\partial w_3}{\partial w_2}\biggr)\frac{\partial w_2}{\partial w_1}\biggr)\frac{\partial w_1}{\partial x} = \cdots \]
これを計算機上で動くように実装したものが後退型自動微分(Reverse Accumulation AD)です。つまり、数学で言うところの微分の連鎖率や合成関数の微分と、コンピューターサイエンスで言うところの後退型自動微分は本質は全く同じものです。微分の連鎖率については学校の授業で習うということや、数式で簡潔に説明できることからネットに情報が多いですが、その実装である後退型自動微分について解説している日本語の情報は少ないように感じます。
中間変数の微分値を\(\bar{w_i}\)とおいた場合に、上記の例に微分の連鎖率を適用すると以下のようになります。
(式だけだとわかりづらいので下の図や上記のwikipediaにある図を参照ください)
\[\bar{w_5} = 1 \tag{1}\]\[\bar{w_4} = \bar{w_5} \frac{\partial w_5}{\partial w_4} = \bar{w_5} \cdot 1 \tag{2}\]\[\bar{w_3} = \bar{w_5} \frac{\partial w_5}{\partial w_3} = \bar{w_5} \cdot 1 \tag{3}\]\[\bar{w_2} = \bar{w_3} \frac{\partial w_3}{\partial w_2} = \bar{w_3}w_1 \tag{4}\]\[\bar{w_1}^a = \bar{w_4} cos(w_1) \tag{5}\]\[\bar{w_1}^b = \bar{w_3}w_2 \tag{6}\]\[\bar{x_1} = \bar{w_1}^a + \bar{w_1}^b = cos(x_1) + x_2 \tag{7}\]\[\bar{x_2} = \bar{w_2} = x_1 \tag{8}\]
直感的にすぐに解を計算できることを考えると、ずいぶん回りくどい感じではありますが、微分の連鎖率の観点からも解を求められることは分かりました。あとはコードに落とします。
上記で見てきたように、後退型自動微分はまず、全部の順計算(Forward)の手順を覚えておき、その逆方向に微分を計算していきます(Backward)。そのためにはメモリ上にForward時の計算グラフを正確に保存し、後で逆に辿れる仕組みを構築する必要があります。その場合、各演算(ここでは、足し算、掛け算、sin)を全て関数として定義しておくと、変数が関数を通り新たに変数が生まれ、その変数がまた別の関数を通るを繰り返すことにより、上記の図のように鎖のようにつながった計算グラフを構築でき都合がよいです。
そのためには、プログラミング言語のプリミティブな変数だけでは役不足です。以下のように仮想の変数を定義します。
(以下コードブロックはC++で説明)

class Variable {
public:
    float data;
    float grad;
    Function *parent_func = NULL;
    Variable(float d);
    void backward();
    void backward(Variable *v);
    void zero_grads();
};

dataはForwardの結果を納める変数、gradはBackwardの結果の微分値を納める変数です。
parent_funcは自分自身を生み出した関数へのポインターです。ここはあとで詳しく述べます。さらに、各演算に当たるクラスを以下のように定義します。

class Function {
public:
    vector inputs;
    Function();
    Variable *forward(Variable *v1);
    Variable *forward(Variable *v1, Variable *v2);
    void backward(float parent_grad);
    virtual  Variable *forward(vector &inputs);
    virtual void backward(float parent_grad, vector &inputs);
};
class Sin : public Function {
public:
    Sin();
    Variable *forward(vector &inputs);
    void backward(float parent_grad, vector &inputs);
};
class Plus : public Function {
public:
    Plus();
    Variable *forward(vector &inputs);
    void backward(float parent_grad, vector &inputs);
};
class Mul : public Function {
public:
    Mul();
    Variable *forward(vector &inputs);
    void backward(float parent_grad, vector &inputs);
};

基底クラスFunctionの中身は以下のようになります。

Variable *Function::forward(Variable *v1){
    inputs.push_back(v1);
    forward(inputs);
}Variable *Function::forward(Variable *v1, Variable *v2){
    inputs.push_back(v1);
    inputs.push_back(v2);
    forward(inputs);
}

void Function::backward(float parent_grad){
    backward(parent_grad, inputs);
}

基底クラスのforward, backward関数が行なっていることはシンプルです。
forward関数は、一つまたは二つの変数Variableを受け取り、継承クラスで定義されたforward関数にその値を渡します。
backward関数は、微分の連鎖率においての上位の微分値を受け取り、継承クラスで定義されたbackward関数にその値を渡します。
継承クラス、例えば、積を担当するクラスであるMulの中身は以下のようになります。

Variable *Mul::forward(vector &inputs){
    Variable *v1 = inputs[0];
    Variable *v2 = inputs[1];
    Variable *r = new Variable(v1->data * v2->data);
    r->parent_func = this;
    return r;
}

void Mul::backward(float parent_grad, vector &inputs){
    Variable *v1 = inputs[0];
    Variable *v2 = inputs[1];
    v1->grad += parent_grad * v2->data;
    v2->grad += parent_grad * v1->data;
}

forward関数は、変数二つを受け取り、積を計算した後、その計算結果を別途確保したVariableに埋め込んで返します。その際、関数自身のポインター(this)をその変数のparent_funcにセットしておきます。これによって、VariableとFunctionの関係を保ち、鎖のように繋がった計算グラフが構築されます。
backward関数は、forward時と同じ変数二つを受け取り、それぞれの変数についての微分(偏微分)を求めて、変数の微分値を保存する変数gradに加えます。その際、上位レイヤーから渡ってきた微分値parent_gradを掛けています。注意すべき点は、gradに計算した微分値を”足し算”しているところです。先に書いた計算式において、\(x_1\)のようにForward時に分岐する変数がある場合、Backward計算式においては、分岐の数だけ微分値が足し合わされることになるためです。ちなみに、足し合わせをしている関係で、各変数の微分値はBackward開始時にあらかじめ、ゼロで初期化されている必要があります。これと同様に他の必要な関数(Sin, Plus)を定義します。

Variable *Sin::forward(vector &inputs){
    Variable *v1 = inputs[0];
    float s = std::sin(v1->data);
    Variable *r = new Variable(s);
    r->parent_func = this;
    return r;
}

void Sin::backward(float parent_grad, vector &inputs){
    Variable *v1 = inputs[0];
    v1->grad += parent_grad * std::cos(v1->data);
}

Variable *Plus::forward(vector &inputs){
    Variable *v1 = inputs[0];
    Variable *v2 = inputs[1];
    Variable *r = new Variable(v1->data + v2->data);
    r->parent_func = this;
    return r;
}

void Plus::backward(float parent_grad, vector &inputs){
    Variable *v1 = inputs[0];
    Variable *v2 = inputs[1];
    v1->grad += parent_grad * 1.0;
    v2->grad += parent_grad * 1.0;
}

次に、Backward時の計算グラフを辿る心臓部と言える部分を見ていきます。
それはVariableクラス内に定義するのがスマートでしょう。

void Variable::backward(){
    this->grad = 1;
    this->backward(this);
}

void Variable::backward(Variable *v){
    if (v == NULL) return;
    if (v->parent_func != NULL) {
        v->parent_func->backward(v->grad);
        for (int i = 0; i< v->parent_func->inputs.size(); i++) {
            Variable *nv = v->parent_func->inputs[i];
            this->backward(nv);
        }
    }
}

void Variable::zero_grads() {
    this->grad = 0;
}

引数なしのbackwardは、計算の最後に出力されたVariableから呼ばれる関数です。上記の計算例でいうところの\(w_5\)を担当する部分です。
シードとして\(1\)を与え、引数ありのbackwardに自分自身(this)を渡します。
引数ありのbackwardは、引数で与えられたVariableとそれを生み出した関数Functionのbackward関数に自身の微分値gradを指定して、関数に入力のあった変数の微分値を計算します。
その後のfor文にて、その関数に入力のあった変数を順にVariableのbackward関数に通すことによって、再帰的に処理していきます。変数またはそれと紐づく関数がNULLであったら、処理を停止します。
このようなVariableとFunctionを組み合わせた単純な仕組みで、計算グラフの構築、およびForward, Backwardの計算を行うことができます。
最後に使用例、上記の計算例を後退型自動微分してみます。

    Variable *x1 = new Variable(2);
    Variable *x2 = new Variable(5);
    Function *sin = new Sin();
    Function *plus = new Plus();
    Function *mul = new Mul();
    Variable *r = plus->forward(mul->forward(x1, x2), sin->forward(x1));
    x1->zero_grads();
    x2->zero_grads();
    r->backward();
    cout << "x1->grad:" << x1->grad << endl;
    cout << "x2->grad:" << x2->grad << endl;

・２つの変数にそれぞれ、2, 5をセットします(値は適当)。
・使用する関数を生成します。（sin, plus, mul）
・まず、forwardを使用して順計算を行います。
・逆計算を行う前に、すべての変数の微分値をゼロに初期化します。
・backwardにて逆計算を実行します。
・最後に、変数x1, x2の微分値を出力します。


いかがでしたでしょうか？けっこう単純な仕組みで後退型自動微分を実装できることが分かると思います。
今回はスカラーを対象として説明しましたが、数値計算するうえで実用を考えるとベクトルや行列での計算ができるようになっている必要があるかと思いますが、基本的には全く同じ方針で実装できます。
また、今回用意したコードはメモリー管理をちゃんと考えて実装していません。とくにFunctionのforward関数内で確保したVariable用のメモリーは関数内で確保し、その後関数外で使ってますので解放のタイミングが難しく、そのままにしておくとメモリーリークとなってしまう典型例かと思います。しっかり実装する段階では、たとえばC++ですとデフォルトでGCが組み込まれていない言語なので、別途スマートポインターを利用するなどが必要になってくるかと思います（ポインターをプログラマーが管理しながらの実装はたぶん破綻します）。
さらに、再帰処理が必要な場合は単純な変数と関数のチェーンだけでは実現できず一工夫必要になってきます。計算の効率化を考えるのであれば例えばGPUを利用した並列計算のためのプログラミングも必要になります。

馴染みのない方からは、こんなものが何の役に立つのかというご指摘もあるかと思います。ごもっともです。この機能単体で何かすごく役に立つということは考えづらいでのですが、近年では数値計算を要する機械学習、とりわけニューラルネットワーク(NN)の学習時の勾配計算において一次微分を利用することが一般的となっており、複雑なネットワークの学習において、Forwardだけ定義すればあとは自動で勾配を計算できることには大きなメリットがあるのです。したがって、近年のNNのフレームワークは、だいたいこの後退型自動微分が実装されています。数十、数百もある変数の微分を実装者が記述するのはもう現実的でありません。実装者は微分がどのように行われているかなど知らなくてよいのです。
このように地味であまり語られることのない自動微分ですが、近年のテクノロジーを支える縁の下の力持ちであることは間違いありません。

ここで、だいぶ前置きが長くなってしまったので、そろそろ本題に入りたいと思います。
タイトルのとおり、自動微分とサンタクロースの共通点はまさに、縁の下の力持ちであるという点です。
ある家庭の子供が書いたサンタへの購入代行依頼申請です。

さんたさんへ
くりすますにほしいのは○○すとろんぐあーむです。れんしゃきっとです。さんたさん、だいすきです。さんたさん、ぷれぜんとたのしみにしています。たまがはこのよこに１２ぱつぐらいついているのをかってください。

最近のちびっこは相手が誰であろうと、媚を売ることを忘れません。
これを見たサンタは、まずイオンなどで現物を確認し、アマゾンで安く買えないか調べ、購入し、届いた際に「あれっ？なにそれー？」のしつこいツッコミに、「えっ、会社で使うやつだよ」とかごまかし、クローゼットの奥にしまい込み、２４日の深夜に枕元にそっと置いておく。朝になって喜んでる彼らに「やっぱりちゃんとサンタさんプレゼントくれたねー」とか気を使って会話したり。
子供からすると、申請書をすぐそばのツリーにぶら下げておくだけで、期日通りにプレゼントが届く。その舞台裏でのサンタの努力など知る余地もないのです。まさにその存在はテクノロジー界における自動微分と一緒じゃないですか！この社会現象のために毎年多くの見えないエネルギーが費やされているのですよね。