5 ms·

Deep symbolic regression for recurrent sequences

70 points by ShamelessC 5y ago

ShamelessC 5y ago
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. Yannic Kilcher video with one of the authors: https://youtu.be/1HEdXwEYrGM https://youtu.be/1HEdXwEYrGM arxiv: https://arxiv.org/abs/2201.04600 https://arxiv.org/abs/2201.04600
- verdverm 5y ago
  If you find this interesting, my phd work is an interesting read https://seminars.math.binghamton.edu/ComboSem/worm-chiu.pge_gecco2013.pdf 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...
  - verdverm 5y ago
    Fast Function extraction is another interesting Algo for SR http://trent.st/ffx/ http://trent.st/ffx/
rurban 5y ago
Fantastic. This can be used for superior compressors, eg. Or to break random number generators.
- deleted 5y ago
  [deleted]
not2b 5y ago
Doesn't do well with 2,3,5,7,11,13. Perhaps they can figure out how to incorporate OEIS or a similar resource in addition to just a simple curve fit.
- somebodythere 5y ago
  That sequence is out of domain I think.
- CasperDern 5y ago
  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.
- alar44 5y ago
  Lol, beat me to it.
fjfaase 5y ago
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-recurrence.html http://www.ryanhmckenna.com/2015/06/automatically-finding-re... it gives the exact recurrence equation within a few seconds.
- ShamelessC 5y ago
  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.
- thethirdone 5y ago
  I think there is a bug in your program. `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.
muds 5y ago
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? An equation is available here: https://en.wikipedia.org/wiki/Damping 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 https://streamlit.io . Seems like a neat tool.
- danuker 5y ago
  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.
  - amelius 5y ago
    Not really a recurrence relation. Perhaps try it on Prophet: https://facebook.github.io/prophet/docs/quick_start.html https://facebook.github.io/prophet/docs/quick_start.html
ShamelessC 5y ago
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."
- bravura 5y ago
  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.
civilized 5y ago
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?
- amelius 5y ago
  Isn't that what you get if you add the formula for (0,0,0,0,0,0,1,...) to the formula for (1,1,2,3,5,8,13,...)?
- eutectic 5y ago
  Seems right to me.
- nextaccountic 5y ago
  It found another formula that worked, what's the problem with that?
sytelus 5y ago
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.
- amelius 5y ago
  Wouldn't it become slower, the more functions you add? And exponentially slower if you start nesting those functions?
  - ShamelessC 5y ago
    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.
  - CasperDern 5y ago
    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.
- verdverm 5y ago
  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?
amelius 5y ago
Assume this works for f(i), how well would it work for even(f(i)), where even returns 1 if the argument is even and 0 otherwise?
amelius 5y ago
I tried it on the digits of pi: 3,1,4,1,5,9,2,6,... but alas ... In hexadecimal, it also didn't work, though there is this formula: https://giordano.github.io/blog/2017-11-21-hexadecimal-pi/ https://giordano.github.io/blog/2017-11-21-hexadecimal-pi/
jmount 5y ago
I really recommend taking a look at the "A=B" identity solver: https://www2.math.upenn.edu/~wilf/AeqB.html https://www2.math.upenn.edu/~wilf/AeqB.html . The accompanying book is amazing.
- mjcohen 5y ago
  The book is also free.
nullc 5y ago
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.
catlifeonmars 5y ago
3n+1 conjecture counts as a recurrence relation, no?

70 points by ShamelessC 5y ago

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. Yannic Kilcher video with one of the authors: https://youtu.be/1HEdXwEYrGM https://youtu.be/1HEdXwEYrGM arxiv: https://arxiv.org/abs/2201.04600 https://arxiv.org/abs/2201.04600

verdverm 5y ago
If you find this interesting, my phd work is an interesting read https://seminars.math.binghamton.edu/ComboSem/worm-chiu.pge_gecco2013.pdf 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...
- verdverm 5y ago
  Fast Function extraction is another interesting Algo for SR http://trent.st/ffx/ http://trent.st/ffx/

rurban 5y ago

Fantastic. This can be used for superior compressors, eg. Or to break random number generators.

deleted 5y ago
[deleted]

not2b 5y ago

Doesn't do well with 2,3,5,7,11,13. Perhaps they can figure out how to incorporate OEIS or a similar resource in addition to just a simple curve fit.

somebodythere 5y ago
That sequence is out of domain I think.
CasperDern 5y ago
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.
alar44 5y ago
Lol, beat me to it.

fjfaase 5y ago

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-recurrence.html http://www.ryanhmckenna.com/2015/06/automatically-finding-re... it gives the exact recurrence equation within a few seconds.

ShamelessC 5y ago
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.
thethirdone 5y ago
I think there is a bug in your program. `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.

muds 5y ago

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? An equation is available here: https://en.wikipedia.org/wiki/Damping 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 https://streamlit.io . Seems like a neat tool.

danuker 5y ago
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.
- amelius 5y ago
  Not really a recurrence relation. Perhaps try it on Prophet: https://facebook.github.io/prophet/docs/quick_start.html https://facebook.github.io/prophet/docs/quick_start.html

ShamelessC 5y ago

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."

bravura 5y ago
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.

civilized 5y ago

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?

amelius 5y ago
Isn't that what you get if you add the formula for (0,0,0,0,0,0,1,...) to the formula for (1,1,2,3,5,8,13,...)?
eutectic 5y ago
Seems right to me.
nextaccountic 5y ago
It found another formula that worked, what's the problem with that?

sytelus 5y ago

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.

amelius 5y ago
Wouldn't it become slower, the more functions you add? And exponentially slower if you start nesting those functions?
- ShamelessC 5y ago
  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.
- CasperDern 5y ago
  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.
verdverm 5y ago
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?

amelius 5y ago

Assume this works for f(i), how well would it work for even(f(i)), where even returns 1 if the argument is even and 0 otherwise?

amelius 5y ago

I tried it on the digits of pi: 3,1,4,1,5,9,2,6,... but alas ... In hexadecimal, it also didn't work, though there is this formula: https://giordano.github.io/blog/2017-11-21-hexadecimal-pi/ https://giordano.github.io/blog/2017-11-21-hexadecimal-pi/

jmount 5y ago

I really recommend taking a look at the "A=B" identity solver: https://www2.math.upenn.edu/~wilf/AeqB.html https://www2.math.upenn.edu/~wilf/AeqB.html . The accompanying book is amazing.

mjcohen 5y ago
The book is also free.

nullc 5y ago

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.

catlifeonmars 5y ago

3n+1 conjecture counts as a recurrence relation, no?