Formal methods are not human one

[Christophe Bal]

Hello.

I'm looking for formal outputs that are not calculated as a human can do (this is for a free french "book"). Do you know such kind of examples ?

Christophe BAL

PS : this questions has been posted on both Sage and Sympy lists.

[Aaron Meurer]

The most canonical example of this is symbolic integration. The two
most powerful algorithms implemented in SymPy, Risch and Meijer G,
work completely differently from how a human would compute an integral
(there are also some table lookup algorithms and manualintegrate which
do work how a human would). Risch works by converting the expression
to a tower of differential extensions (roughly, it converts the
integrand into a rational function where the variables have a
derivative which can be expressed in terms of the other variables). It
then performs what basically amounts to several polynomial
manipulation algorithms on this to compute the integral. To imagine
the difference, consider how many times you compute a polynomial gcd
(the Euclidean algorithm) as part of computing an indefinite integral
by hand. It's probably zero. By contrast, the Risch algorithm computes
gcds hundreds of times over the course of calculating an integral.

The Meijer G algorithm works (very roughly) by converting the integral
into a Meijer G function, integrating it, and then converting it back.

The usual by-hand integration methods are sort of heuristics. There
are several methods which apply to specific expressions, and if you
can pattern match your expression to a known technique then you can
apply it. Risch and the Meijer G algorithm are quite general (Risch is
extremely general, to the point where if it can't compute an integral
for an elementary function then it is a proof that none exists).

There are other good examples from the polys module. For instance, the
algorithm to factorize polynomials (again here, a human "algorithm"
would be heuristics, which might not always apply, whereas the
computer algorithm is based on some deeper math that lets you always
compute the factorization for any polynomial).

In general, I would say that human methods tend to use a lot of little
tricks, which are designed to minimize brute calculation. This is
because humans are bad at brute calculation, but very good at the
pattern matching and intuition required to apply and invent such
methods. Computers on the other hand are very good at brute
calculation, but very bad at pattern matching and intuition.

So even algorithms that are essentially done the same way by a human
and a computer are somewhat different for actual computation because
humans know when they can "skip" certain steps, for instance. A human
isn't going to run through the full Euclidean algorithm to compute
gcd(1, x), for instance, and even for gcd(x, x**2 + x) a human can see
the answer right away without running through any polynomial long
division.

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sympy/CAAb4jGkNc8QcUAxhYnhoRN017tEXfDZrtABVr4w_OTQEhfXSqQ%40mail.gmail.com.
> For more options, visit https://groups.google.com/d/optout.

[Richard Fateman]

There are even simpler examples.  For instance, some systems multiply

polynomials by some evaluation/interpolation scheme in finite fields. Or by FFT

or by so-called Karatsuba   or Cooke-Toom methods or a Kronecker method

evaluating a polynomial to a single huge integer...

Risch integration is certainly another one.

[Christophe Bal]

Thanks for the answers.

Maybe integration will be a good candidate. When I talk about formal output, I think of special case where the formula given is correct but certainl not the one a human will see first.

One day, a student had shown me an integral which was evaluate by its formal calculator to a formula containing arctan whereas my solution do not use it, and was more simple. The problem is that I have not noted this example...

Maybe solving some polynomial of degree 3 can give such "complicated" formulas that a human would not use.

Christophe BAL

--

You received this message because you are subscribed to the Google Groups "sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/a2c48c91-3bc3-4761-bef7-7a8bdebc7297%40googlegroups.com.

[Aaron Meurer]

On Fri, Oct 31, 2014 at 6:37 AM, Christophe Bal <proj...@gmail.com> wrote:
> Thanks for the answers.
>
> Maybe integration will be a good candidate. When I talk about formal output,
> I think of special case where the formula given is correct but certainl not
> the one a human will see first.

I see. I was thinking more of cases where the human wouldn't see how
to solve it at all.

A possible idea here is integrals using square roots. Humans tend to
make simplifications on square roots which are not true in general,
leading to "simpler" output, whereas computer algebra systems try to
be more cautious about them. For instance, sqrt(1/x) != 1/sqrt(x).

Aaron Meurer

> https://groups.google.com/d/msgid/sympy/CAAb4jGmGUqW1vGBkYLieOYhBGJT%3DOn7nfZDyHVNFW524%3DGfN7w%40mail.gmail.com.

[Christophe Bal]

Thanks for this hint. If I find revelant example, I will post them in this discussion.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAKgW%3D6JH_tCkVtKsmFxcJ4Ucbajc8pmxBnzzr3dtNTiWUhMpAg%40mail.gmail.com.

[Richard Fateman]

The simplification of results of integration to logs or to arctan can depend

on how the programmer viewed the importance of avoiding complex numbers.

This is not inherent in computer algebra systems generally, or even Sage

particularly.  It is hardly an example where a computer could not do what

a human could do,  

My advice is you should never get into a situation where a limitation of a particular

computer program --- or even several computer programs -- leads you to

say that computers cannot compute something "the way humans can".

Recall that for many years people claimed that computers could never

play a good game of chess. 

[Joachim Durchholz]

Am 31.10.2014 um 20:03 schrieb Richard Fateman:
> My advice is you should never get into a situation where a limitation of a
> particular
> computer program --- or even several computer programs -- leads you to
> say that computers cannot compute something "the way humans can".
>
> Recall that for many years people claimed that computers could never
> play a good game of chess.

I think the gist of the question was what the computer "does", not what
it "can".

Also, I think it's really a spectrum, and you need to determine where on
that spectrum you wish to go for some particular task:
1) Mimick what a human would do. For some (to-be-determined) definition
of "mimick" and "what a human would do", so this is very vague anyway.
2) Do something wildly different than what a human would do, but
transform the results to something that a human would arrive at
eventually. This is what the vast majority of chess programs tries to do.
3) Do something wildly different than wat a human would do, and
(hopefully) be better than a human's result by some (to-be-determined)
metric.

In the end I think the question whether the computer can arrive at human
capabilities is too narrowly defined - the classical trap of AI: trying
to mimick the human mind instead of exploiting the computer's specific
power will just give us a bad substitute for a human (though research in
that area can still give interesting results).