Approximation in Mathematical Domains

1. Introduction

Explanation-based learning makes use of domain theory to construct an explanation for a single observed example. The explanation is then generalized so the generalized concept can be used in future problem-solving. Explanation-based learning (EBL) is currently the subject of much research. Many EBL systems have been constructed and work is proceeding in cap­ turing a domain independent generalization technique [1-3).

EBL depends on the ability to construct an explanation for the example. This becomes difficult when we a_re dealing with an imperfect domain theory [1. 2, 4. 5). Mitchell outlines three types of imperfect theories: those which are inconsistent. those which are incomplete. and those which are intractable. Our focus in this paper is with intractable theory in mathematical domains.

An intractable problem is one which is very difficult to solve where. because of the great number of rules and/or ways they can be applied. we do not quickly reach the goal. Many real-world problems are of this type. For instance. consider trying to explain why the unemploym_ent rate changed. It is not possible to construct an exact explanation. There will always be further order causations which must be considered inconsequential. Economic theories explaining the change are necessarily approximate. Furthermore. due to the approximate nature of the explanations. many plausible explanations are possible as is evidenced by the variety of economic views.

In mathmatical domains. where a set of exact rules is available, we encounter intractability due to the great number of possible applications of the rules. Chemists who work in chemical kinetics very often need to solve very complicated differential equations. Frequently. the equations. as they stand. along with the set of mathematical operators characterize an intractable problem as discussed above. Chemists proceed to a solution in the only way they can: by applying their common- In a mathematical domain. the in~erences we make using our qualitative knowledge can lead us to consider certain quan­ tities negligible with respect to other quantities. We can then modify our formulae on the basis of the determined negligible quantities to arrive at an approximate set of formulae. For example. a variable can be neglected in a sum formula if it can be considered negligible with respect to all the other quantities in the formula. Figure 1 illustrates this: Given:

This reseuch was supported by the National Science Foundation under grant NSF 1ST 85-11542.

Figure 1: Approximation Within A Sum

There are many variations on this rule. They all ultimately involve neglecting a quantity because it is insignificant in rela­ tion to other quantities in a sum. Several researchers have developed systems which perform order of magnitude reasoning similar to that illustrated above. Recent papers include [9] and [10]. We will apply this type of reasoning to the introduction of approximations.

Figure 2 shows the method by which approximation is used in solving mathematical problems. The knowledge the system uses in solving the problem has both domain dependent and domain independent components. The domain independent portion is pertinent to any examples which involve

mathematical reasoning. Such problem solving skills rely on both quantitative and qualitative knowledge. There ·has been a tendency in past work to separate these. To use approximation in ·mathematical domains. one must frequently use both types of reasoning.

When purely quantitative reasoning is used. many com­ plex problems can't be solved. The system must take full advantage of the information available. including Jess exact qualitative information which can help it to simplify the situa­ tion.

Purely qualitative reasoning can also fail. The quantita­ tive equations representing the problem contain much inf orm.11- · tion. Representing everything in a qualitative fashion is not always desirable and can lead to a large number of envision­ ments which must be disambiguated.

One starts with a representation of the problem state­ ment.1 This representation can be translated into a quantitative representation which consists primarily of equations describing the situation as well as the expression or expressions which we are trying to find. Such a translation makes 'use of quantitative domain knowledge which explains exactly how quantities are related. Had we decided not to use approximations. we would attempt to use our quantitative mathematical reasoning abilities to solve the problem. If the problem is a tractable one. this will lead to a solution. although it may require much effort. If the problem is intractable. it may be impossible to reach the solu­ tion in this way. 2 So. our next step is to analyze our quantita­ tive representation to see if simplifications can be made. This means using techniques like qualitative magnitude reasoning in conjunction with our qualitative domain knowledge to intro­ duce approximations. The result is a simplified set of equations. due to negligible terms having been eliminated. We bring our quantitative mathematical reasoning to bear on the problem to arrive at an approximate solution. In many mathematical examples. it is possible to check the validity of our approxima­ tions. The last step is to use our mathematical reasoning in con­ junction with the original exact quantitative representation to calculate error. If the error is acceptable. our solution is com­ plete.3 In mathematical domains. this ability to learn about the validity of our approximation is an especially important tool.

3. An Example: Acids In Solution

Now. let us consider how this technique is applied. Here is an example. which has been fully implemented. involving an analysis of the effects of adding an acid to water. This chemis­ try problem. taken from [11. p.113]. is:

Find the concentrations of all species in a 0.010 molar solu­ tion of acetic acid with K 0 = 1.75x 10- 5 . The equilibrium constant for water is K ·. = 10- 14 . The OH- ion concentra­ tion in pure ,.·ater is C ·. = 10- 7 .

This type of problem can become intractable if we introduce more iof!S into the solution but. for purposes of illustration. we . present this simplified version. This example uses straight­ forward inferences. clearly shows how one's qualitative assumptions effect the resulting solution. and shows a quantita­ tive verification of the assumptions. In the problem. the fol­ lowing two equilibria are known to be present:

