An analysis on the dendral expert system

Abstract - In this paper, we do an analysis on the influential pioneer project in the application area of Heuristic programming for experimental analysis in empirical science using IUPAC conventions. The primary aim of the DENDRAL project was to help organic chemists in identifying unknown organic molecules from compounds extracted from known origin that had medicinal or utility value. The process was done by analysing their mass spectra and then undergoing comparative study using knowledge of chemistry. It was done at Stanford University by Edward Feigenbaum, Bruce Buchanan, Joshua Lederberg, and Carl Djerassi. It began in 1965 and spans approximately half the history of AI research. The DENDRAL Project was one of the first large-scale programs to embody the strategy of using detailed, task-specific knowledge about a problem domain as a source of heuristics, and to seek generality through automating the acquisition of such knowledge¹.

Keywords- DENDRAL Expert System, Heuristic DENDRAL, Meta-DENDRAL, plan-generate-test paradigm,

I. INTRODUCTION

The DENDRAL Expert system is considered the pioneer in expert systems because it automated the decision-making process and problem-solving behaviour of organic chemists with the help of Heuristics. There were two sub-programs in the software architecture of DENDRAL, Heuristic DENDRAL and Meta- DENDRAL. It was coded in Lisp (programming language), which was considered the language of AI during that time. Many systems were derived from DENDRAL, including MYCIN, MOLGEN, MACSYMA, PROSPECTOR, XCON, and STEAMER. The name DENDRAL is a portmanteau of the term "Dendritic Algorithm".

The DENDRAL programs were knowledge-driven, in the sense of today’s expert systems, with the knowledge principle--that knowledge is power-first articulated in the context of DENDRAL². It was the first of the Expert Systems to use the concept of a separate knowledge base that could be rewritten or redefined for new purposes while having retained all the same source for interpreting and using that information. DENDRAL was the first rule-based system made for a “real-world” problem. It was intended for chemist, other than its developers, for undergoing their research, as this was developed during the cold war it had a lot of other significance too. This project was handled by more than one discipline and was in use for a long time. It was one of the larger more sustained AI projects carried out, making it more prominent other than its successes. Perhaps most significant is that this research was an extensive empirical exploration of heuristic programming techniques as such it was a validation of the strengths and weaknesses of these techniques and an instantiation of a philosophical concept of automatic discovery procedures whose status had long been in dispute². If we go on to define human knowledge as the information that a human being possesses, then Lindsay and Lederberg agree that expert systems, and in particular, DENDRAL, meet that requirement³. DENDRAL was built to add up a database of the known rules (valence requirements) and exceptions in organic chemistry that determine the structures of molecules - the data and knowledge a human chemist might possess and use. Therefore, by definition, it possesses and utilizes this human knowledge. I want to go a step further and agree with Lindsay that expert systems, specifically DENDRAL’s Meta-DENDRAL, possess the learning aspect of human behaviour. Others may argue that DENDRAL and other expert systems cannot possibly learn as humans do, and do not even represent human knowledge. Lederberg even himself points out in retrospect that DENDRAL had flawed rules and knowledge, and even knowingly left out specific “rules” or data³.

If we consider human brain having conscious and un conscious mind, then we consider the short term and long term memories also and we can define human brain as voluntary and involuntary too, the reason to take these three set of inter related names is that if we want to link an expert system and an error free human; then an unconscious mind possessing, involuntarily working human brain in a hypnotic state is similar to an expert system, i.e. in that state the humans won’t forget to take any link of memory that relates to the question which is asked similar to the Agenda in the inference engine of an expert system. It goes through or fires all the rules that are related and in the memory which is the long term memory that is activated at this point (if it was short term then he will be remembering his state of psychotic sleep) and collects all the five types of memory i.e. sight, sound, touch, smell, taste if exist. If it’s a conscious human then there is a gap between the brain memory and the voluntary thinking interface, at that stage humans won’t be fully certain about a decision but then comes the most important part, the ability to take risk and the power to handle a new situation. So even the

Term Paper of Course code: CSE 508, KNOWLEDGE BASED EXPERT SYSTEMS. Submitted to Asst Prof. Gour Sundar Mitra Thakur knowledge engineers of DENDRAL expert system were trying to harvest this state to have a leap to replicate error free expert human thinking.

illustration not visible in this excerpt

Fig 1: General working of an expert system which can also be seen in DENDRAL.

II. DENDRAL PROJECT ORGANISATION

