EXPERT SYSTEMS

Problems with Logical Reasoning

• Brittleness: one axiom/fact wrong, system can
prove anything (Correctness)
• Large proof spaces (Efficiency)
• “Probably” not representable (Representation)
• No notion of combining evidence
• Doesn’t provide confidence in conclusion.
 CSE4403 3.0 & CSE6002E - Soft Computing
Winter Semester, 2011

Expert Systems – Building Blocks of Expert Systems

Another widely used representation, called the unit (also known as frame,
schema, or list structure) is based upon a more passive view of knowledge.
The unit is an assemblage of associated symbolic knowledge about an
entity to be represented. Typically, a unit consists of a list of properties of
the entity and associated values for those properties.
Since every task domain consists of many entities that stand in various
relations, the properties can also be used to specify relations, and the
values of these properties are the names of other units that are linked
according to the relations. One unit can also represent knowledge that is a
"special case" of another unit, or some units can be "parts of" another unit.
 CSE4403 3.0 & CSE6002E - Soft Computing
Winter Semester, 2011

Expert Systems – Early Expert Systems Success Stories

DENDRAL (Feigenbaum, Lederberg, and Buchanan, 1965)
• deduce the likely molecular structure of organic chemical compounds from
known chemical analyses and mass spectrometry data
MYCIN (Buchanan and Shortliffe, 1972-1980)
• diagnosis of infectious blood diseases and recommendation for use of
antibiotics
• “empty” MYCIN = EMYCIN = XPS shell
PROSPECTOR
• analysis of geological data for minerals
• discovered a mineral deposit worth $100 million
XCON/R1 (McDermott, 1978)
• configuration of DEC VAX computer systems
• 2500 rules; processed 80,000 orders by 1986; saved DEC $25M a year
 MYCIN: 1972-1980
• 50-500 rules, acquired from expert by interviewing.
Blood disease diagnosis.
• Example rule:
if stain of organism is gramneg and morphology is rod
and aerobicity is aerobic then strongly suggestive (.8)
that organism is enterocabateriacease.
• Rules matched well knowledge in domain: medical
papers often present a few rules
• Rule = nugget of independent knowledge
 Facts are not facts
• Morphology is rod requires microscopic
evaluation.
– Is a bean shape a rod?
– Is an “S” shape a rod?
• Morphology is rod is assigned a confidence.
• All “facts” assigned confidences, from 0 to 1.
 MYCIN: Shortliffe
• Begins with a few facts about patient
– Required by physicians but irrelevant
• Backward chains from each possible goal (disease).
• Preconditions either match facts or set up new subgoals.
Subgoals may involve tests.
• Finds all “proofs” and weighs them.
• Explains decisions and combines evidence
• Worked better than average physician.
• Never used in practice.
• Methodology used.
 Examples and non-examples
• Soybean diagnosis
– Expert codified knowledge in form of rules
– System almost as good
– When hundreds of rules, system seems reasonable.
• Autoclade placement
– Expert but no codification
• Chess
– Experts but no codification in terms of rules
 Forward Chaining Interpreter
• Repeat
– Apply all the rules to the current facts.
– Each rule firing may add new facts
• Until no new facts are added.
• Comprehensible
• Trace of rule applications that lead to conclusion
is explanation. Answers why.
 Forward Chaining Example
• Facts:
– F1: Ungee gives milk
– F2: Ungee eats meat
– F3: Ungee has hoofs
• Rules:
– R1: If X gives milk, then it is a mammal
– R2: If X is a mammal and eats meat, then carnivore.
– R3: If X is a carnivore and has hoofs, then ungulate
• Easy to see: Ungee is ungulate.
 Backward Chaining
• Start with Goal G1: is Ungee an ungulate?
• G1 matches conclusion of R3
• Sets up premises as subgoals
– G2: Ungee is carnivore
– G3: Ungee has hoofs
• G3 matches fact F3 so true.
• G2 matches conclusion of R2. etc.
 The good and the bad
• Forward chaining allows you to conclude
anything
• Forward chaining is expensive
• Backward chaining requires known goals.
• Premises of backward chaining directs which
facts (tests) are needed.
• Rule trace provides explanation.
 Simple Confidence Calculus
• This will yield an intuitive degree of belief in
system conclusion.
• To each fact, assign a confidence or degree of
belief. A number between 0 and 1.
• To each rule, assign a rule confidence: also a
number between 0 and 1.
• Confidence of premise of a rule =
– Minimum confidence of each condition
– Intuition: strength of argument is weakest link
• Confidence in conclusion of a rule =
– (confidence in rule premise)*(confidence in rule)
• Confidence in conclusion from several rules:
r1,r2,..rm with confidences c1,c2,..cm =
– c1 @ c2 @... cm
 And now with confidences
• Facts:
– F1: Ungee gives milk: .9
– F2: Ungee eats meat: .8
– F3: Ungee has hoofs: .7
• Rules:
– R1: If X gives milk, then it is a mammal: .6
– R2: If X is a mammal and eats meat, then carnivore: .5
– R3: If X has hoofs, then X is carnivore: .4
• R1 with F1: Ungee is mammal. (F4)
• Confidence F4: C(F4) = .9*.6 = .54
• R2 using F2 and F4 yields: Ungee is carnivore
(F5).
• C(F5) from R2 = min(.54, .8)*.5 = .27
• R3 using F3 conclude F5 from R3
• C(F5) from R3 = .7*.4 = .28
• C(F5) from R3 and R2 = .27 @ .28 = 1–
(1-.28)*(1-.27) = .48
 Problems and Counters-Arguments
• People forget to say the obvious
• Rules difficult to acquire (years)
• People don’t have stable or correct estimates of
“confidence”
• Data insufficient to yield good estimate of true
probabilities.
• But Feigenbaum: In the knowledge lies the
power.
• Calculus/confidences not that important
 AI Winter
• Expert Systems found useful
– hundreds of successful systems
• Consultants and hype ->
– Hundreds of unsucessful systems
• Remember:
– needs an expert
– Knowledge needs to be representable as rules
• Now on to Probability based approach