Is the equation a binary tree forest? Discover unknown governing equations and physical mechanisms directly from data

Researchers hope to use machine learning methods to automatically mine the most valuable and important intrinsic laws directly from high-dimensional nonlinear data (that is, to mine the PDE-based governing equations behind the problem) to achieve automatic knowledge discovery.

Recently, research teams from Eastern Institute of Technology, University of Washington, Ruilai Intelligence, and Peking University have proposed a genetic algorithm SGA-PDE based on symbolic mathematics, constructing an open candidate set that can extract data from data. Directly mine arbitrary forms of governing equations.

Experiments show that SGA-PDE can not only mine the Burgers equation (with interaction terms), the Korteweg–de Vries equation (KdV, with higher-order derivative terms), and the Chafee-Infante equation (with exponential terms) from the data terms and derivative terms), and also successfully mined the governing equations with composite functions and equations with fractional structures in the viscous gravity flow problem, the latter two of which were difficult to discover with previous methods. SGA-PDE does not rely on prior knowledge about the equation form and fills the gap in complex structure control equation mining problems. This model does not require a candidate set of equations to be given in advance, which is beneficial to the practical application of automatic knowledge discovery algorithms in unknown scientific problems.

The study was titled "Symbolic genetic algorithm for discovering open-form partial differential equations (SGA-PDE)" and was published in Physical Review Research on June 1.

The current common knowledge discovery idea is to use sparse regression, that is, pre-given a closed candidate set, then select equation terms from it, and combine the governing equations, such as SINDy and PDE-FIND. However, this type of method requires the user to determine the rough form of the equation in advance, and then provide all corresponding differential operators as function terms in the candidate set in advance. It is impossible to find function terms that do not exist in the candidate set from the data . Some of the latest research attempts to use genetic algorithms to expand the candidate set, but there are major limitations in gene recombination and mutation, and it is still unable to generate complex structural function terms (such as fractional structures and composite functions)

The key to mining open-form governing equations directly from data is to generate and represent arbitrary forms of governing equations in a way that is easy to compute, and to evaluate the accuracy of the equation form by measuring how well the generated equations fit the observed data. properties, and then iteratively optimize the mined equations. Therefore, the core issues of automatic knowledge discovery are representation and optimization.

Table 1. Comparison table of automatic control equation mining methods

The challenge of expressing the problem is:

1. How to use Limited basic units to represent infinite complex structural control equations (i.e., open candidate sets);2. How to construct an easy-to-compute control equation representation method. In order to freely express equations of any structure, the researchers weakened the basic representation unit of SGA-PDE to operands and operators, and used symbolic mathematics to construct an open candidate set using binary trees.

The challenges of the optimization problem are:

1. The gradient between the equation form and the equation evaluation index is difficult to calculate; 2. The feasible domain of the open candidate set is infinite, and the optimization process It is difficult to effectively balance exploration and exploitation. In order to efficiently optimize the open candidate set problem, the researchers used a genetic algorithm specially designed for tree structures to achieve optimization in the form of equations.

Figure 1: Schematic diagram of automatic knowledge discovery problem and SGA-PDE

The researchers first refined the basics of the equations in the algorithm Representation units are used to represent open-form partial differential equations,

transforming the representation scale of equations from the level of independent function terms to the more basic level of operators and operands.

SGA-PDE divides the operators in the control equation into double operators (such as, -) and single operators (such as sin, cos), and then defines all potential variables as operands (such as x, t, u ). Researchers use the structure of a binary tree to combine operators and operands to encode different equations. All terminal nodes (leaf nodes with degree 0) in the binary tree correspond to operands, and all non-terminal nodes correspond to operators. Double operators correspond to nodes with degree 2, and single operators correspond to nodes with degree 1. .

As shown in Figure 2, through a computable string as a connection, Any function term can be converted into a binary tree, and at the same time, satisfies certain mathematical rules Binary trees can also be converted into function terms. Furthermore, a governing equation with multiple function terms is equivalent to a forest composed of multiple binary trees. SGA-PDE represents any open-form partial differential governing equation through symbolic mathematics. In addition, the paper also proposes a method to randomly generate binary trees with mathematical meaning, which can ensure that the generated binary trees do not violate mathematical principles.

