Transcript Programming and Problem Solving with Java: Chapter 14

Search Methods
Reasoning/ Proof
Problem Solving
Predicate Logic
Bayesian Network
Expert System
(Rule Based Inference)
• Diagnosis (Decision Making)
• Advice (Recommendations)
• Automatic Control
Pattern Recognition
Data Mining, etc.
Probability (statistics)
Uncertainty (cybernetics)
Fuzzy Theorem
Machine Learning
Fuzzy, NN, GA, etc.
Chapter 9
Rules and Expert Systems
1
Recall:
Deduction over FOPC --- Resolution
Dog(X) ^ Meets(X,Y)^Dislikes(X,Y)  Barks_at(X,Y)
Barks_at(Snoopy,John) False
{X/Snoopy, Y/John}
Dog(Snoopy) ^ Meets(Snoopy,John)^Dislikes(Snoopy,John)  F
T  Dog(Snoopy)
Meets(Snoopy,John)^Dislikes(Snoopy,John)  False
Close_to(Z,DormG)  Meets(Snoopy, Z)
{Z/John}
Close_to(John,DormG)^Dislikes(Snoopy,John)  False
True  Close_to(John, DormG)
Man(W)  Dislikes(Snoopy,W)
Dislikes(Snoopy,John)  False
{W/John}
True  Man(John)
此為 “Implies” Normal Form
了解此法可以銜接 “Expert System”
Man(John)  False
True  False
2
Recall:
Refutation Proofs in Tree Form
Forward Chaining + Refutation
P, PQ Should Q be true?
PQ
TrueP
TrueQ
QFalse
P
¬P VQ
 這兩種形式 
皆有相關研究採用
¬Q
Q
^
TrueFalse
Backward Chaining (Resolution)
QFalse
PQ
PFalse
TrueFalse
TrueP
¬Q
¬P VQ
P
¬P
^
3
Chapter 9 Contents






Rules for Knowledge
Representation
Rule Based Production
Systems
Forward Chaining
Conflict Resolution
Meta Rules
Backward Chaining





The Architecture of
Expert Systems
Expert System Shells
The Rete Algorithm
Knowledge Engineering
CLIPS:
C Language Integrated
Production System


Backward Chaining in
Expert Systems
CYC System
4
Rules for Knowledge Representation

IF… THEN Rules can be used to represent
knowledge:
 IF it rains, then you will get wet

Rules can also be recommendations:
 IF it rains, then you should wear a coat
5
Example (Rule Based Inference)
rains_on(x)  wet(x)
Truerains_on(John)
{x/John}
Truewet(John)
wet(John)False …wet(John)是否成立?
¬ wet(John)False … ¬ wet(John)如何能成立?
p.s. 不穿雨衣一定溼，但穿雨衣不保證不溼
rains_on(x) ^ ¬coat(x)  wet(x)
Truerains_on(John)
{x/John}
¬coat(John)  wet(John)
Truewet(John)
Trure  ¬coat(John)
如果¬coat(John) 會導致 wet(John) 成立
6
Rule Based Production Systems


A production system is a system that uses
knowledge in the form of rules to provide
diagnoses or advice on the basis of input
data.
The system consists of a database of rules
(knowledge base), a database of facts, and
an inference engine which reasons about
the facts using the rules.
7
Forward Chaining


Forward chaining is a reasoning model
that works from a set of facts and rules
towards a set of conclusions, diagnoses or
recommendations.
When a fact matches the antecedent of a
rule, the rule fires, and the conclusion of
the rule is added to the database of facts.
8
Example (Forward Chaining)
Man(W)  Dislikes(Snoopy, W)
{W/John}
Close_to(Z,DormG)  Meets(Snoopy, Z)
TMan(John)
TDislikes(Snoopy, John)
{Z/John}
(1)
(2)
TClose_to(John, DormG)
TMeets(Snoopy, John)
(3)
Dog(X) ^ Meets(X,Y)^Dislikes(X,Y)  Barks_at(X,Y)
(4)
TDog(Snoopy)
Meets(Snoopy,Y)^Dislikes(Snoopy,Y)  Barks_at(Snoopy,Y)
{Y/John}
(5)
Meets(Snoopy,John)  Barks_at(Snoopy,John)
Barks_at(Snoopy,John) False
TBarks_at(Snoopy,John)
9
Conflict Resolution



牴觸的規則
Sometimes more than one rule will fire at once,
and a conflict resolution strategy must be used to
decide which conclusions to use.
One strategy is to give rules priorities and to use
the conclusion that has the highest priority.
Other strategies include applying the rule with the
longest antecedent, or applying the rule that was
most recently added to the database.
(1) 天氣好,睡得好,工作不忙 去打球； vs.“吃飽飯不打球”
(2) 男生,穿拖鞋,靠近女生宿舍小花吠; vs.“吃飯中不吠人”
Priority?
10
Meta Rules




The rules that determine the conflict resolution
strategy are called meta rules.
Meta rules define knowledge about how the
system will work.
For example, meta rules might define that
knowledge from Expert A is to be trusted more
than knowledge from Expert B.
Meta rules are treated by the system like normal
rules, but are given higher priority.
11
Backward Chaining



