Một số phương pháp xử lí tính nhất quán trong cơ sở tri thức xác suất

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

8
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết tổng hợp hai toán tử và đề xuất mới một khôi phục tính nhất quán của cơ sở tri thức xác suất, từ đó đưa ra mô hình xử lí tính không nhất quán trong cơ sở tri thức xác suất và tương ứng với mỗi toán tử, một thuật toán giải quyết được đề xuất. Hơn nữa, chi phí của mỗi thuật toán cũng như các nguyên lí kì vọng của các toán tử khôi phục cũng được xem xét.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Một số phương pháp xử lí tính nhất quán trong cơ sở tri thức xác suất

MỘT SỐ PHƯƠNG PHÁP XỬ LÍ TÍNH NHẤT QUÁN TRONG CƠ SỞ TRI THỨC XÁC SUẤT Nguyễn Văn Thẩm1, Phạm Thanh Huyền2* và Nguyễn Đỗ Kiều Loan3 1 Khoa Công nghệ thông tin, Trường Đại học Thủy lợi 2 Khoa Công nghệ thông tin, Trường Đại học Hạ Long 1 Khoa Cơ bản, Học viện Tài chính * Email: phamthanhhuyen@daihochalong.edu.vn Ngày nhận bài: 22/06/2023 Ngày nhận bài sửa sau phản biện: 27/07/2023 Ngày chấp nhận đăng: 15/08/2023 TÓM TẮT Một số chiến lược giải quyết tính không nhất quán của cơ sở tri thức xác suất đã được đề xuất và phát triển bằng cách thay đổi cấu trúc của các thành phần bên trong cơ sở tri thức, loại bỏ đi một phần tri thức, đánh giá mức độ không nhất quán bằng cách sử dụng các độ đo không nhất quán nhằm thay đổi giá trị xác suất của tri thức. Các chiến lược này thường xây dựng một họ các toán tử để làm cho một cơ sở tri thức không nhất quán trở thành cơ sở tri thức nhất quán. Bài báo này tập trung vào cách tiếp cận thứ ba, xem xét thay đổi giá trị xác suất của các ràng buộc xác suất trong cơ sở tri thức theo hướng đơn giản hơn. Bài báo tổng hợp hai toán tử và đề xuất mới một khôi phục tính nhất quán của cơ sở tri thức xác suất, từ đó đưa ra mô hình xử lí tính không nhất quán trong cơ sở tri thức xác suất và tương ứng với mỗi toán tử, một thuật toán giải quyết được đề xuất. Hơn nữa, chi phí của mỗi thuật toán cũng như các nguyên lí kì vọng của các toán tử khôi phục cũng được xem xét. Từ khóa: cơ sở tri thức xác suất, độ đo không nhất quán, ràng buộc xác suất, toán tử khôi phục tính nhất. SOME METHODS OF HANDLING INCONSISTENCY IN PROBABILISTIC KNOWLEDGE BASE ABSTRACT To solve the inconsistency of probabilistic knowledge bases, several strategies have been proposed and developed by changing the structure of the components inside probabilistic knowledge bases, removing a part of knowledge, and assessing the degree of inconsistency by using inconsistent measures that change the probability value of knowledge. These strategies typically construct a family of operators to convert an inconsistent probabilistic knowledge base to a consistent one. This paper focuses on the third approach, considering changing the probability values of probabilistic constraint in the probabilistic knowledge base towards a simpler direction. This paper synthesizes two operators and proposes a new one to restore the consistency of the probabilistic knowledge base. A model for dealing with inconsistencies in the probabilistic knowledge base is also provided. A resolution algorithm is proposed for each consistency restoring operator. Additionally, the cost of each algorithm, as well as the desirable principles of operators, are taken into account. Keywords: consistency restoring operator, inconsistency measure, probabilistic constraint, probabilistic knowledge bases. Số 09 (2023): 87 – 96 87
leo không chệch Ξ𝑈 (𝛿) để xây dựng bộ khôi 1. ĐẶT VẤN ĐỀ Phương pháp đầu tiên phụ thuộc vào các hàm Một số nghiên cứu gần đây cho rằng tích ℛ Y𝑈 (ℛ) = Ξ𝑈 (𝛿 ∗ ). Nếu 𝛿 = 0 thì Ξ𝑈 (0) = hợp cơ sở tri thức (CSTT) có liên quan chặt phục tính nhất quán leo không chệch ℛ ℛ ℛ. Nếu 𝛿 = 1 thì Ξ𝑈 (1) nhất quán. Kĩ thuật chẽ đến các các phương pháp xử lí tính ℛ khôi phục tính nhất quán là đi tìm một 𝛿 ∗ nhỏ không nhất quán của CSTT. Trong quá trình nhất sao cho Ξ𝑈 (𝛿 ∗ ) nhất quán. Tuy nhiên, tích hợp CSTT, tính không nhất quán có thể ℛ xảy ra khi các chuyên gia chia sẻ tri thức của rất khó xây dựng hàm Ξ𝑈 (𝛿) vì nó phụ thuộc họ. Tính không nhất quán của các CSTT có ℛ vào hàm xác suất đồng thời P0 trên tập hợp thể làm giảm hiệu suất của các hệ thống quản lí tri thức cũng như ảnh hưởng chất lượng của CSTT chung. Có nhiều cách tiếp cận để các thế giới có thể theo mệnh đề. Phương Ξ𝑃 (𝛿) để xây dựng bộ khôi phục tính nhất giải quyết tính không nhất quán. Tuy nhiên, pháp thứ hai phụ thuộc vào hàm leo phạt ℛ quán leo không chệch Y𝑃 (ℛ) = Ξ𝑃 (𝛿). Nếu các giải pháp này phụ thuộc vào phương ℛ 𝛿 = 0 thì Ξℛ (0) = ℛ. Kĩ thuật khôi phục pháp biểu diễn CSTT (Nguyen, 2008). Ba 𝑃 tính nhất quán là tìm 𝛿 ∗ ∈ [0, 1] sao cho cách tiếp cận chính để giải quyết tính không nhất quán đó là loại bỏ một phần tri thức gây Ξ𝑃 (𝛿 ∗ ) nhất quán. Tuy nhiên, xây dựng hàm ℛ ra mâu thuẫn, sửa đổi định tính và sửa đổi Y𝑃 (ℛ) = Ξ𝑃 (𝛿) là không dễ vì phải tìm tất định lượng. ℛ vectơ khả vi của ℛ. Ý tưởng chính của bài toán xử lí tính cả các nghiệm của bài toán tối ưu xác định không nhất quán bằng cách loại bỏ một phần tri thức là xây dựng một tập hợp các heuristic để xử lí tính không nhất quán, cụ thể ánh xạ Bằng cách sử dụng độ đo không nhất 𝒦 thành một CSTT nhất quán 𝒦 ∗ sao cho một CSTT xác suất có thể không nhất quán quán, Bona (2016) đã nghiên cứu các cách 𝒦 ∗ ⊆ 𝒦 . Phương pháp đã áp dụng thành tiếp cận để giải quyết các CSTT không nhất đo vi phạm tối thiểu 𝐼𝑛𝑐𝜋 (ℛ), 𝐼𝑛𝑐𝜋 (ℛ), 1 𝑝 quán. Cách tiếp cận đầu tiên dựa trên các độ 𝐼𝑛𝑐𝜋 (ℛ) và nguyên lí entropy cực đại để ∞ công để phát hiện lỗi trong quản lí và áp dụng tốt trong ví dụ thực tế. Tuy nhiên, cách tiếp cận này không dựa trên một nền tảng lí biến đổi một CSTT không nhất quán thành thuyết. Một cách tiếp cận khác để giải quyết nhất quán. Ý tưởng chính của cách tiếp cận định toán tử hợp nhất ME tổng quát Γ𝑀𝐸 (ℛ). 𝑝 tính không nhất quán là sửa một số công thức này là thay đổi xác suất điểm bằng cách xác sao cho thu được CSTT nhất quán (Rodder & Mỗi công thức (𝐹𝑖 |𝐺𝑖 )[𝑑𝑖 ] ∈ 𝒦 , ∀𝑖 = 1, 𝑛 ̅ nhưng thay vì làm việc với xác suất điểm [𝜌], Xu, 2001; Kern-Isberner & Rodder, 2003). Cách thứ hai kế thừa cách tiếp cận thứ nhất được thay bởi công thức (𝐹𝑖 𝐻𝑖 |𝐺𝑖 𝐻𝑖 )[𝑑𝑖 ] sao khoảng xác suất [𝑙, 𝑢] với 0 ≤ 𝑙 ≤ 𝑢 ≤ 1 được cho 𝒦 nhất quán. Mỗi công thức ̅ phép nới lỏng cho đến khi CSTT trở nên nhất (𝐹𝑖 |𝐺𝑖 )[𝑑𝑖 ] ∈ 𝒦 , ∀𝑖 = 1, 𝑛 được thay bởi 𝒞𝑝 (ℛ). Tuy nhiên, tất cả các cách tiếp cận 𝜀 quán bằng cách xây dựng toán tử hợp nhất công thức (𝐹𝑖 |𝐺𝑖 𝐻)[𝑑𝑖 ] sao cho 𝒦 nhất quán trong các công trình này đều được xem xét (Kern-Isberner & Rodder, 2003). trên ngữ cảnh logic điều kiện xác suất. Một cách tiếp cận xử lí tính không nhất Trong công trình (Nguyen & cs., 2018; buộc xác suất (RBXS) trong 𝒦 theo cách quán đó là sửa giá trị xác suất của các ràng Nguyen, 2021), chúng tôi sử dụng các độ không nhất quán để giải quyết tính không tiếp cận tối thiểu sao cho CSTT xác suất thu nhất quán của CSTT xác xuất bằng cách tập được với giá trị của các ràng buộc đã sửa đổi trung vào việc thay đổi xác suất trong CSTT nhất quán (Potyka, 2016; Bona, 2016). này. Các cách tiếp cận của chúng tôi được mở Potyka (2016) sử dụng các độ đo vi phạm rộng từ các chiến lược trong Potyka, 2016 và để xây dựng hai bài toán khôi phục tính nhất Bona, 2016 nhưng bài toán khôi phục tính quán trong CSTT có điều kiện xác suất. nhất quán được xem xét trong một tập hợp 88 Số 09 (2023): 87 – 96
KHOA HỌC TỰ NHIÊN các sự kiện. Các cách tiếp cận trong Nguyen một số nguyên lí kì vọng của toán tử khôi quán theo chuẩn ℐ𝜋 (ℛ), ℐ𝜋 (ℛ), ℐ𝜋 (ℛ) 1 𝑝 ∞ và cs., 2018 sử dụng các đo độ không nhất phục tính nhất quán. Phần ba tổng hợp hai và độ đo không nhất quán phi chuẩn ℐ𝜋 (ℛ) 𝑢 cách tiếp cận và đề xuất một cách tiếp để xử lí tính không nhất quán trong CSTT xác suất. Γ 𝑝 (ℛ) và toán tử khôi phục phi chuẩn để xây dựng toán tử khôi phục theo chuẩn Các thuật toán tìm CSTT xác suất nhất quán Γ 𝑢 (ℛ). Toán tử khôi phục Γ 𝑝 (ℛ) là lời giải cũng như việc đánh giá độ phức tạp của các thuật toán này được giới thiệu trong phần ba. khi toán tử Γ 𝑢 (ℛ) là lời giải của bài toán tối của bài toán tối ưu không có ràng buộc trong Phần bốn trình bày kết luận và tổng hợp các kết quả thu được, đưa ra một số hướng thực ưu với một tập các ràng buộc. Cách tiếp cận hiện trong tương lai. trong Nguyen và cs., 2018 sử dụng các nguyên lí của entropy cực đại để xây dựng 2. KIẾN THỨC LIÊN QUAN TRONG bài toán khôi phục tính nhất quán. Bài toán CƠ SỞ TRÍ THỨC này cũng là một vấn đề tối ưu hóa phi tuyến 2.1. Một số khái niệm cơ bản trong cơ sở tính với các ràng buộc. Lời giải của bài toán Đặt 𝒮 là một không gian mẫu hữu hạn tri thức xác suất này là một vectơ xác suất được khôi phục thỏa mãn. Các quy tắc xác suất được sử dụng nghiệm thống kê. Đặt ℇ = {𝐸1 , … , 𝐸𝑛 } là để thu được CSTT xác suất nhất quán từ chứa tất cả các kết quả có thể có của một thí vectơ xác suất được khôi phục thỏa mãn. không gian mẫu 𝒮 . Đặt 𝔓(ℇ) là tập các tập một tập hợp các sự kiện được biểu thị trong Trong bài báo này, chúng tôi tổng hợp con của E. Với 𝐹 , 𝐺 ∈ ℇ, đặt 𝐹𝐺 là giao của các phương pháp xử lí tính không nhất quán 𝐹 và 𝐺, 𝐹 ̅ là phủ định của 𝐹 . Đặt Θ = được đề xuất từ công trình của Nguyen và 𝐸̂1 … 𝐸̂𝑛 là hội đầy đủ của ℇ với 𝐸𝑖 = ̂ cs., 2021. Đó là bộ xử lí tính không nhất ̅ {𝐸𝑖 , 𝐸𝑖 }. Đặt h = 2 và Λ(ℇ) = quán biến dạng cân bằng và bộ xử lí tính nhất quán biến dạng phạt được đề xuất như là hai n {Θ1 , … , Θℎ } là tập các hội đầy đủ của ℇ và lựa chọn thay thế để giải quyết tính không 𝐸̅1 … 𝐸̅𝑛 = ∅. Đặt 𝒬 = ℇ ∪ {𝐸̂𝑖 𝐸𝑗 : 𝐸̂𝑖 = ̂ nhất quán trong CSTT xác suất (Nguyen & cs., 2021). Cách tiếp cận này dễ dàng tìm ̅ ̂ ̅ {𝐸𝑖 , 𝐸𝑖 }, 𝐸𝑗 = {𝐸𝑗 , 𝐸𝑗 }, 𝐸𝑖 ≠ 𝐸𝑗 }. Hội được CSTT nhất quán so với các phương đầy đủ thỏa mãn U , kí hiệu Θ ⊨ U nếu U xuất pháp trong Bona, 2016. Từ các cách tiếp cận hiện dương trong Θ. này, chúng tôi đề xuất các toán tử khôi phục tính nhất quán trong CSTT xác suất, xem xét một số nguyên lí kì vọng mà các bộ xử lí tính 𝐹 , 𝐺 ∈ ℰ và 𝜌 ∈ ℝ[0,1]. Một RBXS là một không nhất quán biến dạng cần thoả mãn. Định nghĩa 1. (Nguyen & cs., 2021). Đặt biểu thức có dạng 𝒸[𝜌], trong đó 𝒸 = (𝐹 |𝐺). Sau đó, chúng tôi đề xuất ba thuật toán để giải quyết tính không nhất quán trong CSTT Nếu 𝐹 độc lập với 𝐺, tức 𝐺 là lặp thừa, xác suất: thuật toán khôi phục tính nhất quán 𝐺 ≡ ⊺, kí hiệu | ⊺ bởi (𝐹 ). Hai RBXS 𝒸1 biến hình phạt (EADIS), thuật toán khôi và 𝒸2 được gọi là tương đương về cấu trúc, phục tính nhất quán biến hình cân bằng mở được kí hiệu 𝒸1 ≈ 𝒸2 , nếu sự kiện bên trái của rộng (EEDIS), thuật toán khôi phục tính nhất 𝒸1 bằng sự kiện bên trái của 𝒸2 và sự kiện quán Loga cân bằng (EELIS). Độ phức tạp bên phải của 𝒸1 bằng sự kiện bên phải của 𝒸2 . của các thuật toán cũng được thảo luận và chứng minh. CSTT xác suất 𝒦 là một tập hữu hạn các Bài viết này được tổ chức gồm bốn phần. Định nghĩa 2. (Nguyen & cs., 2021). Một RBXS: 𝒦 = {𝓀1 , … , 𝓀𝑛 } Phần một là phần đặt vấn đề. Phần hai trình bày một số khái niệm trong các kết quả công ̅ Trong đó, 𝓀𝑖 = 𝒸𝑖 [𝜌𝑖 ] ∀𝑖 = 1, 𝑛 bố liên quan về CSTT xác suất gồm các định nghĩa và kí hiệu cơ bản trong CSTT xác suất, Số 09 (2023): 87 – 96 89
𝑎𝑟𝑔 min 𝑓 (𝜔 𝑎 ⃖⃗, ⃗) suất 𝒫 : 𝔓(ℰ ) → ℝ[0,1] trên ℰ thoả mãn: (𝜔 ⃗)∈ℝ𝑚+2𝑛 ⃖⃗,𝑎 Định nghĩa 3. (Hàm xác suất). Hàm xác (1) 𝒫 (ℰ ) = 1 với các ràng buộc: (2) 𝒫 (𝐴 ∪ 𝐵) = 𝒫 (𝐴) + 𝒫 (𝐵) 𝐴𝒦 . 𝑎⊺ ≤ ⃖ − 𝜌 𝐴𝒦 . 𝑎⊺ ≥ −𝜌 ̅ ⃗ ⃗ 1 ⃗, ̅ ⃗ ⃗ 𝐴, 𝐵 ∈ ℰ và 𝐴 ∩ 𝐵 = ∅ ∑𝑚 𝜔𝑖 = 1, 𝜔 ≥ ⃖ ⃖⃗ 0⃗ với 𝑖=1 RBXS (F|G)[ρ] thoả mãn 𝒫 ∈ 𝔓(ℰ ), được kí hiệu bởi 𝒫 ⊨ (F|G)[ρ] nếu và chỉ 𝒞𝒦 𝜔 + (𝜌 + 𝑥 − 𝑦)𝒞𝒦 𝜔 = 0 ℇ,+ ⃖⃗ ⃗ ⃖ ⃗ ⃗ ℇ,− ⃖⃗ nếu 𝒫 (𝐹𝐺) = ρ𝒫 (𝐹 ). Một hàm xác suất 𝒫 thoả mãn 𝒦 kí hiệu bởi 𝒫 ⊨ 𝒦 nếu và 𝑎 = (𝑥1 , … , 𝑥𝑛 , 𝑦1 , … , 𝑦𝑛 ) là vectơ phạt ⃗ Định nghĩa 7. (Nguyen & cs., 2021). Đặt chỉ nếu 𝒫 ⊨ 𝓀 ∀𝓀 ∈ 𝒦 . Đặt ℧(𝒦 ) = trung vị của 𝒦 . Độ đo phạt trung vị của {𝒫 ∈ 𝔓(ℰ ): 𝒫 ⊨ 𝒦 } ̅ 𝓀𝑖 ∈ 𝒦 ∀𝑖 = 1, 𝑛 được định nghĩa như sau: 𝑑(𝓀𝑖 ) = |𝑥𝑖 − 𝑦𝑖 | 𝒦 = {𝒸1 [𝜌1 ], … , 𝒸𝑛 [𝜌𝑛 ]} là một CSTT xác Định nghĩa 4. (Nguyen & cs., 2021). Cho suất. Hàm 𝜕𝒦 : ℝ𝑛 → 𝕂 được gọi là hàm [0,1] ̅ Dấu của 𝓀𝑖 ∈ 𝒦 ∀𝑖 = 1, 𝑛 được định đặc trưng của 𝒦 nếu tồn tại 𝜗 = ⃗ (𝜗1 , … , 𝜗𝑛 ) ∈ ℝ𝑛 ⃗ sao cho 𝜕𝒦 (𝜗) = nghĩa như sau: [0,1] −1 nếu 𝑥𝑖 − 𝑦𝑖 < 0 {𝒸1 [𝜌1 ], … , 𝒸𝑛 [𝜌𝑛 ]}. 𝑠(𝓀𝑖 ) = 0 nếu 𝑥𝑖 − 𝑦𝑖 = 0 {1 ngược lại đo không nhất quán 𝒦 trên ℇ là hàm Định nghĩa 5. (Nguyen & cs., 2021). Độ ℐ : 𝕂 → ℝ+ sao cho ℐ (𝒦 ) = 0 nếu và chỉ 2.2. Nguyên lí kì vọng của toán tử khôi nếu ℧(𝒦 ) ≠ ∅ . phục tính nhất quán Phần này trình bày số nguyên lí kì vọng Hàm chỉ tiêu 𝜇: 𝒬 × Λ(ℇ) → ℝ[0,1] được mà các toán tử khôi phục tính nhất quán nên ℧(𝒦1 ) ≠ ℧(𝒦2 )thì 𝒦1 được gọi là tương thoả mãn được mở rộng từ Bona, 2016. Nếu định nghĩa như sau: 𝜇(𝑈, Θ) = {1 nếu Θ ⊨ U đương mở rộng với 𝒦2 , kí hiệu là 𝒦1 ≎ 𝒦1 . 0 ngược lại Nếu ∃𝜋: 𝒦1 → 𝒦2 sao cho 𝜅 ≡ 𝜋(𝜅) với Đặt 𝒞𝒦 = (𝑐𝑖𝑗 ) ∈ ℝ𝑛×𝑚 là ma trận hệ số ℇ,+ + mỗi 𝜅 ∈ 𝒦1 thì 𝒦1 được gọi là tương đương không âm của 𝒦 trên ℇ. Đặt 𝒞𝒦 = (𝑐𝑖𝑗 ) ∈ ℇ,− − bán mở rộng với 𝒦2 , kí hiệu là 𝒦1 ≏ 𝒦2 . Cho 𝑆𝐶(𝒦 ) là tập hợp bao gồm tất cả các ℝ𝑛×𝑚 là ma trận hệ số không dương của 𝒦 RBXS xuất hiện trong 𝒦 . ̅ trên ℇ. Đặt 𝐴𝒦 = (𝑎̅𝑖𝑗 ) ∈ ℝ𝑛×2𝑛 là ma trận đường chéo kép của 𝒦 trên ℇ, trong đó 𝑐𝑖𝑗 = + Cho 𝒦1 , 𝒦2 , 𝒦 ∈ 𝕂. Hàm Γ: 𝕂 → 𝕂 được Định nghĩa 8. (Các nguyên lí kì vọng). 𝜇(𝐹𝑖 𝐺𝑖 , Θ𝑗 ), 𝑐𝑖𝑗 = −𝜇(𝐺𝑖 , Θ𝑗 ) và − ⎧1 ̅ nếu 𝑖 = 𝑗 và 𝑖 = 1, 𝑛 gọi là toán tử khôi phục tính nhất quán biến ⎪ 𝑎̅𝑖𝑗 = ⎨−1 nếu 𝑗 − 𝑖 = 𝑛 và 𝑗 = 𝑛̅̅̅ ̅ 1,2𝑛 hình nếu thoả mãn các nguyên lí sau: + (EXI) Nguyên lí tồn tại: ∀𝒦 ∈ 𝕂: ∃Γ(𝒦 ) ⎪0 ⎩ ngược lại CSTT xác suất luôn tồn tại Γ(𝒦 ). Nguyên lí này phát biểu rằng với mọi 𝒦 = {𝒸1 [𝜌1 ], … , 𝒸𝑛 [𝜌𝑛 ]} là một CSTT xác Định nghĩa 6. (Nguyen & cs., 2021). Cho (GAI) Nguyên lí khuếch đại: ∀𝒦 ∈ 𝕂 suất và 𝜌 = (𝜌1 , … , 𝜌𝑛 ). Đặt 𝑓 : ℝ𝑚+2𝑛 → ℝ∗ ⃗ nếu ∃Γ(𝒦 ) thì Γ(𝒦 ) nhất quán. sao cho 𝑓 (𝜔 𝑎 = ∑𝑛 (𝑥𝑖 + 𝑦𝑖 ). Vectơ phạt ⃖⃗, ⃗) 𝑖=1 trung vị của 𝒦 tương ứng với 𝑎∗ = (𝑥∗ , 𝑦∗ ) ⃗ ⃖ ⃗ ⃗ Nguyên lí khuếch đại cho rằng nếu áp là lời giải của bài toán tối ưu: dụng toán tử khôi phục tính nhất quán biến 90 Số 09 (2023): 87 – 96
KHOA HỌC TỰ NHIÊN dạng được cho một CSTT xác suất thì thu 3. ĐỀ XUẤT XỬ LÍ TÍNH KHÔNG được CSTT xác suất nhất quán. NHẤT QUÁN TRONG CƠ SỞ TRI THỨC (SCR) Nguyên lí bảo toàn cấu trúc: ∀𝒦 ∈ ⃗ ⃗ 𝕂: Γ(𝒦 ) = 𝜕𝒦 (𝜗) với 𝜗 ∈ ℝ𝑛 . 3.1. Các toán tử khôi phục tính nhất quán [0,1] 3.1.1. Toán tử 𝛤 𝑒 bằng). Cho 𝒦 = {𝒸1 [𝜌1 ], … , 𝒸𝑛 [𝜌𝑛 ]}là Nguyên lí này phát biểu rằng khi áp dụng Định nghĩa 9. (Vectơ biến hình cân một CSTT xác suất và ∆ ∈ ℝ[0,1]. Vectơ biến toán tử khôi phục tính nhất biến dạng thì hình cân bằng của 𝒦 được định nghĩa bởi không làm thay đổi cấu trúc của RBXS trong ⃗ 𝜗𝑒 = (𝜗𝑒 , … , 𝜗𝑒 ) sao cho 𝜗𝑒 = 𝜌𝑖 + (0.5 − CSTT xác suất. (CON) Nguyên lí nhất quán: Nếu 𝒦 nhất 1 𝑛 𝑖 quán thì Γ(𝒦 ) = 𝒦 ̅. 𝜌𝑖 )∆ ∀𝑖 = 1, 𝑛 bằng). Hàm biến hình cân bằng 𝜂𝒦 : ℝ[0,1] → 𝑒 Có thể hiểu nguyên lí này là nếu CSTT Định nghĩa 10. (Hàm biến hình cân 𝕂 của 𝒦 được định nghĩa như sau: 𝜂𝒦 (∆) = 𝑒 xác suất đầu vào nhất quán thì CSTT xác suất ⃗ 𝜕𝒦 (𝜗𝑒 ) đã nhất quán không cần sửa đổi. 𝒦1 ≏ 𝒦2 thì Γ(𝒦1 ) ≏ Γ(𝒦2 ). Dễ dàng thấy rằng 𝜂𝒦 (0) = 𝒦 . (IRS) Nguyên lí không hợp cú pháp: Nếu 𝑒 quán biến hình cân bằng). Cho 𝒦 = Nguyên lí này phát biểu rằng nếu áp dụng Định lí 1. (Toán tử khôi phục tính nhất {𝒸1 [𝜌1 ], … , 𝒸𝑛 [𝜌𝑛 ]} là một CSTT xác suất. toán tử khôi phục tính nhất biến dạng trên hai Đặt Γ 𝑒 : 𝕂 → 𝕂 là toán tử khôi phục tính nhất CSTT xác suất tương đương bán mở rộng thì quán biến hình cân bằng. Khi đó tồn tại ∆∗ = hai CSTT xác suất thu được cũng thu được tương đương bán mở rộng. (NOD) Nguyên lí không độc tài: Nếu 𝜅 = 𝑚𝑖𝑛 {∆∈ ℝ[0,1] |ℐ (𝜂𝒦 (∆)) = 0} sao cho 𝑒 (F|G) và G ≢⊺ thì ∃𝒦 : 𝜅 ∈ 𝒦 , 𝜅 ∉ Γ(𝒦 ). Γ 𝑒 (𝒦 ) = 𝜂𝒦 (∆∗ ). 𝑒 Định lí 2. Toán tử Γ 𝑒 thỏa mãn các tính Nguyên lí này phát biểu rằng không có RBXS phi tự nhiên nào mà làm thay đổi trong 3.1.2. Toán tử 𝛤 𝑎 chất EXI, GAI, SCR, CON, IRS, WIA, IIA. bất kỳ CSTT xác suất nào. biến đổi rời rạc: Nếu 𝑆𝐶(𝒦1 ) ∩ 𝑆𝐶(𝒦2 ) = (WIA) Nguyên lí trung lập yếu của các ∅ thì Γ( 𝒦1 ∪ 𝒦2 ) ≎ Γ(𝒦1 ) ∪ Γ(𝒦2 ). 𝒦 = {𝜅1 , … , 𝜅𝑛 } là một CSTT xác suất và Định nghĩa 11. (Vectơ phạt chuẩn). Cho 𝜀 ∈ ℝ[0,1]. Vectơ phạt chuẩn của 𝒦 được Nguyên lí này phát biểu rằng nếu giao của ⃗ định nghĩa bởi 𝛿 = (𝛿1 , … , 𝛿𝑛 ) trong đó 𝛿𝑖 = 𝑠(𝜅𝑖 )𝑑(𝜅𝑖 ) tất cả các RBXS xuất hiện trong hai CSTT 𝛿̂ xác suất là rỗng thì kết quả khôi phục tính 𝛿 ̂ = 𝑚𝑖𝑛{|𝑠(𝜅𝑖 )𝑑(𝜅𝑖 )|: 𝑠(𝜅𝑖 )𝑑(𝜅𝑖 ) ≠ nhất quán của hợp hai CSTT xác suất sẽ và ̅ ̅ tương đương mở rộng với hợp của các kết 0 ∀𝑖 = 1, 𝑛}. Nếu (𝜅𝑖 )𝑑(𝜅𝑖 ) = 0 ∀𝑖 = 1, 𝑛 thì quả khôi phục tính nhất quán của từng CSTT 𝛿 ̂ = 0. xác suất. rời rạc. Nếu Γ(𝒦1 ) ∪ Γ(𝒦2 ) nhất quán thì (IIA) Nguyên lí trung lập của các biến đổi Γ(𝒦1 ) ∪ Γ(𝒦2 ) = Γ( 𝒦1 ∪ 𝒦2 ). Cho 𝒦 = {𝒸1 [𝜌1 ], … , 𝒸𝑛 [𝜌𝑛 ]} là một Định nghĩa 12. (Vectơ biến hình phạt). CSTT xác suất và ∆ ∈ ℝ[0,1]. Vectơ biến hình phạt của 𝒦 được định nghĩa bởi 𝜗𝑎 = ⃗ Nguyên lí này nói rằng kết quả khôi phục (𝜗1 , … , 𝜗𝑛 ) sao cho 𝜗𝑖 = 𝑝(𝜌𝑖 + ∆ 𝛿𝑖 ) ∀𝑖 = 𝑎 𝑎 𝑎 tính nhất của hợp của từng CSTT xác suất là ̅ 1, 𝑛. nhất quán thì kết quả thu được cũng giống như nguyên lí WIA. Số 09 (2023): 87 – 96 91
(2) Đầu ra: 𝒦 ∗ là nhất quán Hàm biến hình phạt 𝜂𝒦 : ℝ[0,1] → 𝕂 của 𝒦 𝑎 Định nghĩa 13. (Hàm biến hình phạt). ⃗ được định nghĩa như sau: 𝜂 𝑎 (∆) = 𝜕𝒦 (𝜗𝑎 ). (3) Tiến trình xử lí: 𝒦 độ đo không nhất quán bằng 0 và ∆ lớn hơn Bước 1: Tính độ đo không nhất quán. Nếu quán biến hình phạt). Cho 𝒦 = Định lí 3. (Toán tử khôi phục tính nhất {𝒸1 [𝜌1 ], … , 𝒸𝑛 [𝜌𝑛 ]} là một CSTT xác suất. 1 thì dừng, ngược lại chuyển bước 2. Đặt Γ 𝑎 : 𝕂 → 𝕂 là toán tử khôi phục tính nhất Bước 2: quán biến hình phạt. Khi đó tồn tại ∆∗ = 𝑚𝑖𝑛 {∆∈ ℝ[0,1] |ℐ (𝜂𝒦 (∆)) = 0} sao cho - Phương pháp EDIS: 𝑎 Γ 𝑎 (𝒦 ) = 𝜂𝒦 (∆∗ ). + Tìm vectơ biến hình cân bằng theo định 𝑎 nghĩa 9. Định lí 4. Toán tử Γ 𝑒 thỏa mãn các tính + Tìm hàm biến hình cân bằng theo định chất EXI, GAI, SCR, CON, NOD, WIA, IIA. nghĩa 10 và định lí 1. 3.1.3. Toán tử 𝛤 𝑙 - Phương pháp ADIS: Cho 𝒦 = {𝒸1 [𝜌1 ], … , 𝒸𝑛 [𝜌𝑛 ]} là một Định nghĩa 14. (Vectơ loga cân bằng). + Tìm vectơ phạt chuẩn theo định nghĩa 11. CSTT xác suất và 𝜀 ∈ ℝ[0,1]. Vectơ loga cân + Tìm vectơ biến hình phạt theo định bằng của 𝒦 được định nghĩa bởi 𝜗𝑙 = ⃗ nghĩa 12. (𝜗1 , … , 𝜗𝑛 ) sao cho 𝜗𝑖 = 𝜌𝑖 + ∆ 𝑙𝑜𝑔 𝜌𝑖 ∀𝑖 = 𝑙 𝑙 𝑙 0.5 + Tìm hàm biến hình phạt theo định nghĩa ̅ 13, định lí 3. 1, 𝑛. - Phương pháp ELIS: Hàm loga cân bằng 𝜂𝒦 : ℝ[0,1] → 𝕂 của 𝑙 Định nghĩa 15. (Hàm loga cân bằng). + Tìm vectơ loga cân bằng theo định 𝒦 được định nghĩa như sau: 𝜂𝒦 (∆) = nghĩa 14. 𝑙 ⃗ 𝜕𝒦 (𝜗𝑙 ). Dễ dàng thấy rằng 𝜂 𝑙 (0) = 𝒦 . + Tìm hàm loga cân bằng theo định nghĩa 𝒦 15 và định lí 5. Bước 3: Trả về CSTT nhất quán 𝒦 ∗ quán loga cân bằng). Cho 𝒦 = Định lí 5. (Toán tử khôi phục tính nhất {𝒸1 [𝜌1 ], … , 𝒸𝑛 [𝜌𝑛 ]} là một CSTT xác suất. Mô hình xử lí tính không nhất quán được Đặt Γ 𝑙 : 𝕂 → 𝕂 là toán tử khôi phục tính nhất thể hiện trong Hình 1. quán loga cân bằng. Khi đó tồn tại ∆∗ = 3.3. Các thuật toán 𝑚𝑖𝑛 {∆∈ ℝ[0,1] |ℐ (𝜂𝒦 (∆)) = 0} sao cho 𝑙 Phần này trình bày các thuật toán khôi Γ 𝑙 (𝒦 ) = 𝜂𝒦 (∆∗ ). 𝑙 phục tính nhất quán trong mô hình được thể Định lí 6. Toán tử Γ 𝑙 thỏa mãn các tính hiện trong Hình 1. Thuật toán khôi phục tính nhất quán biến chất EXI, GAI, SCR, CON, IRS, WIA, IIA. hình cần bằng mở rộng (EEDIS) mô tả tiến 3.2. Mô hình xử lí tính không nhất quán trình xử lí tính không nhất quán trong CSTT xác suất, bao gồm hai giai đoạn chính: (i) tính Bài toán xử lí tính không nhất quán được toán độ đo không nhất quán của CSTT xác định nghĩa như sau: (1) Đầu vào: 𝒦 = {𝒸1 [𝜌1 ], … , 𝒸𝑛 [𝜌𝑛 ]} cân bằng Γ 𝑒 = 𝜂𝒦 = 𝜕𝒦 (𝜗𝑒 , … , 𝜗𝑒 ) của 𝑒 suất mới (dòng 3) và (ii) tìm hàm biến hình 1 𝑛 và ℇ 𝒦 (từ dòng 3 đến dòng 8). 92 Số 09 (2023): 87 – 96
KHOA HỌC TỰ NHIÊN Hình 1. Mô hình khôi phục tính nhất quán Định lí 7. Gọi 𝒩ℐ là độ phức tạp để tính Đầu vào: 〈𝒦 , ℇ〉 độ đo không nhất quán của 𝒦 = Thuật toán EEDIS Đầu ra: 𝒦 ∗ với ℐ (𝒦 ∗ ) = 0 {𝓀1 , … , 𝓀𝑛 } trên ℇ. Độ phức tạp tính toán 1 Function EEDIS (𝒦 , ℇ) của thuật toán EEDIS là 𝒪(𝑛 × 𝒩ℐ ). 𝜖 = 10−3; Δ = 0; 2 begin Thuật toán khôi phục tính nhất quán biến while Δ < 1 and ℐ (Γ 𝑒 (𝒦 )) ≠ 0 3 hình phạt (EADIS) mô tả tiến trình xử lí tính không nhất quán trong CSTT xác suất, bao 3 Δ = Δ + 𝜖; do gồm ba giai đoạn chính: (i) tìm vectơ phạt for 𝒸𝑖 [𝜌𝑖 ] ∈ 𝒦 do 𝜗𝑒 = 𝜌𝑖 + 5 chuẩn của CSTT xác suất (từ dòng 3 đến 16), 𝑖 (0.5 − 𝜌𝑖 )∆; (ii) tính độ đo không nhất quán của CSTT xác phạt Γ 𝑎 = 𝜂𝒦 = 𝜕𝒦 (𝜗𝑎 , … , 𝜗𝑎 ) của 𝒦 (từ 6 𝑎 suất mới (dòng 18) và (iii) tìm hàm biến hình 7 Γ 𝑒 (𝒦 ) = 𝜕𝒦 (𝜗𝑒 , … , 𝜗𝑒 ); 1 𝑛 1 𝑛 dòng 18 đến dòng 27). 𝒦 ∗ = Γ 𝑒 (𝒦 ) 8 end while return 𝒦 ∗ 9 10 11 end Số 09 (2023): 87 – 96 93
Định lí 8. Gọi 𝒩ℐ là độ phức tạp để tính Đầu vào: 〈𝒦 , ℇ〉 độ đo không nhất quán của 𝒦 = Thuật toán EADIS {𝓀1 , … , 𝓀𝑛 } trên ℇ và 𝒩𝑎 là chi phí để tìm Đầu ra: 𝒦 ∗ với ℐ (𝒦 ∗ ) = 0 vectơ phạt chuẩn của 𝒦 . Độ phức tạp tính Function EADIS (𝒦 , ℇ) 𝒪(𝑚𝑎𝑥{𝒩𝑎 , 𝑛 × 𝒩ℐ }). 1 toán của thuật toán EADIS là 𝑎 = (𝑥, 𝑦) = getOV(𝒦 ); ⃗ ⃖ ⃗ ⃗ 2 begin for 𝓀𝑖 ∈ 𝒦 do 3 Thuật toán khôi phục tính nhất quán loga 𝑑(𝓀𝑖 ) = 𝑥𝑖 − 𝑦𝑖 4 cân bằng EELIS mô tả tiến trình xử lí tính if 𝑑(𝓀𝑖 ) < 0 then 𝑠(𝓀𝑖 ) = −1; 5 không nhất quán trong CSTT xác suất, bao gồm hai giai đoạn chính: (i) tính toán độ đo else if 𝑑(𝓀𝑖 ) = 0 then 6 không nhất quán của CSTT xác suất mới 𝑠(𝓀𝑖 ) = 0; 7 Γ 𝑙 = 𝜂𝒦 = 𝜕𝒦 (𝜗𝑙 , … , 𝜗𝑙 ) của 𝒦 (từ dòng 𝑙 (dòng 3) và (ii) tìm hàm biến hình cân bằng 8 else 𝑠(𝓀𝑖 ) = 1; 1 𝑛 3 đến dòng 8). if ∀𝓀𝑖 ∈ 𝒦 : 𝛿𝑖 = 0 then 𝛿 ̂ = 0; 9 endfor Đầu vào: 〈𝒦 , ℇ〉 10 Thuật toán EELIS for 𝓀𝑖 ∈ 𝒦 do Đầu ra: 𝒦 ∗ với ℐ (𝒦 ∗ ) = 0 11 else 1 Function EELIS(𝒦 , ℇ) if 𝛿𝑖 ≠ 0 and 𝛿 ̂ > 𝛿𝑖 then 12 𝛿 ̂ = 𝛿𝑖 ; 13 𝜖 = 10−3; Δ = 0; 2 begin 3 while Δ < 1 and ℐ (Γ 𝑙 (𝒦 )) ≠ 0 do 14 endfor Δ = Δ + 𝜖; 4 for 𝓀𝑖 ∈ 𝒦 do 𝛿𝑖 = 𝛿𝑖̂ ; 15 endif 𝛿 for 𝒸𝑖 [𝜌𝑖 ] ∈ 𝒦 do 𝜗𝑙 = 𝜌𝑖 + 16 5 𝜖 = 10−3; Δ = 0; 𝑖 ∆ 𝑙𝑜𝑔 𝜌 ; 6 0.5 Δ
⃖ ⃗ 𝒦 tương ứng với a∗ = (x∗ , y∗ ) là lời giải của ⃖ ⃗ ⃗ Với ∆∗ = 0.17 là giá trị nhỏ nhất của ∆ KHOA HỌC TỰ NHIÊN sao cho ℐ (Γ 𝑒 (𝒦 )) = 0 , tức là: 𝒦 ∗ = {𝑐1 [0.5], 𝑐2 [0.583], 𝑐3 [0.666], 𝑐4 [0.583], 𝑐5 [0.749]} bài toán tối ưu: 5 arg min (xi + yi ) (ω ⃖ )∈ℝ8+10 ∑ ⃖⃗,a ⃗ là nhất quán. i=1 x1 − y1 ≤ 0.5, x2 − y2 ≤ 0.4, x3 − y3 ≤ 0.3 với các ràng buộc: Bảng 3. Kết quả sử dụng toán tử khôi phục tính nhất quán biến hình phạt x4 − y4 ≤ 0.4, x5 − y5 ≤ 0.2 Γ 𝑎 (𝒦 ) ∆ x1 + 0.5 ≥ y1 , x2 + 0.6 ≥ y2 , x3 + 0.7 ≥ y3 𝑐𝑖 x4 + 0.6 ≥ y4 , x5 + 0.8 ≥ y5 0.059 0.06 1 8 𝑐1 (ω1 + ω2 +ω3 +ω4 ) − (0.5 + x1 − y1 ) ωi = 0 0.559 0.56 1 ∑ 𝑐2 i=1 0.6 0.6 0.6 8 𝑐3 (ω1 + ω2 +ω5 +ω6 ) − (0.6 + x2 − y2 ) ωi = 0 0.7 0.7 0.7 ∑ 𝑐4 i=1 0.6 0.6 0.6 8 𝑐5 (ω1 + ω3 +ω5 +ω7 ) − (0.7 + x3 − y3 ) ωi = 0 ∑ 0.8 0.8 0.8 i=1 ℐ (Γ 𝑎 (𝒦 )) (ω1 + ω2 ) − (0.6 + x4 − y4 )(ω1 + ω2 +ω5 +ω6 ) = 0 0.001 0 0 (𝜔1 + 𝜔3 ) − (0.8 + 𝑥5 − 𝑦5 )(𝜔1 + 𝜔3 +𝜔5 +𝜔7 ) = 0 Với ∆∗ = 0.06 là giá trị nhỏ nhất của ∆ sao choℐ (Γ 𝑎 (𝒦 )) = 0, là 𝒦 ∗ = ⃖⃗ ⃖⃗ ∑8 ωi = 1, ω ≥ 0 i=1 {𝑐1 [0.56], 𝑐2 [0.6], 𝑐3 [0.7], 𝑐4 [0.6], 𝑐5 [0.8]} tức ⃖ ⃗ Ta có a∗ = (0.06,0,0,0,0,0,0,0,0,0) Bảng 1. Vectơ phạt chuẩn của 𝓚 là nhất quán. 𝓀𝑖 𝑑(𝓀𝑖 ) 𝑠(𝓀𝑖 ) 𝑑(𝓀𝑖 )𝑠(𝓀𝑖 ) ⃗ 𝛿 Bảng 4. Kết quả sử dụng toán tử khôi 𝑐1 [0.5] phục tính nhất quán loga cân bằng Γ 𝑙 (𝒦 ) ∆ 𝑐2 [0.6] 0.06 1 0.06 1 𝑐𝑖 𝑐3 [0.7] 0 0 0 0 0.23 0.24 1.0 𝑐1 𝑐4 [0.6] 0 0 0 0 0.5 0.50 0.500 𝑐2 𝑐5 [0.8] 0 0 0 0 0.582 0.581 0.521 𝑐3 0 0 0 0 Ta có 𝛿 ̂ = 0.06 và 𝛿 = (1,0,0,0,0). ⃗ 0.666 0.665 0.554 𝑐4 0.582 0.581 0.521 Bảng 2. Kết quả sử dụng toán tử khôi 𝑐5 0.753 0.751 0.596 ℐ (Γ 𝑙 (𝒦 )) phục tính nhất quán biến hình cân bằng Γ 𝑒 (𝒦 ) ∆ 0.00183 0 0 𝑐𝑖 Với ∆∗ = 0.24 là giá trị nhỏ nhất của ∆ sao 𝑐1 0.16 0.17 1 ℐ (Γ 𝑙 (𝒦 )) = 0, 𝒦∗ = 𝑐2 0.5 0.5 0.5 cho tức là {𝑐1 [0.5], 𝑐2 [0.581], 𝑐3 [0.665], 𝑐4 [0.581], 𝑐5 [0.751]} 𝑐3 0.584 0.583 0.5 𝑐4 0.668 0.666 0.5 là nhất quán. 𝑐5 0.584 0.583 0.5 4. KẾT LUẬN 0.752 0.749 0.5 ℐ (Γ 𝑒 (𝒦 )) Bài báo này trình bày một số cách tiếp cận 0.002 0 0 để xử lí tính không nhất quán của CSTT xác Số 09 (2023): 87 – 96 95
suất. Ý tưởng cốt lõi của các cách tiếp cận này for Inconsistent Knowledge Management, là tập trung vào việc giữ cho cấu trúc của Advanced Information and Knowledge CSTT xác suất và chỉ thay đổi giá trị của các Processing. London: Springer. DOI: RBXS. Ngoài việc tổng hợp hai cách tiếp cận 10.1007/978-1-84628-889-0 xử lí tính không nhất quán của CSTT xác suất Nguyen, V., T., Nguyen, N., T., Tran, T., H., đã được công bố từ các công trình trước đó là & Nguyen, D., K., L. (2018). Method for toán tử khôi phục tính nhất quán biến hình cân restoring consistency in probabilistic bằng và toán tử khôi phục tính nhất quán biến knowledge bases. International Journal of hình phạt, bài báo đã đề xuất toán tử khôi phục Cybernetics and Systems, Vol.49, 317– tính nhất quán loga cân bằng. Toán tử này cũng thoả mãn một số nguyên lí kì vọng và độ 338. DOI: 10.1080/01969722 phức tạp tính toán cũng giống như toán tử khôi .2017.1418674 phục tính nhất quán biến hình cân bằng. Tuy Nguyen, V., T., Nguyen, N., T., Tran, T., H., nhiên, ba thuật toán EDIS, ADIS, ELIS chỉ & Nguyen, D., K., L. (2021). Resolving được thực hiện và đánh giá từ khía cạnh lí Inconsistencies in Probabilistic thuyết. Vì vậy, việc tiến hành thử nghiệm các Knowledge Bases by Quantitative thuật toán trên bộ dữ liệu trong thế giới thực Modification. Proceedings of KSE 2021, là công việc cho các công bố sau. pp.1-4. TÀI LIỆU THAM KHẢO Rodder, W., & Xu, L. (2001). Elimination of Bona, G., D. (2016). Measuring inconsistent knowledge in the inconsistency in probabilistic knowledge probabilistic expertsystem-shell spiri. In bases, Ph.D. dissertation, University of Proc. Proceedings of Symposium Sao Paulo, 2016. Operations Research, pp.260-265. Kern-Isberner, G., & Rodder, W. (2003). Potyka, N. (2016). Solving reasoning Belief revision and information fusion in a problems for probabilistic conditional probabilistic environment. AAAI Press logics with consistent and inconsistent 2003, pp.506-510. information, Ph.D. dissertation, Nguyen, N., T. (2008). Advanced Methods FernUniversitat, Hagen, 2016. 96 Số 09 (2023): 87 – 96