💻 computer science

Higher Order Automatic Differentiation of Higher Order Functions

本文通过将前向模式自动微分刻画为一种保持结构的唯一宏，并在微分空间上通过泰勒近似推广至高阶导数的粘合构造来确立其有效性，从而在具有代数数据类型的高阶语言中证明了前向模式自动微分的语义正确性。

原作者： Mathieu Huot, Sam Staton, Matthijs Vákár

发布于 2026-05-07

📖 1 分钟阅读☕ 轻松阅读

原作者： Mathieu Huot, Sam Staton, Matthijs Vákár

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你有一份复杂的蛋糕食谱。这份食谱不仅列出了食材，还包含了其他食谱的指令（例如“先制作糖霜”，然后“在此处使用该糖霜”）。在计算机科学中，这被称为高阶函数：一种将其他函数作为输入（食材）或生成新函数作为结果的函数。

现在，想象你想知道改变一种微小食材（例如多加一撮糖）会如何精确地影响蛋糕的最终口味。在数学中，这被称为求导数。在机器学习和人工智能领域，这一过程被称为自动微分（AD）。它是让计算机通过调整内部设置以最小化误差从而学会学习的引擎。

本文解决了一个非常棘手的问题：当食谱本身由其他食谱构成时，我们如何从数学上证明用于计算这些“口味变化”的计算机代码是正确的？

以下是他们解决方案的分解，使用简单的类比：

1. 问题：高阶函数的“黑箱”

通常，如果你有一个简单的函数（如 $f(x) = x^2$ ），微积分会给我们一个清晰的规则来找到它的斜率（导数）。但是，当你拥有一个将另一个函数作为输入的函数（如一个“食谱生成器”）时，标准微积分就会陷入困惑。这就像试图测量一台制造其他机器的机器的斜率。在传统几何学中，并没有一个单一、公认数学规则来处理这种情况。

作者问道：如果我们编写一个程序来自动计算这些复杂的斜率，我们如何知道它没有欺骗我们？

2. 解决方案：一种新类型的地图（微分空间）

为了解决这个问题，作者需要一种新的方式来可视化这些程序所在的“空间”。

旧地图（流形）： 将其想象成一张标准的地球地图。它非常适合描绘平滑的山丘和山谷，但如果你试图绘制“所有可能地图的空间”，它就会失效。它无法处理“函数是你可以持有并操作的对象”这一概念。
新地图（微分空间）： 作者使用了一个称为微分空间（diffeological spaces）的概念。想象这是一张“超级地图”，它不仅观察表面上的点，还观察你可以在该表面上绘制的所有可能的路径（曲线）。
- 如果你能在一个形状上画出平滑的路径，那么该形状就是“平滑”的。
- 这种方法足够灵活，不仅能处理简单的数字，还能处理列表、选择（例如“如果是这样，那么那样”），甚至是将其他函数作为参数的函数。

3. 方法：“对偶数”翻译器

本文描述了一种称为**宏（macro）**的特定工具。可以将这个宏想象成一个翻译器，它接收你的原始程序并将其重写。

原始程序： “计算这个神经网络的代价。”
翻译后的程序： “计算代价，以及如果你轻微扰动每一个数字，代价会如何变化。”

作者使用一种称为**逻辑关系（Logical Relations）**的技术来证明该翻译器是正确工作的。

类比： 想象你有一个“影子世界”（原始程序）和一个“双重影子世界”（带有导数的程序）。作者创建了一本规则手册（一种关系），规定：“你在影子世界中做出的每一个动作，在双重影子世界中都必须有一个对应的、数学上正确的动作。”
他们证明，无论函数的嵌套变得多么复杂，翻译器始终能保持影子对齐。如果原始程序是平滑的，那么翻译后的程序就能正确计算平滑的变化。

4. “粘合”技巧

为了使证明严谨，他们使用了一种称为**粘合（Gluing）**的数学构造。

