17
B. Cập nhật
Thêm có hại: mâu thuẫn
Bớt Dị thƣờng
Sửa bất lợi: dƣ thừa
___________________________________________________________________
Bài tập chương 2:
B i 1: Biểu diễn một cơ sở tri thức trong thực tế gồm 6 luật.
B i 2: Biểu diễn một cơ sở tri thức gồm 8 luật, xác định v xử lý các luật dƣ thừa.
B i 3: Biểu diễn một cơ sở tri thức gồm 8 luật, xác định v xử lý các mâu thuẫn.
18
Chương 3: Các kỹ thuật suy diễn và lập luận
3.1. Nhập môn
Động cơ, mô tơ hay máy suy diễn gồm 2 bộ phận chính:
- Cơ chế suy diễn (Processor) gồm:
+ Suy diễn tiến Inference (CT, KL, set of facts) và KQ: boolean
+ Suy diễn lùi R: set of rule
- Cơ chế cổ điển (control unit):
+ chọn hƣớng suy diễn (MACRO)
+ chọn luật
thƣờng có MẸO (heuristc metaknowledge)
+ phân rã CSTT SD phân tán
SD song song
+ Lọc (tinh)
(nhìn thấy cái n o không cần thiết thì loại, xác định cái n o đƣợc chọn trƣớc)
3.2. Phân rã CSTT
Fact Precedence Graph (FPG) = (F, A)
+ Đỉnh : tập các sự kiện
+ Cung: (a,b)
A
r: left
b
R ; a
left
USER
Động cơ
CSTT
Tình huống
Kernel
19
D: 1) a
b
2) b
c
3) c
e
4) c
d
5) d
e
f
6) b
h
7) f
h
g
Tập sự kiện:
F = { a, b, c, d, e, f, g, h} tách ra hai sự kiện:
F1 = { a, b, c} R1 = { a
b, b
c}
F2 = { e, d, f, g, h} R2 = { d
e
f, f
h
g}
R0 = {c
e, c
d, b
h}
F0 = {b, c, d, b, h}
Đây l một cách phân
rã CSTT
eval({F1, F2})
min
- Mô hình star
a b c
c
e d
f
h g
R1
R0
F0
R2
R4
R0
R1
R2
R3
20
- Nếu phân rã dựa trên tập luật l m gốc thì dẫn đến full condition
- Phân rã theo tập sự kiện hình sao.
3.3. Mô tơ suy diễn
A. Suy diễn tiến, lùi (nhắc lại)
1. Suy diễn tiến
tìm kiếm
VD: 1) a
b
2) b
c
3) c
e
4)c
d
GT = {a}
{a}f min {a,b} min {a,b,c} {a,b,c,d}
{a}
{a, b}
{a, b, c} {a, b, h}
{a, b, h, c}
A b
B c
C e
hed
hb
dc
ghf
r1
2,6 r2
3,4,6 r3
r1
r2
r6
(3,4,6)
(3,4)
.....
.....
.....
5) d
e
f
6) b
h
7) f
h
g
21
SUY DIỄN TIẾN
ĐỒ THỊ SUY DIỄN TIẾN
1) GT
2) T.gian (SK đã chứng minh)
3) THOẢ
T.Gian
T.Gian
{q}
r: left
q
r
thoa
4) Kết thúc
T.Gian
KL
5) VẾT
1) Đỉnh gốc
2) Nút
3) CUNG
T.Gian
T.Gian
T.gian = Tgian
{q}
4) Lá
5) Đƣờng đi
Chú ý:
- Nếu SDT theo vét cạn
độ phức tạp tƣơng ứng với quá trình tìm kiếm
trên đồ thị SD.
CSD trên(vecan)
Ctìm kiếmVC = 0(BH)
B: Branching (độ phân nhánh) v H l chiều cao của cây
2. Suy diễn lùi
tìm kiếm
{g} {f, h} {d, e, h}
ĐỒ THỊ SUY DIỄN LÙI ( And, or)
{g}
{f} {h}
{d} {e} {}
{c} {c} {a}
{b}
r
r1
f
r5
r7
r6
r4
r3
{a}