Tóm tắt Luận văn Tích hợp tri thức sử dụng các kỹ thuật tranh cãi

i LỜI CAM ĐOAN Tôi xin cam đoan luận văn “Tích hợp tri thức sử dụng các kỹ thuật tranh cãi" là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả được trình bày trong luận văn là hoàn toàn trung thực. Tôi đã trích dẫn đầy đủ các tài liệu tham khảo, công trình nghiên cứu liên quan. Ngoại trừ các tài liệu tham khảo này, luận văn hoàn toàn là công việc của riêng tôi. Luận văn được hoàn thành trong thời gian tôi là học viên tại Khoa Công nghệ Thông tin, Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội. Hà Nội, ngày 19 tháng 9 năm 2016 Học viên Nguyễn Trần Vân ii LỜI CAM ĐOAN .................................................................................. i MỞ ĐẦU ............................................................................................. iv Chương 1. Tổng quan về logic và tích hợp tri thức .............................. 1 1.1. Tổng quan về logic ....................................................... 1 1.1.1. Logic cổ điển ............................................................ 1 1.1.2. Logic khả năng ......................................................... 2 1.2. Tổng quan về tích hợp tri thức ...................................... 3 1.2.1. Biểu diễn tri thức ...................................................... 3 1.2.2. Duyệt tri thức ............................................................ 6 1.2.2.1. Mô hình AGM ...................................................... 6 1.2.2.1.1. Bộ định đề AGM cho duyệt tri thức ..................... 6 1.2.2.1.2. Bộ định đề AGM cho loại bỏ tri thức ................... 7 1.2.2.2. Hàm lựa chọn ........................................................ 7 1.2.2.3. Cố thủ tri thức ....................................................... 7 1.2.2.4. Hệ thống các khối cầu tri thức .............................. 7 1.2.3. Tích hợp tri thức ....................................................... 8 1.2.3.1. Một mô hình cho tích hợp với ràng buộc toàn vẹn 8 1.2.3.2. Tích hợp ở mức cú pháp ....................................... 9 1.2.3.3. Phương pháp dựa trên khoảng cách .................... 10 Chương 2. Mô hình tranh luận ........................................................... 12 2.1. Sự chấp nhận của tranh luận ....................................... 12 2.1.1. Mô hình tranh luận ................................................. 12 2.1.2. Ngữ nghĩa cố định và ngữ nghĩa cơ sở (hoài nghi) 13 2.1.3. Điều kiện cho sự trùng giữa ngữ nghĩa khác nhau . 15 2.2. Tranh luận, trò chơi n-người và bài toán hôn nhân bền vững 16 2.2.1. Tranh luận trong trò chơi n -người ......................... 16 2.2.2. Tranh luận và bài toán hôn nhân bền vững ............. 16 Chương 3. Tích hợp tri thức có ưu tiên trong mô hình logic khả năng ............................................................................................................ 17 iii 3.1. Tích hợp tri thức bằng tranh luận trong logic khả năng 17 3.2. Định đề và một số tính chất ........................................ 20 Chương 4. Thực nghiệm và đánh giá ................................................. 21 4.1. Môi trường thực nghiệm ............................................. 22 4.2. Quá trình thực nghiệm ................................................ 22 4.2.1. Giới thiệu về chương trình ...................................... 22 4.2.2. Tập dữ liệu thực nghiệm ......................................... 22 4.2.3. Kết quả thực nghiệm thu được của tập dữ liệu thứ nhất 22 4.2.4. Kết quả thực nghiệm thu được của tập dữ liệu thứ hai 22 4.2.5. Đánh giá kết quả thực nghiệm và hướng nghiên cứu tiếp theo 23 Kết luận .............................................................................................. 24 iv MỞ ĐẦU Ngày nay tích hợp tri thức là một trong các vấn đề nghiên cứu với các ứng dụng quan trọng trong Khoa học máy tính. Mục tiêu chính của tích hợp tri thức là nhằm đạt được các tri thức chung từ các nguồn tri thức riêng lẻ. Vấn đề này được ứng dụng rộng rãi trong nhiều lĩnh vực của khoa học máy tính như tích hợp dữ liệu [1], khôi phục thông tin [2], gộp dữ liệu cảm biến [3], các hệ đa tác tử [4] và các hệ thống đa phương tiện (Multimedia) [5, 6]. Vấn đề tích hợp tri thức bắt đầu được quan tâm, nghiên cứu, phát triển và áp dụng cho một số lĩnh vực trong đời sống, xã hội, kinh tế, an ninh quốc phòng,... Một trong các ví dụ thực tế đó là hiện nay đã có một số hệ thống dự báo kinh tế của Việt Nam như hệ thống của CIA1, hệ thống của WordBank2..., mỗi hệ thống đưa ra một bộ các chỉ số phát triển của nền kinh tế nước ta. Tuy nhiên bộ Kế hoạch đầu tư không thể lấy ngay kết quả của dự báo từ một trong các hệ thống này để báo cáo lên Chính phủ hay Quốc hội được. Thay vào đó Trung tâm Thông tin và Dự báo kinh tế - xã hội quốc gia của bộ Kế hoạch và đầu tư phải tổng hợp thông tin từ các nguồn đó thành một thông tin duy nhất mà phản ánh được thực trạng kinh tế của Việt Nam rồi sau đó mới báo cáo kết quả này lên Chính phủ hay Quốc hội. Hiện nay có nhiều cách tiếp cận để tích hợp tri thức khác nhau như [7, 8]. Tuy nhiên tất cả các cách tiếp cận này đều dựa trên giả thuyết là các bên tham gia đều có tính cộng tác, tức là để các bên đạt được thỏa thuận chung khi mà mỗi bên đều có một số đòi hỏi và các đòi hỏi này mâu thuẫn nhau thì các bên cần thỏa thuận với nhau để mỗi bên hy sinh đi một số đòi hỏi của mình nhằm đạt được sự đồng 1 https://www.cia.gov/library/publications/the-world-factbook/geos/vm.html. 2 v thuận. Các tiếp cận này chưa phản ánh được đúng cách làm việc trong thực tế. Chẳng hạn như bên A có các đòi hỏi là hoàn toàn hợp lý và có đầy đủ bằng chứng, lập luận để bảo vệ ý kiến của mình còn bên B các đòi hỏi hoàn toàn vô lý và không có bằng chứng lập luận gì cả. Nếu theo các tiếp cận truyền thống, hai bên sẽ cùng bớt đi một số đòi hỏi nào đó của mình để đạt được một thỏa thuận chung, điều này là vô lý vì bên B sẽ được hưởng lợi mặc dù mọi đòi hỏi đều không hợp lý và bên A sẽ bị mất một phần quyền lợi chính đáng của mình. Trong luận văn này tôi đề ra một cách tiếp cận mới cho việc tích hợp tri thức nhằm khắc phục những hạn chế của các tiếp cận hiện có. Ý tưởng chính của tiếp cận này như sau: Để đạt được thỏa thuận giữa các bên, ta sẽ để cho các bên tranh luận với nhau, tức là các bên sẽ dùng lý lẽ, lập luận để bảo vệ cho các đòi hỏi của mình đồng thời phản bác lại các đòi hỏi của đối phương, bên nào có nhiều chứng cứ, lập luận tốt hơn thì bên đó sẽ giành được nhiều lợi ích hơn. Để làm được điều này, một mô hình tích hợp cơ sở tri thức khả năng được đề xuất dựa trên một mô hình tranh luận nổi tiếng được đề xuất bởi GS. Phạm Minh Dũng [24]. Bên cạnh đó, một tập các tiên đề cho tích hợp tri thức bằng tranh luận cũng được giới thiệu và các tính chất logic của nó cũng được đem ra thảo luận. Một chương trình thực nghiệm tích hợp tri thức dựa trên mô hình đã đề xuất và các đánh giá về nó được tiến hành. Nội dung chính của luận văn bao gồm các phần: Tổng quan về logic và tích hợp tri thức. Chương này trình bày các kiến thức cơ sở về logic và tích hợp tri thức bao gồm: logic cổ điển, logic khả năng, biểu diễn tri thức, duyệt tri thức và tích hợp tri thức. Mô hình tranh luận. Chương này trình bày về mô hình tranh luận của GS. Phạm Minh Dũng cùng với các ngữ nghĩa của mô hình này. Các mô hình tích hợp tri thức bằng tranh cãi. Chương này là nội dung chính của luận văn, trong đó trình bày cách tiếp cận để giải vi quyết thông tin mâu thuẫn bằng tích hợp tri thức có ưu tiên trong mô hình logic khả năng. Thực nghiệm và đánh giá. Trong chương này tôi tiến hành cài đặt một chương trình tích hợp tri thức như trong mô hình đề xuất và đánh giá các kết quả đạt được. Tóm lược những kết quả đã đạt được của luận văn và đưa ra định hướng nghiên cứu trong tương lai. 1 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 nhân 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. 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). 1.1.1. Logic cổ điển Chúng ta xem xét một ngôn ngữ mệnh đề ℒ được định từ một tập hữu hạn các biến mệnh đề 𝒫 và các hằng số {⊺, ⊥}. Ký hiệu 𝒲 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ừ 𝒫 vào {⊺, ⊥}. xác 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, [Φ] biểu diễn tập các mô hình của Φ, nghĩa là [Φ] = {𝜔 ∈ 𝒲 |∀𝜙 ∈ Φ (𝜔 ⊨ 𝜙)}. Chúng ta sử dụng ký hiệu [𝜙] để thay thế cho[{𝜙}]. Chúng ta cũng sử dụng ký hiệu ⊢ để biểu diễn cho mối quan hệ hệ quả, ví dụ {𝜙, 𝜓} ⊢ 𝜃 nghĩa là 𝜃 là hệ quả logic của {𝜙, 𝜓}. Một cơ sở tri thức (phẳng) 𝐾 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 . Cho nKK ,,1  là n cơ 2 sở tri thức và một số trong số chúng có thể tương đương logic với nhau, một tập tri thức E của n cơ sở tri thức là một đa tập (multi-set)3 },,{= 1 nKKE  . Giả sử },,{= 1 mK   , chúng ta ký hiệu i m iK 1==  và )(= 1= i n i KE  . K là nhất quán khi và chỉ khi 𝜔 ⊨ 𝐾 đối với ít nhất một thế giới có thể 𝜔. 1.1.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 ký hiệu bằng 𝜋, là một ánh xạ từ Ω vào [0, 1] để đại diện cho thông tin có sẵn. 𝜋(𝜔) 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ó. Ở 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 (𝜙, 𝑎) trong đó 𝜙 là một công thức mệnh đề và 𝑎 ∈ [0, 1]. Cặp (𝜙, 𝑎) có nghĩa là mức độ chắc chắn của 𝜙 ít nhất bằng 𝑎 (𝑁(𝜙) ≥ 𝑎). 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 (𝐵∗ = {𝜙𝑖|(𝜙𝑖, 𝑎) ∈ 𝐵}). Cho một cơ sở tri thức khả năng (PKB) B, chúng ta có thể tạo ra một hàm phân bố có thể duy nhất ký hiệu là 𝜋𝐵 như sau [26]: Định nghĩa 1.1  Định nghĩa 1.2 (a-cut và strict a-cut) Cho B là PKB và [0,1]a . Chúng ta gọi a-cut (tương ứng, strict a-cut) của B, ký hiệu là aB 3 Đa tập là tập hợp mà các phần tử của nó có thể giống nhau 3 (tương ứng, aB> ) 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 }),),(|{=( * abBbBB a   (tương ứng, lớn hơn a })>,),(|{=( *> abBbBB a   ). Định nghĩa 1.3 Cho 1B và 2B là hai PKB. 1B và 2B được gọi là tương đương ký hiệu là 21 BB  nếu 21 = BB  . Định nghĩa 1.4 (Độ không nhất quán) Độ không nhất quán của PKB B được xác định như sau: 𝐼𝑛𝑐(𝐵) = max {𝑎𝑖: 𝐵≥𝑎𝑖 là không nhất quán} Định nghĩa 1.5 (Ngưỡng) Cho ),( a là một công thức trong B . ),( a được gọi là ngưỡng trong B nếu:  aaB  )),(( và ),( a được gọi là ngưỡng chặt trong B nếu: aB> . Định nghĩa 1.6 (Suy luận hợp lý) 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: )(> BIncB Định nghĩa 1.7 (Suy luận khả năng) Cho B là một PKB. Công thức ),( a là một kết luận khả năng của B , ký hiệu: B ),( a , nếu: )(>(2),(1) )(> BIncaB BInc  và bBab >,> 1.2. Tổng quan về tích hợp tri thức 1.2.1. Biểu diễn tri thức Tích hợp tri thức là một khái niệm chung. Trong các vấn đề kinh tế - xã hội, tích hợp tri thức liên quan đến vấn đề nghiên cứu của các lĩnh vực: kinh tế, chính trị, văn hóa, giáo dục... Trong trí tuệ nhân tạo, khái niệm về tri thức đôi khi được hiểu với khái niệm về niềm tin và tích hợp tri thức được hiểu là quá trình duyệt tri thức hay tích hợp niềm tin [11]. Duyệt tri thức (Mục 1.2.2) nghiên cứu về quá trình thay 4 đổi tri thức. Có rất nhiều công trình nghiên cứu về vấn đề này, trong đó có [11, 12]. Tích hợp tri thức (Mục 1.2.3) nghiên cứu phương pháp để tổng hợp các cơ sở tri thức của các đối tượng thành một tri thức chung [13, 14]. Trong trí tuệ nhân tạo, có hai cách tiếp cận chính để đối phó với các thông tin mâu thuẫn đã được phân biệt: - Cách tiếp cận thứ nhất bao gồm việc tích hợp các thông tin và xây dựng một tập thông tin nhất quán có thể biểu diễn cho kết quả của việc tích hợp. - Cách tiếp cận thứ hai đó là "sống chung" với mâu thuẫn bằng cách sử dụng các paraconsistent logics [29, 30]. Trong luận văn này tôi tập trung vào cách tiếp cận thứ nhất. Đó là giải quyết mâu thuẫn bằng kỹ thuật tích hợp tri thức. Một cách tổng quát, bài toán tích hợp tri thức dựa trên cấu trúc logic được phát biểu như sau: Cho một tập các cơ sở tri thức, mỗi có sở tri thức được biểu diễn bằng một tập các công thức lôgic. Hãy xác định một cơ sở tri thức chung là đại diện tốt nhất cho tập các cơ sở tri thức đã cho. Các cấu trúc logic đã được nghiên cứu trong lĩnh vực này gồm có logic mệnh đề, logic mờ, logic vị từ, logic mô tả và logic khả năng. Để tiện cho việc diễn đạt và giải thích, luận văn sử dụng ví dụ như sau: Ví dụ 1.2.1 Vừa qua, một cuộc khủng hoảng môi trường nghiêm trọng đã gây ra hiện tượng cá chết )(a hàng loạt tại các tỉnh ven biển miền Trung Việt Nam. Có một số chuỗi ý kiến về nguyên nhân của hiện tượng này như sau: - Công chúng và các nhà khoa học: Cá chết (a) hàng loạt là do vấn đề nước xả thải ô nhiễm của nhà máy gang thép (b): (𝑏 → 𝑎) 5 - Nhà máy gang thép: Nhà máy đã đầu tư một hệ thống xử lý nước thải hiện đại (𝑐), do đó nước đã được xử lý trước khi thải ra biển: (𝑐, 𝑐 → ¬𝑏) - Cơ quan truyền thông: Nhà máy đã nhập hàng trăm tấn hóa chất độc hại (d) đồng thời hệ thống xử lý nước thải đặt ống xả thải ngầm sai quy định (f): (d, f). - Công chúng và các nhà khoa học: Một thợ lặn tham gia xây dựng nhà máy đã chết (g) do nước biển quanh khu vực nhà máy bị nhiễm độc (b): (𝑔, 𝑏 → 𝑔) - Nhà máy: Chúng tôi nhập khẩu chất hóa học (d) để tẩy rửa đường ống, tuy nhiên nước thải đã được xử lý trước khi xả ra biển ): ¬( 𝑏 → 𝑑). Ống xả thải ngầm đã được cấp phép xây dựng nhưng chưa được hoàn thành, do đó không thể xả thải tại thời điểm hiện tại ): (¬𝑓). - Nhà chức trách: Có hai nguyên nhân dẫn đến hiện tượng cá chết hàng loạt. Nó có thể do chất độc hóa học (𝑑) hoặc do hiện tượng tảo nở hoa (𝑒): (𝑑 → 𝑎) ∨ (𝑒 → 𝑎). Ngoài ra chưa thấy có bất kỳ mối quan hệ nào giữa nhà máy với hiện tượng cá chết. - Công chúng và các nhà khoa học: Cá chết không thể do hiện tượng tảo nở hoa bởi vì không có dấu hiệu của hiện tượng này như là tảo dạt vào bờ gây ô nhiễm, tảo nở dày đặc gây đổi màu nước và cá chết ở dưới đáy: (¬𝑒). Từ tiến triển của các sự kiện trên, chúng ta có các tập tri thức như sau: },,,{=1 egbgabB  . }.),(,,{=2 fbdbccB  }.,{=3 fdB )}.(){(=4 aeadB  6 Ví dụ này sẽ được sử dụng để minh họa cho các công việc được đề cập trong suốt luận văn này. 1.2.2. Duyệt tri thức Nghiên cứu quá trình duyệt tri thức là một lĩnh vực nghiên cứu thú vị và được bắt đầu từ những năm 1980. Các bài viết được phổ biến đánh dấu sự ra đời của lĩnh vực này là các chuyên đề, các hội thảo, các báo cáo của Gardenfors, Alchourron và Makinson [15]. Mô hình được phát triển từ [15] được gọi là mô hình AGM (là tên viết tắt của ba người sáng lập) và ngày nay mô hình này chiếm ưu thế trong duyệt tri thức. 1.2.2.1. Mô hình AGM Trong mô hình AGM, tri thức được biểu diễn như là một câu của L và một bộ tri thức là một lý thuyết của L. Quá trình duyệt tri thức được mô phỏng là một hàm * ánh xạ một lý thuyết K và một câu 𝜑 đến một lý thuyết mới 𝐾 ∗ 𝜑. Quá trình duyệt tri thức tuân theo nguyên tắc thay đổi tối thiểu, tức là một tác nhân phải thay đổi tri thức của mình càng ít càng tốt để phù hợp với thông tin mới . 1.2.2.1.1. Bộ định đề AGM cho duyệt tri thức Cho K là một lý thuyết của L và môṭ câu φ. Hàm * là một hàm loại bỏ tri thức nếu nó thỏa mãn các định đề sau: (𝐾 ∗ 1) 𝐾 ∗ 𝜑 là một lý thuyết của 𝐿. (𝐾 ∗ 2) 𝜑 ∈ 𝐾 ∗ 𝜑. (𝐾 ∗ 3) 𝐾 ∗ 𝜑 ⊆ 𝐾 + 𝜑. (𝐾 ∗ 4) Nếu ¬𝜑 ∉ 𝐾 thì 𝐾 + 𝜑 ⊆ 𝐾 ∗ 𝜑. (𝐾 ∗ 5) Nếu 𝜑 là phù hợp thì 𝐾 ∗ 𝜑 cũng phù hợp. (𝐾 ∗ 6) Nếu ⊢ 𝜑 ⟷ 𝜓 thì 𝐾 ∗ 𝜑 = 𝐾 ∗ 𝜓. (𝐾 ∗ 7) 𝐾 ∗ (𝜑 ⋀ 𝜓) ⊆ (𝐾 ∗ 𝜑) + 𝜓. (𝐾 ∗ 8) Nếu ¬𝜓 ∉ 𝐾 ∗ 𝜑 thì (𝐾 ∗ 𝜑) + 𝜓 ⊆ K ∗ (𝜑 ⋀ 𝜓). 7 1.2.2.1.2. Bộ định đề AGM cho loại bỏ tri thức Cho K là một lý thuyết của L và môṭ câu φ. Hàm ∸ là một hàm loại bỏ tri thức nếu nó thỏa mãn các định đề sau: (𝐾 ∸ 1) 𝐾 ∸ 𝜑 là một lý thuyết. (𝐾 ∸ 2) 𝐾 ∸ 𝜑 ⊆ 𝐾. (𝐾 ∸ 3) Nếu 𝜑 ∉ 𝐾 thì 𝐾 ∸ 𝜑 = 𝐾. (𝐾 ∸ 4) Nếu ⊬ φ thì 𝜑 ∉ 𝐾 ∸ 𝜑. (𝐾 ∸ 5) Nếu 𝜑 ∈ 𝐾, thì 𝐾 ⊆ (𝐾 ∸ 𝜑) + 𝜑. (𝐾 ∸ 6) Nếu ⊢ 𝜑 ⟷ 𝜓 thì 𝐾 ∸ 𝜑 = 𝐾 ∸ 𝜓. (𝐾 ∸ 7) (𝐾 ∸ 𝜑)⋂(𝐾 ∸ 𝜓) ⊆ 𝐾 ∸ (𝜑 ⋀ 𝜓). (𝐾 ∸ 8) Nếu 𝜑 ∉ 𝐾 ∸ (𝜑 ⋀ 𝜓) thì 𝐾 ∸ (𝜑 ⋀ 𝜓) ⊆ 𝐾 ∸ 𝜑. Có một mối quan hệ giữa mô hình duyệt tri thức và loại bỏ tri thức, nó được gọi là đồng nhất Levi: 𝐾 ∗ 𝜑 = (𝐾 ∸ ¬𝜑) + 𝜑. Một quy trình xác định loại bỏ trong giới hạn của duyệt cũng đó được chỉ ra. Nó được biết đến với tên gọi là đồng nhất Harper: 𝐾 ∸ 𝜑 = (𝐾 ∗ ¬𝜑) ⋂ 𝐾 1.2.2.2. Hàm lựa chọn 1.2.2.3. Cố thủ tri thức 1.2.2.4. Hệ thống các khối cầu tri thức Hình 1.2 tóm tắt những kết quả chính đầu tiên của mô hình AGM . 8 Hình 1.2 Mô hình AGM 1.2.3. Tích hợp tri thức Tích hợp tri thức nghiên cứu cách hợp các thông tin độc lập, không nhất quán và đến từ nhiều nguồn khác nhau thành một thông tin nhất quán. Một mô hình lý thuyết mô tả các định đề và các toán tử kết hợp được đưa ra bởi Lin và Mendelzon [18]. Một tập các định đề mới cho các toán tử tích hợp tri thức đã được phân biệt (đối với các tiên đề nó thỏa mãn) giữa toán tử trọng tài và toán tử đa số đã được giới thiệu bởi Konieczny và Pino Pérez [10]. 1.2.3.1. Một mô hình cho tích hợp với ràng buộc toàn vẹn Konieczny và cộng sự đã đưa ra các mệnh đề cho toán tử tích hợp IC trong [23] như sau: Định nghĩa 1.2.1 ( Toán tử tích hợp IC). Cho 21,, EEE là các hồ sơ tri thức , 21, KK là các cơ sở tri thức nhất quán, và 21,, ICICIC là các ràng buộc toàn vẹn.  là một toán tử tích hợp với ràng buộc toàn vẹn nếu nó thỏa mãn các định đề sau đây: (IC0) ICEIC )( . (IC1) Nếu IC nhất quán, thì )(EIC cũng nhất quán. (IC2) Nếu E là nhất quán với IC , thì ICEEIC  )( . 9 (IC3) Nếu 21 EE  và 21 ICIC  , thì )()( 2211 EE ICIC  . (IC4) Nếu ICK 1 và ICK 2 , thì 121 }),({ KKKIC  là nhất quán khi và chỉ khi 221 }),({ KKKIC  là nhất quán. (IC5) )()()( 2121 EEEE ICICIC   . (IC6) Nếu )()( 21 EE ICIC  là nhất quán, thì )()()( 2121 EEEE ICICIC   . (IC7) )()( 21 2 1 EICE ICICIC   . (IC8) Nếu 2 1 )( ICEIC  là nhất quán, thì 2 121 )()( ICEE ICICIC    1.2.3.2. Tích hợp ở mức cú pháp Tích hợp dựa trên cú pháp (còn gọi là tích hợp dựa trên công thức) toán tử tích hợp làm việc từ ưu tiên các tập con của các công thức nhất quán. Sự khác biệt giữa các toán tử này với các toán tử khác trong việc xác định các mối quan hệ ưu tiên. Định nghĩa 1.2.3 Cho MAXCONS ),( ICK là tập con nhất quán lớn nhất (đối với tập bao hàm)của }{ICK  có chứa IC . MAXCONS ),( ICK là tập hợp của tất cả các tập M sao cho: • }{ICKM  , và • MIC  , và • Nếu }{ICKMM  , thì M 10 Định nghĩa 1.2.4 Cho E là một hồ sơ tri thức và IC là một cơ sở tri thức: ),(M=)(1 ICEAXCONSECIC  . }{ và),(M:=)(3 ICMEAXCONSMMECIC   là nhất quán. ),(M=)(4 ICEAXCONSE card C IC  . ICMEAXCONSMICMECIC   và),(M:=)( 5 là nhất quán, nếu tập không rỗng và là IC trong các trường hợp còn lại. )(),( 31 EE CIC C IC  và )( 4 ECIC tương ứng với ),1( ICEComb , ),3( ICEComb và ),4( ICEComb được định nghĩa trong [21] (không xem xét các toán tử 2Comb vì nó là tương đương với 1Comb [21]). Các toán tử 5C là một sửa đổi nhỏ của 3C để có thuộc tính hợp lý hơn [22]. 1.2.3.3. Phương pháp dựa trên khoảng cách Chúng ta thấy rằng toán tử đa số được đặc trưng bằng cách cố gắng để giảm thiểu tổng số không hài lòng, trong khi toán tử trọng tài cố gắng giảm thiểu sự không hài lòng của từng đối tượng. Do đó chúng ta có thể thấy khoảng cách như là một cách để nắm bắt những khái niệm về sự không hài lòng. Mục đích là lựa chọn các diễn giải có khoảng cách nhỏ nhất giữa mô hình của IC và các mô hình của hồ sơ tri thức E . Nó có thể được xác định như sau: )),((=))(( dIC ICmodminEmod  Định nghĩa 1.2.5 ( Khoảng cách) Một khoảng cách giữa các diễn giải là một hàm tổng d từ  tới  sao cho với mỗi 21, 11 • ),(=),( 1221  dd , và • 0=),( 21 d khi và chỉ khi 21 = Khoảng cách giữa một diễn giải  và một hồ sơ tri thức K . Đó là khoảng cách nhỏ nhất giữa  và mô hình của K . được xác định như sau: ).,(=),( )(   dminKd Kmodw Để xác định được khoảng cách này, chúng ta cũng cần phải thực hiện hai bước: Bước đầu tiên chúng ta sẽ xác định hàm hợp   RRD n: là khoảng cách giữa các mô hình của IC và cơ sở tri thức iK và kết hợp chúng thành một khoảng cách chung. Tức là: )),(),...,,(),,((=),( 21 nKdKdKdDED  . Định nghĩa 1.2.6 ( hàm hợp) Một hàm hợp là một hàm dùng để kết hợp một số không âm thỏa mãn các tính chất sau: - Nếu 𝑥 ≤ 𝑦: 𝐷(𝑥1, 𝑥, 𝑥𝑛) ≤ 𝐷(𝑥1, 𝑦, 𝑥𝑛). - 𝐷(𝑥1, 𝑥𝑛) = 0 khi và chỉ khi 𝑥1 = ⋯ = 𝑥𝑛 = 0. - Đối với tất cả các số nguyên không âm 𝑥, 𝐷(𝑥) = 𝑥. Trong số các đề xuất, [18] đã áp dụng khoảng cách Hamming cho d và sum hoặc max cho D (ký hiệu là 𝐷Σ và MaxD ). Định nghĩa 1.2.7 Cho 21, là hai diễn giải chúng ta có thể xác định được các khoảng cách sau: • Khoảng cách Hamming Hd được xác định bởi:  .)()(|=),( 2121 xxxdH   Cuối cùng, leximaxD lựa chọn giá trị nhỏ nhất theo thứ tự từ điển. 12 Chương 2. Mô hình tranh luận Tranh luận đã trở thành một thành phần chính của trí tuệ con người, khả năng tham gia vào tranh luận giúp con người hiểu được những vấn đề mới, để diễn giải khoa học, để giải thích, làm rõ và bảo vệ những quan điểm của họ trong đời sống hàng ngày. Cách mà con người tham gia vào tranh luận dựa trên một nguyên tắc có thể tóm gọn bằng một câu nói: người có tiếng nói cuối cùng là người chiến thắng và một quy tắc diễn giải thông thường: Chỉ định trách nhiệm: Nếu một tác tử thực hiện một hành động là nguyên nhân của một vài trạng thái thì tác tử đó phải chịu trách nhiệm cho trạng thái đó đến khi nào hành động đó được biện minh, giải thích. 2.1. Sự chấp nhận của tranh luận 2.1.1. Mô hình tranh luận Lý thuyết tranh luận dựa trên khái niệm của mô hình tranh luận [24] được xác định là một cặp của tập các lập luận và một quan hệ nhị phân biểu diễn mối quan hệ tấn công giữa chúng. Định nghĩa 2.1.1 Một mô hình tranh luận là một cặp  attacksARAF ,= Trong đó AR là tập các lập luận, và attacks là mối quan hệ nhị phân trên AR , nghĩa là ARARattacks  . Cho hai tranh luận A và B , ),( BAattacks biểu diễn một tấn công của A chống lại B . Hình 2.1 Mô hình tranh luận 13 Chúng ta nói rằng A tấn công B (hoặc B bị tấn công bởi A ) nếu ),( BAattacks là đúng. Tương tự, chúng ta nói tập lập luận S tấn công B (hoặc B bị tấn công bởi tập S ) nếu B bị tấn công bởi một lập luận ở trong S . Định nghĩa 2.1.2 Một tập lập luận S được gọi là không chứa xung đột (conflict-free) nếu không có các lập luận A và B trong S sao cho A tấn công B . Định nghĩa 2.1.3 1. Một lập luận ARA là có thể chấp nhận bởi tập lập luận S khi và chỉ khi với mỗi lập luận ARB , nếu B tấn công A thì B bị tấn công bởi S . 2. Một tập lập luận không chứa xung đột S là bao đóng có thể chấp nhận nếu mỗi lập luận trong S được chấp nhận bởi S . Ngữ nghĩa (tin cậy) của một mô hình tranh luận được định nghĩa bởi khái niệm của phần mở rộng ưu tiên (preferred extension) Định nghĩa 2.1.4 Một mở rộng ưu tiên của một mô hình tranh luận AF là tập bao đóng có thể chấp nhận lớn nhất (đối với bao hàm tập) của AF . Định nghĩa 2.1.5 Một tập lập luận không chứa xung đột S được gọi là phần mở rộng ổn định khi và chỉ khi S tấn công mỗi lập luận không thuộc về S : )],()(()[( ABattacksSBSAArgA  . 2.1.2. Ngữ nghĩa cố định và ngữ nghĩa cơ sở (hoài nghi) Lập luận có thể đặc trưng bởi lý thuyết điểm cố định cung cấp cách để giới thiệu ngữ nghĩa cơ sở (hoài nghi). 14 Định nghĩa 2.1.6 Hàm đặc trưng, ký hiệu là AFF của mô hình tranh luận attcksARAF ,= được xác định như sau: ARAR AFF 22=  |{=)( AASFAF Ngữ nghĩa hoài nghi của mô hình tranh luận được xác định bởi khái niệm của phần mở rộng cơ sở như sau: Định nghĩa 2.1.7 Phần mở rộng cơ sở của một mô hình tranh luận AF , ký hiệu là AFGE , là điểm cố định nhỏ nhất của AFF . Khái niệm phần mở rộng đầy đủ sẽ cung cấp kết nối giữa phần mở rộng ưu tiên (ngữ nghĩa tin cậy) và phần mở rộng cơ sở (ngữ nghĩa hoài nghi) Định nghĩa 2.1.8 Một tập lập luận có thể chấp nhận được S được gọi là phần mở rộng đầy đủ khi và chỉ khi mỗi lập luận được chấp nhận bởi S thuộc về S . Mối quan hệ giữa phần mở rộng ưu tiên, phần mở rộng cơ sở và phần mở rộng đầy đủ được cho ở định lý sau: Định nghĩa 2.1.9 1. Mỗi phần mở rộng ưu tiên là một phần mở rộng đầy đủ, nhưng không có điều ngược lại. 2. Phần mở rộng cơ sở là phần nhỏ nhất (theo bao hàm tập) của phần mở rộng đầy đủ. 3. Phần mở rộng đầy đủ tạo thành một nửa hoàn chỉnh đối với bao hàm tập. 15 2.1.3. Điều kiện cho sự trùng giữa ngữ nghĩa khác nhau Mô hình tranh luận có cơ sở (chắc chắn - Well-founded) Phần này sẽ cung cấp ở các điều kiện đủ cho sự trùng nhau giữa ngữ nghĩa cở sở, ngữ nghĩa ưu tiên cũng như ngữ nghĩa ổn định. Định nghĩa 2.1.11 Một mô hình tranh luận là có cơ sở khi và chỉ khi tồn tại một chuỗi hữu hạn 𝐴0, 𝐴1, , 𝐴𝑛 sao cho với mỗi 1, iAi tấn công iA . Mô hình tranh luận rõ ràng (Coherent – mạch lạc, nhất quán) Nhìn chung sự tồn tại của một phần mở rộng ưu tiên không ổn định do sự tồn tại của một số “bất thường” trong mộ hình tranh luận tương ứng.4 Ví dụ, trong mô hình tranh luận )},{(},{ AAA 5 có một phần mở rộng ưu tiên rỗng là không ổn định. Định nghĩa 1.12 1. Một mô hình tranh luận AF được gọi là rõ ràng nếu mỗi phần mở rộng ưu tiên của AF là ổn định. 2. Chúng ta nói rằng một mô hình tranh luận AF là cơ sở tương đối nếu phần mở rộng cơ sở trùng với giao điểm của tất cả các phần mở rộng ưu tiên. 4 Sự tồn tại của một vài "bất thường" không có nghĩa là sẽ có một vài lỗi trong mô hình tranh luận tương ứng 5 Mô hình tranh luận này tương ứng với chương trình logic pp 16 2.2. Tranh luận, trò chơi n-người và bài toán hôn nhân bền vững 2.2.1. Tranh luận trong trò chơi n -người Trong lý thuyết của trò chơi n -người được phát triển bởi Von Neuman và Morgenstern, một mô hình kinh tế xã hội được xem như một trò chơi mà người chơi là động lực chính của nền kinh tế. Lý thuyết trò chơi cổ điển quan tâm chủ yếu đến khía cạnh kỹ thuật của trò chơi. Trong khi lý thuyết trò chơi n -người là một lý thuyết về sự thưởng phạt cho người chơi. Khái niệm tập trung của lý thuyết trò chơi n -người là một tập các vector thưởng phạt được gọi là khoản tính đối với người tham gia. Do đó việc xem xét một nền kinh tế xã hội như một trò chơi n - người, mô hình khoản tính là cách để phân chia tài sản trong một nền kinh tế 2.2.2. Tranh luận và bài toán hôn nhân bền vững Cho hai tập M của n người đàn ông và W của n người phụ nữ. Vấn đề hôn nhân ổn định )(SMP là vấn đề tìm kiếm một cách để sắp xếp các cuộc hôn nhân dành cho những người đàn ông và phụ nữ trong M và W . Chúng ta giả sử rằng tất cả những đàn ông và phụ nữ trong M và W đã bày tỏ sở thích về nhau (mỗi người đàn ông phải nói cảm giác của anh ấy như thế nào về mỗi người phụ nữ và ngược lại). Ví dụ, nếu A kết hôn với B , thì tất cả những người A thích hơn B , chẳng hạn là C thì đã phải kết hôn với một người D nào đó mà C thích D hơn A . Cuối cùng, một giải pháp cho các SMP là tương ứng một – một WMS : sao cho không tồn tại cặp WMnm ),( sao cho m thích w hơn )(mS và w thích m hơn )(1 wS  . 17 Chương 3. Tích hợp tri thức có ưu tiên trong mô hình logic khả năng Bài toán tích hợp tri thức có ưu tiên trong một framework logic khả năng được phát biểu như sau: 1. Dữ liệu đầu vào: là tập các cơ sỏ tri thức mà mỗi cơ sở tri thức riêng lẻ là nhất quán. 2. Dữ liệu đầu ra: một cơ sở tri thức chung nhất quán, thu được từ việc tích hợp các cơ sở tri thức đầu vào. 3. Phạm vi của bài toán: mỗi cơ sở tri thức được xét chứa các biểu thức logic được xây dựng dưới dạng logic khả năng. 4. Tiến trình thực hiện: dùng tranh luận: Bước 1: Xác định hàm hợp và kết quả của tích hợp. Bước 2: Xác định các hệ quả tồn tại. Bước 3: Tính kết quả của tích hợp tri thức. 5. Kết quả dự kiến: thu được một tập các tri thức chung nhất quán 3.1. Tích hợp tri thức bằng tranh luận trong logic khả năng Trong phần này, chúng ta xem xét một phương pháp chung dùng mô hình tranh luận để giải quyết những mâu thuẫn xảy ra khi chúng ta kết hợp các cơ sở tri thức (𝐵1, 𝐵𝑛) Chúng ta sẽ bắt đầu với khái niệm của lập luận: Định nghĩa 3.1.1 Một lập luận là một cặp  hH , , trong đó h là một công thức của ngôn ngữ  và H là một tập con của cơ sơ tri thức B thỏa mãn: (1) *H , (2) 𝐻 ⊢ ℎ, (3) H là nhất quán và nhỏ nhất. 18 H được gọi là phần hỗ trợ và h được gọi là phần kết luận của một lập luận. )( sẽ biểu diễn tập tất cả các lập luận có thể xây dựng từ  . Định nghĩa 3.1.2 Một mô hình tranh luận (AF) là một bộ ba  ,, trong đó  là tập hữu hạn các lập luận,  là mối quan hệ nhị phân biểu diễn mối quan hệ của các lập luận trong  ,  là thứ tự ưu tiên trên  . Chúng ta cũng sử dụng  để biểu diễn thứ tự ưu tiên ngặt đối với  . Định nghĩa 3.1.3 Cho A và B là hai lập luận trong  - B tấn công A nếu 𝐵 ℛ 𝐴 và 𝐵 ≽ 𝐴 - Nếu 𝐵 ℛ 𝐴 khi đó A có thể tự bảo vệ nó nếu 𝐴 ≻ 𝐵. - Một tập lập luận S bảo vệ A nếu B tấn công A thì tồn tại 𝐶 ∈ 𝑆 tấn công B. Định nghĩa 3.1.4 Cho  ,,= AF là một mô hình tranh luận. Một tập lập luận  là không chứa xung đột trong AF nếu  YX , sao cho .YX Mối quan hệ loại trừ lẫn nhau giữa các lập luận được gọi là “Undercut”. Nó được xác định như sau: Định nghĩa 3.1.5 Cho  hH , và  hH , là hai lập luận của )( .  hH , undercut  hH , khi có một khHk  , . Một lập luận là bị tấn công undercut nếu tồn tại ít nhất một lập luận tấn công lại một phần tử hỗ trợ của nó Định nghĩa 3.1.6 Cho  hH , và  hH , là hai lập luận của )( .  hH , bác bỏ (rebut)  hH , nếu hh  . 19 Hai lập luận bác bỏ nhau khi kết luận của chúng mâu thuẫn với nhau. Trong [25] đã chỉ ra rằng mỗi lập luận có thể có ảnh hưởng khác nhau. Ảnh hưởng của một lập luận được định nghĩa như sau. Định nghĩa 3.1.7 Cho  hHA ,= là một lập luận. Ảnh hưởng của A ký hiệu là )(Aforce được xác định như sau: }.),( và:{=)(  iiii aHaminAforce  Ảnh hưởng của một lập luận giúp ta có thể so sánh các cặp lập luận như sau Định nghĩa 3.1.8 (Mối quan hệ ưu tiên) Cho A và A là hai lập luận trong )( . A được ưu tiên hơn A ký hiệu AA  nếu )(>)( AforceAforce  . Mệnh đề 3.1.2 Cho B là một cơ sở tri thức khả năng và  ,),( Undercut là một mô hình tranh luận. }.att |))(),(({=)( jiji att AAAforceAforceminmaxBInc Trong đó },{ rebutundercutatt . Bây giờ chúng ta xác định tích hợp tri thức bằng tranh luận như sau: Định nghĩa 1.9 Cho }),...,({ 1 nBB là một tập các cơ sở tri thức khả năng. Toán tử tích hợp tri thức được định nghĩa như sau: }),{( )}.(>,|),{(=)( rebutundercutattIncaa attatt     20 Chúng ta gọi )(att là toán tử BMA (Belief Merging by Argumentation). Tiếp tục ví dụ 1.2.1. Giả sử các tri thức có trọng số như sau: ;0.3)}(;0.4),(;0.6),(;0.7),{(=1 egbgbaB  , ;0.4)}(;0.5),(;0.5),(;0.8),{(=2 dbcbcfB  , ;0.3)}(;0.9),{(=3 dfB , 7)}..);0(){((=4 aeadB  Và  là hàm hợp được định nghĩa như sau  .=),(  . Chúng ta có: 0.8.=)(  undercutInc 3.2. Định đề và một số tính chất Trong phần tiếp theo tôi xin giới thiệu một số định đề cho tích hợp tri thức bằng tranh luận. Giả sử chúng ta có }B,...,B{= 1 n là tập hữu hạn các cơ sở tri thức khả năng, sAF là mô hình tranh luận được xác định từ  . Hàm hợp  xác định như sau:   n: *. Tập các định đề được giới thiệu như sau: (SYM) }),...,({=}),...,({ )((1)1 nn BBBB  . (CON) )}),...,({()}),...,({( 11    nn BBBB . 21 (UNA) Nếu ** 1 ... nBB  thì * 11 }),...,({ BBB n  (IDN) *}),...,({ iii BBB  (CLO) }),...,({ * 11= ii n i BBB  (MAJ) Nếu 2 |>}1,...,=,{| * n niBi  thì  }),...,({ ii BB . (COO) Nếu niBi 1,...,=, *  thì  }),...,({ ii BB . Chúng ta có các nhận xét sau: - (UNA) bao hàm (IDN). - (MAJ) bao hàm (COO). Khảo sát với các toán tử tích hợp được xác định ở phần trước, chúng ta có: Định lý 2.1 Toán tử BMA thỏa mãn các định đề (SYM), (CON), (UNA) và (CLO). Không thỏa mãn (MAJ). Chương 4. Thực nghiệm và đánh giá Do hạn chế về mặt thời gian, trong khuôn khổ luận văn này, chúng tôi chỉ tiến hành thực cài đặt một phần của mô hình đề xuất, cụ thể là quá trình tích hợp chỉ thực hiện được với dữ liệu đầu vào trong công thức có chứa phép tuyển, chưa thực hiện được với phép hội. Phần còn lại sẽ được tiến hành trong những nghiên cứu tiếp theo. 22 4.1. Môi trường thực nghiệm 4.2. Quá trình thực nghiệm 4.2.1. Giới thiệu về chương trình 4.2.2. Tập dữ liệu thực nghiệm - Tập thứ nhất là hai cơ sở tri thức khả năng được sử dụng trong luận văn. - Tập thứ hai là hai cơ sở tri thức khả năng do chương trình tự sinh ra với khoảng 3000 công thức ở mỗi cơ sở tri thức khả năng. 4.2.3. Kết quả thực nghiệm thu được của tập dữ liệu thứ nhất 4.2.4. Kết quả thực nghiệm thu được của tập dữ liệu thứ hai Sau khi chạy thực nghiệm với tập dữ liệu do chương trình sinh ra, ta có được biểu đồ kết quả như sau: Hình 4.7. Biểu đồ thời gian thực nghiệm 23 4.2.5. Đánh giá kết quả thực nghiệm và hướng nghiên cứu tiếp theo Kết quả thực nghiệm cho thấy: • Trong quá trình chạy tập dữ liệu thứ nhất, kết quả thu được phù hợp với kết quả kết quả sủ dụng trong các ví dụ đã trình bày ở trên. • Trong thời gian tới, chương trình sẽ hoàn thành bổ xung thêm tích hợp với dữ liệu đầu vào trong công thức có chứa phép hội. 24 Kết luận Nội dung chủ yếu của luận văn này là cung cấp một mô hình để tích hợp tri thức bằng phương pháp tranh luận. Ý tưởng chính của mô hình này là sử dụng độ không nhất quán như là một thước đo cùng với khái niệm undercut để xây dựng một mô hình tranh luận cho tích hợp tri thức. Luận văn đã thu được các kết quả chính sau đây: • Tìm hiểu về logic cổ điển, logic khả năng, duyệt niềm tin, biểu diễn tri thức, tích hợp tri thức và mô hình tranh luận của GS. Phạm Minh Dũng [24]. • Xây dựng các mô hình tiên đề và mô hình xây dựng cho tích hợp tri thức bằng phương pháp tranh luận. Trong đó một tập các định đề cũng đã được giới thiệu và tính hợp lý của nó cũng đã được đề cập và thảo luận. • Một mô hình xây dựng sử dụng quan hệ tấn công undercut được đề xuất. • Các quan hệ giữa mô hình tiên đề và mô hình xây dựng được xem xét và bàn luận. • Một hệ thống thực nghiệm được xây dựng và chạy thử. Các kết quả thực nghiệm được thu thập, phân tích và luận giải. Mặc dù tôi đã có nhiều cố gắng để thực hiện đề tài một cách hoàn chỉnh nhất. Tuy nhiên do lần đầu tiên được làm quen với công tác nghiên cứu và năng lực của bản thân còn hạn chế và thời gian nghiên cứu có hạn nên luận văn mới đạt được một số kết quả nhất định. Các phân tích chuyên sâu và sự phức tạp trong tính toán của mô hình được dành cho các công việc trong tương lai.