Figure 2: Representation and transformation method between binary tree and function terms

Because the representation method shown in Figure 2 can There is a one-to-one correspondence between samples in the function space and samples in the binary tree space. This means that the representation method based on symbolic mathematics is efficient and non-redundant and can be used as the encoding process in the genetic algorithm. The researchers proposed a genetic algorithm for tree structures (Figure 3) to automatically mine control equations consistent with observed data from experimental data. This genetic algorithm for tree structures can achieve optimization at different levels.

The reorganization link is to optimize

at the forest (equation) level to find the optimal combination of binary trees (function terms). This link is similar to the current common sparse regression method, which is optimization within a closed candidate set.

The mutation link is optimized at the binary tree (function term) level

. By randomly generating different node attributes, we find the optimal combination of node attributes under a given binary tree structure. Essentially It is an exploitation of the current structure.

The replacement process is also optimized at the binary tree (function item) level

, but it will generate a new binary tree structure, which is an exploration of the tree structure and achieves a completely open candidate set. optimization. SGA-PDE can take into account the utilization and exploration of binary tree topology through multi-level optimization, which is conducive to efficiently finding the optimal equation form.

Figure 3: Genetic algorithm for tree structure

The experimental data is shown in Figure 4, in which the second column shows Physical field observations,

are the only input information

of SGA-PDE. The underlying first derivatives in columns 3 and 4 can be obtained by differencing the physical field observations. Column 1 is the correct form of the equation. In the experiment, SGA-PDE uses the same preset operands and operators, and does not need to be adjusted for specific problems in order to verify the versatility of the algorithm. Finally, SGA-PDE successfully mined the Burgers equation, KdV equation, Chafee-Infante equation, viscous gravity flow governing equations with composite function derivation, and equations with fractional structure from the data. The above equation has many complex forms

such as exponential terms, higher-order derivative terms, interaction terms, composite functions and nested structures.

Table 2 compares the calculation results of various existing algorithms in the above five calculation examples. It can be seen that SGA-PDE fills the gap in mining the control equations of complex structures

Figure 4: Experimental data graph

Table 2 Experimental results of automatic knowledge discovery algorithm in different control equation mining problems

In order to more fully understand the search of SGA-PDE Optimization process, Figure 5 shows the evolution path when mining the KdV equation. It can be seen that the optimal equation generated by the first generation is far from the actual equation. In the subsequent evolution process, with the changes in the topological structure of the binary tree and the meaning of the nodes, as well as the cross-recombination between function terms, the correct solution was finally found in the 31st generation, and at this time the AIC index has reached the convergence given in the article standard. Interestingly, if the optimization is continued, a more parsimonious expression of the KdV equation based on the derivation of a composite function is found at generation 69. Figure 6 shows the optimization process of SGA-PDE to find the governing equations with fractional structure.

Figure 5: SGA-PDE optimization process of KdV equation

Figure 6: SGA-PDE optimization process for equations with fractional structure

Control equations are an efficient representation of domain knowledge. However, the equation parameters and even equation forms of many real-world problems are Uncertain, it is difficult to write accurate control equations, which greatly restricts the application of domain knowledge in machine learning.

SGA-PDE transforms equations through symbolic mathematics and solves the representation problem of arbitrary forms of partial differential equations. In addition, SGA-PDE uses a genetic algorithm designed for binary trees, and automatically mines control equations consistent with observation data from the open domain through iterative optimization of the tree's topology and node attributes. In optimization, SGA-PDE does not rely on prior information in the form of equations, nor does it need to be given a candidate set, realizing automatic optimization of complex structural equations. At the same time, SGA-PDE is also a gradient-free algorithm, which avoids the problem of difficult calculation of the gradient between the equation structure and the loss value.

Future research will focus on: 1. Try to combine reinforcement learning or combinatorial optimization algorithms; 2. Reduce the solution space by embedding physical mechanisms; 3. Evaluate and improve the applicability of SGA-PDE to sparse data and noisy data. nature; 4. Integrate knowledge embedding methods and knowledge discovery methods.

Paper link (available for free):

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

Code and example data Link:

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

The above is the detailed content of Is the equation a binary tree forest? Discover unknown governing equations and physical mechanisms directly from data. For more information, please follow other related articles on the PHP Chinese website!