Partial differentiation
Hi,
How do I find the partial derivative of an equation symbolically? How do I make the computer automatically find the derivative of a function without heuristics? The difference quotient can be used to find the derivative, but what about functions such as sin, cos, log, and special functions?
The CAS cannot differentiate these functions because it does not "understand" how the functions are composed of. I have to explicitly define these functions its identities using simpler functions.
For example, for the sin function, it has an identity: sin(x) = (e^(ix) - e^(-ix))/2i.
I can define the cos function, for example, using this: cos(x) = sin(x + pi/2).
However, how do I find the logarithm?
I can define the the log(x) function by using algebra:
log(x) is the same as solving for "y" in the equation: b^y == x
I can tell the CAS that addition is repeatively adding one, multiplication is repeated addition, exponentiation is repeated multiplication, etc.
I can tell the CAS that division for "a divided by b" is the same as solving for "x" in this equation: x * b == a
The CAS can now "understand" the functions so it can automatically deduce that integer addition, multiplication, etc. are associative, communitive, etc.
The main goal of computer algebra systems is to optimize equations and functions.
Anyway, how do I tell the CAS to automatically find the derivative of functions?
For example, how do I let the CAS automatically find the derivative of some functions without using heuristics such as pattern matching?
Thank you very much
[1640 byte] By [
alta] at [2007-10-3 0:20:28]
Now let me get this straight
It takes some 12 years of education through high school and some fraction of 4 years to get a reasonabaly intelligent and mathematically inclined human being to even understand what partial integration is
Precious few if any of these human entities are able to deduce the existance or the utility of abstract algebraic concepts like associativity, and commutattivity just by being told that addition is repeated succesor function, multiplication is repeted addition, exponentiation is repeted multiplication.
And by the way tell me how come the first two that are just repetitions of the previous functions are commutattive but exponentiation which is also just a repetition is not? I assume that this is just as obvious to you as it will be to the CAS.
And yet somehow this magic CAS system, that we will momentarily tell you how to build, is going to make all these deductions, derive the principals of math that it has taken human genius thousands of years to evolve, and generate the code to find your partial derivatives symbolically to spare you the need to write some code with heuristics?
So, do you want fries with that?
> Precious few if any of these human entities are able to deduce the
> existance or the utility of abstract algebraic concepts like associativity,
> and commutattivity just by being told that addition is repeated
> succesor function, multiplication is repeted addition
I remember a throw away line in a maths lecture when I was young to the
effect that the commutivity of multiplication was "of course" equivalent to the
axiom that stated that two triangles in perspective from a line would be in
perspective from a point.
Mathematics is, fundamentally, creative - but good luck with the CAS!
Computers are very bad at resolving (or even calculating) formulas.
You have to talk to someone who is really into this matter, a real expert. Teaching the computer math is such a complex thing, that only a bunch of companies around the world really managed to develop something useful in there.
DON'T try it yourself!
> DON'T try it yourself!What is that all about? If the dude wants to try to build a CAS, then he should do so. He may not be successful, but at least he'll learn something on the way. You don't just give up if something's going to be hard.
> > DON'T try it yourself!
>
> What is that all about? If the dude wants to try to
> build a CAS, then he should do so. He may not be
> successful, but at least he'll learn something on the
> way. You don't just give up if something's going to
> be hard.
Furthermore, it just so happens that the one stated goal, to have the CAS perform partial derivatives without the use of heuristics (meaning guessing) is one of the easiest CAS problems. Derivatives don't require heuristics. It is far easier than say simplifying the output which in the absence of a cannonical form is basically a heuristic.
It was just all the other stuff, about telling the system a few facts and asking the system to deduce the laws of mathematics and to somehow code itself up that betrays such breathtaking innocence that it became difficult to give the typical answer that one gives to gives to questions about how to build symbolic math packages.
But I did say that I would tell you what to do so here is the typical answer:
1) chose the subset of math that you wish your program to work with. This is NOT an optional step. You can not do everything. No one comes even close to knowing it all. Algebraic Topology is not Differential Geometry is not Linear Differential Equations, is not Arithmetic. Even in the lowly field of arithmetic you got to be asking yourslef, "Am I only dealing with integers or do I allow rationals or do I attempt real numbers - do I deal with arbitrary precision ..."
You must choose a subset or you will never get anywhere. Do not kid yourself that you can design a framework that will allow you to eventually include polynomials, and trig, and geometric proofs, and polytopes in higher dimensional spaces. I mean, how are you going to represent Desarg's theorem of projective geometry or Russel's hierarchy of Types? That is also a black hole. The art is how you limit your attention.
2) choose a representation for that subset. Meaning choose a language. For example if you do arithmetic a fairly simple representaion is 2 + 3 =, the traditional calculator language. However you could always choose reverse polish instead like 2 3 + .
In a more complicated setting, like being able to do polynomials, you again must deal with subsets. Do you mean all multi-variate polynomials or are you dealing with polynomials with a single variable? These have repersentattional issues that you must address. Are the variables just single letters x,y,z? when you run out of letters do you shift to "fred" "Bob" and "Joe" or do you go to Xsub1, Xsub2. Does the expression 3xy have one variable, xy, or does it have two?
Also, when building your language don't forget the imperatives that are absent from traditional paper math notation. Those would be things like "Solve this for Q, numerically out to about 3 decimal places. and quit if some nearby singularity in the analytic extension to the complex plane is causing an instabiity that makes it take more than a minute to converge."
Take some time and choose your language carefully. It should be something that conveys meaning to the user, since that is one entity that will be using the language, and it should also be not too difficlt to parse, because that is what the computer is going to have to do next. Excuse me, I mean it the part that YOU are going to have to do next.
3) Once you have defined a domain to talk about and a little language in which to do that talking, the rest is rather straightforward. You build a parser, you crack your language into an internal representation, probably a tree. You then apply your little tree re-arrangement algorithms based on your imperatives to shove the internal symbols around, much as you would on paper, and there you go... Computer Aided Symbolic Mathematics
If you would like a little exercise to get the full flavor with almost none of the heavy lifting. Write the little calculator expression parser that deals with the minimal language that consistes of integers of arbitrary precision, exactly 4 operators, plus, times, subtract and negate. It should use parenthesis properly and calculate and prints the single integer result of the expression. Do this without using the BigInteger package - becuase the purpose of the exercise is to see how to do symbolic manipulation and how to do your own list processing.
Thus it should be able to reduce the string
3*(2+-4) + 123456789012345678906
to the string
123456789012345678900
Don't forget to spew a cryptic error number if the input was not a WFF. :)
If you are a Java God and know what you are doing this is an afternoon's work. If you are a little less sure it will be about 3 afernoons (one for +,-,-, one more for *, and another one for () and operator precedence.) If it takes longer than a week, either take a class or ask for help.
When you are done, you will have a nice handy little calculator program the does infinite precision integer math and you will have a monkey on your back that will never leave you alone. You will start asking yourself, "Could I extend this thing to include factorial. I mean it is just one symbol ! and it binds tightly so it doesn't change the parse much and it is trivial to evaluate once multiplicattion is working.."
Trust me, 3 days of work and you could be hacking on computers for the rest of your life.
Advance with caution.
Enjoy!
I believe it is possible for a CAS can deduce laws of mathematics if programmed cannily. Laws such as associativity, communitivity, distributivity, etc. can be deduced from its definitions easily by it without decree.
But how can a cas find the derivative of this?: f(x) = x^100000
It does not need to expand this function. It must use heuristics. But because I do not want to explicitly implement the power rule to the CAS, the CAS has to deduce the heuristic itself. The CAS will automatically make a proof of the power rule, which is easy. If the proof is valid, the CAS will automatically make a heuristic by itself for the power rule.
Laws such as associability, communitivity, etc. can be easily proved by a CAS. Humans can prove the laws easily. In my opinion, the stereotype that computers are so stupid that it cannot perform some tasks that is trivial for humans is completely wrong. Because I am an optimist, I will believe that a CAS can deduce the laws of mathematics correctly, because humans can prove it trivially.
Simplifying an expression is not a heuristic because simplifying is akin to optimizing the expression. The computer can just find an expression equal which takes the most efficient amount of operations without using heuristics. However, putting it in canonical is a heuristic because the canonical form is usually not the optimized form. The canonical form is basically an "elegant" form of the expression.
On the other hand, integration is much harder for a computer than differentiation. The CAS cannot simply use pattern matching because some expressions cannot be integrated by just ysing this method, which is also true for humans. The computer must to use an algorithm.
It can use series expansion to find the integral of a function, which is easy because find the series expansion of the function is repeatively differentiating the expression so it forms a Taylor series. It can use partial fractions for integration. It can use the Risch algorithm for integration.
alta at 2007-7-14 17:11:58 >
I would not post this useless stuff about CAS anymore because this is a Java forum. The reasons for not using heuristics because it would make the CAS not robust, cannot do noncommutative rings, etc. I also do not like to re-invent the wheel. I do not like build a CAS that is not better than other CAS. I want to make a CAS because other CAS do not have the features that I need from other CAS.
alta at 2007-7-14 17:11:58 >
> deduce the heuristic itself. The CAS will
> automatically make a proof of the power rule, which
> is easy.
Automated theorem proving is easy!? I'm not so sure about that.
You might be interested in doing some research in the area of formal proofs with computers. The most ambitious project in this area that I'm aware of is the flyspeck project (~20 man years left to complete):
http://www.math.pitt.edu/~thales/flyspeck/
Interesting reading. There are plenty of links on that page to tools that will help you explore the problem of theorem proving.
I'm a very sloppy mathematician myself, e.g. when I have to solve for, say x
in an equation, I scan over the equation, fiddle diddle with some simple parts,
recognize that a sub-expression occurs on both side of the equal sign so they
can go, move something back and forth and voila, problem solved.
Basically it's an extremely heuristic process of expression recognition and a
bit of fiddling so I decided to build a program that mimics my sloppy behaviour.
I talked things over with another (extremely sloppy) mathematician and decided
that pattern matching was not the way to go so I came up with 'tree matching
and rewriting'.
A 'meta expression tree' (MET) is just an expression tree (ET) where the variables
in that tree have a special meaning:
1) variables starting with an 'i' in MET matches a variable in ET
2) variables starting with a 'c' in MET matches a constant in ET
3) other variables match expressions
4) for two identical variables in MET they must match identical sub-expressions
in ET.
5) expressions are ordered as follows: contants < variables < other expressions.
6) in those three subgroups simple lexicographical orderering does the rest.
7) an expression solely consisting of constant operands and functions/operators
can simply be evaluated numerically.
e.g. the expression (3*x-x*2)/((42-41)*x) has the following ET:
__/_
/\
-*
/ \/ \
**- x
/ \ / \/ \
3 x x 2 42 41
Rule 5) and 6) reorder this expression a bit:
__/_
/\
-*
/ \/ \
**- x
/ \ / \/ \
3 x 2 x 42 41
and rule 7 takes care of of this:
__/_
/\
-*
/ \/ \
**1 x
/ \ / \
3 x 2 x
Here are some MEs (METs in textual format) and their rewriting MEs:
c1*x-c2*x> (c1-c2)*x
1*x> x
x/x> 1
... these reflect my simple sloppy thought processes a bit. When I use these rules
(in no particular order), the expression tree vanishes slowly:
__/_
/\
-x
/ \
**
/ \ / \
3 x 2 x
__/_
/\
*x
/ \
-x
/ \
3 2
__/_
/\
*x
/ \
1x
__/_
/\
xx
1
I've collected a few 100 or so of these simple MET 'rules' and apply them to quite complicated
expressions, equations etc. Here are the rules that take care of ordinary differentiation:
delta=((x) delta x)(1)
deltaadd=((y+z) delta x)(y delta x + z delta x)
deltamin=((y-z) delta x)(y delta x - z delta x)
deltamul=((y*z) delta x)((y delta x) * z + (z delta x)*y)
deltadiv=((y/z) delta x)((z*y delta x-y*z delta x)/(z*z))
deltaconst=(c delta x)(0)
deltasine=(sin(y) delta x)(cos(y)*(y delta x))
deltacosine=(cos(y) delta x)(-sin(y)*(y delta x))
deltatangent=(tan(y) delta x)(1/(cos(y)*cos(y))*y delta x)
deltalog=(log(y) delta x)((1/y) * y delta x)
deltaexp=(exp(y) delta x)(exp(y) * y delta x)
... being sloppy as I am I'm sure I must've forgotten a few of them ;-) Those couple of
hundred of those 'rules' and basically all the system has; what it does is: compile the expression,
and race through all these rules like a madman (like my sloppy behaviour) and see if at least one is
applicable; if so, apply it and race through it again. If not, stop.
More than once the results printed out by that little system have amazed me. I realize that
there is no clear separation between algebra, calculus, trig etc. but a bunch of rewriting
METs can go quite far. Maybe I should investigate the idea a bit further ...
kind regards,
Jos
JosAHa at 2007-7-14 17:11:58 >
Jos, The only thing I don't quite follow in your post is your statement
"...decided that pattern matching was not the way to go.. "
You then proceed to describe your little pattern matching system that looks for little local shapes in the trees that you are your internal representation.
All the basic symbolic math packages, Maple, Macsyma, Mathematica, Derive and who knows how many others were either written in Lisp or built along similar lines. They keep their expressions as long lists (list of list of lists, i.e. trees) of symbols which they then locally rearrange based on little local pattern matching. Since the data is kept in trees typically the matcher and the rearranger are just the same.
after all the expression 2*x is a tree and the expression
X*Y = Y*X
is a statement of the commutativity of multiplication
The equality is the roof of the tree that represents the rule and the rearrangement is just that if you find a tree that looks like the left subtree of the equality you can replace it with the right subtree. The X and Y are just free variables that can match any subtree.
I know that you know all of this JosAH since you clearly already implemented the system.
What I don't understand is what you consider "pattern matching" to be that you don't want to call this pattern matching.
What you have done strikes me as essentially the same as what other folks have been doing in symbolic math for decades. That is not a put down, that is praise. The pros don't have any magic dust that that makes their systems work better. All they have is more cash and more time invested in their code base which is doing the same basic thing.
I also have a comment for Mr. alt -
I did not intend my comments to discourage you from posting to this forum. While this is a Java forum, the Algorithms subsection would be pretty lame if it was only Java focused. Algorithms transcend language.
I do feel that if you want to write a symbolic math system for whatever reason you should do so and I will be happy to help kibitz.
However, I do believe that you have stated several goals any one of which could take quite a while to achieve. You want the system to be able to take partial derivatives. That will requie some work. You don't want to input the power law. You want the computer to discover it. This will also take work, both for you and for the computer.
I am not saying that you can't do both, I am saying that either one is work and you should decide where you want to start. Suppose you do want to evaluate partials. Well the power law is necessary. You can write it down in a single line.
If the computer grinds away at it's math discovery process for a year and finally (Hooray!) develops the power law, if it is indeed correct it will be EXACTLY the same law that you could type in in one single line today.
So after its year of grinding and developing this law what should the computer do next in order to implement this law and use it to reduce expressions?
That is another problem that you will need to solve. So which one do you want to work on first, the bit about deriving laws from simple abstract algebra or the part about converting laws into code that will actually do the symbolic manipulations that you wish to do?
My guts tell me that the place to start is with the symbolic manipulation, because it will help you understand the problems that the machine will need to solve when it starts trying to write symbolic manipulation code based on laws that it derives.
Furthermore, chances are if you want the computer to be deriving the power law it will probably need to do this by the classical methods of logic which are of course just more symbolic manipulation.
The advice I gave:
1) choose an reduced problem area to work on
2) choose an external and internal representation
3) start developing methods to match and rearrange your internals.
I believe remains valid regardless of whether you want to start on the logical derivation of rules or the massaging of rules into code.
The advice that JosAH gave is much more detail on both the representation and specific methods of matching and rearranging.
By all means, if you have things that you want your system to do that current symbolic packages do not do, focus on those things first. But the fact that your system will do things that others don't does not mean that you won't build on the same foundation that many others have used before you, namely: 1) a domain that you work in, 2) a tree representation of that domain 3) a bunch of rules (which are also trees) that are used for manipulating ALL the trees (including the rules) in your system.
> Jos, The only thing I don't quite follow in your post
> is your statement
>
> "...decided that pattern matching was not the way to go.. "
>
> You then proceed to describe your little pattern matching system that
> looks for little local shapes in the trees that you are your internal
> representation.
That was me expressing myself sloppy again ;-) My very first attempts
at this tried to find identical sub expressions by simply matching for
it in the textual representation of the expression, which obviously didn't
work out well.
I should have written 'textual pattern matching is not the way to go'.
Sorry for the confusion I caused.
kind regards,
Jos
JosAHa at 2007-7-14 17:11:58 >
The CAS can automatically deduce some rules from the code below:
add(a, b) := succ^b(a);
sub(a, b) := solve(x + b == a, x);
mul(a, b) := add^b(a);
div(a, b) := solve(x * b == a, x);
pow(a, b) := mul^b(a);
e() := limit((1 + 1/x)^x, x->infinity);
exp(a) := pow(e(), a);
log(a, b) := solve(b ^ x == a, x);
log(a) := log(a, e());
d(f(x)) := limit((f(x+h) - f(x)) / h, h->0);
fibonacci(0) := 0;
fibonacci(1) := 1;
fibonacci(a > 1) := fibonacci(a-1) + fibonacci(a-2);
factorial(1) := 1;
factorial(a) := factorial(a-1) * a;
That's why have to only define the successor function heuristically and all of the other heuristics are automatically deduced. The CAS uses a brute force search, evaluate all of the combinations of the expression without changing its value, and then selects simplest form of the expression. Because brute force search is slow, it automatically deduce laws so it can heuristically apply the pattern so the simplification process can be faster. When differentiating a function such as f(x) := x^1000000, it is fast because it uses the power rule because the CAS prooved the power rule from the binomial theorem, which is not really automatically derived. I gave a hint to the CAS to use the binomial theorem to derive the power rule, so it is not really "automatically" deduced.
The sum and product rule are trivial because it has to use a brute force search to find the difference quotient of the functions. The brute force search to find the simplest form of the expression is analogous to the evaluation function of chess programming.
The CAS can automatically generate some efficient algorithms similar to fifth-generation programming languages such as Prolog. It can automatically find a closed-form formula for fibonacci numbers by just defining this:
fibonacci(0) := 0;
fibonacci(1) := 1;
fibonacci(a > 1) := fibonacci(a-1) + fibonacci(a-2);
From the above definition, it automatically generates a formula similar to Binet's formula, which is a closed-form formula for the n-th fibonacci number. I find the CAS can optimize farther than any fifth-generations languages such as Prolog. But I do not know how to make the CAS generate efficient arbitrary precision algorithms such as multiplication algorithms. How do I make the CAS automatically generate near optimal arbitrary precision numeric libraries for major platforms by just defining the processor's instruction set? How do I make the CAS automatically generate Fast Fourier Transform multiplication algorithms?
Thank you very much
alta at 2007-7-14 17:11:58 >
I programmed the CAS so it can learn stuff. I programmed the sucessor function. The CAS treats variables as functions. The CAS uses a brute force search. It searches the combinations, evaluates them, and chooses the most efficient one. String matching is slow, so the function names are converted to IDs. String matching for function names would take O(n log(n)) time, but when I use IDs to reference to the function, string matching took constant time.
The CAS matches the "unrolled" form of the recursive function. For example when the tree contains add(add(add(2))), it would match the recursive defination of the "unrolled" multiplication function, so it would be converted to mul(2,3). The CAS basically converts all of the functions to the successor function, optimize them, then replaces the successor function with simpler functions.
Because the CAS does not "know" that mul(2,3) is more efficient than add(add(add(2))), I have to assign a complexity rating for the efficiency of each function. Addition is assigned O(n). Multiplication is O(n log(n)). The brute force tries combinations of the functions, sums the complexity of all of the ratings, at each combination, and then picks the combination that has minimum complexity rating. This method is highly analogous to chess programming.
Every time the whole tree has to get evaluated. The speed is unacceptable for larger trees. A major speed-up is to only evaluate the nodes that are changed.
An advantage of brute force search to optimize the expression is that it is very easy to add functions not even touching a single line of Java code. The CAS uses a domain-specific programming language.
Another advantage of using this method is that the CAS would result less buggy. Pattern matching is considered "hackish" and "naive". Many CASs are filled with bugs. Using a pure logic system, without pattern matching, would result in a much less buggy CAS.
Traditional CASs use pattern matching. It is easy to program. However, when the CASs contains hundreds of predefined functions, using of pattern matching becomes exponentially harder and tedious to maintain. Making a CAS based on pure logic, pattern recognition, artificial intelligence, and automated theorem proving is much more manageable.
CAS does not have to prove all of the rules by itself. "Hints" for proving theorems would help greatly. The CAS can just analyze some proofs by other mathematicans, check the proof if it makes sense, and apply the proof. The proofs are written in the domain-specific programming language used by the CAS. The CAS can learn from the proof using pattern recognition, and try to proove other problems from the prooving techniques it just learned.
Synthetic creativity is a challenging task. Synthetic creativity is vital for automated theorem proving. The CAS has to do random things to emulate creativity. A rudimentary Monte Carlo method for emulating creativity is slow. It can be improved from some techniques such as imitating the creative process of proving theorems using the techniques learned from previous proofs.
Synthetic creativity can also be improved by conceptual blending. For example, to find a method to calculate fractional derivatives, integrals, and differintegrals, it relates to the fbinomial thereom for proving the power rule. Because fractional calculates involves non-integer values, the binomial theorem cannot be applied. But with conceptual blending, the CAS knew that the Gamma function is a generalization of the factorial function, it can apply the binomial theorem using the similar Gamma function, instead of the factorial function.
It is possible for the CAS to generate fast FFT algorithms. It can generate them by analyzing the proofs that FFT algorithms are faster. Than it applies the proofs. It can generate fast arbitrary-precision libraries written by assembly by trying to convert the expression to a limited set of process and optimizing it.
Using brute force search with evaluation can help, not only simpler, but more customizable. Suppose a processor have a specialized sqrt() function. The CAS knew the sqrt() function is assigned faster complexity than using Newton's method for this type of processor. The sqrt() function has faster complexity, so the brute force search can make use of the sqrt() function by applying it more. It is the same with other specialized operators, or missing ones. If a processor does not have a "greater than or equal to " but a "greater than" instruction, the CAS can optimize the code for the "greater than" instruction.
Brute force search and evaluation has much more advantages. Suppose the CAS has to implement the expand() function, which expands parenthesized expressions. A user can just define the expand() function by setting the a penalty, or a higher complexity rating, for using parenthesis. If using pattern matching, the user has to code the expanded form of every function, which is extremely tedious. Same with the solve(), simplify(), factor(), etc.
There are a lot more ideas not written down.
There are a lot more advantages using brute force search but not written here.
alta at 2007-7-14 17:11:58 >
Are you going to publish your results or otherwise make them available to the community?
