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