Expert Systems

Expert Systems

Resources Wikipedia [link] handout from AI illuminated, pages 46-50, 75-78, 81-83, 144-152, 267-284

http://www.cs.usfca.edu/www.AlanTuring.net/turing_archive/pages/Referenc

[distance learning link]

AI  So

far: Machine Learning

– Inductive reasoning

 Now:

Logical Inference

– Deductive reasoning







An expert system is a computer program dedicated to solving problems and giving advice within a specialised area of knowledge. A good system can match the performance of a human specialist; expert systems are in wide commercial use. Uses include medical diagnosis, chemical analysis, credit authorization, financial management, corporate planning, automobile design and manufacture, camera lens design, computer installation design, airline scheduling, cargo placement, and on and on….

Expert Systems “Common sense” hard to program - just so broad. “Deep Knowledge” / Expert System / Fact-Rich easier to program if the domain is limited. Hundreds of applications: medical, science, business, … One of great success stories of AI

Expert Systems

 http://www.aiinc.ca/demos/whale.ht

 http://www.myacquire.com/aiinc/sto

edural Knowledge

cision diagram is a kind xpert system

to implement this c in a computer program

n knowledge not cally “stored” in this way

Big View Knowledge Base

User Inference Engine

Knowledge Base  stores

facts about a domain  often in form of “if-then” rules  example  [FROM CS Illuminated p 420]

example rule in knowledge base

(from MYCIN - bacterial infections 1972) If the site of the culture is blood, and the stain of the organism is gramneg, and the morphology of the organism is rod, and the patient has been seriously burned, then there is evidence (.4) that the identity of the organism is pseudomonas.  

Thousands of rules Knowledge Engineer with domain expert

possible works in concert to extract useful

Inference Engine  Abstract

rules of logic showing what deductions can be made.

Crash course: propositional logic symbols: AND (∧), OR (∨), IMPLIES (→), NOT (¬)

Truth Table for Implies A F T T F

B

A →B F T T

F

F T ?

?

Not the same as “causes” !!

Example Translation 1. 2. 3. • 4. • • •

If Pat was involved, then Quinn was too. Pat or Ralph did it. If Ralph did it, then so did Sam. P → has Q a good alibi. Sam P ∨ R Translation into logic statements R → S ¬S

example deduction rules If you know Then you can p, p → q conclude q p ∧ q

p

p

p ∨ q

p ∨ q, q → p ∨ r r p → q, ¬q ¬p p ∨ q, ¬p

q

forward chaining

resolution contraposit ive

Example Deduction: “whodunnit”

1. 2. 3. • 4. • • •

If Pat was involved, then Quinn was too. Pat or Ralph did it. If Ralph did it, then so did Sam. P → has Q a good alibi. Sam P ∨ R Translation into logic statements R → S ¬S

n n n n

P → Q P ∨ R R → S ¬S

stmt 3, 4, contrapositive, gives: n ¬R stmt 2, 5 implies 9. P stmts 6, 1 implies 11. Q Therefore, Pat and Quinn are guilty.

Inference Engine  Two

methods

– forward chaining (you’ve just seen it)  start with known facts  look for left sides of implications that are met, and conclude the right side.  repeat

– backward chaining (example to follow)

 goal to conclude some goal “fact” G  find implication rule with right side G

RULES (from KB) n A ∧ B → C FORWARD CHAINING n A → D (b) Facts A, B, and n C ∧ D → E rule (1) gives n B ∧ E ∧ F → C H (c) Fact A, rule (2) n A ∧ E → G gives D (d) (a), (b), and (3) FACTS (from gives E user): (e) Fact A, (c), rule A, B, F (5) gives G GOAL:

G

THUS, G is true.

RULES (from KB) n A ∧ B → C n A → D n C ∧ D → E n B ∧ E ∧ F → H n A ∧ E → G

FACTS (from user): A, B, F GOAL:

G

BACKWARD CHAINING (b) Goal G (c) By (5), subgoals: A, E (d) Subgoal A met (FACT) (e) By (3), subgoals C, D (f) By (2), subgoal D met (g) By (1), subgoals A, B (h) A, B met (FACTS)

the process USER SUPPLIED FACTS system may request more facts from user

DOMAIN KNOWLEDGE

INFERENCE ENGINE chaining with logical rules

Main task in building an expert system

MORE FACTS CONCLUSIONS

Do we have an algorithm for Logical Inference?

 Input

assumptions + G  Keep applying each rule of inference.  Stop when we get to G

Does this terminate? Which problem does this remind you of? Can we think of an algorithm that works? (Yes we can !!)

Explainable results Nice feature of expert systems is that typically they can explain the reasons for their answers to human users: “G is true because A and B were found to be true.” “A is true because C and D are true.”