tl;dr - They model operations (e.g. multiply, add, cosine, sqrt) as tokens, and use a transformer to predict a recursive function from (incomplete) integer sequences (and float sequences, separately).
This is not dissimilar from e.g. DALL-E where they model images as NLP-style tokens and use a transformer to predict image tokens (operations, respectively) from text tokens (list of ints/floats, respectively).
This demo lets you interact with the model. Pretty cool stuff. Refreshing to see symbolic problems being tackled with deep learning.
It is a deterministic algo for SR that I've always thought would benefit from RL.
The biggest problem is SR research has been and still is the lack of a widely used dataset and reproducible results. There is a researcher who beats everyone's results within a year by publishing to Springer without code or data...
The goal of the paper was not to get the best pattern fitter, but to see if it's even possible to do symbolic regression with a simple token-to-token prediction method.
If I enter the sixteen terms of the sequence A003742 it does not find the exact recurrence equation (with six terms). About twenty years ago, I wrote a program that did find this recurrence equation just from the sequence. If I enter these numbers at http://www.ryanhmckenna.com/2015/06/automatically-finding-re... it gives the exact recurrence equation within a few seconds.
Sort of a shallow dismissal, wouldn't you say? These models are for research purposes and the authors aren't claiming to have solved this to the degree of a hand-crafted program. In fact, they probably used a program very similar to the one linked in order to create the dataset.
`1,1,2,3,5` gets the result "No Solution" whereas `1,1,2,3,5,8` correctly guesses the pattern. Its just a linear recurrence with j=2 which means you get 2 data points to guess the relation and 1 to confirm.
Hmmm. I can't get the model to recognize a damped sinusoidal wave (10, 0, -10, 0, -5, 0, 5, ...). Does the model have the capacity to express such a function?
Looks like it fails quite hard for "natural" sequences. I input the Bitcoin price and I got some ridiculous zigzag around a constant instead of say, a power law fit.
To clarify as some people have mismatched expectations, the authors mention viability for real-world applications in the paper:
"One may ask to what extent our model can be used for real-world applications, such as time-series forecasting. Although the robustness to noise is an encouraging step in this direction, we believe our model is not directly adapted to such applications, for two reasons.
First, because real-world data generally cannot be
described by neat mathematical equations, in which
case numeric approaches will outperform symbolic
approaches. Second, even in cases where the sequence
is described by a formula, this formula will often con-
tain complex prefactors. While our method is capable
of approximating prefactors rather remarkably, this
adds a layer of difficulty to the original problem, as
the model sometimes needs to use many operators
to approximate a single prefactor (see Table 2). However, one easy way to solve this issue is to extend
the vocabulary of the decoder, enabling it to build
prefactors more easily, or use a separate solver to fit
the prefactors as done in approaches. We leave this
for future work."
Since data from real-world phenomenon have noise in it, wouldn't it be useful to add a "noise" term to the recovered formula? The weight (importance) of the noise term could be adjusted: Low noise would lead to symbologic regression with his structural complexity. High noise would lead to simpler models. In ML, the choice of the noise would be a hyperparameter, determined through minimizing uncertainty on held-out data.
I changed the 13 in the Fibonacci sequence to 14 just to see what it would do.
It added the term "quotient(u_{n-1} , n)" to the Fibonacci recursion, and claimed the resulting formula fit the data perfectly.
What?
EDIT: since people seem to be confused about why this is wrong... according to the graph, the sequence starts at n = 0. So the modified Fibonacci sequence I created is:
n | 0 1 2 3 4 5 6
u | 1 1 2 3 5 8 14
The computer says this formula fits it perfectly:
u[n] = u[n-1] + u[n-2] + u[n-1]/n
Let n = 5:
8 = 5 + 3 + 5/5
8 = 9
EDIT 2: hmm, contrary to the graph, the engine seems to assume the sequence starts at 1. So then we have
n | 1 2 3 4 5 6 7
u | 1 1 2 3 5 8 14
I guess the formula works if "quotient" is defined as integer division?
I don't think people here realize how amazing this is. You are providing very little data and the machine is able to fit the closed-form recurrent relation out of it. Very little data and the clean simple expressions is the key. It's just matter of adding more ops like sinusoidals, primes etc to make it recognize more and more complex expressions.
There's not any execution of the functions occurring here. It's modeled as a sequence-to-sequence problem where the training sequences have been pre-computed programmatically.
I think in this case the attention operation bounds the runtime by the longest possible sequence that can go in at once. Since you have a positional embedding, you can add arbitrarily many more functions without incurring a runtime penalty, although it may begin to interfere with the model's ability to effectively generalize as well, particularly when used with very long sequence lengths (so chains of operations, lists of ints).
Since each operation is mapped to an integer, the maximum number of tokens is bound by the precision of the system.
They used a fixed size transformer, where the vocab determines the functions and input/output range. So unless the model needs more 'memory' for your class of expression there wouldn't necessarily be a big change in performance. They have experiments in the paper with bigger/smaller vocabs.
People have been doing Symbolic Regression for a long time. I don't really see any novelty in this paper. They have left out a large part of the history and comparative results. How good is this compared to other methods?
There are much better options than mathematica for SR. The even cite the paper that made SR famous again (the nature one by Hod and Mike Schmidt).
They could have at least compared to them. They barely mention the standard method and leave out an entire class of top tier solutions, the more recent deterministic stratgeies. Shows they did not do their background reading and know the history. More like someone with a tool looking for an interesting application than someone deeply interested in a problem and finding all of the tools which can be used.
They go on to leave out all of the common test problems used in the field. Makes one wonder if the tests were too difficult for neural nets to produce publishable results with, or if they are just ignorant of the research and test problems. They almost state as much in the next paragraph. They don't even .mention how the other algos are capable where they are not.
It's also worth thinking about the environmental cost of the, now three, methods.
Anywhere to download the implementation? This seems useful but I fear it'll be gone the time I go to reach for it like has often been the case with the (full size version of the) inverse symbolic calculator.
34 comments
[ 0.18 ms ] story [ 82.5 ms ] threadThis is not dissimilar from e.g. DALL-E where they model images as NLP-style tokens and use a transformer to predict image tokens (operations, respectively) from text tokens (list of ints/floats, respectively).
This demo lets you interact with the model. Pretty cool stuff. Refreshing to see symbolic problems being tackled with deep learning.
Yannic Kilcher video with one of the authors: https://youtu.be/1HEdXwEYrGM
arxiv: https://arxiv.org/abs/2201.04600
https://seminars.math.binghamton.edu/ComboSem/worm-chiu.pge_...
It is a deterministic algo for SR that I've always thought would benefit from RL.
The biggest problem is SR research has been and still is the lack of a widely used dataset and reproducible results. There is a researcher who beats everyone's results within a year by publishing to Springer without code or data...
http://trent.st/ffx/
`1,1,2,3,5` gets the result "No Solution" whereas `1,1,2,3,5,8` correctly guesses the pattern. Its just a linear recurrence with j=2 which means you get 2 data points to guess the relation and 1 to confirm.
An equation is available here: https://en.wikipedia.org/wiki/Damping
Pretty neat otherwise!! I especially love the interface. I wonder if there is a plug and play framework for deploying pytorch models on a website.
EDIT: They seem to be using https://streamlit.io . Seems like a neat tool.
https://facebook.github.io/prophet/docs/quick_start.html
"One may ask to what extent our model can be used for real-world applications, such as time-series forecasting. Although the robustness to noise is an encouraging step in this direction, we believe our model is not directly adapted to such applications, for two reasons. First, because real-world data generally cannot be described by neat mathematical equations, in which case numeric approaches will outperform symbolic approaches. Second, even in cases where the sequence is described by a formula, this formula will often con- tain complex prefactors. While our method is capable of approximating prefactors rather remarkably, this adds a layer of difficulty to the original problem, as the model sometimes needs to use many operators to approximate a single prefactor (see Table 2). However, one easy way to solve this issue is to extend the vocabulary of the decoder, enabling it to build prefactors more easily, or use a separate solver to fit the prefactors as done in approaches. We leave this for future work."
It added the term "quotient(u_{n-1} , n)" to the Fibonacci recursion, and claimed the resulting formula fit the data perfectly.
What?
EDIT: since people seem to be confused about why this is wrong... according to the graph, the sequence starts at n = 0. So the modified Fibonacci sequence I created is:
The computer says this formula fits it perfectly: Let n = 5: EDIT 2: hmm, contrary to the graph, the engine seems to assume the sequence starts at 1. So then we have I guess the formula works if "quotient" is defined as integer division?I think in this case the attention operation bounds the runtime by the longest possible sequence that can go in at once. Since you have a positional embedding, you can add arbitrarily many more functions without incurring a runtime penalty, although it may begin to interfere with the model's ability to effectively generalize as well, particularly when used with very long sequence lengths (so chains of operations, lists of ints).
Since each operation is mapped to an integer, the maximum number of tokens is bound by the precision of the system.
They could have at least compared to them. They barely mention the standard method and leave out an entire class of top tier solutions, the more recent deterministic stratgeies. Shows they did not do their background reading and know the history. More like someone with a tool looking for an interesting application than someone deeply interested in a problem and finding all of the tools which can be used.
They go on to leave out all of the common test problems used in the field. Makes one wonder if the tests were too difficult for neural nets to produce publishable results with, or if they are just ignorant of the research and test problems. They almost state as much in the next paragraph. They don't even .mention how the other algos are capable where they are not.
It's also worth thinking about the environmental cost of the, now three, methods.
but alas ...
In hexadecimal, it also didn't work, though there is this formula:
https://giordano.github.io/blog/2017-11-21-hexadecimal-pi/