Dendral Expert System Case Study Ppt Template

Presentation on theme: "Dendral: A Case Study Lecture 25."— Presentation transcript:

1 Dendral: A Case StudyLecture 25

2 DENDRAL: Introduction
DENDRAL (for DENDritic ALgorithm) was an early intelligent system for science informaticsDEDNRAL’s primary task was to discover a chemical’s structure from its mass spectrum.A mass spectrometer uses electrons to break a chemical into fragments.Given a histogram of fragment abundance, DENDRAL identifies the original structure.Although never widely used, DENDRAL did lead to results publishable in the chemistry literature.

3 Using DendralUsers interacted with Dendral through a teletype, which imposed limitations on the system’s interface.The interface was limited and required users to learn a formal language.The ability to view chemical structure on a teletype was unique.Users entered problem specific information.DENDRAL returned an array of potential structures.from Lindsey et al. (1993) AI Journal

4 Knowledge in DENDRALAt its outset, DENDRAL was unique due to its incorporation of domain specific knowledge.Researchers involved with DENDRAL espoused the knowledge principle:A system exhibits a high level of intelligence primarily because of the knowledge that it can bring to bear.Following this, the system was given knowledge about chemical structures and mass spectrometry.This knowledge constrained the structures that DENDRAL would consider, eliminating many that were implausible.Domain knowledge also informed the evaluation of the plausible structures that remained.

5 Plan – Generate – TestThe generate-and-test approach is a common strategy in discovery systems.A system following this strategy has a generator that suggests solutions and a tester that evaluates them.DENDRAL extended this approach by automatically adapting the generator to the particular problem at hand.The plan-generate-test strategy includes an initial problem assessment that produces situational constraints.These constraints limit the generator and substantially reduce the number of structures considered.This approach effectively creates a situation-specific solution generator for each problem it encounters.

6 CONGENCONGEN, for CONstrained GENeration, produced the candidate chemical structures.To generate these structures, CONGEN requiresa chemical formula, such as C12H14O;a set of superatoms that define partial molecular structures, such as the methyl group CH3; andconstraints on how the atoms and superatoms may be assembled into a structure.CONGEN produced an exhaustive and nonredundant set of chemical structures.DENDRAL’s developers saw this as a necessary condition for chemists to trust the system’s output.Of course, humans are not so systematic.

7 PLANNERPLANNER automated the specification of constraints for working with a particular mass spectrum.To produce the constraints, PLANNER requiresa structure common to a class of chemical compounds;descriptions of potential fragmentations, including the bonds they break and any side effects they have; anda mass spectrum.PLANNER’s constraints stated the atoms contained in the substructures attached to the class-level structure.Plausible substructures were placed on a GOODLIST and implausible ones were placed on a BADLIST to be avoided.

8 PREDICTORPREDICTOR tested CONGEN’s structures by comparing simulated fragmentations to the mass spectrum.To evaluate a candidate structure, PREDICTOR requiresa structure in the form used by CONGEN;a set of production rules that simulate the fragmentation processes that occur within a mass spectrometer; anda mass spectrum.When multiple structures can explain the data, they are ranked according to a user-provided scoring measure.

9 Why Wasn’t DENDRAL Commonly Used?
Chemists were unaware of the program.Chemists didn’t want to invest the time to learn it.Exhaustive generation was not seen as essential to the structure elucidation problem.The niche that DENDRAL fills wasn’t considered important enough to warrant use of the system.DENDRAL was not cost-effective for single individuals.Attitudes such as "Machines can't think; that’s my job.”DENDRAL’s pieces were easier to market than the whole system.Edited and abridged conjectures from the Lindsey et al article in AI Journal.

10 Science Informatics Lessons from DENDRAL
An interactive user interface is not merely a nicety but is essential.Providing assistance to problem solvers is a more realistic goal than doing their jobs for them.Computer assistants should maintain records just as a human assistant would.A uniform knowledge representation eases user interaction and program development.Users must understand the scope of problems a system can solve and the limitations in its abilities.Explicit assumptions and initial conditions of a problem, help users understand the results.Edited and abridged lessons from the Lindsey et al article in AI Journal.

11 DENDRAL: SummaryDENDRAL used heuristic search to address a challenging task of scientific discovery.The system relied heavily on knowledge, and its underlying formalism affected its development and usability.As an informatics tool, DENDRAL resembles BLAST in thatdevelopers made it publicly available to researchers;it addressed a specific need of chemists.DENDRAL’s case differs from BLAST in thatthe speed and accessibility of the internet was limited;it was difficult to port to other computing environments;it was not integrated with other useful tools.




Introduction

PROSPECTOR: Operational details

PROSPECTOR: Knowledge Base

PROSPECTOR's Inference Mechanism

PROSPECTOR: Conclusions

PROBABLISTIC REASONING: MYCIN, XCON and PROSPECTOR










PROSPECTOR: An Introduction

Problem domain:
                                                   • Evaluation of the mineral potential of a geological site or region

                                                   • Multi-disciplinary decision making: PROSPECTOR deals with
                                                      geologic setting, structural controls, and kind of rocks, minerals,
                                                      and alteration products present or suspected

Target Users:
                                                     Exploration geologist who is in the early part of investigating an
                                                     exploration site or "prospect"

