Suy Luận Tự Động - CÁC CHỦ ĐỀ NÂNG CAO

Chia sẻ: Bui Trung Hieu | Ngày: | Loại File: PDF | Số trang:17

Thêm vào BST

Báo xấu

90
lượt xem 11
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Phần này sẽ khảo sát hai lĩnh vực TTNT quan trọng: suy luận tự động và máy học; đây là các lĩnh vực mà sự phát triển của chúng ảnh hưởng sâu sắc đến định hướng của toàn thể ngành khoa học TTNT. Trong lời mở đầu của phần III, chúng ta đã thảo luận những ưu và khuyết điểm của các hệ giải quyết vấn đề (GQVĐ) theo phương pháp yếu. Những vấn đề về các phương pháp yếu bao gồm tính phức tạp của không gian tìm kiếm và những khó khăn trong việc biểu diễn tri...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Suy Luận Tự Động - CÁC CHỦ ĐỀ NÂNG CAO

Chương 8: Suy Luận Tự Động PHẦN IV CÁC CHỦ ĐỀ NÂNG CAO Phần này sẽ khảo sát hai lĩnh vực TTNT quan trọng: suy luận tự động và máy học; đây là các lĩnh vực mà sự phát triển của chúng ảnh hưởng sâu sắc đến định hướng của toàn thể ngành khoa học TTNT. Trong lời mở đầu của phần III, chúng ta đã thảo luận những ưu và khuyết điểm của các hệ giải quyết vấn đề (GQVĐ) theo phương pháp yếu. Những vấn đề về các phương pháp yếu bao gồm tính phức tạp của không gian tìm kiếm và những khó khăn trong việc biểu diễn tri thức về thế giới bằng những biểu diễn tổng quát. Mặc cho những thành công của các hệ chuyên gia và các hệ GQVĐ theo phương pháp mạnh tương tự, nhiều lĩnh vực vẫn đòi hỏi phải có các phương pháp tổng quát; mà thực chất, chiến lược điều khiển của bản thân các hệ chuyên gia đều dựa trên những phương pháp GQVĐ yếu tốt. Nhiều nghiên cứu hứa hẹn về các hệ GQVĐ theo phương pháp yếu tiếp tục được tiến hành bởi cộng đồng chứng minh định lý tự động. Những kỹ thuật này đã tìm thấy ứng dụng của mình trong nhiều lĩnh vực quan trọng, trong đó có thiết kế và kiểm chứng mạch điện tích hợp, chứng minh tính đúng đắn của chương trình, và một cách gián tiếp, sự ra đời của ngôn ngữ PROLOG. Trong chương 8, chúng ta sẽ xem xét các vấn đề xung quanh suy luận tự động. Chương 9 giới thiệu máy học, một trong những vấn đề nghiên cứu trung tâm của TTNT hiện nay. Trong chương này, chúng ta xem xét 3 tiếp cận học khác nhau. Tiếp cận thứ nhất là học dựa trên ký hiệu. Bằng cách bắt đầu với một tập hợp các ký hiệu biểu diễn những thực thể và quan hệ trong một lĩnh vực vấn đề, các thuật toán học cố gắng suy ra những khái quát mới lạ, có căn cứ và hữu ích mà có thể thể hiện được qua những ký hiệu. Ngược lại với tiếp cận ký hiệu, tiếp cận kết nối thì biểu diễn tri thức như là những hình mẫu của sự hoạt động trong mạng các đơn vị xử lý nhỏ, riêng lẻ. Được thúc đẩy bởi kiến trúc não bộ, các mạng liên hệ học bằng cách sửa đổi cấu trúc của chúng nhằm đáp ứng với dữ liệu luyện tập. Thay vì tìm kiếm những khái quát có khả năng mà một ngôn ngữ biểu diễn ký hiệu có thể đem lại, các mô hình liên hệ nhận biết những hình mẫu bất biến trong dữ liệu và biểu diễn những mẫu này theo cấu trúc của chính bản thân chúng. Cũng giống như mạng kết nối được thúc đẩy bởi hệ nơron sinh học, các mô hình nổi trội của tiếp cận thứ ba được thúc đẩy bởi các phép tương tự di truyền và tiến hóa. Các thuật toán di truyền bắt đầu bằng một quần thể những lời giải ứng cử viên. Những lời giải ứng viên này sẽ được đánh giá theo khả năng giải quyết bài toán, chỉ có những lời giải phù hợp nhất mới sống sót và kết hợp với nhau để tạo ra thế hệ tiếp theo những lời giải có khả năng. Do đó, những lời giải có tốt hơn sẽ tăng dần và nổi lên như thuyết Darwin về vũ trụ. Võ Huỳnh Trâm – Trần Ngân Bình 135
Giáo Trình Trí Tuệ Nhân Tạo Chương VIII SUY LUẬN TỰ ĐỘNG (AUTOMATIC REASONING) Nội dung chính : Trong chương này, chúng ta sẽ tìm hiểu về một thành quả của nhánh nghiên cứu Suy luận tự động đã được giới thiệu ở chương I, đó là phương pháp chứng minh hợp giải (Resolution) hay còn gọi là thủ tục hợp giải. Mục tiêu cần đạt : Sau chương này, sinh viên có thể : Vận dụng giải thuật chuyển câu về dạng mệnh đề Vận dụng giải thuật Hợp giải để chứng minh các vấn đề được biểu diễn bằng ngôn ngữ logic mệnh đề. Vận dụng giải thuật Hợp Giải để chứng minh các vấn đề được biểu diễn bằng ngôn ngữ logic vị từ Kiến thức tiên quyết: Ngôn ngữ logic mệnh đề, ngôn ngữ logic vị từ, phương pháp chứng minh dẫn xuất, phép đối sánh mẫu trong logic vị từ. Tài liệu tham khảo : [1] Geogre F. Luger – Artificial Intelligence, Structures and Strategies for Complex Problem Solving 4th Ed. – Addison-Wesley Publishing Company, Inc – 2002 (trang 509 – trang 552) [2] Elaine Rich, Kevin Knight – Artificial Intelligence, 2nd Ed. McGraw Hill, Inc – 1991 (trang 131 – trang 169) 136 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 8: Suy Luận Tự Động I GIỚI THIỆU: Như đã giới thiệu trong chương I, suy luận tự động có thể xem là nhánh nghiên cứu lâu đời nhất của AI, bắt nguồn từ Logic Theorist và General Problem Solver của Newell và Simon. Sức hấp dẫn của suy luận tự động nằm trong tính chặt chẽ và tổng quát của logic. Bởi vì logic là một hệ thống hình thức, nên ta có thể tự động hóa nó. Rất nhiều vấn đề khác nhau có thể giải quyết được bằng cách biểu diễn các mô tả vấn đề và các thông tin liên quan ở dạng các tiên đề luận lý và xem bài toán như là các định lý cần chứng minh. Nổ lực của các nhà khoa học trong lĩnh vực này là tự động hóa quá trình chứng minh các định lý dựa vào các tiên đề cơ sở. Mặc dù cho đến nay vẫn chưa đạt được mục tiêu ban đầu, nhưng nhánh nghiên cứu này đã tạo ra nhiều kết quả rất quan trọng trong việc hình thức hóa các giải thuật tìm kiếm và phát triển các ngôn ngữ biểu diễn hình thức như Đại số quan hệ mà ta đã học ở chương II. Trong chương này ta sẽ tiếp tục khảo sát một trong những thành quả của lĩnh vực này, đó là phương pháp chứng minh Hợp Giải (resolution). Một ứng dụng quan trọng của hợp giải đó là làm nền tảng cho trình thông dịch của ngôn ngữ PROLOG đang được sử dụng hiện nay. Hợp giải 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 được phát triển vào giữa thập niên 60 do Robinson đề xướng. Hợp giải sử dụng phản chứng để chứng minh một vấn đề. Hay nói cách khác, để chứng minh một câu (nghĩa là chứng minh câu này đúng), hợp giải sẽ chỉ ra rằng phủ định của câu sẽ tạo ra một mâu thuẫn với các câu đã biết. Tiếp cận này trái ngược với kỹ thuật mà chúng ta đã sử dụng để chứng minh ở chương II, chương III, tức là sử dụng phép dẫn xuất để chứng minh. Trước khi đi vào phương pháp chứng minh hợp giải, chúng ta sẽ xem một ví dụ sử dụng Logic Vị Từ để biểu diễn tri thức và sử dụng phép dẫn xuất ở chương II để chứng minh. Thí dụ 8.1: Xét ví dụ với tập hợp các câu như sau: 1. Marcus was a man. 2. Marcus was a Pompeian. 3. All Pompeians were Romans. 4. Caesar was a ruler. 5. All Romans were either loyal to Caesar or hated him. 6. Everyone is loyal to someone. 7. People only try to assasinate rulers they are not loyal to. 8. Marcus tried to assasinate Caesar. Hãy chứng minh ‘Was Marcus loyal to Caesar?’ Các câu trên có thể được biểu diễn dưới dạng các câu hay công thức dạng chuẩn (wff) trong ngôn ngữ Phép tính vị từ như sau: 1) man (marcus) Võ Huỳnh Trâm – Trần Ngân Bình 137
Giáo Trình Trí Tuệ Nhân Tạo 2) pompeian (marcus) 3) ∀X pompeian (X) → roman(X) 4) ruler (caesar) 5) ∀X roman(X) → loyalto (X, caesar) ∨ hate(X, caesar) 6) ∀X, ∃Y loyalto (X,Y) 7) ∀X, ∀Y person(X) ∧ ruler(Y) ∧ trytoassasinate(X) → ¬loyalto (X,Y) 8) trytoassasinate (marcus, caesar) Chứng minh ¬loyalto(marcus, caesar) Để chứng minh mục tiêu trên, chúng ta sử dụng luật suy diễn để biến đổi thành mục tiêu mới (hay nhiều mục tiêu con mới), và cứ tiếp tục cho đến khi không còn mục tiêu nào chưa thỏa mãn. Quá trình này có thể biểu diễn bằng một đồ thị AND/OR. Ở đây, để đơn giản ta chỉ vẽ một đường duy nhất. Hình bên dưới minh họa một cách chứng minh cho mục tiêu trên: ¬loyalto (marcus, caesar) ↑ (câu 7, {marcus/X, ceasar/Y}) person (marcus) ∧ ruler (caesar) ∧ trytoassasinate (marcus, caesar) ↑ (câu 4) person (marcus) ∧ trytoassasinate (marcus, caesar) ↑ (câu 8) person (marcus) Đến đây ta gặp phải một vấn đề là mặc dù chúng ta biết Marcus là một người đàn ông (man), chúng ta không có cách nào kết luận Marcus là một người (person). Vì vậy, ta phải thêm vào cơ sở tri thức một câu như sau: 9) ∀X man (X) ∨ woman (X) → person(X) Với câu 9 vừa thêm vào, ta có thể chứng minh thành công mục tiêu trên. Từ chứng minh trên, chúng ta có nhận xét như sau: − Thậm chí các kết luận rất đơn giản cũng đòi hỏi phải chứng minh qua nhiều bước. − Quá trình tạo ra một chứng minh có liên quan đến nhiều quá trình khác nhau như quá trình đối sánh, thay thế, áp dụng luật Modus Ponens. Quá trình này sẽ phức tạp hơn nếu như các luật có nhiều từ hai mục ở vế phải hay vế trái gồm nhiều biểu thức phức tạp And hay Or với nhau. Từ những nhận xét này cho thấy việc xây dựng một chương trình có thể chứng minh được như con người là không dễ dàng chút nào. Vì vậy, ta cần một phương pháp chứng minh đơn giản hơn. Và Hợp Giải (resolution) ra đời như là một công cụ chứng minh hiện đại và mạnh 138 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 8: Suy Luận Tự Động mẽ hơn cho ngành suy luận tự động. Sự đơn giản trong phép chứng minh của hợp giải xuất phát từ nguyên nhân: Thay vì suy luận trên các câu vị từ, hợp giải thao tác trên các câu đã được chuyển thành một dạng chuẩn trước khi bắt đầu quá trình chứng minh để làm giảm tính phức tạp của vấn đề. Phần còn lại của chương này sẽ giới thiệu về thủ tục Hợp giải này. II THỦ TỤC HỢP GIẢI (RESOLUTION) Thủ tục hợp giải chứng minh bằng phản chứng (refutation). Nghĩa là để chứng minh một câu, nó sẽ chứng minh rằng phủ định của câu đó sẽ tạo ra một mâu thuẫn với các câu đã cho. Nhưng trước khi áp dụng thủ tục Robinson, các câu sẽ được chuyển về một dạng chuẩn mà ta gọi là dạng mệnh đề (clause form) II.1 Chuyển về dạng mệnh đề (Clause form): II.1.1 Nhu cầu chuyển câu về dạng mệnh đề: Giả sử chúng ta có một luật như sau: “Tất cả những người Roman biết Marcus thì hoặc là sẽ ghét Caesar hoặc nghĩ rằng bất cứ ai ghét người khác là điên rồ”, ta có thể biểu diễn tri thức này dưới dạng một công thức dạng chuẩn (wff) như sau: ∀X [roman (X) ∧ know (X,marcus) → [hate(X,caesar) ∨ (∀Y (∃Z hate(Y,Z) → thinkcrazy(X,Y) ) )]] (1) Để sử dụng công thức này trong một chứng minh đòi hỏi một quá trình đối sánh phức tạp. Quá trình này sẽ dễ dàng hơn nếu công thức được biểu diễn ở dạng đơn giản hơn. Công thức sẽ dễ dàng thao tác hơn nếu chúng nó: − Phẳng hơn, nghĩa là có ít thành phần được nhúng vào. − Các lượng tử biến (∀,∃) được tách khỏi phần còn lại của công thức để ta khỏi bận tâm xem xét chúng. Dạng chuẩn Conjunctive Normal Form (CNF) hội đủ cả hai tính chất này. CNF (Dạng chuẩn hội) : một biểu thức mệnh đề được xem là ở dạng chuẩn hội nếu nó là một chuỗi các mệnh đề kết nối nhau bằng quan hệ AND (∧). Mỗi mệnh đề có dạng một tuyển OR (∨) của các biến mệnh đề. Thí dụ 8.2: Các biểu thức sau ở dạng CNF : • (¬a ∨ c) ∧ (¬a ∨¬b ∨ e) ∧ (c ∨ ¬d ∨ ¬e) • (¬dog(X) ∨ animal(X)) (¬animal(Y) die(Y)) ∧ (dog(fido)) Công thức (1) được biểu diễn tương đương ở dạng CNF như sau: ¬ roman (X) ∨ ¬ know (X,Marcus) ∨ hate(X,Caesar) ∨ ¬ hate(Y,Z) ∨ thinkcrazy(X,Y) Một vấn đề trong thực tế khi được biểu diễn trong hệ thống thường là ở dạng các câu đúng cùng một lúc (vì vậy đó là hội của các câu), mỗi câu có thể được biểu diễn bằng một tuyển. Vì vậy, tri thức của bài toán có thể được biểu diễn như là hội của các tuyển. Võ Huỳnh Trâm – Trần Ngân Bình 139
Giáo Trình Trí Tuệ Nhân Tạo Ta có sẵn một giải thuật để chuyển bất kỳ một câu trong Logic vị từ hay công thức dạng chuẩn (wff) về dạng CNF, mà vẫn không làm mất tính tổng quát nếu chúng ta sử dụng một thủ tục chứng minh như Hợp giải để thao tác trên các wff ở dạng này. Vì vậy, để có thể sử dụng thủ tục Robinson, ta phải chuyển toàn bộ tri thức bài toán về dạng CNF hay nói khác hơn, chuyển từng câu về dạng mệnh đề (clauses). * Định nghĩa mệnh đề: Một mệnh đề được định nghĩa như là một wff ở dạng CNF nhưng không có sự hiện diện của phép hội (∧), hay nói khác hơn mỗi mệnh đề là tuyển (∨) của các biến mệnh đề (literal). Trong thí dụ 8.2 ở trên, dog(X), animal(X),.. là các biến mệnh đề. II.1.2 Giải thuật chuyển về dạng mệnh đề: Bước 1. Loại bỏ dấu → sử dụng công thức tương đương a → b = ¬a ∨ b Bước 2. Thu hẹp phạm vi của toán tử ¬ về cho từng mục (term) đơn, sử dụng các tương đương: a. ¬(¬p) = p b. Luật De Morgan:¬(a ∧ b) = ¬a ∨ ¬b hay ¬(a ∨ b) = ¬a ∧ ¬b c. ¬∀X p(X) = ∃X ¬p(X) hay ¬∃X p(X) = ∀X ¬p(X) Bước 3. Chuẩn hóa các biến sao cho mỗi lượng tử chỉ kết nối với một biến duy nhất. Vì các biến chỉ đơn giản là các tên để ‘giữ chỗ’, nên quá trình này không làm ảnh hưởng đến chân trị của wff. Ví dụ: ∀X p(X) ∨ ∀X q(X) có thể chuyển thành ∀X p(X) ∨ ∀Y q(Y) Bước 4. Dịch chuyển tất cả các lượng tử về bên trái của công thức nhưng vẫn giữ nguyên thứ tự của chúng. Bước 5. Xóa bỏ các lượng tử tồn tại (∃). Chúng ta có thể loại bỏ lượng tử tồn tại bằng cách thay thế biến đó bằng một hàm sinh ra giá trị mong muốn. Ta chỉ cần một hàm mới cho mỗi lần thay thế như vậy. ∃Y president(Y) Ví dụ: được chuyển thành president(S1) Với S1 là một hàm tạo ra giá trị thỏa mãn vị từ president. Trong trường hợp lượng tử tồn tại xuất hiện bên trong phạm vi của lượng tử phổ biến, thì giá trị thỏa mãn vị từ này sẽ phải phụ thuộc vào giá trị của biến lượng tử tồn tại. Ví dụ: ∀X ∃Y father_of (Y,X) được chuyển thành ∀X father_of (S2(X),X) Các hàm (S1, S2) này được gọi là hàm Skolem. Đôi khi các hàm Skolem không có đối số được gọi là hằng Skolem như S2. Bước 6. Bỏ đi các tiền tố (lượng tử phổ biến) Bước 7. Chuyển công thức về dạng hội của các tuyển. Sử dụng luật phân phối ( a ∧ b) ∨ c = ( a ∨ c ) ∧ (b ∨ c) (a ∨ b) ∧ c = (a ∧ c) ∨ (b ∧ c) hay Ví dụ: (winter ∧ wearingboots) ∨ (summer ∧ wearingsandals) [ (winter ∨ (summer ∧ wearingsandals) ] ∧ [ wearingboots ∨ (summer ∧ wearingsandals)] (winter ∨ summer) ∧ 140 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 8: Suy Luận Tự Động (winter ∨ wearingsandals) ∧ (wearingboots ∨ summer) ∧ (wearingboots ∨ wearingsandals) Bước 8. Tạo ra các mệnh đề tách biệt tương ứng với từng toán hạng tuyển trên. Ví dụ ở bước 7: từ kết quả ở bước 7, ta có thể tách thành 4 mệnh đề. Bước 9. Chuẩn hoá các biến trong tập hợp các mệnh đề vừa tạo ở bước 8, nghĩa là đặt lại tên cho các biến sao cho không có hai mệnh đề có cùng tên biến. Câu hỏi : Hãy skolemize các biểu thức sau: 1. ∃ X dog(X) 2. (∀X) (∃Y) mother (X,Y) 3. (∀X) (∀Y) (∃Z) (∀ W ) ( foo(X, Y, Z, W)) Thí dụ 8.3: Áp dụng giải thuật trên, hãy chuyển câu vị từ ở ví dụ Thí dụ 8.1 về dạng mệnh đề : ∀X [roman (X) ∧ know (X,marcus) → [hate(X,caesar) ∨ (∀Y (∃Z hate(Y,Z) → thinkcrazy(X,Y) ) )]] Loại bỏ dấu → 1. ∀X [ ¬ (roman (X) ∧ know (X,marcus)) ∨ [hate(X,caesar) ∨ (∀Y ( ¬(∃Z hate(Y,Z)) ∨ thinkcrazy(X,Y)) )]] Đưa ¬ vào trong 2. ∀X [(¬roman (X) ∨ ¬know (X,marcus)) ∨ [hate(X,caesar) ∨ (∀Y (∀Z (¬hate(Y,Z) ) ∨ thinkcrazy(X,Y)))]] 3. Chuẩn hoá các biến 4. Dịch chuyển tất cả các lượng tử về bên trái: ∀X ∀Y ∀Z [(¬roman (X) ∨ ¬know (X,marcus) ) ∨ [hate(X,caesar) ∨ (¬hate(Y,Z) ∨ thinkcrazy(X,Y))]] 5. Xoá bỏ các lượng tử tồn tại 6. Bỏ đi lượng tử phổ biến [(¬roman (X) ∨ ¬know (X,marcus) ) ∨ [hate(X,caesar) ∨ (¬hate(Y,Z) ∨ thinkcrazy(X,Y))]] 7. Chuyển thành hội của các tuyển: vì trong công thức trên không còn toán tử And, nên ở đây ta chỉ đơn giản là bỏ đi các dấu ngoặc là ta có được công thức ở dạng mệnh đề như sau: ¬roman (X) ∨ ¬know (X,marcus) ∨ hate(X,caesar) ∨ ¬hate(Y,Z) ∨ thinkcrazy(X,Y) Câu hỏi : Đưa câu vị từ sau về dạng mệnh đề: ∀X ( a(X)→ b(X) ) ↔ ∃X q(X) Võ Huỳnh Trâm – Trần Ngân Bình 141
Giáo Trình Trí Tuệ Nhân Tạo II.2 Cơ sở của Hợp giải (Resolution): Thủ tục hợp giải là một quá trình lặp đơn giản: ở mỗi lần lặp, hai mệnh đề, gọi là mệnh đề cha, được so sánh (hay giải quyết - resolved), để tạo ra mệnh đề kết quả, trong đó những biến mệnh đề mâu thuẫn nhau sẽ bị loại bỏ. Để hiểu lý do loại bỏ hai biến mệnh đề mâu thuẫn này, ta xét một trường hợp sau. Giả sử trong hệ thống có hai mệnh đề (nghĩa là cùng lúc cả hai mệnh đề đều phải đúng): winter ∨ summer ¬winter ∨ cold và Tại bất kỳ thời điểm nào, chỉ có một trong hai biến mệnh đề winter và ¬winter là đúng. Nếu winter đúng, thì buộc cold phải đúng. Còn nếu ¬winter đúng thì buộc summer phải đúng. Vì vậy, từ hai mệnh đề trên có thể dẫn xuất thành: summer ∨ cold Đây chính là dẫn xuất mà hợp giải sẽ sử dụng. Hợp giải sẽ thao tác trên hai mệnh đề có chứa cùng biến mệnh đề (trong ví dụ trên là winter). Biến mệnh đề này phải ở dạng khẳng định trong một mệnh đề, và ở dạng phủ định trong mệnh đề kia. Kết quả đạt được bằng cách kết hợp hai mệnh đề cha trừ đi biến mệnh đề chung đó. Nếu mệnh đề kết quả là rỗng thì xem như đã tìm được sự mâu thuẫn (contradiction), nghĩa là mục tiêu đã được chứng minh. Trong hai phần kế tiếp, ta sẽ xét giải thuật hợp giải sử dụng trong hai trường hợp, đó là trường hợp vấn đề được biểu diễn bằng ngôn ngữ logic mệnh đề và trường hợp vấn đề được biểu diễn bằng ngôn ngữ logic vị từ. II.3 Giải thuật hợp giải dùng cho Logic mệnh đề: Cho trước: Tập hợp các tiên đề (axioms) F viết dưới dạng các câu trong phép tính mệnh đề. Yêu cầu: Chứng minh P 142 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 8: Suy Luận Tự Động * Giải thuật Hợp giải dùng cho Phép tính mệnh đề (Propositional Logic): Bước 1. Chuyển tất cả các câu trong F về dạng mệnh đề (clause form) Bước 2. Lấy phủ định P và chuyển về dạng mệnh đề. Thêm nó vào tập các mệnh đề vừa tạo ở bước 1. Bước 3. Lặp lại cho đến khi tìm thấy sự mâu thuẫn hoặc không thể tiếp tục: a. Chọn hai mệnh đề. Gọi là các mệnh đề cha. b. Hợp giải chúng. Mệnh đề kết quả là tuyển của tất cả các biến mệnh đề trong các mệnh đề cha trừ: nếu có bất kỳ các cặp biến mệnh đề L và ¬L, một nằm trong mệnh đề cha này, một nằm trong mệnh đề cha kia, thì chọn một cặp và xóa cả hai L và ¬L ra khỏi mệnh đề kết quả. c. Nếu mệnh đề kết quả là rỗng, thì xem như đã tìm được sự mâu thuẫn. Nếu không, thêm mệnh đề kết quả đó vào trong tập hợp các mệnh đề hiện có. Thí dụ 8.4: Các câu cho trước Chuyển về dạng mệnh đề P P (1) (P ∧ Q) → R ¬P ∨ ¬Q ∨ R (2) (S ∨ T) → Q ¬S ∨ Q (3) ¬T ∨ Q (4) T T (5) Hãy chứng minh R. Các bước thực hiện của thủ tục hợp giải được biểu diễn trong đồ thị hợp giải (hay cây hợp giải) dưới đây: ¬P ∨ ¬Q ∨ R ¬R ¬P ∨ ¬Q P ¬T ∨ Q ¬Q ¬T T II.4 Giải thuật hợp giải dùng cho Logic vị từ Trong trường hợp biểu diễn bằng Logic mệnh đề, việc xác định hai biến mệnh đề mâu thuẫn (không thể đúng cùng lúc) là rất dễ dàng, chỉ cần đơn giản tìm L và ¬L. Trong khi biểu diễn bằng Logic vị từ, quá trình đối sánh này phức tạp hơn vì cần phải xem xét các đối số của vị từ. Chẳng hạn như, man(John) và ¬man(John) thì mâu thuẫn, còn man(John) và ¬man(Spot) thì không. Vì vậy, để xác định các cặp mâu thuẫn, ta cần một thủ tục để so sánh các biến mệnh đề và tìm xem liệu có tồn tại tập phép thế nào làm cho chúng giống nhau. Đó chính là giải thuật đồng nhất (unification) mà ta đã thảo luận ở chương II. Cho trước: Tập hợp các tiên đề F viết dưới dạng các câu trong phép tính vị từ. Yêu cầu: Chứng minh P Võ Huỳnh Trâm – Trần Ngân Bình 143
Giáo Trình Trí Tuệ Nhân Tạo * Giải thuật Hợp giải dùng cho Phép tính vị từ (Predicate Logic): Bước 1. Chuyển tất cả các câu trong tập F về dạng mệnh đề (clause form) Bước 2. Lấy phủ định của P và chuyển về dạng mệnh đề. Thêm nó vào tập các mệnh đề vừa tạo ở bước 1. Bước 3. Lặp lại cho đến khi tìm thấy sự mâu thuẫn hay không thể tiếp tục: a. Chọn hai mệnh đề. Gọi là các mệnh đề cha. b. Hợp giải chúng. Mệnh đề kết quả là tuyển của tất cả các biến mệnh đề trong các mệnh đề cha với các phép thế phù hợp và trừ đi: nếu có một cặp biến mệnh đề T1 và ¬T2, sao cho T1 nằm trong mệnh đề cha này, còn ¬T2 nằm trong mệnh đề cha kia, và nếu T1 và T2 là hai biến mệnh đề có thể đồng nhất (unifiable), thì xóa cả hai T1 và ¬T2 ra khỏi mệnh đề kết quả. Ta nói T1 và T2 là các biến mệnh đề bù nhau (complementary literals). Sử dụng tập phép thế trả ra bởi giải thuật đồng nhất để tạo ra mệnh đề kết quả. Nếu có nhiều hơn một cặp biến mệnh đề bù nhau thì chỉ xóa một cặp. c. Nếu mệnh đề kết quả là rỗng, thì xem như đã tìm được sự mâu thuẫn. d. Nếu không, thêm mệnh đề kết quả đó vào trong tập hợp các mệnh đề hiện có. Việc lựa chọn mệnh đề nào để đưa vào hợp giải trước sẽ ảnh hưởng đến quá trình chứng minh cho mục tiêu. Vì vậy, để tăng tốc độ cho quá trình chứng minh này, một số chiến lược được đưa ra hỗ trợ cho việc lựa chọn này: − Chỉ hợp giải những cặp mệnh đề có chứa các biến mệnh đề bù nhau. − Loại bỏ các mệnh đề ngay khi chúng vừa được tạo ra trong quá trình hợp giải. Có hai loại mệnh đề có thể loại bỏ được là: mệnh đề luôn luôn đúng (tautology), và mệnh đề được tạo thành từ các mệnh đề khác (ví dụ P ∨ Q được tạo thành từ P). − Mỗi khi có thể, hãy hợp giải với một trong những mệnh đề là một phần của câu mà ta cần phản chứng hoặc với một mệnh đề được sinh ra do hợp giải với mệnh đề như vậy. Chiến lược này gọi là set-of-support. Nó phát sinh từ trực giác cho rằng sự mâu thuẫn mà chúng ta tìm kiếm phải liên quan đến câu mà ta đang muốn chứng minh. − Mỗi khi có thể, hợp giải với mệnh đề chỉ có một biến mệnh đề. Hợp giải này sẽ tạo ra mệnh đề mới với ít biến mệnh đề hơn các mệnh đề cha của nó, và vì vậy có thể nó sẽ gần đến mục tiêu là một mệnh rỗng hơn. Chiến lược này gọi là unit-preference. Thí dụ 8.5: Các câu trong thí dụ 8.1 được chuyển về dạng mệnh đề như sau: 1. man (marcus) 2. pompeian (marcus) ¬pompeian (X1) ∨ Roman (X1) 3. 4. ruler (caesar) ¬roman (X2) ∨ loyalto (X2, caesar) ∨ hate (X2, caesar) 5. 6. loyato (X3, fl(X3)) 144 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 8: Suy Luận Tự Động 7. ¬man (X4) ∨ ¬ ruler (Y1) ∨ ¬ tryassasinate (X4, Y1) ∨ loyalto (X4, Y1) 8. tryassasinate (marcus, caesar) Chứng minh: hate (marcus, caesar) ¬ hate (marcus, caesar) 5 marcus / X2 ¬ roman (marcus) ∨ loyalto (marcus, caesar) 3 marcus / X1 ¬ pompeian (marcus) ∨ loyalto (marcus, caesar) 2 7 loyalto (marcus, caesar) marcus /X4, caesar / Y1 ¬ man(marcus) ∨ ¬ruler(caesar) ∨ ¬ tryassasinate (marcus, caesar) 1 ¬ ruler (caesar) ∨ ¬ tryassasinate (marcus, caesar) 4 ¬ tryassasinate (marcus, caesar) 8 (đpcm) Đến đây, chúng ta đã biết cách thức sử dụng hợp giải một cách cơ bản để chứng minh cho các vấn đề được biểu diễn ở ngôn ngữ logic mệnh đề hay logic vị từ. Phần kế tiếp chúng ta sẽ thảo luận về tính chất dừng của thủ tục này, nghĩa là thủ tục có khả năng phát hiện các trường hợp không tồn tại sự mâu thuẫn và kết thúc việc chứng minh. Hai phần kế tiếp nữa sẽ thảo luận về sự mở rộng của ngôn ngữ logic vị từ hỗ trợ cho sự tính toán, và trả lời câu hỏi. 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: Đối với những vấn đề không chứng minh được, nghĩa là quá trình hợp giải không thể kết thúc bằng kết quả rỗng, thì hợp giải vẫn có khả năng phát hiện được những tình huống này, và cho phép thủ tục dừng, đồng thời đưa ra kết luận là không thể chứng minh được. Giả sử với câu hỏi đưa ra là ‘Did Marcus hate Caesar?’. Trong trường hợp này, ta có thể sẽ đưa ra câu cần chứng minh là ¬ hate (marcus, caesar). Để chứng minh câu này, ta thêm vào tập hợp các mệnh đề một mệnh đề: hate (marcus, caesar) Và bắt đầu chứng minh. Nhưng ngay lập tức ta sẽ thấy là việc chứng minh không thể được tiếp tục vì không có mệnh đề nào chứa biến mệnh đề ¬hate. Vì vậy, ta có thể kết luận hate (marcus, caesar) sẽ không tạo ra sự mâu thuẫn nào với các câu đã cho. Võ Huỳnh Trâm – Trần Ngân Bình 145
Giáo Trình Trí Tuệ Nhân Tạo Đôi khi hợp giải không phát hiện tình huống này ngay bước khởi đầu, mà có thể sau một vài bước hợp giải như trong ví dụ sau. Thí dụ 8.6: Giả sử trong cơ sở tri thức của ta có thêm hai câu: persecute(X,Y) → hate(Y,X) ¬persecute(X5,Y2) ∨ hate(Y2,X5) 9. hate(X,Y) → persecute(Y,X) ¬hate(X6,Y3) ∨ persecute(Y3,X6) 10. Ta cần chứng minh: loyalto (marcus, caesar) ¬ loyalto (marcus, caesar) 5 marcus / X2 ¬ roman (marcus) ∨ hate (marcus, caesar) 3 marcus /X1 ¬ pompeian (marcus) ∨ hate (marcus, caesar) 2 hate (marcus, caesar) 10 marcus / X6 , caesar /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) ¬man(X1) ∨ mortal (X1) 4. ¬pompeian (X2) ∨ died (X2,79) 5. 6. erupted (volcano,79) ¬mortal (X3) ∨ ¬born (X3, T1) ∨ ¬gt(T2 – T1,150) ∨ dead(X3,T2) 7. 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) ¬ alive (marcus, now) Chứng minh: alive (marcus, now) 9a marcus / X4, now/T3 10 dead (marcus, now) marcus/X6, now/T6 ¬ dead (marcus, T5) ∨ ¬ gt(now, T5) 5 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. ⇒ ∀T ¬died(marcus, T) Chuyển về dạng mệnh đề, nó sẽ là: ⇒ ¬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) ∨ died(marcus,79) pompeian(marcus) 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) ¬judge(X) ∨ crooked(X) ∨ educated(X) Chuyển về dạng mệnh đề: 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 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 : a ∧ ((a ∧ x) → d) 1. (a → (b ∧ c)) ∧ x 2. ( c → a ) → (d ∧ e ) 3. b → (( d ∧ x) → f) 4. ( e ∧ b) → f 5. ( e ∧ y) → g 6. d→f 7. f → ( ¬ a ∨ g) 8. 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. 150 Võ Huỳnh Trâm – Trần Ngân Bình
Chương 9: Học máy 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 Võ Huỳnh Trâm – Trần Ngân Bình 151