Tóm tắt Luận án Một số phương pháp xử lý tri thức không nhất quán trong Ontology
ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN VĂN TRUNG
MỘT SỐ PHƯƠNG PHÁP
XỬ LÝ TRI THỨC KHÔNG NHẤT QUÁN
TRONG ONTOLOGY
CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH
MÃ SỐ: 62.48.01.01
LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH
HUẾ - NĂM 2018
Công trình này được hoàn thành tại:
Trường Đại học Khoa học - Đại học Huế
Người hướng dẫn khoa học:
PGS. TS. Hoàng Hữu Hạnh, Ban Hợp tác quốc tế, Đại học Huế
Phản biện 1: ......................................................................................
......................................................................................
Phản biện 2: ......................................................................................
......................................................................................
Phản biện 3: ......................................................................................
.......................................................................................
Luận án sẽ được bảo vệ tại Hội đồng chấm luận án cấp Đại học Huế
họp tại Đại học Huế vào lúc ...... giờ ..... ngày ..... tháng ..... năm 2017
Có thể tìm hiểu luận án tại thư viện:
• Thư viện Quốc gia Việt Nam
• Thư viện Trường Đại học Khoa học, Đại học Huế
MỞ ĐẦU
1. Tính cấp thiết của đề tài
Năm 2001, Tim Berners Lee cùng cộng sự đã đưa ra phác thảo cho một “dạng thức
mới về nội dung web mà dạng thức này có ý nghĩa đối với máy tính”. Thế hệ web sử
dụng dạng thức nội dung này, gọi là Web ngữ nghĩa, cho phép máy tính có thể “hiểu”
tri thức được lưu trữ, theo đó có thể chia sẻ và tái sử dụng các cơ sở tri thức trong
các hệ thống thông tin thuộc nhiều lĩnh vực khác nhau. So với Web hiện tại – là một
kho tài liệu được liên kết với nhau, Web ngữ nghĩa là một nền tảng dữ liệu mà trong
đó thông tin được lưu ở dạng định nghĩa tường minh, cho phép máy tính và con người
có thể làm việc được cùng nhau.
Web ngữ nghĩa là một lĩnh vực nghiên cứu đang phát triển nhanh và nhận được
sự quan tâm của cộng đồng nghiên cứu trong thập niên vừa qua. Công nghệ Web ngữ
nghĩa đang được áp dụng vào nhiều lĩnh vực khác nhau trong thực tế. Thành phần
quan trọng trong các ứng dụng web ngữ nghĩa là ontology.
Trong một ontology người ta định nghĩa các thực thể (bao gồm khái niệm, thuộc
tính, cá thể) và mối quan hệ giữa các thực thể này theo ngữ nghĩa được quy định
tường minh bởi một ngôn ngữ logic xác định. Ngôn ngữ ontology được sử dụng phổ
biến và chuẩn hoá bởi tổ chức tiêu chuẩn quốc tế W3C (World Wide Web Consortium)
là OWL. Phiên bản mới nhất của ngôn ngữ này là OWL 2 (được giới thiệu vào năm
2009) dựa trên logic mô tả SROIQ(D).
Vấn đề quan trọng của Web ngữ nghĩa là phải xử lý tri thức không nhất quán trong
các ontology. Điều này bắt nguồn từ chính đặc điểm xây dựng và sử dụng ontology
trong các ứng dụng Web ngữ nghĩa: Đặc tính có thể mở rộng, có thể chia sẻ, tái sử
dụng, phân tán và đa người dùng luôn tiềm ẩn khả năng làm xuất hiện tri thức không
nhất quán trong các ontology.
Trên thực tế, nếu một ontology là không nhất quán, các truy vấn trên nó là không
có nghĩa. Điều này là bởi bất kỳ tiên đề nào cũng là hệ quả logic của một ontology
không nhất quán. Nói cách khác, sự không nhất quán làm mất đi ý nghĩa sử dụng của
ontology trong các ứng dụng Web ngữ nghĩa. Chính vì vậy, xử lý tri thức không nhất
quán trong ontology là bài toán quan trọng, có ý nghĩa thực tiễn và được cộng đồng
khoa học máy tính quan tâm nghiên cứu.
2. Động lực nghiên cứu và cách tiếp cận nghiên cứu của luận án
Các phương pháp xử lý tri thức không nhất quán trong ontology có thể được phân
làm hai nhóm: (1) nhóm phương pháp chấp nhận tồn tại tri thức không nhất quán
trong ontology, và (2) nhóm phương pháp tìm cách loại bỏ tri thức không nhất quán
khỏi ontology:
(1) Các giải pháp thuộc nhóm thứ nhất – chấp nhận tồn tại tri thức không nhất
quán trong ontology. Một số tiếp cận thuộc nhóm này định nghĩa các logic mô tả với
ngữ nghĩa nửa nhất quán và xây dựng ontology dựa trên các logic đó. Việc sử dụng
logic với ngữ nghĩa nửa nhất quán để xây dựng ontology, mặc dù tạo ra được mô hình
biểu diễn tri thức toàn diện nhưng lại khó triển khai trong thực tế do tính phổ biến
của các ngôn ngữ ontology đã được chuẩn hoá và khuyến nghị sử dụng bởi tổ chức
W3C.
1
Trong rất nhiều trường hợp thực tế, các ứng dụng Web ngữ nghĩa cần truy vấn
thông tin được tổng hợp từ các ontology đến từ nhiều nguồn khác nhau (và có thể
không nhất quán) mà không được phép chỉnh sửa hay tạo mới ontology. Một giải pháp
cho vấn đề này là khung lập luận với ontology không nhất quán sử dụng chiến lược
phát triển tuyến tính tập tiên đề diễn giải, được đề xuất bởi nhóm tác giả Zhisheng
Huang, Frank van Harmelen và cộng sự. Khung lập luận này tìm câu trả lời có nghĩa
cho truy vấn với ontology không nhất quán bằng cách chọn ra một tập con gồm các
tiên đề nhất quán từ ontology đầu vào – gọi là tập tiên đề diễn giải truy vấn: tập tiên
đề này có liên quan với truy vấn theo một tiêu chí cụ thể cho trước và có thể trả lời
được truy vấn. Phần quan trọng nhất của khung lập luận với ontology không nhất
quán là hàm chọn để xây dựng tập tiên đề diễn giải truy vấn. Hai hàm chọn điển hình
được nhóm tác giả phát triển là hàm chọn dựa trên sự liên quan cú pháp và hàm chọn
dựa trên khoảng cách ngữ nghĩa theo máy tìm kiếm Google. Hai hàm chọn này đều có
nhược điểm là phụ thuộc vào cú pháp của tiên đề. Khắc phục nhược điểm này chính
là một động lực nghiên cứu của luận án: Luận án đề xuất xây dựng tập tiên đề diễn
giải theo độ liên quan ngữ nghĩa giữa các tiên đề với truy vấn đầu vào. Độ liên quan
này được xác định dựa trên khoảng cách ngữ nghĩa giữa các biểu thức khái niệm khi
đặt chúng trên cây phân cấp khái niệm của một ontology gọi là ontology tham chiếu.
(2) Các giải pháp thuộc nhóm thứ hai – tìm cách loại bỏ tri thức không nhất quán
thông qua việc xây dựng mới ontology từ một hoặc nhiều ontology đầu vào. Việc tạo
mới ontology như vậy diễn ra theo hai chiến lược: chiến lược thứ nhất, dò tìm, đề xuất
chỉnh sửa hoặc loại bỏ một số tiên đề gây nên sự không nhất quán khỏi ontology; và
chiến lược thứ hai, áp dụng lý thuyết đồng thuận để xây dựng tập tiên đề hợp lý nhất
(theo một tiêu chuẩn xác định trước) có thể đại diện cho các ontology đầu vào. Chiến
lược thứ nhất thường được sử dụng để duy trì sự nhất quán của một ontology, trong
khi chiến lược thứ hai thường được sử dụng để xử lý xung đột trong quá trình tích
hợp ontology đến từ nhiều nguồn phân tán, độc lập nhau.
Các công trình xử lý tri thức không nhất quán dựa trên lý thuyết đồng thuận được
tác giả Nguyễn Ngọc Thành đề xuất vào năm 2002 và cùng với các cộng sự mở rộng
trong những năm tiếp theo. Tác giả và cộng sự đã phân loại xung đột trong quá trình
tích hợp ontology theo các mức (mức khái niệm, mức quan hệ, mức cá thể) và đề xuất
phương pháp để xử lý xung đột theo các mức này.
Trong bài toán xử lý xung đột mức khái niệm, cấu trúc khái niệm được xét theo
hai khía cạnh: tập thuộc tính mô tả khái niệm và miền giá trị của thuộc tính. Tuy vậy,
các nghiên cứu xử lý xung đột mức khái niệm trong quá trình tích hợp ontology hiện
nay chỉ tập trung xây dựng danh sách thuộc tính của khái niệm cần tích hợp. Miền
giá trị của các thuộc tính chỉ được xác định bằng cách lấy hợp của các miền giá trị
thành phần. Điều này có nghĩa xung đột về miền giá trị của thuộc tính là chưa được
xét đến. Luận án sẽ áp dụng mô hình tổng quát tích hợp tri thức theo phương pháp
đồng thuận và đề xuất phương án xử lý xung đột mức khái niệm trong quá trình tích
hợp ontology, trong đó có xét đến cả hai khía cạnh: danh sách thuộc tính và miền giá
trị của thuộc tính.
Một mức xung đột khác cũng có thể xảy ra trong quá trình tích hợp ontology đó
là xung đột mức tiên đề, theo đó, tập tiên đề của các ontology tham gia tích hợp là
có sai khác nhau hoặc thậm chí mâu thuẫn nhau. Tình huống này cũng có thể thường
xuyên xảy ra trong quá trình xây dựng ontology theo kiểu phân tán, cộng tác, đa
2
người dùng mà trong đó, một ontology có thể được xây dựng bởi nhiều người dùng tự
nguyện thông qua một wiki ngữ nghĩa hoặc bởi các chuyên gia được thuê. Xung đột
mức tiên đề trong quá trình tích hợp ontology hiện vẫn là bài toán chưa có giải pháp
tốt và thuyết phục như các mức khái niệm, quan hệ hay cá thể. Bằng cách biểu diễn
một tiên đề dưới dạng một literal, mỗi ontology thành phần có thể được biểu diễn
dưới dạng hội của các literal đó. Như vậy, bài toán xử lý xung đột tập tiên đề có thể
được dẫn về bài toán xử lý xung đột ở cấp độ cú pháp của các công thức hội. Luận án
sẽ xây dựng khoảng cách giữa hai công thức hội, phân tích các tiêu chuẩn cho công
thức hội đồng thuận và đề xuất phương án tìm công thức hội đồng thuận. Kết quả
này có thể áp dụng cho bài toán xử lý xung đột mức tiên đề.
3. Mục tiêu, đối tượng và phạm vi nghiên cứu của luận án
Đối tượng nghiên cứu của luận án là ontology, tri thức không nhất quán trong
ontology, và các phương pháp xử lý tri thức không nhất quán trong ontology. Trên cơ
sở phân tích các động lực nghiên cứu, luận án xác định mục tiêu xử lý tri thức không
nhất quán trong ontology theo hai tác vụ truy vấn và tích hợp. Mục tiêu nghiên cứu
cụ thể của luận án được giới hạn theo ba bài toán sau đây:
• Bài toán thứ nhất: Xác định câu trả lời có nghĩa khi truy vấn với ontology không
nhất quán. Trong bài toán này, luận án nghiên cứu đề xuất phương pháp sử dụng
ontology tham chiếu để tính khoảng cách ngữ nghĩa giữa hai khái niệm, giữa hai
biểu thức khái niệm, giữa hai tiên đề. Khoảng cách ngữ nghĩa này sẽ được dùng
để xây dựng hàm chọn của khung lập luận với ontology không nhất quán.
• Bài toán thứ hai: Xử lý xung đột mức khái niệm trong quá trình tích hợp ontology.
Luận án sẽ áp dụng mô hình tổng quát tích hợp tri thức theo phương pháp đồng
thuậnđể tìm đồng thuận cho cấu trúc khái niệm. Sự không nhất quán trong cấu
trúc khái niệm sẽ được giải quyết ở cả danh sách thuộc tính và miền giá trị của
các thuộc tính.
• Bài toán thứ ba: Xử lý xung đột mức tiên đề trong quá trình tích hợp ontology.
Trên cơ sở biểu diễn xung đột mức tiên đề trong quá trình tích hợp ontology dưới
dạng xung đột về cú pháp, luận án đánh giá độ sai khác của các tập tiên đề và
xây dựng phương pháp tìm tập tiên đề đồng thuận theo các tiêu chuẩn dựa trên
độ sai khác này.
Chương 1
TỔNG QUAN VỀ XỬ LÝ TRI THỨC KHÔNG NHẤT
QUÁN TRONG ONTOLOGY
1.1. Ontology và tri thức không nhất quán
Định nghĩa 1.1 (Ontology). Một ontology là một bộ bốn hC, I, R, Zi, trong đó: C
là tập hợp các khái niệm (các lớp); I là tập hợp các cá thể của các khái niệm; R là
tập hợp các quan hệ; Z là tập hợp các tiên đề biểu diễn các ràng buộc toàn vẹn dùng
để mô tả các thực thể (khái niệm, cá thể, quan hệ).
ꢀ
3
Ở Định nghĩa 1.1, R còn được gọi là tập thuộc tính. Người ta phân biệt hai loại
thuộc tính: thuộc tính đối tượng dùng để liên kết các cá thể, và thuộc tính kiểu dữ liệu
dùng để liên kết các cá thể với các giá trị dữ liệu.
Một ontology được gọi là không nhất quán nếu nó không có mô hình nào. Nguyên
nhân dẫn đến điều này là do tập tiên đề của ontology là có chứa mâu thuẫn. Việc truy
vấn một ontology không nhất quán là không có nghĩa do mọi tiên đề đều là hệ quả
logic của ontology không nhất quán.
Luận án xử lý tri thức không nhất quán trong ontology theo hai vấn đề: truy vấn
ontology không nhất quán và xử lý tri thức không nhất quán trong quá trình tích hợp
ontology. Cơ sở lý thuyết cho vấn đề thứ nhất là khung lập luận với ontology không
nhất quán và lý thuyết đồng thuận sẽ được trình bày trong chương tổng quan này.
1.2. Khung lập luận với ontology không nhất quán sử dụng chiến lược phát triển
tuyến tính tập tiên đề diễn giải
1.2.1. Các khái niệm cơ bản
Khung lập luận với ontology không nhất quán được đề xuất bởi Zhisheng Huang,
Frank van Harmelen và cộng sự vào năm 2005. Khung lập luận này xem một ontology
như là một tập hợp các tiên đề và không giới hạn cho loại ngôn ngữ ontology cụ thể
nào. Gọi L là một ngôn ngữ ontology, chúng ta ký hiệu 2L là tập gồm tất cả các tập
tiên đề trên ngôn ngữ L. Ontology Σ có thể xem là một tập tiên đề trên ngôn ngữ L:
Σ ∈ 2L. Để phân biệt với phép suy luận chuẩn |=, chúng ta sử dụng |≈ để ký hiệu
cho phép suy luận không chuẩn, phép suy luận này có thể được tham số hoá để có thể
chấp nhận sự không nhất quán.
Định nghĩa 1.2 (Tính đúng). Một phép suy luận không chuẩn |≈ được gọi là đúng
nếu các tiên đề được suy dẫn từ một ontology không nhất quán Σ theo |≈ thì cũng
được suy dẫn từ một tập con gồm các tiên đề nhất quán của Σ (gọi là ontology con
nhất quán của Σ) bằng phép suy luận chuẩn |=
ꢀ
Định nghĩa 1.3 (Tính có nghĩa). Một kết quả của phép suy luận không chuẩn được
gọi là có nghĩa nếu nó đúng và nhất quán: Σ |≈ φ ⇒ Σ |≈ ¬φ.
Phép suy luận |≈ được gọi là có nghĩa nếu và chỉ nếu mọi câu trả lời của nó đều
là có nghĩa.
ꢀ
Định nghĩa 1.4 (Truy vấn ontology không nhất quán sử dụng phép suy luận không
chuẩn). Một truy vấn φ với ontology không nhất quánΣ sử dụng phép suy luận không
chuẩn |≈ là phép đánh giá các quan hệ hệ quả “Σ |≈ φ?” và “Σ |≈ ¬φ?”. Có thể có
bốn câu trả lời cho truy vấn này tương ứng với bốn trường hợp sau đây.
(a) Quá xác định: Σ |≈ φ và Σ |≈ ¬φ.
(b) Chấp nhận: Σ |≈ φ và Σ |≈ ¬φ.
(c) Bác bỏ: Σ |≈ φ và Σ |≈ ¬φ.
(d) Không xác định: Σ |≈ φ và Σ |≈ ¬φ.
ꢀ
4
Định nghĩa 1.5 (Tính đầy đủ cục bộ). Cho Σ là một ontology không nhất quán,
Σ0 ⊂ Σ là một ontology con nhất quán của Σ. Với φ là một tiên đề, kết quả suy luận
Σ |≈ φ được gọi là đầy đủ cục bộ theo Σ0 nếu: Σ0 |= φ ⇒ Σ |≈ φ.
Phép suy luận |≈ với ontology Σ được gọi là đầy đủ cục bộ theo Σ0 nếu mọi kết
quả suy luận của nó là đầy đủ cục bộ theo Σ0.
ꢀ
Định nghĩa 1.6 (Tính đúng cục bộ). Cho Σ là một ontology không nhất quán,
Σ0 ⊂ Σ là một ontology con nhất quán của Σ. Một trả lời truy vấn φ với Σ được gọi
là đúng cục bộ theo Σ0 nếu và chỉ nếu:Σ |≈ φ ⇒ Σ0 |= φ.
Phép suy luận |≈ với ontology Σ được gọi là là đúng cục bộ theo Σ0 nếu mọi trả
lời truy vấn Σ |≈ φ là đúng cục bộ theo Σ0.
ꢀ
Định nghĩa 1.7 (Tính cực đại). Cho Σ là một ontology không nhất quán, Σ0 ⊂ Σ là
một ontology con nhất quán của Σ. Phép suy luận |≈ với ontology không nhất quán
Σ được gọi là cực đại theo Σ0 nếu:
(Σ0 |= > v ⊥) ∧ (∀Σ00 ⊂ Σ : Σ00 ⊃ Σ0 ⇒ Σ00 |= > v ⊥) ∧ (∀φ : Σ0 |= φ ⇔ Σ |≈
φ) .
ꢀ
Zhisheng Huang và cộng sự đã chỉ ra rằng:
Mệnh đề 1.1. Cho Σ là một ontology không nhất quán, Σ0 ⊂ Σ là ontology con nhất
quán của Σ, |≈ là một phép suy luận không chuẩn, φ là một tiên đề bất kỳ. Khi đó:
(a) Tính đúng cục bộ kéo theo tính đúng và tính có nghĩa.
(b) Tính cực đại kéo theo tính đầy đủ cục bộ.
1.2.2. Hàm chọn
Cho L là một ngôn ngữ ontology, Σ ∈ 2L là một ontology, φ ∈ L là một tiên đề
trên L. Hàm chọn s trả về một tập con của Σ ở bước k > 0 (k ∈ N) trong quá trình
đánh giá truy vấn “Σ |≈ φ?” được định nghĩa tổng quát như sau:
Định nghĩa 1.8 (Hàm chọn). Hàm chọn s là ánh xạ s: 2L × L × N → 2L sao cho
s(Σ, φ, k) ⊆ Σ với ∀Σ ∈ 2L, φ ∈ L, k ∈ N.
ꢀ
Định nghĩa 1.9 (Hàm chọn đơn điệu). Một hàm chọn s được gọi là đơn điệu nếu các
tập con mà nó chọn được là tăng hoặc giảm một cách đơn điệu theo bước lặp.
ꢀ
1.2.3. Phép suy luận không chuẩn sử dụng hàm chọn đơn điệu
Một phép suy luận sử dụng hàm chọn đơn điệu tăng (tương ứng, đơn điệu giảm)
thì được gọi là phép suy luận sử dụng chiến lược mở rộng tuyến tính (tương ứng, rút
gọn tuyến tính). Một chiến lược mở rộng tuyến tính được thực hiện như ở Hình 1.1.
Mệnh đề 1.2 (Tính chất của chiến lược mở rộng tuyến tính). Một phép suy luận sử
dụng chiến lược mở rộng tuyến tính sẽ thoả các tính chất sau đây:
(a) không bao giờ quá xác định (b) có thể không xác định
(c) luôn luôn đúng
(e) luôn luôn đầy đủ cục bộ
(g) luôn luôn đúng cục bộ.
(d) luôn luôn đầy đủ cục bộ
(f) có thể không cực đại
5
Hình 1.1: Chiến lược mở rộng tuyến tính
1.2.4. Phép suy luận không chuẩn sử dụng hàm chọn dựa trên sự liên quan
cú pháp
Hàm chọn dựa trên sự liên quan cú pháp sSyn
Với một tiên đề φ, chúng ta sử dụng I(φ), C(φ), R(φ) để tương ứng ký hiệu cho
tập tên cá thể, tập tên khái niệm và tập tên quan hệ xuất hiện trong tiên đề này.
Định nghĩa 1.10 (Liên quan trực tiếp). Hai tiên đề φ, ψ được gọi là liên quan trực
tiếp với nhau nếu có ít nhất một tên thực thể xuất hiện trong cả φ và ψ, tức là:
ꢀ
ꢁ
ꢀ
ꢁ
ꢀ
ꢁ
I(φ) ∩ I(ψ) = ∅ ∨ C(φ) ∩ C(ψ) = ∅ ∨ R(φ) ∩ R(ψ) = ∅ .
(1.1)
ꢀ
Định nghĩa 1.11 (Liên quan trực tiếp với một tập hợp). Một tiên đề φ được gọi là
liên quan trực tiếp với một tập tiên đề Σ nếu tồn tại một tiên đề ψ ∈ Σ sao cho φ và
ψ là liên quan trực tiếp với nhau.
ꢀ
Định nghĩa 1.12 (Hàm chọn dựa trên sự liên quan cú pháp). Hàm chọn dựa trên sự
liên quan cú pháp được định nghĩa như sau:
2L × L × N → 2L
(Σ, φ, k) → sSyn(Σ, φ, k)
với: sSyn(Σ, φ, 0) := ∅; sSyn(Σ, φ, 1) := {ψ ∈ Σ | ψ liên quan trực tiếp với φ}; và
sSyn(Σ, φ, k) := {ψ ∈ Σ | ψ liên quan trực tiếp với sSyn(Σ, φ, k − 1)} (k > 1).
Phép suy luận không chuẩn sử dụng hàm chọn sSyn
ꢀ
Hàm chọn dựa trên sự liên quan cú pháp sSyn là hàm chọn đơn điệu tăng. Phép
suy luận sử dụng hàm chọn sSyn trong khung lập luận được mô tả ở phần trước, được
6
ký hiệu là |≈Syn, thường phát triển đến tập hợp các tiên đề không nhất quán một cách
nhanh chóng. Để cải thiện điều này, người ta buộc hàm chọn phải trả về một tập
các tiên đề nhất quán Σ00 ở bước k khi sSyn(Σ, φ, k) là không nhất quán, sao cho
sSyn(Σ, φ, k − 1) ⊂ Σ00 ⊂ sSyn(Σ, φ, k). Quy trình này được gọi là quy trình xử lý
quá xác định - ODP của hàm chọn. Tuy nhiên, quá trình xử lý ODP lại dẫn đến vấn
đề gọi là không quyết định được: việc lựa chọn các tập con nhất quán lớn nhất của
s(Σ, φ, k) có thể sinh ra nhiều câu trả lời cho truy vấn Σ |≈Syn φ.
1.2.5. Các nghiên cứu liên quan đến khung lập luận với ontology không
nhất quán sử dụng chiến lược mở rộng tuyến tính tập tiên đề diễn
giải
Hàm chọn đóng vai trò quan trọng khi áp dụng khung lập luận với ontology không
nhất quán sử dụng chiến lược mở rộng tuyến tính tập tiên đề diễn giải. Mục này của
luận án phân tích hai hàm chọn đã được xây dựng – hàm chọn dựa trên sự liên quan
cú pháp và hàm chọn dựa trên độ liên quan ngữ nghĩa sử dụng khoảng cách Google
được chuẩn hoá.
Hàm chọn dựa trên sự liên quan cú pháp có một số nhược điểm:
• Phép suy luận thường xuyên phải sử dụng thủ tục ODP để quay lui.
• Số lượng tiên đề được bổ sung trong một bước lặp là thường là lớn.
Hàm chọn dựa trên độ liên quan ngữ nghĩa sử dụng khoảng cách Google được chuẩn
hoá NGD - Normalized Google Distance được đề xuất để khắc phục được các nhược
điểm trên. Tuy vậy, hàm chọn này cũng có nhược điểm khi phụ thuộc cú pháp của
tiên đề:
• Chiến lược mở rộng tập tiên đề hoàn toàn phụ thuộc vào cú pháp biểu diễn các
thực thể (tên khái niệm, tên vai trò, tên cá thể) trong tiên đề.
• Chiến lược mở rộng tập tiên đề diễn giải không xét các thực thể (tên khái niệm,
tên vai trò, tên cá thể) trong tổng thể biểu thức của chúng.
Để khắc phục các nhược điểm nêu trên, luận án đề xuất phương án đánh giá sự
liên quan của hai tiên đề trong quá trình mở rộng tập tiên đề diễn giải dựa trên ngữ
nghĩa của một ontology tham chiếu: sự liên quan của hai tiên đề được đánh giá dựa
trên khoảng cách ngữ nghĩa giữa các biểu thức khái niệm (trong tiên đề) khi đặt chúng
trên cây phân cấp khái niệm của ontology tham chiếu.
1.3. Xử lý không nhất quán tri thức trong quá trình tích hợp ontology theo phương
pháp đồng thuận
1.3.1. Hồ sơ xung đột
Gọi U là một tập hữu hạn các đối tượng biểu diễn các ý kiến tiềm năng về chủ đề
Q
xung đột đã xác định trước; (U) là tập tất cả các bộ gồm k phần tử lập được từ
Q
U (k ∈ N∗). Mỗi phần tử trong (U) được gọi là một hồ sơ xung đột, hoặc gọi ngắn
gọn là một hồ sơ. Chúng ta phân biệt những lớp hồ sơ xung đột sau đây.
Q
Định nghĩa 1.13 (Phân loại hồ sơ xung đột). Một hồ sơ xung đột X ∈ (U) được
gọi là:
7
(1) Hồ sơ đồng nhất nếu mọi phần tử của nó là giống nhau; nghĩa là X = {n ∗ x}
với x ∈ U và n ∈ N.
(2) Hồ sơ phân biệt được nếu các phần tử của nó là khác nhau từng đôi một.
(3) Bội của một hồ sơ Y, viết là X = n ∗ Y, nếu Y = {x1, x2, . . . , xk} và X =
{n ∗ x1, n ∗ x2, . . . , n ∗ xk} với k, n ∈ N và n > 1.
(4) Hồ sơ chính tắc nếu nó là phân biệt được hoặc là bội của hồ sơ phân biệt được.
ꢀ
1.3.2. Sự không nhất quán tri thức
Sự không nhất quán tri thức của một tập cho trước các tác tử về một chủ đề xác
định có thể được biểu diễn bằng hồ sơ xung đột.
Định nghĩa 1.14 (Sự không nhất quán tri thức). Tri thức của các tác tử khi tham
chiếu về chủ đề s cho trước có thể được lập thành các hồ sơ X+(x) và X−(s). Các hồ
sơ này tương ứng chứa các trạng thái tri thức từ tập vũ trụ U biểu diễn sự khẳng định
và phủ định về chủ đề s của các tác tử. Chúng ta gọi có sự không nhất quán tri thức
hay xung đột tri thức về chủ đề s xuất hiện nếu ít nhất một trong hai hồ sơ X+(s) và
X−(s) là không đồng nhất.
ꢀ
Định nghĩa 1.15 (Hàm đánh giá khoảng cách). Hàm d: U × U → [0, 1] được gọi
là hàm đánh giá khoảng cách giữa hai phần tử trong tập vũ trụ U nếu thoả các tính
chất:
1) Không âm: ∀x, y ∈ U : d(x, y) ≥ 0 ;
2) Phản xạ: ∀x, y ∈ U : d(x, y) = 0 nếu và chỉ nếu x = y ;
3) Đối xứng: ∀x, y ∈ U : d(x, y) = d(y, x) .
ꢀ
Hàm đánh giá khoảng cách được sử dụng làm cơ sở để đánh giá mức độ nhất quán
cũng như xây dựng đồng thuận cho hồ sơ xung đột. Độ nhất quán của hồ sơ xung đột
Q
được đánh giá thông qua hàm c định nghĩa như sau: c : (U) → [0, 1]. Người ta đã
đưa ra bộ tiêu chuẩn P cho hàm nhất quán. (Định nghĩa 1.16)
1.3.3. Hàm đồng thuận
Định nghĩa 1.17. Hàm đồng thuận trong không gian nửa-mêtric (U, d) là ánh xạ
Q
C : (U) → 2U trong đó, 2U ký hiệu tập hợp gồm tất cả các tập con của U.
ꢀ
Định nghĩa 1.18 (Tiêu chuẩn cho hàm đồng thuận). Gọi U là tập vũ trụ, (U, d) là
một không gian nửa-mêtric. Một hàm đồng thuận cần thoả mãn một hoặc nhiều tiêu
chuẩn trong bộ tiêu chuẩn sau đây (gọi là bộ tiêu chuẩn cho hàm đồng thuận): Tính
tin cậy, Tính nhất trí, Tính đơn giản, Tính gần-nhất trí, Tính nhất quán, Tính nhất
quán Condorcet, Tính nhất quán chung, Tính đồng biến, Tính tối ưu O1, Tính tối ưu
O2.
ꢀ
8
Nói chung, không phải từ bất kỳ hồ sơ xung đột nào chúng ta cũng có thể chọn ra
được một giải pháp đồng thuận. Định nghĩa dưới đây cho biết tính khả đồng thuận
theo tiêu chuẩn O1 của một hồ sơ X.
Định nghĩa 1.19 (Tiêu chuẩn khả đồng thuận). Trên không gian nửa-mêtric (U, d),
Q
hồ sơ X ∈ (U) là khả đồng thuận theo tiêu chuẩn O1 nếu và chỉ nếu:
dt_mean(X) ≥ dmin(X) .
(1.2)
ꢀ
1.3.4. Các nghiên cứu liên quan xử lý không nhất quán tri thức trong quá
trình tích hợp ontology bằng phương pháp đồng thuận
Đặc tính có thể mở rộng, có thể chia sẻ được của ontology là một trong những
nhân tố thúc đẩy cho sự phát triển và hiện thực hoá tầm nhìn của web ngữ nghĩa.
Bốn mức xung đột thường gặp trong quá trình tích hợp ontology là xung đột mức
khái niệm, mức cá thể, mức quan hệ và mức tiên đề.
Đối với mức khái niệm, các nghiên cứu hiện nay chỉ tập trung xây dựng danh sách
thuộc tính của khái niệm cần tích hợp, trong khi yếu tố xung đột về miền giá trị của
thuộc tính vẫn chưa được xử lý. Trên cơ sở mô hình tích hợp tri thức tổng quát theo
phương pháp đồng thuận luận án sẽ đề xuất phương án xử lý không nhất quán mức
khái niệm, trong đó có xét đến cả hai khía cạnh: danh sách thuộc tính và miền giá trị
của thuộc tính. Thách thức chính để xử lý xung đột về miền giá trị của các thuộc tính
là phải xây dựng được hàm đánh giá khoảng cách cho các miền giá trị. Nội dung này
sẽ được trình bày trong Chương 3 của luận án.
Hiện nay vẫn chưa có công trình nghiên cứu đầy đủ phương án giải quyết cho bài
toán xử lý xung đột mức tập tiên đề trong quá trình tích hợp ontology nói chung,
cũng như trong quá trình xây dựng ontology cộng tác nói riêng. Bằng cách biểu diễn
một tiên đề dưới dạng một literal, tri thức đóng góp của mỗi người dùng có thể được
biểu diễn dưới dạng hội của các literal đó. Như vậy, bài toán xử lý xung đột về tập
tiên đề trong quá trình xây dựng ontology cộng tác có thể được dẫn về bài toán xử lý
xung đột ở cấp độ cú pháp. Bài toán xử lý xung đột mức tập tiên đề trong quá trình
tích hợp ontology cũng có thể được giải quyết theo cách tương tự. Các thách thức đặt
ra của bài toán này là: (1) Xây dựng hàm đánh giá khoảng cách giữa hai cấu trúc hội
của các literal; và (2) Phân tích mối quan hệ của hàm đánh giá khoảng cách này với
các tiêu chuẩn đồng thuận, từ đó đề ra phương pháp xây dựng đồng thuận cho một
hồ sơ xung đột đầu vào. Chương 4 của luận án sẽ trình bày chi tiết nội dung này.
1.4. Tiểu kết Chương 1
Chương này đã trình bày tổng quan về ontology và sự không nhất quán tri thức
trong ontology. Hai vấn đề được luận án đặt ra cần giải quyết liên quan đến sự không
nhất quán tri thức với ontology là tìm kết quả có nghĩa khi truy vấn với ontology
không nhất quán và xử lý xung đột trong quá trình tích hợp ontology. Các khái niệm
cơ bản và tổng quan về các cách tiếp cận để giải quyết các vấn đề này cũng đã được
giới thiệu trong chương này.
9
Chương 2
SUY LUẬN VỚI ONTOLOGY KHÔNG NHẤT QUÁN
SỬ DỤNG HÀM CHỌN DỰA TRÊN KHOẢNG CÁCH
NGỮ NGHĨA CỦA ONTOLOGY THAM CHIẾU
Ontology có thể được xem là một tập các tiên đề, mà mỗi tiên đề được xây dựng
từ các thực thể khái niệm, vai trò, cá thể theo quy tắc được quy định bởi ngôn ngữ
ontology cụ thể. Các tiên đề bao hàm của ontology cấu trúc nên các cây phân cấp
của các thực thể: cây phân cấp của các khái niệm, cây phân cấp các thuộc tính. Vì
tính tương tự của khái niệm và thuộc tính trên cây phân cấp của chúng nên luận án
chỉ phân tích khoảng cách ngữ nghĩa của hai khái niệm trên cây phân cấp. Có nhiều
phương pháp đánh giá khoảng cách ngữ nghĩa của hai khái niệm. Luận án sử dụng
phương pháp của Wu và Palmer để đánh giá khoảng cách ngữ nghĩa của hai khái niệm
có tên trong ontology: đánh giá khoảng cách ngữ nghĩa của hai khái niệm dựa vào số
cung nối giữa chúng trên cây phân cấp khái niệm của ontology.
2.1. Khoảng cách ngữ nghĩa giữa hai khái niệm trong ontology
Gọi O là một ontology, C là tập tất cả khái niệm có tên trong O. Với c1, c2 ∈ C
O
O
là hai khái niệm có tên trong ontology O, chúng ta sử dụng một số ký hiệu sau:
• DP (c1) là tập các khái niệm có tên trong O là khái niệm cha trực tiếp của c1.
O
• DC (c1) là tập các khái niệm có tên trong O là khái niệm con trực tiếp của c1.
O
• LCP (c1, c2) là tập các khái niệm có tên trong O là khái niệm cha chung tối
O
thiểu của c1 và c2.
Định nghĩa 2.1 (Số cung nối trực tiếp tối thiểu µ giữa hai khái niệm trên ontology).
Gọi O là một ontology. Với hai khái niệm c1, c2 ∈ C , ta nói k ∈ N là số cung nối trực
O
tiếp tối thiểu từ c1 đến c2 trên cây phân cấp khái niệm của O, ký hiệu µO (c1, c2) = k,
nếu tồn tại d1, d2, . . . , dk là dãy ngắn nhất các khái niệm có tên trong O sao cho:
c1 ≡ d1, c2 ≡ dk, di ∈ DC (di+1) với ∀i = 1, 2, . . . , k − 1. Ta quy ước:
O
• µ (c, c) = 0 với ∀c ∈ C .
O
O
• µO (c1, c2) = +∞ khi c1 ≡ ⊥ hoặc O |= c1 v c2 (không tồn tại đường đi từ c1
đến c2 trên cây phân cấp khái niệm của O).
ꢀ
Với một ontology O cùng với tập khái niệm có tên C , chúng ta có thể tính được
O
các giá trị µ (c1, c2) (c1, c2 ∈ C ) bằng cách áp dụng các thuật toán như Floyd,
O
O
Ford-Bellman, . . . trên đồ thị lập được từ quan hệ bao hàm (@) giữa các khái niệm
của ontology.
Định nghĩa 2.2 (Khoảng cách ngữ nghĩa δ của hai khái niệm trên ontology). Khoảng
cách ngữ nghĩa δ của hai khái niệm có tên c1, c2 trong ontology O, ký hiệu là δ (c1, c2),
O
10
được xác định như sau:
n
o
µO (c1, c0) + µO (c2, c0)
δ (c1, c2) := min
O
| c0 ∈ LCP (c1, c2)
O
µO (c1, c0) + µO (c2, c0) + 2.µO (c0, >)
(2.1)
ꢀ
Hàm δ có nhược điểm không đánh giá được khoảng cách ngữ nghĩa giữa hai khái
niệm khái niệm cha là >. Chúng ta có thể khắc phục điều này bằng cách sử dụng
khoảng cách µ0 thay cho µ:
Định nghĩa 2.3 (Số cung nối trực tiếp tối thiểu µ0 giữa hai khái niệm trên cây phân
cấp). Số cung nối trực tiếp tối thiểu µ0 giữa hai khái niệm c1, c2 ∈ C trên cây phân
O
cấp khái niệm O, ký hiệu là µ0 (c1, c2), được xác định như sau:
O
(
µ (c1, c2)
với c2 = > ,
O
µ0O(c1, c2) =
(2.2)
µ (c1, c2) + 1 với c2 = >
O
Trong trường hợp ontology O đã xác định, chúng ta viết µ0 thay vì viết µO0 .
ꢀ
2.2. Khoảng cách ngữ nghĩa giữa hai biểu thức khái niệm theo ontology tham chiếu
Gọi O là một ontology, CE1, CE2 là hai biểu thức khái niệm bất kỳ. Chúng ta
gọi khoảng cách ngữ nghĩa giữa CE1 và CE2 khi đặt chúng trên cây phân cấp khái
niệm của O là khoảng cách ngữ nghĩa giữa hai biểu thức khái niệm theo ontology O.
Ontology O được gọi là ontology tham chiếu (để tính khoảng cách ngữ nghĩa).
Định nghĩa 2.4 (Khoảng cách ngữ nghĩa giữa hai biểu thức khái niệm theo ontology
tham chiếu). Cho O là một ontology, CE1, CE2 là các biểu thức khái niệm. Khoảng
cách giữa CE1 và CE2 theo ontology tham chiếu O được xác định như sau:
δ (CE1, CE2) =
O
n
o
µO (CE1, c0) + µO (CE2, c0)
µO (CE1, c0) + µO (CE2, c0) + 2.µO (c0, >)
min
| c0 ∈ LCP (CE1, CE2)
O
trong đó:
• µO (CE1, CE2) là số cung nối trực tiếp tối thiểu giữa hai biểu thức khái niệm
CE1, CE2 khi đặt chúng trên cây phân cấp khái niệm của ontology O.
• c0 là khái niệm cha chung tối thiểu của CE1 và CE2.
ꢀ
(1) Tập khái niệm cha chung tối thiểu LCP (CE1, CE2) được xác định theo các
O
trường hợp sau đây:
(i) Nếu CE1 v CE2 thì LCP (CE1, CE2) = {CE2};
O
(ii) Nếu CE1 w CE2 thì LCP (CE1, CE2) = {CE1};
O
11
(iii) Trong những trường hợp còn lại, LCP (CE1, CE2) được xác định theo định
O
n
nghĩa về khái niệm cha chung tối thiểu ở Mục 2.1: LCP (CE1, CE2) = c ∈
O
o
ꢀ
ꢁ
C | CE1 v c ∧ CE2 v c ∧ ∀c0 ∈ C : CE1 v c0 ∧ CE2 v c0 ⇒ c v c0
.
O
O
(2) Chúng ta có thể xác định µO (CE1, CE2) nhờ vào các giá trị µO (c1, c2) với
c1, c2 ∈ C theo nguyên tắc quy hoạch động.
O
(i) Tồn tại hai khái niệm c1, c2 ∈ C sao cho c1 ≡ CE1 và c2 ≡ CE2. Đây là trường
O
hợp đơn giản nhất, khi đó: µO (CE1, CE2) = µO (c1, c2) .
(ii) Tồn tại khái niệm c1 ∈ C sao cho c1 ≡ CE1, đồng thời không tồn tại khái niệm
O
có tên nào trên O tương đương với CE2. Khi đó:
µ (CE1, CE2) = µ (c1, CE2) = min{µ (c1, c) + 1 | c ∈ DC (CE2)} .
O
O
O
O
(iii) Tồn tại khái niệm c2 ∈ C sao cho c2 ≡ CE2, đồng thời không có khái niệm có
O
tên nào trên O tương đương với CE1. Khi đó:
µ (CE1, CE2) = µ (CE1, c2) = min{µ (c, c2) + 1 | c ∈ DP (CE1)} .
O
O
O
O
(iv) Không tồn tại khái niệm có tên nào trên O tương đương với các biểu thức khái
niệm CE1, CE2. Khi đó:
µ (CE1, CE2) := min{µ (c, c0) + 2 | c ∈ DP (CE1), c0 ∈ DC (CE2)} .
O
O
O
O
Như vậy, chúng ta luôn xác định được số cung nối trực tiếp tối thiểu giữa hai biểu
thức khái niệm bất kỳ khi đặt chúng trên cây phân cấp khái niệm của ontology tham
chiếu dựa vào các µ (c1, c2) được tính trước cho ∀c1, c2 ∈ C .
O
O
2.3. Khoảng cách ngữ nghĩa giữa hai tiên đề theo ontology tham chiếu
Định nghĩa 2.5 (Khoảng cách ngữ nghĩa giữa hai tập biểu thức khái niệm theo
ontology tham chiếu). Cho O là một ontology, A và B là hai tập hợp khác rỗng gồm
các biểu thức khái niệm. Khoảng cách ngữ nghĩa của hai tập này theo ontology tham
chiếu O, ký hiệu là d (A, B), được xác định như sau:
O
X
δ (CEa, CEb)
O
CEa∈A,CEb∈B
d (A, B) :=
.
(2.3)
O
card(A).card(B)
Ta quy ước, d (A, B) = 1 khi A = ∅ hoặc B = ∅ .
ꢀ
O
Định nghĩa 2.6 (Khoảng cách ngữ nghĩa giữa hai tiên đề theo ontology tham chiếu).
Cho O là một ontology. Khoảng cách ngữ nghĩa giữa hai tiên đề φ, ψ theo ontology
tham chiếu O, ký hiệu là d (φ, ψ), được xác định theo công thức sau:
O
ꢂ
ꢃ
d (φ, ψ) := d CE(φ), CE(ψ) ,
O
O
trong đó, CE(φ), CE(ψ) là tập hợp các biểu thức khái niệm của tiên đề φ, ψ.
ꢀ
12
2.4. Suy luận với ontology không nhất quán sử dụng hàm chọn dựa trên khoảng
cách ngữ nghĩa
Luận án xây dựng hàm chọn dựa trên khoảng cách ngữ nghĩa để sử dụng trong
khung lập luận với ontology không nhất quán mô tả ở Mục 1.2. Hàm chọn này cụ thể
hoá Định nghĩa 1.8 bằng cách sử dụng một ontology tham chiếu để đánh giá khoảng
cách ngữ nghĩa.
Định nghĩa 2.7 (Hàm chọn dựa trên khoảng cách ngữ nghĩa theo ontology tham
chiếu). Gọi O là ontology tham chiếu; Σ là một ontology không nhất quán trên ngôn
ngữ L. Hàm chọn dựa trên khoảng cách ngữ nghĩa theo ontology tham chiếu O, ký
hiệu sOSem, được định nghĩa như sau:
2L × L × N → 2L
(Σ, φ, k) → sOSem(Σ, φ, k)
trong đó sOSem(Σ, φ, k) được định nghĩa theo công thức truy hồi:
- sOSem(Σ, φ, 0) = ∅;
- sOSem(Σ, φ, k) = sSOem(Σ, φ, k − 1) ∪
n
o
ψ ∈ Σ | ¬∃ψ0 ∈ Σ : ψ0 ∈/ sSOem(Σ, φ, k − 1) ∧ d (ψ0, φ) < d (ψ, φ) , (k ≥ 1).
O
O
ꢀ
Hàm chọn sOSem là một hàm chọn đơn điệu tăng. Chúng ta có thể xây dựng phép
suy luận |≈O sử dụng hàm chọn hàm chọn này để mở rộng tuyến tính tập tiên đề diễn
giải theo khung lập luận ở Mục 1.2.
2.5. Thực nghiệm và đánh giá kết quả
Luận án tiến hành thực nghiệm với bộ dữ liệu gồm 3 ontology Madcow, MiniE-
conomy và Transportion được lấy từ tập dữ liệu thử nghiệm thuộc dự án nghiên cứu
trong bộ dữ liệu thử nghiệm.
Bảng 2.1: Các ontology thực nghiệm
Số khái niệm
không thoả được
Ontology
Số khái niệm
Số tiên đề
Madcow
54
1
174
MiniEconomy
Transporation
338
445
51
62
2 314
2 380
Với mỗi ontology thử nghiệm Σ, gọi UΣ là tập các khái niệm không thoả của Σ,
tập các truy vấn được thử nghiệm có dạng Σ |≈ “C v D?00 trong đó C ∈ UΣ và
D ∈ CΣ \ UΣ.
Bảng 2.2 và Bảng 2.3 trình bày kết quả thực nghiệm của hai phép suy luận |≈O
và |≈Syn với các ontology trong bộ dữ liệu thực nghiệm.
Kết quả thực nghiệm cho thấy:
13
Bảng 2.2: So sánh theo số lượng kết quả xác định của truy vấn
Bảng 2.3: So sánh sự phát triển tập tiên đề diễn giải
• Phép suy luận |≈O trả về số lượng kết quả xác định nhiều hơn so với phép suy
luận |≈Syn. Như vậy phép suy luận |≈O cho phép khai thác một ontology không
nhất quán tốt hơn so với phép suy luận |≈Syn
.
• Số tiên đề được bổ sung sau mỗi bước mở rộng tập tiên đề diễn giải ở phép suy
luận |≈O là thấp hơn rất nhiều so với ở phép suy luận |≈Syn. Kết quả này phù
hợp với nhận định hàm chọn sOSem định lượng khoảng cách giữa tiên đề với truy
vấn tốt hơn so với hàm chọn sSyn
.
• Số tiên đề cần loại bỏ trong quy trình xử lý ODP đối với phép suy luận |≈O là
thấp hơn rất nhiều so với ở phép suy luận |≈Syn: nhỏ hơn 10 lần trong các bộ
dữ liệu thử nghiệm. Nhờ vậy, chi phí tính toán cho ODP ở phép suy luận |≈O là
thấp hơn nhiều so với |≈Syn
.
2.6. Tiểu kết Chương 2
Trong chương này luận án đã xây dựng được phương án hiệu quả dựa trên nguyên
lý quy hoạch động để tính khoảng cách ngữ nghĩa giữa hai biểu thức khái niệm theo
một ontology tham chiếu. Luận án cũng đã phân loại tiên đề trong các ontology
OWL 2, phân tách các biểu thức thực thể trong những dạng tiên đề này và làm cơ
sơ sở cho việc tính khoảng cách ngữ nghĩa giữa hai tiên đề theo ontology tham chiếu.
Dựa trên khoảng cách ngữ nghĩa theo ontology tham chiếu giữa hai tiên đề, luận án
đã xây dựng hàm chọn và áp dụng vào khung lập luận với ontology không nhất quán.
Tính hiệu quả của hàm chọn được đề xuất bởi luận án so với với hàm chọn dựa trên
14
sự liên quan cú pháp được thể hiện rõ qua các kết quả thực nghiệm được trình bày
ở cuối chương. Kết quả của chương đã được đăng ở Tạp chí Khoa học và Công nghệ
Trường Đại học Khoa học, Đại học Huế [CT6].
Chương 3
XỬ LÝ XUNG ĐỘT MỨC KHÁI NIỆM
TRONG QUÁ TRÌNH TÍCH HỢP ONTOLOGY
3.1. Mô hình tích hợp tri thức dựa trên lý thuyết đồng thuận
Định nghĩa 3.1 (Thế giới thực (A, V)). Gọi A là tập hợp các thuộc tính. Mỗi thuộc
tính a ∈ A có miền xác định là tập hợp Va gồm các giá trị sơ cấp. Chúng ta giả thiết
rằng một giá trị của thuộc tính a có thể là một tập con của Va hoặc một phần tử
S
của Va. Với V = a∈A Va, ta nói, một thế giới thực có thể được biểu diễn bằng cặp
(A, V).
ꢀ
S
S
Va, 2V
=
a∈T 2Va.
T
Với T ⊆ A, ta ký hiệu VT =
a∈T
Định nghĩa 3.2 (Bộ phức kiểu T). Bộ phức kiểu T được thành lập bởi hàm r: T →
2V sao cho r(a) ⊆ Va, ∀a ∈ T. Thay vì viết r(a) chúng ta có thể viết ra và
T
một bộ kiểu T được viết là rT. Một bộ rT cũng có thể được viết dưới dạng tập
hợp: rT = {(a, ra) | a ∈ T}. Tập hợp gồm tất cả các bộ kiểu T được ký hiệu là
TUPLE(T).
ꢀ
Định nghĩa 3.3 (Bộ sơ cấp kiểu T). Bộ sơ cấp kiểu T được thành lập bởi hàm
r: T → VT sao cho r(a) ∈ Va, ∀a ∈ T. Nếu Va = ∅ thì r(a) = ε, trong đó, ký hiệu
ε biểu diễn một giá trị đặc biệt, được sử dụng khi miền xác định của thuộc tính là
tập hợp rỗng. Tập hợp tất cả các bộ sơ cấp kiểu T được ký hiệu là E-TUPLE(T).
ꢀ
Định nghĩa 3.4 (Tổng của hai bộ). Tổng của hai bộ rT và r0T là một bộ r00 , trong
0
T00
đó T00 = T ∪ T0 và
0
với a ∈ T ∩ T0
với a ∈ T \ T0
với a ∈ T0 \ T
ra ∪ r
ra
ra0
a
ra00 =
ꢀ
Định nghĩa 3.5 (Tích của hai bộ). Tích của hai bộ rT và r0T là một bộ r00 trong
T00
0
đó T00 = T ∩ T0 và r00 = ra ∩ r0 với mỗi a ∈ T00.
ꢀ
a
a
Định nghĩa 3.6 (Quan hệ ≺). Cho r ∈ TUPLE(T) và r0 ∈ TUPLE(T0) trong đó
T ⊆ T0. Ta nói rằng bộ r là được chứa trong bộ r0, ký hiệu là r ≺ r0, nếu ra ⊆ ra0 với
mỗi a ∈ T.
ꢀ
Bài toán tích hợp tri thức được phát biểu như sau: Với một hồ sơ xung đột X =
{ri ∈ TUPLE(Ti) | Ti ⊆ A với i = 1, 2, . . . , n}, cần phải xác định một bộ r∗ kiểu
T∗ ⊆ A sao cho r∗ đại diện tốt nhất cho các bộ đã cho. Bộ đồng thuận r∗ được gọi là
bộ tích hợp cho hồ sơ xung đột X.
15
Đồng thuận là “đại diện tốt nhất” được hiểu là đồng thuận thoả nhiều nhất các
tiêu chuẩn thuộc bộ tiêu chuẩn cho bộ tích hợp (Định nghĩa 3.7): Tính bao đóng
của tri thức - 1 (T1), tính bao đóng của tri thức - 2 (T2), tính nhất quán của tri thức
(T3), tính ưu tiên của tri thức - 1 (T4), tính ưu tiên của tri thức - 2 (T5) và độ tương
tự cực đại (T6).
3.2. Các mức xung đột trong quá trình tích hợp ontology
Người ta phân loại các mức xung đột sau đây trong quá trình tích hợp ontology:
(1) Xung đột mức cá thể : Các cá thể có cùng tên nhưng được đặc tả khác nhau trong
các ontology khác nhau. (2) Xung đột mức khái niệm: Các khái niệm có cùng tên
nhưng có cấu trúc khác nhau trong các ontology khác nhau. (3) Xung đột mức quan
hệ : Cùng hai khái niệm có các mối quan hệ không nhất quán nhau trong các ontology
khác nhau. (4) Xung đột mức tiên đề : Tập tiên đề là khác nhau trong các ontology là
khác nhau.
3.3. Xử lý xung đột mức khái niệm trong quá trình tích hợp ontology
Định nghĩa 3.14 (Bài toán tích hợp ontology mức khái niệm). Gọi O1, O2, . . . , On,
(n ∈ N) là các ontology dựa trên - (A, V). Giả sử khái niệm c trong ontology Oi là
ꢄ
(c, Ai, Vi), i = 1, 2, . . . , n. Từ hồ sơ xung đột X = (Ai, Vi) | i = 1, 2, . . . , n , hãy
xác định cặp (A∗, V∗) biểu diễn tốt nhất cấu trúc cho khái niệm c.
ꢀ
Luận án đề xuất Thuật toán 3.1 xác định cấu trúc tối ưu cho khái niệm.
ꢄ
Định lý 3.1. Với mọi hồ sơ X = (Ai, Vi) | i = 1, 2, . . . , n , Thuật toán 3.1 có các
tính chất sau đây:
(a) Đồng thuận được xác định bởi thuật toán thoả các tiêu chuẩn T1, T2, T3, T4.
(b) Nếu quy tắc R5 (quy tắc về tần suất xuất hiện quá bán của thuộc tính trong hồ
sơ xung đột) không được áp dụng trong thuật toán, đồng thuận được xác định
bởi thuật toán thoả tiêu chuẩn T5.
(c) Đồng thuận được xác định bởi thuật toán thoả mãn một phần tiêu chuẩn T6.
Một số nhận xét về Thuật toán 3.1:
• Thuật toán xác định cấu trúc đồng thuận cho khái niệm c ở cả hai thành phần:
thuộc tính và miền giá trị của nó.
• Việc quyết định có áp dụng quy tắc R5 hay không là tuỳ thuộc vào lựa chọn
“muốn lấy hết tất cả các thuộc tính của khái niệm trong các ontology thành
phần” hay không:
− Lựa chọn “Có” phản ánh ý muốn khai thác tri thức của tất cả các chuyên
gia.
− Lựa chọn “Không” phản ánh ý muốn cần có sự đồng thuận cao từ các tác tử
tri thức.
• Chúng ta có thể chỉnh sửa ở Bước 3 của thuật toán: Nếu Xa là không khả đồng
thuận theo tiêu chuẩn O1, thay vì loại bỏ thuộc tính a ra khỏi A∗, ta xác định
miền giá trị Va∗ là tổng của các miền giá trị trong các cặp (Ai, Vi). Điều chỉnh
16
Thuật toán 3.1: Xác định đồng thuận cấu trúc khái niệm
Đầu vào:
ꢄ
• Hồ sơ xung đột X = (Ai, Vi) | i = 1, 2, . . . , n , trong đó (Ai, Vi) là mô tả cấu trúc của
khái niệm c trong ontology Oi.
• Ua (a ∈ A) là tập vũ trụ, chứa tất cả các giá trị khả dĩ cho Va (miền giá trị của thuộc
tính a).
• da (a ∈ A) là hàm đánh giá khoảng cách giữa hai phần tử trong tập vũ trụ Ua.
Đầu ra: Cặp (A∗, V∗) biểu diễn đồng thuận cấu trúc đại diện của khái niệm c.
begin
S
n
Bước 1
Bước 2
A∗ := i=1 Ai;
foreach a, b ∈ A∗ do
if (a ↔ b hoặc a ↓ b) then
Thay thế a bởi b;
A∗ := A∗ \ {a};
foreach a, b ∈ A∗ do
if (a → b) then
A∗ := A∗ \ {b};
Bước 3
foreach a ∈ A∗ do
n
if (số lần xuất hiện của a trong các cặp (Ai, Vi) là nhỏ hơn ) then
2
A∗ := A∗ \ {a};
else
3a
3b
Thành lập hồ sơ Xa := {V1, V2, . . . , Vk} với Vj là miền giá trị của thuộc tính
a trong cặp (Ai, Vi), j = 1, 2, . . . , k và i = 1, 2, . . . , n;
if (Xa là khả đồng thuận theo tiêu chuẩn O1) then
Chọn Va∗ là đồng thuận O1 trong không gian nửa-mêtric (Ua, da):
ꢄ
da(Va∗, Xa) = min da(Va, Xa) | Va ∈ Xa ;
Đặt Va∗ là miền giá trị cho thuộc tính a trong A∗;
else
A∗ := A∗ \ {a};
Bước 4
foreach a ∈ A∗ do
if (có mối quan hệ a ↔ b hoặc a → b hoặc a ↓ b) then
A∗ := A∗ ∪ {b};
17
này giúp thu thập nhiều đặc tả thuộc tính của khái niệm cần tích hợp (không ưu
tiên sự đồng thuận miền giá trị).
3.4. Vấn đề xây dựng hàm đánh giá khoảng cách cho các miền giá trị của các thuộc
tính
Để áp dụng Thuật toán 3.1, chúng ta phải thành lập hàm đánh giá khoảng cách
da giữa hai miền giá trị của thuộc tính a theo Định nghĩa 1.15. Có hai loại thuộc tính
trong các ontology là thuộc tính đối tượng và thuộc tính dữ liệu: Thuộc tính đối tượng
liên kết các cá thể với nhau, trong khi đó thuộc tính dữ liệu liên kết cá thể với các giá
trị dữ liệu. Luận án đã trình bày cách xây dựng hàm đánh giá khoảng cách cho các
kiểu miền giá trị tương ứng với hai kiểu thuộc tính trong ontology OWL 2 là biểu thức
khái niệm và biểu thức khoảng giá trị.
3.5. Tiểu kết Chương 3
Trong chương này luận án đã đề xuất phương án xử lý xung đột mức khái niệm
trong quá trình tích hợp ontology sử dụng mô hình tích hợp tri thức dựa trên lý thuyết
đồng thuận. Đồng thuận xác định theo phương pháp được đề xuất bởi luận án cũng
được chứng minh là thoả các tiêu chuẩn quan trọng cho một bộ tích hợp. Trong chương
này, luận án cũng đã trình bày phương pháp xây dựng hàm đánh giá khoảng cách cho
các dạng miền giá trị thuộc hai loại thuộc tính đối tượng và thuộc tính dữ liệu trong
quá trình đặc tả khái niệm ontology OWL 2.
Các kết quả của chương này đã được công bố ở Hội thảo International Conference
on Computitational Collective Intelligence - ICCCI (2014) [CT2], đăng trên Tạp chí
Tin học và Điều khiển học (2014) [CT1] và Tạp chí Transactions of Computitational
Collective Intelligence (2016) [CT5].
Chương 4
XỬ LÝ XUNG ĐỘT MỨC TIÊN ĐỀ
TRONG QUÁ TRÌNH TÍCH HỢP ONTOLOGY
4.1. Mô hình xử lý xung đột tri thức cấp độ cú pháp
Giả sử rằng để biểu diễn tri thức, một tác tử hay một chuyên gia sử dụng một tập
hợp hữu hạn L các ký hiệu để biểu diễn các giá trị logic khẳng định, tham chiếu đến
các sự kiện và đối tượng cụ thể trong một thế giới thực. Mỗi ký hiệu biểu diễn cho
một phần tử riêng biệt trong thế giới thực. Một literal tồn tại ở một trong hai dạng
literal dương hoặc literal âm.
Một tác tử có thể đưa ra ý kiến của nó về một chủ đề trong thế giới thực dưới
dạng một công thức hội của các literal như sau: t1 ∧t2 ∧· · ·∧tk, trong đó ti ∈ L hoặc
ti = ¬t0i, với ti00 ∈ L, i = 1, 2, . . . , k và ti = tj với i = j; i, j = 1, 2, . . . , k.
Ta ký hiệu Conj(L) là tập hợp tất cả các công thức hội với các ký hiệu lấy từ tập
hợp L. Một công thức hội x được biểu diễn bằng cặp (x+, x−), trong đó x+ (tương
ứng, x−) gồm các ký hiệu trong công thức thuộc về các literal dương (tương ứng, các
literal âm).
Định nghĩa 4.1. Một công thức hội (x+, x−) với x+, x− ⊆ L được gọi là không xung
đột nếu x+ ∩ x− = ∅ .
ꢀ
18
Tải về để xem bản đầy đủ
28 trang
14400
Free
Bạn đang xem 20 trang mẫu của tài liệu "Tóm tắt Luận án Một số phương pháp xử lý tri thức không nhất quán trong Ontology", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- tom_tat_luan_an_mot_so_phuong_phap_xu_ly_tri_thuc_khong_nhat.pdf
