ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC
TRẦN THANH LƯƠNG
HỌC KHÁI NIỆM CHO CÁC HỆ THỐNG THÔNG TIN
DỰA TRÊN LOGIC MÔ TẢ
LUẬN ÁN TIẾN SĨ MÁY TÍNH
HUẾ, NĂM 2015
ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC
TRẦN THANH LƯƠNG
HỌC KHÁI NIỆM CHO CÁC HỆ THỐNG THÔNG TIN
DỰA TRÊN LOGIC MÔ TẢ
CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH
MÃ SỐ: 62.48.01.01
LUẬN ÁN TIẾN SĨ MÁY TÍNH
Người hướng dẫn khoa học:
1. PGS. TSKH. NGUYỄN ANH LINH
2. TS. HOÀNG THỊ LAN GIAO
HUẾ, NĂM 2015
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu do tôi thực hiện dưới sự hướng
dẫn của PGS. TSKH. Nguyễn Anh Linh và TS. Hoàng Thị Lan Giao. Những nội dung
trong các công trình đã công bố chung với các tác giả khác đã được sự đồng ý của
đồng tác giả khi đưa vào luận án. Các số liệu và kết quả nghiên cứu trình bày trong
luận án là trung thực, khách quan và chưa được công bố bởi tác giả nào trong bất cứ
công trình nào khác.
Nghiên cứu sinh
Trần Thanh Lương
i
LỜI CẢM ƠN
Luận án này được thực hiện và hoàn thành tại Khoa Công nghệ Thông tin,
Trường Đại học Khoa học, Đại học Huế. Trong suốt quá trình học tập, tôi đã nhận
được sự quan tâm, giúp đỡ của thầy giáo, cô giáo hướng dẫn, thầy cô giáo trong Ban
chủ nhiệm Khoa Công nghệ Thông tin, Phòng Đào tạo Sau đại học và Ban giám hiệu
Trường Đại học Khoa học.
Tôi xin bày tỏ lòng biết ơn sâu sắc đến PGS. TSKH. Nguyễn Anh Linh và
TS. Hoàng Thị Lan Giao, là những người Thầy đã tận tình hướng dẫn, động viên
và truyền đạt những kinh nghiệm quý báu trong nghiên cứu khoa học để tôi có thể
hoàn thành luận án này.
Tôi xin chân thành cảm ơn Quý thầy cô giáo trong Ban chủ nhiệm Khoa Công nghệ
Thông tin đã tạo điều kiện thuận lợi trong công tác để tôi có đủ thời gian cho công
việc nghiên cứu của mình. Tôi xin cảm ơn Quý thầy cô và cán bộ của Phòng Đào tạo
Sau Đại học, Ban giám hiệu Trường Đại học Khoa học đã giúp đỡ tôi trong việc hoàn
thành kế hoạch học tập.
Tôi xin trân trọng cảm ơn GS. TSKH. Andrzej Szalas, PGS. TS. Hà Quang Thụy,
PGS. TSKH. Nguyễn Hùng Sơn đã đóng góp nhiều ý kiến quý báu trong quá trình
nghiên cứu và công bố các công trình khoa học. Tôi xin trân trọng cảm ơn PGS. TS.
Lê Mạnh Thạnh đã đọc và đưa ra những góp ý cho luận án.
Tôi xin cảm ơn Quý thầy cô giáo và các anh chị đồng nghiệp trong Khoa Công nghệ
Thông tin đã giúp đỡ, chia sẻ trong quá trình công tác, học tập, nghiên cứu và thực
hiện luận án của mình.
Tôi xin cảm ơn bạn bè đã động viên và đặc biệt là những người thân trong gia
đình luôn luôn quan tâm, ủng hộ và tạo mọi điều kiện thuận lợi nhất cho tôi hoàn
thành luận án này.
Nghiên cứu sinh
Trần Thanh Lương
ii
MỤC LỤC
Lời cam đoan
Lời cảm ơn
Mục lục
Danh mục từ viết tắt
Danh mục các ký hiệu
Danh mục bảng, biểu
Danh mục hình vẽ
Mở đầu
Chương 1. Logic mô tả và cơ sở tri thức
1.1. Tổng quan về logic mô tả . . . . . . . . . . . . . . . . . . . .
1.1.1. Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . .
1.1.2. Ngôn ngữ logic mô tả ALC . . . . . . . . . . . . . . .
1.1.3. Biểu diễn tri thức . . . . . . . . . . . . . . . . . . . .
1.1.4. Khả năng biểu diễn . . . . . . . . . . . . . . . . . . .
1.1.5. Logic mô tả và các tên gọi . . . . . . . . . . . . . . .
1.2. Cú pháp và ngữ nghĩa của logic mô tả . . . . . . . . . . . . .
1.2.1. Logic mô tả ALC reg . . . . . . . . . . . . . . . . . . .
1.2.2. Ngôn ngữ logic mô tả LΣ,Φ . . . . . . . . . . . . . . .
1.3. Các dạng chuẩn . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.1. Dạng chuẩn phủ định của khái niệm . . . . . . . . . .
1.3.2. Dạng chuẩn lưu trữ của khái niệm . . . . . . . . . . .
1.3.3. Dạng chuẩn nghịch đảo của vai trò . . . . . . . . . . .
1.4. Cơ sở tri thức trong logic mô tả . . . . . . . . . . . . . . . .
1.4.1. Bộ tiên đề vai trò . . . . . . . . . . . . . . . . . . . .
1.4.2. Bộ tiên đề thuật ngữ . . . . . . . . . . . . . . . . . .
1.4.3. Bộ khẳng định cá thể . . . . . . . . . . . . . . . . . .
1.4.4. Cơ sở tri thức và mô hình của cơ sở tri thức . . . . .
1.5. Suy luận trong logic mô tả . . . . . . . . . . . . . . . . . . .
1.5.1. Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . .
1.5.2. Các thuật toán suy luận . . . . . . . . . . . . . . . . .
Tiểu kết Chương 1 . . . . . . . . . . . . . . . . . . . . . . . . . .
Chương 2. Mô phỏng hai chiều trong logic mô tả và tính bất
2.1. Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Mô phỏng hai chiều . . . . . . . . . . . . . . . . . . . . . . .
2.2.1. Khái niệm . . . . . . . . . . . . . . . . . . . . . . . .
iii
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
biến
. . . .
. . . .
. . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. .
. .
. .
i
ii
iii
v
vi
vii
viii
1
7
7
7
8
11
13
16
17
17
18
21
21
22
23
24
24
25
25
26
29
29
30
32
33
33
34
34
2.2.2. Quan hệ tương tự hai chiều và quan hệ tương đương . . . . . .
2.3. Tính bất biến đối với mô phỏng hai chiều . . . . . . . . . . . . . . . .
2.3.1. Quan hệ giữa mô phỏng hai chiều với các khái niệm và vai trò
2.3.2. Tính bất biến của khái niệm . . . . . . . . . . . . . . . . . . .
2.3.3. Tính bất biến của cơ sở tri thức . . . . . . . . . . . . . . . . .
2.4. Tính chất Hennessy-Milner đối với mô phỏng hai chiều . . . . . . . .
2.5. Tự mô phỏng hai chiều . . . . . . . . . . . . . . . . . . . . . . . . . .
Tiểu kết Chương 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Chương 3. Học khái niệm cho hệ thống thông tin trong logic mô tả
3.1. Hệ thống thông tin . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1. Hệ thống thông tin truyền thống . . . . . . . . . . . . . . . . .
3.1.2. Hệ thống thông tin dựa trên logic mô tả . . . . . . . . . . . . .
3.2. Học khái niệm trong logic mô tả với Ngữ cảnh (3) . . . . . . . . . . .
3.2.1. Giới thiệu bài toán . . . . . . . . . . . . . . . . . . . . . . . .
3.2.2. Bộ chọn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.3. Tính đơn giản của khái niệm . . . . . . . . . . . . . . . . . . .
3.2.4. Độ đo dựa trên entropy . . . . . . . . . . . . . . . . . . . . . .
3.2.5. Thuật toán học khái niệm trong logic mô tả với Ngữ cảnh (3) .
3.3. Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4. Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . .
Tiểu kết Chương 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Chương 4. Học khái niệm cho cơ sở tri thức trong logic mô tả
4.1. Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2. Phân hoạch miền của diễn dịch . . . . . . . . . . . . . . . . . . . . .
4.3. Học khái niệm trong logic mô tả với Ngữ cảnh (1) . . . . . . . . . . .
4.3.1. Thuật toán BBCL . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.2. Thuật toán dual-BBCL . . . . . . . . . . . . . . . . . . . . . .
4.3.3. Tính đúng đắn của thuật toán BBCL . . . . . . . . . . . . . .
4.3.4. Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4. Học khái niệm trong logic mô tả với Ngữ cảnh (2) . . . . . . . . . . .
4.4.1. Thuật toán BBCL2 . . . . . . . . . . . . . . . . . . . . . . . .
4.4.2. Tính đúng đắn của thuật toán BBCL2 . . . . . . . . . . . . . .
4.4.3. Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . . .
Tiểu kết Chương 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Kết luận
Danh mục các công trình của tác giả
Tài liệu tham khảo
iv
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
40
42
42
47
48
50
54
56
57
57
57
58
61
61
63
68
70
71
74
80
84
86
86
88
91
91
94
94
95
98
98
100
101
103
104
106
107
DANH MỤC TỪ VIẾT TẮT
Từ viết tắt
ABox
Diễn giải
Assertion Box
Bộ khẳng định cá thể
BBCL
Bisimulation-Based Concept Learning
Học khái niệm dựa trên mô phỏng hai chiều
CWA
Close World Assumption
Giả thiết thế giới đóng
LCS
Least Common Subsumers
Bao hàm chung nhỏ nhất
OWA
Open World Assumption
Giả thiết thế giới mở
OWL
Web Ontology Language
Ngôn ngữ Web Ontology
PAC
Probably Approximately Correct
Khả năng học chính xác
RBox
Role Box
Bộ tiên đề vai trò
TBox
Terminology Box
Bộ tiên đề thuật ngữ
W3C
World Wide Web Consortium
Tổ chức tiêu chuẩn quốc tế về World Wide Web
v
DANH MỤC CÁC KÝ HIỆU
Ký hiệu
Diễn giải ý nghĩa
A, B
Các thuộc tính/tên khái niệm
C, D
Các khái niệm
r, s
Các tên vai trò đối tượng
R, S
Các vai trò đối tượng
a, b
Các cá thể
c, d
Các phần tử thuộc miền giá trị
σ, %
Các vai trò dữ liệu
range(A)
Miền giá trị của thuộc tính A
range(σ)
Miền giá trị của vai trò dữ liệu σ
†
Σ, Σ
Các tập ký tự logic mô tả
ΣI , Σ†I
ΣC , Σ†C
ΣA , Σ†A
ΣdA , Σ†dA
ΣnA , Σ†nA
ΣoR , Σ†oR
ΣdR , Σ†dR
†
Các tập cá thể
Φ, Φ
Các tập đặc trưng của logic mô tả
∼Σ† ,Φ† ,I
Quan hệ LΣ† ,Φ† -tự mô phỏng hai chiều lớn nhất
≡Σ† ,Φ† ,I
Quan hệ LΣ† ,Φ† -tương đương
Ref
Khẳng định vai trò phản xạ
Irr
Khẳng định vai trò không phản xạ
Sym
Khẳng định vai trò đối xứng
Tra
Khẳng định vai trò bắc cầu
Dis
Khẳng định vai trò không giao nhau
R
Bộ tiên đề vai trò
T
Bộ tiên đề thuật ngữ
A
Bộ khẳng định cá thể
KB
Cơ sở tri thức trong logic mô tả
Các tập tên khái niệm
Các tập thuộc tính
Các tập thuộc tính rời rạc
Các tập thuộc tính số
Các tập tên vai trò đối tượng
Các tập vai trò dữ liệu
vi
DANH MỤC BẢNG, BIỂU
Bảng 3.1. Kết quả ước lượng trên tập dữ liệu WebKB, PokerHand và Family
với 100 khái niệm ngẫu nhiên trong logic mô tả ALCIQ . . . . . . .
Bảng 3.2. Kết quả ước lượng trên tập dữ liệu Family với 5 khái niệm phổ biến
81
trong logic mô tả ALCI . . . . . . . . . . . . . . . . . . . . . . . . .
Bảng 3.3. Kết quả ước lượng trên tập dữ liệu Poker Hand với 6 tập đối tượng
82
trong logic mô tả ALCQ . . . . . . . . . . . . . . . . . . . . . . . . .
83
vii
DANH MỤC HÌNH VẼ
Hình 1.1.
Hình 1.2.
Hình 1.3.
Hình 1.4.
Diễn dịch của logic mô tả . . . . . . . . . . . . . . .
Kiến trúc của một hệ cơ sở tri thức trong logic mô tả
Diễn dịch của các vai trò phức và khái niệm phức . .
Một minh họa cho cơ sở tri thức của Ví dụ 1.9 . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
9
11
21
27
Hình 2.1. Các diễn dịch I và I 0 trong LΣ,Φ của Ví dụ 1.10 . . . . . . . . . . . .
42
Hình 3.1.
Hình 3.2.
Hình 3.3.
Hình 3.4.
Hình 3.5.
Hình 3.6.
60
76
77
78
79
79
Một minh họa cho cơ sở tri thức của Ví dụ 3.2 . . . . . . . . . . . . .
Quá trình làm mịn phân hoạch của Ví dụ 3.5 . . . . . . . . . . . . .
Quá trình làm mịn phân hoạch của Ví dụ 3.6 . . . . . . . . . . . . .
Hệ thống thông tin tương ứng với cơ sở tri thức trong Ví dụ 3.7 . . .
Quá trình làm mịn phân hoạch sử dụng các bộ chọn đơn giản . . . .
Quá trình làm mịn phân hoạch sử dụng các bộ chọn đơn giản và mở rộng
Hình 4.1. Quá trình làm mịn phân hoạch của Ví dụ 4.1
Hình 4.2. Quá trình làm mịn phân hoạch của Ví dụ 4.2
viii
. . . . . . . . . . . . .
. . . . . . . . . . . . .
90
91
MỞ ĐẦU
Logic mô tả (Description Logics) là một họ các ngôn ngữ hình thức rất thích hợp
cho việc biểu diễn và suy luận tri thức trong một miền quan tâm cụ thể [2]. Trong
logic mô tả, miền quan tâm được mô tả thông qua các thuật ngữ về cá thể, khái niệm
và vai trò. Một cá thể đại diện cho một đối tượng, một khái niệm đại diện cho một tập
các đối tượng và một vai trò đại diện cho một quan hệ hai ngôi giữa các đối tượng.
Các khái niệm phức được xây dựng từ các tên khái niệm, tên vai trò và tên cá thể
bằng cách kết hợp với các tạo tử.
Logic mô tả có tầm quan trọng đặc biệt trong việc cung cấp mô hình lý thuyết
cho các hệ thống ngữ nghĩa. Nó là nền tảng cơ bản trong việc xây dựng các ngôn ngữ
để mô hình hóa các ontology, trong đó Web Ontology Language (OWL) là ngôn ngữ
được tổ chức tiêu chuẩn quốc tế World Wide Web Consortium (W3C) khuyến nghị
sử dụng cho các hệ thống Web ngữ nghĩa (Semantic Web). Về cơ bản, OWL là một
ngôn ngữ dựa trên các logic mô tả [25], [26], [27]. Phiên bản đầu tiên của OWL (được
giới thiệu vào năm 2004) dựa trên logic mô tả SHOIN và SHOIQ [25], [27], phiên
bản thứ hai của OWL là OWL 2 (được giới thiệu năm 2009) dựa trên logic mô tả
SROIQ [26]. Logic mô tả SHOIN , SHOIQ và SROIQ có khả năng biểu diễn rất
tốt nhưng lại có độ phức tạp tính toán đối với các thuật toán suy luận rất cao (tương
ứng là NExpTime-đầy đủ cho SHOIN , SHOIQ và NExpTime-khó cho SROIQ)
và độ phức tạp dữ liệu cũng cao (NP-khó) đối với những bài toán suy luận cơ bản.
Do vây, W3C khuyến khích nên sử dụng OWL 2 EL, OWL 2 QL và OWL 2 RL, là
những ngôn ngữ con của OWL 2 Full với độ phức tạp dữ liệu đa thức tương ứng với
miền quan tâm, mô để hình hóa các hệ thống ngữ nghĩa.
Web ngữ nghĩa là một lĩnh vực đang phát triển rất 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ế, trình duyệt web ngữ nghĩa, quản trị tri thức, kỹ nghệ phần mềm, . . .
Một trong các tầng cơ bản và đóng vai trò quan trọng trong Web ngữ nghĩa là ontology
- thành phần được sử dụng để biểu diễn tri thức và suy luận cho Web ngữ nghĩa.
Xây dựng ontology cho các hệ thống Web ngữ nghĩa và đặc tả các khái niệm phù
hợp là một trong những vấn đề rất được quan tâm trong công nghệ ontology. Do vậy,
bài toán đặt ra là cần tìm được các khái niệm quan trọng và xây dựng được định nghĩa
1
cho các khái niệm đó. Học khái niệm trong logic mô tả nhằm mục đích kiểm tra, suy
luận và tìm ra được các khái niệm này phục vụ cho các ứng dụng cụ thể.
Vấn đề học khái niệm trong logic mô tả tương tự như phân lớp nhị phân trong học
máy truyền thống. Tuy nhiên, việc học khái niệm trong ngữ cảnh logic mô tả khác với
học máy truyền thống ở điểm, các đối tượng không chỉ được đặc tả bằng các thuộc
tính mà còn được đặc tả bằng các mối quan hệ giữa các đối tượng. Các mối quan hệ
này là một trong những yếu tố làm giàu thêm ngữ nghĩa của hệ thống huấn luyện.
Do đó, các phương pháp học khái niệm trong logic mô tả cần phải tận dụng được
chúng như là một lợi thế.
Thông qua việc khảo sát các công trình [4], [17], [32], [35], [15], [16], [36], [44], chúng
tôi khái quát vấn đề học khái niệm trong logic mô tả theo ba ngữ cảnh chính như sau:
• Ngữ cảnh (1): Cho cơ sở tri thức KB trong logic mô tả LΣ,Φ và các tập các cá
thể E + , E − . Học khái niệm C trong LΣ,Φ sao cho:
1. KB |= C(a) với mọi a ∈ E + , và
2. KB |= ¬C(a) với mọi a ∈ E − .
trong đó, tập E + chứa các mẫu dương và E − chứa các mẫu âm của C.
• Ngữ cảnh (2): Ngữ cảnh này khác với ngữ cảnh đã đề cập ở trên là điều kiện
thứ hai được thay bằng một điều kiện yếu hơn:
1. KB |= C(a) với mọi a ∈ E + , và
2. KB 6|= C(a) với mọi a ∈ E − .
• Ngữ cảnh (3): Cho một diễn dịch I và các tập các cá thể E + , E − . Học khái
niệm C trong logic mô tả LΣ,Φ sao cho:
1. I |= C(a) với mọi a ∈ E + , và
2. I |= ¬C(a) với mọi a ∈ E − .
Chú ý rằng I |= ¬C(a) tương đồng với I 6|= C(a).
Mô tả chi tiết của các ngữ cảnh được trình bày trong các chương tiếp theo, trong
đó Ngữ cảnh (1) được trình bày trong Mục 3.2, Ngữ cảnh (2) được trình bày trong
Mục 4.3 và Ngữ cảnh (3) được trình bày trong Mục 4.4.
Học khái niệm trong logic mô tả đã được nhiều nhà khoa học quan tâm nghiên
cứu và chia thành ba hướng tiếp cận chính. Hướng tiếp cận thứ nhất tập trung vào
khả năng học trong logic mô tả [10], [11], [19] và xây dựng một số thuật toán đơn giản
2
liên quan [51], [11], [19], [33]. Hướng tiếp cận thứ hai nghiên cứu học khái niệm trong
logic mô tả bằng cách sử dụng các toán tử làm mịn (refinement operators) [4], [17], [32],
[35], [15], [16], [36]. Hướng tiếp cận thứ ba khai thác mô phỏng hai chiều (bisimulation)
cho bài toán học khái niệm trong logic mô tả [44].
Quinlan nghiên cứu việc học các định nghĩa của mệnh đề Horn từ các dữ liệu được
biểu diễn thông qua các quan hệ và đề xuất thuật toán học Foil [51]. Cohen và Hirsh
nghiên cứu lý thuyết về khả năng học (Probably Approximately Correct - PAC) trong
logic mô tả và đề xuất thuật toán học khái niệm LCSLearn dựa trên các “bao hàm
chung nhỏ nhất” (least common subsumers) [10], [11]. Frazier và Pitt đã nghiên cứu
về khả năng học trong logic mô tả Classic bằng cách sử dụng các truy vấn trên mô
hình học PAC [19]. Lambrix và Larocchia đã đề xuất một thuật toán học khái niệm
đơn giản dựa trên việc chuẩn hóa khái niệm và lựa chọn khái niệm thông qua các thể
hiện của dạng chuẩn hóa [33].
Trong hướng tiếp cận thứ hai, Badea và Nienhuys-Cheng nghiên cứu học khái niệm
trong logic mô tả ALER bằng cách sử dụng toán tử làm mịn như trong lập trình logic
đệ quy [4]. Các tác giả đã giới thiệu một số tính chất của toán tử làm mịn và sử dụng
chúng để thực hiện tìm kiếm theo chiến lược từ trên xuống. Iannone và cộng sự cũng
nghiên cứu các thuật toán học bằng cách sử dụng toán tử làm mịn nhưng trên một
logic mô tả giàu ngữ nghĩa hơn, logic mô tả ALC. Ý tưởng chính của các thuật toán
này là tìm và loại bỏ những phần của khái niệm dẫn đến lỗi về phân loại [32]. Cả hai
công trình trên đều nghiên cứu việc học khái niệm trong logic mô tả với Ngữ cảnh (1).
Fanizzi cùng các cộng sự nghiên cứu toán tử làm mịn trên xuống trong logic mô
tả ALN [17] và xây dựng hệ thống DL-Foil [15] cho việc học khái niệm trong logic
mô tả hỗ trợ ngôn ngữ OWL. Các tác giả đã sử dụng kỹ thuật học bán giám sát với
dữ liệu không gán nhãn. Các thành phần chính của hệ thống sử dụng tập các toán tử
làm mịn tương tự như trong công trình của Badea và Nienhuys-Cheng [4].
Lehmann và Hitzler đề xuất thuật toán học DL-Learner theo phương pháp lập
trình đệ quy và có khai thác thêm các kỹ thuật về lập trình di truyền [35], [36]. Các
công trình này nghiên cứu việc học khái niệm trong logic mô tả với Ngữ cảnh (2).
Ngoài việc sử dụng các toán tử làm mịn, các hàm tính điểm và chiến lược tìm kiếm
cũng đóng vai trò quan trọng đối với các thuật toán đã được đề xuất trong những
công trình nêu trên [4], [32], [35], [15], [36].
Hướng tiếp cận thứ ba sử dụng mô phỏng hai chiều trong logic mô tả [12], [44], [14].
Nguyen và Szalas đã áp dụng mô phỏng hai chiều vào trong logic mô tả để mô hình
hóa tính không phân biệt được của các đối tượng [44]. Dựa trên tự mô phỏng hai chiều
3
lớn nhất, các tác giả đã đề xuất một phương pháp tổng quát để học khái niệm cho
các hệ thống thông tin trong logic mô tả. Đây là công trình tiên phong trong việc sử
dụng mô phỏng hai chiều cho việc giải quyết bài toán trên. Divroodi [12] và cộng sự
đã nghiên cứu khả năng học trong logic mô tả sử dụng mô phỏng hai chiều. Các công
trình này nghiên cứu bài toán học khái niệm trong logic mô tả với Ngữ cảnh (3).
Ngoại trừ công trình của Nguyen và Szalas [44], Divrooodi [12] sử dụng mô phỏng
hai chiều trong logic mô tả để hướng dẫn việc tìm kiếm khái niệm kết quả. Tất cả các
công trình nghiên cứu còn lại [51], [11], [33], [4], [32], [17], [15], [35], [16], [36] đều sử dụng
toán tử làm mịn như trong lập trình logic đệ quy và/hoặc các chiến lược tìm kiếm dựa
vào các hàm tính điểm mà không sử dụng mô phỏng hai chiều. Các công trình này
chủ yếu tập trung vào vấn đề học khái niệm với Ngữ cảnh (1) và Ngữ cảnh (2) trên
các logic mô tả khá đơn giản ALER, ALN và ALC. Việc nghiên cứu học khái niệm
trong các logic mô tả phức tạp hơn như ALCN , ALCQ, ALCIQ, SHIF, SHIQ,
SHOIN , SHOIQ, SROIQ, . . . với các ngữ cảnh khác nhau chưa được các công
trình trên đề cập đến vì còn gặp nhiều vấn đề khó khăn về mặt kỹ thuật đối với các
toán tử làm mịn. Trong công trình [44], Nguyen và Szalas đã sử dụng mô phỏng hai
chiều cho việc học khái niệm trong các logic mô tả chỉ với Ngữ cảnh (3) nhưng không
đề cập đến các thuộc tính và vai trò dữ liệu trong hệ thống thông tin cũng như các
đặc trưng quan trọng của logic mô tả như: F (tính chất hàm), N (hạn chế số lượng
không định tính). Do không đề cập đến các thuộc tính và vai trò dữ liệu nên lớp các
logic mô tả này không thể biểu diễn những hệ thống thông tin có chứa thuộc tính số
và thuộc tính đa trị cũng như không giải quyết tốt những bài toán trong các logic mô
tả SHIF, SHIN , SHOIN ,. . . Trong công trình [12], Divroodi và các cộng sự chỉ
nghiên cứu về mô phỏng hai chiều và áp dụng để giải quyết bài toán khả năng học
trong logic mô tả với Ngữ cảnh (3). Hai công trình trên không đề cập đến vấn đề học
khái niệm trong logic mô tả với Ngữ cảnh (1) và Ngữ cảnh (2).
Từ các khảo sát như đã nêu ở trên, chúng ta nhận thấy rằng học khái niệm trong
logic mô tả là một vấn đề quan trọng trong việc xây dựng các khái niệm hữu ích phục
vụ cho các hệ thống ngữ nghĩa nói chung và ontolgy nói riêng. Từ đó, nó tác động
lên nhiều ứng dụng trong thực tế có áp dụng Web ngữ nghĩa vào hệ thống. Học khái
niệm trong logic mô tả dựa trên mô phỏng hai chiều là một hướng đi mới chưa từng
được nghiên cứu ngoại trừ công trình của Nguyen và Szalas [44], Divroodi [12] với một
số kết quả ban đầu như đã đề cập ở trên. Trên cơ sở các kết quả của Nguyen, Szalas
và Divroodi [44], [12], luận án tập trung nghiên cứu các phương pháp học khái niệm
trong logic mô tả dựa trên mô phỏng hai chiều với các mục tiêu chính đặt ra là:
4
• Nghiên cứu cú pháp, ngữ nghĩa đối với một lớp lớn các logic mô tả giàu ngữ
nghĩa hơn so với các công trình đã có bằng cách cho phép sử dụng các thuộc
tính như là các phần tử cơ bản của ngôn ngữ, các quan hệ thông qua các vai trò
dữ liệu và đề cập đến đặc trưng F, N . Lớp các logic này bao phủ những logic
mô tả hữu ích như ALC, SHIF, SHIQ, SHOIN , SHOIQ, SROIQ, . . .
• Xây dựng, mở rộng các định nghĩa, định lý, bổ đề về mô phỏng hai chiều trong
lớp các logic mô tả đã đề cập ở trên và sử dụng nó để mô hình hóa tính không
phân biệt được của các đối tượng làm cơ sở cho các thuật toán học khái niệm
trong logic mô tả.
• Phát triển thuật toán học khái niệm dựa trên mô phỏng hai chiều cho các hệ
thống thông tin trong logic mô tả với Ngữ cảnh (3).
• Xây dựng phương pháp làm mịn phân hoạch miền của các diễn dịch trong logic
mô tả dựa trên mô phỏng hai chiều sử dụng các bộ chọn hợp lý và độ đo gia
lượng thông tin.
• Đề xuất các thuật toán học khái niệm cho các cơ sở tri thức trong logic mô tả
với Ngữ cảnh (1) và Ngữ cảnh (2) sử dụng mô phỏng hai chiều.
Nội dung của luận án được trình bày trong bốn chương:
Chương 1 trình bày cú pháp và ngữ nghĩa của logic mô tả, khả năng biểu diễn của
logic mô tả. Xây dựng ngôn ngữ logic mô tả lấy các thuộc tính làm thành phần cơ bản
của ngôn ngữ, cho phép sử dụng vai trò dữ liệu cũng như mở rộng tập các đặc trưng
của logic mô tả so với các công trình đã có. Trên cơ sở đó, chương này đề cập đến cơ
sở tri thức, mô hình của cơ sở tri thức và những vấn đề cơ bản về suy luận trong logic
mô tả.
Chương 2 giới thiệu mô phỏng hai chiều trên lớp các logic mô tả đã đề cập ở
Chương 1. Chúng tôi phát biểu các định nghĩa, định lý, bổ đề mở rộng về mô phỏng
hai chiều và chứng minh tính bất biến đối với mô phỏng hai chiều cho các khái niệm,
bộ tiên đề thuật ngữ, bộ khẳng định và cơ sở tri thức đối với các logic mô tả đang
nghiên cứu. Đặc biệt tính bất biến của khái niệm là nền tảng cho phép mô hình hóa
tính không phân biệt được của các đối tượng thông qua ngôn ngữ con. Đây là cơ sở cho
việc sử dụng ngôn ngữ con trong quá trình xây dựng các thuật toán học khái niệm.
Chương 3 trình bày thuật toán học khái niệm cho các hệ thống thông tin trong
logic mô tả với Ngữ cảnh (3) (thể hiện qua Thuật toán 3.1). Thuật toán này cho phép
học một khái niệm từ một hệ thống thông tin huấn luyện trong logic mô tả với tập
5
các mẫu dương và mẫu âm cho trước. Chúng tôi đã sử dụng bộ chọn cơ bản, bộ chọn
đơn giản và bộ chọn mở rộng kết hợp với độ đo gia lượng thông tin để phân chia các
khối trong quá trình làm mịn các phân hoạch miền của diễn dịch. Ngoài ra, chương
này còn trình bày các kết quả thực nghiệm đối với thuật toán đã đề xuất.
Chương 4 trình bày các thuật toán học khái niệm cho các cơ sở tri thức trong logic
mô tả với Ngữ cảnh (1) và Ngữ cảnh (2), bao gồm thuật toán BBCL, dual-BBCL và
BBCL2. Các thuật toán này sử dụng các mô hình của cơ sở tri thức kết hợp với mô
phỏng hai chiều trong mô hình đó (để mô hình hóa tính không phân biệt được) và
cây quyết định (để phân lớp dữ liệu) cho việc tìm kiếm khái niệm cần học. Chúng tôi
cũng chứng minh tính đúng đắn của thuật toán thông qua các mệnh đề liên quan.
Cuối cùng, phần kết luận trình bày tóm tắt những đóng góp chính của luận án,
hướng phát triển và những vấn đề cần phải giải quyết trong tương lai.
6
Chương 1.
LOGIC MÔ TẢ VÀ CƠ SỞ TRI THỨC
1.1. Tổng quan về logic mô tả
1.1.1. Giới thiệu
Các nghiên cứu về biểu diễn tri thức được đặt ra từ những năm 70 của thế kỷ XX.
Những công trình nghiên cứu đầu tiên trong lĩnh vực này dựa trên hướng tiếp cận
phi logic. Hướng tiếp cận này sử dụng đồ thị làm nền tảng, trong đó tri thức được
biểu diễn bằng những cấu trúc dữ liệu đặc biệt và việc suy luận được thực hiện thông
qua các thủ tục thao tác trên những cấu trúc đó. Năm 1967, Quillian [49] đã sử dụng
mạng ngữ nghĩa (semantic networks) để biểu diễn và suy luận tri thức thông qua các
cấu trúc nhận thức dạng mạng lưới. Sau đó, năm 1974, Minsky giới thiệu hệ thống
khung (frame systems) dựa trên các khái niệm về một “khung” như một giao thức và
khả năng biểu diễn các mối quan hệ giữa các khung [37]. Hướng tiếp cận như trên
không trang bị được ngữ nghĩa dựa trên logic hình thức. Để khắc phục nhược điểm
này, người ta biểu diễn tri thức theo hướng tiếp cận dựa trên logic. Theo đó, ngôn ngữ
biểu diễn thường là một biến thể của logic vị từ bậc nhất và việc tính toán, suy luận
thường dựa vào các hệ quả logic.
Logic mô tả được thiết kế như là một sự mở rộng của mạng ngữ nghĩa và hệ thống
khung với ngữ nghĩa dựa trên logic. Nó là một họ các ngôn ngữ hình thức rất thích
hợp cho việc biểu diễn và suy luận tri thức trong một miền quan tâm cụ thể [2]. Thuật
ngữ “logic mô tả” được sử dụng rộng rãi từ những năm 80 của thế kỷ XX. Ngày nay,
cùng với sự phát triển của các hệ thống biểu diễn tri thức, logic mô tả đã trở thành
một nền tảng quan trọng của Web ngữ nghĩa do nó được sử dụng để cung cấp mô
hình lý thuyết trong việc thiết kế các ontology.
Logic mô tả được xây dựng dựa vào ba thành phần cơ bản gồm tập các cá thể (có
thể hiểu như là các đối tượng), tập các khái niệm nguyên tố (có thể hiểu như là các
lớp, các vị từ một đối) và tập các vai trò nguyên tố (có thể hiểu như là các quan hệ
hai ngôi, các vị từ hai đối). Các logic mô tả khác nhau được đặc trưng bởi tập các tạo
tử khái niệm và tạo tử vai trò mà nó được phép sử dụng để xây dựng các khái niệm
phức, vai trò phức từ các khái niệm nguyên tố và vai trò nguyên tố.
7
Năm 1985, hệ thống biểu diễn tri thức dựa trên logic mô tả đầu tiên KL-one [56], [7]
ra đời đã đánh dấu một sự khởi đầu mạnh mẽ về nghiên cứu logic mô tả. Một
số hệ thống biểu diễn tri thức dựa trên logic mô tả khác tiếp tục xuất hiện sau
đó là LOOM (1987), BACK (1988), CLASSIC (1991). Các hệ thống này có bộ suy
luận sử dụng các thuật toán bao hàm cấu trúc. Gần đây, các hệ thống biểu diễn
tri thức sử dụng các ngôn ngữ logic mô tả có khả năng biểu diễn tốt hơn như
SHOIN , SHOIQ, SROIQ,. . . và các bộ suy luận hiệu quả hơn như FaCT (1998),
RACER (2001), CEL (2005) và KAON 2 (2005) [53]. Các bộ suy luận này sử dụng
các thuật toán tableaux để giải quyết các bái toán suy luận.
1.1.2. Ngôn ngữ logic mô tả ALC
Logic mô tả cơ bản ALC được Schmidt-Schaubß và Smolka giới thiệu lần đầu
tiên vào năm 1991 [55]. Tên ALC đại diện cho “Attribute concept Language with
Complements”. Trên cơ sở logic mô tả cơ bản ALC, người ta mở rộng nó để có các
logic mô tả khác có khả năng biểu diễn tốt hơn bằng cách thêm vào các tạo tử khái
niệm và tạo tử vai trò. Các định nghĩa sau đây trình bày cú pháp và ngữ nghĩa của
logic mô tả cơ bản ALC [34], [36].
Định nghĩa 1.1 (Cú pháp của ALC). Cho ΣC là tập các tên khái niệm và ΣR là tập
các tên vai trò (ΣC ∩ ΣR = ∅). Các phần tử của ΣC được gọi là khái niệm nguyên tố.
Logic mô tả ALC cho phép các khái niệm được định nghĩa một cách đệ quy như sau:
• Nếu A ∈ ΣC thì A là một khái niệm của ALC,
• Nếu C, D là các khái niệm và r ∈ ΣR là một vai trò thì >, ⊥, ¬C, C u D, C t D,
∃r.C và ∀r.C cũng là các khái niệm của ALC.
Các ký hiệu và các tạo tử khái niệm trong Định nghĩa 1.1 có ý nghĩa như sau:
• > gọi là khái niệm đỉnh,
• ⊥ gọi là khái niệm đáy,
• ¬C biểu diễn phủ định của khái niệm C,
• C u D biểu diễn giao của khái niệm C và D,
• C t D biểu diễn hợp của khái niệm C và D,
• ∃r.C biểu diễn hạn chế tồn tại của khái niệm C bởi vai trò r,
• ∀r.C biểu diễn hạn chế phổ quát của khái niệm C bởi vai trò r.
8
Cú pháp của logic mô tả ALC có thể mô tả một cách vắn tắt bằng các luật sau:
C, D −→ A | > | ⊥ | ¬C | C u D | C t D | ∃r.C | ∀r.C
Định nghĩa 1.2 (Ngữ nghĩa của ALC). Một diễn dịch trong logic mô tả ALC là một
bộ I = ∆I , ·I , trong đó ∆I là một tập khác rỗng được gọi là miền của I và ·I là
một ánh xạ, được gọi là hàm diễn dịch của I, cho phép ánh xạ mỗi cá thể a ∈ ΣI
thành một phần tử aI ∈ ∆I , mỗi tên khái niệm A ∈ ΣC thành một tập AI ⊆ ∆I và
mỗi tên vai trò r ∈ ΣR thành một quan hệ hai ngôi rI ⊆ ∆I × ∆I . Diễn dịch của các
khái niệm phức được xác định như sau:
>I = ∆I ,
⊥I = ∅,
(¬C)I = ∆I \ C I ,
(∃r.C)I = {x ∈ ∆I | ∃y ∈ ∆I [rI (x, y) ∧ C I (y)]},
(C u D)I = C I ∩ DI ,
(∀r.C)I = {x ∈ ∆I | ∀y ∈ ∆I [rI (x, y) ⇒ C I (y)]},
(C t D)I = C I ∪ DI .
Hình 1.1 minh họa ngắn gọn cho diễn dịch trong logic mô tả. Mỗi cá thể được diễn
dịch thành một đối tượng, mỗi khái niệm được diễn dịch thành một tập các đối tượng
và mỗi vai trò được diễn dịch thành một quan hệ hai ngôi giữa các đối tượng [21].
Tên khái niệm
Tên vai trò
. . . a ∈ ΣI . . .
. . . A ∈ ΣC . . .
. . . r ∈ ΣR . . .
diễn dịch I
aI
∆I
bộ ký tự
Tên cá thể
AI
rI
Hình 1.1: Diễn dịch của logic mô tả
Ví dụ 1.1. Giả sử chúng ta có các cá thể, khái niệm nguyên tố và vai trò nguyên tố
như sau:
LAN, HAI, HUNG
là các cá thể,
Human
là khái niệm chỉ các đối tượng là con người,
9
F emale
là khái niệm chỉ các đối tượng là giống cái,
Rich
là khái niệm chỉ những đối tượng giàu có,
hasChild
là vai trò chỉ đối tượng này có con là đối tượng kia,
hasDescendant
là vai trò chỉ đối tượng này có con cháu là đối tượng kia,
marriedT o
là vai trò chỉ đối tượng này kết hôn với đối tượng kia.
Với những khái niệm nguyên tố, vai trò nguyên tố đã cho ở trên và các tạo tử phủ
định của khái niệm (¬), giao của các khái niệm (u), hợp của các khái niệm (t), lượng
từ hạn chế tồn tại (∃), lượng từ hạn chế với mọi (∀), chúng ta có thể xây dựng các
khái niệm phức như sau:
Human u F emale
là khái niệm chỉ các đối tượng là người phụ nữ,
Human u ∃hasChild.F emale
là khái niệm chỉ các đối tượng là người có con gái,
Human u ∃marriedT o.Human là khái niệm chỉ những người đã kết hôn,
Human u F emale u Rich
là khái niệm chỉ những người phụ nữ giàu có,
Human u ∀hasChild.F emale
là khái niệm chỉ những người chỉ có toàn con gái
hoặc những người không có con.
Ngoài ra chúng ta có thể dùng khái niệm đỉnh (ký hiệu >), khái niệm đại diện cho
tất cả các đối tượng và khái niệm đáy (ký hiệu ⊥), khái niệm không đại diện cho bất
kỳ đối tượng nào, để xây dựng các khái niệm phức. Chẳng hạn như sau:
Human u ∃hasChild.>
là khái niệm chỉ các đối tượng là người có con,
Human u ∀hasChild.⊥
là khái niệm chỉ những người không có con.
Ví dụ 1.2. Cho tập các cá thể, khái niệm và vai trò như trong Ví dụ 1.1. Xét diễn
dịch I như sau:
LANI
= LAN,
HAII
= HAI,
HUNGI
= HUNG,
∆I
= {LAN, HAI, HUNG},
HumanI
= {LAN, HAI, HUNG},
F emaleI
= {LAN},
RichI
= {HUNG},
hasChildI
= {hLAN, HUNGi, hHAI, HUNGi},
marriedT oI = {hLAN, HAIi, hHAI, LANi},
10
- Xem thêm -