Trí tuệ nhân tạo như là biểu diễn và tìm kiếm

Phép hợp nhất (unification) là một thuật toán dùng đểxác định những phép thế cần thiết để

làm cho hai biểu thức vị từ đối sánh (match) nhau.

Hợp nhất và các luật suy diễn khác nhưModus ponens cho phép chúng ta tạo ra các suy diễn

dựa trên một tập hợp các khẳng định logic. Phép hợp nhất phức tạp do có thể thay thế một

biến với bất kỳ mục nào gồm cảnhững biến và những biểu thức hàm khác với độ phức tạp

tùy ý. Những biểu thức này tự thân chúng lại có thể chứa các biến.

pdf17 trang | Chia sẻ: thienmai908 | Lượt xem: 1505 | Lượt tải: 0download
Nội dung tài liệu Trí tuệ nhân tạo như là biểu diễn và tìm kiếm, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
của các phép thế biến. Điều này được phát biểu trong giải thuật đối sánh mẫu. II.2 Giải thuật đối sánh mẫu 1. Hằng / hằng đối sánh : chỉ khi chúng giống hệt nhau 2. Hằng a / biến X đối sánh: a. Biến chưa kết buộc: biến trở thành kết buộc với hằng {a/X} b. Biến đã kết buộc : xem (1) 3. Biến / biến đối sánh: a. Hai biến chưa kết buộc: luôn luôn đối sánh b. Một biến kết buộc và một biến chưa kết buộc: xem (2) 12 Võ Huỳnh Trâm – Trần Ngân Bình Chương 9: Học máy Võ Huỳnh Trâm – Trần Ngân Bình c. Hai biến kết buộc: xem (1) 4. Biểu thức / biểu thức đối sánh: chỉ khi các tên hàm hoặc vị từ, số ngôi giống nhau thì áp dụng đối sánh từng đối số một. Lưu ý : Phạm vi của một biến là một câu. Một khi biến đã bị kết buộc, các phép hợp nhất theo sau và các suy luận kế tiếp phải giữ sự kết buộc này. Câu hỏi : Hợp nhất các cặp biểu thức dưới đây, chỉ ra các giá trị đối sánh (nếu có) hoặc giải thích tại sao chúng không thể hợp nhất : a) P(X, Y) và p(a, Z) b) P(X, X) và p(a, b) c) ancestor(X, Y) và ancestor(bill, father(bill)) d) ancestor(X, father(X)) và ancestor(david, george) e) q(X) và ¬ q(a) II.3 Ứng dụng : Chương trình tư vấn tài chính Họat động của chương trình là trợ giúp người dùng trong việc quyết định có nên đầu tư vào một tài khoản tiết kiệm hay thị trường chứng khoán hay không, một số nhà đầu tư cũng có thể muốn phân bổ số tiền của họ thành hai khoản. Việc đầu tư sẽ được gợi ý cho những nhà đầu tư dựa trên thu nhập của họ và số tiền hiện tại mà họ đã có trong tài khoản tiết kiệm. Hệ làm việc theo các quy tắc sau : 1. Các cá nhân không đủ tiền tiết kiệm cần ưu tiên tăng tiền tiết kiệm, bất kể thu nhập là bao nhiêu. 2. Các cá nhân có đủ tiền tiết kiệm và đủ thu nhập nên xem xét việc đầu tư mạo hiểm hơn nhưng có khả năng đem lại lợi nhuận hơn vào thị trường chứng khoán. 3. Các cá nhân với thu nhập thấp nhưng đủ tiền tiết kiệm có thể chia phần thu nhập thêm vào tiết kiệm và chứng khoán, nhằm làm tăng số tiền tiết kiệm trong khi vẫn muốn tăng thu nhập thông qua chứng khoán. Sự tương xứng giữa tiền tiết kiệm và thu nhập được xác định bởi số thành viên gia đình mà một cá nhân cần chu cấp. Quy tắc là : - Tiết kiệm đủ là 5000$/ người phụ thuộc - Thu nhập đủ 15000$ + (4000$ / người phụ thuộc) Ta xây dựng hệ thống logic với các câu vị từ như sau: 1. savings_account(inadequate) ⇒investment(saving) 2. savings_account(adequate) ∧ income(adequate) ⇒ investment(stocks) 3. savings_account(adequate) ∧ income(inadequate) ⇒ investment(combination) 13 Giáo Trình Trí Tuệ Nhân Tạo 4. ∀X amount_saved(X) ∧ ∃Y(dependents(Y) ∧ greater(X,minsavings(Y))) ⇒ savings_account(adequate) 5. ∀X amount_saved(X) ∧ ∃Y(dependents(Y) ∧ ¬greater(X,minsavings(Y))) ⇒ savings_account(inadequate) 6. ∀X earning(X, steady) ∧ ∃Y(dependents(Y) ∧ greater(X,minincome(Y))) ⇒ income(adequate) 7. ∀X earning(X, steady) ∧ ∃Y(dependents(Y) ∧ ¬greater(X,minincome(Y))) ⇒ income(inadequate) 8. ∀X earning(X, unsteady) ⇒ income(inadequate) With: minsavings(X) = 5000 * X minincome(X)=15000+(4000*X) Để thực hiện một phiên tư vấn, thông tin mô tả về một nhà đầu tư nào đó được bổ sung vào tập hợp các câu vị từ. Chẳng hạn một cá nhân với 3 thành viên phụ thuộc, có số tiền trong tài khoản tiết kiệm là 22.000$ và có thu nhập ổn định là 25.000$ sẽ được mô tả như sau : 9. amount_saved(22000) 10. earnings(25000,steady) 11. dependents(3) Sử dụng phép hợp nhất và modus ponens, một chiến lược đầu tư đúng đắn người này có thể được rút ra như là một hệ quả logic từ những mô tả này : Hợp giải (10), (11) với (7) bằng đối sánh {25000/X, 3/Y}, ta có : 12. income(inadequate) Hợp giải (9), (11) với (4) bằng đối sánh {22000/X, 3/Y}, ta có : 13. savings_account(adequate) Hợp giải (12), (13) với (3) ⇒ investment (combination) Như vậy hình thức đầu tư được tư vấn từ hệ là kết hợp cả việc gởi tiền vào tài khoản tiết kiệm và đầu tư vào chứng khoán. TỔNG KẾT CHƯƠNG II: Trong chương này, chúng ta đã được giới thiệu phép tính vị từ như một ngôn ngữ biểu diễn dùng cho việc giải quyết vấn đề trong AI. Chúng ta đã định nghĩa các khái niệm về biến, hàng, hàm, biểu thức, … và ngữ nghĩa của ngôn ngữ này. Dựa trên ngữ nghĩa của phép tính vị từ, các luật suy diễn cũng cho phép suy diễn các câu từ một tập hợp các biểu thức cho trước. Phần cuối chương định nghĩa một thuật toán hợp nhất và đối sánh mẫu dùng xác định các phép thay thế biến làm cho hai biểu thức đối sánh nhau, một ví dụ minh họa ứng dụng cụ thể cho giải thuật này là bài toán hệ tư vấn tài chính. Trong chương tiếp theo, lý thuyết và những kỹ thuật tìm kiếm trên không gian trạng thái bài toán sẽ được giới thiệu. 14 Võ Huỳnh Trâm – Trần Ngân Bình Chương 9: Học máy Võ Huỳnh Trâm – Trần Ngân Bình 15 III BÀI TẬP CHƯƠNG 2 II.1. Jane có bốn thành viên gia đình phụ thuộc, thu nhập bằng lương hàng tháng là 30.000$ và tài khoản tiết kiệm của cô ta là 20.000$. Hãy đưa ra các vị từ thích hợp mô tả tình trạng tài chính của Jane cho chương trình tư vấn tài chính và tiến hành các phép hợp nhất, suy diễn cần thiết để xác định phương thức đầu tư thích hợp cho cô ta. II.2. Chuyển các câu sau đây thành câu trong logic vị từ: a) Tất cả các con mèo đều là động vật. b) Không có con chó nào là loài bò sát. c) Tất cả các nhà khoa học máy tính đều thích một hệ điều hành nào đó. d) Mọi đứa trẻ đều thích Coca-cola. e) Không có đứa trẻ nào thích ăn rau. f) Một số người thích kẹo, một số khác thì không. g) Không có sinh viên nào học mà thi rớt môn này. II.3. Cho một vấn đề được phát biểu như sau: 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 vấn đề trên theo logic vị từ bậc nhất. 2. Dùng giải thuật đối sánh mẫu để chứng minh “John thích đậu phộng” II.4. Câu chuyện dưới đây được lấy từ quyển sách Algorithms + Data structures = Programs (Thuật toán + Cấu trúc dữ liệu = Chương trình) của N. Wirth (1976): “Tôi cưới một góa phụ (W), bà ta có một cô con gái đã lớn (D). Cha tôi (F), người thường xuyên đến thăm chúng tôi đã phải lòng cô con riêng của vợ tôi và cưới cô ta. Vì thế cha tôi trở thành con rể tôi và con ghẻ tôi trở thành mẹ tôi. Vài tháng sau đó, vợ tôi sinh một đứa con trai (S1), nó trở thành em rể của bố tôi, cũng như trở thành chú tôi. Vợ của bố tôi, tức là con ghẻ của tôi, cũng sinh một đứa con trai (S2).” Sử dụng phép tính vị từ, hãy tạo ra một tập hợp các biểu thức biểu diễn hoàn cảnh trong câu chuyện trên. Hãy đưa ra các biểu thức định nghĩa các quan hệ gia đình cơ bản như định nghĩa bố vợ chẳng hạn, và sử dụng modus ponens trên hệ này để chứng minh kết luận “Tôi cũng chính là ông tôi”. Giáo Trình Trí Tuệ Nhân Tạo 16 Võ Huỳnh Trâm – Trần Ngân Bình Chương 9: Học máy Võ Huỳnh Trâm – Trần Ngân Bình 17 PHẦN II ....................................................................................................................................1 TRÍ TUỆ NHÂN TẠO NHƯ LÀ .............................................................................................1 BIỂU DIỄN VÀ TÌM KIẾM ....................................................................................................1 Chương II ..................................................................................................................................6 LOGIC HÌNH THỨC ...............................................................................................................6 I. PHÉP TÍNH MỆNH ĐỀ ..............................................................................................7 I.1. Định nghĩa – Ký hiệu phép tính mệnh đề............................................................7 I.2. Ngữ nghĩa của phép tính mệnh đề.......................................................................8 I.3. Phép tính vị từ .....................................................................................................9 I.4. Ngữ nghĩa - Phép tính vị từ ...............................................................................10 I.5. Phép tính vị từ bậc nhất (First – order predicate calculus) ...............................11 I.6. Các luật suy diễn ...............................................................................................11 II. ĐỐI SÁNH MẪU VÀ PHÉP HỢP NHẤT................................................................12 II.1. Phép hợp nhất ....................................................................................................12 II.2. Giải thuật đối sánh mẫu.....................................................................................12 II.3. Ứng dụng : Chương trình tư vấn tài chính ........................................................13 BÀI TẬP CHƯƠNG II ............................................................................................15

Các file đính kèm theo tài liệu này:

  • pdfChap2.pdf