Tóm tắt Luận văn Thạc sĩ: Tích hợp tri thức sử dụng các kỹ thuật tranh cã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

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 Logic cổ điển ............................................................ 1 1.1.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 Hàm lựa chọn ........................................................ 7 1.2.2.2. Cố thủ tri thức ....................................................... 7 1.2.2.3. Hệ thống các khối cầu tri thức .............................. 7 1.2.2.4. 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

1.2.3.2. 1.2.3.3.

8 Tích hợp ở mức cú pháp ....................................... 9 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. 2.2.2.

Tranh luận trong trò chơi -người ......................... 16 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

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

iii

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 http://www.worldbank.org/en/country/vietnam.

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

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.

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ó khi nó là

có thể xem là tương đương về logic với công thức

kết hợp của tất cả các công thức của

. Cho

là

cơ

sở tri thức và một số trong số chúng có thể tương đương logic cơ sở tri thức là một đa tập của với nhau, một tập tri thức (multi-set)3 , chúng ta . Giả sử

ký hiệu

và

.

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 là PKB và .

Chúng ta gọi a-cut (tương ứng, strict a-cut) của B, ký hiệu là

3 Đa tập là tập hợp mà các phần tử của nó có thể giống nhau

(tương ứng, ) 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

(tương ứng, lớn hơn a ).

Định nghĩa 1.3 Cho và là hai PKB. và được gọi là

tương đương ký hiệu là nếu .

Định nghĩa 1.4 (Độ không nhất quán) Độ không nhất quán của PKB

được xác định như sau:

𝐼𝑛𝑐(𝐵) = max {𝑎𝑖: 𝐵≥𝑎𝑖 là không nhất quán}

Định nghĩa 1.5 (Ngưỡng) Cho là một công thức trong .

được gọi là ngưỡng trong nếu: và

được gọi là ngưỡng chặt trong nếu: .

Định nghĩa 1.6 (Suy luận hợp lý) Cho là một PKB. Công thức

được gọi là kết luận hợp lý của nếu:

Định nghĩa 1.7 (Suy luận khả năng) Cho là một kết luận khả năng của là một PKB. Công thức , nếu: , ký hiệu: B

và

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 3

đổ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 hàng loạt tại các tỉnh ven biển trọng đã gây ra hiện tượng cá chết

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): (𝑏 → 𝑎)

- 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:

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ô ̣t 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 ∗ (𝜑 ⋀ 𝜓).

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ô ̣t 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

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 là các hồ

sơ tri thức , là các cơ sở tri thức nhất quán, và

là một toán tử tích hợp với ràng buộc là các ràng buộc toàn vẹn. toàn vẹn nếu nó thỏa mãn các định đề sau đây:

(IC0) .

(IC1) Nếu nhất quán, thì cũng nhất quán.

(IC2) Nếu là nhất quán với , thì .

(IC3) Nếu và , thì .

(IC4) Nếu và , thì là nhất quán

khi và chỉ khi là nhất quán.

(IC5) .

(IC6) Nếu là nhất quán, thì

(IC7) .

(IC8) Nếu là nhất quán, thì

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 là tập con nhất quán lớn

nhất (đối với tập bao hàm)của có chứa . MAXCONS

là tập hợp của tất cả các tập sao cho:

• , và

• Nếu , thì

là một hồ sơ tri thức và là một cơ sở Định nghĩa 1.2.4 Cho tri thức:

là nhất

quán.

là nhất

quán, nếu tập không rỗng và là trong các trường hợp còn lại.

và tương ứng với ,

và được định nghĩa trong [21]

(không xem xét các toán tử vì nó là tương đương với

là một sửa đổi nhỏ của để có [21]). Các toán tử 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 và các mô hình của hồ sơ tri thức . Nó có thể được xác định như sau:

Định nghĩa 1.2.5 ( Khoảng cách) Một khoảng cách giữa các diễn sao cho với mỗi giải là một hàm tổng tới từ

• , và

• khi và chỉ khi

Khoảng cách giữa một diễn giải và một hồ sơ tri thức

là khoảng cách nhỏ nhất giữa và mô hình của . Đó . được xác định

Để xác định được như sau:

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 là khoảng cách

giữa các mô hình của và cơ sở tri thức và kết hợp chúng thành

một khoảng cách chung. Tức là:

