Bài giảng Trí tuệ nhân tạo - Chương 4: Tri thức và suy diễn - Lê Thanh Hương

1Chương 4 
Tri thức và suy diễn
Lê Thanh Hương
Khoa CNTT - ĐHBK HN
1
4.1. Tri thức là gì?
• Dữ liệu và Tri thức: là những dạng khác nhau 
của thông tin nên khó phân biệt rạch ròi
Tri thức
- ký hiệu tượng trưng
- tản mạn
- cấu trúc phức hợp
Dữ liệu
- số
- có cấu trúc
- cấu trúc đơn giản
2
- VD: Đông y:
- hâm hấp sốt
- mạch nhanh/chậm
- VD: Tây y:
- t0 390
- mạch 75
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Phân loại tri thức
a Tri thức mô tả: what?. 
– về tình huống (GT + KL): sự kiện
– về lĩnh vực: luật nếu  thì
3Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Phân loại tri thức
b. Tri thức thủ tục: how?
– Modus Ponens 
– Modus Tollens
Tri thức cũ về tình huống --------→ Tri thức mới về t/huống
Hiểu biết về lĩnh vực
Modus Ponens Modus Tollens
4
A, A →B A →B, ¬B
B ¬A 
• Ví dụ: Trán rộng →Thông minh
Bình: trán rộng ⇒ Bình thông minh
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
2Phân loại tri thức
c Tri thức điều khiển: heuristic. 
– Chọn hướng suy diễn: tiến, lùi, hỗn hợp
– Chọn luật áp dụng: đảm bảo đủ, không 
thừa, có cấu trúc, ngắn gọn
– Vẽ hình phụ
5Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Ví dụ 1: Chứng minh bài toán hình học
• Mô tả? 
• Thủ tục?
• Điều khiển?
GT, KL, hình vẽ + Định lý, tính chất
Áp dụng định lý đường trung bình vào tam giác ABC ta có
Nghĩ→ SD tiến, lùi; Viết → SD tiến 
Cho X = 600, Y = 600. CM XY = XZ, XY = YZ
Mô tả: 
• Sự kiện: Bnhau(XY,UV) Bang(X,Y) Banggoc(X,a)
• Luật:
– Bnhau(XY,UV) ⇒ bnhau(UV,XY)
– Bnhau(XY,UV)⇒ bnhau(XY,VU)
X
Y Z
60
60
6
– Bang(Y,Z) ⇒ bnhau(XY,XZ)
– Bnhau(XY,UV) ∧ bnhau(UV,ST) ⇒ bnhau(XY,ST)
– ???
• Ban đầu: banggoc(X,60), banggoc(Y,60)
• Đích: bnhau(XY,XZ), bnhau(XY,YZ)
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Ví dụ 2
H là 1 thỏ H (H )• arry con are arry
• Tom là 1 con rùa Tortoise(Tom)
• Thỏ chạy nhanh hơn rùa
),()()(, yxOutrunsyTortoisexyHarex →∧∀
7
• Harry chạy nhanh hơn Tom?
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Tom và Harry
Tri thức mô tả:
• Giả thiết dưới dạng phép And 
• Luật
• Kết luận
)()( TomTortoiseHareHarry ∧
),()()( TomHarryOutrunsTomTortoiseHarryHare →∧
)( THO t
8
Tri thức thủ tục?
Tri thức điều khiển?
, omarryu runs
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
3Bản chất tri thức chuyên gia
Làm sao để chuyển tri thức từ chuyên gia con 
ời à á Æ kỹ ử lý t i thứ
lĩnh vực 
chuyên môn
tin học
ch/gia đầu ngành giỏi ε1 ∼ 0
ngư v o m y sư x r c
9
lập trình viên ε2 ∼ 0 giỏi
ksư xử lý tri thức khá khá
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Biểu diễn tri thức
Có nhiều cách biểu diễn tri thức.
GT, KL → sự kiện → mệnh đề, vị từ → đỉnh
R → luật → mệnh đề, vị từ, sản xuất → cung ngữ nghĩa
1. BDTT = logic
2. BDTT = luật sản xuất
3 BDTT = mạng ngữ nghĩa
10
. 
4. BDTT = frame
5. BDTT = bộ 3 Object – Attribute - Value
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
BDTT = logic
• BDTT = logic mệnh đề 
– Tri thức mô tả:
• Các mệnh đề p, q, r, 
• Các luật suy diễn (đưa về dạng chuẩn Horn)
p1 ∧ p2 ∧ ∧ pn ⇒ q
– Tri thức thủ tục: 
11
• modus ponens: {A, A →B} → {A,B}
• modus tollens: {A →B, ¬B} → {¬A, ¬B}
– Tri thức điều khiển: tiến, lùi
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Ví dụ
• Nếu trời đẹp thì đi chơi.
p q
• Nếu đi chơi và có tiền và có thời gian thì đi Hồ Tây.
q s t u
• Nếu đi Hồ Tây và có tiền và có thời gian thì đi Nhật Tân.
u s t v
• Nếu đi Nhật Tân thì mời Lâm
12
 .
v w
• Nếu mời Lâm thì mời bạn Lâm.
w x
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
4BDTT = luật sản xuất
Các luật sản xuất có dạng:
• Nếu điều kiện 1
. . . . . 
và điều kiện m
• thì kết luận 1 và  và kết luận n
• Trong logic mệnh đề hay vị từ, đk1đkm, kl1kln là 
những biểu thức logic, còn cặp nếuthì thì ⇔ dấu →
13
• Trong nguyên tắc dịch
– one → một
– one → người ta
– one → cái
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
BDTT = mạng ngữ nghĩa
• Mạng ngữ nghĩa là một đồ thị định hướng 
G=(N,A), trong đó
– N - tập các đối tượng, các sự kiện hay các khái 
niệm cụ thể (đỉnh)
– A - tập các mối liên hệ giữa các cặp đối tượng, sự 
kiện hay khái niệm (cung)
– A = {(x,y) | x,y ∈ N} = ∪ {(x,y) | x Ri y}
14
Ri là 1 quan hệ nào đó trên tập N
• VD: Giải bài toán lượng giác: cho biết a,b,ma. 
Tìm hc
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
BDTT = frame
• Là 1 dẫn xuất của BDTT = mạng ngữ nghĩa, là cơ sở 
của phương pháp xử lý thông tin kiểu hướng đối tượng
• Phương pháp BDTT = logic và mạng ngữ nghĩa mang
mạng 
ngữ nghĩa
frame (tri thức 
hướng đối tượng)
đặc trưng mô tả
• Phương pháp BDTT = luật sản xuất : thủ tục
• Phương pháp BDTT = frame kết hợp mô tả và thủ tục
15
thực thể đỉnh đối tượng (object)
quan hệ cung phân cấp (hierachy)
VD: 
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
BDTT = bộ 3 
Object – Attribute - Value
• VD: 
– (bồ câu, là, chim)
– (bồ câu, biết, ăn) ⇔ mạng ngữ nghĩa
– (bồ câu, biết, bay)
16
• Hạn chế: chỉ thể hiện được những quan 
hệ “=“, khó khăn khi biểu diễn ≥, ≤, 
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
5Các phương pháp chứng minh
• Chứng minh sử dụng phương pháp tìm kiếm 
• Hợp giải (kỹ thuật chứng minh)
• Suy diễn
– Sinh các câu mới từ các câu cũ
– Chứng minh = áp dụng các luật suy diễn. Có thể 
ử d l ật diễ h á t á tử t
17
s ụng u suy n n ư c c o n rong 
phương pháp tìm kiếm chuẩn
– Thường đòi hỏi chuyển các câu sang dạng chuẩn 
Horn
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Kỹ thuật CM Suy diễn
BT = GT + KL
GT → KL
CM
BT = GT + KL
GT → KL
R
18
GT + ¬KL → >< GT + R → KL
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Suy diễn
• Dạng chuẩn Horn
CSTT = tập các câu ở dạng chuẩn Horn
Câ H– u orn = 
• các ký hiệu mệnh đề 
• biểu thức kết hợp các ký hiệu ⇒ ký hiệu 
– Ví dụ
C ∧ (B ⇒ A) ∧ (C ∧ D ⇒ B)
• Modus Ponens (cho dạng chuẩn Horn):
β
19
α1,  ,αn, α1 ∧ ∧ αn⇒
β
• Có thể dùng cho suy diễn tiến và suy diễn lùi
• Các thuật toán này có độ phức tạp tuyến tính.
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Suy diễn đối với logic mệnh đề
Bài toán: Cho 1 CSTT R={r1 r } , , n , 
ri là luật, ri có dạng p1∧∧pm→q
Ngữ nghĩa:
– Nếu p1 đúng và  và pm đúng
– thì q đúng
• Cho biết GT={f1,,fu}
20
• Cần CM KL={q1,,qv} đúng
• Ta nói
KLGT
R
*
a
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
6Suy diễn đối với logic mệnh đề
Định nghĩa: Giả sử xét tập trung gian các sự kiện:
Nếu r: p1∧∧pm→q và p1,,pm ∈ Tgian
thì Tgian Tgian ∪ {q}
Nxét: quá trình SD là đơn điệu
r
a
KLTGTGTGGTKLGT j
rrr
R
ijii ⊇⇔ aaaaa ...21
* 21
21
GT ⊆ TG1 ⊆ TG2 ⊆ ⊆ TGj
GT
KL
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Suy diễn
Phương pháp suy diễn:
Modus Ponens: Modus Tollens:
A, A→B A→B, ¬B
B ¬A
• Suy diễn tiến: Xuất phát từ các mệnh đề/vị từ đã cho 
ban đầu, sử dụng các luật cho đến khi đưa ra kết luận 
mong muốn
• Suy diễn lùi: Xuất phát từ các kết luận mong muốn, 
xem những luật có khả năng suy ra chúng thêm các
22
 , 
tiền đề vào d/s các KL cần CM và cứ như vậy tiếp tục 
đến khi d/s KL cần CM rỗng. 
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Suy diễn tiến
Ý tưởng: 
• áp dụng các luật có vế trái nằm trong CSTT
• bổ sung vế phải của các luật áp dụng vào CSTT 
đến khi tìm thấy kết luận
23Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Ví dụ
VD1 Cho GT = {a b m } Tìm KL ={h }. , , a . c
1. a,b,ma→c 6. a,B →hc
2. a,b,c → A 7. A,B →C
3. b,A → hc 8. B,C →A
4 a b c→ B 9 A C→B
24
. , , . , 
5. a,b,c →C
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
7Bài tập tại lớp
BT1 Cho GT={a } KL={u} BT2 GT={a} KL={u}
So sánh stack và queue
. , 
1. a→ b
2. b → c
3. c → d
4. a → u
. , 
1. a → b
2. d → c
3. c → u
4. a → m
5. b→ n
25
6. m → p
7. p → q
8. q → u
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Thuật toán
Vào: 
• Tập các mệnh đề/vị từ đã cho (ở dạng chuẩn 
Horn)
• Tập các luật RULE dạng p→q
• Tập các mệnh đề/vị từ kết luận KL
Ra: 
• Thông báo “Thành công” nếu KL có thể suy
26
ra từ GT
PP: /*Tgian là tập các mệnh đề/vị từ đúng cho 
đến thời điểm đang xét*/
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Thuật toán
{1 Tgian = GT;
Thoa = Loc(Tgian,R);
while Thoa 0 and KL∉Tgian do
{2 r ← get(Thoa); /* r: left → q */
R = R \ {r}; Vet = Vet ∪ {r};
Tgian = Tgian ∪ {q};
Thoa = Loc(Tgian,R) 
27
}2
if KL ⊆ Tgian then exit(“Thành công”)
else exit(“Không thành công”)
}1 Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Suy diễn lùi
VD: 
1 A C B 6 B h. , → . a, → c
2. a,b,ma→c 7. b,A → hc
3. a,b,c → A 8. c,S → hc
4. a,b,c → B 9. a,b,c → S
28
5. a,b,c → C 1’. ha,c → B
GT={a,b,ma}; KL={hc}
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
8Suy diễn lùi
Ý tưởng: suy diễn lùi từ kết luận KL
• kiểm tra xem KL đã được biết chưa, nếu không 
• chứng minh bằng quay lui sử dụng các luật dẫn đến q 
• Tránh lặp vô tận: 
– lưu trữ các đích đã được chứng minh
– trước khi chứng minh kiểm tra xem đích cần chứng 
minh đã có trong goal stack chưa?
29
• Tránh lặp lại công việc: kiểm tra xem KL mới 
– đã ở trong tập đã được chứng minh chưa
– đã làm nhưng thất bại chưa
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Suy diễn lùi
Đầu: 
• Goal = tập các sự kiện cần CM=KL
• Goal = {f| f cần CM cho đến thời điểm 
hiện tại}
• Vet ={(f,j)| để CM f thì dùng luật j: leftj→f}
• Cờ Back = true khi quay lui
30
false không quay lui
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
f ← lấy từ GOAL
Tìm rj: leftj→ f
OKf ∈ GT goal = 0?đ đ
s
s
Vet = Vet ∪{(f,j)}
Goal = Goal ∪ leftj\GT
(g,k) ← Vet:
Tìm (g,k) ∈ VET
rk: leftk→ g; f ∈ leftk
f ∈KL?
not OK Tìm được
s
đ
đ
s
đối với f thử dùng rj
31
Tìm luật (g,l), l>k
Goal = Goal\leftk
Goal = Goal ∪ leftl\GT
Vet = Vet ∪{(g,l)}f = g Tìm được
đs
Suy diễn lùi 
1. Quá trình SD lùi tương tự quá trình 
tìm cây/đồ thị lời giải trong đồ thị V/H
2. Để tăng hiệu quả của thủ tục SDL, có 
thể đưa vào 2 tập:
– Tập Đúng chứa các sự kiện đã được 
khẳ đị h là đú (đã á đị h)
32
ng n ng x c n
– Tập Sai chứa các sự kiện đã được khẳng 
định là sai (không thể xác định)
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
9Bài tập tại lớp
BT1. Cho GT={a,b,ma}, BT2 GT={a} KL={u}
KL={hc}
1. a,b,ma→ c
2. a,b,C → s
3. a,s → ha
4. b,s → hb
5 c s h
. , 
1. a → b
2. d → c
3. c → u
4. a → m
33
. , → c
6. a,B → hc
7. a,b,c → B
5. b → n
6. m → p
7. p → q
8. q → u
So sánh SD tiến và SD lùi
• SD tiến hướng dữ liệu, tự động, không định 
hướng. Ví dụ, nhận dạng đối tượng, xác định 
hành trình
• Có thể làm rất nhiều việc không liên quan 
đến KL
• SD lùi hướng KL, thích hợp cho các bài toán 
giải quyết vấn đề Ví dụ tìm chìa khoá lập
34
 . , , 
kế hoạch thi TOEFL
• Độ phức tạo của SD lùi thường nhỏ hơn rất 
nhiều so với kích thước của CSTT.
Lê Thanh Hương – Khoa CNTT - ĐHBKHN
Suy diễn đối với logic vị từ
VD1: Xét bài toán chứng minh hình học 
I
A
L
D
J
B
GT AI=IB, BJ=JC, CK=KD, DL=LA
KL IJKL là hình bình hành
35
K C
Suy diễn đối với logic vị từ
1. trd(U,XY) Æ trd(U,YX)
2 trd(U XY) trd(V XZ)Æ ss(UV YZ). , , , ,
3. ss(XY,UV), ss(UV,ST)Æ ss(XY,ST)
4. ss(XY,VU), ss(XV,YU) Æ hbh(XYUV)
5. ss(XY,UV) Æ ss(XY,VU)
6. ss(XY,UV) Æ ss(UV,XY)
36
GT:
trd(I,AB), trd(J,BC), trd(K,CD), trd(L,DA)
KL: hbh(IJKL)
10
1. Fred là con chó giống Collie. 
2. Sam là chủ của nó. 
3. Hôm nay là thứ bảy. 
4. Thứ bảy trời lạnh. 
5. Fred là con chó được huấn luyện. 
6. Chó spaniel và (chó collie được huấn luyện) là chó tốt. 
7. Nếu một con chó tốt và có ông chủ thì nó sẽ đi cùng ông chủ. 
8 Nếu thứ bảy và ấm thì Sam ở công viên. . 
9. Nếu thứ bảy và không ấm thì Sam ở viện bảo tàng. 
• Hỏi fred ở đâu? ∃X loc(fred,X)
1. collie(Fred). 
2. owner(Sam, Fred). 
3. day(sat). 
4. cold(sat).
37
5. trained(Fred).
6. spaniel(X) ∨ (collie(X) ∧ trained(X)) Æ gooddog(X).
7. gooddog(X) ∧ owner(Y,X) ∧ loc(Y,Z)Æ loc(X,Z). 
8. day(sat) ∧ ¬cold(sat) Æ loc(Sam, park).
9. day(sat) ∧ cold(sat) Æ loc(Sam,museum).
Lê Thanh Hương – Khoa CNTT - ĐHBKHN