Dendral

From Wikipedia, the free encyclopedia

 This article may require cleanup to meet Wikipedia's quality standards.
Please improve this article if you can. (June 2007)

Dendral was an influential pioneer project in artificial intelligence (AI) of the 1960s, and the computer software expert system that it produced. Its primary aim was to help organic chemists in identifying unknown organic molecules, by analyzing their mass spectra and using knowledge of chemistry.[1] It was done at Stanford University by Edward Feigenbaum, Bruce Buchanan, Joshua Lederberg, and Carl Djerassi.[2] It began in 1965 and spans approximately half the history of AI research.[3]

The software program Dendral is considered the first expert system because it automated the decision-making process and problem-solving behavior of organic chemists.[4] It consists of two sub-programs, Heuristic Dendral and Meta-Dendral,[5]. It was written in Lisp (programming language), which was considered the language of AI.[6]

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".[7]

Contents

[edit] Heuristic Dendral

Heuristic Dendral is a program that uses mass spectra or other experimental data together with knowledge base of chemistry, to produce a set of possible chemical structures that may be responsible for producing the data.[8] A mass spectrum of a compound is produced by a mass spectrometer, and is used to determine its molecular weight, the sum of the masses of its atomic constituents. For example, the compound water (H2O), has a molecular weight of 18 since hydrogen has a mass of 1.01 and oxygen 16.00, and its mass spectrum has a peak at 18 units. Heuristic Dendral would use this input mass and the knowledge of atomic mass numbers and valence rules, to determine the possible combinations of atomic constituents whose mass would add up to 18.[9] As the weight increases and the molecules become more complex, the number of possible compounds increases drastically. Thus, a program that is able to reduce this number of candidate solutions through the process of hypothesis formation is essential.

[edit] Meta-Dendral

Meta-Dendral is a knowledge acquisition system that receives the set of possible chemical structures and corresponding mass spectra as input, and proposes a set of hypotheses to explain correlation between some of the proposed structures and the mass spectrum.[10] These hypotheses would be fed back to Heuristic Dendral to test their applicability.[11] Thus, "Heuristic Dendral is a performance system and Meta-Dendral is a learning system".[12] The program is based on two important features: the plan-generate-test paradigm and knowledge engineering.[13]

[edit] Plan-generate-test paradigm

The plan-generate-test paradigm is the basic organization of the problem-solving method, and is a common paradigm used by both Heuristic Dendral and Meta-Dendral systems.[14] The generator generates potential solutions for a particular problem, which are then expressed as chemical graphs in Dendral.[15] However, this is feasible only when the number of candidate solutions is minimal. When there are large numbers of possible solutions, Dendral has to find a way to put constraints that rules out large sets of candidate solutions.[16] This is the primary aim of Dendral planner, which is a “hypothesis-formation” program that employs “task-specific knowledge to find constraints for the generator”.[17] Last but not least, the tester analyzes each proposed candidate solution and discards those that fail to fulfill certain criteria.[18] This mechanism of plan-generate-test paradigm is what holds Dendral together.[19]

[edit] Knowledge Engineering

The primary aim of knowledge engineering is to attain a productive interaction between the available knowledge base and problem solving techniques.[20] This is possible through development of a procedure in which large amounts of task-specific information is encoded into heuristic programs.[21] Thus, the first essential component of knowledge engineering is a large “knowledge base.” The knowledge base would include specific knowledge about the mass spectrometry technique, large amount of information that forms the basis of chemistry and graph theory, and any information that might be helpful in finding the solution of a particular chemical structure elucidation problem.[22] Through knowledge engineering Dendral is able to use this “knowledge base” to both determine the set of possible chemical structures that correspond to the input data, and form new “general rules” that helps it reduce the number of candidate solutions. Thus, at the end the user is now provided with a minimal number of possible solutions, which can now be tested by any non-expert user to find the right solution.

[edit] Heuristics

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 and irrelevant solutions.[23] 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 induce the solution to problems via rules of thumb and specific information.

Heuristics programming was a major approach and a giant step forward in artificial intelligence,[24] as it allowed scientists to finally automate certain traits of human intelligence. It became prominent among scientists in the late 1940s through George Polya’s book, How to Solve It: A New Aspect of Mathematical Method.[25] 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."

[edit] History

During mid 20th century, the question "can machines think?" became intriguing and popular among scientists, primarily to add humanistic characteristics to machine behavior. John McCarthy, who was one of the prime researchers of this field, termed this concept of machine intelligence as "artificial intelligence" (AI) during the Dartmouth summer in 1956. AI is usually defined as the capacity of a machine to perform operations that are analogous to human cognitive capabilities.[26] Much research to create AI was done during the 20th century.

