[seqfan] Re: Alien Coding article

hv at crypt.org hv at crypt.org
Wed Feb 1 03:32:27 CET 2023

I had a brief look through it. The headline claim of 78000 sequences
matched actually refers to programs that matched the values shown in
the main entry: a significant number of those failed when additionally
checked against b-files (10-30%), and I suspect a similar number of
the matches were for entries in which only a few values are known.

At this stage, it seems there is still significant human effort needed
to interpret the programs to determine whether they are actually
calculating the underlying sequence, and that effort has been expended
for only a very small number of the programs.

It also seems like quite a resource intensive approach that may make
sense when applied to the OEIS as a whole, but does not offer an obvious
path for a lightweight test suitable for Superseeker. I don't know
much about this area though, it may be worth contacting the authors
to see if they see that differently.

That said, I do feel that the direction shows promise, and it suggests to
me that there is additional value in creating extended b-files for those
sequences where we can do so - a similar endeavour that restricted the
training set to sequences with, say, at least 100 or 1000 values seems
more likely to generate programs that correctly generate the sequences.

The authors' reluctance to introduce literal values greater than 2 into
their programming language also seems quite restrictive. It would be
interesting to see how the results differ if they permitted constants
up to 10 with a "size" penalty but no "speed" penalty.


Neil Sloane <njasloane at gmail.com> wrote:
:I looked at the Alien Coding article on the arXiv that I mentioned here
:yesterday.  It looks to me - after a quick read - that they are still
:getting their sequence-guessing algorithm working, and that they can
:successfully predict how tens of thousands of sequences will grow just by
:looking at the DATA lines.  I did not see any statements like "we found
:formulas that appear to generate 25 sequences for which no formula was
:presently known".  I suppose that will be the next stage in the project.
:Best regards
:Neil J. A. Sloane, Chairman, OEIS Foundation.
:Also Visiting Scientist, Math. Dept., Rutgers University,
:Email: njasloane at gmail.com
:On Mon, Jan 30, 2023 at 3:08 PM Neil Sloane <njasloane at gmail.com> wrote:
:> Dear Seq Fans, This article looks very interesting.  Maybe it could be
:> added to Superseeker?  I haven't had time to read it yet.
:> arXiv:2301.11479 Computer Science > Artificial Intelligence [Submitted on
:> 27 Jan 2023] Alien Coding by Thibault Gauthier, Miroslav Olšák, Josef Urban
:> Abstract: We introduce a self-learning algorithm for synthesizing programs
:> for OEIS sequences. The algorithm starts from scratch initially generating
:> programs at random. Then it runs many iterations of a self-learning loop
:> that interleaves (i) training neural machine translation to learn the
:> correspondence between sequences and the programs discovered so far, and
:> (ii) proposing many new programs for each OEIS sequence by the trained
:> neural machine translator. The algorithm discovers on its own programs for
:> more than 78000 OEIS sequences, sometimes developing unusual programming
:> methods. We analyze its behavior and the invented programs in several
:> experiments.
:> Best regards
:> Neil
:> Neil J. A. Sloane, Chairman, OEIS Foundation.
:> Also Visiting Scientist, Math. Dept., Rutgers University,
:> Email: njasloane at gmail.com
:Seqfan Mailing list - http://list.seqfan.eu/

More information about the SeqFan mailing list