Các hệ thống thông minh nhân tạo & ứng dụng - Logic (Phần 2) - Bùi Thị Danh

Nội dung text: Các hệ thống thông minh nhân tạo & ứng dụng - Logic (Phần 2) - Bùi Thị Danh

1. CÁC HỆ THỐNG THÔNG MINH NHÂN TẠO & ỨNG DỤNG Logic THS. BÙI THỊ DANH BM.KHMT, KHOA CNTT, ĐH.KHTN TP.HCM
2. Nội dung chính Tổng quan Logic mệnh đề Logic bậc nhất 2
3. Hạn chế của logic mệnh đề Mục tiêu của logic là biểu diễn tri thức, sự kiện của thế giới một cách súc tích. Logic mệnh đề có đảm bảo việc này? Alice và Bob đều biết số học ◦ AliceKnowsArithmetic ∧ BobKnowsArithmetic Tất cả sinh viên đều biết số học ◦ AliceIsStudent → AliceKnowsArithmetic ◦ BobIsStudent → BobKnowsArithmetic Nhiều, cồng kềnh ◦ Mọi số nguyên chẵn lớn hơn 2 đều là tổng của 2 số nguyên tố ◦ ??? Khó biểu diễn 3
4. Hạn chế của Logic mệnh đề Logic mệnh đề thiếu các khái niệm để cho phép diễn đạt sự kiện súc tích hơn, chẳng hạn: ◦ Đối tượng (object) và quan hệ (relation): các mệnh đề (AliceKnowsArithmetic) có cấu trúc bên trong (alice, Knows, arithmetic) ◦ Lượng từ (quantifier) và biến (variable): “tất cả” là một lượng từ có thể dùng để ám chỉ mọi người, mà không phải liệt kê từng người một Logic bậc nhất (First Order Logic – FOL) 4
5. Logic bậc nhất (First Order Logic) 5
6. Cú pháp: các thành phần cơ bản Kí hiệu hằng (Constant symbol) ◦ Biểu diễn đối tượng ◦ Ví dụ: 푙푖 푒, 표 , 2, Kí hiệu vị từ (Predicate symbol) ◦ Biểu diễn quan hệ (trả lời ‘yes’ hoặc ‘no’) ◦ Ví dụ: 표푡ℎ푒 ( 푖 ℎ , 푗표ℎ푛), 푒 푡푒 ℎ 푛(3, 2), Kí hiệu hàm (Function symbol) ◦ Biểu diễn cho hàm (Trả về một giá trị) ◦ Ví dụ: 푆푞 푡(4), 표푡ℎ푒 (푗표ℎ푛), 6
7. Cú pháp: các thành phần cơ bản Khái niệm Ví dụ Hằng (constant) alice, arithmetic, bob, 2, Vị từ (Predicate) Knows, Brother, GreaterThan, Hàm (Function) MotherOf, Sqrt, Biến (Variable) x, y, a, b Phép nối (Connective) ¬,∧,∨, →, ↔ Sự bằng nhau (Equality) = Lượng từ (Quantifier) ∃ , ∀ 7
8. Cú pháp Term là biểu thức logic ám chỉ đối tượng. ◦ Hằng: 푙푖 푒, 표 , 푖푡ℎ 푒푡푖 , 2 ◦ Biến: , , , , ◦ Hàm: 푆푞 푡(4), 표푡ℎ푒 (푗표ℎ푛), Công thức hoặc câu (sentence) ◦ Công thức nguyên tử: vị từ áp dụng lên biểu thức ◦ 퐾푛표푤푠( , 푖푡ℎ 푒푡푖 ) ◦ Phép nối áp dụng lên công thức ◦ 푆푡 푒푛푡 → 퐾푛표푤푠( , 푖푡ℎ 푒푡푖 ) ◦ Lượng từ áp dụng lên công thức ◦ ∀ 푆푡 푒푛푡 → 퐾푛표푤푠( , 푖푡ℎ 푒푡푖 ) 8
9. Cú pháp: Lượng từ Lượng từ với mọi (∀): ◦ ∀ 푃( ) thì giống như 푃 ∧ 푃 ∧ ⋯ Lượng từ tồn tại (∃): ◦ ∃ 푃( ) thì giống như 푃 ∨ 푃 ∨ ⋯ Một số thuộc tính: ◦ ¬∀ 푃( ) tương đương với ∃ ¬푃( ) ◦ ∀ ∃ 푃 , thì khác với ∃ ∀ 푃( , ) 9
10. Cú pháp: Qui tắc De Morgan cho lượng từ ¬ 푃 ∨ 푄 ≡ ¬푃 ∧ ¬푄 ∀ 푃 ≡ ¬∃ ¬푃( ) ¬ 푃 ∧ 푄 ≡ ¬푃 ∨ ¬푄 ∃ 푃( ) ≡ ¬∀ ¬푃( ) 푃 ∨ 푄 ≡ ¬ ¬푃 ∧ ¬푄 ¬∀ 푃( ) ≡ ∃ ¬푃( ) 푃 ∧ 푄 ≡ ¬ ¬푃 ∨ ¬푄 ¬∃ 푃( ) ≡ ∀ ¬푃( ) 10
11. Cú pháp: Lượng từ với ngôn ngữ tự nhiên Lượng từ với mọi (∀): ◦ Mọi sinh viên đều biết số học ◦ ∀ 푆푡 푒푛푡 → 퐾푛표푤푠( , 푖푡ℎ 푒푡푖 ) Lượng từ tồn tại (∃): ◦ Một số sinh viên thì biết số học ◦ ∃ 푆푡 푒푛푡( ) ∧ 퐾푛표푤푠( , 푖푡ℎ 푒푡푖 ) 11
12. Cú pháp: ví dụ Mọi loại nấm màu tím đều có độc ◦ ∀ 푠ℎ 표표 ∧ 푃 푙푒 → 푃표푖푠표푛표 푠( ) Mèo là động vật có vú ◦ ∀ 푡 → 푙( ) Không ai yêu Lan ◦ ¬∃ 퐿표푣푒( , 퐿 푛) hoặc ∀ ¬퐿표푣푒( , 퐿 푛) Cháu là con của anh em ◦ ∀ ∀ 푖푒 푒 푒 ℎ푒푤 , ↔ ∃ 푆푖 푙푖푛 ( , ) ∧ ℎ푖푙 ( , ) Bà ngoại là mẹ của mẹ ◦ ∀ ∀ 푛 표푡ℎ푒 , ↔ ∃ 표푡ℎ푒 ( , ) ∧ 표푡ℎ푒 ( , ) ◦ ∀ ∀ = 푛 표푡ℎ푒 ↔ ∃ = 표푡ℎ푒 ∧ = 표푡ℎ푒 ( ) 12
13. Cú pháp: ví dụ Có một số khóa học mà mọi sinh viên đều tham gia ◦ ∃ 표 푠푒 ∧ ∀ 푆푡 푒푛푡 → 푒푠( , ) Mọi số nguyên chẵn lớn hơn 2 là tổng của 2 số nguyên tố ◦ ∀ 푣푒푛 푛푡 ∧ 푒 푡푒 , 2 → ∃ ∃ 푞 푙푠( , 푆 , ) ∧ 푃 푖 푒( ) ∧ 푃 푖 푒( ) Nếu một sinh viên học một khóa học và khóa học đó có đề cập đến một khái niệm thì sinh viên đó biết về khái niệm đó. ◦ ∀ ∀ ∀ 푆푡 푒푛푡 ∧ 표 푠푒 ∧ 푒푠 , ∧ 표푣푒 푠 , → 퐾푛표푤푠( , ) 13
14. Cú pháp: bài tập Lan là sinh viên học giỏi Mọi người đều yêu ai đó Ai cũng có một cha Ai cũng có một cha và một mẹ Bất kỳ ai có một cha cũng có một mẹ 14
15. Cú pháp: bài tập Lan là sinh viên học giỏi ◦ 푆푡 푒푛푡 퐿 푛 ∧ 푆푡 − 푤푒푙푙(퐿 푛) Mọi người đều yêu ai đó ◦ ∀ ∃ 퐿표푣푒푠( , ) Ai cũng có một cha ◦ ∀ ∃ 퐹 푡ℎ푒 ( , ) Ai cũng có một cha và một mẹ ◦ ∀ ∃ ∃ 퐹 푡ℎ푒 ( , ) ∧ 표푡ℎ푒 ( , ) Bất kỳ ai có một cha cũng có một mẹ ◦ ∀ ∃ 퐹 푡ℎ푒 , → ∃ 표푡ℎ푒 ( , ) 15
16. Ngữ nghĩa Mô hình 푤 trong logic bậc nhất ánh xạ ◦ Kí hiệu hằng số sang đối tượng ◦ 푤 푙푖 푒 = 표1, 푤 표 = 표2, 푤 푖푡ℎ 푒푡푖 = 표3 ◦ Kí hiệu vị từ sang cặp các đối tượng ◦ 푤 퐾푛표푤푠 = 표1, 표3 , 표2, 표3 , 16
17. Ngữ nghĩa Nếu tồn tại ánh xạ một – một giữa các kí hiệu hằng số và các đối tượng thì logic bậc nhất là dạng ngắn của logic mệnh đề Ví dụ: KB ở dạng Logic bậc nhất 푆푡 푒푛푡( 푙푖 푒) ∧ 푆푡 푒푛푡 표 ∀ 푆푡 푒푛푡 → 푃푒 푠표푛( ) Propositionalization ∃ 푆푡 푒푛푡 ∧ 푒 푡푖푣푒( ) KB ở dạng Logic mệnh đề 푆푡 푒푛푡( 푙푖 푒) ∧ 푆푡 푒푛푡 표 푆푡 푒푛푡 푙푖 푒 → 푃푒 푠표푛( 푙푖 푒) ∧ 푆푡 푒푛푡 표 → 푃푒 푠표푛( 표 ) 푆푡 푒푛푡 푙푖 푒 ∧ 푒 푡푖푣푒( 푙푖 푒) ∨ 푆푡 푒푛푡 표 ∧ 푒 푡푖푣푒 표 17
18. Phương pháp suy dẫn Mục tiêu: cần các luật suy diễn có thể làm việc với các công thức có lượng từ Ví dụ ◦ Cho 푃( 푙푖 푒) và ∀ 푃 → 푄 ◦ Có suy diễn được 푄 푙푖 푒 ? ◦ Vấn đề: 푃( ) và 푃( 푙푖 푒) không khớp nhau Đề xuất các khái niệm: ◦ Phép thay thế (substitution): ánh xạ công thức sang một công thức khác. ◦ Phép đồng nhất (unification): làm cho hai công thức giống nhau. 18
19. Phép thay thế (substitution) Một phép thay thế 휃 là một ánh xạ từ các biến sang các kí hiệu hằng hoặc biến khác Kí hiệu: 푆 푠푡 휃, 훼 , trả về kết quả thực hiện phép thay thế 휃 trên công thức 훼 Ví dụ ◦ 푆 푠푡 / 푙푖 푒 , 푃( ) = 푃( 푙푖 푒) ◦ 푆 푠푡 / 푙푖 푒, / , 푃( ) ∧ 퐾( , ) = 푃( 푙푖 푒) ∧ 퐾( 푙푖 푒, ) 19
20. Phép đồng nhất (unification) Phép đồng nhất thực hiện trên hai công thức 훼 푣à 훽, trả về một phép thay thế 휃 làm cho hai công thức giống nhau, tức: ◦ Hoặc 푈푛푖 훼, 훽 = 휃 sao cho 푆 푠푡 휃, 훼 = 푆 푠푡 휃, 훽 ◦ Hoặc lỗi nếu không tồn tại 휃 Ví dụ: ◦ 푈푛푖 퐾푛표푤푠 푙푖 푒, 푖푡ℎ 푒푡푖 , 퐾푛표푤푠( , 푖푡ℎ 푒푡푖 ) = / 푙푖 푒 ◦ 푈푛푖 퐾푛표푤푠 푙푖 푒, , 퐾푛표푤푠( , ) = / 푙푖 푒, / ◦ 푈푛푖 퐾푛표푤푠 푙푖 푒, , 퐾푛표푤푠( 표 , ) = 푙ỗ푖 ◦ 푈푛푖 퐾푛표푤푠 푙푖 푒, , 퐾푛표푤푠( , 퐹( )) = / 푙푖 푒, /퐹( 푙푖 푒) 20
21. Phương pháp suy dẫn Hợp giải với KB ở dạng CNF Suy diễn với KB ở dạng Horn 21
22. Hợp giải với KB ở dạng CNF Nhắc lại: Để chứng minh 퐾 ⊨ 훼 ta chứng minh 퐾 ∧ ¬훼 không thỏa Các bước chứng minh: ◦ Chuyển 퐾 ∧ ¬훼 về dạng CNF ◦ Áp dụng luật hợp giải: tìm cặp mệnh đề đối ngẫu 푃 và ¬푃 22
23. Chuyển về dạng CNF Ví dụ: Người yêu tất cả các động vật thì được yêu bởi một ai đó ◦ ∀ ∀ 푛푖 푙 → 퐿표푣푒푠 , → ∃ 퐿표푣푒푠( , ) Loại bỏ dấu tương đương và kéo theo ◦ ∀ ∀ ¬ 푛푖 푙 ∨ 퐿표푣푒푠 , → ∃ 퐿표푣푒푠( , ) ◦ ∀ ¬ ∀ ¬ 푛푖 푙 ∨ 퐿표푣푒푠 , ∨ ∃ 퐿표푣푒푠( , ) Đẩy dấu phủ định vào trong, loại bỏ 2 dấu phủ định ◦ ∀ ∃ 푛푖 푙 ∧ ¬퐿표푣푒푠 , ∨ ∃ 퐿표푣푒푠( , ) Chuẩn hóa biến: mỗi lượng từ nên sử dụng các biến khác nhau ◦ ∀ ∃ 푛푖 푙 ∧ ¬퐿표푣푒푠 , ∨ ∃ 퐿표푣푒푠( , ) 23
24. Chuyển về dạng CNF ◦ ∀ ∃ 푛푖 푙 ∧ ¬퐿표푣푒푠 , ∨ ∃ 퐿표푣푒푠( , ) Skolem hóa: thay thế các biến với lượng từ tồn tại bằng hàm Skolem theo các biến có lượng từ với mọi ◦ ∀ 푛푖 푙 푌 ∧ ¬퐿표푣푒푠 , 푌 ∨ 퐿표푣푒푠(푍( ), ) Bỏ lượng từ với mọi: các biến còn lại giả định là với mọi ◦ 푛푖 푙 푌 ∧ ¬퐿표푣푒푠 , 푌 ∨ 퐿표푣푒푠(푍( ), ) Phân phối ∨ 푣ớ푖 ∧: ◦ 푛푖 푙 푌 ∨ 퐿표푣푒푠(푍( ), ) ∧ ¬퐿표푣푒푠 , 푌 ∨ 퐿표푣푒푠(푍( ), ) 24
25. Hợp giải Luật hợp giải: Ví dụ 훼1∨⋯∨훼푛∨ℎ1 푛𝑖 푙 푌 ∨ 퐿표푣푒푠(푍 , ) 훽1∨⋯∨훽 ∨¬ℎ2 ¬퐿표푣푒푠 ,푣 ∨ 퐹푒푒 푠( ,푣) 푆 푠푡 휃,훼1∨⋯∨훼푛∨훽1∨⋯∨훽 푛𝑖 푙 푌 ∨ 퐹푒푒 푠 (푍 , ) ◦ Trong đó, 휃 = 푈푛푖 (ℎ1, ℎ2) ◦ Phép thay thế 휃 = 푈푛푖 /푍 , 푣/ 25
26. Ví dụ 1 Chứng minh ∃ 푄( ) từ KB như bên cạnh KB 푃 → 푄( ) 푃( ) Bước Công thức Suy dẫn 1 ¬푃( ) ∨ 푄( ) Cho trước 2 푃( ) Cho trước 3 ¬푄( ) Phủ định kết luận 4 ¬푃(z) 1, 3 휃 = { Τ } 5 False 2, 4 휃 = / 26
27. Ví dụ 2 Cho KB như bên cạnh. Tìm sao cho 푄( ) đúng KB 푃 → 푄( ) 푃( ) 푃( ) Bước Công thức Suy dẫn 1 ¬푃( ) ∨ 푄( ) Cho trước 2 푃( ) Cho trước 3 푃( ) Cho trước 4 ¬푄( ) Phủ định kết luận 5 ¬푃(z) 1, 4 휃 = { Τ } 6 False 2, 5 휃 = / 7 False 3, 5 휃 = / 27
28. Ví dụ 3 Cho KB gồm các câu như sau. Hỏi Art có phải là ông nội của Coe không? ◦ Art là cha của Bob và Bud. ◦ Bob là cha của Cal và Coe. ◦ Ông nội là cha của cha. Biểu diễn lại KB theo logic bậc nhất ◦ 퐹 푡ℎ푒 ( 푡, 표 ) ∧ 퐹 푡ℎ푒 ( 푡, ) ◦ 퐹 푡ℎ푒 ( 표 , 푙) ∧ 퐹 푡ℎ푒 ( 표 , 표푒) ◦ ∃ 퐹 푡ℎ푒 , ∧ 퐹 푡ℎ푒 , → 푛 푡ℎ푒 , ◦ 푛 푡ℎ푒 푡, 표푒 ? 28
29. Ví dụ 3 Bước Công thức Suy dẫn 1 퐹 푡ℎ푒 ( 푡, 표 ) Cho trước 2 퐹 푡ℎ푒 ( 푡, ) Cho trước 3 퐹 푡ℎ푒 ( 표 , 푙) Cho trước 4 퐹 푡ℎ푒 ( 표 , 표푒) Cho trước 5 ¬퐹 푡ℎ푒 ( , ) ∨ ¬퐹 푡ℎ푒 ( , ) ∨ 푛 푡ℎ푒 ( , ) Cho trước 6 ¬ 푛 푡ℎ푒 푡, 표푒 Phủ định kết luận 7 ¬퐹ather( 푡, z) ∨ ¬퐹 푡ℎ푒 ( , 표푒) 5, 6 휃 = { Τ 푡 , Τ 표푒} 8 ¬퐹 푡ℎ푒 ( 표 , coe) 1, 7 휃 = Τ 표 9 False 4, 5 29
30. Ai là ông của Coe? Bước Công thức Suy dẫn 1 퐹 푡ℎ푒 ( 푡, 표 ) Cho trước 2 퐹 푡ℎ푒 ( 푡, ) Cho trước 3 퐹 푡ℎ푒 ( 표 , 푙) Cho trước 4 퐹 푡ℎ푒 ( 표 , 표푒) Cho trước 5 ¬퐹 푡ℎ푒 ( , ) ∨ ¬퐹 푡ℎ푒 ( , ) ∨ 푛 푡ℎ푒 ( , ) Cho trước 6 ¬ 푛 푡ℎ푒 2, 표푒 Phủ định kết luận 7 ¬퐹ather( 2, z) ∨ ¬퐹 푡ℎ푒 ( , 표푒) 5, 6 휃 = { Τ 2 , Τ 표푒} 8 ¬퐹ather( 2, 표 ) 4, 7 휃 = Τ 표 9 False 1, 8 휃 = 풙 Τ 풓풕 30
31. Bài tập 1 Là phạm tội nếu một người Mỹ bán vũ khí cho kẻ địch Nono có một vài tên lửa Tất cả các tên lửa mà Nono có đều được bán bởi West Tên lửa là vũ khí Một kẻ thù của nước Mỹ được gọi là kẻ địch West là một người Mỹ Nono là một kẻ thù của nước Mỹ West có phạm tội không? 31
32. Bài tập 1 Là phạm tội nếu một người Mỹ bán vũ khí cho kẻ địch ◦ ∀ ∀ ∀ 푒 푖 ∧ 푊푒 표푛 ∧ 표푠푡푖푙푒 ∧ 푆푒푙푙푠 , , → 푖 푖푛 푙( ) Nono có một vài tên lửa ◦ ∃ 푤푛푠 푛표푛표, ∧ 푖푠푠푖푙푒( ) Tất cả các tên lửa mà Nono có đều được bán bởi West ◦ ∀ 푖푠sile x ∧Owns nono, x →Sells(west, x, nono) Tên lửa là vũ khí ◦ ∀ 푖푠푠푖푙푒 → 푊푒 표푛( ) Một kẻ thù của nước Mỹ được gọi là kẻ địch ◦ ∀ 푛푒 , 푒 푖 → 표푠푡푖푙푒( ) West là một người Mỹ ◦ 푒 푖 (푤푒푠푡) Nono là một kẻ thù của nước Mỹ ◦ 푛푒 (푛표푛표, 푒 푖 ) West có phạm tội không? 푖 푖푛 푙(푤푒푠푡) 32
33. Bài tập 1 33
34. Bài tập 2 Người nào yêu tất cả động vật thì được yêu bởi ai đó Bất kì ai giết động vật thì không được ai yêu Jack yêu tất cả động vật Hoặc Curiosity hoặc Jack đã giết Tuna Tuna là một con mèo Mèo là một loài động vật Hỏi Jack có giết Tuna không? 34
35. Bài tập 2 Người nào yêu tất cả động vật thì được yêu bởi ai đó ◦ ∀ ∀ 푛푖 푙 → 퐿표푣푒푠 , → ∃ 퐿표푣푒푠( , ) Bất kì ai giết động vật thì không được ai yêu ◦ ∀ ∃ 퐾푖푙푙푠 , → ∀ ¬퐿표푣푒푠( , ) Jack yêu tất cả động vật ◦ ∀ 푛푖 푙 → 퐿표푣푒푠(퐽 , ) Hoặc Curiosity hoặc Jack đã giết Tuna ◦ 퐾푖푙푙푠 푖표푠푖푡 , 푡 푛 ∨ 퐾푖푙푙푠(푗 , 푡 푛 ) Tuna là một con mèo ◦ 푡( 푛 ) Mèo là một loài động vật ◦ ∀ 푡 → 푛푖 푙( ) Hỏi Curiosity có giết Tuna không? 퐾푖푙푙푠( 푖표푠푖푡 , 푡 푛 ) 35
36. Bài tập 2 36
37. Suy diễn với KB ở dạng Horn Modus Ponen Ví dụ ′ , . . . , ′ 1 Cho các tiền đề ∀ ∧ . . . ∧ → 1 푛 1 ◦ 푒푠 푙푖 푒, 푠221 ′ ◦ 표푣푒 푠 푠221, 푙표 푖 ◦ Tìm phép đồng nhất tổng quát nhất trên tiền đề ◦ ∀ ∀ ∀ 푒푠 , ∧ 표푣푒 푠 , → ◦ 휃 = 푈푛푖 ′ ∧ . . . ∧ ′ , ∧ . . . ∧ 1 1 퐾푛표푤푠( , ) ◦ Áp dụng 휃 để xác định kết luận: ◦ 푆 푠푡 휃, = ′ Kết luận ◦ 휃 = / 푙푖 푒, / 푠221, /푙표 푖 ◦ ′ = 퐾푛표푤푠( 푙푖 푒, 푙표 푖 ) 37
38. Suy diễn tiến (forward chaining) function FOL − FC − ASK(KB, 훼) returns phép thay thế hoặc false repeat until 푛푒푤 là rỗng 푛푒푤 ← { } for each công thức trong 퐾 do Chuẩn hóa r 푡ℎà푛ℎ 1 ∧ ⋯ ∧ 푛 → 푞 for each 휃 sao cho (p1   pn) = (p’1   p’n) do Với p’1, , p’n nào đó trong KB 푞′ ← 푆 푠푡(휃, q) if 푞′ không phải là một câu đã có trong KB hay 푛푒푤 then thêm q’ vào new   Unify(q’, ) if  thành công then return  Thêm 푛푒푤 푣à표 퐾 return false 38
39. Ví dụ 퐹 푡ℎ푒 ( 푡, 표 ) 표푡ℎ푒 , → 푃 푒푛푡( , ) 퐹 푡ℎ푒 ( 푡, ) 1 = {x/ave, y/bee} 표푡ℎ푒 ( 푣푒, 푒푒) 푞’ = 푃 푒푛푡( 푣푒, 푒푒) 퐹 푡ℎ푒 표 , 푙 2 = {x/bee, y/cal} 표푡ℎ푒 ( 푒푒, 푙) 퐹 푡ℎ푒 ( 표 , 표푒) 푞’ = 푃 푒푛푡( 푒푒, 푙) 표푡ℎ푒 ( 푣푒, 푒푒) 3 = {x/bee, y/coe} 표푡ℎ푒 ( 푒푒, 표푒) 푞’ = 푃 푒푛푡( 푒푒, 표푒) 표푡ℎ푒 ( 푒푒, 표푒) 표푡ℎ푒 ( 푒푒, 푙) 표푡ℎ푒 , → 푃 푒푛푡( , ) 퐹 푡ℎ푒 , → 푃 푒푛푡( , ) 푃 푒푛푡 , ∧ 푃 푒푛푡 , → 푛 푃 푒푛푡( , ) 푛 푃 푒푛푡( , 표푒) ? 39
40. Ví dụ 푃 푒푛푡( 푣푒, 푒푒) 퐹 푡ℎ푒 ( 푡, 표 ) 퐹 푡ℎ푒 , → 푃 푒푛푡( , ) 푃 푒푛푡( 푒푒, 푙) 퐹 푡ℎ푒 ( 푡, ) 1 = {x/art, y/bob} 퐹 푡ℎ푒 ( 푡, 표 ) 퐹 푡ℎ푒 표 , 푙 푃 푒푛푡( 푒푒, 표푒) q’ = 푃 푒푛푡( 푡, 표 )  = {x/art, y/bud} 퐹 푡ℎ푒 ( 푡, ) 퐹 푡ℎ푒 ( 표 , 표푒) 2 q’ = 푃 푒푛푡( 푡, ) 표푡ℎ푒 ( 푣푒, 푒푒) 3 = {x/bob, y/cal} 퐹 푡ℎ푒 ( 표 , 푙) 표푡ℎ푒 ( 푒푒, 표푒) q’ = 푃 푒푛푡( 표 , 푙) 표푡ℎ푒 ( 푒푒, 푙) 4 = {x/bob, y/coe} 퐹 푡ℎ푒 ( 표 , 표푒) 표푡ℎ푒 , → 푃 푒푛푡( , ) q’ = 푃 푒푛푡( 표 , 표푒) 퐹 푡ℎ푒 , → 푃 푒푛푡( , ) 푃 푒푛푡 , ∧ 푃 푒푛푡 , → 푛 푃 푒푛푡( , ) 푛 푃 푒푛푡( , 표푒) ? 40
41. Ví dụ 퐹 푡ℎ푒 ( 푡, 표 ) 푃 푒푛푡( 푣푒, 푒푒) 푃 푒푛푡 , ∧ 푃 푒푛푡 , → 푛 푃 푒푛푡( , )  = {x/ave,y/bee,z/cal} 푃 푒푛푡( 푣푒, 푒푒) ∧ 푃 푒푛푡( 푒푒, 푙) 퐹 푡ℎ푒 ( 푡, ) 푃 푒푛푡( 푒푒, 푙) 1 q’ = 푛 푃 푒푛푡( 푣푒, 푙) 퐹 푡ℎ푒 표 , 푙 푃 푒푛푡( 푒푒, 표푒) 2 = {x/ave,y/bee,z/coe} 푃 푒푛푡( 푣푒, 푒푒) ∧ 푃 푒푛푡( 푒푒, 표푒) 퐹 푡ℎ푒 ( 표 , 표푒) 푃 푒푛푡( 푡, 표 ) q’ = 푛 푃 푒푛푡( 푣푒, 표푒) 3 = {x/art, y/bob, z/cal} 푃 푒푛푡( 푡, 표 ) ∧ 푃 푒푛푡( 표 , 푙) 표푡ℎ푒 ( 푣푒, 푒푒) 푃 푒푛푡( 푡, ) q’ = 푛 푃 푒푛푡( 푡, 푙) 표푡ℎ푒 ( 푒푒, 표푒) 푃 푒푛푡( 푡, ) 4 = {x/art, y/bob, z/coe} 푃 푒푛푡( 푡, 표 ) ∧ 푃 푒푛푡( 표 , 표푒) q’ = 푛 푃 푒푛푡( 푡, 표푒) 표푡ℎ푒 ( 푒푒, 푙) 푃 푒푛푡( 표 , 표푒) 표푡ℎ푒 , → 푃 푒푛푡( , ) 퐹 푡ℎ푒 , → 푃 푒푛푡( , ) 푃 푒푛푡 , ∧ 푃 푒푛푡 , → 푛 푃 푒푛푡( , ) 푛 푃 푒푛푡( , 표푒) ? 41
42. Ví dụ - cây suy diễn 푛 푃 푒푛푡( 푡, 푙) 푛 푃 푒푛푡( 푡, 표푒) 푛 푃 푒푛푡( 푣푒, 표푒) 푛 푃 푒푛푡( 푣푒, 푙) 푃 푒푛푡 푣푒, 푒푒 푃 푒푛푡( 푡, 표 ) 푃 푒푛푡( 푡, ) 푃 푒푛푡( 표 , 푙) 푃 푒푛푡( 표 , 표푒) 푃 푒푛푡 푒푒, 표푒 푃 푒푛푡 푒푒, 푙 표푡ℎ푒 푣푒, 푒푒 퐹 푡ℎ푒 ( 푡, 표 ) 퐹 푡ℎ푒 ( 푡, ) 퐹 푡ℎ푒 ( 표 , 푙) 퐹 푡ℎ푒 ( 표 , 표푒) 표푡ℎ푒 푒푒, 표푒 표푡ℎ푒 푒푒, 푙 42
43. Suy diễn lùi (Backward Chaining) function FOL − BC − ASK(KB, goals, θ) returns tập các phép thay thế inputs: 퐾 : một cơ sở tri thức 표 푙푠: danh sách ở dạng nối liền của câu truy vấn 휃: phép thay thế hiện tại, được khởi tạo rỗng { } biến cục bộ: ans, một phép thay thế , được khởi tạo rỗng { } if 표 푙푠 là rỗng then return 휃 푞′ ← 푆 푠푡 휃, 푖 푠푡 표 푙푠 for each trong KB mà r có dạng chuẩn (p1   pn → q) và 휃′ ← 푈푛푖 (푞, 푞′) thành công ans  FOL − BC − ASK(KB, [p1, ,pn| REST(goals)],   ’)  ans return ans 43
44. Ví dụ 1 풔풌(푮풓 풏풅푷 풓풆풏풕( 풓풕, 풍), {}) 푞′ = 푛 푃 푒푛푡 푡, 푙 // 푃 푒푛푡( , )  푃 푒푛푡( , ) → 푛 푃 푒푛푡( , ) 휃′ = { / 푡, / 푙} 푠 ({푃 푒푛푡( , ), 푃 푒푛푡( , )}, { / 푡, / 푙}) 푞’ = 푃 푒푛푡( 푡, ) // 퐹 푡ℎ푒 ( 2, 2) → 푃 푒푛푡( 2, 2) ′ 휃 = 2/ 푡, / 2 푠 ({퐹 푡ℎ푒 ( 2, 2), 푃 푒푛푡( , )}, { / 푡, / 푙, 2/ 푡, / 2}} 푞’ = 퐹 푡ℎ푒 푡, 2 // 퐹 푡ℎ푒 ( 푡, 표 ) ’ = { 2/ 표 } 푠 ({푃 푒푛푡( , )}, { / 푡, / 푙, 2/ 푡, 2/ 표 , / 2}) 푞’ = 푃 푒푛푡 표 , 푙 // 퐹 푡ℎ푒 3, 3 → 푃 푒푛푡( 3, 3) ’ = { 3/ 표 , 3/ 푙} 푠 ({퐹 푡ℎ푒 ( 3, 3)}, { 3/ 표 , 3/ 푙} 푛푠 44
45. Ví dụ 1 – Cây suy diễn { / 푡, / 푙, / 표 } 퐹 푡ℎ푒 ( 푡, 표 ) 퐹 푡ℎ푒 ( 표 , 푙) 퐹 푡ℎ푒 ( 푡, ) 퐹 푡ℎ푒 ( , 푙) { / 푡, / 푙} 푃 푒푛푡( 푡, ) 푃 푒푛푡( , 푙) 푛 푃 푒푛푡( 푡, 푙) 45
46. Ví dụ 2 풔풌(푮풓 풏풅푷 풓풆풏풕( 풓풕, 풛), {}) 푞’ = 푛 푃 푒푛푡( 푡, ) // 푃 푒푛푡 ,  푃 푒푛푡 , → 푛 푃 푒푛푡( , ) ’ = { / 푡} 푠 ({푃 푒푛푡( , ), 푃 푒푛푡( , )}, { / 푡}) 푞’ = 푃 푒푛푡( 푡, ) // 퐹 푡ℎ푒 , → 푃 푒푛푡( , ) ’ = { / 푡} 푠 ({퐹 푡ℎ푒 ( , ), 푃 푒푛푡( , )}, { / 푡}) 푞’ = 퐹 푡ℎ푒 푡, // 퐹 푡ℎ푒 ( 푡, 표 ) ’ = { / 푡, / 표 } 푠 ({푃 푒푛푡( , )}, { / 푡, / 표 }) 푞’ = 푃 푒푛푡 표 , // 퐹 푡ℎ푒 2, 2 → 푃 푒푛푡( 2, 2) ’ = { 2/ 표 , 2/ } 46
47. Ví dụ 2 풔풌(푮풓 풏풅푷 풓풆풏풕( 풓풕, 풛), {}) 푠 ({퐹 푡ℎ푒 ( 2, 2)}, { 2/ 표 , 2/ }) 푞’ = 퐹 푡ℎ푒 ( 표 , ) // 퐹 푡ℎ푒 ( 표 , 푙) ’ = { / 푙} 푠 ({}, { / 푙}) 푛푠 // 퐹 푡ℎ푒 ( 표 , 표푒) ’ = { / 표푒} 푠 ({}, { / 표푒}) ans // 표푡ℎ푒 , → 푃 푒푛푡( , ) ’ = { / 푡} 푠 ({ 표푡ℎ푒 ( , ), 푃 푒푛푡( , )}, { / 푡}} 푞’ = 표푡ℎ푒 ( 푡, ) 푙푠푒 47
48. Ví dụ 2 – Cây suy diễn { / 푡, / 표 , / 표푒} 퐹 푡ℎ푒 ( 표 , 표푒) { / 푡, / 표 , / 푙} 퐹 푡ℎ푒 ( 표 , 푙) { / 푡, / 표 } 퐹 푡ℎ푒 ( 푡, 표 ) 퐹 푡ℎ푒 ( 표 , ) 퐹 푡ℎ푒 ( 푡, ) 퐹 푡ℎ푒 ( , ) { / 푡} 푃 푒푛푡( 푡, ) 푃 푒푛푡( , ) 푛 푃 푒푛푡( 푡, ) 48
49. Suy diễn lùi (Backward Chaining) Tìm kiếm chứng minh bằng cách đệ qui theo chiều sâu: không gian tuyến tính theo kích thước của chứng minh Không đầy đủ do lặp vô tận ◦ Giải pháp: Kiểm tra trạng thái hiện tại với mọi trạng thái đang có trong stack Không hiệu quả do các mục tiêu con bị lặp lại (cả khi thất bại cũng như thành công) ◦ Giải pháp: dùng bộ nhớ tạm lưu các mục tiêu con đã duyệt 49
50. Tài liệu tham khảo Cơ sở Trí tuệ Nhân tạo, Lê Hoài Bắc, Tô Hoài Việt, NXB Khoa học & Kỹ thuật. Slide bài giảng Trí tuệ nhân tạo, GV. Tô Hoài Việt, GV. Lê Ngọc Thành, Khoa CNTT, ĐH. KHTN TP.HCM Artificial Intelligence: A Modern Approach, 3rd Edition, S. Russel and P. Norvig, Pearson Education Inc., 2010 Techniques in Artificial Intelligence (SMA 5504) , MIT OpenCourseWare, Massachusetts Institute of Technology Artificial Intelligence: Principles and Techniques, Stanford courses, Autumn 2015. 50