Python 30行で理解する自動微分（Automatic Differentiation）

 (vmartin.fr)
3 ポイント 投稿者 GN⁺ 2023-08-27 | 1件のコメント | WhatsAppで共有
  • ニューラルネットワーク学習の中核である 自動微分 を、スカラー用 Tensor クラスとして自分で実装し、値の計算と微分の計算が同じ計算グラフ上でどのようにつながるかを示す
  • 通常の Python 変数では z = x + y の結果値しか残らず関係が失われるため、Tensor は値と 演算履歴 をあわせて保存する必要がある
  • Children(a, b, op) と forward() の再帰呼び出しで 二分木の計算グラフ を作り、加算・乗算の再定義によって後から値を入れても式を再計算できる
  • grad(deriv_to) は自分自身に関する微分を 1、別のスカラーに関する微分を 0 とし、基本演算の微分規則を再帰的に適用して 新しい計算グラフ を作る
  • 実装はスカラーしか扱わず遅い可能性があり、配列演算、0 乗算の枝刈り、定数ノード処理、繰り返し計算を減らす キャッシュ が改善課題として残る

通常の Python 変数では関係が失われる

  • x = 3, y = 5, z = x + y のように計算すると、z には結果値 8 しか残らない
  • その後 x や y の値が変わっても、z はどの変数から作られたのか追跡できない
  • 変数同士の関係が残らないため、特定の変数に対する導関数を自動計算するのが難しい

Tensor で演算履歴を保持する

  • 新しい型 Tensor は値（value）を保存し、演算子を再定義して Tensor 同士を計算すると新しい Tensor を返す
  • 初期実装では __add__ だけを再定義し、Tensor(3) + Tensor(5) が T:8 を作れる
  • この段階ではまだ z が x + y の結果だという 演算履歴 を保持できていない

計算グラフと forward()

  • 演算履歴を保持するために Children = namedtuple('Children', ['a', 'b', 'op']) を導入する
    • a: 左側の入力テンソル
    • b: 右側の入力テンソル
    • op: np.add, np.multiply などの実際の演算
  • 各 Tensor は数値だけでなく children も持つことができ、これによって 二分木 形式の計算グラフを構成する
  • forward() は子ノードを再帰的にたどって実際の値を計算する
    • x = Tensor(3), y = Tensor(5) で z1 = x + y, z2 = z1 * y は T:40 になる
    • x = Tensor(None), y = Tensor(None) として先にグラフを作り、後から x.value = 3, y.value = 5 を入れて z2.forward() を呼んでも T:40 を計算できる

自動微分を計算グラフとして作る

  • 自動微分は、Tensor がサポートする各基本演算に微分規則を追加する形で実装する
  • grad(self, deriv_to) は計算グラフを再帰的に巡回し、複雑な関数を単純な関数の組み合わせへと分解する
  • 基本規則は次のとおり
    • テンソルを自分自身で微分すると Tensor(1)
    • 子を持たないスカラーを別のテンソルで微分すると Tensor(0)
    • 加算: (a + b)' = a' + b'
    • 乗算: (ab)' = a'b + ab'
  • z2 = (x + y) * y を y について微分すると、結果 g は単なる値ではなく 偏微分を表す新しい計算グラフ になる
    • 式では g = ∂z2/∂y = x + 2*y
    • x = 3, y = 5 のとき g の値は 13

減算・除算・指数関数まで拡張

  • より複雑な式を扱うために Tensor に減算、除算、指数関数、負値演算を追加する
  • grad() には各演算に対応する微分規則が入る
    • 減算: (a - b)' = a' - b'
    • 除算: (a/b)' = (a'b - ab') / b²
    • 指数関数: exp(a)' = a' * exp(a)
  • forward() も 1 項だけを必要とする演算を処理できるよう変更される
    • 例: exp(a) は 2 番目の項 b を必要としない
    • -x は 0 - x の形で処理する

例の式と Sympy による検証

  • 次の式を Tensor で書き、x, y に関する偏微分を計算する
z = (12 - (x * e^y)) / (45 + x * y * e^-x)
  • コードでは次のように表現する
