Transcript Teknik Asas Pengkelasan Corak

Rulebase Expert System and Uncertainty
Rule-based ES
• Rules as a knowledge representation
technique
• Type of rules :- relation, recommendation,
directive, strategy and heuristic
ES development tean
Project manager
Domain expert
Knowledge engineer
End-user
Programmer
Structure of a rule-based ES
External
database
External program
Knowledge base
Database
Rule: IF-THEN
Fact
Inference engine
Explanation facilities
User interface
User
Developer interface
Knowledge engineer
Expert
Structure of a rule-based ES
• Fundamental characteristic of an ES
– High quality performance
• Gives correct results
• Speed of reaching a solution
• How to apply heuristic
– Explanation capability
• Although certain rules cannot be used to justify a
conclusion/decision, explanation facility can be used
to expressed appropriate fundamental principle.
– Symbolic reasoning
Structure of a rule-based ES
• Forward and backward chaining inference
Database
Fact: A is x
Fact: B is y
Match
Fire
Knowledge base
Rule: IF A is x THEN is y
Conflict Resolution
• Example
– Rule 1:
IF
the ‘traffic light’ is green
THEN the action is go
– Rule 2:
IF
the ‘traffic light’ is red
THEN the action is stop
– Rule 3:
IF
the ‘traffic light’ is red
THEN the action is go
Conflict Resolution Methods
• Fire the rule with the highest priority
– example
• Fire the most specific rules
– example
• Fire the rule that uses the data most recently
entered in the database - time tags attached
to the rules
– example
Uncertainty Problem
• Sources of uncertainty in ES
–
–
–
–
Weak implication
Imprecise language
Unknown data
Difficulty in combining the views of different
experts
Uncertainty Problem
• Uncertainty in AI
–
–
–
–
Information is partial
Information is not fully reliable
Representation language is inherently imprecise
Information comes from multiple sources and it
is conflicting
– Information is approximate
– Non-absolute cause-effect relationship exist
Uncertainty Problem
• Representing uncertain information in ES
–
–
–
–
–
–
–
Probabilistic
Certainty factors
Theory of evidence
Fuzzy logic
Neural Network
GA
Rough set
Uncertainty Problem
• Representing uncertain information in ES
–
–
–
–
–
–
–
Probabilistic
Certainty factors
Theory of evidence
Fuzzy logic
Neural Network
GA
Rough set
Uncertainty Problem
• Representing uncertain information in ES
– Probabilistic
• The degree of confidence in a premise or a
conclusion can be expressed as a probability
• The chance that a particular event will occur
P( X ) 
Num berof outcom esfavoringthe occurenceof
Total num berof events
Uncertainty Problem
• Representing uncertain information in ES
– Bayes Theorem
• Mechanism for combining new and existent
evidence usually given as subjective probabilities
• Revise existing prior probabilities based on new
information
• The results are called posterior probabilities
Num berof outcom esfavoringthe occurenceof
P( X ) 
Total num berof events
Uncertainty Problem
• Bayes theorem
P( A / B) 
P( B / A * P( A))
p( B / A) P( A)  P( B / not A) * P(not A)
– P(A/B) = probability of event A occuring, given that B
has already occurred (posterior probability)
– P(A) = probability of event A occuring (prior
probability)
– P(B/A) = additional evidence of B occuring, given A;
– P(not A) = A is not going to occur, but another event is
P(A) + P(not A) = 1
Uncertainty Problem
• Representing uncertain information in ES
–
–
–
–
–
–
–
Probabilistic
Certainty factors
Theory of evidence
Fuzzy logic
Neural Network
GA
Rough set
Uncertainty Problem
• Representing uncertain information in ES
– Certainty factors
• Uncertainty is represented as a degree of belief
• 2 steps
– Express the degree of belief
– Manipulate the degrees of belief during the use of
knowledge based systems
• Based on evidence (or the expert’s assessment)
• Refer pg 74
Certainty Factors
• Form of certainty factors in ES
IF <evidence>
THEN <hypothesis> {cf }
• cf represents belief in hypothesis H given that
evidence E has occurred
• Based on 2 functions
– Measure of belief MB(H, E)
– Measure of disbelief MD(H, E)
• Indicate the degree to which belief/disbelief of
hypothesis H is increased if evidence E were
observed
Certainty Factors
• Uncertain term and their intepretation
Term
Definitely not
Almost certainly not
Probably not
Certainty Factor
-1.0
-0.8
-0.6
Maybe not
Unknown
Maybe
-0.4
-0.2 to +0.2
+0.4
Probably
Almost certainly
Definitely
+0.6
+0.8
+1.0
Certainty Factors
• Total strength of belief and disbelief in a
hypothesis (pg 75)
MB( H , E )  MD( H , E )
cf 
1  min[MB( H , E ), MD( H , E )]
Certainty Factors
• Example : consider a simple rule
IF A is X
THEN B is Y
– In usual cases experts are not absolute certain
that a rule holds
IF A is X
THEN B is Y {cf 0.7};
B is Z {cf 0.2}
• Interpretation; how about another 10%
• See example pg 76
Certainty Factors
• Certainty factors for rules with multiple
antecedents
– Conjunctive rules
• IF <E1> AND <E2> …AND <En> THEN <H> {cf}
• Certainty for H is
cf(H, E1 E2  … En)= min[cf(E1), cf(E2),…, cf(En)] x cf
See example pg 77
Certainty Factors
• Certainty factors for rules with multiple
antecedents
– Disjunctive rules rules
• IF <E1> OR <E2> …OR <En> OR <H> {cf}
• Certainty for H is
cf(H, E1 E2  … En)= max[cf(E1), cf(E2),…, cf(En)] x cf
See example pg 78
Certainty Factors
• Two or more rules effect the same hypothesis
– E.g
– Rule 1 :
IF
A is X THEN C is Z {cf 0.8}
IF
B is Y THEN C is Z {cf 0.6}
Refer eq.3.35 pg 78 : combined certainty factor
Uncertainty Problem
• Representing uncertain information in ES
–
–
–
–
–
–
–
Probabilistic
Certainty factors
Theory of evidence
Fuzzy logic
Neural Network
GA
Rough set
Theory of evidence
• Representing uncertain information in ES
• A well known procedure for reasoning with
uncertainty in AI
• Extension of bayesian approach
• Indicates the expert belief in a hypothesis given a
piece of evidence
• Appropriate for combining expert opinions
• Can handle situation that lack of information
Rough set approach
• Rules are generated from dataset
– Discover structural relationships within
imprecise or noisy data
– Can also be used for feature reduction
• Where attributes that do not contributes towards the
classification of the given training data can be
identified or removed
Rough set approach:Generation of Rules
[E1, {a, c}],
[E2, {a, c},{b,c}],
[E3, {a}],
[E4, {a}{b}],
[E5, {a}{b}]
Reducts
Class
a
E1
E2
E3
E4
E5,1
E5,2
1
1
2
2
3
3
b
2
2
2
3
5
5
c
3
1
3
3
1
1
dec
1
2
2
2
3
4
Equivalence Classes
a1c3  d1
a1c1  d2,b2c1  d2
a2  d2
b3  d2
a3  d3,a3  d4
b5  d3,b5  d4
Rules
Rough set approach:Generation of Rules
Class
Rules
E1
E2
E2
E3, E4
E4
E5
E5
E5
E5
a1c3  d1
a1c1  d2
b2c1  d2
a2  d2
b3  d2
a3  d3
a3  d4
b5  d3
b5  d4
Membership
Degree
50/50 = 1
5/5 = 1
5/5 = 1
40/40 = 1
10/10 = 1
4/5 = 0.8
1/5 = 0.2
4/5 = 0.8
1/5 = 0.2
Rules Measurements : Support
Given a description contains a conditional part  and the
decision part , denoting a decision rule   . The support
of the pattern  is a number of objects in the information
system A has the property described by .
sup port( )  
The support of  is the number of object in the IS A that have
the decision described by .
sup port(  )  
The support for the decision rule    is the probability of
that an object covered by the description is belongs to the
class.
sup port (   )  sup port(   )
Rules Measurement : Accuracy
The quantity accuracy (  ) gives a measure of how
trustworthy the rule is in the condition . It is the probability
that an arbitrary object covered by the description belongs to the
class. It is identical to the value of rough membership function
applied to an object x that match . Thus accuracy measures the
degree of membership of x in X using attribute B.
Accuracy(   ) 
sup port (   )
sup port ( )
Rules Measurement : Coverage
Coverage gives measure of how well the pattern 
describes the decision class defined through . It is a
probability that an arbitrary object, belonging to the class
C is covered by the description D.
Coverage(   ) 
sup port (   )
sup port (  )
Complete, Deterministic and Correct Rules
The rules are said to be complete if any object
belonging to the class is covered by the description
coverage is 1 while deterministic rules are rules with
the accuracy is 1. The correct rules are rules with
both coverage and accuracy is 1.