Organizing Math as a Rule-based Decision Tree

Comments by Albert D. Rich, Co-author of muMath and Derive, and originator of Rubi

Since the beginning of recorded history, mathematicians have been amassing mathematical truths at an ever greater rate and into ever more esoteric realms. However, this vast amount of knowledge has not been systematically organized so the precise formula required to solve a particular problem can easily be found. It’s like leaves scattered on a lawn, rather than organized into a heavily branched tree with each leaf attached to the appropriate limb.

It’s Feasible

I am convinced much of mathematical knowledge can be organized into a rule-based decision tree that is unique and optimal. Others have proposed similar such grandiose programs, but the rule-based paradigm actually makes it possible to accomplish it. And this is not just armchair speculation.

Over my 40-year career implementing computer algebra systems, I have been driven to the realization that rule-based systems are the optimal way to get optimal results. This is not limited to my current focus: indefinite integration. The muMath and Derive systems I co-authored are general purpose programs able to solve a broad range of problems. Throughout their development, these systems gained knowledge by the addition of new rules and the generalization of existing ones.

David Stoutemyer and I began the design and implementation of muMath in the late 1970s. From the earliest versions, despite being limited to a 64-kilobyte address space, the system provided a mechanism for assigning rules to the property lists of functions and operators. When an expression was being evaluated, the property list of its top-level function or operator was searched to see if there was a rule specifically for the expression’s second-level function or operator. If so, the rule was applied and the process repeated recursively until no more rules applied.

Although crude by today’s standards, this two-level pattern matching mechanism was used extensively in the implementation of muMath. Also, its modularity and simplicity allowed users to add their own rules to the system. Derive was also heavily dependent on rules to simplify, solve and integrate expressions; but the rules were “hard-wired” in programming code. Although more powerful than muMath, Derive was sometimes criticized for not allowing users to define their own rules for built-in functions and operators.

muMath and Derive are no longer commercially available. And in any event, computer hardware and software are highly ephemeral, so the mathematical knowledge in these systems will soon be lost. After the development of Derive was terminated in 2005, I was determined to find a way to pass on the accumulated knowledge in such systems that would survive changing technology.

To that end, I began implementing a Rule-based integrator, nicknamed Rubi. Currently, it uses pattern matching to uniquely determine which of its over 6600 integration rules to apply to a given integrand. Conceptually, however, the system can be thought of as a simple rule-based decision tree. This is what distinguishes Rubi from the conventional program code used by the majority of computer algebra systems to integrate expressions.

Indefinite integration accounts for only a tiny fraction of all mathematical knowledge. However, based on my experience implementing muMath, Derive, and now Rubi, I see no reason why much of the rest of mathematics cannot be organized as a rule-based decision tree as well. Certainly much of analysis including equation solving, expression simplification, differentiation, summation, limits, etc. can be automated using this paradigm.

It’s Desirable

So assuming a discipline of mathematics can be reduced to a rule-based decision tree, is it worth the considerable effort required? My experience implementing Rubi clearly indicates the answer is a resounding yes! The benefits include:

To fully solve a problem several such applications may be required. For example, Rubi uses over 427,867 rule applications to integrate the 71,183 problems in its test suite, for an average of about 6 applications per problem.

Therefore, only about 76 (=12.7 x 6) tests are required to fully integrate a typical problem in the test suite. What’s more, the tests are fast and easy to perform. For example, common in Rubi are tests to determine if an exponent is an integer, fraction or symbolic; or if the discriminant of a quadratic (b2-4ac) is positive, negative or of unknown sign.

But since Rubi 4.15 is slowed down by its use of pattern matching to search down a list of over 6,600 rules, it is only able to integrate expressions at roughly the same rate as Mathematica’s built-in integrator. However, the forthcoming version 5 of Rubi uses the highly efficient if-then-else control construct instead of pattern matching to select rules. Preliminary testing indicates Rubi 5 will integrate expressions almost 2 orders of magnitude faster than Rubi 4.15 or Mathematica.

All the integration rules, test suite problems and results demonstrating the above benefits are freely available on Rubi’s website.

Rule-based Decision Trees Exist and Are Unique

Finally, it should be noted that Rubi is an ever improving, but imperfect, model of the actual integration decision tree existing in some Platonic sense. In the same way, software simulating a hurricane is just an imperfect model of the actual hurricane blowing in the physical world. So Rubi may be just a model, but she’s a darn good-looking one.

Not only does an optimal integration decision tree exist, it is unique. Time and again, in order to achieve optimal antiderivatives for integrands of a given form, I was forced to restructure Rubi’s decision tree and/or discover new rules. Often this repetitive process severely tested my deeply held belief that an optimal set of rules for integrating expressions must exist. But eventually, the process always did converge, leaving me no choice in the design of the decision tree.

Rubi provides proof-of-concept of the utility of organizing mathematical knowledge in the form of a rule-based decision tree. Hopefully, it will convince others in the math and computer science communities to join the rule-based revolution, and explore whether it applies to their field of interest as well.