回归直线方程的推导（方程就是二叉树森林）

机器之心专栏

机器之心编辑部

偏微分方程是领域知识的一种简洁且易于理解的表示形式，对于加深人类对物理世界的认知以及预测未来变化至关重要。然而，现实世界的系统过于紊乱和无规律，控制方程往往具有复杂的结构，难以从机理模型中直接推导获得。

研究者们希望通过机器学习方法，直接从高维非线性数据中自动挖掘最有价值和最重要的内在规律（即挖掘出问题背后以 PDE 为主的控制方程），实现自动知识发现。

近日，东方理工、华盛顿大学、瑞莱智慧和北京大学等机构的研究团队提出了一种基于符号数学的遗传算法 SGA-PDE，构建了开放的候选集，可以从数据中直接挖掘任意形式的控制方程。

实验表明，SGA-PDE 不但可以从数据中挖掘到 Burgers 方程（具有交互项），Korteweg–de Vries 方程（KdV，具有高阶导数项），和 Chafee-Infante 方程（具有指数项和导数项），而且还成功挖掘到粘性重力流问题中的具有复合函数的控制方程，以及具有分式结构的方程，而后两者是此前方法难以发现的。SGA-PDE 不依赖关于方程形式的先验知识，填补了复杂结构控制方程挖掘问题的空白。该模型无需提前给定方程候选集，利于自动知识发现算法在未知科学问题中的实际应用。

该研究以《Symbolic genetic algorithm for discovering open-form partial differential equations (SGA-PDE)》为题，于 6 月 1 日发表在 Physical Review Research 上。

目前常见的知识发现思路是利用稀疏回归，即预先给定一个封闭的候选集，然后从中选择方程项，并组合出控制方程，如 SINDy 和 PDE-FIND。但是此类方法要求使用者预先确定方程的大致形式，再将所有对应的微分算子作为候选集中的函数项提前给出，无法从数据中找到候选集中不存在的函数项。最新的一些研究尝试利用遗传算法扩充候选集，但是基因的重组和变异存在较大局限性，依然无法产生复杂结构的函数项（如分式结构和复合函数）

从数据中直接挖掘开放形式控制方程的关键在于以一种易于计算的方式生成并表示任意形式的控制方程，并通过衡量生成的方程与观测数据的符合程度，来评估方程形式的准确性，进而对挖掘的方程进行迭代优化。因此，自动知识发现的核心问题是表示与优化。

表 1. 自动控制方程挖掘方法对比表

表示问题的挑战在于：1. 如何利用有限的基础单元来表示无限的复杂结构控制方程（即开放候选集）；2. 如何构建易于计算的控制方程表示方法。为了能够自由表示任意结构的方程，研究人员将 SGA-PDE 的基本表示单元弱化到了运算元和运算符，并通过符号数学的方法，利用二叉树构建了开放候选集。

优化问题的挑战在于：1. 方程形式与方程评估指标之间的梯度难以计算；2. 开放候选集的可行域是无穷大的，优化过程很难有效兼顾探索（exploration）与利用（exploitation）。为了能够对开放候选集问题高效寻优，研究人员利用一种针对树结构特殊设计的遗传算法实现方程形式的优化。

图 1：自动知识发现问题和 SGA-PDE 示意图

研究人员首先通过细化算法中方程的基本表示单元来表示开放形式的偏微分方程，将方程的表示尺度从独立的函数项层面转化为更基础的运算符和运算元层面。

SGA-PDE 将控制方程中的运算符分为双运算符（如 、-）与单运算符（如 sin、cos），然后将所有潜在变量定义为运算元（如 x、t、u）。研究人员采用二叉树的结构将运算符与运算元组合起来，对不同的方程进行编码。二叉树中所有的终端节点（度为 0 的叶子节点）对应于运算元，所有的非终端节点对应于运算符，其中双运算符对应于度为 2 的节点，单运算符对应度为 1 的节点。

如图 2 所示，通过一种可计算字符串作为连接，任何一个函数项都可以转化为一颗二叉树，同时，满足一定数学规则的二叉树也可以转化为函数项。进而一个具有多个函数项的控制方程等价于一个由多棵二叉树组成的森林。SGA-PDE 通过符号数学的方式，表示任何开放形式的偏微分控制方程。此外，论文中也提出了一种随机生成具有数学含义的二叉树的方法，可以保证生成的二叉树不违背数学原理。

