Machine Learning people apparently built a symbolic integrator

[Dima Pasechnik]

https://openreview.net/pdf?id=S1eZYeHFDS

I wish they had code available...

[Eric Gourgoulhon]

Thanks for sharing!

This looks very promising. I hope we have it in Sage some day.

Eric.

[mmarco]

I would be very interested in comparing their results with RUBI.

[Martin R]

Actually, I think it would be even more interesting to compare with FriCAS, because FriCAS has the most complete implementation of the Risch algorithm and does not at all rely on pattern matching.

Martin

[rjf]

I think that if you read the paper you would not expect it to compete with a CAS

except on its made-up artificial testset.

RJF

[Emmanuel Charpentier]

Le mercredi 2 octobre 2019 01:48:15 UTC+2, rjf a écrit :

I think that if you read the paper you would not expect it to compete with a CAS

except on its made-up artificial testset.

Could you amplify ?

[rjf]

If they were interested in a fair comparison they would use a test set from

(for example) Rubi or one of the CAS.   

My guess is that they did this:

 1. generate a random expression S favoring + and * in the tree.

2.  differentiate S to get S'

3. "learn" the integral of S'.

Here's the trick.  S' will, with very high probability, be a sum.  Say s1+s2+s3.

A CAS will usually try to compute integrate(s1,x) + integrate(s2,x)+ integrate(s3,x).

That's the way integral tables work too.

Unfortunately, for many "random" expressions,  s1, s2, s3, ... are

NOT integrable in terms of elementary functions. Only their sum.

So a CAS will fail.

Here's a particular example.  exp(-x^3)/x^4.

Differentiate (I'm copy/pasting from Maxima) to get

-(3*%e^(-x^3))/x^2-   (4*%e^(-x^3))/x^5

Neither of these terms is separately integrable in terms of elementary functions.

So a "real" CAS will fail on even "simple" problems.  If you generate

trees with 15 random operators, the probably of failing increases.

For this particular example, which is the 2nd one I tried, Maxima gives

gamma_incomplete(-1/3,x^3)+(4*gamma_incomplete(-4/3,x^3))/3

Non elementary it seems.  But we know this is supposed to be the same as exp(-x^3)/x^4.

A minute testing numerically suggests it is, indeed, equal.

So what we have for "ML" here is a made-up test set that is not

reflective of the actual task of computing integrals as needed in

applied math, and as considered in (for example) integral

tables or integration algorithms.  

We are perhaps familiar with the notion of "teaching for the test"

in which students and teachers collude to get excellent grades

on some standardized test.  Yet the students may really

not know the material.

This is maybe worse because the "test" is not some 

important standardized suite of integration problems.

It is just randomly generated. Maybe it would

be fair to call it noise?  The author could post the

test suite, I suppose.

RJF

RJF

[Martin R]

Here's the trick.  S' will, with very high probability, be a sum.  Say s1+s2+s3.

A CAS will usually try to compute integrate(s1,x) + integrate(s2,x)+ integrate(s3,x).

That's the way integral tables work too.

Are you saying that  FriCAS is the only CAS which doesn't do this?

Martin

[Emmanuel Charpentier]

Hi, Martin !

AFAICT, FriCAS dos this also... 

Martin

[Emmanuel Charpentier]

!!!!!

What you describe

• is doable, and
  
• is outright academic fraud...
  

I doubt somehow that the authors would be dumb enough to risk that.

"Never assign to human ill will what can be explained by human stupidity". (Napoleon Bonaparte, IIRC).

However, I agree that using an external problem test set would be more convincing. By the way, translating a standard set to the input language of their integrator would be a good test of their parsing abilities ;-)...

[Martin R]

Are you saying that  FriCAS is the only CAS which doesn't do this?

AFAICT, FriCAS dos this also... 

I don't think so - are you sure?  Neither do I not know the Risch algorithm nor FriCAS' implementation of it too well, but I would have thought that FriCAS doesn't do pattern matching in the sense described above.

Martin

[rjf]

I am not aware specifically of the methods used in FriCAS.

It is possible, I suppose, that given an expression it immediately

tries to find an appropriate differential field and begins some version

of the Risch "algorithm"  (which actually fails to be an algorithm

for various reasons), and doesn't use the usual methods first.

Since a huge percentage of integration problems (Like 90 percent

of textbook problems) can be done by the "derivative divides"

method, that takes about a page of code, and is almost

instantaneous, I would be surprised if this is not used by

FriCAS.  But as I said, it is possible that FriCAS doesn't

do this.

As for the paper being a fraud, I do not know for sure

what the authors did,  just a suspicion.  And they may

just be well-intentioned, but naive. see the quote above..

I think you might find that much of the literature in AI

describes the results in an overly self-serving mode.

It is probably worse than science literature generally,

but even that has been getting some bad press about

results that are not reproducible.  One would hope

that computer science software results would be more

generally reproducible, but that depends on the

software being made available.

RJF

[Richard_L]

Apparently, someone disagrees. See Ernest Lample's posting to the arXiv: https://arxiv.org/abs/1912.05752

[Dima Pasechnik]