Also around mid 20th century, science, especially biology, faced a fast-increasing need to develop a "man-computer symbiosis", to aid scientists in solving problems.[27] For example, the structural analysis of myogoblin, hemoglobin, and other proteins relentlessly needed instrumentation development due to its complexity.

In the early 1960s, Joshua Lederberg started working with computers and quickly became tremendously interested in creating interactive computers to help him in his exobiology research.[28] Specifically, he was interested in designing computing systems that to help him study alien organic compounds.[29] As he was not an expert in either chemistry or computer programming, he collaborated with Stanford chemist Carl Djerassi to help him with chemistry, and Edward Feigenbaum with programming, to automate the process of determining chemical structures from raw mass spectrometry data.[30] Feigenbaum was an expert in programming languages and heuristics, and helped Lederberg design a system that replicated the way Carl Djerassi solved structure elucidation problems.[31] They devised a system called Dendritic Algorithm (Dendral) that was able to generate possible chemical structures corresponding to the mass spectrometry data as an output.[32]

Dendral then was still very inaccurate in assessing spectra of ketones, alcohols, and isomers of chemical compounds.[33] Thus, as seen in figure 1, Djerassi "taught" general rules to Dendral that could help eliminate most of the "chemically implausible" structures, and produce a set of structures that could now be analyzed by a "non-expert" user to determine the right structure.[34] Figure 2 shows how Dendral operates without an expert, after all the general rules were entered into Dendral's knowledge base.[35]

The Dendral team recruited Bruce Buchanan to refine Feigenbaum’s Lisp program.[36] Buchanan had similar ideas and interests as Feigenbaum and Lederberg, but his special interest was hypothesis formation.[37] As Joseph November said in Digitizing Life: The Introduction of Computers to Biology and Medicine, "(Buchanan) wanted the system (Dendral) to make discoveries on its own, not just help humans make them". Buchanan designed "Meta-Dendral", which was a "hypothesis maker".[38] Meta-Dendral and Dendral were fused together to create Heuristic Dendral" in 1966-67.[39] The prime difference was that Heuristic Dendral "would serve as a template for similar systems in other areas" rather than just concentrating in the field of organic chemistry.[40]

[edit] Notes

  1. ^ November, 2006
  2. ^ Lederberg, 1987
  3. ^ Lindsay et al., 1980
  4. ^ November, 2006
  5. ^ Lindsay et al., 1980
  6. ^ November, 2006
  7. ^ Lindsay et al., 1980
  8. ^ Lindsay et al., 1980
  9. ^ November, 2006
  10. ^ Lindsay et al., 1980
  11. ^ November, 2006
  12. ^ Lindsay et al., 1980
  13. ^ Lindsay et al., 1980
  14. ^ Lindsay et al., 1980
  15. ^ Lindsay et al., 1980
  16. ^ Lindsay et al., 1980
  17. ^ Lindsay et al., 1980
  18. ^ Lindsay et al., 1980
  19. ^ Lindsay et al., 1980
  20. ^ Lindsay et al., 1980
  21. ^ Lindsay et al., 1980
  22. ^ Lindsay et al., 1980
  23. ^ November, 2006
  24. ^ Lindsay et al., 1980
  25. ^ November, 2006
  26. ^ Berk, 1985
  27. ^ Lederberg, 1963
  28. ^ November, 2006
  29. ^ November, 2006
  30. ^ November, 2006
  31. ^ November, 2006
  32. ^ November, 2006
  33. ^ November, 2006
  34. ^ November, 2006
  35. ^ November, 2006
  36. ^ November, 2006
  37. ^ November, 2006
  38. ^ November, 2006
  39. ^ November, 2006
  40. ^ November, 2006

[edit] References

  1. Berk, A A. LISP: the Language of Artificial Intelligence. New York: Van Nostrand Reinhold Company, 1985. 1-25.
  2. Lederberg, Joshua. An Instrumentation Crisis in Biology. Stanford University Medical School. Palo Alto, 1963.
  3. Lederberg, Joshua. How Dendral Was Conceived and Born. ACM Symposium on the History of Medical Informatics, 5 November 1987, Rockefeller University. New York: National Library of Medicine, 1987.
  4. Lindsay, Robert K., Bruce G. Buchanan, Edward A. Feigenbaum, and Joshua Lederberg. Applications of Artificial Intelligence for Organic Chemistry: The Dendral Project. McGraw-Hill Book Company, 1980.
  5. November, Joseph A. “Digitizing Life: The Introduction of Computers to Biology and Medicine.” Doctoral dissertation, Princeton University, 2006.