图 2：二叉树与函数项之间的表示和转化方法

由于图 2 所示表示方法能够将函数空间中的样本和二叉树空间的样本一一对应。这意味着基于符号数学的表示方法是有效且非冗余的，可以作为遗传算法中编码过程。研究者提出了一种针对树结构的遗传算法（图 3），从实验数据中自动挖掘符合观测数据的控制方程。这种针对树结构的遗传算法可以实现在不同层面的优化。

重组环节是在森林（方程）层面优化，以找到二叉树（函数项）的最优组合方式。这一环节与当前常见的稀疏回归类方法类似，是在封闭候选集内的寻优。

变异环节是在二叉树（函数项）层面优化，通过随机产生不同的节点属性，找到在给定的二叉树结构下，最优的节点属性组合，本质上是对当前结构的利用（exploitation）。

替换环节同样是在二叉树（函数项）层面优化，但是会产生新的二叉树结构，是对树结构的探索（exploration），实现了完全开放候选集中的优化。

SGA-PDE 通过多层级的优化，可以兼顾二叉树拓扑结构的利用与探索，有利于高效找到最优的方程形式。

图 3：针对树结构的遗传算法

实验数据如图 4 所示，其中第 2 列展示了物理场观测值，是 SGA-PDE 的唯一输入信息。第 3 列和第 4 列中的基础一阶导数可以通过对物理场观测值差分获得。第 1 列为正确的方程形式。实验中 SGA-PDE 采用了相同的预置运算元和运算符，不需要针对具体问题进行调整，以便验证算法的通用性。

最终，SGA-PDE 成功从数据中挖掘到 Burgers 方程，KdV 方程，Chafee-Infante 方程，具有复合函数求导的粘性重力流控制方程，以及具有分式结构的方程。上述方程具有指数项、高阶导数项、交互项、复合函数和嵌套结构等多种复杂形式。

表 2 对比了多种已有算法在上述 5 种算例中的计算结果，可见 SGA-PDE 填补了挖掘复杂结构控制方程的空白

图 4：实验数据图

表 2 自动知识发现算法在不同控制方程挖掘问题中的实验结果

为了更充分地理解 SGA-PDE 的寻优过程，图 5 展示了挖掘 KdV 方程时的演化路径。可见第 1 代产生的最优方程与实际方程相差甚远。在此后演化过程中，随着二叉树的拓扑结构以及节点含义的变异，以及函数项之间的交叉重组，最终在第 31 代找到了正确的解，且此时 AIC 指标已达到文中给定的收敛标准。有意思的是，如果继续优化，则会在第 69 代找到 KdV 方程基于复合函数求导的更加简约的表达形式。图 6 则展示了 SGA-PDE 寻找具有分式结构控制方程的优化过程。

图 5：SGA-PDE 对 KdV 方程的优化过程

图 6：SGA-PDE 对具有分式结构的方程的优化过程

控制方程是对领域知识的一种高效表示形式，然而许多现实问题的方程参数甚至方程形式都不确定，很难写出准确的控制方程，极大制约了领域知识在机器学习中的应用。

SGA-PDE 通过符号数学的方法对方程进行转化，解决了任意形式的偏微分方程的表示问题。此外，SGA-PDE 采用针对二叉树设计的遗传算法，通过对树的拓扑结构以及节点属性的迭代优化，从开放域中自动挖掘符合观测数据的控制方程。在优化中，SGA-PDE 不依赖于方程形式的先验信息，也无需给定候选集，实现了对复杂结构方程的自动寻优。同时，SGA-PDE 也是无梯度算法，避免了方程结构与损失值之间梯度难以计算的问题。

未来研究将关注于：1. 尝试结合强化学习或者组合优化算法；2. 通过嵌入物理机理缩小求解空间；3. 评估并提升 SGA-PDE 对稀疏数据和有噪数据的适用性；4. 将知识嵌入方法与知识发现方法进行融合。

论文链接（可免费获取）：

https://journals.aps.org/prresearch/abstract/10.1103/PhysRevResearch.4.023174

代码与算例数据链接：

https://github.com/YuntianChen/SGA-PDE

,