Đị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 và sum hoặc max cho ). (ký hiệu là 𝐷Σ và

Định nghĩa 1.2.7 Cho 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 được xác định bởi:

Cuối cùng, lựa chọn giá trị nhỏ nhất theo thứ tự từ điển.

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

Trong đó là tập các lập luận, và là mối quan hệ nhị

phân trên , nghĩa là .

Cho hai tranh luận và , biểu diễn một tấn

công của chống lại .

Hình 2.1 Mô hình tranh luận

tấn công

(hoặc

Chúng ta nói rằng ) nếu

bị tấn công bởi là đúng. Tương tự, chúng ta nói tập lập

tấn công

(hoặc

bị tấn công bởi tập

) nếu

bị

luận tấn công bởi một lập luận ở trong

.

được gọi là không chứa xung sao trong và

Định nghĩa 2.1.2 Một tập lập luận đột (conflict-free) nếu không có các lập luận cho tấn công .

Định nghĩa 2.1.3

1. Một lập luận

luận

khi và chỉ khi với mỗi lập luận

là có thể chấp nhận bởi tập lập tấn công

, nếu

thì

bị tấn công bởi

.

2. Một tập lập luận không chứa xung đột

thể chấp nhận nếu mỗi lập luận trong

là bao đóng có .

được chấp nhận bởi

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 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 .

Định nghĩa 2.1.5 Một tập lập luận không chứa xung đột là phần mở rộng ổn định khi và chỉ khi không thuộc về được gọi tấn công mỗi lập luận . :

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).

Định nghĩa 2.1.6 Hàm đặc trưng, ký hiệu là của mô hình tranh

luận được xác định như sau:

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

, ký hiệu là , là điểm cố định nhỏ nhất của .

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 đượ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 thuộc về .

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.

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.

tấn Đị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

công .

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 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

được gọi là rõ ràng nếu mỗi

phần mở rộng ưu tiên của

là ổn định.

2. Chúng ta nói rằng một mô hình tranh luận

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

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 -người

Trong lý thuyết của trò chơi

-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 -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 -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 - 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

của

Cho hai tập

người đàn ông và

, thì tất cả những người

thích hơn

nào đó mà

. Cuối cùng, một giải pháp cho các

người là vấn đề tìm kiếm phụ nữ. Vấn đề hôn nhân ổn định một cách để sắp xếp các cuộc hôn nhân dành cho những người . Chúng ta giả sử rằng tất cả và đàn ông và phụ nữ trong những đàn ông và phụ nữ trong đã bày tỏ sở thích về và nhau (mỗi người đàn ông phải nói cảm giác của anh ấy như thế kết hôn nào về mỗi người phụ nữ và ngược lại). Ví dụ, nếu với , chẳng hạn là hơn thì đã phải kết hôn với một người thích là tương ứng một – sao

sao cho không tồn tại cặp

một

cho

thích

hơn

và

thích

hơn

.

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 , trong đó là một

công thức của ngôn ngữ và là một tập con của cơ sơ tri thức

thỏa mãn: (1) là nhất quán và nhỏ , (2) 𝐻 ⊢ ℎ, (3)

nhất.

H được gọi là phần hỗ trợ và h được gọi là phần kết luận của sẽ biểu diễn tập tất cả các lập luận có thể

một lập luận.

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 là mối quan là tập hữu hạn các lập luận, trong đó

hệ nhị phân biểu diễn mối quan hệ của các lập luận trong , là

. Chúng ta cũng sử dụng để biểu diễn

thứ tự ưu tiên trê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 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 nếu

sao cho

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 và là hai lập luận của

. undercut khi có một .

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 và là hai lập luận của .

bác bỏ (rebut) nếu .

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 là một lập luận. Ảnh hưởng của

ký hiệu là được xác định như sau:

Ả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 trong được ưu tiên hơn . và ký hiệu là hai lập luận nếu

Mệnh đề 3.1.2 Cho là một cơ sở tri thức khả năng và

là một mô hình tranh luận.

Trong đó

.

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 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:

Chúng ta gọi là toán tử (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:

Và

là hàm hợp được định nghĩa như sau

. Chúng ta có:

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ó

là tập hữu hạn các cơ sở tri thức khả năng,

là mô hình tranh luận được xác định từ

. Hàm hợp

xác

*. Tập các định đề được giới thiệu

định như sau:

như sau:

(SYM) .

(CON) .

(UNA) Nếu thì

(IDN)

(CLO)

(MAJ) Nếu thì .

(COO) Nếu thì .

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ó:

thỏa mãn các định đề (SYM), (CON), Định lý 2.1 Toán tử (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.

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

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.

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.