1月14日 專家系統
1
Rules and Expert Systems 1
Topic 9 Rules and Expert
Systems
Rules and Expert Systems 2
Architecture of an expert system
Modules that make up a
typical expert system:
User interface
Knowledge base
General knowledge
Case-specific information
Inference engine
Explanation subsystem
Why queries
Why the system needs a
particular piece of data
How queries
How the system makes the
conclusion
Knowledge-base editor
2
Rules and Expert Systems 3
Problems appropriate for expert
systems
1. The need for the solution justifies the cost and effort of building
an expert system.
2. Human expertise is not available in all situations where it is
needed.
3. The problem may be solved by symbolic reasoning.
4. The problem domain is well structured and does not require
commonsense reasoning.
5. The problem may not be solved using traditional computing
methods.
6. Cooperative and articulate experts exist.
7. The problem is of proper size and score.
Rules and Expert Systems 4
Who involves in building expert
systems?
Domain expert
Provide the knowledge of the problem domain.
Knowledge engineer
Help the domain expert articulate the necessary
knowledge and implement that knowledge in a
knowledge base.
End user
Determine the main design constraints.
3
Rules and Expert Systems 5
Knowledge acquisition
Buchanan et al. (1983) define knowledge
acquisition as:
The transfer and transformation of potential
problem-solving expertise from some knowledge
source to a program.
Rules and Expert Systems 6
Conceptual model in knowledge
acquisition
To simplify knowledge engineering, it is
useful to consider a conceptual model that
lies between expertise and the implemented
program.
4
Rules and Expert Systems 7
Rule-based expert systems
Represent problem-solving knowledge as
if … then… rules.
if portion
The premise of the rule
The condition of the rule
then portion
The conclusion of the rule
The action of the rule
Rules and Expert Systems 8
Rule-based expert systems (cont’d)
Rule-based systems or production systems
are computer systems that use rules
to provide recommendations or diagnoses, or
to determine a course of action in a particular
situation or
to solve a particular problem.
5
Rules and Expert Systems 9
Rule-based expert systems (cont’d)
A rule-based system consists of
a database of rules (knowledge based);
a database of facts;
an interpreter, or inference engine.
The rule-based system derives conclusions
using deduction
forward chaining
Known as data-driven reasoning
backward chaining
Known as goal-driven reasoning
Rules and Expert Systems 10
Forward chaining
The system starts from a set of facts, and a set of
rules, and tries to find a way of using those rules
and facts to deduce a conclusion or come up with a
suitable course of action.
Compare the contents of working memory with the
conditions of each rule using the ordering of the rule base.
If the data in working memory supports a rule’s firing the
result is placed in working memory and then control moves
on to the next rule.
Once all rules have been considered, search starts again at
the beginning of the rule set.
6
Rules and Expert Systems 11
Fact 1
At first floor
Fact 2
Button pressed on third floor
Fact 3
Today is Tuesday
Example 1
Rule 1:
IF on first floor AND button is pressed on first floor THEN open door
Rule 2:
IF on first floor AND button is pressed on second floor THEN go to second floor
Rule 3:
IF on first floor AND button is pressed on third floor THEN go to third floor
Rule 4:
IF on second floor AND button is pressed on first floor AND already going to third floor
THEN remember to go to first floor later
matching
action
Rules and Expert Systems 12
Fact 1
At first floor
Fact 2
Button pressed on second floor
Fact 3
Button pressed on third floor
Example 2
Rule 1:
IF on first floor AND button is pressed on first floor THEN open door
Rule 2:
IF on first floor AND button is pressed on second floor THEN go to second floor
Rule 3:
IF on first floor AND button is pressed on third floor THEN go to third floor
Rule 4:
IF on second floor AND button is pressed on first floor AND already going to third floor
THEN remember to go to first floor later
matching
Conflict
resolution
7
Rules and Expert Systems 13
Example 2
Rule 1:
IF the engine is getting gas, AND the engine will turn over,
THEN the problem is spark plugs.
Rule 2:
IF the engine does not turn over, AND the lights do not come on
THEN the problem is battery or cables.
Rule 3:
IF the engine does not turn over, AND the lights do come on
THEN the problem is the starter motor.
Rule 4:
IF there is gas in the fuel tank, AND there is gas in the carburetor
THEN the engine is getting gas.
“Askable” information: the information that makes up the premise of
a rule is not the conclusion of some other rule. For example, “The
engine is getting gas” is not askable.
“Askable” information: the information that makes up the premise of
a rule is not the conclusion of some other rule. For example, “The
engine is getting gas” is not askable.
Engine turns over
Working memory after considering rule 2
Rule 1: The engine is getting gas is not askable.
Rule 2: The engine does not turn over is askable.
Suppose the answer is fail.
Rule 3: fail
Rule 4: the premises are askable.
Suppose that the answers to both questions are true.
The engine is getting gas
Gas in fuel tank
Gas in carburetor
Engine turns over
Working memory after considering rule 4
First pass
8
The problem is spark
plugs
The engine is getting gas
Gas in fuel tank
Gas in carburetor
Engine turns over
Working memory after firing rule 1
Second pass
No more rule can fire and the search is completed
Matching the premises of rule 1
Fire rule 1
WM
The engine turns over
The engine turns over
The engine is getting gas
Gas in fuel tank
Gas in carburetor
Engine turns over
fail fail fail fire
First pass
Rule1 Rule2 Rule3 Rule4
The engine is getting gas
Gas in fuel tank
Gas in carburetor
Engine turns over
Second pass
The problem is spark plugs
The engine is getting gas
Gas in fuel tank
Gas in carburetor
Engine turns over
Rule1 Rule2 Rule3 Rule4
Halt with no more rules matching
Rule 1 fires
Breadth-first search
9
Rules and Expert Systems 17
Refinement on the breadth-first search
strategy
Opportunistic search
Whenever a rule fires to conclude new information,
control moves to consider those rules which have
the new information as a premise.
Rules and Expert Systems 18
Explanation in data-driven systems
Data-driven reasoning is much less “focused”
in its search.
The explanation available to the user at any
time in the search is quite limited.
10
Rules and Expert Systems 19
Backward chaining
Backward chaining is very appropriate to the
case that a single specific conclusion is to be
proved.
It is often to build an expert system by using
a rule-based system with backward chaining.
Rules and Expert Systems 20
Example 1
Rule 1:
IF the engine is getting gas, AND the engine will turn over,
THEN the problem is spark plugs.
Rule 2:
IF the engine does not turn over, AND the lights do not come on
THEN the problem is battery or cables.
Rule 3:
IF the engine does not turn over, AND the lights do come on
THEN the problem is the starter motor.
Rule 4:
IF there is gas in the fuel tank, AND there is gas in the carburetor
THEN the engine is getting gas.
11
Rules and Expert Systems 21
The problem is X
Working memory
Rule 1
Rule 2
Rule 3
Rule 4
Production rules
The engine is
getting gas.
The engine will
turn over
The problem is
spark plugs.
Working memory
Rule 1
Rule 2
Rule 3
Rule 4
Production rules
Rule 1 is fired
Gas in fuel tank.
Gas in carburetor.
The engine will
turn over
The problem is
spark plugs.
Rule 1
Rule 2
Rule 3
Rule 4
Rule 4 is fired
Do not match
with any rule
conclusions
Q: Is gas in fuel tank?
Q: Is gas in carburetor?
Q: Will the engine turn over?
Query the
user directly
“Askable” information: the information that makes up the
premise of a rule is not the conclusion of some other rule.
Rules and Expert Systems 22
Searching in and/or graph
and
or
12
Rules and Expert Systems 23
Explanation: why query
Q: Is gas in fuel tank?
yes
Q: Is gas in carburetor?
yes
Q: Will the engine turn over?
why
(why do you want to know whether the engine will turn over?)
Show the chain of rules and goals between the current goal and the
top goal.
Answer>It has been established that the engine is getting gas; therefore if
the engine will turn over, then the problem is spark plugs.
Rules and Expert Systems 24
Current goal
Top goal
The ‘why’ explanation.
13
Rules and Expert Systems 25
Explanation: how query
How the engine is getting gas
(how query)
Give a trace of the reasoning that leads to a goal.
Answer>This follows from rule 4:
if there is gas in the fuel tank, and there is gas in the carburetor then
the engine is getting gas.
Rules and Expert Systems 1
Topic 9 Rules and Expert
Systems
Rules and Expert Systems 2
Architecture of an expert system
Modules that make up a
typical expert system:
User interface
Knowledge base
General knowledge
Case-specific information
Inference engine
Explanation subsystem
Why queries
Why the system needs a
particular piece of data
How queries
How the system makes the
conclusion
Knowledge-base editor
2
Rules and Expert Systems 3
Problems appropriate for expert
systems
1. The need for the solution justifies the cost and effort of building
an expert system.
2. Human expertise is not available in all situations where it is
needed.
3. The problem may be solved by symbolic reasoning.
4. The problem domain is well structured and does not require
commonsense reasoning.
5. The problem may not be solved using traditional computing
methods.
6. Cooperative and articulate experts exist.
7. The problem is of proper size and score.
Rules and Expert Systems 4
Who involves in building expert
systems?
Domain expert
Provide the knowledge of the problem domain.
Knowledge engineer
Help the domain expert articulate the necessary
knowledge and implement that knowledge in a
knowledge base.
End user
Determine the main design constraints.
3
Rules and Expert Systems 5
Knowledge acquisition
Buchanan et al. (1983) define knowledge
acquisition as:
The transfer and transformation of potential
problem-solving expertise from some knowledge
source to a program.
Rules and Expert Systems 6
Conceptual model in knowledge
acquisition
To simplify knowledge engineering, it is
useful to consider a conceptual model that
lies between expertise and the implemented
program.
4
Rules and Expert Systems 7
Rule-based expert systems
Represent problem-solving knowledge as
if … then… rules.
if portion
The premise of the rule
The condition of the rule
then portion
The conclusion of the rule
The action of the rule
Rules and Expert Systems 8
Rule-based expert systems (cont’d)
Rule-based systems or production systems
are computer systems that use rules
to provide recommendations or diagnoses, or
to determine a course of action in a particular
situation or
to solve a particular problem.
5
Rules and Expert Systems 9
Rule-based expert systems (cont’d)
A rule-based system consists of
a database of rules (knowledge based);
a database of facts;
an interpreter, or inference engine.
The rule-based system derives conclusions
using deduction
forward chaining
Known as data-driven reasoning
backward chaining
Known as goal-driven reasoning
Rules and Expert Systems 10
Forward chaining
The system starts from a set of facts, and a set of
rules, and tries to find a way of using those rules
and facts to deduce a conclusion or come up with a
suitable course of action.
Compare the contents of working memory with the
conditions of each rule using the ordering of the rule base.
If the data in working memory supports a rule’s firing the
result is placed in working memory and then control moves
on to the next rule.
Once all rules have been considered, search starts again at
the beginning of the rule set.
6
Rules and Expert Systems 11
Fact 1
At first floor
Fact 2
Button pressed on third floor
Fact 3
Today is Tuesday
Example 1
Rule 1:
IF on first floor AND button is pressed on first floor THEN open door
Rule 2:
IF on first floor AND button is pressed on second floor THEN go to second floor
Rule 3:
IF on first floor AND button is pressed on third floor THEN go to third floor
Rule 4:
IF on second floor AND button is pressed on first floor AND already going to third floor
THEN remember to go to first floor later
matching
action
Rules and Expert Systems 12
Fact 1
At first floor
Fact 2
Button pressed on second floor
Fact 3
Button pressed on third floor
Example 2
Rule 1:
IF on first floor AND button is pressed on first floor THEN open door
Rule 2:
IF on first floor AND button is pressed on second floor THEN go to second floor
Rule 3:
IF on first floor AND button is pressed on third floor THEN go to third floor
Rule 4:
IF on second floor AND button is pressed on first floor AND already going to third floor
THEN remember to go to first floor later
matching
Conflict
resolution
7
Rules and Expert Systems 13
Example 2
Rule 1:
IF the engine is getting gas, AND the engine will turn over,
THEN the problem is spark plugs.
Rule 2:
IF the engine does not turn over, AND the lights do not come on
THEN the problem is battery or cables.
Rule 3:
IF the engine does not turn over, AND the lights do come on
THEN the problem is the starter motor.
Rule 4:
IF there is gas in the fuel tank, AND there is gas in the carburetor
THEN the engine is getting gas.
“Askable” information: the information that makes up the premise of
a rule is not the conclusion of some other rule. For example, “The
engine is getting gas” is not askable.
“Askable” information: the information that makes up the premise of
a rule is not the conclusion of some other rule. For example, “The
engine is getting gas” is not askable.
Engine turns over
Working memory after considering rule 2
Rule 1: The engine is getting gas is not askable.
Rule 2: The engine does not turn over is askable.
Suppose the answer is fail.
Rule 3: fail
Rule 4: the premises are askable.
Suppose that the answers to both questions are true.
The engine is getting gas
Gas in fuel tank
Gas in carburetor
Engine turns over
Working memory after considering rule 4
First pass
8
The problem is spark
plugs
The engine is getting gas
Gas in fuel tank
Gas in carburetor
Engine turns over
Working memory after firing rule 1
Second pass
No more rule can fire and the search is completed
Matching the premises of rule 1
Fire rule 1
WM
The engine turns over
The engine turns over
The engine is getting gas
Gas in fuel tank
Gas in carburetor
Engine turns over
fail fail fail fire
First pass
Rule1 Rule2 Rule3 Rule4
The engine is getting gas
Gas in fuel tank
Gas in carburetor
Engine turns over
Second pass
The problem is spark plugs
The engine is getting gas
Gas in fuel tank
Gas in carburetor
Engine turns over
Rule1 Rule2 Rule3 Rule4
Halt with no more rules matching
Rule 1 fires
Breadth-first search
9
Rules and Expert Systems 17
Refinement on the breadth-first search
strategy
Opportunistic search
Whenever a rule fires to conclude new information,
control moves to consider those rules which have
the new information as a premise.
Rules and Expert Systems 18
Explanation in data-driven systems
Data-driven reasoning is much less “focused”
in its search.
The explanation available to the user at any
time in the search is quite limited.
10
Rules and Expert Systems 19
Backward chaining
Backward chaining is very appropriate to the
case that a single specific conclusion is to be
proved.
It is often to build an expert system by using
a rule-based system with backward chaining.
Rules and Expert Systems 20
Example 1
Rule 1:
IF the engine is getting gas, AND the engine will turn over,
THEN the problem is spark plugs.
Rule 2:
IF the engine does not turn over, AND the lights do not come on
THEN the problem is battery or cables.
Rule 3:
IF the engine does not turn over, AND the lights do come on
THEN the problem is the starter motor.
Rule 4:
IF there is gas in the fuel tank, AND there is gas in the carburetor
THEN the engine is getting gas.
11
Rules and Expert Systems 21
The problem is X
Working memory
Rule 1
Rule 2
Rule 3
Rule 4
Production rules
The engine is
getting gas.
The engine will
turn over
The problem is
spark plugs.
Working memory
Rule 1
Rule 2
Rule 3
Rule 4
Production rules
Rule 1 is fired
Gas in fuel tank.
Gas in carburetor.
The engine will
turn over
The problem is
spark plugs.
Rule 1
Rule 2
Rule 3
Rule 4
Rule 4 is fired
Do not match
with any rule
conclusions
Q: Is gas in fuel tank?
Q: Is gas in carburetor?
Q: Will the engine turn over?
Query the
user directly
“Askable” information: the information that makes up the
premise of a rule is not the conclusion of some other rule.
Rules and Expert Systems 22
Searching in and/or graph
and
or
12
Rules and Expert Systems 23
Explanation: why query
Q: Is gas in fuel tank?
yes
Q: Is gas in carburetor?
yes
Q: Will the engine turn over?
why
(why do you want to know whether the engine will turn over?)
Show the chain of rules and goals between the current goal and the
top goal.
Answer>It has been established that the engine is getting gas; therefore if
the engine will turn over, then the problem is spark plugs.
Rules and Expert Systems 24
Current goal
Top goal
The ‘why’ explanation.
13
Rules and Expert Systems 25
Explanation: how query
How the engine is getting gas
(how query)
Give a trace of the reasoning that leads to a goal.
Answer>This follows from rule 4:
if there is gas in the fuel tank, and there is gas in the carburetor then
the engine is getting gas.
留言
張貼留言