Bài giảng Hệ chuyên gia - Phan Huy Khánh - Chương 3: Máy suy diễn

tục áp dụng luật r
FB ←
FB ∪
RHF(r) ;
' Thêm vào FB các sự
kiện mới
RB ←
RB –
{ r
} ;
' Loại bỏ
luật r đã xử
lý 
Call
CYCLE(RB)
;
Else
Call
CYCLE(R1)
;
Return
;
46/70
Forward chaining algorithm
47/70
Forward chaining Example 2.
KBBKBKKB
WMWMWM
Match Fire
WM
A B C D E
X
Match Fire
A B C D E
LX
Match Fire
A C D E
YL
B
X
Match Fire
A C D E
ZY
B
LX
Cycle 1 Cycle 2 Cycle 3
X Ÿ
B Ÿ
E Y
ZY ∧
D
LC
L Ÿ
M
A X
N
X Ÿ
B Ÿ
E Y
ZY Ÿ
D
LC
L Ÿ
M
A X
N
X Ÿ
B Ÿ
E Y
ZY Ÿ
D
LC
L Ÿ
M
A X
N
X Ÿ
B Ÿ
E Y
ZY Ÿ
D
LC
L Ÿ
M
A X
N
48/70
Example 3. Diagnosing car problems
a Rule 1: 
IF
the engine is getting gas
AND the engine will turn over
THEN the problem is spark plugs
a Rule 2:
IF
the engine does not turn over
AND the lights do not come on
THEN the problem is battery or cables
a Rule 3:
IF
the engine does not turn over
AND the lights do come on
THEN the problem is the starter motor
a Rule 4:
IF
there is gas in the fuel tank
AND there is gas in the carburettor
THEN the engine is getting gas
49/70
Rule 1
Rule 2
Rule 3
Rule 4
l
l
l
l
the engine
 turns over
i
Rule 1
Rule 2
Rule 3
Rule 4
l
l
l
l
Working space
Working space
a Facts
The engine is getting gas
50/70
The engine is
 getting gas 
There is gas
 in the fuel tank
 There is gas
 in the carburettor
 The engine
 turns over
i i
 i
i
 i l
i
 i
i
Working space
Rule 1
Rule 2
Rule 3
Rule 4
l
l
l
l
51/70
Example 4.
a Rulesbase:
1.
K, L, M
→
I
2.
I, L, J
→
Q
3.
C, D, E
→
B
4.
A, B
→
Q
5.
L, N, O, P
 →
Q
 6.
C, H
→
R
7.
R, J, M
→
S
8.
F, H
→
B
9.
G
→
F
a Factsbase:
A, C, D, E, G, H, K
l
Đồ
thị
VÀ-HOẶC 
(And-Or Tree)
ị
=
G
E
D
C 
==
= = = =
=
=
SQ
H
F C
H
M L
K
O N
P
L
B
A J
L J R
M
I
52/70
Example 4.
Kết quả
suy diễn
a Xây dựng đồ thị con VÀ-HOẶC từ đồ thị VÀ-HOẶC trên đây
V Tìm được Q khi các sự kiện A, C, D và E được thiết lập 
B
A
E
D
C 
=
=
Q
=
G
E
D
C 
==
= = = =
=
=
SQ
H
F C
H
M
L
K
O N
P
L
B
A
J
L J R
M
I
53/70
Exercise 1.
a Rulesbase:
1.
B, D, E
→
F
2.
G, D
→
A
3.
C, F
→
A
4.
B
→
X
5.
D
→
E
6.
X, A
→
H
7.
C
→
D
8.
X, C
→
A
9.
X, B
→
D
a Factsbase:
B, C
l
a Yêu cầu :
V Vẽ đồ thị và-hoặc
V Áp dụng thuật toán suy diễn tiến
để tìm kết quả H
V Có nhận xét gì ?
54/70
Exercise 2.
a Rules Base:
R1:
IF management competence is good
AND External credit rating is fair
AND Bank's credit rating is 
marginal
 THEN Loan is rejected
R2:
IF Loan type is seasonal
AND Profitability rating is high
AND Solvency rating is low
THEN Bank's credit rating is 
marginal
 R3:
IF Cash/current liabilities > 0.1
AND Tentative solvency rating is 
low
 THEN Solvency rating is low
l
 i 
 l i i i f i
 ' i i i 
i l
 i j
 i l
 fi ili i i i
 l i i l
 ' i i i 
i l
 li ili i .
 i l i i 
l
 l i i l
