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 | 原始出處連結 ↗

對應章節 / 時間戳: 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。

學習目標

從數學上證明為何多路徑消費變數必須使用累加 (`+=`)，並示範直接賦值 (`=`) 如何造成嚴重的隱蔽梯度覆蓋 Bug。

操作指引

執行分叉節點預設的前向與反向指令：

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 = ...（覆蓋賦值）會導致什麼錯誤結果。

獨立掌握標準

學習者能夠證明多元鏈式法則為何要求 `+=` 累加，並在理論和數值上指出賦值缺陷的後果。

權威來源資源與權利證明

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

Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation

作者 / 機構: Andreas Griewank, Andrea Walther | 原始出處連結 ↗

對應章節 / 時間戳: 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 | 原始出處連結 ↗

對應章節 / 時間戳: 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 輔助的獨立條件下，驗證拓撲排序、分叉累加推導與數值梯度差分計算的完整掌握度。

操作指引

請在無大型語言模型、無自動程式碼生成輔助的獨立條件下完成下列推導。在實作草稿區寫下詳細計算過程。

自主實作與記錄

考慮計算圖：輸入 $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 在計算圖中被引用了兩次，分支 1 貢獻梯度 $+3.0$，分支 2 貢獻梯度 $+7.0$。若程式碼錯誤寫成 self.grad = ...，最終 a.grad 會發生什麼？

3.

在對 $\text{ReLU}(x)$ 在 $x = 0.0$ 處進行數值梯度檢驗時，設定步長 $h = 10^{-5}$，為什麼中心有限差分返回 $0.5$，而解析自動微分返回 $0.0$？

作答應證與歷史記錄

    獨立掌握標準

    獨立推導得出多分叉梯度 $\frac{\partial L}{\partial x} = 7.0$，並完成有限差分數值檢驗，誤差在容差範圍之內。

    權威來源資源與權利證明

    linking Modified BSD

    PyTorch Documentation: Autograd Mechanics

    作者 / 機構: PyTorch Contributors | 原始出處連結 ↗

    對應章節 / 時間戳: 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 | 原始出處連結 ↗

    對應章節 / 時間戳: 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.