Originators
                                                     R. Duda, P. E.Hart, N.J. Nilsson, R. Reboh, J. Slocum, and G. Sutherland
                                                     and John Gasching (1974-1983)
                                                     Artificial Intelligence Center,
                                                     Stanford Research Institute (SRI) International
                                                     Menlo Park,
                                                     California, USA

References:
                                                     Waterman A., Donald., (1986), "A Guide to Expert Systems". Reading, Mass (USA).
                                                     Addison-Wesley Publishing Company. pp 49-60
                                                     Barr, Aaron & Feigenbaum, Edward., (1982)"The Handbook of Artificial Intelligence".
                                                     Reading, Mass (USA). Addison-Wesley Publishing Company. pp 155-162


PROSPECTOR: An Introduction
 

• consultation system to assist geologists working in mineral exploration

• developed by Hart and Duda of SRI International

• attempts to represent the knowledge and reasoning processes of experts in the geological domain

• intended user is an exploration geologist in the early stages of investigating a possible drilling site
 
 


PROSPECTOR: Operational details
 
 

Characterisitics of a particular 'prospect'(exploration site)
volunteered by expert
(e.g.geologic setting, structural controls, and kinds of rocks minerals, and
alteration products present or suspected)

PROSPECTOR compares observations with stored models of
ore deposits

PROSPECTOR notes similarities, differences and missing
information

(POSPECTOR asks for additional information if neccessary)

PROSPECTOR assesses the mineral potential of the prospect

PROSPECTOR

• system has been kept domain independent

• it matches data from a site against models describing regional and local characteristics favourable for specific ore deposits

• the input data are assumed to be incomplete and uncertain



PROSPECTOR At Work
 
 


PROSPECTOR: Operational details
 

PROSPECTOR performs a consultation to determine such things as


PROSPECTOR: Knowledge Base
 

The Knowledge Base (K.B.) is divided into two parts

PROSPECTOR uses PRODUCTION RULES and
SEMANTIC NETWORKS to organize the domain
knowledge and backward chaining inference strategy



PROSPECTORS' Knowledge Base:

The Representation Scheme
The knowledge representation scheme used by the developer's of PROSPECTOR is called 'the inference network': a network of connections between evidence and hypotheses or a network of nodes (assertions)and arcs (links)
 
 


PROSPECTOR system contains rules linking observed evidence, 'E'. of the particular (geological) findings with hypotheses, 'H', implied by the evidence: LS and LN are prestored (ranging from +5 to -5) and do not change during the execution of the program. Also, each piece of evidence (E1,E2, E3..) and hypotheses (H1...) has a probability assigned to it (P1,P2..) whichmay change during execution according to Baye's Theorem.
 
 



PROSPECTOR: Knowledge Base:

Static Data

In addition to the PROSPECTOR rule-base, the system also has a large taxonomic network: A 'hierarchical' data-base containing super- and sub-ordinate relationships between the objects of the domain.
 



 
 


PROSPECTOR Knowledge Base

Semantic networks: Quillian (1966) introduced the idea of semantic networks based on the so-called "associative memory model": the notion that human memory is organized on the basis of association, that humans represent the real-world through a series of associations. More precisely a semantic network is defined as a type of knowledge representation that formalises objects and values as nodes and connects the nodes with arcs or links that indicate the relationships between the various nodes: A data structure for representing declarative knowledge. It can be argued that the nodes can also represent concepts, and the arcs the relations between concepts, thereby forming semantic networks.Quillian has pointed out the "type-token" distinction. This may be related to the generic/specific relationship.
 
 


PROSPECTOR's Inference Mechanism

Probablistic Reasoning

To deal with uncertainty PROSPECTOR uses

                                                • subjective probability theory (including Bayes' theorem.) supplemented
                                                   by Certainty Factors (MYCIN) and fuzzy sets.

A form of Bayes' theorem called "odds-liklihood"is used in PROSPECTOR.
  Definition

                                                            P(h) = LS x P(h)                                        • LS is used when the evidence is known to exist.

                                        • Probabilities are provided subjectively by the expert
 
 


PROSPECTOR's Inference Mechanism

Probablistic Reasoning

DefinitionLN = measure of necessity Again the probabilities are given subjectively by the domain expert.
 
 


PROSPECTOR: Conclusions
 

Points to note about the PROSPECTOR system
 

• the conclusions drawn by the PROSPECTOR system match those of the expert who designed the system to within 7% on a scale used to represent the validity of the conclusions

• work on the system illustrated the importance of accommodating the special characteristics of a domain if the system is intended for practical use - all domains have their own peculiarities in how decisions are made


PROBABLISTIC REASONING: MYCIN, XCON and PROSPECTOR

Evidential Strength Model and Certainty: MYCIN approach


PROBABLISTIC REASONING: MYCIN, XCON and PROSPECTOR

MYCIN: Each rule is associated with a number between 0 and 1 (CF, the 'cretainity factor') representing certainity of the inference contained in the rule: MYCIN combines several sources of inconclusive information to form a conclusion of which it may be almost certain. Ad-hoc appraoch to probability

PROSPECTOR: Confidence measures (LS,LN)are interpreted precisely as as probabilities and Bayes' rule is used as the basis of inference procedure.

XCON: In XCON's task domain it is possible to state exactly the correct thing to be done in each particular set of circumstances. Probablistic information is not neccessary.

0 thoughts on “Dendral Expert System Case Study Ppt Template

Leave a Reply

Your email address will not be published. Required fields are marked *