Simplifying symbolic regression models without simplification rules

Symbolic regression (SR) is a non-parametric technique for finding models that present a good balance between predictive power and model simplicity, and it is usually done with evolutionary algorithms¹. Symbolic regression creates models by using trees to compose a mathematical expression, like so:

SR is suitable when the user wants the final model to be interpretable, but these models don’t always come in their simplest form; there are problems such as overparameterization of models², introns (non-coding parts)³, and semantic redundancies⁴ in the model. Although it is simple for humans to catch many simple cases of these problems at a glance, it is challenging for the computer to simplify these models automatically.

Our recent work⁵ explores a simplification approach based on memoization. By mapping similar expressions to the same hash, we create a table that stores similar expressions in increasing order of size, allowing us to quickly identify simpler and approximately equivalent substitute symbols.

In this post, I will discuss the main idea and then analyze its effects in a case study, focusing on the benefits of memorization as a strategy to learn to simplify.

Background

Many SR algorithms have a simplification step, but a non-linear problem has infinite solutions, and simplifying these models is difficult. Simplifying a model can be as complicated as finding it in the first instance.

Some previous works have formalized different strategies to simplify models. Still, these strategies are not perfect, either because they are simple enough to run fast or because they are so complex that they increase the algorithm’s execution time (or they are so complicated that it is better not to implement them!).

Approach

Instead of defining simplification rules, we can learn them during the algorithm’s execution. This is done by iterating over parts of the models and learning which ones are similar enough to be considered equivalent during runtime.

If we create a map associating these model parts with different keys, we can map similar parts to the same key. If each key saves an ordered list of similar expressions, we can always replace the occurrence of any part with the smallest of the same key. This is where the idea of using LSH comes in, an approximate way of mapping similar objects to the same key.

Note that this depends on having good diversity in the first generations and that the number of individuals and generations is large enough to populate the table with the occurrences. It’s the price you pay for not implementing a single rule!

Locality-Sensitive Hashing (LSH)

Locality-sensitive hashing (LSH) techniques were first introduced by Gionis et al.⁶, and aim to map similar structures to the same hash without worrying too much about the accuracy of the similarity calculation: it is a trade-off between having a faster execution by relaxing the definition of equality of two large structures. This is particularly interesting when we want to work with a very large amount of data, such as when saving several parts of mathematical expressions.

Inexact simplification

Simply put, the inexact simplification algorithm works by mapping similar expressions to the same hash, and retrieving the simplest one when doing the simplification of an expression⁵.

The structure being mapped in our case is the prediction vector of a sub-tree. As we traverse the expression, we calculate its prediction vector for each sub-tree and use it in LSH to obtain a hash. The obtained hash is used in a key-value dictionary, where the value is a list ordered by size — so that there is at least one equivalent expression for each key added to it. When the list is not empty, the first element is used to replace the originating tree. If the list is empty, the tree is inserted as the simplest for that specific hash.

Although it is not necessary to store all occurrences of the same hash in a list, this brings some benefits, such as the possibility of identifying isomorphic trees that were created during execution, doing an analysis of the diversity and redundancy that exists in the data, find insights into data-based simplifications (e.g., a simplification that only makes sense when evaluating the data).

The inexact part comes from the fact that LSH has an stochastic way of mapping similar inputs to the same key, and we also tried to force some collisions (every near-constant prediction vector is mapped to the same hash by multiplying all values by zero if the variance of predictions is smaller than a very low value).

We allow the LSH to store an expression in the hashmap if the difference between the vectors is less than 0.01 (this is what we call tolerance threshold, and it was intended to give the models a small tolerance to numeric rounding, truncating, and calculation differences).

Another example

As a proof of concept, we ran the algorithm for a database with and without simplification and observed the following results.

The simplification led the SR algorithm to find a smaller expression with a better goodness-of-fit on the test data than without simplifying. With only 9 nodes, the simplified tree does not contain any redundancy (such as taking the square root of the square, as the other tree does). It also has one less parameter to adjust, and both models share the same features, which means they rely on the same information to make predictions. Cool!

Takeaways

It is possible to eliminate the task of defining ways to simplify expressions at the cost of relaxing a little on how rigorous we are when making simplifications. This technique is easy to implement and can be pretty convenient for implementations where i) defining simplifications is a tedious and laborious task or ii) it is not known for sure what possible simplifications we can make.

References

• 2024 1
• 2023 2
• 2022 1