类比： 想象你正在用扁平的纸片构建一个 3D 模型。你有“原始”纸片和“导数”纸片。“粘合”就是将它们固定在一起的胶带，确保导数纸片始终以正确的方式附着在原始纸片上。
这种“粘合”后的空间允许他们将原始函数及其导数视为一个单一的、统一的对象。他们表明，他们的翻译器是构建这种胶水的唯一方式，能够保留语言的内部结构。

5. 意外发现：导数并不总是唯一的

最有趣的发现之一是，对于这些复杂的“函数构建”机器，并不总是只有一个正确的导数。

类比： 想象你在开车。“导数”就是你的速度。如果你在直路上行驶，你的速度是清晰的。但是，如果你驾驶一辆制造其他汽车的汽车，可能会有两种不同的方式来定义“速度”，这两种方式对于最终结果都完全有效，即使它们在仪表盘上的显示看起来不同。
作者表明，他们的方法选择了一个特定的、简单的、高效的导数版本。只要它能正确计算最终在现实世界中实际使用的简单数字（一阶函数）的变化，选择哪个“有效”版本并不重要。

总结

简而言之，本文为高级自动微分构建了一个数学安全网。

他们创建了一种新型数学空间（微分空间），能够容纳复杂的、嵌套的函数。
他们证明了他们的代码翻译器（宏）通过展示其与该新空间的规则完美对齐，从而正确计算了这些复杂函数的导数。
他们证明，虽然对于“函数生成器”可能存在多种定义导数的方式，但他们的方法是一个有效、一致且正确的选择，确保了人工智能和机器学习的最终计算是准确的。

他们并没有发明一种训练人工智能的新方法，但他们提供了证明，表明当前使用这些复杂工具训练人工智能的方法在数学上是稳健的。

技术摘要：高阶函数的高阶自动微分

1. 问题陈述

自动微分（AD）是机器学习和科学计算中的一项基础技术，用于计算由程序定义的函数的导数。虽然自动微分对于一阶函数（将实数映射到实数的函数）已得到充分理解，但在处理高阶编程语言中的高阶函数（接受其他函数作为参数或返回其他函数的函数）时，形式化理论存在显著差距。

本文解决的核心挑战有两个方面：

语义鸿沟：传统的微分几何（基于流形）并不天然支持函数空间，这使得为高阶可微程序定义指称语义变得困难。
高阶自动微分的正确性：现有的自动微分方法（特别是前向模式）通常被实现为转换代码的语法宏。虽然这些宏具有组合性，但尚未有严格的语义证明确立它们在包含高阶函数和代数数据类型（如列表和变体）的语言中的正确性。具体而言，高阶函数的“导数”在语义上应意味着什么尚不明确，且语法转换是否保留了正确的数学性质也存疑。

2. 方法论

作者采用指称语义方法，结合逻辑关系和范畴粘合（categorical gluing），对高阶自动微分进行形式化并证明其正确性。

2.1. 语义模型：微分空间（Diffeological Spaces）

为了解决标准流形理论中缺乏函数空间的问题，本文利用微分空间。

定义：微分空间是一个集合，配备了一组选定的“图”（从 $\mathbb{R}^n$ 的开子集到该集合的光滑映射），并满足特定公理（常数映射、光滑预复合和粘合）。
优势：该框架支持函数空间（两个微分空间之间的光滑映射集合本身也是一个微分空间）和归纳类型（如列表），从而允许对整个语言进行组合式解释。
光滑性：作者证明了其语言中每个可定义的表达式在该模型中都被解释为光滑函数。

2.2. 语法转换：泰勒模式自动微分宏

本文定义了一个语法宏转换，记为 $\vec{D}_{(k,R)}$ ，它将程序 $t$ 转换为新程序 $\vec{D}(t)$ 。

