Considered a "stepping stone" from older AI programs since it is based on heuristic search but involves an explicit representation of the domain knowledge (before systems used just states)

Task: Identification (classification?) of molecular structures of organic compounds (note: formula is known)

Technique: Generate and Test (Jackson Second edition: page 36)

Knowledge representation - substructures

• example: glasses
• Mass spectogram (spectral processes)

Mass Spectrometer - charged particles collected by mass to form a spectrum (In most ions, the charge is 1, so m/e is simply the mass of the ion)

If have two compounds, one known and one unknown, then mass spectra is proof ("almost beyond the shadow of a doubt" Organic Chemistry, Morrison and Boyd) that the two compounds are identical.

To establish a new compound,

• it can give an exact molecular weight
• can indicate the presence of certain structural units
• it can give a molecular formula (narrow possibilities)

Problem: many ways to fragment (glasses example)

Solution: Constraints as heuristics

• have deduced a possible chemical formula
• have presence (or absence) of certain substructures
  what is the actual arrangement?

Constraints: serve to restrict or rule out many possibilities

Why not just generate all possibilities of isomer arrangements

and discard ones that don't fit constraints?

10,000 for C6H13NO2

Want to minimize the initial generation

"it applies knowledge of spectral processes (how things break) to infer constraints from instrumental data." (page 38)

Types of constraints

1. required: based on conclusions so far and requisite features
2. forbidden: don't fit data, chemical instability

a DENDRAL program - "constructs complete chemical structures by manipulating symbols that stand for atoms and molecules...receives as its input a molecular formula, together with a set of constraints which serve to restrict the possible interconnections among atoms. Its output is a list of all possible ways of assembling the atoms into molecular structures, given the constraints imposed."

(aside: input, what, output, how (subprocesses))

Note: allows chemist to specify various kinds of structural constraints, then generates an exhaustive and nonredundant list

Specific kinds of constraints (page 39)

still, too many can be generated:

MSPRUNE - eliminates candidates

MSRANK - orders

basically: hypothesize and test (but note how each program has its own task (possibly different forms of reasoning - we decided this, the program does not know it, nor how it does what it does)

Example: page 40

In STRIPS Fikes and Nilsson [1971] use a GPS-like [Newell 1963] means-ends analysis strategy.

It was intended to solve the problem of plan formation in a robot designed to move (and stack) objects.

In the STRIPS representation, a world state is represented by a set of logical formulas, a conjunction of which describes the given state.

W = {ON(b,a) & ONTABLE(a) & ONTABLE(c) & ONTABLE(d) & ARMEMPTY}

W'

W''

GOAL = {ON(c,a) & ON(b,d) & ONTABLE(a) & ONTABLE(d) }

Actions are represented by operators which consist of three lists:

• ADD: The list of new predicates that the operator causes to become true.
• DELETE: The list of old predicates that the operator causes to become false.
• PRECONDITION: The list of predicates that must be true for the operator to be applied.

OPERATORS:

STACK(x,y)

• P: CLEAR(y) & HOLDING(x)
• D: CLEAR(y) & HOLDING(x)
• A: ARMEMPTY & ON(x,y)

UNSTACK(x,y)

• P: ON(x,y) & CLEAR (x) & ARMEMPTY
• D: ON(x,y) & ARMEMPTY
• A: HOLDING(x) & CLEAR(y)

PICKUP(x)

• P: CLEAR (x) & ONTABLE(x) & ARMEMPTY
• D: ONTABLE(x) & ARMEMPTY
• A: HOLDING(x)

PUTDOWN(x)

• P: HOLDING(x)
• D: HOLDING(x)
• A: ONTABLE(x) & ARMEMPTY

"to assist a physician who is not an expert in the field of antibiotics with the treatment of blood infections."

notes (example run)

Production system:

• production memory ... rules
• working memory (patient database)
• inference engine: recognize-act

• consultation program (to help with the knowledge above)
• explanation program
• knowledge acquisition program

MYCINs rules

Rule premise: conjuntion of clauses can contain arbitrarily complex conjunctions or disjunctions

KNOWLEDGE REPRESENTATION

• rules ... if then
• clauses: each has 4 components

(<predicate fcn>  <object> <attribute> <value>)

(   MEMB	   CNTXT      SITE     STERILESITES)

Medical facts are represented as 4-tuples made up of an associative triple and its current Confidence Factor.

(IDENT 		ORGANISM-2 	KLEBSIELLA 	.25)
(IDENT 		ORGANISM-2  	E.COLI       	.73)
(SENSITIVS 	ORGANISM-1   	PENICILLIN  	-1.0)
(IMMUNOSUPPRESSED  PATIENT-1    YES    		 1.0)

Rules: composed of a premise and an action. For example:

IF

1. the infection is primary-bacteremia, and

2. the site of the culture is one of the sterile sites, and

3. the suspected portal of entry of the organism is the gastrointestinal tract

there is suggestive evidence (.7) that the identity of the organism is bacteroids

PREMISE:

	(AND (SAME_CONTEXT INFECT PRIMARY-BACTEREMIA)

	(MEMBF_CONTXT SITE STERILESITES)

	(SAME_CNTXT PORTAL GI)

ACTION:

	(CONCLUDE CNTXT_IDENT BACTEROIDES TALLY .7)

INFERENCE ENGINE

backward chaining,

exhaustive

depth-first search of the AND/OR tree

Improvements

MYCIN - Diagnosis and Treatment for Infectious Diseases [Shortliffe, 1976]

TEIRESAIS - metarules; knowledge acquisition

premise: explanation simply by trace of program execution

Meta-rule 001

If

1. the infection is a pelvic-abscess, and

2. there are rules that mention in their premise Enterobacteriaceae, and

3. there are rules that mention in their premise gram

   positive rods

[Davis, doctoral diss., 1976] ...supported explanation& acquisition

GUIDON - teaching diagnostic problem-solving (tutorial) ICAI: Intelligent Computer Aided Instruction [Clancey, doctoral diss.,1979]

EMYCIN - domain independent Mycin [VanMelle, doctoral diss., 1980 ]

NEOMYCIN - domain independent Teiresias - separates diagnostic strategy from domain knowledge.

-

Uses hierarchical organization of data and hypothesis (makes implicit design knowledge explicit) [Clancey & Letsinger, 1981]

Evaluation, Comparisons

see text, pages 53-55

AI Considerations

Generic Types (categories of applications):

arguments:

• primitives - what are tasks and what are methodologies
  - atomic vs. molecular types
  eg. is "analogy" a task or method?
  is "consultation" (MYCIN) a category?

• Interpretation vs. Diagnosis
  (difference in problem-type?)

• Interpretation vs. Perception

• Diagnosis and Classification

• explicit properties (due to the problems representation) vs. emergent properties (due to implicit aspects of an agent's strategy)

• * significance - explanatory power

Significant Issue

Issue not raised: significance in both: What a system does AND How it does it