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.