Equilibrium El represents the dissociation of Acetic Acid (HAc) into H + and Ac- ions in solution. What complicates the prob­ lem is that equilibrium E2 is also present and represents the dissociation of water (Ji ~ ) into H + and OH- ions. The con­ stants K. and K.. are called equilibrium constants. They reflect how far the equilibrium is shifted to the left or right. This concept of an equilibrium can , be repr~nted by a quarti­ tative formula. The respe;ctive quantitative relationships for E1 and E2 are (brackets denote concentrations):

1 We will not address the translation from natural language to the representation.

2 UsuaJly one would resort to numeric methods some of which are actually repeated approximations.

1 If necessary, we can use this feedback in a loop to arrive at the technique of successive approximations whereby our error gets smaller on every iteration until it is within the desired bounds.

In Q2. [H ~]doesn't appear because. since the concentration of water is assumed to be constant. it has already been included in K ·. . Two more equations need to be written: the charge balance equation and the mass balance equation. The charge balance equation equates the total amount of positive charge with the total amount of negative charge:

The mass balance equation illustrates that if we start with C 0 moles/ liter of HAc. that acetate (Ac) is conserved after some of the HAc has formed Ac-.

With a knowledge of equations Ql through Q4 and the con­ stants K ·. K ·.. C 11 and C ·. . a cubic equation can be developed which will lead to an exact solution. However. for most pur­ poses. only an approximation is necessary. For those who util­ ize their commonsense knowledge of chemistry. the approxima­ tion is far easier and yields results far more quickly than the exact solution. Had we considered a problem with more equili­ bria. the order of the exact equation would have increased enough to make this an intractable problem.

The commonsense knowledge which is applied to this problem is represented in the form of inferences. The following two rules from our set of chemistry domain rules are pertinent to this problem: problem:

(Rule 1)

IF the acid is present at a much greater concentration than to- 7 Molar. THEN [on-] will be negligible compared to all other species.

(Rule 2)

IF the ac·id is a weak acid , THEN [Ac-]<<[HAc ]. This is because weak acids dissociate very little.

These rules tells us what to expect the relationship between the quantities to be based on the strength of the acid and/or its concentration. If we knew neither. these inference rules would not help us to make any approximations. But. in this specific example. we now do know that Acetic acid is com­ monly considered to be a weak acid. Furthermore. 0.010 is far greater than 10- 7 · This means that rules 1 and 2 apply. yield­ ing: [on-] negligible with respect to everything and [Ac-]<<[HAc]. This reduces equations Q3 and Q4 to:

Now the system proceeds using its basic quantitative knowledge to much more easily solve for the unknowns. Combining equa­ tions Ql. Q3A. and Q4A we arrive at:

Q2 and Q5A give:

Q3. Q5A. and Q6A give:

Now we have ·expressions for all the unknowns. The expres­ sions are all based on our initial assumptions: the strength of the acid. and the correctness of'our inference rules. In problems like these. we can verify the correctness of our assumptions. We use equation Q4:

The approximation is good to within 5%. We can now express our error in terms of K ·. K ·.. and C 11 as follows:

Once the approximate solution has been constructed. the solution structure is generalized using the EGGS generalization . technique [3] to produce rules like the following:

Learned Rule For Hydrogen Ion Concentration

(dissoc-const water ?k ,.. ) & (dissoc-const ?ha ?ka) & (acid ?ha) & (strength ?ha \\'eak) & (cone ?ha ?cO) and(>> ?cO (expt 10 -7)) & (pos-ion ?ha ?h) & (neg-ion ?ha ?a) & (pos-ion u·ater ?h) & (neg-ion u·ater ?oh)

==> (aqueous-cone ?h (sqrt (* ?ka ?cO)))

Although not shown in the above rule. the error estimation form shown in PEl can be incorporated into the precondition of the rule to check if the rule meets the system's specified accu­ racy criterion.

4. Conclusions

A method has been proposed that shows how approxima­ tion can be used to overcome obstacles in mathematical problem solving [12]. Powerful techniques like these permit solutions to otherwise intractable problems and can facilitate efficient solu­ tion to many less difficult problems. One advantage of using an approximation technique like this in a mathematical domain is our ability to reason about the correctness of the approxima­ tion. Any flaws in our original domain dependent qualitative rules become immediately evident when we attempt to verify the solution. We can also more accurately determine future applicability of the formula.

Many issues have yet to be addressed. This paper has dis­ cussed how approximation takes place in highly mathematical domains. There are many other domains in which approxima­ tion can be used to deal with intractability. Work is underway in developing a system which generates plausible explanations for observed events. An explanation is selected for generaliza­ tion but difficulties with the new generalized rule will trigger generation of a new plausible explanation for the observations.

ACKNOWLEDGMENTS

I would like to thank my advisor Gerald DeJong and the members of the group: Ray Mooney. Jude Shavlik. Shankar Rajamoney. and Steve Chien for their many helpful discussions.