32 / 90

第 32 日：トポロジカルソート、分岐勾配の累積加算と数値勾配検査トレランス

グラフ巡回と数値検証の習得：深さ優先後順トポロジカルソートの実装、勾配累積加算 (`+=`) による分岐連鎖律の正確な処理、および有限差分法による厳格な gradcheck 検証体系の構築。

数学とアルゴリズム基礎 480 分（8 時間の集中学習）
01 120 分

有向非巡回グラフ（DAG）トポロジカルソートの実装

Agent支援エンジニアリング確認

前提条件

第31日の計算グラフの概念と深さ優先探索（DFS）の基礎。

学習目標

逆伝播において、あるノードの後退処理を実行する前に、そのノードのすべての下流消費ノードからの勾配伝播が完了していなければならない理由と後順巡回トポロジカルソートを理解する。

手順

CLI を使用して分岐共有ノードグラフの構造を確認します:

python3 projects/autograd/cli.py graph --preset shared-node --format ascii

ノード a が加算ノード $(a+b)$ と最終乗算ノード $(a+b) \cdot a$ の双方に供給されていることを観察してください。任意の走査順や単純な幅優先探索では、すべての勾配寄与が到着する前に a._backward() が時期尚早に実行されてしまいます。

演習と予測記録

$f = (a + b) \cdot a$（$a = 3.0, b = 4.0$）について:
1. 根ノード $f$ から開始する深さ優先探索（DFS）の巡回経路をトレースします。
2. 訪問完了順（後順）でノードを列挙します。
3. 反転した逆トポロジカル順序が、根ノード $f$ を最初、加算ノードを中間、葉ノード $a, b$ を最後に並べることを確認します。

独立習得基準

外部のグラフライブラリに頼らず、DFS による後順トポロジカルソートアルゴリズムを自力で実装できること。

公式ソースリソースと権利証跡

linking MIT

micrograd: A tiny scalar-valued autograd engine

著者・提供機関: Andrej Karpathy | オリジナル出所URL ↗

該当セクション・タイムスタンプ: micrograd/engine.py: class Value (_backward closures and backward() topological sort); README 'Example usage'

検証バージョンと日付: commit a9a9f94 (Verified: 2026-10-30)

選定理由:

Clear reference implementation of recursive DFS topological sort for reverse-mode ordering.

ソース前提知識:

Graph traversal fundamentals (DFS/BFS)

安全フォールバック（オフライン回復性）:

Local implementation in projects/autograd/engine.py.

比較対象候補リソースと選定評価 (2)
PyTorch autograd C++ engine ↗ compared_alternative [Modified BSD]

Production scale, but too large and complex for tracing by hand in introductory lessons.

Autograd (HIPS) ↗ compared_alternative [MIT]

Vectorized autograd; micrograd's pure scalar model is pedagogical for hand backprop.

02 120 分

共有ノードの勾配累積加算と多変数連鎖律

独立習得確認

前提条件

多変数微積分の全微分連鎖律（全経路和の公式）およびアクティビティ 32-01。

学習目標

複数経路から参照される変数に対して累積加算 (`+=`) が不可欠である数学的根拠を証明し、代入 (`=`) による上書きが致命的なバグを生む様子を検証する。

手順

共有ノードプリセットに対して順方向および逆方向コマンドを実行します:

python3 projects/autograd/cli.py forward-backward --preset shared-node

$f = (a + b) \cdot a$（$a = 3.0, b = 4.0$）において:
$\frac{\partial f}{\partial a} = 2a + b = 2(3) + 4 = 10.0$ となることを確認します。
逆伝播が双方の分岐経路からの勾配を正しく累積していることを検証してください。

演習と予測記録

$f(a, b) = (a + b) \cdot a$（$a = 3.0, b = 4.0$）とします:
1. $u = a + b$ と置き、$f = u \cdot a$ とします。乗算ステップから $\frac{\partial f}{\partial a}$（直接寄与）と $\frac{\partial f}{\partial u}$ を計算します。
2. 加算ステップ $u = a + b$ から $\frac{\partial u}{\partial a}$ を求め、$a$ への寄与を計算します。
3. $\frac{\partial f}{\partial a} = \frac{\partial f}{\partial u} \frac{\partial u}{\partial a} + \left(\frac{\partial f}{\partial a}\right)_{\text{direct}}$ が $10.0$ となることを示します。
4. 実装で self.grad = ...（代入）を使用した場合に生じる不具合を説明してください。

