1The Spirit Of The Undertaking: Origins In Macsyma And Dendral6.871-- Lecture 36.871 - Lecture 3 2MACSYMA: Symbolic Mathematics Goals of the Project System Description Lessons6.871 - Lecture 3 4To help applied mathematicians in solving problems()=−∫25241 xxGoals of Project6.871 - Lecture 3 5Symbolic Mathematics: AI Approaches Slagle: SAINT Moses: SIN Moses and Martin: MACSYMA Reduce-II Mathematica, Matlab6.871 - Lecture 3 6Try y = arcsin x, yielding:()dxxx∫−25241dyyy∫44cossinSAINT: Symbolic Automatic Integrator6.871 - Lecture 3 13ydy4tan∫ydy4cot−∫dyyy∫44cossin()()32114224zzzdz+−∫(from z = tan(y/z))three possible ways to deal with this:dzzz241 +∫dzzz⎟⎠⎞⎜⎝⎛+++−∫221112313 zdzzz+∫++−()−+∫dzzz421try w = arctan zarcsin( ) tan(arcsin( )) tan (arcsin( ))xx x−+13326.871 - Lecture 3 14SAINT 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» Ex., is of depth 32xxe6.871 - Lecture 3 15SAINT 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 alternatives6.871 - Lecture 3 16Some interesting statistics:Saint’s Average PerformanceUnused HeuristicSubgoals Subgoals Level Level32 Author problem 6.4 2.0 3.5 1.052 MIT Problems 4.7 0.8 2.9 .884 Problems 5.3 1.25 3.0 .9SAINT6.871 - Lecture 3 18SAINT 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 whichbehaved 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]The Mindset Shift6.871 - Lecture 3 19Sin Steps1. Derivative divides2. 11 specific methods– Substantial effort in deciding which to apply– Largely organized around recognizing the form of the problem3. 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 20Macsyma Organization 5000 operations User-driven Independent operations36.871 - Lecture 3 21Macsyma 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 system6.871 - Lecture 3 22Symbolic Math 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 Process not understandable to users but provably correct.6.871 - Lecture 3 23Dendral: Structure Elucidation Given:– Empirical Formula: C9H18O (total MW = 142)– Known Structure Constraints– Mass Spectrum6.871 - Lecture 3 24ResultO||C –C –C –C –C –C –C –C –C6.871 - Lecture 3 25How to Proceed? Given:– Empirical Formula: C9H18O (total MW = 142)– Known Structure Constraints– Mass Spectrum Catalog?6.871 - Lecture 3 26|—C — H — —O —|For C9H18O two possible structures areOO|| ||C –C –C –C –C –C –C –C –C C –C –C –C –C –C –C –C –CGenerate and Test46.871 - Lecture 3 27212 - 422 - 9130 !!Difficulties in Generate & Test6.871 - Lecture 3 28CompleteIrredundantInformedThe overall paradigm should be:PLANGENERATETESTThe need in structure elucidation:Empirical formula C20H43NPossible Structures: 14, 715, 813The Generator Should Be:6.871 - Lecture 3 29What should the program know?Rules: spectrum features ⇒ molecule classIF There are peaks at M1 and M2 such thatM1 + M2 = MW + 28 and M1 is high and M2 is highTHEN The structure is one of the ketonesIF There is a high peak at 44 andthere is a high peak at M1 – 44THEN The structure is one of the aldehydesHow Can the Program Plan Its Attack?6.871 - Lecture 3 30Knowledge Representation Efficiency vs. Comprehensibilityvs. Additivityvs. Modifiability Level of representation6.871 - Lecture 3 32Efficiency and …If high peak at 57 and high peak at 113 Then ketoneIf high peak at 57 and high peak at 98Then ether6.871 - Lecture 3 33IFThere are peaks at M1 and M2 such thatM1 + M2 = MW + 28 and M1 is high and M2 is highTHENThe structure is one of the ketonesLevel of Representation56.871 - Lecture 3 35O||X –C –C –C –YO||X – C – C C – Y⇒⇒O||X – C C – C – YLevel of RepresentationIF There are peaks at M1 and M2 such thatM1 + M2 = MW + 28 and M1 is high and M2 is highTHEN The structure is one of the ketones6.871 - Lecture 3 36Representation PunchlineLesson:Use theHighest levelMost TransparentEasily modifiedrepresentation you can findO||X –C –C –C –YO||X –C –C –C –YO||X –C –C C –YO||X – C C – C – Y⇒⇒6.871 - Lecture 3 38In the Knowledge Lies the PowerEmpirical formula: C20H43NInformation Sources Possible StructuresTopology 42,867,912ChemistryMass SpectrumChemist’s InformationNMR6.871 - Lecture 3