\documentstyle{article}
\title{Referee Report on
``Solving Symbolic Equations with PRESS''
(Sterling, Bundy, Byrd, OKeefe, Silver)}
\author{Richard J. Fateman}
\begin{document}
\maketitle
This paper describes a program PRESS
(Prolog Equation Solving System)
which is solves some
symbolic, transcendental, non-differential equations. The problem
of solving such equations is divided into two levels,
a {\em meta-level}
which is intended as a research vehicle for exploring search
strategies in mathematical reasoning and
{\em equation-solving modules} used initial for the MECHO
system (a project which aims
to solve high-school mechanics problems stated in English.)
The authors suggest that ``the techniques used may have something
to offer the field of symbolic and algebraic manipulation''.
Previous reports of work on PRESS have appeared generally
in AI publications, (IJCAI6, IJCAI17 and AI 16(2)), but it appears that
this work has not previously been reviewed from any
mathematical perspective.
\section{What problem does PRESS solve?}
The equations that PRESS has been
trained to solve are taken from various British A-level examinations.
That is, the equations are limited to single-variable problems
which are amenable to tricks taught to high-school students.
They appear to generally involve applying identities to take
advantage of coincidences which simplify the problem so that it
can be solved.
I would guess that the objective of the A-level exam questions
is to see if the
student knows a sufficient collection of identities, and has
the ability to search for the clever twist that solves the problem.
For this task, largely heuristic methods are perhaps appropriate.
Of the 80 single-variable equations in their sample, the authors
are pleased to point out that it can solve 62.
Nowhere is the class of expressions acceptable to the program
indicated. It appears to allow integers, only one variable, $x$,
logarithms, trigonometric functions, square-root, and
hyperbolic functions. It appears to exclude complex numbers, although
they can obviously be constructed. Division appears in no example,
but negative exponents allow us to construct division.
\section{How does PRESS work?}
Let us talk about the lower level methods first.
Six "major methods" are implemented.
Some of the methods are obvious, and would be included in any
program, heuristic or not, to solve an equation with a single
occurrence of an unknown. Some are simplified cases that could
be solved by algorithms, but are not.
Others methods do not
always work, since they produce extraneous solutions or ignore
some solutions. These methods are not described exactly in the paper.
Three of the methods, {\em Isolation}, {\em Attraction}, and {\em Collection}
attempt to move a (single occurrence) of an unknown to one
side of an equation. If the unknown occurs in more than one
place, heuristics are used to try to merge these occurrences.
{\em Polysolve} attempts to solve polynomial equations. The ones it
solves are those likely to occur in ``cooked'' problems for
high-school students: quadratics, or polynomials with small-integer
zeros, or minor transformations on them. Any equation
of degree 3 or more, or requiring factoring, or involving
extra symbolic parameters, or (I suspect) division
or GCD for simplification, will not work.
{\em Homogenization} is an attempt to find an appropriate substitution
to explicitly recognize the relationship of apparently unrelated
terms (like $\exp (x)$ and $ exp (3 x)$).
{\em Function Swapping}
is essentially a heuristic attempt to apply known inverses to both sides of an
equation.
\section{Should We be Impressed by PRESS?}
Most mathematicians do not need help to solve this artificial
class of high-school algebra problems.
In any case, it appears that PRESS does not find all solutions,
nor does it distinguish between actual solutions and extraneous
ones.
It would help if
the paper actually stated the form of the solutions which the computer
obtains for the sample problems.
There is some evidence that the program produces forms that
are not particularly useful. The discussion below
even suggests that in some cases
that the authors do not know (all) the solutions
to some of the examples!
Furthermore, it seems quite unlikely that a "solution vetting [checking]
procedure" to eliminate extraneous roots
would be feasible with the heuristic methods used by PRESS. Some
of the problems are computationally undecidable, for example. Others
can be solved by much more powerful simplification programs than
that which apparently exists in PRESS.
Since some of the criticisms may seem rather harsh, we
supply some specifics:
\medskip
Equation 2 is $ \cos(x) + \cos(3x) + \cos(5*x) =0 $.
The authors advocate solving this by
a trick that works for ``cosine terms
in arithmetic progression.''
Notice that
$ \cos(x)+\cos(5x) = 2\cos(3x)\cos(2x)$, so we can rewrite
the problem as
$\cos(3x) (1+\cos(2x)) = 0$.
``The cos(3*x) can then be factored out, and the other factor
produces the other root after a simple application of Isolation.''
The program presumably produces $x=\arccos(0)/3$ or perhaps
$\pi / 6$, and$ x= \arccos(-1 ) /2$, or $\pi/2$.
A reasonable requirement on an equation solver is that it
be able to indicate how many solutions there are, and provide
a representation for them. It seems doubtful that PRESS responds
that there are an infinite number of positive and negative solutions at
the following multiples of $\pi$: ($ \pm1/6 \pm 1/3$, $ \pm 1/2\pm 1$).
If the program were to return the answer as expressions in $\arccos$,
it would appear that there were but 2 answers. There is no indication
how PRESS deals with sets of answers.
Incidentally, the program seems to deal in degrees, rather than radian
measure for angles.
\medskip
Equation 6 is $\log(x-1)+\log(x+1)=3$.
The solution is alleged to be $x=\pm \sqrt{e^{3}+1}$.
This was obtained by claiming that $\log(x-1)+\log(x+1) = \log(x^{2}-1)$,
which is not always true. For example, when $x=-\sqrt{(e^3+1}$,
the left-hand side is $3+ 2 \pi i$.
There is no indication that the program or the authors realize
that only the positive square-root is a solution.
\medskip
Equation 7 is
$\exp (3x)-4 \exp(x)+3 \exp(-x)=0.$
The solutions are alleged to be $ x=\log(\sqrt{3})$ and $x=0$.
The additional solutions, $\log(-1)$ and $\log(-\sqrt{3})$ are apparently
also produced by PRESS, but it is suggested that a future implementation
would reject these. In fact, if $log(-1)= i \pi$, there is
nothing wrong with either of the rejected
answers. There are an infinite number of other solutions for other
values of $\log(-1)$.
\bigskip
I suspect that there are numerous other traps into which PRESS will fall.
\section{Meta Level Solving}
So what if the mathematical methods are not so great: what about
this `meta-level' idea?
It is basically another level of heuristics. I found it curious
that the arithmetic-progression-of-cosines is
a meta-level heuristic.
So what do the authors mean by this meta-level?
They apparently mean the use of local cues to direct
the search for a method to invert an equation,
rather than what they seem to think is the alternative:
trying to run the axioms of arithmetic backwards.
I doubt that any of the methods used by the
algebraic manipulation systems Macsyma, Reduce, Mumath, Scratchpad,
SMP, or Maple include
directly accessing axioms of arithmetic. PRESS
seem to nearly ignore alternative, algorithmic
methods for some important sub-classes of these equation-solving
that are used by other systems.
\medskip
What kinds of local clues have the authors
elevated to Meta-Level Concepts?
It appears they are ideas such as
Is there more than one occurrence of the unknown?
How close, measured syntactically, are terms in which the unknown occurs?
Is the problem a polynomial equation?
I am unimpressed by this meta-level. It does not seem
like a useful subdivision of responsibility or a even a realistic
strategy for solving non-trivial equations.
\section {How does PRESS compare to existing algebraic manipulation programs?}
It would appear that PRESS and equation-solving programs in Macsyma,
Reduce, Mu-Math, Maple, etc., can solve many of the same equations.
Having tried some of the examples with Macsyma, it seems that
the {\tt solve} program itself does not have the capability to handle
these problems ``cold''. However, a preliminary transformation by
another simplification program (e.g. {\tt logcontract}, {\tt trigexpand},
{\tt exponentialize}, {\tt ratsubst}), brings the problem into a solvable form.
Thus a front-end which would heuristically call one or more of
these algorithmic simplifiers and then call {\tt solve} might be used
to construct a poly-algorithm which would out-score
PRESS on a set of symbolic equation problems.
\medskip
Can PRESS combine the merits of searching/matching with
mathematical methods? Probably by
discarding most of PRESS and adding
some additional heuristics to any of
the well-known systems: but
generally at the risk of
introducing extraneous roots (difficult to check), or possibly missing
roots.
There is considerable
literature on solving equations by computer, none of
it referenced. (See, for example, the bibliographies in {\em Computer Algebra}
edited by B. Buchberger, et al.)
\section{Conclusion}
This paper describes a well-publicized ``artificial intelligence'' project,
PRESS, from a distinguished research institution.
The program has substantial design
flaws proceeding from its basic premises in AI and search, which
emerge as defects in
its detailed design.
PRESS appears to not represent an advance in the state
of the art in symbolic mathematics. Rather, it is an attempt to solve, using
weak methods, a set of canned problems unrepresentative of mathematical
problems outside the realm of simple school exams.
Although the paper is easy to follow, I would have found it useful
if the authors had given concrete results of the output from PRESS,
(and perhaps other systems) on their examples, compared their methods
with others in the literature (computer and mathematics). However,
correcting
such problems would only strengthen the
superficial plausibility, and not attack the real weakness of PRESS.
\section {Recommendation}
What kind of a journal would accept a paper on
computer arithmetic that presented
a program to do 3-decimal-digit subtractions the way a 4th-grader
might do them? Perhaps a journal on elementary educational psychology,
but not a mathematics or computer science journal.
In the same way, it may be appropriate for PRESS to be described
in a journal on psychology or artificial intelligence, but not
on mathematical problem solving.
I suggest the
paper be submitted to the SIGSAM Bulletin
as a public service to explain to the
symbolic mathematics community what it is that the PRESS program does.
Perhaps an interchange in that forum would be useful. If so,
it should certainly include critical
comments reflecting the point of view here.
\medskip
In particular, the apparent success of PRESS from an AI
point of view (perhaps as an ``expert system''?)
might provide an interesting contrast
to its rather different appearance
in a field in which more than a few ``strong'' methods are available.
\bigskip
This report is being signed to allow direct
correspondence from the authors of the paper to the referee.
I may be
reached by electronic mail \verb|fateman@berkeley.edu| or by
mail c/o EECS Dept. Univ. of Calif., Berkeley CA 94720, USA.
\end{document}