their preprint is here now:

https://arxiv.org/abs/1912.01412

- but no source code.

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/a9ca2337-6fe9-458a-a5c5-327b008e709f%40googlegroups.com.

[Martin R]

I tested (some of?) the integrals from Table 7 with FriCAS, without any (bad) surprises.

Am Montag, 16. Dezember 2019 16:39:11 UTC+1 schrieb Dima Pasechnik:

On Mon, 16 Dec 2019, 15:14 Richard_L, <Rich...@lozestech.com> wrote:

Apparently, someone disagrees. See Ernest Lample's posting to the arXiv: https://arxiv.org/abs/1912.05752

On Friday, September 27, 2019 at 8:06:31 AM UTC-7, Dima Pasechnik wrote:

https://openreview.net/pdf?id=S1eZYeHFDS

I wish they had code available...

their preprint is here now:

https://arxiv.org/abs/1912.01412

- but no source code.

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.

To unsubscribe from this group and stop receiving emails from it, send an email to sage-...@googlegroups.com.

[Richard_L]

You could e-mail the authors, now that you have names and addresses.

Maybe they'd part with source.

On Monday, December 16, 2019 at 7:39:11 AM UTC-8, Dima Pasechnik wrote:

On Mon, 16 Dec 2019, 15:14 Richard_L, <Rich...@lozestech.com> wrote:

Apparently, someone disagrees. See Ernest Davis's posting to the arXiv: https://arxiv.org/abs/1912.05752

On Friday, September 27, 2019 at 8:06:31 AM UTC-7, Dima Pasechnik wrote:

https://openreview.net/pdf?id=S1eZYeHFDS

I wish they had code available...

their preprint is here now:

https://arxiv.org/abs/1912.01412

- but no source code.

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.

To unsubscribe from this group and stop receiving emails from it, send an email to sage-...@googlegroups.com.

[rjf]

disagrees with me? or Emmanuel?  

Lample's abstract (of the review) concluded with

The claim that this outperforms Mathematica on symbolic integration needs to be very much qualified.

I glanced at the full review and I don't see that I disagree with it.

Generating 80 million randomly generated expressions, storing them and claiming

that you can integrate their derivatives does not become a method for doing integrals.

It is a method for looking up expressions in a table.  Since most of those expressions

will be sums, and the one of the main methods for actually computing integrals

is to observe that the integral of a sum is the sum of the integrals,  there is

very little use for such a table.

[rjf]

oops, the review is by Davis; the paper is by Lample and Charton, both of Facebook.

[Richard_L]

I was unclear. Davis disagrees with Lample and Charton in their claim of neural nets being somehow superior to established CAS.

(And yes, the review is by Davis, not Lample.)

On Tuesday, December 17, 2019 at 4:21:07 PM UTC-8, rjf wrote:

[rjf]

I was trying to come up with a simple example of how this integration program claim

was bogus.  Here it is.

Take one of your favorite prime-testing programs and generate

a list of 10,000  Largish Primes.  I don't know how large, but

say 50 decimal digits or more.

Make  10^8 factorization problems by multiplying them together

in pairs, a*b=c.  In a table with 10^8 entries of all the values of c,

remember the a, b that are the factors of that c.

Now write a "machine learning factoring program"  "trained" on

exactly those entries in the table.  (It can be done in about 3 lines, that

program).  That's going to be a factoring program that is much faster

than (say) Mathematica.  And if you want to make it much much much

faster than Mathematica, just use numbers with 500 or 5000 digits.

Now, is this a breakthrough that demonstrates that machine learning

can be used to factor integers fast?

Indeed, outside of the 10^8 preset problems, it can't factor anything.

What do you think? Is this a fair comparison to the integration program?

RJF

[E. Madison Bray]

On Wed, Dec 18, 2019 at 6:39 AM rjf <fat...@gmail.com> wrote:
>
> I was trying to come up with a simple example of how this integration program claim
> was bogus. Here it is.
>
> Take one of your favorite prime-testing programs and generate
> a list of 10,000 Largish Primes. I don't know how large, but
> say 50 decimal digits or more.
>
> Make 10^8 factorization problems by multiplying them together
> in pairs, a*b=c. In a table with 10^8 entries of all the values of c,
> remember the a, b that are the factors of that c.
> Now write a "machine learning factoring program" "trained" on
> exactly those entries in the table. (It can be done in about 3 lines, that
> program). That's going to be a factoring program that is much faster
> than (say) Mathematica. And if you want to make it much much much
> faster than Mathematica, just use numbers with 500 or 5000 digits.
>
> Now, is this a breakthrough that demonstrates that machine learning
> can be used to factor integers fast?
>
> Indeed, outside of the 10^8 preset problems, it can't factor anything.
>
> What do you think? Is this a fair comparison to the integration program?

I think so, based on my limited read. More to the point, if you throw
a bunch of tables of integrals at a machine learning program it will
know how to integrate exactly those integrals, and *maybe* some simple
compound expressions like sums and products; maybe...

But if you throw at it, say, some special function that it's never
seen before of course it won't know what to do with it.