高阶导数：该宏不仅仅计算一阶导数（对偶数），而是计算 $(k, R)$ -泰勒近似。这涉及追踪 $k$ 个维度中直到 $R$ 阶的偏导数。
机制：该转换在语言的语法上递归定义（变量、运算、 $\lambda$ -抽象、应用、元组、模式匹配以及像列表这样的归纳类型）。
基本运算：对于原始运算（例如 $+$ 、 $\times$ 、 $\sigma$ ），该宏将它们替换为其 $(k, R)$ -泰勒表示（源自 Faà di Bruno 公式），这些表示计算值以及直到 $R$ 阶的所有偏导数。

2.3. 证明技术：逻辑关系与粘合

为了证明正确性，作者使用了逻辑关系论证，随后将其重构为范畴粘合。

逻辑关系：他们定义了一个关系 $S_\tau$ ，连接类型 $\tau$ 的语义解释与其转换后类型 $\vec{D}(\tau)$ 的解释。该关系将光滑函数 $f$ 与其泰勒表示联系起来。
基本引理：他们证明了如果输入由 $S$ 关联，则程序的输出和转换后程序的输出也由 $S$ 关联。这确立了宏能正确计算导数。
范畴粘合：逻辑关系被形式化为“粘合空间”（ $Gl_k$ ）范畴，其中的对象是三元组 $(X, X', S)$ ，分别表示一个空间、其导数空间以及它们之间的关系。在此设定下，自动微分宏被证明是一个唯一的保结构函子。

3. 主要贡献

高阶自动微分的指称语义：本文提供了首个使用微分空间对具有代数数据类型的高阶语言的指称语义，证明了所有可定义函数都是光滑的。
高阶自动微分的正确性证明：它提出了一个严格的证明，表明前向模式自动微分宏 $\vec{D}_{(k,R)}$ 能正确计算任何可定义函数的 $(k, R)$ -泰勒表示，即使该函数涉及高阶构造。
范畴刻画：作者将自动微分宏刻画为在给定基本运算导数选择下的唯一保结构函子（一种“粘合”构造）。这为自动微分提供了一个通用性质。
扩展到归纳类型：该方法被扩展以涵盖变体类型和归纳类型（特别是列表），证明了自动微分可应用于操作复杂数据结构的程序。
非唯一性分析：本文研究了高阶函数的导数，并证明与一阶函数不同，高阶函数的语义导数不一定唯一。语法宏选择了一个有效的导数，但存在其他在语义上同样正确的导数。

4. 结果

定理 4.3（有限正确性）：对于任何类型为 real 的项 $t$ （即使是用高阶函数定义的），转换后项 $\vec{D}(t)$ 的解释是 $t$ 的解释的 $(k, R)$ -泰勒表示。
定理 6.6（完全正确性）：该结果被推广到所有一阶类型（例如 list(real)、real -> real）。语法转换与流形上的 $(k, R)$ -切丛函子一致（模去典范同构）。
非唯一性（第 7 节）：作者通过反例（求值函数）表明，高阶函数可能存在多个不同的语义导数。自动微分宏选择了一个特定的导数，但只要所选导数能对一阶函数产生正确结果，语义并不强制唯一的选择。

5. 意义与主张

本文声称实现了两个主要目标：

组合式理解：它提供了可微编程的组合式指称理解，弥合了自动微分的语法运算与微分几何数学理论之间的鸿沟。
形式正确性：它提供了高阶自动微分为何有效的形式化解释，从经验观察转向基于逻辑关系和粘合构造的语义证明。

作者强调，他们的方法在高阶导数的唯一性方面是适度的。他们认为，在编程实践中，为高阶函数选择特定导数并不重要，重要的是确保导数能正确传播到最终计算的一阶函数。语义允许导数非唯一这一事实，被框架化为一种体现编程实用灵活性的特性，而非缺陷。

这项工作将先前关于一阶自动微分的研究（例如 [HSV20a]）扩展到高阶导数和高阶函数，为在函数式语言中计算高阶导数（泰勒模式自动微分）的工具提供了理论基础。它并未声称解决实现效率问题（如反向模式优化），但确立了前向模式方法的语义正确性。