CARPS(ID:3978/)Word-problems languagefor CAlculus Rate Problem Solver Word-maths problem language, after the fashion of STUDENT, but with a rationalised internal structure. Exemplary and underrated structural AI solution done by Eugene Charniak as a Master's Thesis. Charniak was the editor of the multivolume AI Encyclopedia Internal pattern matching done in CONVERT, and Moses SIN used to do the final mathematics (which raises the question of why CONVERT was preferable to the internal patterning system of SIN, given the latter was purpose built to algebra, while the former was designed for maths) Related languages
References: It was found that the use of structures made CARPS more powerful than STUDENT in several respects. 1) CARPS is better able to recognize that two phrases describe the same object. (e.g., CONICAL PILE and PILE OF SAND) 2) Information about an object can be gathered in piecemeal fashion. In calculus word problems it is not uncommon to have two or three sentences providing information for one equation. 3) CARPS to a limited degree is able to use its knowledge to parse its input sentences. For example, in a problem about a filter, ALTITUDE was interpreted as ALTITUDE OF THE FILTER because CARPS knew that since the filter was a cone and cones have altitudes the filter had an altitude. The program has solved 14 calculus problems, most taken (sometimes with slight modifications) from standard calculus texts. Extract: Introduction Introduction The research described in this paper had as its goal the creation of a program which solves freshman calculus word problems. The program, CARPS (CAlculus Rate Problem Solver), is restricted to rate problems. It is described in greater detail in MAC-TR-51 (Thesis). CARPS was primarily motivated by Bobrow's work on STUDENT? a program which solves high school algebra word problems. An understanding of STUDENT is sufficiently important to our work that we shall analyze Bobrow's program in the second section of the paper. CARPS is written in two languages. The bulk of the coding is in LISP. There are, however, large sections which require a great deal of pattern matching, something in which LISP is not particularly powerful. These sections were written in CONVERT, a language especially designed for pattern matching. Since CONVERT is embedded in LISP it was an especially convenient choice because we could easily switch back and forth between the two languages. Both of these languages were available on the Project MAC PDP-6 time sharing system which was used in this research. Also available were J. Moses' algebraic simplification and differentiation routines which are described in [Moses]. The PDP-6 system which has a quarter million words of core storage, gave us a decided advantage over Bobrow, whose program had to fit into a 32K 7094 LISP system, whereas ours wallows in the comparative luxury of 45K of memory. Extract: STUDENT STUDENT As we mentioned earlier Bobrow's program, STUDENT, solves algebra word problems. To really understand how STUDENT works we should go through a problem and see how the program solves it. Extract: Conclusions Conclusions In section 2 we noted several aspects of STUDENT which we felt needed further work. Let us compare CARPS and STUDENT in these areas. 1) By storing information in terms of structures, CARPS is better able to recognize that two phrases describe the same object. 2) Again because of the use of structures CARPS can gather information about an object in piecemeal fashion. STUDENT was essentially required to generate one equation for each sentence in the problem description. In calculus word problems it is not uncommon to have two or three sentences providing information for one equation. 3) CARPS to a limited degree is able to use its knowledge to parse its input sentences. For example we saw how ALTITUDE was interpreted as ALTITUDE OF THE FILTER because CARPS knew that since the filter was a cone and cones have altitudes, the filter had an altitude. 4) Whereas STUDENT has only one soiutlon method (i.e., solution of linear equations), CARPS has several and can decide which is appropriate for a given problem. CARPS machinery for solving its equations (e.g., differentiation, simplification) is also more complex than STUDENT'S. 5) CARPS utilizes a more sophisticated gramtical analysis of the sentences than STUDENT. This is used both in breaking up sentences and in generating the internal structures. Up to now 14 problems have been solved by CARPS. Most were taken from standard texts, sometimes with slight modifications. (Variations in the statements of problems would, of course, increase the number of problems solvable by CARPS.) The other problems solved by CARPS are in Appendix A. Many of the improvements that we claim for CARPS were necessitated by the increased complexity of the problems that we expected it to solve. However many weaknesses of STUDENT are still present in some form in our design. 1) An important weakness in the program is due to its dependence on key words to signify the type of problem (i.e., distance or volume) and the method of solution to be used. What one would like to have in a calculus problem solver is a program which would use the information presented in the problem to figure out relationships among the elements (e.g., similar triangles) and actually propose the method of solution. The answers which could be provided by such a program are currently built into CARPS' data base for several cases, but this scheme severely limits the power of the program. 2) Another weakness of CARPS is its limited knowledge of English syntax. It would not be too difficult for CARPS to learn new syntactic rules by adding these rules to its CONVERT subroutines. Actually what would be more satisfying would be a different method of parsing the sentences into components of structures. Currently the CONVERT rules are attempted one at a time until one matches the sentence. A better approach would be an incremental left to right parse which, when finished with the sentence, would have.translated it into the internal model. 3) A very powerful calculus word problem solver will require a good deal of "cormnon sense'' knowledge. Consider this problem which we gave to CARPS (A LADDER 20.0 FT LONG LEANS AGAINST A HOUSE /. FIND THE RATE AT WHICH THE TOP OF THE LADDER IS MOVING DOWNWARD IF ITS FOOT IS 12.0 FT FROM THE HOUSE AND MOVING AT THE RATE 2.0 ET PER SEC /.) Much to our surprise CARPS was not able to solve it. A closer look at the problem shows why. The last phrase mentions that the ladder is moving at the rate 2 ft per second. CARPS has, as an internal check, the requirement that associated with each velocity must be the direction of the velocity. The point is that the problem never gave this direction. Most people, however, would assume that it was moving horizontally away from the nouse. T'ne reason of course, is that a familiarity with ladders or the law of gravity tells us that this is the most likely way for it to be moving. This is not an isolated incident. Consider the problem (A BARGE WHOSE DECK IS 10 FT BELOW THE LEVEL OF A DOCK IS BEING DRAWN IN BY MEANS OF A CABLE ATTACHED TO THE DECK AND PASSING THROUGH A RING ON THE DOCK. WHEN THE BARGE IS 24 FT FROM AND APPROACHING THE DOCK AT 3/4 FT / SEC, HOW FAST IS THE CABLE BEING PULLED IN ?) The ship is moving horizontally towards the dock. The problem does not mention this. Nor is the need for a body of "real world" information unique to calculus problems. Consider an example taken from a children's story. "Mike's costume had big ruffles. He refused to wear it." The question is "Why?". A program which will answer correctly must know that boys usually will not wear girl's clothes, and anything with ruffles on it must be for girls. It is our belief that a program which is to understand second grade stories must have at its disposal a body of facts comparable to that of an average seven year old. More generally, computer understanding of any body of literature will require a data base similar to that of a human reader. The major problems facing computer understanding of natural language are, in our opinion, collecting, storing, and utilizing such large bodies of information. in Donald E. Walker, Lewis M. Norton (Eds.): Proceedings of the 1st International Joint Conference on Artificial Intelligence IJCAI-69, Washington, DC, May 1969. William Kaufmann, 1969 view details |