Các chủ đề nâng cao

/Y3 persecute (caesar, marcus) 9 marcus / X5 , caesar / Y2 hate (marcus, caesar) : Bây giờ để khẳng định là không tồn tại sự mâu thuẫn ta phải phát hiện rằng mệnh đề kết quả hate(marcus, caesar) chính là mệnh đề đã được tạo ra trước đó. Hay nói cách khác, mặc dù ta có thể tạo ra mệnh đề kết quả, nhưng không tạo ra mệnh đề mới. II.6 Sử dụng hàm tính toán, vị từ tính toán, và mối quan hệ bằng: Để có thể biểu diễn tri thức hiệu quả hơn, người ta có thể sử dụng các hàm tính toán (computable function), các vị từ tính toán (computable predicate), và các mối quan hệ bằng (equality relationship). Thí dụ 8.7: Giả sử ta có cơ sở tri thức đã được chuyển sang dạng mệnh đề như sau: 1. man (marcus) 2. pompeian (marcus) 3. born(marcus, 40) 4. ¬man(X1) ∨ mortal (X1) 5. ¬pompeian (X2) ∨ died (X2,79) 6. erupted (volcano,79) 7. ¬mortal (X3) ∨ ¬born (X3, T1) ∨ ¬gt(T2 – T1,150) ∨ dead(X3,T2) 8. now = 2003 9. 146 Võ Huỳnh Trâm – Trần Ngân Bình Chương 8: Suy Luận Tự Động a. ¬alive(X4,T3) ∨ ¬dead(X4,T3) b. dead(X5,T4) ∨ alive(X5,T4) 10. ¬died (X6, T5) ∨ ¬gt(T6, T5) ∨ dead(X6,T6) Chứng minh: ¬ alive (marcus, now) alive (marcus, now) 9a marcus / X4, now/T3 10 dead (marcus, now) marcus/X6, now/T6 5 ¬ dead (marcus, T5) ∨ ¬ gt(now, T5) marcus/X2, 79/T5 ¬ pompeian(marcus) ∨ ¬gt(now,79) thay thế bằng ¬ pompeian(marcus) ∨ ¬gt(2003,79) đơn giản ¬ pompeian(marcus) 2 † II.7 Trả lời câu hỏi: Đến đây, chúng ta đã biết hợp giải được sử dụng như thế nào để trả lời cho các câu hỏi đúng- sai, có-không, chẳng hạn như câu hỏi ‘Liệu Marcus có còn sống?’ trong thí dụ 8.7 trên. Trong phần này, chúng ta xem làm cách nào hợp giải có thể trả lời được các câu hỏi dạng điền vào chỗ trống như: “Marcus đã chết khi nào?’ => died(marcus, ??) Vì ta có thể chứng minh câu died (marcus, 79), nên đáp án ở đây là 79. Điều này cho thấy thủ tục hợp giải cung cấp một cách đơn giản để định vị câu mà chúng ta cần và tìm cách chứng minh nó. Trả lời câu hỏi “Marcus đã chết khi nào?’, có nghĩa là sự kiện ‘Marcus đã chết’ là đúng. Vì vậy ta có thể đưa ra câu cần chứng minh là: ∃T died(marcus, T) Áp dụng thủ tục hợp giải, chúng ta sẽ chứng minh rằng ¬∃T died(marcus, T) sẽ tạo ra một sự mâu thuẫn. Chuyển về dạng mệnh đề, nó sẽ là: ⇒ ∀T ¬died(marcus, T) ⇒ ¬died(marcus,T) Võ Huỳnh Trâm – Trần Ngân Bình 147 Giáo Trình Trí Tuệ Nhân Tạo Cây hợp giải bên dưới mô tả các bước hợp giải để trả lời cho câu hỏi trên. ¬pompeian(X1) ∨ died(X1,79) ¬died(marcus, T) 79/T , marcus/X1 pompeian(marcus) ¬pompeian(marcus) † Đáp án cho câu hỏi nêu ra sẽ được suy ra từ một chuỗi các phép thế lần về mệnh đề bắt đầu. Để loại bỏ đi động tác này, ta có thể thêm vào một biểu thức phụ cho mệnh đề mà ta cần chứng minh. Biểu thức phụ (hay còn gọi là biểu thức ‘câm’ - dummy) này chỉ đơn giản là mệnh đề mà ta muốn chứng minh là đúng. Để phân biệt biểu thức này với các mệnh đề khác, ta sẽ gạch dưới để làm dấu. Trong quá trình chứng minh, biểu thức ‘câm’ này chỉ đơn giản là được truyền dọc theo các bước hợp giải, các biến trong biểu thức này cũng sẽ được gắn kết (bound) như các mệnh đề khác. Trong trường hợp này, thay vì thủ tục hợp giải sẽ kết thúc khi mệnh đề kết quả là rỗng, thì nó sẽ kết thúc khi kết quả chỉ còn lại các biểu thức ‘câm’. Và các giá trị gắn kết của các biến trong các biểu thức câm này chính là lời giải cho câu hỏi đặt ra ban đầu. Cây hợp giải trả lời cho câu hỏi ‘Marcus đã chết khi nào?’ sẽ được cải biên như sau. Vì vậy, cây hợp giải dưới đây đôi khi được gọi là cây chứng minh cải biên. ¬pompeian(X1) ∨ died(X1,79) ¬died(marcus, T) ∨ died(marcus,T) 79/T , marcus/X1 pompeian(marcus) ¬pompeian(marcus) ∨ died(marcus,79) died(marcus,79) III NHẬN XÉT VỀ PHƯƠNG PHÁP HỢP GIẢI: Các kết quả của Robinson đã đặt nền móng cho một loạt các nghiên cứu có liên quan đến việc vận dụng phương pháp hợp giải và các phương pháp tương tự trong lĩnh vực chứng minh định lý tự động. Những ưu điểm chính của phương pháp hợp giải là tính tổng quát, tính phổ dụng, khả năng áp dụng tốt đối với các dạng câu Horn (tức là câu có dạng A1 ∧ A2 ∧ … An → B), song nó cũng có hai nhược điểm chủ yếu: − Trong quá trình tư duy, thông thường con người không sử dụng chiến lược suy diễn này. Vì vậy một người khó có thể giao tiếp với chương trình chứng minh sử dụng phương pháp hợp giải, để có thể cho nó một lời khuyên hay nhận lời khuyên từ nó. Việc chứng minh các vấn đề khó vẫn còn là một điều khó khăn đối với máy tính, vì vậy về mặt thực tế, nếu con người và máy tính có thể tương tác với nhau cũng là điều rất quan trọng . 148 Võ Huỳnh Trâm – Trần Ngân Bình Chương 8: Suy Luận Tự Động − Trong khi chuyển các câu về dạng mệnh đề, chúng ta đã đánh mất các thông tin kinh nghiệm có giá trị chứa trong các câu ban đầu. Ví dụ: Với câu ‘Người am hiểu và không quanh co là người được giáo dục tốt’ ∀X judge(X) ∧ ¬crooked(X) → educated(X) Chuyển về dạng mệnh đề: ¬judge(X) ∨ crooked(X) ∨ educated(X) Câu này cũng có thể diễn dịch thành ‘một người không phải là người am hiểu nếu như anh ta không quanh co và không được giáo dục tốt’! Điều này cho thấy ý nghĩa của câu phát biểu ban đầu đã bị mất hoàn toàn. TỔNG KẾT CHƯƠNG VIII : Nội dung chính của chương này bao gồm: - Hợp giải (hay còn gọi là thủ tục Robinson) là một kỹ thuật chứng minh định lý được biểu diễn bằng đại số mệnh đề hay đại số vị từ. Hợp giải sử dụng phản chứng để chứng minh một vấn đề. - Trước khi áp dụng thủ tục Robinson, các câu phải được chuyển về dạng chuẩn hay dạng mệnh đề. Một mệnh đề là một tuyển của các biến mệnh đề. - Thủ tục hợp giải là một quá trình lặp đơn giản. Ở mỗi lần lặp, ta tìm hai mệnh đề có chứa hai biến mệnh đề bù nhau để hợp giải và cho ra mệnh đề mới. Quá trình này cứ tiếp tục cho đến khi ta được một mệnh đề rỗng. - Trong logic vị từ, nếu biến mệnh đề có đối số là biến, thì muốn biết hai biến mệnh có bù nhau hay không ta phải đối sánh chúng theo giải thuật đồng nhất đã học ở chương 2. Sau khi hợp giải chúng, ta phải giữ lại tập phép thế trả ra bởi giải thuật đồng nhất này. - Hợp giải có thể phát hiện trường hợp không tồn tại sự mâu thuẫn, khi đó một mệnh đề kết quả sẽ xuất hiện lặp lại. - Để hỗ trợ tốt hơn cho quá trình chứng minh, hợp giải có thể sử dụng hàm tính toán, vị từ tính toán hay mối quan hệ bằng. - Có thể sử dụng hợp giải cho các bài toán dạng trả lời câu hỏi bằng cách sử dụng thêm biểu thức phụ hay biểu thức ‘câm’. IV BÀI TẬP CHƯƠNG VIII VIII.1. Đưa câu vị từ sau về dạng mệnh đề: ∀X ( [ a(X) ∧ b(X)] → [c(X,I) ∧∃Y (∃Z[c(Y,Z)] → d(X,Y))] ) ∨ ∀X(e(X)) VIII.2. Ta có các tri thức như sau: Võ Huỳnh Trâm – Trần Ngân Bình 149 Giáo Trình Trí Tuệ Nhân Tạo 150 Võ Huỳnh Trâm – Trần Ngân Bình 1. Ngón tay là bộ phận của bàn tay 2. Bàn tay là bộ phận của cánh tay 3. Cánh tay là bộ phận của cơ thể Sử dụng hợp giải hãy chứng minh ngón tay là bộ phận của cơ thể VIII.3. Giả sử các hiểu biết của một chuyên gia trong một tình huống nào đó được phát biểu dưới dạng các biểu thức logic mệnh đề sau đây : 1. a ∧ ((a ∧ x) → d) 2. (a → (b ∧ c)) ∧ x 3. (c → a) → (d ∧ e) 4. b → (( d ∧ x) → f) 5. (e ∧ b) → f 6. ( e ∧ y) → g 7. d → f 8. f → (¬a ∨ g) Hãy chứng minh g đúng bằng thủ tục hợp giải. VIII.4. Sử dụng các tri thức đã cho ở bài tập 2.3: a) John thích mọi loại thức ăn. b) Táo là thức ăn. c) Gà là thức ăn. d) Tất cả mọi thứ ăn được mà vẫn còn sống thì đó là thức ăn. e) Bill ăn đậu phộng và Bill vẫn còn sống. f) Sue ăn mọi thứ mà Bill ăn. 1. Hãy biểu diễn tri thức trên theo logic vị từ. 2. Hãy sử dụng hợp giải để chứng minh “John thích đậu phộng” 3. Sử dụng hợp giải để trả lời câu hỏi : “Sue ăn gì ?” VIII.5. Giải lại bài tập 2.4 bằng thủ tục hợp giải. Chương 9: Học máy Võ Huỳnh Trâm – Trần Ngân Bình 151 PHẦN IV ................................................................................................................................................... 135 CÁC CHỦ ĐỀ NÂNG CAO...................................................................................................................... 135 Chương VIII............................................................................................................................................... 136 SUY LUẬN TỰ ĐỘNG ............................................................................................................................ 136 (AUTOMATIC REASONING)................................................................................................................. 136 I. GIỚI THIỆU: ................................................................................................................................ 137 II. THỦ TỤC HỢP GIẢI (RESOLUTION) ...................................................................................... 139 II.1. Chuyển về dạng mệnh đề (Clause form):............................................................................. 139 II.2. Cơ sở của Hợp giải (Resolution):......................................................................................... 142 II.3. Giải thuật hợp giải dùng cho Logic mệnh đề: ...................................................................... 142 II.4. Giải thuật hợp giải dùng cho Logic vị từ ............................................................................. 143 II.5. Hợp giải có thể phát hiện trường hợp không tồn tại sự mâu thuẫn:..................................... 145 II.6. Sử dụng hàm tính toán, vị từ tính toán, và mối quan hệ bằng:............................................. 146 II.7. Trả lời câu hỏi: ..................................................................................................................... 147 III. NHẬN XÉT VỀ PHƯƠNG PHÁP HỢP GIẢI: ....................................................................... 148 TỔNG KẾT CHƯƠNG VIII : ............................................................................................................... 149 BÀI TẬP CHƯƠNG VIII........................................................................................................... 149