27
Nhận xét:
#VET +Complexity
h
ˆ
x m
ii)Đồ thị RPG(Rule Precedence Graph)
RPG=(R,A)
Trong đó R: Tập các đỉnh
A: l tập các cạnh sao cho:
r
r’, r:left
q
q
left’
r’:left
q’
VD:Xây dựng đồ thị RPG cho ví dụ trên ta có:
*Xây dụng h m
h
ˆ
2 (r)?
h
ˆ
2 (r)=?
RKL={r:left
q/q
KL}
R
h
ˆ
2 (r)=kcRPG(r,RKL)
Chọn r sao cho
h
ˆ
2 (r)
min
Xét ví dụ sau:
GT={a b R}, KL={r}
{a,b,r}7,8
{a b R A}8
{a b R A B}4
{a b R A B C}1,13
{a b R A B C
c}9,10,11
……..KL
h
ˆ
2 (r7)=kcRPG(r7, r16)=3
r5 r13
r6 r4 r1 r+9
r7 r2 r10
r8 r3 r11 r16
r14
r12 r15
28
h
ˆ
2 (r8)=kcRPG(r8, r16)=3
h
ˆ
2 (r1)=kcRPG(r1, r16)=2
h
ˆ
2 (r13)=kcRPG(r13, r16)=1
h
ˆ
2 (r15)=kcRPG(r15, r16)=
h
ˆ
2 (r10)=kcRPG(r10, r10)=1
h
ˆ
2 (r11)=kcRPG(r11, r16)=1
h
ˆ
2 (r14)=kcRPG(r14, r16)=1
h
ˆ
2 (r16)=kcRPG(r16, r16)=0
2. Suy diễn lùi
Đồ thị FPG
Tình huống đụng độ khi suy diễn lùi:
Goal= Tập những sự kiện cần chứng minh; ban đầu Goal=KL
Xét f
Goal. Có nhiều luật suy ra f. Ta chọn luật bằng các thử sai v quay lui. Để
tránh phải quay lui ta cần chọn luật nhƣ thế n o.
Nhắc lại các cách chọn có quay lui:
+ cứng nhắc: - Chỉ số max: chọn luật có chỉ số lớn nhất trong tập luât thoả
- Chỉ số min: chọn luật có chỉ số nhỏ nhất trong tập luât thoả
+ mềm dẻo :
h
ˆ
(r)
max/min: Đánh giá tốt hay không dựa v o quay lui, c ng
nhiều cáng kém
VD:
GT={a b R}
{S}12,13,14
{a b c p}
{a b mb p}
…….
* Cách tính
h
ˆ
3(r)
h
ˆ
3(r)=
h
ˆ
3(left
f)=kc(GT,left)
Chọn r:
h
ˆ
3(r)
min
Kc(GT, left)=max(GT,a)
a
left
Chọn r13
29
Kc(GT, left)=max(b,a)
b
GT
VD: GT={a b R}, KL={S}
{S}12,13,14
{a b c p}
{a b mb p}
…….
h
ˆ
3(r12)=kc(a b R,a ha)=
h
ˆ
3(r13)=kc(a b R,a a b C)= 2
h
ˆ
3(r14)=kc(a b R,a b c p)= 4
h
ˆ
3(r6)=kc(a b R,b hc)=
h
ˆ
3(r17)=kc(a b R,a R)= 0
h
ˆ
3(r5)=kc(a b R,a hc)=
h
ˆ
3(r8)=kc(a b R,b R)= 0
ii) Đồ thị RPG.
* Cách tính
h
ˆ
4(r)?
h
ˆ
4(r)=kcRPG(RGT , r)
Chọn r:
h
ˆ
4(r)
min
RGT={r: left
q/left
GT}
VD: GT={a b R} KL={S}
{S}12,13,14
{a b c p}
{a b mb p}
…….
Tính
h
ˆ
4(r) ta có:
…….
D. Hạn chế các ứng viên trong quá trình suy diễn
1. Suy diễn tiến
Giả sử xét tại một thời điểm trong quá trình suy diễn :
+ Thời gian
+ THOẢ= LỌC(R, TGian)={r: left
q/ left
TGian}
THOẢ’ THOẢ . Khi đó lựa chọn trong THOẢ’ bằng phƣơng pháp vét cạn hay
heuristic.
Chọn r13
Chọn r7
Chọn r8
30
1. Suy diễn lùi
Xét 1 sự kiện thuộc Goal.
h
ˆ
() =
/min XACDINH (f) = {r; left
f}
= 0/max Kĩ sƣ tri thức
XACDINH’(f)
XACDINH (f)
Kết luận: Nâng cao hiẹu quả quá trình suy diễn
- Chọn hƣớng suy diễn
- Chọn luật
- Phân tách cơ sở tri thức (CSTT)
- Hạn chế ứng viên
3.4. Biểu diễn TRI THỨC bằng LOGIC vị từ và SUY DIỄN
Luật ri P1 (…)
P2 (…)
……
Pn (…)
q (…)
Pi (…) l vị từ / predicate: l những phát biểu có phụ thuộc v o các biến
q (…) hay tham số
VD: Các định lý hình học
1.tđ(U,XY)
tđ(V,XZ)
SS(UV,XZ)
2.SS(UV,XY)
SS(UV,ST)
SS(ST,XY)
3.SS(XY,UV)
SS(XZ,UV)
Thang(X,Y,Z)
4.SS(XY,UV)
Thang(X,Y,Z)
SS(UV,XZ)
tđ(U,XY)
tđ(U,YX)
SS(XY,UV)
SS(UV,XY)
SS(XY,UV)
SS(VU,YX)
A. Suy diễn tiến
GT: tđ (P, AB); tđ (Q, AC)
tđ (I, BQ); tđ (J, CP)
tđ (E, CQ)
KL { SS (PS, BC)
Control
mechanisms
Explicit
Implici t
A
P
Q
B
C
I
J
31
B
'
1
: TG0 = GT
THOA = {(r1,
1), (r1,
2), (r1,
3), (r1,
4)}
1 = {A/X; B/Y; C/Z; P/U; Q/V}
2 = {C/X; Q/Y; P/Z; E/U; J/V}
3 = ...
4 = ....
Chọn (r1,
1)
TG1 = TG0
{SS (UV, YZ),
1} = TG0
{SS (PQ, BC)}
B
'
2
: TG1 =
THOA = {(r1,
2), (r1,
3), (r1,
4)
….
Vđề: L m nhƣ thế n o để xác định (ri,
i)
B. Suy diễn lùi.
Nói chung suy diễn tiến v suy diễn lùi đều giống nhƣ nhau trong logic mệnh đề vì
đều l quá trình hợp nhất (Unification)
Để rõ hơn ta hãy xét ví dụ sau:
GT tđ(P,AB), tđ(Q,AC), tđ(I,PQ), tđ(J,CP), tđ(E,QC)
KL SS(IJ, BC)
Ta áp dụng thủ tục suy diễn lùi, nhƣng co khó khăn l khi không tiếp tục đƣợc ta lại
phải quay lui.Từ đây ta có thể đƣa ra nhận xét sau:
Sự giống v khác nhau giữa suy diễn lùi của logic vị từ v suy diễn Prolog
- Giống nhau: cả trong prolog cv logic vị từ đều có phép hợp nhất v quá trình
thử sai
- Khác nhau: Tính chất trong prolog l chúng minh suy ra điều vô lý, còn suy
diễn lùi l suy ra goal=0. Cơ chế của prolog l theo chỉ số min v đi từ trái
sang phải. Còn trong logic vị từ thì có thể áp dụng hất mọi cacchs đi thông
thƣờng: Trai, phải v ngƣợc lại hay l trên duới v ngƣợc lại.