a Facts Base:
Bank's credit rating
UNKNOWN
Cash/current liabilities
0.18
External credit rating
FAIR
Loan
SEASONAL
Loan type
UNKNOWN
Management competenceUNKNOWN
Profitability rating
HIGH
Solvency rating
UNKNOWN
Tentative solvency rating
LOW
' i i
 li ili i
.
l i i
fi ili i
 l i
 i l i
55/70
Example knowledge base contd.
... it is a crime for an American to sell weapons to hostile nations:
American(X)
∧
Weapon(Y)
∧
Sells(X,Y,Z) ∧
Hostile(Z)
→
Criminal(X)
Nono
…
has some missiles, i.e., ∃X
Owns(Nono,X)
∧
Missile(X):
Owns(Nono,M1) and Missile(M1)
…
all of its missiles were sold to it by Colonel West
Missile(X)
∧
Owns(Nono,X)
→
Sells(West,X,Nono)
Missiles are weapons:
Missile(X)
→
Weapon(X)
An enemy of America counts as "hostile“:
Enemy(X,America) →
Hostile(X)
West, who is American …
American(West)
The country Nono, an enemy of America …
Enemy(Nono,America)
56/70
Forward chaining proof
American(West)i ( )
Hostile(Nono)il ( )
Criminal(West)i i l( )
Weapon(M1)( )
Missile(M1)i il ( ) Owns(Nono,M1)( , ) Enemy(Nono,America)( , i )
Sells(West,M1,Nono)ll ( , , )
57/70
Phương pháp suy diễn lùi
a Phương pháp suy diễn lùi :
V Tiến hành các lập luận theo chiều ngược lại
(so với phương pháp suy diễn tiến)
V Đầu vào có dạng một câu hỏi «Cho biết giá trị thuộc tính đích (goal) A ?»
V MSD suy diễn để đưa ra tình huống trả lời gồm các sự kiện là cơ sở của giả
thuyết đã cho gồm để gán giá trị cho thuộc tính A
a Ví dụ :
V Nếu ai đó vào nhà mà cầm áo mưa và áo quần bị ướt (hậu quả)
thì giả thuyết là trời mưa (nguyên nhân)
V Để củng cố giả thuyết này,
ta sẽ hỏi người đó xem có phải trời mưa không ?
V Nếu người đó trả lời có
thì giả thuyết trời mưa đúng và trở thành một sự kiện
V Nghĩa là trời mưa nên phải cầm áo mưa và áo quần bị ướt
58/70
Ý tưởng thuật toán suy diễn lùi
a Với mỗi thuộc tính đã cho, người ta định nghĩa nguồn của nó :
V Nếu thuộc tính xuất hiện như là tiền đề của một luật (phần đầu 
của luật), thì nguồn sẽ thu gọn thành một câu hỏi
V Nếu thuộc tính xuất hiện như là hậu quả của một luật (RHS),
thì nguồn sẽ là các luật mà trong đó, thuộc tính là kết luận
V Nếu thuộc tính là trung gian, xuất hiện đồng thời như là tiền đề và 
như là kết luận, khi đó nguồn có thể là các luật, hoặc có thể là các 
câu hỏi mà chưa được nêu ra
V Nếu mỗi lần với câu hỏi đã cho, người sử dụng trả lời hợp lệ, giá trị
trả lời này sẽ được gán cho thuộc tính và xem như thành công
V Nếu nguồn là các luật, MSD sẽ tìm giá trị các thuộc tính thuộc tiền 
đề (LHS) bằng cách xét lần lượt các luật có thuộc tính đích xuất 
hiện ở kết luận
V Nếu các luật thoã mãn, thuộc tính kết luận sẽ được ghi nhận
59/70
Backward Chaining
a Conclude from "B" and "A implies B" to "A" 
a Example:
The dress is wet
 If it is raining, the dress is wet
 --------------------------------------
 It is raining
B
 A
