Một phương pháp hỗ trợ xử lý tri thức không nhất quán trong tiến hoá ontology
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, Trường Đại học Khoa học, ĐH Huế
Tập 17, Số 1 (2020)
MỘT PHƯƠNG PHÁP HỖ TRỢ XỬ LÝ TRI THỨC KHÔNG NHẤT QUÁN
TRONG TIẾN HOÁ ONTOLOGY
1*
1*
2
Nguyễn Văn Trung , Nguyễn Thị Bích Lộc , Trần Đình Sơn
1
Khoa Công nghệ Thông tin, Trường Đại học Khoa học, Đại học Huế
2
Cao đẳng Công nghệ Thông tin, Đại học Đà Nẵng
*Email: [email protected]
Ngày nhận bài: 31/12/2019; ngày hoàn thành phản biện: 14/01/2020; ngày duyệt đăng: 02/7/2020
TÓM TẮT
Ontology biểu diễn tri thức của một lĩnh vực cụ thể và đóng vai trò quan trọng trong
các ứng dụng Web ngữ nghĩa. Khi có sự thay đổi về tri thức của lĩnh vực thì ontology
cũng phải được thay đổi – gọi là tiến hoá ontology - theo thông qua việc bổ sung,
chỉnh sửa hoặc xoá các tiên đề để phản ánh tri thức mới. Thách thức lớn nhất trong
quá trình tiến hoá ontology đó là, ngoài việc phản ánh tri thức mới, ontology còn
phải bảo đảm tính nhất quán. Bài báo này đề xuất phương pháp dựa trên khoảng
cách ngữ nghĩa để xây dựng tập tiên đề nhất quán trong quá trình tiến hoá ontology.
Từ khóa: tiến hoá ontology, xử lý tri thức không nhất quán, khoảng cách ngữ nghĩa.
1. MỞ ĐẦU
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” [2]. Thế hệ
web sử dụng dạng thức nội dung này -- gọi là Web ngữ nghĩa (Semantic Web) -- 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.
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ế như tin-sinh học,
tin học trong y tế, quản trị tri thức, công nghệ phần mềm, … 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à OWL2,
49
Một phương pháp hỗ trợ xử lý tri thức không nhất quán trong tiến hoá ontology
được xây dựng dựa trên logic mô tả ꢀℛ풪ℐꢁ(퐃). Sử dụng các bộ lập luận, người ta có thể
truy vấn các thông tin ngay cả khi không được phát biểu tường minh trong ontology.
Đây là lợi ích logic của ontology so với các giải pháp lưu trữ thông tin thế hệ trước.
Các ontology biểu diễn tri thức cho một lĩnh vực cụ thể tương ứng với thế giới
thực thường có nhu cầu thay đổi theo thời gian để phản ánh đúng với thế giới thực. Quá
trình thay đổi này thường được biết đến trong lĩnh vực kỹ nghệ ontology với tên gọi tiến
hoá ontology. Thách thức quan trọng của quá trình tiến hoá ontology đó là phải bảo đảm
tính nhất quán. Điều này được giải thích bởi, nếu ontology không nhất quán thì mọi tiên
đề đều là hệ quả logic của nó. Nói cách khác ontology không nhất quán làm mất đi ích
lợi biểu diễn và truy vấn thông tin.
Người ta đã đưa ra nhiều giải pháp để đảm bảo tính nhất quán của ontology
trong quá trình tiến hoá. Các giải pháp này tựu trung lại đều được căn cứ trên các quy
tắc [1] nhằm đảm bảo tính hợp lệ về cú pháp của ontology theo ràng buộc ngôn ngữ đã
được xác định (ví dụ ngôn ngữ OWL 2 DL, OWL 2 Full, …) và/hoặc đảm bảo quy tắc
đảm bảo không mâu thuẫn về mặt logic của các tiên đề.
Các quy tắc về cú pháp hoàn toàn có thể được kiểm tra và gợi ý để người dùng
tuân thủ trong các hệ thống soạn thảo ontology. Trong khi đó, các quy tắc về logic rất
khó được đảm bảo thực hiện: Các quy tắc này hướng đến giải pháp dò tìm tập tiên đề là
nguyên nhân gây lỗi trong ontology (làm cho ontology là không nhất quán) và sau đó
gợi ý người dùng chỉnh sửa và/hoặc xoá một hoặc nhiều tiên đề này khỏi ontology. Tuy
vậy, người dùng rất khó sử dụng các gợi ý này trong trường hợp họ phải xoá/chỉnh sửa
nhiều tiên đề, do họ không biết nên áp dụng bao nhiêu lần, theo thứ tự nào. Đây chính
là động lực nghiên cứu của bài báo.
Bài báo này đề xuất phương pháp sử dụng khoảng cách ngữ nghĩa để xác định
mức độ ưu tiên khi chọn lựa tập tiên đề trong quá trình tiến hoá ontology. Các phần tiếp
theo của bài báo được trình bày như sau: Phần 2 giới thiệu cách xác định khoảng cách
ngữ nghĩa giữa hai tiên đề của ontology. Phần 3 phân tích và trình bày thuật toán chọn
tập tiên đề tối ưu trong quá trình tiến hoá ontology dựa theo tiêu chuẩn về khoảng cách
ngữ nghĩa giữa hai tiên đề. Phần 4 thảo luận về đóng góp của bài báo và các hướng mở
rộng kết quả.
2. KHOẢNG CÁCH NGỮ NGHĨA GIỮA HAI TIÊN ĐỀ TRONG ONTOLOGY
Một ontology 푂 được thành lập từ hai thành phần 푂 = < 푆, 퐴 >, trong đó, 푆 là bộ
từ vựng là tập hợp tên các thực thể (gồm tên khái niệm 푁퐶, tên thuộc tính 푁푃 , tên kiểu
dữ liệu 푁퐷푇, tên cá thể 푁 ), 퐴 là tập tiên đề của ontology. Ontology 푂 được gọi là nhất
퐼
quán khi tập tiên đề của nó, 퐴, là nhất quán, tức không chứa mâu thuẫn [5].
50
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, Trường Đại học Khoa học, ĐH Huế
Tập 17, Số 1 (2020)
Các tiên đề trong tập hợp 퐴 của ontology 푂 định ra các ràng buộc cũng như mối
quan hệ giữa các thực thể trong 푆. Mối quan hệ thường được xét đến nhiều nhất giữa
các thực thể trong một ontology chính là mối quan hệ phân cấp, theo đó, các thực thể
trong ontology được xếp trên các cây phân cấp: cây phân cấp khái niệm và cây phân cấp
thuộc tính. Vị trí tương đối của các thực thể trên cây phân cấp cho phép xác định khoảng
cách ngữ nghĩa giữa chúng. Do tiên đề được thành lập từ các thực thể nên khoảng cách
ngữ nghĩa giữa hai tiên đề có thể được xây dựng từ khoảng cách ngữ nghĩa giữa các
thực thể cấu tạo nên chúng.
Trên thực tế, mối quan hệ phân cấp giữa các khái niệm và mối quan hệ phân cấp
giữa các thuộc tính (thuộc tính đối tượng, thuộc tính dữ liệu) có bản chất tương tự. Do
đó, không mất tính tổng quát, bài báo chỉ trình bày cách tính khoảng cách ngữ nghĩa
giữa hai khái niệm và sau đó mở rộng cho việc tính khoảng cách giữa hai biểu thức khái
niệm. Phần này của bài báo sẽ trình bày lần lượt khoảng cách ngữ nghĩa giữa hai khái
niệm trong ontology, khoảng cách ngữ nghĩa giữa hai biểu thức khái niệm và cuối cùng
là khoảng cách ngữ nghĩa giữa hai tiên đề.
2.1. Khoảng cách ngữ nghĩa giữa hai khái niệm trong ontology
Trong ontology 푂, với hai khái niệm 푐1, 푐2 ∈ 푁퐶, chúng ta ký hiệu:
( )
−
−
−
퐷푃퓞 푐1 là tập các khái niệm cha trực tiếp của 푐1 trên 풪.
( )
퐷퐶퓞 푐1 là tập các khái niệm con trực tiếp của 푐1 trên 풪.
(
)
퐿퐶푃퓞 푐1, 푐2 là tập các khái niệm cha chung nhỏ nhất của 푐1và 푐2 trên 풪.
Chúng ta định nghĩa số cạnh nối giữa hai khái niệm trên cây phân cấp khái niệm
của ontology 풪 như sau:
Định nghĩa 1. (Số cạnh nối giữa hai khái niệm trên cây phân cấp của ontology)
Gọi 풪 là một ontology. Ta nói 푘 ∈ 푵 là số cạnh nối giữa hai khái niệm 푐1, 푐2 ∈ 푁퐶, ký hiệu là
(
)
휇풪 푐1, 푐2 = 푘 nếu tồn tại 푑1, 푑2, … , 푑푘 là dãy ngắn nhất các khái niệm có tên trong 풪 sao cho:
푐1 ≡ 푑1
푐2 ≡ 푑2
{
(
)
푑푖 ∈ 퐷퐶풪 푑푖+1 ∀ꢂ = 1,2, … , 푘 − 1
Ta quy ước:
(
)
−
−
−
휇퓞 푐, 푐 = 0 với ∀푐 ∈ 푁퐶;
(
)
휇퓞 푐1, 푐2 = +∞ nếu 푐1 ≡⊥ hoặc 푐1 không phải là khái niệm con của 푐2.
Trong trường hợp ontology 풪 đã được xác định rõ, chúng ta có thể bỏ qua chỉ số 풪 để
viết μ thay vì 휇풪 .
Khoảng cách ngữ nghĩa giữa hai khái niệm trên cây phân cấp được định nghĩa
dựa trên thông số số cạnh nối đã được định nghĩa ở trên như sau.
51
Một phương pháp hỗ trợ xử lý tri thức không nhất quán trong tiến hoá ontology
Định nghĩa 2. (Khoảng cách ngữ nghĩa giữa hai khái niệm trên cây phân cấp của
ontology) Gọi 풪 là một ontology. Khoảng cách ngữ nghĩa giữa hai khái niệm 푐1, 푐2 ∈ 푁퐶 ký hiệu
là 훿푂(푐1, 푐2) được xác định theo công thức:
(
)
(
)
휇퓞 푐1, 푐0 + 휇퓞 푐2, 푐0
(
)
( )
| 푐0 ∈ 퐿퐶푃풪 푐1, 푐2 }
훿퓞 푐1, 푐2 = min{
(
)
(
)
(
)
휇퓞 푐1, 푐0 + 휇퓞 푐2, 푐0 + 2. 휇퓞 푐0, ⊤
Trong trường hợp ontology 풪 đã được xác định rõ, chúng ta có thể bỏ qua chỉ số 풪 để viết 훿 thay
vì 훿풪.
Chúng ta có một số nhận xét rút ra trực tiếp từ Định nghĩa 1 và Định nghĩa 2
như mệnh đề dưới đây:
Mệnh đề 1. Gọi 풪 là một ontology. Với mọi khái niệm 푐1, 푐2 ∈ 푁퐶, ta có:
( )
훿 푐1, 푐2 = 훿(푐2, 푐1)
•
•
•
•
(
)
0 ≤ 훿 푐1, 푐2 ≤ 1
(
)
훿 푐1, 푐2 = 0 khi 푐1 ≡ 푐2
(
)
(
)
{ }
훿 푐1, 푐2 = 1 khi 퐿퐶푃퓞 푐1, 푐2 = ⊤ hoặc 푐1 ≡ ⊥ hoặc 푐2 ≡ ⊥
2.2. Khoảng cách ngữ nghĩa giữa hai hai biểu thức khái niệm bất kỳ
Với 풪 là một ontology, chúng ta mở rộng khái niệm khoảng cách ngữ nghĩa giữa
hai khái niệm trong ontology thành “khoảng cách ngữ nghĩa giữa hai biểu thức khái
niệm theo ontology 풪” như sau: Khoảng cách ngữ nghĩa giữa hai biểu thức khái niệm
퐶퐸1, 퐶퐸2 theo ontology 풪 được hiểu là khoảng cách ngữ nghĩa của hai biểu thức khái niệm
này khi đặt trên cây phân cấp khái niệm của ontology 풪.
Theo công thức ở Định nghĩa 2, khoảng cách ngữ nghĩa giữa hai khái niệm
퐶퐸1, 퐶퐸2 theo ontology 풪 là:
(
)
(
)
휇퓞 퐶퐸1, 퐶퐸0 + 휇퓞 퐶퐸2, 퐶퐸0
(
)
( )
| 퐶퐸0 ∈ 퐿퐶푃풪 퐶퐸1, 퐶퐸2 }
훿퓞 퐶퐸1, 퐶퐸2 = min{
)
휇퓞 퐶퐸1, 퐶퐸0 + 휇퓞 퐶퐸2, 퐶퐸0 + 2. 휇퓞 퐶퐸0, ⊤
(
)
(
)
(
Chúng ta có thể tính số cung nối giữa hai biểu thức khái niệm bất kỳ 퐶퐸1và 퐶퐸2
dựa theo số cung nối giữa hai khái niệm có tên của ontology 풪 theo 3 trường hợp như
sau:
- Trường hợp 1) ∃푐1 ∈ 퐶풪: 푐1 ≡ 퐶퐸1. Khi đó:
(
)
(
)
휇 퐶퐸1, 퐶퐸2 = min{ 휇퓞 푐1, 푐 | 푐 ∈ 퐷퐶풪(퐶퐸2)}
- Trường hợp 2) ∃푐2 ∈ 퐶풪: 푐2 ≡ 퐶퐸2. Khi đó:
(
)
(
)
휇퓞 퐶퐸1, 퐶퐸2 = min{ 휇퓞 푐, 푐2 | 푐 ∈ 퐷푃풪(퐶퐸1)}
52
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, Trường Đại học Khoa học, ĐH Huế
Tập 17, Số 1 (2020)
- Trường hợp 3) Không có khái niệm có tên trên 풪 tương đương với 퐶퐸1 hoặc
퐶퐸2. Khi đó:
′
(
)
(
)
(
)
휇퓞 퐶퐸1, 퐶퐸2 = min{ 2 + 휇퓞 푐, 푐′ | 푐 ∈ 퐷푃풪 퐶퐸1 , 푐 ∈ 퐷퐶풪(퐶퐸2)}
Như vậy, bằng cách tính sẵn các thông số μ giữa các cặp khái niệm của ontology
풪 (có thể dùng thuật toán tìm đường đi ngắn nhất giữa các cặp đỉnh như Floyd [3] chẳng
hạn), chúng ta có thể tính nhanh khoảng cách ngữ nghĩa 훿 cho cặp biểu thức khái niệm
bất kỳ.
2.3. Khoảng cách ngữ nghĩa giữa hai tiên đề
Theo tài liệu đặc tả cấu trúc OWL 2, chúng ta luôn xác định được tập biểu thức
khái niệm (cũng như tập biểu thức thuộc tính đối tượng, tập biểu thức thuộc tính dữ
liệu) của một tiền đề bất kỳ của ontology OWL 2. Điều tương tự cũng có thể thực hiện
được với các ngôn ngữ ontology khác. Khoảng cách ngữ nghĩa giữa hai tiên đề theo
ontology tham chiếu có thể được tính bằng trung bình cộng của tất cả các khoảng cách
ngữ nghĩa giữa hai biểu thức khái niệm có trong hai tiên đề đó. Cụ thể như sau:
Định nghĩa 3 (Khoảng cách ngữ nghĩa giữa hai tiên đề). Gọi 푂 = < 푆, 퐴 > là một
ontology. Khoảng cách ngữ nghĩa giữa hai tiên đề Φ, 휓 ∈ 퐴, ký hiệu là 푑풪(Φ, 휓), được định
nghĩa như sau:
∑
퐶퐸 ∈푪푬 Φ ,퐶퐸 ∈푪푬(휓) 훿풪(퐶퐸1, 퐶퐸2)
(
)
1
2
(
)
푑퓞 Φ, 휓 =
,
( )
( )
2. 푐푎푟푑(푪푬 Φ ). 푐푎푟푑(푪푬 ψ )
trong đó:
( )
−
−
푪푬 Φ là tập các biểu thức khái niệm xuất hiện trong tiên đề Φ.
푐푎푟푑(푿) là lực lượng của tập hợp 푿.
Khi đã rõ ontology 푂, chúng ta có thể viết 푑 thay vì 푑푂.
Như vậy, chúng ta luôn luôn xác định được khoảng cách ngữ nghĩa giữa hai tiên
đề bằng cách dựa vào số cung nối giữa hai khái niệm bất kỳ của ontology.
3. XÂY DỰNG TẬP TIÊN ĐỀ NHẤT QUÁN TRONG QUÁ TRÌNH TIẾN HOÁ
ONTOLOGY
Tiến hoá ontology được hiểu là quá trình điều chỉnh (bổ sung, chỉnh sửa, xoá)
một hoặc nhiều tiên đề trong ontology để đáp ứng sự thay đổi của thế giới thực mà
ontology này biểu diễn. Điều kiện cốt lõi nhất của quá trình tiến hoá ontology là phải
giữ cho ontology tính nhất quán.
Thao tác chỉnh sửa tiên đề trong quá trình tiến hoá ontology có thể được xem là
tổng hợp của hai thao tác tuần tự là xoá và bổ sung tiên đề. Mặt khác, nếu ontology đang
53
Một phương pháp hỗ trợ xử lý tri thức không nhất quán trong tiến hoá ontology
là nhất quán thì việc xoá một hoặc nhiều tiên đề khỏi ontology sẽ không làm mất đi tính
nhất quán của nó. Như vậy, vấn đề bảo đảm tính nhất quán trong quá trình tiến hoá
ontology có thể quy về bài toán “bảo đảm tính nhất quán của ontology khi bổ sung mới
một hoặc nhiều tiên đề”. Có thể phát biểu một cách hình thức cho bài toán này như sau:
Gọi 푂 = < 푆, 퐴 > là ontology nhất quán (퐴 là tập tiên đề nhất quán). 퐴푎푑푑 là tập tiên đề
cần bổ sung trong quá trình tiến hoá ontology 푂. Trong trường hợp 퐴 ∪ 퐴푎푑푑 không nhất quán,
hãy tìm ra tập con 퐴∗ ⊂ 퐴 ∪ 퐴푎푑푑 sao cho 퐴∗ là tập tiên đề nhất quán.
3.1. Phân tích yêu cầu tiến hoá
Quá trình tiến hoá ontology thường được thực hiện để đảm bảo ontology phản
ánh đúng thế giới thực. Theo đó, các tiên đề cần bổ sung vào được xem như có giá trị
hơn nhưng tiên đề đã có trong ontology hiện tại. Nói cách khác, chúng ta ưu tiên giữ lại
những tiên đề này trong quá trình tiến hoá. Mặt khác, chúng ta cũng giả thiết rằng, tập
tiên đề cần bồ sung 퐴푎푑푑 là không chứa mâu thuẫn. Chiến lược chọn tập tiên đề tiến hoá
là xây dựng tập tiên đề 퐴′ bằng cách xoá một số ít nhất các tiên đề trong 퐴 sao cho 퐴′ ∪
퐴푎푑푑 là nhất quán.
Một ontology là không nhất quán khi trong ontology có tạo ra cá thể của một khái
niệm không thoả được (unsatisfiable concept) (hoặc thuộc tính đối tượng không thoả được,
hoặc thuộc tính dữ liệu không thoả được). Do sự tương tự của khái niệm và thuộc tính
đối tượng, thuộc tính dữ liệu, bài báo này chỉ xét đến việc xử lý tri thức không nhất quán
với khái niệm không thoả được.
Trên thực tế, với một khái niệm không thoả được trong ontology, người ta có thể
tính ra được tập tiên đề nhỏ nhất sao cho khái niệm đó vẫn không thoả được trong tập tiên đề
này, gọi là MUPS (Minimal unsatisfiability-preserving sub-ontology) [6]. Bằng cách xoá
đi một tiên đề khỏi tập tiên đề MUPS, chúng ta sẽ thu được tập tiên đề nhất quán. Đây
chính là ý tưởng của việc xây dựng tập tiên đề nhất quán trong quá trình tiến hoá [4].
Tuy vậy, chọn tiên đề nào để xoá cũng là một vấn đề đang gây khó khăn cho người
dùng. Bài báo này đề xuất lựa chọn tiên đề có khoảng cách ngữ nghĩa nhỏ nhất đến tiên
đề trong 퐴푎푑푑 để xoá. Lý do cho lựa chọn này là: Tiên đề có khoảng cách ngữ nghĩa nhỏ
nhất đến tập tiên đề muốn thêm vào thì sẽ có “ngữ nghĩa” gần giống với các tiên đề
chuẩn bị thêm vào. Do đó, việc xoá nó đi sẽ làm mất ít ngữ nghĩa hơn.
3.2. Chiến lược chọn tập tiên đề cho ontology tiến hoá
Gọi 푂 = < 푆, 퐴 > là ontology nhất quán ban đầu. 퐴푎푑푑 là tập tiên đề cần bổ sung
trong quá trình tiến hoá ontology 푂. Giả thiết 퐴 ∪ 퐴푎푑푑 là không nhất quán, trong đó 푐푢푠
là khái niệm không thoả được trên tập tiên đề 퐴 ∪ 퐴푎푑푑. Theo phân tích ở phần trước,
chiến lược xây dựng tập tiên đề nhất quán trong quá trình tiến hoá ontology 푂 sẽ được
thực hiện theo hai giai đoạn:
54
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, Trường Đại học Khoa học, ĐH Huế
Tập 17, Số 1 (2020)
(
)
Giai đoạn 1: Tìm một tập tiên đề 퐴푚푖푛 ≔ 푀푈푃푆 푐푢푠, 퐴 ∪ 퐴푎푑푑 sao cho khái niệm
푐푢푠 là không thoả được trong 퐴푚푖푛, đồng thời 퐴푚푖푛 là tối thiểu theo nghĩa:
퐴푚푖푛 ⊆ 퐴 ∪ 퐴푎푑푑 và ∀훼 ∈ 퐴푚푖푛: 푐푢푠 là thoả được trong 퐴푚푖푛\ {훼}.
Giai đoạn 2: Tìm tiên đề 훼∗ ∈ 퐴푚푖푛 sao cho khoảng cách từ nó đến các tiên đề cần
thêm là cực tiểu:
∗
(
)
∀훼 ∈ 퐴푚푖푛, 훽 ∈ 퐴푎푑푑: 푑푂 훼 , 훽 ≤ 푑푂(훼, 훽)
Hiển nhiên rằng, có thể có nhiều khái niệm không thoả trong tập tiên đề 퐴 ∪
퐴푎푑푑. Trong tình huống này, với mỗi khái niệm không thoả, chúng ta áp dụng lần lượt
hai giai đoạn xử lý ở trên để thu được tập tiên đề tối ưu.
Dưới đây là mô tả mã giả cho toàn bộ quá trình chọn tập tiên đề để thực hiện tiến
hoá ontology:
Đầu vào:
- Ontology 푂 =< 푆, 퐴 >;
- Tập tiên đề cần thêm vào: 퐴푎푑푑 với 퐴 ∪ 퐴푎푑푑 là không nhất quán.
Đầu ra:
∗
∗
Tập tiên đề mới 퐴′ nhất quán, sao cho 퐴′ = 퐴∗ ∪ 퐴푎푑푑, 퐴 ⊂ 퐴 và 퐴 lớn nhất có thể
| |
được.
Thủ tục:
Xác định: 퐴∗ ≔ 퐴;
Tính 퐶푈푆 ∶= {푐푢푠 ∈ 푆 | 푐푢푠 푘ℎô푛푔 푡ℎ표ả đượ푐 푡푟표푛푔 퐴 ∪ 퐴푎푑푑};
for 푐푢푠 ∈ 퐶푈푆
∗
(
)
;
Tính 퐴푚푖푛 ≔ 푀푈푃푆 푐푢푠, 퐴 ∪ 퐴푎푑푑
Tìm 훼∗ ∈ 퐴∗ sao cho:
∗
∀훼 ∈ 퐴∗, 훽 ∈ 퐴푎푑푑: 푑푂 훼 , 훽 ≤ 푑푂 훼, 훽
(
)
(
)
Thực hiện gán 퐴∗ ≔ 퐴∗ \ {훼∗}.
Nếu 퐴∗ ∪ 퐴푎푑푑 không còn chứa khái niệm không thoả được thì chấm dứt lặp;
Kết luận tập tiên đề tiến hoá 퐴′ = 퐴∗ ∪ 퐴푎푑푑
.
3.3. Ví dụ minh hoạ
Chúng ta kết thúc phần này bằng một ví dụ minh hoạ cách làm việc theo chiến
lược chọn tập tiên đề tiến hoá dựa vào khoảng cách ngữ nghĩa. Chẳng hạn, cho ontology
푂 với tập tiên đề 퐴 = {퐸푚푝푙표푦푒푒 ⊑ 푃푒푟푠표푛, 푆푡푢푑푒푛푡 ⊑ 푃푒푟푠표푛, 푃ℎ퐷푆푡푢푑푒푛푡 ⊑
( )
푆푡푢푑푒푛푡, 푆푡푎푓푓 ⊑ 퐸푚푝푙표푦푒푒, 푆푡푎푓푓 ⊓ 푆푡푢푑푒푛푡 = ⊥, 푃ℎ퐷푆푡푢푑푒푛푡 푋 }. Tập tiên đề 퐴 hiện
tại không chứa mâu thuẫn. Giả sử, trong quá trình tiến hoá, người ta muốn bổ sung thêm
55
Một phương pháp hỗ trợ xử lý tri thức không nhất quán trong tiến hoá ontology
tiên đề 훼 = 푃ℎ퐷푆푡푢푑푒푛푡 ⊑ 푆푡푎푓푓. Hiển nhiên rằng 퐴 ∪ {훼} có chứa mâu thuẫn. Áp dụng
chiến lược đã nêu ở Phần 3.2, chúng ta tìm cách loại ra khỏi 퐴 một số tiên đề để việc bổ
sung 훼 tạo nên tập tiên đề nhất quán như dưới đây.
Trước hết, xác định 퐴∗ = 퐴.
Khái niệm không thoả xuất hiện trong tập tiên đề 퐴 ∪ {훼} là 푃ℎ퐷푆푡푢푑푒푛푡. Tập
tiên đề MUPS cho khái niệm này chính là { 푃ℎ퐷푆푡푢푑푒푛푡 ⊑ 푆푡푢푑푒푛푡, 훼, 푆푡푎푓푓 ⊑
퐸푚푝푙표푦푒푒, 푆푡푎푓푓 ⊓ 푆푡푢푑푒푛푡 = ⊥}.
Cần phải tìm ra một trong ba tiên đề khác 훼 trong MUPS để loại trừ. Tiêu chí để
lựa chọn là khoảng cách ngữ nghĩa giữa các tiên đề này với 훼.
Ta có:
1
1
(
)
훿 푃ℎ퐷푆푡푢푑푒푛푡, 푆푡푢푑푒푛푡 =
=
1 + 2 × 2
5
1
=
1
(
)
훿 푃ℎ퐷푆푡푢푑푒푛푡, 푆푡푎푓푓 =
1 + 2 × 3
7
1 + 2
=
3
5
(
)
훿 푆푡푎푓푓, 푆푡푢푑푒푛푡 =
1 + 2 + 2 × 1
2 + 1
3
5
(
)
훿 푃ℎ퐷푆푡푢푑푒푛푡, 퐸푚푝푙표푦푒푒 =
=
2 + 1 + 2 × 1
1
1
(
)
훿 푆푡푎푓푓, 퐸푚푝푙표푦푒푒 =
=
1 + 2 × 2
5
Như vậy:
(
)
푑 훼, 푃ℎ퐷푆푡푢푑푒푛푡 ⊆ 푆푡푢푑푒푛푡
1
=
4
(
)
(
)
× (훿 푃ℎ퐷푆푡푢푑푒푛푡, 푆푡푢푑푒푛푡 + 훿 푆푡푎푓푓, 푃ℎ퐷푆푡푢푑푒푛푡
1
1
1
3
1
33
35
(
)
+ 훿 푆푡푎푓푓, 푆푡푢푑푒푛푡 ) = × ( + + ) =
×
4
5
7
5
4
(
)
푑 훼, 푆푡푎푓푓 ⊑ 퐸푚푝푙표푦푒푒
1
=
4
(
)
(
)
× (훿 푃ℎ퐷푆푡푢푑푒푛푡, 푆푡푎푓푓 + 훿 푃ℎ퐷푆푡푢푑푒푛푡, 퐸푚푝푙표푦푒푒
1
1
3
1
1
33
35
(
)
+ 훿 푆푡푎푓푓, 퐸푚푝푙표푦푒푒 ) = × ( + + ) =
×
4
7
5
5
4
56
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, Trường Đại học Khoa học, ĐH Huế
Tập 17, Số 1 (2020)
(
)
푑 훼, 푆푡푎푓푓 ⊓ 푆푡푢푑푒푛푡 = ⊥
1
=
4
(
)
(
)
× (훿 푃ℎ퐷푆푡푢푑푒푛푡, 푆푡푎푓푓 + 훿 푃ℎ퐷푆푡푢푑푒푛푡, 푆푡푢푑푒푛푡
1
1
3
3
1
47
35
(
)
+ 훿 푆푡푎푓푡푡, 푆푡푢푑푒푛푡 ) = × ( + + ) =
×
4
7
5
5
4
Vậy cần phải loại bỏ tiên đề 푃ℎ퐷푆푡푢푑푒푛푡 ⊆ 푆푡푢푑푒푛푡 hoặc tiên đề 푆푡푎푓푓 ⊑
퐸푚푝푙표푦푒푒 ra khỏi 퐴 trước khi bổ sung tiên đề 훼 trong quá trình tiến hoá.
4. KẾT LUẬN
Bài báo trình bày phương pháp sử dụng khoảng cách ngữ nghĩa để xây dựng tập
tiên đề trong quá trình tiến hoá. Đây là đóng góp có ý nghĩa bởi nó sẽ giúp người dùng
có được tiêu chí định lượng cụ thể khi xét duyệt các tiên đề.
Trong một số trường hợp, việc dựa trên khoảng cách ngữ nghĩa cũng không định
ra được duy nhất tiên đề cần loại bỏ. Hướng phát triển tiếp theo của bài báo là xét thêm
một số tiêu chí nữa, chẳng hạn quy tắc được đề xuất bởi [1] để thu gọn lại tập hợp tiên
đề gợi ý loại bỏ.
TÀI LIỆU THAM KHẢO
[1] Leila Bayoudhi, Najla Sassi, and Wassim Jaziri. Overview and Reflexion on OWL 2 DL
Ontology Consistency Rules. In Proceedings of the Second International Conference on
Internet of Things, Data and Cloud Computing, ICC ’17, pages 133:1—-133:8, New York, NY,
USA, 2017 ACM.
[2] Tim Berners-Lee, James Hendler, and Ora Lassila. The semantic web. Scientific American,
284(5):34–43, 2001.
[3] Robert W Floyd. Algorithm 97: shortest path. Communications of the ACM1, 5(6):345, 1962.
[4] Peter Haase, Frank Van Harmelen, Zhisheng Huang, Heiner Stuckenschmidt, and York Sure.
A framework for handling inconsistency in changing ontologies. In The Semantic Web - SWC
2005, volume 3729 LNCS, pages 353–367. Springer, 2005.
[5] Markus Kr¨otzsch, Frantisek Simancik, and Ian Horrocks. A Description Logic Primer. arXiv
preprint arXiv:1201.4089, pages 1–17, jan 2012.
[6] Stefan Schlobach and Ronald Cornet. Non-standard reasoning services for the debugging of
description logic terminologies. In IJCAI Interna tional Joint Conference on Artificial
Intelligence, volume 3, pages 355–360. Morgan Kaufmann, 2003.
57
Một phương pháp hỗ trợ xử lý tri thức không nhất quán trong tiến hoá ontology
A NOVEL METHOD TO RESOLVE INCONSISTENCY
IN ONTOLOGY EVOLUTION
1*
1*
2
Nguyen Van Trung , Nguyen Thi Bich Loc , Tran Dinh Son
1
Faculty of Information Technology, University of Sciences, Hue University
2
College of Information Technology, The University of Danang
*Email: [email protected]
ABSTRACT
Ontology captures domain knowledge and play an important role in Semantic Web
applications. When domain knowledge change, ontology should adapt to change by
adding, editing or deleting its axioms. The big challenge of this process – which
called as ontology evolution – is how to guarantee the consistency state of the
ontology. This paper proposes a novel method based on semantic distance to
formulate consistent set of axioms in ontology evolution process.
Keywords: inconsistency handling, ontology evolution, , semantic distance
58
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, Trường Đại học Khoa học, ĐH Huế
Tập 17, Số 1 (2020)
Nguyễn Văn Trung sinh ngày 25/10/1981 tại Thừa Thiên Huế. Năm 2003,
ông tốt nghiệp cử nhân Tin học; năm 2006, ông nhận bằng thạc sĩ chuyên
ngành Công nghệ Thông tin; năm 2018, ông nhận học vị Tiến sĩ chuyên
ngành Khoa học Máy tính tại trường Đại học Khoa học, Đại học Huế. Từ
năm 2004 đến nay ông giảng dạy tại trường Đại học Khoa học, Đại học
Huế.
Lĩnh vực nghiên cứu: Các hệ thống thông tin, Quản lý và biểu diễn tri thức,
Web ngữ nghĩa, Linked Data, Công nghệ phần mềm.
Nguyễn Thị Bích Lộc sinh ngày 25/05/1979 tại Thừa Thiên Huế. Năm
2004, bà tốt nghiệp kỹ sư chuyên ngành Đảm bảo Toán học cho tin học
tại trường Đại học kỹ thuật Taganrog. Năm 2007 bà nhận bằng thạc sĩ
chuyên ngành Khoa học Máy tính tại trường Đại học Khoa học, Đại học
Huế. Từ năm 2004 đến nay bà giảng dạy tại trường Đại học Khoa học,
Đại học Huế.
Lĩnh vực nghiên cứu: Logic mô tả. Quản lý và biểu diễn tri thức. Lý thuyết
đồ thị. Độ phức tạp tính toán
Trần Đình Sơn sinh ngày 08/11/1974 tại Hải Phòng. Năm 1996, ông tốt
nghiệp đại học chuyên ngành ngành Toán – Tin tại Trường Đại học Khoa
học, Đại học Huế. Năm 2003, ông tốt nghiệp thạc sĩ chuyên ngành Công
nghệ thông tin tại Đại học Đà Nẵng. Từ năm 1996 đến nay, ông giảng
dạy tại Trường Đại học Bách khoa và Trường Cao đẳng Công nghệ
Thông tin, Đại học Đà Nẵng.
Lĩnh vực nghiên cứu: Trí tuệ nhân tạo, Toán rời rạc, Đồ họa và Xử lý ảnh.
59
12 trang
20220
Free
Bạn đang xem tài liệu "Một phương pháp hỗ trợ xử lý tri thức không nhất quán trong tiến hoá 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:
- mot_phuong_phap_ho_tro_xu_ly_tri_thuc_khong_nhat_quan_trong.pdf
