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.
17 trang |
Chia sẻ: thienmai908 | Lượt xem: 1513 | Lượt tải: 0
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:
- Chap2.pdf