JL: 7 7 j _ ‘Y . IS Led CAhOL I (2, [io bois -e . So, with that background, if you could teli me what vou see as the major ideas and the major contributions which have come forth from the DENDRAL project. Well, 1'm an ignoramous about Computer Science as a discipline. ] spend a lot of time trying to learn things about it and I do as ij go along, ~ but in a certain sense I'm not well-equipped to answer that question because | don't know the myths, the intellectual structure of the field and so on well enough to know in what way it wast very Pins : sere ee CPD Me tad et eye ae obvi OUus,s that, the DENDRAL Project | asx. What was going on thef’ which made ... and soon. I've heard comments about that From time, a) time teas A, Se Ao Daebead y Tie ERO Ak. BORGES Es, woe : mo yp PY “ from Ed ana Bruce, { f And, in fact, ‘the main thing that | would say that at BW I've learned in this direction is that a job like this can be done. - vat it is possible to engineer a system of this kind. i find it «ard to lay down what are the broad theoretical accomplishments; 1 have:'~ J been that self-conscious about the theoretical structure of what iv c¢ that we were doing. And that's a point about which | certainly eu be acutely self-critical — At! s not quite the way «nuxkkch | would approacn by (Then Contra quel things #& my own -samete discipline, | [ am a little skeptical about tne extent to which any enormous theoretical structure has developed as a result of this effort. | think we've done a very good job of engineering and to try to figure out wherein what we did from point to point differed Tr IM2 greatly fromjcommon sense and experimental probing about a few thing» that work and a few things that don't work, and so on, and packagince -t in/fatelligent and orderly fashion, I'ma little at a loss to describe, partly /bessnges 1 don't have wax the theoretical framework which maxes \ Poise ble, rev her Le such a description/ That may be af/more modest view of what we've been “ up to than my friends would be wil! ,ing to admit to,’ Ati s- not something Lyi nd Gee bal SATE SC Bia ree i'm insisting on, i'm just telling yous | “did outline a couple of RL: JL: ae things in a note that came out a few years ago, /status report. Let me see if | can find that particular one because isolating things out of the DENDRAL reports. ¢: i don't think I|'ve seen that particular one. You probably have. It's under some other Azo hene. ON MEWKR, es Yreka feds f | couldn't find it in that pile but I'm sure I'll find it here. / ‘this is the one. So it's report No. 104 and it's not exactly the same as ase” the way it appeared in Machine Intelligence V so that’ A Well, let me ponder on that a little bit. | guess | started out with a lot of prejudices about the design of the system without having had necessarily very much of a theoretical framework about what other people were doing, And so | may indeed have had a fairly strong explicit theory in mind without knowing that 1 did speak in-prose for a long time. The notion of a ENOL EE senerator is one that | guess !'ve not really seen expressed explicitly anywhere else, but | sort of live with it as a given from which one then gaes:into heuristic pruning exercises. And that's In a nutshell what DENDRAL does, fad the issues of how you go about doing it and tuning it to the reality of the situation™=so maybe that deserves some emphasis? --4n trying to discriminate problems for their amenability to this approach, that camretkeat- generator looms Qare very, very large,} Particularly with the criteria for equivalence#and ? fr ? | have frequently told myself I'd be willing to go into any other of ote’ “eye scientific field, ve | like tojbreak out of chemistry, if 1 could satisfy the criterion of having a notation in which hypotheses could be expressed, and a machine that could test statements for semantic New ile can equivalence to one another. Ajo that for structures of organic molecules and that is just about all as far as real world oriented science is concerned. A lot of mathematics, obviously, Sne cart make transformations RL: JL: RL: JL: , Bogie ees: ERP es ia ‘ . 2 ma eae’. 4 of expressions ..,) have that property... be st woald it be fair to Say that if you found a field in which there were of thot & vx yf no structural generator/that DENDRAL has no lessons in that area? No, | think that there has been a good deal of shrewdness in solving ie or “e many/other kinds of problems down the way that don't require the be generator, ens so that's too strong a statement, / | think the central concept of DENDRAL is built anya that approach to the selection of Lupe Fa fen ol loci Che 1 hypotheses/and there really is an exhaustive genes a tor that can construct Ley fo Fee: valid statinentss even before you look at the data/you have some way of parsing through all acceptable sentences and being sure that you had all of them, and so on. Do you have any advice for somebody as to how to go about discovering fre or inventing such a generator ‘in a different area? No, not especially. Well, I don't know whether | do or not. Again, | have an image of what to do about it in chemistry, and one is able to map hypotheses of analytical organic chemistry onto some fairly elementary algebraic concepts {°graphs, and one knows the properties of automorphism, and from that you can generate the generatorphe fact it took a lot of fairly particular hacking away at It to discover efficient ways of building the generator.—¥t's one thing to say, let us produce all possible non-equivalent representations, and another to do it in a way that does not involve an enormous amount of back comparisons, of weeding out of redundancy / sxplicit search for equivalences, and that sort of thing. These go under the heading roughly of labelling problems, and when we come to the cyclic graphs the situation is not quite so kn feed straightforward and/it took quite a while to get a good way of handling wc c wy thatweo si just came out fairly recently. So I'm not sure that one is in ler ed a position to generalize from that about how you go about doing it in the baa erother fielcz* "fe ought to re-examine that question? Anat's a very interesting questions i've never looked at it quite that way. All 1 can say is that the first step is to look for trem procs ile that would _ x9 do that, is to try to find some way £3 of organizing the generator that is prospectively efficient, that has in it built-in constraints, so that you can guarantee and demonstrate in some reasonably rigorous fashion that it has the properties that you have been describing. f . For trees, that was quite straightforward, for rings, it was somewhat but, , the one trar Ao in.) more __ comp lexs the iia Auestion/t think is a little bit of an Joye , At theek tAad ls JARO LD ECCS . a “tevestote is knowing fuhat you want to do. So | think a description of what you mean by a prospectively eificient generator could be a fn 2a ends of tals fos very important element/ Now there's some fields where that simply doesn't apply. If you're talking about chess, your move generatory en» if at wae there's such a total] lack of symmetry in the game” gams, and thefe “6 / positions at each move are relevant, you're not only interested in final statess, you have to match your situations move by move; you al can't go through a transition that involves a check-mate and have which is something the other side of it, you See, tots a little different from some of the generations that we go into. So there the total lack of ahi symmetry in effect gives you no, you might say/no difficulty, or no fart thras '$ WAL opportunity,/no weeding;algorithm that | can think of that would ? \ 2 ; A Qeimnjeletely Got reduce the combinatorial space of valid moves. But maybe that's not, J . xv to-.° a first approximation that's true; however, you can't move your king across a file that's controlled by a queen and things of that sort, happens when teondsey is broken, | ans things of that sort. So there we have a series of mechanisms that are sufficiently close to what we have in organic chemistry without being quite identical to them. | think we do have a chance to try to formalize that a bit. And the idel sort of problems/we run into there are mechanizing the kind of imagination that suggests new sorts of experiments to do, ‘And we b ? Bet would then need a formal language to describe those experinentss |4t seems graspable and | think it's something we should be able to get on® “> with much less effort than the first round of DENDRAL. The other areas that one might contemplate | think do suffer from the formal statement problem and | think there are probably quite a number of fields where that can be done, but KxRRKAKXAAXSULKERXAKRXLABXKBRMAK ay vhte nto a “« kKnOW as much about as a) it's a formidable effort. It's not oné . l'd like to. Pat Suppes might have something to say about that. We've had a few conversations on this point. There are a few formal Woodyer tried to do somethinge~ systems in psychology, sociology,/embrfology, a few years ago. In peg hick fact, Woodyer also tried a piece on psychology in which he quite literally tries to express a number of concepts, building them up i : é Dw fide rh png % ian it e 1! from propositional calculus yzanatural language, not really in good position to judge those; | gather they haven't made very much impact on the field that they were ins xcept as first triels of { trying to beeblomto do it. | think that's where we're at right now} TF dint al Hund There's been d° very great effort to attempt to formalize them. People outside of mathematical logic | think sometimes try to develop formal Qa’ systemsy / People inside the field have despaired and gone to less and less formal representations of what they're doing. But | think without thin bhe motivation of purting/into computer programs you won't have the i Cp D hte. sense of need to do thats. work that's necessary to do that kind of translation. Some people think that the way around that is to wait h . . for the natural language/Pacgst > far enough along that you can just give them our own natural language text and programs extract them... | think om re ST it will a a very long wait. / Well, that's one piece of it. There are a few perceptions, strategy that are mentioned in that article, but they apes really have much more to do with ‘engineering tidiness f avolding some fairly obvious traps that are obvious after you've been in them, than any great theoretical doctrine. And maintaining the logical consistency of your system is really much more difficult than you would ever believe. Qe As you keep maintaining it and correcting/little piece of it you're ir just constantly knocking other things down that you weret't aware of at the time you were laying it all outs &nd so your notion of putting . . an’. , PAoOvEes your basic system of rules and axiomsy legitimate utes and so forth, in one place and making sure that the program generates all the code that it needs throughout the system, from one consistent source, | pat, t 3 4 abs think is a lesson you learn’ the hard way, At still hasn't been done tas c completely perfectly and systematically, but wherever possible it is, Now 'S tAa- and we've had a much happier time of it since then. /A-great theoretical “ contribution or just a rule of experience But if the first time you x ever trped to do something like this, if you're not aware of that, and it hasn't been knocked into you,you'can flounder around for a very Od long time.f It ends up being very similar though to the general wa caren AEN Aan jams ne 2 A programming problem, which | don't think fs all that different from che fircnd artificial intelligence. } tery comp !ex algorithms, and how to keep them runningg, ‘}ow to maintain them and keep them running well 43 part and parcel of the problem of Al. | don't really see a very sharp houndary between Al and other complicated algorithms. The other kinds of things that can be done in looking for shortcuts is not only rely on the real world, but you san also, once you've got a generator, ¢het it can Quel Youre generate its own problem situation3,|then start developing Yee heuristics wore ~~ for shortcutting into themf letting the generator use its sets of rules, for example, well, it would be a little bit analogous to saying you don't have to wait for all the games of the grand mastersgif you're doing this In a chess programs et the system play some of [ts own games, dnd play the problems that it itself generates in looking for the strategiess {ln the case of chess you may have enough material to work witha ‘that isn't a problem. In our situation we did run out of, wwe we would have difficulties putting in thousands of examples of tx, solutiong to known problems « é@nd while we put in as many as possible, RL: JL: a tpg ft leg bette in sharpening the tools for looking for the shortcuts from/data to the pued. nell hypotheses, since everything depends on the consistency of your/ generator anyhow, you might as well let it spin those out and invent data that you oe, MM Ges Tin pore payec is « then use in £2 in yerse fashion in looking for short cuts/ That's something we have not really implemented to any great degree. It's be. as been used a few times and it's successful, Seen on the ehelr for a while. aad Dare Nea Some of the other strategies that we've developed are also, maybe there's a lesson to be derived/' 408 FbGe fage ther, haven't really beeng thoroughly worked out be! Ss only a little while that we've had the luxury of this ee stable computing environment, and the resources to really do the things wots oe “hy A¢ Ke e wefwant to doy We "re too buby/to do a Vist of priorities of things wecunte’ to clean up. But the role of the dictionary is a very interesting question Oe and strategies for using it | think Foe sort of the next level of em A.l. “thal o and | think there's some generality on icy You know what issue |'m referring tie ud - lac? ad to? And we never really did address what the heuristics ought to be, Flow Jd you go about making choices as to when to consult the dictionary and when not. I thing that's a rather interesting horizon to try to get into. There were a number of occasions that various people thought that had radieally ancl ldipn different approaches to the problem, they ended up to be quite mapable vie AST hy re onto the original notions of graph generation yand/ver ious kinds of /definttion£ye of the canons of order. What were some of those? FL PAfse that was Well, this (planner) idea. That was used. .. there was a specific strategy/set up for the amines, which doesn't look at all like the DENDRAL generator. But* then if you look twice at it, you discover that it really is, only you've redefined the center of the graph, you've got some superatoms layed on, and that you could describe the entire procedure in terms of canonical generator, RL: JL: 10 but just with those kinds of substitutions of arguments. We ended up discovering that DENDRAL really was a very general machine. And | re ee a: bbe find it hard to say how it could be otherwise§ wacom we really are giving fundamental graphic description of the molecules and the oF Poe vat A strategi” suggested really weren't totally A: they again involved graphic generations. 1 wasn't surprised when the tables showed that they were homolog aus in fact prmotygoes to one another. But it does say something that you tha f really do want to write your generators in such a way/they can be internally rearranged very readily, that you don't have them locked into difficult code, fhat the sequence of priority of different steps can be readily altered so that you end up with a table driven approach to that, and that enables you to experiment with alternative strategies in terms of what) the most efficient ways of setting up your heuristics for different Kinds of problems. That's something |'ve advocated Wat CA belts mechanizing anci/ have not done to any appreciable degree. But some of . . . . A Sint as these discoveries of new strategies involvewsimetiing} in the long run ekxsemaxkkagxuak were not much more than inverting the order of precedence of some of. the operations in the generator, which is entirely appropriate to different situations and in ich one could scan either icicles ie Leen, thane INOUE, effi Chaat the data or ohe problem space and dos igaen strategy that could be used there. Ok, that gives me a pretty good idea of what | wanted. Do you have anything else to add? Not right off hand. !'m sure I would after some further iteration.