独立習得基準

多分岐 DAG ノードにおいてなぜ `+=` が必須であるかを数学的に証明し、代入欠陥による数値的な誤りを指摘できること。

公式ソースリソースと権利証跡

linking SIAM Copyright / Academic Linking Only No text extraction or distribution permitted

Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation

著者・提供機関: Andreas Griewank, Andrea Walther | オリジナル出所URL ↗

該当セクション・タイムスタンプ: Section 3.2: Accumulation along Adjoint Graphs

検証バージョンと日付: 2nd Edition, SIAM 2008 (Verified: 2026-10-30)

選定理由:

Mathematical proof showing that total derivative equals the sum of adjoint contributions across all outbound paths.

ソース前提知識:

Multivariate calculus

安全フォールバック（オフライン回復性）:

Self-contained mathematical derivations in activity text.

比較対象候補リソースと選定評価 (2)
micrograd: A tiny scalar-valued autograd engine ↗ compared_alternative [MIT License]

Executable scalar reference implementation the learner later rebuilds; the textbook supplies the formal reverse-mode theory.

Baydin, Pearlmutter, Radul, Siskind: Automatic Differentiation in Machine Learning: a Survey (JMLR 2018) ↗ compared_alternative [JMLR open access]

Broad survey taxonomy of the field; the textbook was selected for its rigorous treatment of reverse-mode complexity.

03 120 分

有限差分法による数値勾配検査 (Gradcheck) とトレランス設計

Agent支援エンジニアリング確認

前提条件

テイラー展開および IEEE 754 浮動小数点丸め誤差の理解。

学習目標

両側中心有限差分法を実装し、適切な相対誤差・絶対誤差トレランス基準を設計し、非微分折点（Kink Point）の数学的特異性を理解する。

手順

複合式の数値勾配検査コマンドを実行します:

python3 projects/autograd/cli.py gradcheck --preset complex

続いて ReLU の折点における検査を実行します:

python3 projects/autograd/cli.py gradcheck --preset relu-kink

出力される相対誤差レポートと折点に関する説明を確認してください。

演習と予測記録

1. 中心差分 $\frac{f(x+h) - f(x-h)}{2h}$ の打ち切り誤差が $\mathcal{O}(h^2)$ であるのに対し、前進差分 $\frac{f(x+h) - f(x)}{h}$ が $\mathcal{O}(h)$ となる理由を説明してください。
2. 浮動小数点演算において、ステップ幅 $h$ を極端に小さく（例: $10^{-20}$）してはならない理由を述べてください。
3. 解析勾配 $g_a = 10.0$ と数値勾配 $g_n = 9.999999999$ の相対誤差を計算し、$\text{rtol} = 10^{-3}$ を満たすか判定してください。

独立習得基準

ステップ幅 $h=10^{-5}$、トレランス $\text{rtol}=10^{-3}, \text{atol}=10^{-5}$ の選定根拠を論理的に説明し、ReLU(0) の折点での挙動の数学的意味を理解していること。

公式ソースリソースと権利証跡

linking BSD-style License

PyTorch Autograd: Numerical Gradient Checking (torch.autograd.gradcheck)

著者・提供機関: PyTorch Core Team | オリジナル出所URL ↗

該当セクション・タイムスタンプ: Finite-difference formula, default tolerances (rtol, atol), and step-size selection

検証バージョンと日付: PyTorch 2.5 (Verified: 2026-10-30)

選定理由:

Widely adopted benchmark for validating analytical autodiff against central difference approximations.

ソース前提知識:

Numerical methods basics and IEEE 754 floating-point awareness

安全フォールバック（オフライン回復性）:

Local gradcheck implementation in projects/autograd/gradcheck.py.

比較対象候補リソースと選定評価 (2)
JAX documentation: Automatic differentiation ↗ compared_alternative [Apache-2.0]

Alternative framework autodiff API; PyTorch gradcheck was selected to match the projects/autograd numerical checks used in the drill.

numdifftools: automatic numerical differentiation ↗ compared_alternative [BSD-3-Clause]

General finite-difference toolkit; PyTorch gradcheck was selected because it integrates directly with the tensor autograd objects the drill verifies.