> On Tuesday, December 17, 2019 at 5:03:59 PM UTC-8, Richard_L wrote:
>>
>> I was unclear. Davis disagrees with Lample and Charton in their claim of neural nets being somehow superior to established CAS.
>> (And yes, the review is by Davis, not Lample.)
>>
>> On Tuesday, December 17, 2019 at 4:21:07 PM UTC-8, rjf wrote:
>>>
>>> disagrees with me? or Emmanuel?
>>> Lample's abstract (of the review) concluded with
>>>
>>> The claim that this outperforms Mathematica on symbolic integration needs to be very much qualified.
>>>
>>> I glanced at the full review and I don't see that I disagree with it.
>>> Generating 80 million randomly generated expressions, storing them and claiming
>>> that you can integrate their derivatives does not become a method for doing integrals.
>>> It is a method for looking up expressions in a table. Since most of those expressions
>>> will be sums, and the one of the main methods for actually computing integrals
>>> is to observe that the integral of a sum is the sum of the integrals, there is
>>> very little use for such a table.
>>>
>>>
>>> On Monday, December 16, 2019 at 7:14:02 AM UTC-8, Richard_L wrote:
>>>>
>>>> Apparently, someone disagrees. See Ernest Lample's posting to the arXiv: https://arxiv.org/abs/1912.05752
>>>>
>>>> On Friday, September 27, 2019 at 8:06:31 AM UTC-7, Dima Pasechnik wrote:
>>>>>
>>>>> https://openreview.net/pdf?id=S1eZYeHFDS
>>>>>
>>>>> I wish they had code available...
>

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/636e16e5-668f-4946-94b3-fab04c7ba265%40googlegroups.com.

[rjf]

See, for example, Rubi, or my earlier project Tilu, for programs that absorbed,

in some sense learning from tables of integrals.

This is not classical machine learning, because the objects being learned are

patterns.  So the result for sin(x)dx works for sin(u)du,  as a trivial pattern

match.

Categorizing the patterns so there is an effect search method for finding one

that matches a problem is important for efficiency.

Also important (and quite a challenge to do effectively) is a

method to simplify expressions.

So there are ways of using "data" productively in 

methods for symbolic definite integration.

[Dima Pasechnik]

Yes, I agree - perhaps even more to the point would be integration of
rational functions, where
one does not merely seek an expansion into sums over roots of
irreducible polynomials,
but also building radical experessions for the roots of solvalbe polynomials.
(so that for solvable polynomials these sums over roots may be made
fully explicit).

I'd be very, very surprised if an ML system would be able to build
enough Galois theory to be able to
solve any problem from such a class... :-)

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAOTD34Zpkz22xhp1pwwsNpDP_FwYJOMO86RFm5BeUdk-%3DoFTsA%40mail.gmail.com.

[Brent W. Baccala]

I know the Risch algorithm fairly well.

I made two screencast videos describing how to use Axiom or Sage to simplify one of the integrals used in the Facebook paper.

Quick summary - Axiom works quite well.  Sage can't do it in one step, but the new function field features in Sage 9 allow the integral to computed, but you have to know something about the Risch algorithm to step through it.

The second video is a whirlwind overview of the Risch theorem and shows how to do a Risch calculation (on the Facebook integral) using Sage.

You can view the videos here:

https://www.freesoft.org/blogs/soapbox/the-facebook-integral/

[Dima Pasechnik]

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/d4b54993-e650-4627-a7fa-27b6b0c289c0%40googlegroups.com.

[rjf]

The problem chosen seems to be 

integrate((16*x^3-42*x^2+2*x)/sqrt(-16*x^8+112*x^7-204*x^6+28*x^5-x^4+1),x)

The integrand is of the form dy/sqrt(1-y^2)

and so the integral is  arcsin(y).

An algorithm to look for this kind of pattern (in general) would not be

difficult to write, although it does assume you can compute the integral

of any polynomial  (here,let y= the integral of the numerator of the integrand above), 

and also that you can compute 1-y^2 and compare it to the radicand in the

denominator. 

I  find it somewhat unlikely that the machine learning mechanism in that paper

would come up with this generalization. 

 Even given 80 million specific examples of this.

e.g. for i from 1 to 80000000 do  {h=arcsin( random_expression[i]), g=diff(h,x), remember 

 the integral of g is h}

would it integrate  other technically similar examples?

One could propose a mechanical artificial

intelligence that, given sufficient knowledge of axioms, logical methods,

etc, would derive all the theorems of mathematics past, present, and

future. This would presumably include any theorems of Robert Risch

relevant to symbolic indefinite integration in finite terms.

Hilbert thought about this.

It may not be possible --  Gödel's incompleteness results

are probably relevant.   If we replaced the phrase "all the theorems"

in the paragraph above with the phrase "all the useful theorems",

or "all the necessary theorems to do symbolic indefinite integration" there

could be a debate of some sort.  I don't know that Sage has incorporated

theorem provers, but there are research programs e.g. Coq.

It may be useful to see John McCarthy's paper from 1996

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.8613&rep=rep1&type=pdf

But this is wandering far afield from the presumed topic of this thread.

RJF