→
B
A
60/70
Backward Chaining
61/70
Thuật toán suy diễn lùi
a Definitions :
FB, RB, R1 ⊆
RB
Q : Sự
kiện đưa vào xử
lý 
a Algorithme :
Procedure
DEDUCE (Q)
If
Q ∈
BF Then
Write " Success"
;
Else
Push BR, BF
;
IP ≠
1 ;
Call
CYCLE(BR, BF)
;
Return;
62/70
Thuật toán suy diễn lùi
Procedure
CYCLE(ER, EF)
Var
: ER, EF, r
; ' Các biến làm việc địa phương
If
ER = ∅
Then
IP ≠
IP -1
; ' Lấy một luật ở đỉnh Stack
If
IP = 0 Then
Write " Failure"
; Return;
Else
ER ≠
Luật ở đỉnh Stack chưa xét
EF ≠
Các sự
kiện
ở đỉnh Stack;
Call
CYCLE(ER, EF) ; Return;
r ≠
CHOOSE(r, ER)
; ' Chọn một luật
ER ≠
ER –
{ r }
; ' Loại bỏ
luật đã xét ở
ER
If
LHS(r) ∈
EF Then
If
RHF(r) ∈
Q Then
Write " Success"
; Return;
Else
Push (EF ∪
RHF(r)), BR
; ' (IP ≠ IP +1)
Đánh dấu màu đỏ
phần tử ngay dưới đỉnh Stack;
Đánh dấu màu đỏ
cho luật r ở đỉnh
Đánh dấu màu xanh cho luật r tại đỉnh -
1
;
ER ≠
Các luật ở đỉnh chưa đánh dấu. Thông thường là
màu đỏ;
EF ≠
Các sự
kiện
ở đỉnh Stack ;
Call
CYCLE(ER, EF)
; Return;
Call
CYCLE(ER, EF)
; Return;
63/70
Example 4. Backward Chaining
a Rulesbase:
1.
K, L, M
→
I
2.
I, L, J
→
Q
3.
C, D, E
→
B
4.
A, B
→
Q
5.
L, N, O, P
→
Q
6.
C, H
→
R
7.
R, J, M
→
S
8.
F, H
→
B
9.
G
→
F
a Factsbase:
A, C, D, E, G, H, K
a Question (Goal):
Q
l
,
 .
, ,
 .
,
 .
, , ,
 .
,
 .
, , 
 .
, 
 .
i l
Đồ
thị
VÀ-HOẶC 
(And-Or Tree)
ị
 =
G
E
D
C 
==
= = = =
=
=
SQ
H
F C
H
M L
K
O N
P
L
B
A J
L J R
M
I
64/70
Đồ
thị
Và-Hoặc thiết lập Q
Q
E
D
C 
=
= =
=
M L
K
B
A J
L
I
Khởi động 1i 
Khởi động 2i 
Khởi động 3i 
Khởi động 4i 
Luật 2 
Luật 1 
Luật 4 
Luật 3 
65/70
Áp dụng thuật toán suy diễn lùi
Q
A C D E G H K
I J L
A C D E G H K 
B
A C D E G H K
M J L
A C D E G H K 
A C D E G H K
Luật 1 Luật 3
 (khởi động 2)
(khởi động 4)
Luật 2
Luật 4
(khởi động 1)
(khởi động 3)
Failure
Success
66/70
Exercise
a Áp dụng thuật toán suy diễn lùi cho ví dụ Colonel West 
67/70
Data-driven ×
Goal-driven
here seen holidayli
absent
buildingil ihome
finei sicki
data driven
goal driven
68/70
Data-driven ×
Goal-driven
a Goal Driven (backward chaining) ~ blood diagnostic, 
theorem proving
V Limited number of goal hypothesis
V Data shall be acquired, complicated data about the object
V Less operators to start with at the goal rather than at the data
a Data Driven (forward chaining) ~ configuration, interpretation,
V reasonable set of input data
V data are given at the initial state
V huge set of possible hypothesis
a Taxonomy of rules, meta-rules, priorities, …
69/70
Forward or Backward Reasoning?
a Four major factors
a More possible start states or goal states?
Move from smaller set of states to the larger
Assume you are at home and you need some bread. You've one initial 
state and many possible goal states where to get bread from 
(Sainsbury's, Tesco, Aldi, Morrison, ASDA, CornerShop, Bakery). That is, 
in such a situation it is probably a good approach to search in forward 
chaining fashion, since you have many chances to hit a goal. If you 
choose backward chaining you would have to commit to one of the 
goals, e.g. the Bakery and then search backwardly how the get there 
from home.
If, however, there are 5 people Alice, Bob, Claire, Dora, and Edgar at 5 
different places A, B, C, D, and E, and one of them should get the Tesco 
home brand of ketchup, then it would be better to start backward
chaining from the Tesco store and stop search when one of the places 
A, B, C, D, or E is reached
70/70
Forward or Backward Reasoning? (Cont'd)
a Has program to justify reasoning?
V Prefer direction that corresponds more closely to the way 
users think
aWhat kind of events triggers problem-solving?
V If it is arrival of a new fact, forward chaining makes sense
V If it is a query to which a response is required, 
backward chaining is more natural. 
a In which direction is branching factor greatest?
V Go in direction with lower branching factor