The Spirit Of The Undertaking: Origins In Macsyma And Dendral 6.871-- Lecture 3MACSYMA: Symbolic Mathematics • Goals of the Project • System Description • Lessons 6.871 - Lecture 3 2Goals of Project To help applied mathematicians in solving problems 4 ∫ x 13 5 x = arcsin( x) − tan(arcsin( x)) + tan (arcsin( )) 22 (1 − x ) 3 6.871 - Lecture 3 3Symbolic Mathematics: AI Approaches • Slagle: SAINT • Moses: SIN • Moses and Martin: MACSYMA • Reduce-II • Mathematica 6.871 - Lecture 3 4SAINT: Symbolic Automatic Integrator 4 ∫ x dx5 2(1 − x )2 Try y = arcsin x, yielding: ∫ sin 4 ydy4cos y 6.871 - Lecture 3 5∫ sin 4 ydy4cos y three possible ways to deal with this: 6.871 - Lecture 3 6sin 4 y dyy∫ 4cos 4z three possible ways to deal with this: 2 24∫ tan4 ydy ∫ cot−4 ydy ∫ 32 (1 + z )(1 − z ) dz (from z = tan(y/z)) 6.871 - Lecture 3 7SAINT • Steps – 26 standard forms (1-step solutions, tables) – 8 Algorithmic transforms (eg. sum of integrals) – 10 Heuristic transforms, of which derivative divides is “the most successful” • Goals evaluated on depth of integrand 2 • Ex., xex is of depth 3 6.871 - Lecture 3 8SAINT • Worked like the average engineer, i.e., lots of search and backtracking • Conceived of in terms of search, worked because of that. The power comes from: – Problem decomposition – Methodical exploration of alternatives – Looking far, wide, and deep – Speedy tree construction, search, backtracking • Success is just a matter of trying enough alternatives 6.871 - Lecture 3 9SAINT Some interesting statistics: Saint’s Average Performance Unused Heuristic Subgoals Subgoals Level Level 32 Author problem 6.4 2.0 3.5 1.0 52 MIT Problems 4.7 0.8 2.9 .8 84 Problems 5.3 1.25 3.0 .9 6.871 - Lecture 3 10The Mindset Shift SAINT will frequently [need to] explore several paths to a solution … because it lacks the powerful machinery that SIN possesses. One of the striking features of these programs is how little knowledge they require in order to obtain a solution. Persson in his recent thesis dealing with “sequence prediction” seems to feel that placing a great deal of context dependent information in a program would be “cheating.” This emphasis seems to be useful when one desires to study certain problem solving mechanisms in as pure a manner as possible. We, on the other hand, intended no such study of specific problem solving mechanisms, but mainly desired a powerful integration program which behaved closely to our conception of expert human integrators. SIN, we hope, signals a return to an examination of complex problem domains. -- Moses, 1963. [emphasis added]Note: almost always needed one (otherwise avg would be lower) almost always needed exactly one (otherwise avg higher) Can’t prove that search was irrelevant, since we don’t know whether earlier use of heuristics would have helped, but we should certainly be suspicious. Also don’t know whether it was the same one heuristic each time. (Even if it was a different one, it’s still interesting that every problem needs one and only one heuristic. Great example of seeing what you want to see, being mechanism driven, 6.871 - Lecture 3 11Sin • Steps 1. Derivative divides2. 11 specific methods– Substantial effort in deciding which to apply – Largely organized around recognizing the form of the problem 3. General purpose methods (e.g., search)• Note the sequence. • “We feel that too few AI programs employ the fact that in many problem domains there exist methods which solve a large number of problems quickly.” 6.871 - Lecture 3 12Macsyma Lessons • Character of the problem changes as knowledge evolves – SAINT • Worked as people appeared to: extensive search and backtracking –SIN • Almost always correct on the first guess: found the sources of power in the domain – RISCH: Algorithmic Integration • Guaranteed to succeed if the expression is integrable – Uses very special representation – Computationally complex and expensive 6.871 - Lecture 3 – Process not understandable to users but provably correct. 13Macsyma Lessons • Keep the system modular and loosely coupled – It is sometimes cheaper to translate one representation to another in order to solve the problem more efficiently – Use of a common language for communication makes this approach tractable (eg, dense and sparse polynomials) • Do not duplicate knowledge – leads to unmanageable system 6.871 - Lecture 3 14Dendral: Structure Elucidation •Given: – Empirical Formula: C9H18O (total MW = 142) – Known Structure Constraints Abun. – Rel. Mass Spectrum 40 50 60 70 80 90 100 110 6.871 - Lecture 3 Mass 15Result O | | C –C –C –C –C –C –C –C –C 6.871 - Lecture 3 16How to Proceed? • Given: – Empirical Formula: C9H18O (total MW = 142) – Known Structure Constraints – Mass Spectrum Rel. Abun. 40 50 60 70 80 90 100 110 • Catalog? Mass 6.871 - Lecture 3 17Generate and Test | —C — H — — O — | For C9 H18 O two possible structures are O O || || C – C –C –C –C –C –C –C –C C –C –C –C –C –C –C –C –C 6.871 - Lecture 3 18Difficulties in Generate & Test 212-422-9130!!6.871 - Lecture 3 19How Can the Program Plan Its Attack? What should the program know? Rules: spectrum features ⇒ molecule class IF There are peaks at M1 and M2 such that M1 + M2 = MW + 28 and M1 is high and M2 is high THEN The structure is one of the ketones IF There is a high peak at 44 and there is a high peak at M1 – 44 THEN The structure is one of the aldehydes 6.871 - Lecture 3 20Knowledge Representation • Efficiency vs. Comprehensibility Additivity Modifiability • Level of representation 6.871 - Lecture 3 21Efficiency and … If high peak at 57 and high peak at 113 Then ketone If high peak at 57 and high peak at 98 Then ether If high peak at 57 Then if high peak at 113 then ketone Else if high peak at 98 then ether 6.871 - Lecture 3 22Level of Representation IF There are peaks at M1 and M2 such that M1 + M2 = MW + 28 and M1 is high and M2 is high THEN The structure is one of the ketones 6.871 - Lecture 3 23Representation Punchline Lesson: Use the Highest level Most Transparent Easily modified representation you can find OO || ⇒ || X –C –C –C –Y X – C – C C – Y OO || ||⇒X –C –C –C –Y X – C C