There have been few successful and long-term interdisciplinary projects in the history of science. We believe DENDRAL should be counted among them. The project worked cohesively for a decade and it involved productive interaction of researchers from the disciplines of chemistry, computer science, genetics, philosophy, physics, mathematics, electrical engineering, management science, and psychology. It is difficult to give a recipe for this success but we believe we can list some important ingredients. The task was conceived in such a way as to appeal to many interests, it could have been described as a pure mass spectrometry problem or a content free hypothesis formation problem but it was not. This task is not prohibitively difficult it can be understood (with a moderate effort) by anyone with a modest technical background. One scientist with knowledge of both chemistry and computer science was willing to coordinate and arbitrate the often conflicting efforts of the group and was able to do it because others felt sufficient respect for his ideas and vision to sacrifice some of the traditional autonomy and rugged individualism of scientists. The project leaders were skilled managers who had learned to delegate responsibility through management of other academic organizations.

They also shared a willingness to take risks with unproven personnel. Not the least important but a natural selection occurred resulting in a staff of specialists each of whom was truly willing to go more than half way to understand the other’s discipline, paradigms and arcane jargon. There was also a genuine desire among the computer science personnel to create programs of value to chemists on the way to solving the big problem. Although many of these utilities did not use AI methods they provided tangible benefits to the chemist collaborators whose assistance was essential. This piece of common sense (“quid pro quo”) is missing in projects that skim the cream in a new problem area and that have left colleagues disgruntled about AI. We may offer no magic advice here but the lessons are important and mistakes are costly. Interdisciplinary work is antithetical to most scientists no matter how wistfully they long for it. It is expensive folly to establish a project or institute and fill it with scientists from a variety of disciplines selected only on the basis of scientific credentials. Without leadership specific common goals, mutual empathy, human consideration and a great deal of effort the result will be a collection of scientists none of whom has a colleague. Finally, it should be noted that it is not easy to get funds for a large, interdisciplinary project. It is important to find a sponsoring agency that is willing to invest in long-term research, because continuity is critical, the original proposal memo for the DENDRAL expert system is attached in Appendix 1.

Term Paper of Course code: CSE 508, KNOWLEDGE BASED EXPERT SYSTEMS. Submitted to Asst Prof. Gour Sundar Mitra Thakur

III. METHODS

DENDRAL expert system was one of the first systems with which the phrase expert system has been associated. The DENDRAL project commenced in 1965 at Stanford University. The system was developed by J. Lederberg, an organic chemist (and Nobel Prize winner in chemistry), in conjunction with E.A. Feigenbaum and B.G. Buchanan, both well-known research scientists in artificial intelligence at that time. The DENDRAL system was developed to assist in the field of organic chemistry to determine the structural formula of a chemical compound that has been isolated from a given sample. In determining a structural formula, information concerning the chemical formula, such as C4H9OH for butanol, and the source the compound has been taken from, is used as well as information that has been obtained by subjecting the compound to physical, chemical and spectrometric tests.

The original DENDRAL algorithm was developed by J. Lederberg for generating all possible isomers of a chemical compound. DENDRAL contains a subsystem, the Structure Generator, which implements the DENDRAL algorithm, but in addition incorporates various heuristic constraints on possible structures, thus reducing the number of alternatives to be considered by the remainder of the system. Heuristic DENDRAL helps in interpreting the patterns in a spectrogram. It contains a considerable amount of chemical knowledge especially organic chemistry. To this end, another subsystem of Heuristic DENDRAL, called the Predictor, suggests expected mass spectrograms for each molecular structure generated by the Structure Generator. Each expected mass spectrogram is then tested against the mass spectrogram observed using some measure of similarity for comparison. This has been implemented in the last part of the system, the Evaluation Function. Usually, more than one molecular structure matches the pattern found in the spectrogram. Therefore, the system usually produces more than one answer, ordered by the amount of evidence favouring them⁴.

A heuristic is a rule of thumb, an algorithm that does not guarantee a solution⁶, but reduces the number of possible solutions by discarding unlikely, less chance and irrelevant solutions. The use of heuristics to solve problems is called heuristics programming and was used in DENDRAL to allow it to replicate in machines the process through which human experts infers the solution to problems using rules of thumb and specific, proven information. Heuristics programming was a major approach and a giant step forward in artificial intelligence, as it allowed scientists to finally automate certain traits of human intelligence. It became prominent among scientists in the late 1940s through George Polly’s book, How to Solve It: A New Aspect of Mathematical Method. As Herbert Simon said in The Sciences of the Artificial, if you take a heuristic conclusion as certain, you may be fooled and disappointed; but if you neglect heuristic conclusions altogether you will make no progress at all.

illustration not visible in this excerpt

Fig 2: The user interface symbolic output mapping of cyclic chemical structure rendered in DENDRAL.

[...]