04 120 分

独立習得確認：トポロジカル順序と数値勾配検証

独立習得確認

前提条件

アクティビティ 32-01 から 32-03。

学習目標

AI支援のない独立環境下で、トポロジカル順序、分岐勾配の累積加算、有限差分数値検査を自力で遂行できることを確認する。

手順

LLMや自動生成ツールを使わず、独立した環境で以下の問題を解いてください。演習草稿エリアに計算プロセスを記録してください。

演習と予測記録

入力 $x = 2.0$ が $y_1 = x^2$ と $y_2 = 3x$ に分岐し、損失が $L = y_1 + y_2$ となる計算グラフを考えます:
1. 解析的導関数 $\frac{\partial L}{\partial x}$ を求めてください。
2. $h = 0.001$ として $x = 2.0$ における中心有限差分勾配を計算してください。
3. 解析勾配と数値勾配の相対誤差を計算してください。

客観的理解度チェック：トポロジー、分岐累積と数値勾配検査

以下の設問に解答して理解度を確認してください。提出前に利用した補助条件を誠実に申告してください。

申告補助条件

注記: AI不使用は誠実な申告条件であり、監視や強制検知ではありません。

1.

計算グラフにおいてノード A がノード B とノード C の双方に入力され、B と C が共に損失 L に接続されている場合、逆伝播はどのような順序で実行される必要がありますか？

2.

ノード a が式の中で 2 回参照され、分岐 1 から $+3.0$、分岐 2 から $+7.0$ の勾配が伝播される場合、実装が self.grad = ...（代入）となっているとどうなりますか？

3.

$\text{ReLU}(x)$ の $x = 0.0$ においてステップ幅 $h = 10^{-5}$ で数値勾配検査を行うと、中心有限差分は $0.5$ を返し、解析自動微分は $0.0$ を返します。この差が生じる本質的な原因は何ですか？

解答根拠と履歴

    独立習得基準

    多分岐勾配 $\frac{\partial L}{\partial x} = 7.0$ を自力で導出し、有限差分法による検証誤差を $10^{-5}$ 以内に収められること。

    公式ソースリソースと権利証跡

    linking Modified BSD

    PyTorch Documentation: Autograd Mechanics

    著者・提供機関: PyTorch Contributors | オリジナル出所URL ↗

    該当セクション・タイムスタンプ: How autograd encodes the history

    検証バージョンと日付: PyTorch 2.5 Documentation (Verified: 2026-10-30)

    選定理由:

    Official reference for computational graph construction, backward pass execution, and in-place mutation pitfalls.

    ソース前提知識:

    Basic understanding of computational graphs and tensors.

    安全フォールバック（オフライン回復性）:

    The training loop mechanics and zero_grad requirements are illustrated with runnable Python code.

    比較対象候補リソースと選定評価 (2)
    TensorFlow tf.GradientTape Documentation ↗ compared_alternative [Apache 2.0]

    Alternative tape-based execution; PyTorch dynamic graph semantics are standard in modern LLM research.

    JAX autodiff cookbook ↗ compared_alternative [Apache 2.0]

    Functional transformations (grad, vjp); PyTorch object-based graph is closer to the beginner micrograd model.

    linking BSD-3-Clause

    SciPy numerical derivative reference

    著者・提供機関: SciPy Developers | オリジナル出所URL ↗

    該当セクション・タイムスタンプ: derivative API: finite differences, step-size iteration, tolerances

    検証バージョンと日付: SciPy documentation, verified 2026-10-30

    選定理由:

    Documents numerical differentiation as an approximation with finite step sizes and stopping criteria.

    ソース前提知識:

    Python arithmetic and the definition of a derivative

    安全フォールバック（オフライン回復性）:

    The local Day 18 tables and pure-Python snippets reproduce the relevant finite-difference behavior without SciPy.

    比較対象候補リソースと選定評価 (2)
    NumPy: numpy.gradient ↗ compared_alternative [BSD 3-Clause License]

    Array-oriented gradient estimation on sampled grids; the SciPy derivative reference matches the pointwise finite-difference helper the exercises implement.

    SymPy Calculus tutorial ↗ compared_alternative [BSD License]

    Symbolic rather than numerical differentiation; useful for exact cross-checks but not the finite-difference practice target.