In cases where a particular conclusion is to be
proved, backward chaining can be more
appropriate.
Works back from a conclusion towards the
original facts.
When a conclusion matches the conclusion of a
rule in the database, the antecedents of the rule
are compared with facts in the database.
12
Example (Backward Chaining)
Dog(X) ^ Meets(X,Y)^Dislikes(X,Y)  Barks_at(X,Y)
Barks_at(Snoopy,John) False
{X/Snoopy, Y/John}
Dog(Snoopy) ^ Meets(Snoopy,John)^Dislikes(Snoopy,John)  F
T  Dog(Snoopy)
Meets(Snoopy,John)^Dislikes(Snoopy,John)  False
Close_to(Z,DormG)  Meets(Snoopy, Z)
{Z/John}
Close_to(John,DormG)^Dislikes(Snoopy,John)  False
True  Close_to(John, DormG)
Dislikes(Snoopy,John)  False
Man(W)  Dislikes(Snoopy, W)
True  Man(John)
{W/John}
Man(John)  False
True  False
13
Recall:
Example (Forward Chaining)
Man(W)  Dislikes(Snoopy, W)
{W/John}
TMan(John)
TDislikes(Snoopy, John)
Close_to(Z,DormG)  Meets(Snoopy, Z)
{Z/John}
TClose_to(John, DormG)
TMeets(Snoopy, John)
Dog(X) ^ Meets(X,Y)^Dislikes(X,Y)  Barks_at(X,Y)
TDog(Snoopy)
Meets(Snoopy,Y)^Dislikes(Snoopy,Y)  Barks_at(Snoopy,Y)
{Y/John}
Meets(Snoopy,John)  Barks_at(Snoopy,John)
TBarks_at(Snoopy,John)
14
Chapter 9 Contents






Rules for Knowledge
Representation
Rule Based Production
Systems
Forward Chaining
Conflict Resolution
Meta Rules
Backward Chaining





The Architecture of
Expert Systems
Expert System Shells
The Rete Algorithm
Knowledge Engineering
CLIPS:
C Language Integrated
Production System


Backward Chaining in
Expert Systems
CYC System
15
The Architecture of Expert Systems (1)

An expert system
uses expert
knowledge
derived from
human experts to
diagnose
illnesses, provide
recommendations
and solve other
problems.
16
The Architecture of Expert Systems (2)

Knowledge base:
 database of rules (domain knowledge).

Explanation system:
 explains the decisions the system makes.

Knowledge base editor:
 allows the user to edit the information in the knowledge base.

User Interface:
 the means by which the user interacts with the expert system.
17
Expert System Shells

The part of an expert system (內容不算)
 Neither domain specific nor case specific knowledge is
contained in the expert system shell.

A single expert system shell can be used
 to build a number of different expert systems.

An example of an expert system shell is
 CLIPS.
18
The Rete Algorithm
root
¬man(J)
man(J)
¬dog(S)
dog(S)




recommendations

A rete is a directed, acyclic, rooted
graph (i.e. a “Search Tree”).
A path from the root node to a leaf
represents the left hand side of a rule.
Each node stores details of which
facts have been matched so far.
As facts are changed, the changes are
propagated through the tree from the
root to the leaves.
This makes an efficient way for expert
systems to deal with environments
which change often.
19
Knowledge Engineering



A knowledge engineer takes knowledge
from experts and inputs it into the expert
system. (擷取)
A knowledge engineer will usually choose
which expert system shell to use. (實現)
The knowledge engineer is also
responsible for entering meta-rules. (整合)
Expert System (Rule Based Production System)
只是後來所謂「知識工程」的一個小部份
20
CLIPS


CLIPS is C Language
Integrated Production
System – an expert
system shell.
CLIPS uses a LISP-like
notation to enter rules.
21
Backward Chaining in Expert Systems

Backward chaining is often used in expert
systems that are designed for medical diagnosis:
 For each hypothesis, H:
 If H is in the facts database, it is proved.
 Otherwise, if H can be determined by asking a question, then enter
the user’s answer in the facts database. Hence, it can be
determined whether H is true or false, according to the user’s
answer.
 Otherwise, find a rule whose conclusion is H. Now apply this
algorithm to try to prove this rule’s antecedents.
 If none of the above applies, we have failed to prove H.

Usually backward chaining is used in conjunction
with forward chaining.
相輔相成
22
CYC



A frame based production system.
Uses a database of over 1,000,000 facts
and rules, encompassing all fields of
human knowledge.
CYC can answer questions about all kinds
of knowledge in its database, and can even
understand analogies, and other complex
relations.
23
Relevant Research
Search Methods
Reasoning/ Proof
Problem Solving
Predicate Logic
Bayesian Network
Expert System
(Rule Based Inference)
Probability (statistics)
Uncertainty (cybernetics)
• Diagnosis (Decision Making)
• Advice (Recommendations)
• Automatic Control
Fuzzy Theorem
In my opinion:
記憶
評判
Pattern Recognition
Data Mining, etc.
搜尋解答
邏輯推理
Machine Learning
Fuzzy, NN, GA, etc.
weak
sub?
控制
學習
strong
創作
Fuzzy,NN,GA
24