Chương 1 Tổng quan về logic và tích hợp tri thức 1.1 Tổng quan về logic Phương pháp tích hợp dựa trên logic đã nhận được rất nhiều sự chú ý trong nhiều lĩnh vực của khoa học máy tính, chẳng hạn như các hệ thống thông tin có cộng tác, cơ sở dữ liệu phân tán, hệ thống đa tác tử và các hệ thống chuyên gia phân tán. Trong mô hình logic, mỗi nguồn thông tin thường được coi như là một cơ sở tri thức và được biểu diễn là một tập hợp của các công thức logic. Một trong những vấn đề quan trọng của tích hợp nhiều cơ sở tri thức là đối phó với vấn đề không nhất quán. Mặc dù có thể mỗi cơ sở tri thức là nhất quán, tuy nhiên khi ta đặt chúng với nhau thì chúng có thể làm phát sinh những mâu thuẫn.
Trong logic mệnh đề vấn đề không nhất quán thường được giải quyết bằng tích hợp tri thức. Phương pháp tích hợp bằng logic mệnh đề được chia làm hai loại: Tích hợp ở mức cú pháp (công thức logic) và tích hợp ở mức ngữ nghĩa (mô hình). Loại thứ nhất dựa trên việc lựa chọn một vài tập con nhất quán có được khi hợp nhất các cơ sở tri thức ban đầu còn loại thứ hai thì được xác định bởi mối quan hệ nhị phân trên tập các diễn giải. Các thông tin được ưu tiên đóng một vai trò quan trọng trong việc giải quyết vấn đề không nhất quán khi các cơ sở tri thức được tích hợp.
Logic khả năng [28] đã cung cấp một mô hình linh hoạt để biểu diễn các thông tin được ưu tiên và đối phó với vấn đề không nhất quán. Ở mức độ cú pháp, thông tin được biểu diễn là một công thức logic có gắn trọng số, trọng số này được hiểu là mức độ chắc chắn của công thức này. Một cơ sở tri thức khả năng (Possibilistic Knowledge Base (PKB)) là một tập các công thức có trọng số. Ở mức độ ngữ nghĩa, nó dựa trên khái niệm của hàm phân phối khả năng, đó là một ánh xạ từ tập các diễn giải Ω vào r0, 1s để đại diện cho thông tin có sẵn.1 Logic cổ điển Chúng ta xem xét một ngôn ngữ mệnh đề L được xác định từ một tập hữu hạn các biến mệnh đề P và các hằng số tJ, Ku.
Ký hiệu W dùng để ký hiệu tập của các thế giới có thể, trong đó mỗi thế giới có thể là một hàm từ P vào tJ, Ku. Một mô hình của công thức φ là một thế giới có thể ω làm cho φ đúng, ký hiệu là ω ( φ. Với Φ là một tập của các công thức, rΦs biểu diễn tập các mô hình của Φ, nghĩa là rΦs “ tω P W |@φ P Φpω ( φqu. Chúng ta sử dụng ký hiệu rφs để thay thế cho rtφus.
Chúng ta cũng sử dụng ký hiệu $ để biểu diễn cho mối quan hệ hệ quả, ví dụ 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com tφ, ψ u $ θ nghĩa là θ là hệ quả logic của {φ, ψ}. Một cơ sở tri thức (phẳng) K là tập hữu hạn các công thức, nó có thể xem là tương đương về logic với công thức φ khi nó là kết hợp của tất cả các công thức của K. , Kn là n cơ sở tri thức và một số trong số chúng có thể tương đương logic với nhau, một hồ sơ tri thức E của n cơ sở tri thức là một đa tập (multi- set)1 E “ tK1 ,. , φm u, chúng ta ký hiệu ^K “ ^m i“1 φi và n ^E “ ^i“1 p^Ki q.
K là nhất quán khi và chỉ khi ω |ù K đối với ít nhất một thế giới có thể ω. Hai cơ sở tri thức K và K 1 là tương đương, ký hiệu K ” K 1 , khi và chỉ khi @φ P K, K 1 $ φ và ngược lại. Một tập tri thức E 1 “ tK11 ,. , Kn1 u là tương đương logic với một tập tri thức E “ tK1 ,.
, Kn u, ký hiệu E ” E 1 , khi và chỉ khi tồn tại một hoán vị σ trên tập {1,. ,n} sao cho Ki ” Kσ1 piq với mọi i “ 1,. Hợp của hai tập tri thức E và E 1 cũng là một tập tri thức E \ E 1 “ tK1 , .2 Logic khả năng Ở mức độ ngữ nghĩa logic khả năng dựa trên khái niệm của một hàm phân phối khả năng (possibility distribution) ký hiệu bằng π, là một ánh xạ từ tập các diễn giải Ω vào r0, 1s để đại diện cho thông tin có sẵn. π pω q thể hiện mức độ phù hợp của diễn giải ω đối với những tri thức sẵn có.
Quy ước, π pω q “ 1 có nghĩa là chúng ta hoàn toàn có thể cho ω là một thế giới thực (hoặc ω thỏa mãn hoàn toàn), 1 ą π pω q ą 0 có nghĩa ω chỉ thỏa mãn được một phần, trong khi π pω q “ 0 có nghĩa ω chắc chắn không phải là một thế giới thực (hoặc không đáp ứng tất cả). Từ một hàm phân bố khả năng π ta có thể xác định được độ có thể (possibility degree) của công thức φ ký hiệu là Πpφq “ maxtπ pω q|ω P Ω, ω |ù φu. Đó là mức độ đòi hỏi của công thức φ đối với với những tri thức có sẵn và độ chắc chắn (necessity degree) của mỗi công thức φ : N pφq “ 1 ´ Πp φq đối với các thông tin có sẵn, N pφq “ 1 có nghĩa φ là phần thông tin hoàn toàn chắc chắn hoặc một mục tiêu bắt buộc, trong khi N pφq “ 0 thể hiện sự không có thông tin đối với φ nhưng không có nghĩa là φ sai. Ở mức độ cú pháp, một công thức được gọi là một công thức khả năng được xác định bằng một cặp pφ, aq trong đó φ là một công thức mệnh đề và a P r0, 1s.
Cặp pφ, aq có nghĩa là mức độ chắc chắn của φ ít nhất bằng apN pφq ě aq. Một PKB là một tập hữu hạn các công thức khả năng có dạng B “ tpφi , ai q : i “ 1,. Chúng ta ký hiệu B ˚ là cơ sở tri thức phẳng liên kết với B, cụ thể là các cơ sở tri thức thu được từ B bằng cách loại bỏ đi các trọng số của công thức pB ˚ “ tφi |pφi , ai q P B uq. Một PKB B là nhất quán khi và chỉ khi B ˚ là nhất quán.
Cho một PKB B, hàm phân phối khả năng của B ký hiệu là πB được xác định như sau [27]: Định nghĩa 1. @ω P Ω " 1 nếu @pφi , ai q P B, ω |ù φi πB pω q “ 1 ´ maxtai : pφi , ai q P B và ω * φi u ngược lại 1 Đa tập là tập hợp mà các phần tử của nó có thể giống nhau 2 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.1 tại trang 5) Cho B “ tp c; 0.4qu là một cơ sở tri thức. Từ Định nghĩa 1.1, ta có thể xác định được phân phối khả năng của B như sau: - πB pa b cq “ πB pab cq “ 0.5, - πB p ab cq “ πB p a b cq “ 0.2, - πB pabcq “ πB pa bcq “ πB p abcq “ πB p a bcq “ 0. [27] Cho B là PKB và a P r0, 1s.
Chúng ta gọi a-cut (tương ứng, strict a-cut) của B, ký hiệu là Běa (tương ứng, Bąa ) là tập của các công thức mệnh đề trong B có mức độ chắc chắn ít nhất bằng a pBěa “ tφ P B ˚ |pφ, bq P B, b ě auq (tương ứng, lớn hơn a pBąa “ tφ P B ˚ |pφ, bq P B, b ą auq). [27] Cho B1 và B2 là hai PKB. B1 và B2 được gọi là tương đương ký hiệu là B1 ” B2 nếu πB1 “ πB2. Sự tương đương của hai PKB cũng có thể xác định như sau: B1 ” B2 nếu pB1 qěa ” pB2 qěa.
[27] Độ không nhất quán của PKB B được xác định như sau: IncpB q “ maxtai : Běai là không nhất quánu Độ không nhất quán của B là trọng số lớn nhất ai sao cho ai ´ cut của B là không nhất quán. Với IncpB q “ 0 thì B là nhất quán Định nghĩa 1. [27] Cho pφ, aq là một công thức trong B. pφ, aq được gọi là ngưỡng trong B nếu: pB ´ pφ, aqqěa $ φ Vàpφ, aq được gọi là ngưỡng chặt trong B nếu Bąa $ φ.
Công thức ngưỡng trong một vài trường hợp cần thiết được chỉ ra trong các bổ đề sau: Bổ đề 1. Cho pφ, aq là một công thức ngưỡng trong B. Thì B và B 1 “ B ´ pφ, aq là tương đương. [27] Cho B là một PKB.
Công thức φ được gọi là kết luận hợp lý của B nếu: BąIncpB q $ φ Định nghĩa 1. [27] Cho B là một PKB. Công thức pφ, aq là một kết luận khả năng của B, ký hiệu B $π pφ, aq, nếu: - BąIncpB q $ φ - a ą IncpB q và @b ą a, Bąb & φ Suy luận khả năng yêu cầu trọng số của công thức mệnh đề phải lớn hơn độ không nhất quán của B bởi vì với mỗi công thức mệnh đề pφ, aq. Nếu a ď IncpB q thì Běa $ φ.
Nghĩa là pφ, aq có thể được suy ra từ B. 3 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Với mỗi PKB B không nhất quán, các công thức có mức độ chắc chắn mà không lớn hơn IncpB q thì sẽ không được sử dụng trong suy diễn. Tiếp tục Ví dụ 1.1, rõ ràng B tương đương với B 1 “ tpa, 0.5qu bởi vì IncpB q “ 0.4q không được sử dụng trong suy luận khả năng. Ta có ngưỡng pB q “ t b _ a, c _ bu, kết luận hợp lý pB q = tpaq, p cq, p b _ aq, p c _ bqu và kết luận khả năng pB q = tp b _ a, 0.2 Tổng quan về tích hợp tri thức 1.1 Biểu diễn tri thức Ngày nay việc giải quyết sự không nhất quán là một trong các lĩnh vực nghiên cứu chính trong trí tuệ nhân tạo.
Không nhất quán thể hiện sự thiếu (hoặc thừa) thông tin cho quá trình suy luận. Do đó, việc giải quyết sự không nhất quán của tri thức là một nhiệm vụ quan trọng trong việc quản lý tri thức. Sự không nhất quán thường xảy ra do các thông tin thường đến từ các nguồn khác nhau và từ đó nảy sinh sự mâu thuẫn.