x = Tensor(3)
y = Tensor(5)
z = (Tensor(12) - (x * y.exp())) / (Tensor(45) + x * y * (-x).exp())
  • 計算された偏微分の値は次のとおり
    • z.grad(x) → T:-3.34729777301069
    • z.grad(y) → T:-9.70176956641438
  • 同じ式を Sympy の diff() と evalf() で計算した結果も一致する
    • xs = 3, ys = 5 で x に関する微分値は -3.34729777301069
    • y に関する微分値は -9.70176956641438

単純な実装の制約と最適化ポイント

  • この実装は最も単純な自動微分システムに近く、同時に非常に遅い可能性がある
  • 現在のクラスは スカラー しか扱わない
    • より実用的なライブラリにするには任意サイズの配列演算を追加する必要がある
  • 計算グラフを見ると、いくつかの最適化が可能である
    • 乗算ノードで子のどちらかが 0 なら、それ以上深く探索する必要はない
    • あるノードとその子が微分対象テンソル x に依存していなければ、そのノードを 定数 とみなして巡回を止められる
    • 同じ演算が繰り返される場合は キャッシュ を置き、同じ計算を何度も実行しないようにできる

関連記事

1件のコメント

 
GN⁺ 2023-08-27
Hacker News の意見

  • こういう小さくてエレガントなコードデモは良い。自分で手を動かしながら概念を理解できるから
    Sasha Rush の GPU Puzzles や Tensor Puzzles も似た例
    https://github.com/srush/GPU-Puzzles
    https://github.com/srush/Tensor-Puzzles

  • これだけで自動微分を完全に理解したと信じるなら、それは自分を欺いている
    グラフが木である場合は、この記事のようにすべてが非常に単純。だが、グラフがより一般的な有向非巡回グラフ、たとえば x = 5; y = 2x; z = xy のようなものになると、実装は依然としてとても単純でも、なぜその実装が正しいのかを理解するのは簡単ではない。「単に普通の連鎖律だ」と考えるなら、それもまた自分を欺いている
    初期の説明の一つは Paul Werbos によるもので、彼は必要な規則を順序付き導関数の連鎖律と呼び、通常の連鎖律から帰納法で証明した。それでも通常の連鎖律からただちに自明に導かれるわけではない。逆だと信じている人がいるなら、間違いだと証明してほしい。そうしてもらえればとても嬉しい

    • それなら、どこでさらに読めばいいのだろうか。autograd、PyTorch、mxnet のようなフレームワークを作った人たちは、どこかで詳しく学んだはずで、その出典が気になる。知る限り mxnet は学術界、おそらく CMU から出てきたものだと思う
    • 正直、こうした議論で人々が何を求めているのかよく分からないし、暗黙の抽象化である順序付き導関数が理想的ではないからなのかもしれない
      計算グラフ、つまり有向非巡回グラフの辺に沿って通常の連鎖律を適用すれば、各段階で正しい値が得られる。必要な追加規則は「1つの変数を計算で複数回使う場合、つまり同じノードから複数の辺が出る、または逆向きに複数の辺が入ってくる場合は、それぞれ計算された勾配を足す」という程度で、これもかなり基本的で直感的だと思う
      たとえば f(x, y) に x と y の両方として z を入れると、d/dz f(z, z) = f_x(z, z) + f_y(z, z) で、下付き文字は偏導関数を意味する。私には、このやり方のほうが、両者を混ぜて「連鎖律を超えるもの」のように見せるよりも数学的にも単純で、実際の実装、特に自分が最も慣れている PyTorch がやっていることにも近く見える
    • 連鎖律は偏導関数について定義されているので、技術的にはそれでも単に連鎖律だと見なせる

  • 自動微分は魔法のように感じる
    多くのコンピュータ科学者がこれに魅了され、より広い観点から手法を紹介する記事を書いている。私の記事もその一つで、演算子オーバーロードなしで複素数を使う「貧者のバリエーション」も含んでいる
    https://pizzaseminar.speicherleck.de/automatic-differentiati...

    • 私が機械学習をしていた1994〜1995年には自動微分を知らず、目的関数を作った教授も解析的な導関数を自分で求めていた。数年前になって初めて知ったのだが、90年代後半に Mathematica を十分に学んで、自分で解析的な導関数を作っていた時間を思うと驚きだった
    • これは2003年の J. Martins、P. Sturdza、J. Alonso による複素ステップ導関数近似にさかのぼるようだ。その論文は読む価値がある
      [0]: https://doi.org/10.1145/838250.838251
    • 本当に魔法のように感じる。似たような方式で書かれた逆伝播の入門資料があれば知りたい

  • 私が作った26行の Python 自動微分実装がある: https://gist.github.com/sradc/d9d66e3898ffe3a02e0b6b266629b0...

    • 短いのは良いが、自分の頭は適度な空白があるとずっとよく働くようだ。こういう別の書き方にも少し慣れる必要がありそう

  • 知識ベース工学システムで使われる手法と非常によく似ていて、そこでは依存関係トラッキングと呼ばれる。ノードやテンソルのキャッシュと組み合わせると計算量を減らせるので、特に大規模なパラメトリック 3D モデルに有用
    値を取得するときに二分木／依存関係ツリーを再帰的に呼び出し、どの変数が変わったかを確認して、必要なものだけを再計算する。__set__、__get__ メソッドを持つカスタム Python オブジェクトと属性を使えば、オブジェクト指向モデルの組み込み機能のようにできる
    x = Tensor(3)
    y = Tensor(5)
    z = x + y
    print(x, y) # 3, 5
    print(z) # 8
    x.value = 4 # 値を設定するときは何も再計算しない
    print(z) # 9, 値を取得する瞬間に変化した依存関係が再計算されるため

  • Andrej Karpathy がautograd エンジンを作る興味深い動画があり、かなり洞察に富んでいる
    https://youtu.be/VMj-3S1tku0?si=wuKhELwOwoYbzpt7
    リポジトリ:
    https://github.com/karpathy/micrograd

  • 私の知っている自動微分の変種は、計算グラフを作りません。代わりに、その値をその場で計算します

    • おそらくフォワードモード自動微分のことを考えているのだと思います。関数の出力次元が比較的大きい場合により有用で、出力次元が比較的小さい場合により有用なリバースモード自動微分とは異なります。
      どちらも動作しますが、状況によって一方のほうが効率的です。「ニューラルネットワークの学習」のような場合は、多くの対象に対して単一の損失出力を最適化することが多いので、通常はリバースモードを使います

  • 自動微分は、単に数値的な連鎖律と呼ぶか、少なくともそう説明してほしいです。文字どおりそれがすべてで、特定の演算でヤコビ行列を明示的に計算しないためのいくつかの工夫が付いている程度なので、そのほうがずっと明確です

    • ここで説明され、バックプロパゲーションの実装で最もよく使われる「autodiff」は逆方向モード自動微分ですが、順方向モードもあり、両極端の間の戦略もあります。結局はどれも連鎖律に帰着しますが、アルゴリズムのレベルでどの方式を選ぶかは決して些細なことではありません。
      実際に計算グラフを通じて勾配を伝播するよう連鎖律を使えと言われたら、ほとんどの人は直感的に順方向モードをデフォルトとして思い浮かべると思います。私もそうするでしょう。
      https://en.wikipedia.org/wiki/Automatic_differentiation#Beyo...
      こうした点を見ると、連鎖律が与える式をたどりながら勾配を蓄積する特定の方法を指す用語として使うのは有用に思えます
    • 技術的には誤りです。数値的な連鎖律は有限差分法を使い、計算を進めるにつれて誤差が蓄積します。
      「他の方法との違い」の節を見るとよいです: https://en.m.wikipedia.org/wiki/Automatic_differentiation
      近くのコメントにもあるように、重要なのは実装が本当に大事で、学ぶ価値があるということです。自動微分を連鎖律を実装する方法の集合だと言うのは構いませんが、「単に」数値的な連鎖律だと言うのは間違いです
    • より正確ではあり得ても、より明確だとは呼ばないでしょう

  • 自動微分は、滑らかな関数の圏におけるヤコビ行列と全微分のデカルトレンズにすぎないのに、何が問題なのでしょうか？ https://www.youtube.com/watch?v=ne99laPUxN4

  • クラス名をTensorと呼ぶ理由が気になります。式やその導関数をテンソルと考える方法があるのでしょうか？ それともスカラーもテンソルであり、これを他のテンソル型までサポートするよう拡張できるからなのでしょうか？

    • 間違っているかもしれませんが、数学的には2次元のオブジェクトを行列、3次元以上のオブジェクトをテンソルと呼ぶのだと思います。
      説明されている自動微分アルゴリズムは任意の高次元オブジェクトに対して動作するので、こうしたオブジェクトをテンソルと呼ぶのは筋が通っているように思います