Deep symbolic regression for recurrent sequences | Hacker News Reader

Deep symbolic regression for recurrent sequences

recur-env.eba-rm3fchmn.us-east-2.elasticbeanstalk.com

70 pointsShamelessC33 comments

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

arxiv: https://arxiv.org/abs/2201.04600

If you find this interesting, my phd work is an interesting read

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

Fast Function extraction is another interesting Algo for SR

http://trent.st/ffx/

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.

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.

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

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.

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.

Not really a recurrence relation. Perhaps try it on Prophet:

https://facebook.github.io/prophet/docs/quick_start.html

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.

Wouldn't it become slower, the more functions you add? And exponentially slower if you start nesting those functions?

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?

Have people been using transformers for it? Their method beats mathematica by a large margin on OEIS.

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.

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.

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.

That sequence is out of domain I think.

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.

Lol, beat me to it.

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?

Seems right to me.

It found another formula that worked, what's the problem with that?

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,...)?

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

The book is also free.

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

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.

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?

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

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/

Reply on news.ycombinator.com