Học khái niệm cho hệ thống thông tin dựa trên logic mô tả: Tóm tắt luận án Tiến sĩ Máy tính

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

HUẾ, NĂM 2015

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:

1. PGS. TSKH. Nguyễn Anh Linh, Trường Đại học Warsaw, Ba Lan

2. TS. Hoàng Thị Lan Giao, Trường Đại học Khoa học, Đại học Huế

Phản biện 1: GS. TSKH. Hoàng Văn Kiếm

Trường Đại học CNTT, ĐHQG TP. Hồ Chí Minh

Phản biện 2: PGS. TS. Đoàn Văn Ban

Viện Công nghệ Thông tin, Viện Hàn lâm KH&CN Việt Nam

Phản biện 3: PGS. TS. Nguyễn Mậu Hân

Trường Đại học Khoa học, Đại học Huế

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 2015

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

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. Bài toán học khái niệm được đặt ra 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 (cid:54)|= 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 (cid:54)|= C(a).

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ả [4], [8]. Cohen và Hirsh nghiên cứu lý thuyết về khả năng học 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” [4]. 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 [8].

Trong hướng tiếp cận thứ hai nghiên cứu học khái niệm trong logic mô tả sử dụng toán tử làm mịn. Badea và Nienhuys-Cheng [1] nghiên cứu học khái niệm trong logic mô tả ALER, Iannone và cộng sự [9] cũng nghiên cứu các thuật toán học trên một logic mô tả giàu ngữ nghĩa hơn, ALC. 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ộng sự [?]iới thiệu hệ thống DL-Foil cho việc học khái niệm trong logic mô tả hỗ trợ ngôn ngữ logic mô tả OWL [7]. 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 [10]. 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).

Hướng tiếp cận thứ ba nghiên cứu học khái niệm trong logic mô tả sử dụng mô phỏng hai chiều [6]. Nguyen và Sza(cid:32)las đã á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 [14]. 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ả. Divroodi [5] 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à Sza(cid:32)las [14], Divroodi [5] 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 đề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. Trong khi đó công trình [14] và [5] 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). 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à ontology 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. Do đó, 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à:

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

Chương 1.

LOGIC MÔ TẢ VÀ CƠ SỞ TRI THỨC

1.1.1. Giới thiệu

1.1. Tổng quan về logic mô tả

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ể, tập

1.1.2. Biểu diễn tri thức

các khái niệm nguyên tố và tập các vai trò nguyên tố.

1.1.3. Ngôn ngữ logic mô tả ALC

Từ các cá thể, các khái niệm và các vai trò, người ta có thể xây dựng một hệ thống để biểu diễn và suy luận tri thức dựa trên logic mô tả gồm: bộ tiên đề vai trò, bộ tiên đề thuật ngữ, bộ khẳng định, hệ thống suy luận, giao diện người dùng.

Đị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ì (cid:62), ⊥, ¬C, C (cid:117) D, (cid:4)

C (cid:116) D, ∃r.C và ∀r.C cũng là các khái niệm của ALC.

Đị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 = (cid:104)∆I, ·I(cid:105), 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 = ∅,

(cid:62)I = ∆I, (∃r.C)I = {x ∈ ∆I | ∃y ∈ ∆I [rI(x, y) ∧ C I(y)]}, (∀r.C)I = {x ∈ ∆I | ∀y ∈ ∆I [rI(x, y) ⇒ C I(y)]},

(¬C)I = ∆I \ C I, (C (cid:117) D)I = C I ∩ DI, (C (cid:116) D)I = C I ∪ DI. (cid:4)

1.1.4. Khả năng biểu diễn

1.1.5. Logic mô tả và các tên gọi

Khả năng biểu diễn tri thức của logic mô tả phụ thuộc vào các tạo tử khái niệm và tạo tử vai trò mà nó được phép sử dụng. Logic sử dụng càng nhiều tạo tử thì càng có khả năng biểu diễn tốt.

• ALC - logic mô tả cơ bản ALC là ngôn ngữ khái niệm thuộc tính có phủ định.

• F - tính chất hàm.

• S - ALC + tính chất bắc cầu của vai trò.

• N - hạn chế số lượng không định tính.

• R - bao hàm vai trò phức.

• H - bao hàm vai trò.

• I - vai trò nghịch đảo.

• Q - hạn chế số lượng có định tính.

• O - định danh.

1.2.1. Ngôn ngữ logic mô tả ALCreg

1.2. Cú pháp và ngữ nghĩa của logic mô tả

Định nghĩa 1.3 (Cú pháp của ALCreg). 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ố và các phần tử của ΣR được gọi là vai trò nguyên tố. Logic mô tả động ALCreg cho phép các khái niệm và các vai trò được định nghĩa một cách đệ quy như sau:

• nếu r ∈ ΣR thì r là một vai trò của ALCreg, • nếu A ∈ ΣC thì A là một khái niệm của ALCreg, • nếu C, D là các khái niệm và R, S là các vai trò thì

– ε, R ◦ S, R (cid:116) S, R∗, C? là các vai trò của ALCreg, – (cid:62), ⊥, ¬C, C (cid:117) D, C (cid:116) D, ∃R.C và ∀R.C là các khái niệm của ALCreg. (cid:4)

(R∗)I = (RI)∗,

Diễn dịch của các vai trò phức trong ALCreg được xác định như sau: (R ◦ S)I = RI ◦ SI, εI = {(cid:104)x, x(cid:105) | x ∈ ∆I},

(R (cid:116) S)I = RI ∪ SI, (C?)I = {(cid:104)x, x(cid:105) | C I(x)}.

1.2.2. Ngôn ngữ logic mô tả LΣ,Φ

Một bộ ký tự logic mô tả là một tập hữu hạn Σ = ΣI ∪ ΣdA ∪ ΣnA ∪ ΣoR ∪ ΣdR, trong đó ΣI là tập các cá thể, ΣdA là tập các thuộc tính rời rạc, ΣnA là tập các thuộc tính số, ΣoR là tập các tên vai trò đối tượng và ΣdR là tập các vai trò dữ liệu. Tất cả các tập ΣI, ΣdA, ΣnA, ΣoR và ΣdR rời nhau từng đôi một.

Xét các đặc trưng của logic mô tả gồm I (vai trò nghịch đảo), O (định danh), F (tính chất hàm), N (hạn chế số lượng không định tính), Q (hạn chế số lượng có định tính), U (vai trò phổ quát), Self (tính phản xạ cục bộ của vai trò). Tập các đặc trưng của logic mô tả Φ là một tập rỗng hoặc tập chứa một số các đặc trưng nêu trên.

Định nghĩa 1.4 (Ngôn ngữ LΣ,Φ). Cho Σ là bộ ký tự logic mô tả, Φ là tập các đặc trưng của logic mô tả và L đại diện cho ALCreg. Ngôn ngữ logic mô tả LΣ,Φ cho phép các vai trò đối tượng và các khái niệm được định nghĩa một cách đệ quy như sau:

• nếu r ∈ ΣoR thì r là một vai trò đối tượng của LΣ,Φ, • nếu A ∈ ΣC thì A là một khái niệm của LΣ,Φ, • nếu A ∈ ΣA \ ΣC và d ∈ range(A) thì A = d và A (cid:54)= d là các khái niệm của LΣ,Φ, • nếu A ∈ ΣnA và d ∈ range(A) thì A ≤ d, A < d, A ≥ d và A > d là các khái

niệm của LΣ,Φ,

• nếu R và S là các vai trò đối tượng của LΣ,Φ, C và D là các khái niệm của LΣ,Φ,

r ∈ ΣoR, σ ∈ ΣdR, a ∈ ΣI và n là một số tự nhiên thì

– ε, R ◦ S , R (cid:116) S, R∗ và C? là các vai trò đối tượng của LΣ,Φ,

(cid:4)

– (cid:62), ⊥, ¬C, C (cid:117) D, C (cid:116) D, ∃R.C và ∀R.C là các khái niệm của LΣ,Φ, – nếu d ∈ range(σ) thì ∃σ.{d} là một khái niệm của LΣ,Φ, – nếu I ∈ Φ thì R− là một vai trò đối tượng của LΣ,Φ, – nếu O ∈ Φ thì {a} là một khái niệm của LΣ,Φ, – nếu F ∈ Φ thì ≤ 1 r là một khái niệm của LΣ,Φ, – nếu {F, I} ⊆ Φ thì ≤ 1 r− là một khái niệm của LΣ,Φ, – nếu N ∈ Φ thì ≥ n r và ≤ n r là các khái niệm của LΣ,Φ, – nếu {N , I} ⊆ Φ thì ≥ n r− và ≤ n r− là các khái niệm của LΣ,Φ, – nếu Q ∈ Φ thì ≥ n r.C và ≤ n r.C là các khái niệm của LΣ,Φ, – nếu {Q, I} ⊆ Φ thì ≥ n r−.C và ≤ n r−.C là các khái niệm của LΣ,Φ, – nếu U ∈ Φ thì U là một vai trò đối tượng của LΣ,Φ, – nếu Self ∈ Φ thì ∃r.Self là một khái niệm của LΣ,Φ.

(C?)I = {(cid:104)x, x(cid:105) | C I(x)} εI = {(cid:104)x, x(cid:105) | x ∈ ∆I}

(R∗)I = (RI)∗ (R−)I = (RI)−1 (C (cid:116) D)I = C I ∪ DI

U I = ∆I × ∆I ⊥I = ∅

(R ◦ S)I = RI ◦ SI (R (cid:116) S)I = RI ∪ SI (C (cid:117) D)I = C I ∩ DI (A ≤ d)I = {x ∈ ∆I | AI(x) xác định và AI(x) ≤ d} (A ≥ d)I = {x ∈ ∆I | AI(x) xác định và AI(x) ≥ d} (A = d)I = {x ∈ ∆I | AI(x) = d} (A < d)I = ((A ≤ d) (cid:117) (A (cid:54)= d))I (∀R.C)I = {x ∈ ∆I | ∀y [RI(x, y) ⇒ C I(y)]} (∃R.C)I = {x ∈ ∆I | ∃y [RI(x, y) ∧ C I(y)]} (≥ n R.C)I = {x ∈ ∆I | #{y | RI(x, y) ∧ C I(y)} ≥ n} (≤ n R.C)I = {x ∈ ∆I | #{y | RI(x, y) ∧ C I(y)} ≤ n}

{a}I = {aI} (cid:62)I = ∆I (¬C)I = ∆I \ C I (A (cid:54)= d)I = (¬(A = d))I (A > d)I = ((A ≥ d) (cid:117) (A (cid:54)= d))I (∃r.Self)I = {x ∈ ∆I | rI(x, x)} (∃σ.{d})I = {x ∈ ∆I | σI(x, d)} (≥ n R)I = (≥ n R.(cid:62))I (≤ n R)I = (≤ n R.(cid:62))I

Hình 1.1: Diễn dịch của các vai trò phức và khái niệm phức

Định nghĩa 1.5 (Ngữ nghĩa của LΣ,Φ). Một diễn dịch trong LΣ,Φ là một bộ I = (cid:104)∆I, ·I(cid:105), 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, mỗi thuộc tính A ∈ ΣA \ ΣC thành một hàm từng phần AI : ∆I → range(A), mỗi tên vai trò đối tượng r ∈ ΣoR thành một quan hệ hai ngôi rI ⊆ ∆I × ∆I và mỗi vai trò dữ liệu σ ∈ ΣdR thành một quan hệ hai ngôi σI ⊆ ∆I × range(σ). Hàm diễn dịch ·I được mở rộng cho các vai trò đối tượng phức và các khái niệm phức như trong Hình 1.1, trong đó #Γ ký hiệu cho lực lượng của tập Γ. (cid:4)

1.3.1. Dạng chuẩn phủ định của khái niệm

1.3. Các dạng chuẩn

Khái niệm C được gọi là ở dạng chuẩn phủ định nếu toán tử phủ định chỉ xuất

hiện trước các tên khái niệm có trong C.

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ò

Dạng chuẩn lưu trữ khái niệm được xây dựng dựa trên dạng chuẩn phủ định và tập hợp. Khái niệm ở dạng này được biểu diễn dưới dạng tập hợp của các khái niệm con.

Vai trò đối tượng R được gọi ở dạng chuẩn nghịch đảo nếu tạo tử nghịch đảo chỉ

áp dụng cho các tên vai trò đối tượng có trong R (không xét đến vai trò U ).

oR = ΣoR ∪ {r− | r ∈ ΣoR}. Một vai trò đối tượng cơ bản là một phần tử oR (tương ứng, ΣoR) nếu ngôn ngữ được xem xét cho phép vai trò nghịch đảo

Đặt Σ±

thuộc Σ± (tương ứng, không cho phép vai trò nghịch đảo).

1.4.1. Bộ tiên đề vai trò

1.4. Cơ sở tri thức trong logic mô tả

1.4.2. Bộ tiên đề thuật ngữ

Định nghĩa 1.6 (Tiên đề vai trò). Một tiên đề bao hàm vai trò trong ngôn ngữ LΣ,Φ là một biểu thức có dạng ε (cid:118) r hoặc R1 ◦ R2 ◦ · · · ◦ Rk (cid:118) r, trong đó k ≥ 1, r ∈ ΣoR và R1, R2, . . . , Rk là các vai trò đối tượng cơ bản của LΣ,Φ khác với vai trò phổ quát U . Một khẳng định vai trò trong ngôn ngữ LΣ,Φ là một biểu thức có dạng Ref(r), Irr(r), Sym(r), Tra(r) hoặc Dis(R, S), trong đó r ∈ ΣoR và R, S là các vai trò đối tượng của LΣ,Φ khác với vai trò phổ quát U . Một tiên đề vai trò trong ngôn ngữ LΣ,Φ là một tiên đề bao hàm vai trò hoặc một khẳng định vai trò trong LΣ,Φ. (cid:4) Định nghĩa 1.7 (Bộ tiên đề vai trò). Bộ tiên đề vai trò (RBox) trong ngôn ngữ LΣ,Φ là một tập hữu hạn các tiên đề vai trò trong LΣ,Φ. (cid:4)

1.4.3. Bộ khẳng định cá thể

Định nghĩa 1.8 (Tiên đề thuật ngữ). Một tiên đề bao hàm khái niệm tổng quát trong ngôn ngữ LΣ,Φ là một biểu thức có dạng C (cid:118) D, trong đó C và D là các khái niệm của LΣ,Φ. Một tiên đề tương đương khái niệm trong ngôn ngữ LΣ,Φ là một biểu thức có dạng C ≡ D, trong đó C và D là các khái niệm của LΣ,Φ. Một tiên đề thuật ngữ trong ngôn ngữ LΣ,Φ là một tiên đề bao hàm khái niệm tổng quát hoặc một tiên đề tương đương khái niệm trong LΣ,Φ. (cid:4) Định nghĩa 1.9 (Bộ tiên đề thuật ngữ). Bộ tiên đề thuật ngữ (TBox) trong ngôn ngữ LΣ,Φ là một tập hữu hạn các tiên đề thuật ngữ trong LΣ,Φ. (cid:4)

1.4.4. Cơ sở tri thức và mô hình của cơ sở tri thức

Định nghĩa 1.10 (Khẳng định cá thể). Một khẳng định cá thể trong ngôn ngữ LΣ,Φ là một biểu thức có dạng C(a), R(a, b), ¬R(a, b), a = b, a (cid:54)= b, trong đó C là một khái niệm và R là một vai trò đối tượng của LΣ,Φ. (cid:4) Định nghĩa 1.11 (Bộ khẳng định cá thể). Bộ khẳng định cá thể (ABox) trong ngôn ngữ LΣ,Φ là một tập hữu hạn các khẳng định cá thể trong LΣ,Φ. (cid:4)

Định nghĩa 1.12 (Cơ sở tri thức). Một cơ sở tri thức trong ngôn ngữ LΣ,Φ là một bộ ba KB = (cid:104)R, T , A(cid:105), trong đó R là một RBox, T là một TBox và A là một ABox trong LΣ,Φ. (cid:4)

Định nghĩa 1.13 (Mô hình). Một diễn dịch I là một mô hình của RBox R (tương ứng, TBox T , ABox A), ký hiệu là I |= R (tương ứng, I |= T , I |= A), nếu I thỏa mãn tất cả các tiên đề vai trò trong R (tương ứng, tiên đề thuật ngữ trong T , khẳng định cá thể trong A). Một diễn dịch I là một mô hình của cơ sở tri thức KB = (cid:104)R, T , A(cid:105), ký hiệu là I |= KB, nếu nó là mô hình của cả R, T và A. (cid:4)

Ví dụ 1.1. Ví dụ sau đây là các cơ sở tri thức đề cập về các ấn phẩm khoa học:

ΣI = {P1, P2, P3, P4, P5, P6},

ΣdA = ΣC,

ΣnA = {Year },

Φ = {I, O, N , Q}, ΣC = {Pub, Awarded , UsefulPub, Ad}, ΣdR = ∅, ΣoR = {cites, cited_by},

R = {cites − (cid:118) cited_by, cited_by − (cid:118) cites, Irr(cites)}, T = {(cid:62) (cid:118) Pub, UsefulPub ≡ ∃cited_by.(cid:62)}, A(cid:48) 0 = {Awarded (P1), ¬Awarded (P2), ¬Awarded (P3), Awarded (P4),

A0 = A(cid:48)

¬Awarded (P5), Awarded (P6), Year (P1) = 2010, Year (P2) = 2009, Year (P3) = 2008, Year (P4) = 2007, Year (P5) = 2006, Year (P6) = 2006, cites(P1, P2), cites(P1, P3), cites(P1, P4), cites(P1, P6), cites(P2, P3), cites(P2, P4), cites(P2, P5), cites(P3, P4), cites(P3, P5), cites(P3, P6), cites(P4, P5), cites(P4, P6)}, 0 ∪ {(¬∃cited_by.(cid:62))(P1), (∀cited_by.{P2, P3, P4})(P5)}.

0 = (cid:104)R, T , A(cid:48)

0(cid:105) và KB0 = (cid:104)R, T , A0(cid:105) là các cơ sở tri thức trong LΣ,Φ. 0 hoặc KB0

Lúc đó KB(cid:48)

Tiên đề (cid:62) (cid:118) Pub để chỉ ra rằng miền của bất kỳ mô hình nào của KB(cid:48) đều chỉ gồm các ấn phẩm khoa học.

1.5. Suy luận trong logic mô tả

Có nhiều bài toán suy luận được đặt ra trong các hệ thống biểu diễn tri thức dựa trên logic mô tả. Để giải quyết các bài toán suy luận, người ta sử dụng hai thuật đó là: thuật toán bao hàm theo cấu trúc và thuật toán tableaux. Thuật toán bao hàm theo tỏ ra hiệu quả đối với các ngôn ngữ logic mô tả đơn giản như FL0, FL⊥, ALN , còn thuật toán tableaux giải quyết các bài toán suy luận với lớp ngôn ngữ logic mô tả rộng hơn như ALC [11], ALCI [12], ALCIQ [12], SHIQ [13],. . .

Tiểu kết Chương 1

Trong chương này, luận án đã giới thiệu khái quát về logic mô tả, khả năng biểu diễn tri thức của các logic mô tả. Thông qua cú pháp và ngữ nghĩa của logic mô tả, luận án đã trình bày về cơ sở tri thức, mô hình của cơ sở tri thức trong logic mô tả và những vấn đề cơ bản về suy luận trong logic mô tả. Ngoài việc trình bày ngôn ngữ logic mô tả một cách tổng quát dựa trên logic ALCreg với các đặc trưng mở rộng I (vai trò nghịch đảo), O (định danh), F (tính chất hàm), N (hạn chế số lượng không định tính), Q (hạn chế số lượng định tính), U (vai trò phổ quát), Self (tính phản xạ cục bộ của vai trò), luận án còn xem xét các thuộc tính như là các thành phần cơ bản của ngôn ngữ, bao gồm thuộc tính rời rạc và thuộc tính số. Cách tiếp cận này phù hợp đối với các hệ thống thông tin dựa trên logic mô tả thường có trong thực tế.

Chương 2.

MÔ PHỎNG HAI CHIỀU TRONG LOGIC MÔ TẢ

VÀ TÍNH BẤT BIẾN

2.1. Giới thiệu

Mô phỏng hai chiều được nghiên cứu trong logic hình thái (modal logic) [2], [17]. Mô phỏng hai chiều là một quan hệ hai ngôi cho phép đặc tả tính tương tự giữa hai trạng thái cũng như tính tương tự giữa các mô hình Kripke. Divroodi và Nguyen đã nghiên cứu mô phỏng hai chiều trong một số logic mô tả cụ thể [6].

2.2.1. Khái niệm

C, B ∈ Σ†

I, A ∈ Σ†

2.2. Mô phỏng hai chiều

dR, d ∈ range(σ), x, y ∈ ∆I, x(cid:48), y(cid:48) ∈ ∆I(cid:48)

(2.1)

)

(2.2)

(2.3)

(x(cid:48))] (x(cid:48)) hoặc cả hai đều không xác định]

(2.4)

| [Z(y, y(cid:48)) ∧ rI(cid:48)

(2.5)

(x(cid:48), y(cid:48))] (x(cid:48), y(cid:48))] ⇒ ∃y ∈ ∆I | [Z(y, y(cid:48)) ∧ rI(x, y)]

(2.6) Định nghĩa 2.1 (Mô phỏng hai chiều). Cho Σ và Σ† là các bộ ký tự logic mô tả sao cho Σ† ⊆ Σ, Φ và Φ† là tập các đặc trưng của logic mô tả sao cho Φ† ⊆ Φ, I và I (cid:48) là các diễn dịch trong LΣ,Φ. Một LΣ†,Φ†-mô phỏng hai chiều giữa I và I (cid:48) là một quan hệ hai ngôi Z ⊆ ∆I × ∆I(cid:48) A \ Σ† thỏa các điều kiện sau với mọi a ∈ Σ† C, oR, σ ∈ Σ† r ∈ Σ† Z(aI, aI(cid:48) Z(x, x(cid:48)) ⇒ [AI(x) ⇔ AI(cid:48) Z(x, x(cid:48)) ⇒ [BI(x) = BI(cid:48) [Z(x, x(cid:48)) ∧ rI(x, y)] ⇒ ∃y(cid:48) ∈ ∆I(cid:48) [Z(x, x(cid:48)) ∧ rI(cid:48) Z(x, x(cid:48)) ⇒ [σI(x, d) ⇔ σI(cid:48)

(x(cid:48), d)],

nếu I ∈ Φ† thì

(2.7)

| [Z(y, y(cid:48)) ∧ rI(cid:48)

(2.8)

[Z(x, x(cid:48)) ∧ rI(y, x)] ⇒ ∃y(cid:48) ∈ ∆I(cid:48) [Z(x, x(cid:48)) ∧ rI(cid:48)

(y(cid:48), x(cid:48))] (y(cid:48), x(cid:48))] ⇒ ∃y ∈ ∆I | [Z(y, y(cid:48)) ∧ rI(y, x)],

nếu O ∈ Φ† thì

(2.9)

Z(x, x(cid:48)) ⇒ [x = aI ⇔ x(cid:48) = aI(cid:48)

],

nếu N ∈ Φ† thì

(2.10)

Z(x, x(cid:48)) ⇒ #{y ∈ ∆I | rI(x, y)} = #{y(cid:48) ∈ ∆I(cid:48)

| rI(cid:48)

(x(cid:48), y(cid:48))},

nếu {N , I} ⊆ Φ† thì

(2.11)

Z(x, x(cid:48)) ⇒ #{y ∈ ∆I | rI(y, x)} = #{y(cid:48) ∈ ∆I(cid:48)

| rI(cid:48)

(y(cid:48), x(cid:48))},

nếu F ∈ Φ† thì

(2.12)

Z(x, x(cid:48)) ⇒ [#{y ∈ ∆I | rI(x, y)} ≤ 1 ⇔ #{y(cid:48) ∈ ∆I(cid:48) | rI(cid:48)(x(cid:48), y(cid:48))} ≤ 1],

nếu {F, I} ⊆ Φ† thì

(2.13)

Z(x, x(cid:48)) ⇒ [#{y ∈ ∆I | rI(y, x)} ≤ 1 ⇔ #{y(cid:48) ∈ ∆I(cid:48) | rI(cid:48)(y(cid:48), x(cid:48))} ≤ 1],

oR, tồn tại một song ánh

nếu Q ∈ Φ† thì

(2.14) nếu Z(x, x(cid:48)) thỏa mãn thì với mọi r ∈ Σ† h : {y ∈ ∆I | rI(x, y)} → {y(cid:48) ∈ ∆I(cid:48) | rI(cid:48)(x(cid:48), y(cid:48))} sao cho h ⊆ Z,

oR, tồn tại một song ánh

nếu {Q, I} ⊆ Φ† thì

(2.15) nếu Z(x, x(cid:48)) thỏa mãn thì với mọi r ∈ Σ† h : {y ∈ ∆I | rI(y, x)} → {y(cid:48) ∈ ∆I(cid:48) | rI(cid:48)(y(cid:48), x(cid:48))} sao cho h ⊆ Z,

nếu U ∈ Φ† thì

(2.16)

(2.17)

∀x ∈ ∆I, ∃x(cid:48) ∈ ∆I(cid:48) ∀x(cid:48) ∈ ∆I(cid:48)

, Z(x, x(cid:48)) , ∃x ∈ ∆I, Z(x, x(cid:48)),

nếu Self ∈ Φ† thì

(2.18)

Z(x, x(cid:48)) ⇒ [rI(x, x) ⇔ rI(cid:48)

(x(cid:48), x(cid:48))],

(cid:4)

trong đó #Γ ký hiệu cho lực lượng của tập hợp Γ.

Bổ đề 2.1.

1. Quan hệ {(cid:104)x, x(cid:105) | x ∈ ∆I} là một LΣ†,Φ†-mô phỏng hai chiều giữa I và I. 2. Nếu Z là một LΣ†,Φ†-mô phỏng hai chiều giữa I và I (cid:48) thì Z −1 cũng là một

LΣ†,Φ†-mô phỏng hai chiều giữa I (cid:48) và I.

3. Nếu Z1 là một LΣ†,Φ†-mô phỏng hai chiều giữa I0 và I1, Z2 là một LΣ†,Φ†-mô phỏng hai chiều giữa I1 và I2 thì Z1 ◦ Z2 là một LΣ†,Φ†-mô phỏng hai chiều giữa I0 và I2.

(cid:4)

4. Nếu Z là một tập các LΣ†,Φ†-mô phỏng hai chiều giữa I và I (cid:48) thì (cid:83) Z là một

LΣ†,Φ†-mô phỏng hai chiều giữa I và I (cid:48).

2.2.2. Quan hệ tương tự hai chiều và quan hệ tương đương

(cid:4)

Định nghĩa 2.2. Cho I và I (cid:48) là các diễn dịch trong ngôn ngữ LΣ,Φ. Ta nói rằng I LΣ†,Φ†-tương tự hai chiều với I (cid:48) nếu tồn tại một LΣ†,Φ†-mô phỏng hai chiều giữa I và I (cid:48).

(cid:4)

Định nghĩa 2.3. Cho I và I (cid:48) là các diễn dịch trong ngôn ngữ LΣ,Φ, x ∈ ∆I và x(cid:48) ∈ ∆I(cid:48) . Ta nói rằng x LΣ†,Φ†-tương tự hai chiều với x(cid:48) nếu tồn tại một LΣ†,Φ†-mô phỏng hai chiều giữa I và I (cid:48) sao cho Z(x, x(cid:48)) thỏa mãn.

. Định nghĩa 2.4. Cho I và I (cid:48) là các diễn dịch trong ngôn ngữ LΣ,Φ, x ∈ ∆I và x(cid:48) ∈ ∆I(cid:48) . Ta nói rằng x LΣ†,Φ†-tương đương với x(cid:48) nếu với mọi khái niệm C của LΣ†,Φ†, x ∈ C I khi và chỉ khi x(cid:48) ∈ C I(cid:48)

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. Tính bất biến đối với mô phỏng hai chiều

(2.19)

(x(cid:48))]

(2.20)

| [Z(y, y(cid:48)) ∧ RI(cid:48)

(2.21) Bổ đề 2.2. Cho I và I (cid:48) là các diễn dịch trong ngôn ngữ LΣ,Φ, Z là một LΣ†,Φ†-mô phỏng hai chiều giữa I và I (cid:48). Lúc đó, với mọi khái niệm C của LΣ†,Φ†, mọi vai trò đối tượng R của LΣ†,Φ†, mọi đối tượng x, y ∈ ∆I, x(cid:48), y(cid:48) ∈ ∆I(cid:48) và mọi cá thể a ∈ Σ† I, các điều kiện sau sẽ được thỏa mãn: Z(x, x(cid:48)) ⇒ [C I(x) ⇔ C I(cid:48) [Z(x, x(cid:48)) ∧ RI(x, y)] ⇒ ∃y(cid:48) ∈ ∆I(cid:48) [Z(x, x(cid:48)) ∧ RI(cid:48)

(x(cid:48), y(cid:48))] (x(cid:48), y(cid:48))] ⇒ ∃y ∈ ∆I | [Z(y, y(cid:48)) ∧ RI(x, y)],

(cid:4)

nếu O ∈ Φ† thì:

(2.22)

Z(x, x(cid:48)) ⇒ [RI(x, aI) ⇔ RI(cid:48)

(x(cid:48), aI(cid:48)

)].

2.3.2. Tính bất biến của khái niệm

(cid:4)

Định nghĩa 2.5 (Khái niệm bất biến). Một khái niệm C được gọi là bất biến đối với LΣ†,Φ†-mô phỏng hai chiều nếu Z(x, x(cid:48)) thỏa mãn thì x ∈ C I khi và chỉ khi x(cid:48) ∈ C I(cid:48) với mọi diễn dịch I, I (cid:48) trong ngôn ngữ LΣ,Φ và với mọi LΣ†,Φ†-mô phỏng hai chiều Z giữa I và I (cid:48), trong đó Σ† ⊆ Σ, Φ† ⊆ Φ.

Định lý 2.1. Tất cả các khái niệm của LΣ†,Φ† đều bất biến đối với LΣ†,Φ†-mô phỏng hai chiều. (cid:4)

2.3.3. Tính bất biến của cơ sở tri thức

(cid:4)

Định lý này 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 LΣ†,Φ†. Tính không phân biệt của các đối tượng là một trong những đặc trưng cơ bản trong quá trình phân lớp dữ liệu.

(cid:4)

Định nghĩa 2.6. Một TBox T (tương ứng, ABox A) trong LΣ†,Φ† được gọi là bất biến đối với LΣ†,Φ†-mô phỏng hai chiều nếu với mọi diễn dịch I và I (cid:48) trong LΣ,Φ tồn tại một LΣ†,Φ†-mô phỏng hai chiều giữa I và I (cid:48) sao cho I là mô hình của T (tương ứng, A) khi và chỉ khi I (cid:48) là mô hình của T (tương ứng, A).

Hệ quả 2.1. Nếu U ∈ Φ† thì tất cả các TBox trong LΣ†,Φ† đều bất biến đối với LΣ†,Φ†-mô phỏng hai chiều.

i (xi−1, xi) thỏa mãn với mọi 1 ≤ i ≤ k [6].

Một diễn dịch I trong LΣ,Φ được gọi là kết nối đối tượng được đối với LΣ†,Φ† nếu với mọi đối tượng x ∈ ∆I tồn tại cá thể a ∈ Σ† I, các đối tượng x0, x1, . . . , xk ∈ ∆I và các vai trò đối tượng cơ bản R1, R2, . . . , Rk của LΣ†,Φ† với k ≥ 0 sao cho x0 = aI, xk = x và RI

Định lý 2.2. Cho T là một TBox trong LΣ†,Φ†, I và I (cid:48) là các diễn dịch trong LΣ,Φ thỏa điều kiện kết nối đối tượng được đối với LΣ†,Φ† sao cho tồn tại một LΣ†,Φ†-mô phỏng hai chiều giữa I và I (cid:48). Lúc đó I là mô hình của T khi và chỉ khi I (cid:48) là mô hình của T . (cid:4)

(cid:4)

Định lý 2.3. Cho A là một ABox trong LΣ†,Φ†. Nếu O ∈ Φ† hoặc A chỉ chứa các khẳng định dạng C(a) thì A bất biến đối với LΣ†,Φ†-mô phỏng hai chiều.

Hệ quả 2.2. Cho cơ sở tri thức KB = (cid:104)R, T , A(cid:105) trong LΣ†,Φ† sao cho R = ∅ và giả thiết O ∈ Φ† hoặc A chỉ chứa các khẳng định có dạng C(a), I và I (cid:48) là các diễn dịch kết nối đối tượng được trong LΣ†,Φ† sao cho tồn tại một LΣ†,Φ†-mô phỏng hai chiều giữa I và I (cid:48). Lúc đó I là mô hình của KB khi và chỉ khi I (cid:48) là mô hình của KB. (cid:4)

2.4. Tính chất Hennessy-Milner đối với mô phỏng hai chiều

oR thì:

(cid:4)

Định nghĩa 2.7. Một diễn dịch I trong LΣ,Φ được gọi là phân nhánh hữu hạn (hay hữu hạn ảnh) đối với LΣ†,Φ† nếu với mọi x ∈ ∆I và với mọi vai trò r ∈ Σ†

• tập {y ∈ ∆I | rI(x, y)} là hữu hạn, • nếu I ∈ Φ† thì tập {y ∈ ∆I | rI(y, x)} là hữu hạn.

I, aI LΣ†,Φ†-tương đương với aI(cid:48)

I (cid:54)= ∅. Lúc đó, x ∈ ∆I LΣ†,Φ†-tương đương với x(cid:48) ∈ ∆I(cid:48)

I, aI LΣ†,Φ†-tương đương với aI(cid:48)

(cid:4)

Định lý 2.4 (Tính chất Hennessy-Milner). Cho Σ và Σ† là các bộ ký tự logic mô tả sao cho Σ† ⊆ Σ, Φ và Φ† là tập các đặc trưng của logic mô tả sao cho Φ† ⊆ Φ, I và I (cid:48) là các diễn dịch trong LΣ,Φ thỏa mãn điều kiện phân nhánh hữu hạn đối với LΣ†,Φ†, sao cho với mọi a ∈ Σ† . Giả thiết rằng U (cid:54)∈ Φ† hoặc Σ† khi và chỉ khi tồn tại một LΣ†,Φ†-mô phỏng hai chiều Z giữa I và I (cid:48) sao cho Z(x, x(cid:48)) thỏa mãn. (cid:4) Hệ quả 2.3. Cho Σ và Σ† là các bộ ký tự logic mô tả sao cho Σ† ⊆ Σ, Φ và Φ† là tập các đặc trưng của logic mô tả sao cho Φ† ⊆ Φ, I và I (cid:48) là các diễn dịch trong LΣ,Φ thỏa điều kiện phân nhánh hữu hạn đối với LΣ†,Φ†. Giả thiết rằng Σ† I (cid:54)= ∅ và với . Lúc đó, quan hệ {(cid:104)x, x(cid:48)(cid:105) ∈ ∆I × ∆I(cid:48) | x mọi a ∈ Σ† LΣ†,Φ†-tương đương với x(cid:48)} là một LΣ†,Φ†-mô phỏng hai chiều giữa I và I (cid:48).

2.5. Tự mô phỏng hai chiều

Định nghĩa 2.8 (Tự mô phỏng hai chiều). Cho I là một diễn dịch trong LΣ,Φ. Một LΣ†,Φ†-tự mô phỏng hai chiều của I là một LΣ†,Φ†-mô phỏng hai chiều giữa I và chính nó. Một LΣ†,Φ†-tự mô phỏng hai chiều Z của I được gọi là lớn nhất nếu với mọi LΣ†,Φ†-tự mô phỏng hai chiều Z (cid:48) của I thì Z (cid:48) ⊆ Z. (cid:4)

Cho I là một diễn dịch trong LΣ,Φ, chúng ta ký hiệu LΣ†,Φ†-tự mô phỏng hai chiều lớn nhất của I là ∼Σ†,Φ†,I, và ký hiệu quan hệ hai ngôi ≡Σ†,Φ†,I trên ∆I là quan hệ thỏa mãn tính chất x ≡Σ†,Φ†,I x(cid:48) khi và chỉ khi x LΣ†,Φ†-tương đương với x(cid:48). Định lý 2.5. Cho Σ và Σ† là các bộ ký tự của logic mô tả sao cho Σ† ⊆ Σ, Φ và Φ† là tập các đặc trưng của logic mô tả sao cho Φ† ⊆ Φ, I là một diễn dịch trong LΣ,Φ. Lúc đó:

1. LΣ†,Φ†-tự mô phỏng hai chiều lớn nhất của I tồn tại và nó là một quan hệ tương đương,

2. nếu I là một phân nhánh hữu hạn đối với LΣ†,Φ† thì quan hệ ≡Σ†,Φ†,I là một LΣ†,Φ†-tự mô phỏng hai chiều lớn nhất của I (nghĩa là, quan hệ ≡Σ†,Φ†,I và ∼Σ†,Φ†,I trùng khớp nhau). (cid:4)

Chúng ta nói rằng tập Y bị phân chia bởi tập X nếu Y \ X (cid:54)= ∅ và Y ∩ X (cid:54)= ∅. Như vậy, tập Y không bị phân chia bởi tập X nếu hoặc Y ⊆ X hoặc Y ∩X = ∅. Phân hoạch Y = {Y1, Y2, . . . , Yn} được gọi là nhất quán với tập X nếu với mọi 1 ≤ i ≤ n, Yi không bị phân chia bởi X.

Định lý 2.6. Cho Σ và Σ† là các bộ ký tự của logic mô tả sao cho Σ† ⊆ Σ, Φ và Φ† là tập các đặc trưng của logic mô tả sao cho Φ† ⊆ Φ, I là một diễn dịch hữu hạn trong LΣ,Φ và X ⊆ ∆I. Gọi Y là phân hoạch của ∆I thông qua quan hệ ∼Σ†,Φ†,I. Lúc đó:

1. nếu tồn tại khái niệm C của LΣ†,Φ† sao cho C I = X thì phân hoạch Y nhất quán

với tập X,

(cid:4)

2. nếu phân hoạch Y nhất quán với tập X thì tồn tại khái niệm C của LΣ†,Φ† sao cho C I = X.

Tiểu kết Chương 2

Thông qua ngôn ngữ LΣ,Φ và ngôn ngữ con LΣ†,Φ†, chương này đã trình bày mô phỏng hai chiều và tính bất biến đối với mô phỏng hai chiều trên một lớp các logic mô tả như đã đề cập trong Chương 1. Các khái niệm, định nghĩa và các định lý, bổ đề cũng như các hệ quả được phát triển dựa trên các kết quả của các công trình [6], [14] với lớp các logic mô tả lớn hơn. Chúng tôi cũng trình bày các chứng minh cho những định lý, bổ đề, hệ quả đã nêu ra trong chương này. Tính bất biến, đặc biệt là tính bất biến của khái niệm là một trong những 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. Tính không phân biệt của các đối tượng là một trong những đặc trưng cơ bản trong quá trình xây dựng các kỹ thuật phân lớp dữ liệu. Điều này có nghĩa là chúng ta có thể sử dụng ngôn ngữ con cho các bài toán học máy trong logic mô tả bằng cách sử dụng mô phỏng hai chiều.

Chương 3.

HỌC KHÁI NIỆM CHO HỆ THỐNG THÔNG TIN

TRONG LOGIC MÔ TẢ

3.1.1. Hệ thống thông tin truyền thống

3.1. Hệ thống thông tin

Một cách hình thức, hệ thống thông tin được định nghĩa như sau [15]:

Định nghĩa 3.1. Hệ thống thông tin là một bộ IS = (cid:104)U, A, V, ρ(cid:105), trong đó:

• U là một tập hữu hạn, khác rỗng, được gọi là tập vũ trụ các đối tượng,

• A là một tập hữu hạn, khác rỗng, được gọi là tập thuộc tính, • V = (cid:83)

Va, trong đó Va là tập khác rỗng các giá trị của thuộc tính a ∈ A và Va

a∈A

được gọi là miền giá trị của a,

• ρ : U×A → V là một hàm thông tin, sao cho ρ(u, a) ∈ Va với mọi u ∈ U và a ∈ A.(cid:4)

Hạn chế của hệ thống thông tin truyền thống là không thể hiện được mối quan hệ

3.1.2. Hệ thống thông tin dựa trên logic mô tả

giữa các đối tượng.

Định nghĩa 3.2 (Cơ sở tri thức không vòng). Cơ sở tri thức không vòng trong ngôn ngữ LΣ,Φ là một bộ KB = (cid:104)R, T , A(cid:105), trong đó:

• R là một danh sách hữu hạn (ψ1, ψ2, . . . , ψm). Mỗi ψi là một tiên đề vai trò có dạng r ≡ R, trong đó R là một vai trò đối tượng của LΣ,Φ và r ∈ ΣoR là một tên vai trò đối tượng không có mặt trong R, A và ψ1, ψ2, . . . , ψi−1,

• T là một danh sách hữu hạn (ϕ1, ϕ2, . . . , ϕn). Mỗi ϕi là một tiên đề thuật ngữ có dạng A ≡ C, trong đó C là một khái niệm của LΣ,Φ và A ∈ ΣC là một tên khái niệm không có mặt trong C, A và ϕ1, ϕ2, . . . , ϕi−1,

(cid:4)

• A là một tập hữu hạn chứa các khẳng định cá thể.

Cho cơ sở tri thức không vòng KB = (cid:104)R, T , A(cid:105). Một mô hình I của KB trong

LΣ,Φ được gọi là mô hình chuẩn nếu I thỏa mãn các điều kiện sau:

• ∆I = ΣI (nghĩa là, miền của I chứa tất cả các tên cá thể của Σ), • nếu A ∈ ΣC là một khái niệm nguyên thủy trong KB thì AI = {a | A(a) ∈ A}, • nếu B ∈ ΣA \ ΣC thì BI : ∆I → range(B) là một hàm từng phần sao cho

BI(aI) = c nếu (B(a) = c) ∈ A,

• nếu r ∈ ΣoR là một vai trò đối tượng nguyên thủy trong KB thì rI= {(cid:104)a, b(cid:105)| r(a, b) ∈ A}, • nếu σ ∈ ΣdR thì σI = {(cid:104)a, d(cid:105) | σ(a, d) ∈ A},

• nếu r ≡ R là một định nghĩa vai trò đối tượng trong R thì rI = RI, • nếu A ≡ C là một định nghĩa khái niệm trong T thì AI = C I, • nếu A ∈ ΣC mà A không có mặt trong KB thì AI = ∅, • nếu r ∈ ΣoR mà r không xuất hiện trong KB thì rI = ∅.

Các định nghĩa khái niệm và định nghĩa vai trò đối tượng áp dụng cho giả thiết

tên duy nhất và giả thiết thế giới đóng.

Định nghĩa 3.3. Cho cơ sở tri thức không vòng KB = (cid:104)R, T , A(cid:105). Hệ thống thông tin dựa trên logic mô tả được xác định bởi một cơ sở tri thức không vòng KB trong LΣ,Φ là một mô hình chuẩn của cơ sở tri thức đó trong LΣ,Φ.

3.2.1. Giới thiệu bài toán

3.2. Học khái niệm trong logic mô tả với Ngữ cảnh (3)

Cho I là một hệ thống thông tin huấn luyện trong LΣ,Φ. Gọi Ad ∈ ΣC là một khái niệm đại diện cho “thuộc tính quyết định”, E = (cid:104)E+, E−(cid:105) với E+ = {a | aI ∈ AI d} và E− = {a | aI ∈ (¬AI d)} tương ứng là tập các mẫu dương và mẫu âm của Ad trong I. Giả sử rằng Ad có thể được biểu diễn bởi một khái niệm C trong ngôn ngữ con LΣ†,Φ†, trong đó Σ† ⊆ Σ \ {Ad} và Φ† ⊆ Φ. Học khái niệm C dựa trên các thông tin cơ bản I, E+, E− trong ngôn ngữ con LΣ†,Φ† sao cho C thỏa mãn các điều kiện sau:

• I |= C(a) với mọi a ∈ E+, • I |= ¬C(a) với mọi a ∈ E−.

Lưu ý rằng, I |= ¬C(a) tương đồng với I (cid:54)|= C(a). Với E = (cid:104)E+, E−(cid:105), trong đó E+ là tập chứa các mẫu dương và E− là tập chứa các mẫu âm cho trước, ta nói rằng tập Y ⊆ ∆I bị phân chia bởi E nếu tồn tại a ∈ E+ và b ∈ E− sao cho {aI, bI} ⊆ Y . Một phân hoạch Y = {Y1, Y2, . . . , Yn} của ∆I được gọi là nhất quán với E nếu với mọi 1 ≤ i ≤ n, Yi không bị phân chia bởi E.

3.2.2. Bộ chọn

Dựa trên ý tưởng của phương pháp được đề xuất bởi Nguyen và Sza(cid:32)las [14], phương pháp học khái niệm trong luận án này cũng thực hiện làm mịn phân hoạch ∆I bằng các bộ chọn để đạt được phân hoạch tương ứng với ∼Σ†,Φ†,I.

C và d ∈ range(A),

A \ Σ† dR và d ∈ range(σ), oR và 1 ≤ t ≤ k,

Định nghĩa 3.4. Một bộ chọn cơ bản trong LΣ†,Φ† dùng để phân chia khối Yij của phân hoạch Y = {Yi1, Yi2, . . . , Yik} là một khái niệm thuộc một trong các dạng sau:

• A, trong đó A ∈ Σ† C, • A = d, trong đó A ∈ Σ† • ∃σ.{d}, trong đó σ ∈ Σ† • ∃r.Cit, trong đó r ∈ Σ† • ∃r−.Cit, nếu I ∈ Φ†, r ∈ Σ† oR và 1 ≤ t ≤ k, • {a}, nếu O ∈ Φ† và a ∈ Σ† I,

oR,

oR, oR, 0 < l ≤ #∆I và 0 ≤ m < #∆I,

và

• ≤ 1 r, nếu F ∈ Φ† và r ∈ Σ† • ≤ 1 r−, nếu {F, I} ⊆ Φ† và r ∈ Σ† • ≥ l r và ≤ m r, nếu N ∈ Φ†, r ∈ Σ† • ≥ l r− và ≤ m r−, nếu {N , I} ⊆ Φ†, r ∈ Σ† • ≥ l r.Cit và ≤ m r.Cit, nếu Q ∈ Φ†, r ∈ Σ†

oR, 0 < l ≤ #∆I và 0 ≤ m < #∆I, oR, 1 ≤ t ≤ k, 0 < l ≤ #C I it

0 ≤ m < #C I it

• ≥ l r−.Cit và ≤ m r−.Cit, nếu {Q, I} ⊆ Φ†, r ∈ Σ†

oR, 1 ≤ t ≤ k, 0 < l ≤ #C I it

(cid:4)

, và 0 ≤ m < #C I it

• ∃r.Self, nếu Self ∈ Φ† và r ∈ Σ†

oR.

Định lý 3.1. Cho Σ và Σ† là các bộ ký tự logic mô tả sao cho Σ† ⊆ Σ, Φ và Φ† là tập các đặc trưng logic mô tả sao cho Φ† ⊆ Φ, I là một hệ thống thông tin trong LΣ,Φ. Xuất phát từ phân hoạch {∆I} và thực hiện việc làm mịn liên tục nó bằng các bộ chọn cơ bản ta sẽ nhận được một phân hoạch tương ứng với quan hệ tương đương ∼Σ†,Φ†,I.(cid:4)

Định nghĩa 3.5 (Bộ chọn đơn giản). Giả sử Y1, Y2, . . . , Yn là các khối được tạo ra trong quá trình làm mịn phân hoạch {∆I}, trong đó Yi được đặc trưng bởi khái niệm Ci sao cho Yi = C I i . Một bộ chọn đơn giản trong LΣ†,Φ† để phân chia một khối là một bộ chọn cơ bản hoặc một khái niệm có dạng sau:

• A ≤ d và A < d, trong đó A ∈ Σ†

nA, d ∈ range(A) và d không phải là phần tử

nhỏ nhất của range(A),

• A ≥ d và A > d, trong đó A ∈ Σ†

nA, d ∈ range(A) và d không phải là phần tử

oR và 1 ≤ i ≤ n,

lớn nhất của range(A),

• ∃r.(cid:62), ∃r.Ci và ∀r.Ci, trong đó r ∈ Σ† • ∃r−.(cid:62), ∃r−.Ci và ∀r−.Ci, nếu I ∈ Φ†, r ∈ Σ† • ≥ l r.Ci và ≤ m r.Ci, nếu Q ∈ Φ†, r ∈ Σ†

oR và 1 ≤ i ≤ n, oR, 1 ≤ i ≤ n, 0 < l ≤ #C I

i và

0 ≤ m < #C I i ,

• ≥ l r−.Ci và ≤ m r−.Ci, nếu {Q, I} ⊆ Φ†, r ∈ Σ†

oR, 1 ≤ i ≤ n, 0 < l ≤ #C I i (cid:4)

và 0 ≤ m < #C I i .

Gọi D là tập chứa các bộ chọn hiện có. Cùng với phân hoạch hiện thời Y, tập D = {D1, D2, . . . , Dh} được gọi là tập các bộ chọn hiện thời. Chúng tôi định nghĩa các bộ chọn mở rộng để phục vụ cho quá trình làm mịn được hiệu quả hơn.

oR và Du ∈ D,

Định nghĩa 3.6 (Bộ chọn mở rộng). Cho D = {D1, D2, . . . , Dh} là tập các bộ chọn hiện thời. Một bộ chọn mở rộng trong LΣ†,Φ† để phân chia một khối của phân hoạch hiện thời là một khái niệm thuộc một trong các dạng sau:

• ∃r.Du và ∀r.Du, trong đó r ∈ Σ† • ∃r−.Du và ∀r−.Du, nếu I ∈ Φ†, r ∈ Σ†

oR và Du ∈ D,

• ≥ l r.Du và ≤ m r.Du, nếu Q ∈ Φ†, r ∈ Σ†

oR, Du ∈ D, 0 < l ≤ #DI

u và

0 ≤ m < #DI u,

• ≥ l r−.Du và ≤ m r−.Du, nếu {Q, I} ⊆ Φ†, r ∈ Σ†

oR, Du ∈ D, 0 < l ≤ #DI

u và

(cid:4)

0 ≤ m < #DI u.

3.2.3. Tính đơn giản của khái niệm

Định nghĩa 3.7. Cho C là một khái niệm ở dạng chuẩn trong ngôn ngữ LΣ,Φ. Độ sâu khả năng của khái niệm C, ký hiệu là mdepth(C), được xác định như sau:

• 0 nếu C có dạng (cid:62), ⊥, A, A = d, A (cid:54)= d, A > d, A ≥ d, A < d hoặc A ≤ d,

• mdepth(D) nếu C là dạng chuẩn của ¬D,

• 1 nếu C có dạng ∃σ.{d}, ∃r.Self, ≥ n R hoặc ≤ n R,

• 1 + mdepth(D) nếu C có dạng ∃R.D, ∀R.D, ≥ n R.D hoặc ≤ n R.D, • max{mdepth(D1), mdepth(D2), . . . , mdepth(Dn)} nếu C có dạng (cid:117){D1, D2, . . . , Dn}

(cid:4)

hoặc (cid:116){D1, D2, . . . , Dn}.

Định nghĩa 3.8. Cho C là một khái niệm ở dạng chuẩn trong ngôn ngữ LΣ,Φ. Độ dài của khái niệm C, ký hiệu bởi length(C), được xác định như sau:

• 0 nếu C có dạng (cid:62) hoặc ⊥,

• 1 nếu C có dạng A, A = d, A (cid:54)= d, A > d, A ≥ d, A < d hoặc A ≤ d,

• length(D) nếu C ≡ D và D là dạng chuẩn của ¬D,

• 3 nếu C có dạng ∃σ.{d}, ∃r.Self, ≥ n R hoặc ≤ n R,

• 2 + length(D) nếu C có dạng ∃R.D hoặc ∀R.D,

• 3 + length(D) nếu C có dạng ≥ n R.D hoặc ≤ n R.D, • 1+length(D1)+length(D2)+· · ·+length(Dn) nếu C có dạng (cid:117){D1, D2, . . . , Dn} (cid:4)

hoặc (cid:116){D1, D2, . . . , Dn}.

3.2.4. Độ đo dựa trên entropy

Khái niệm đơn giản nhất là khái niệm có độ dài và độ sâu khả năng nhỏ nhất.

Cho I là một hệ thống thông tin, X và Y là các tập con của ∆I, trong đó X đóng

vai trò là tập các mẫu dương, Y đóng vai trò là một khối của phân hoạch.

Định nghĩa 3.9 (Entropy). Entropy của tập Y đối với tập X trong miền ∆I của hệ thống thông tin I, ký hiệu là E∆I (Y /X), được xác định như sau:

  (3.1)

E∆I (Y /X) =

−

, nếu ngược lại,

log2



0, nếu Y ∩ X = ∅ hoặc Y ⊆ X #XY #Y

#XY #Y

(cid:4)

trong đó XY đại diện cho tập X ∩ Y và XY đại diện cho tập X ∩ Y .

Định nghĩa 3.10 (Gia lượng thông tin). Gia lượng thông tin của bộ chọn D trong việc phân chia tập Y đối với tập X trong ∆I của hệ thống thông tin I, ký hiệu là IG∆I (Y /X, D), được xác định như sau:

(3.2)

E∆I (DIY /X)+

(cid:33) E∆I (DIY /X)

IG∆I (Y /X, D) = E∆I (Y /X) −

(cid:32) #DIY #Y

#DIY #Y

(cid:4)

trong đó DIY đại diện cho tập DI ∩ Y và DIY đại diện cho tập DI ∩ Y .

Trong ngữ cảnh ∆I và X đã rõ ràng, chúng ta viết E(Y ) thay cho E∆I (Y /X) và

IG(Y, D) thay cho IG∆I (Y /X, D).

3.2.5. Thuật toán học khái niệm trong logic mô tả với Ngữ cảnh (3)

Function chooseBlockSelector

(cid:11) sao cho IG(Yij , Sij ) cực đại, trong đó Yij ∈ Y và Sij ∈ D

Input : Y, D Output: (cid:10)Yij , Sij

1 BS := ∅; 2 foreach Yij ∈ Y do

foreach Du ∈ D do Tính IG(Yij , Du);

S := arg max

{IG(Yij , Du)};

Du∈D

(cid:11)};

Lấy Sij ∈ S sao cho Sij là khái niệm đơn giản nhất; BS := BS ∪ {(cid:10)Yij , Sij

(cid:11) ∈ BS sao cho IG(Yij , Sij ) là cực đại;

(cid:11);

8 Chọn (cid:10)Yij , Sij 9 return (cid:10)Yij , Sij

Phương pháp học khái niệm cho hệ thống thông tin trong logic mô tả được mô tả như trong Thuật toán 3.1, trong thuật toán này có sử dụng hàm chooseBlockSelector để quyết định khối và bộ chọn cần phân chia trước.

3.3. Ví dụ minh họa

Các ví dụ sau đây chỉ ra một bức tranh khá đầy đủ về hiệu quả của các bộ chọn đơn giản và bộ chọn mở rộng đã đề cập trong Mục 3.2.2. Đầu tiên chúng ta xét ví dụ về một cơ sở tri thức và hệ thống thông tin tương ứng với cơ sở tri thức đó.

ΣI = {Ava, Britt, Colin, Dave, Ella, F lor, Gigi, Harry},

ΣC = {Human, M ale, F emale, N ephew, N iece}, ΣdA = ΣC, ΣnA = ∅,

ΣoR = {hasChild, hasP arent, hasSibling}, ΣdR = ∅. R = {hasP arent ≡ hasChild−, Sym(hasSibling)}, T = {Human ≡ (cid:62), N iece ≡ F emale (cid:117) ∃hasChild−.(∃hasSibling.(cid:62)),

N ephew ≡ M ale (cid:117) ∃hasChild−.(∃hasSibling.(cid:62))},

Ví dụ 3.1. Cho cơ sở tri thức KB = (cid:104)R, T , A(cid:105)trong LΣ,Φ, với Σ = ΣI ∪ ΣdA ∪ ΣnA ∪ ΣoR ∪ ΣdR và Φ = {I}, trong đó:

Thuật toán 3.1: Học khái niệm cho hệ thống thông tin trong logic mô tả

Input : I, Σ†, Φ†, E = (cid:104)E−, E+(cid:105) Output: Khái niệm C sao cho:

• I |= C(a) với mọi a ∈ E+, và • I (cid:54)|= C(a) với mọi a ∈ E−.

/* Định nghĩa 3.4, 3.5 và/hoặc 3.6 */

1 n := 1; Y1 := ∆I; C1 := (cid:62); Y := {Y1}; D = ∅; 2 Tạo và thêm các bộ chọn vào D; 3 while (Y không nhất quán với E) do 4

(cid:11) := chooseBlockSelector(Y, D);

) then

(cid:10)Yij , Sij if (Yij không bị phân chia bởi SI ij

break;

;

Cs := Cij (cid:117) Sij ;

s := n + 1; t := n + 2; n := n + 2; Ys := Yij ∩ SI ij Yt := Yij ∩ (¬Sij )I; Ct := Cij (cid:117) ¬Sij ; if (Yij không bị phân chia bởi E) then

LargestContainer [s] := LargestContainer [ij]; LargestContainer [t] := LargestContainer [ij];

else

if (Ys không bị phân chia bởi E) then

LargestContainer [s] := s;

if (Yt không bị phân chia bởi E) then

LargestContainer [t] := t;

Y := Y ∪ {Ys, Yt} \ {Yij }; Tạo và thêm các bộ chọn vào D;

/* Định nghĩa 3.4, 3.5 và/hoặc 3.6 */

19 20 J := ∅; C := ∅; 21 if (Y nhất quán với E) then foreach Yij ∈ Y do 22

if (∃a ∈ E+ : aI ∈ Yij ) then

J := J ∪ {LargestContainer [ij]} ;

foreach l ∈ J do C := C ∪ {Cl};

C := (cid:70) C; return Crs :=simplify (C);

28 29 else

return failure;

A = {F emale(Ava), F emale(Britt), M ale(Colin), M ale(Dave), F emale(Ella),

F emale(F lor), F emale(Gigi), hasChild(Ava, Dave), hasChild(Ava, Ella),

M ale(Harry), hasChild(Britt, F lor), hasChild(Colin, Gigi), hasChild(Colin, Harry),

hasSibling(Britt, Colin), hasSibling(Colin, Britt), hasSibling(Dave, Ella),

hasSibling(Ella, Dave), hasSibling(Gigi, Harry), hasSibling(Harry, Gigi)}.

∆I = {Ava, Britt, Colin, Dave, Ella, F lor, Gigi, Harry},

AvaI = Ava, BrittI = Britt, . . . , HarryI = Harry,

HumanI = ∆I, F emaleI= {Ava, Britt, Ella, F lor, Gigi},

M aleI = {Colin, Dave, Harry}, hasChildI = {(cid:104)Ava, Dave(cid:105),(cid:104)Ava, Ella(cid:105),(cid:104)Britt, F lor(cid:105),(cid:104)Colin, Gigi(cid:105),(cid:104)Colin, Harry(cid:105)}, hasP arentI = {(cid:104)Dave, Ava(cid:105),(cid:104)Ella, Ava(cid:105),(cid:104)F lor, Britt(cid:105),(cid:104)Gigi, Colin(cid:105),(cid:104)Harry, Colin(cid:105)}, hasSiblingI = {(cid:104)Britt, Colin(cid:105), (cid:104)Colin, Britt(cid:105), (cid:104)Dave, Ella(cid:105), (cid:104)Ella, Dave(cid:105),

(cid:104)Gigi, Harry(cid:105), (cid:104)Harry, Gigi(cid:105)},

(cid:4)

(hasSibling−)I = hasSiblingI, N ieceI = {F lor, Gigi}, N ephewI = {Harry}.

Hệ thống thông tin I của cơ sở tri thứ KB có thể được xây dựng như sau:

Ví dụ tiếp theo chỉ ra rằng sử dụng các bộ chọn đơn giản kết hợp với bộ chọn mở

rộng cho kết quả tốt hơn so với chỉ sử dụng các bộ chọn đơn giản.

Ví dụ 3.2. Xét hệ thống thông tin I như đã cho trong Ví dụ 3.1, ngôn ngữ con LΣ†,Φ† với Σ† = {F emale, hasChild, hasSibling} và Φ† = {I}, và tập X = {F lor, Gigi} (nghĩa là, E = (cid:104)E+, E−(cid:105)với E+ = {F lor, Gigi} và E− = {Ava, Britt, Colin, Dave, Ella, Harry}). Học định nghĩa của tập X. Chúng ta có thể xem X như là tập các thể hiện của khái niệm N iece ≡ F emale (cid:117) ∃hasChild−.(∃hasSibling.(cid:62)) trong I.

1. Học định nghĩa của X trong LΣ†,Φ† bằng cách sử dụng các bộ chọn đơn giản.

Khái niệm kết quả học được rút gọn thành khái niệm Crs như sau:

Crs ≡ F emale (cid:117) ∀hasChild.⊥ (cid:117) (∀hasChild−.(¬F emale) (cid:116) ∀hasSibling.⊥).

2. Học định nghĩa của X trong LΣ†,Φ† bằng cách sử dụng các bộ chọn đơn giản và

bộ chọn mở rộng. Khái niệm kết quả học được là Crs ≡ F emale (cid:117) ∃hasChild−.(∃hasSibling.(cid:62)).

Trong trường hợp thứ hai, khái niệm ∃hasChild−.(∃hasSibling.(cid:62)) là một bộ chọn mở rộng. Bộ chọn này được tạo ra bằng cách áp dụng luật thứ hai trong Định nghĩa 3.6 với ∃hasSibling.(cid:62) là một khái niệm có trong tập các bộ chọn hiện thời D.(cid:4)

3.4. Kết quả thực nghiệm

Các tập dữ liệu dùng để thử nghiệm là WebKB [16], PokerHand [3] và Family.

Chúng tôi trình bày các thông tin chi tiết như sau:

• độ sâu khả năng (Dep.) trung bình (Avg.) của các khái niệm gốc (Org.),

• độ dài (Len.) trung bình của các khái niệm gốc,

• độ sâu khả năng trung bình của các khái niệm kết quả (Res.),

• độ dài trung bình của các khái niệm kết quả,

• độ đúng đắn (Acc.), tỉ lệ chính xác (Pre.), tỉ lệ bao phủ (Rec.) và độ đo F1,

• độ lệch chuẩn, giá trị nhỏ nhất (Min) và giá trị lớn nhất (Max) của độ đúng

đắn, tỉ lệ chính xác, độ bao phủ và độ đo F1.

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

Avg. Dep. Avg. Len. Res./Org. Res./Org.

Avg. Acc. [Min;Max]

Avg. Pre. [Min;Max]

Avg. Rec. [Min;Max]

Avg. F1 [Min;Max]

WebKB dataset

0.82/1.02

6.81/4.41

Bộ chọn đơn giản

93.84±13.50 [33.69;100.0]

92.09±17.04 [32.08;100.0]

92.82±17.32 [23.08;100.0]

91.59±16.68 [27.69;100.0]

0.84/1.02

3.40/4.41

Bộ chọn đơn giản và mở rộng

94.60±12.20 [33.69;100.0]

92.81±15.93 [32.08;100.0]

93.14±17.17 [23.08;100.0]

92.33±16.17 [27.69;100.0]

PokerHand dataset

1.41/2.60

37.02/15.97

Bộ chọn đơn giản

97.17±08.61 [50.57;100.0]

95.96±14.99 [01.67;100.0]

94.95±14.40 [01.67;100.0]

94.66±14.64 [01.67;100.0]

1.23/2.60

3.47/15.97

Bộ chọn đơn giản và mở rộng

99.44±02.15 [83.25;100.0]

98.68±09.08 [01.67;100.0]

98.06±09.58 [01.67;100.0]

98.18±09.14 [01.67;100.0]

Family dataset

2.38/3.34

78.50/18.59

Bộ chọn đơn giản

88.50±16.65 [27.91;100.0]

90.60±18.57 [04.55;100.0]

85.66±22.36 [07.69;100.0]

86.09±20.10 [08.70;100.0]

2.29/3.34

10.20/18.59

Bộ chọn đơn giản và mở rộng

92.79±14.35 [27.91;100.0]

91.99±18.40 [04.55;100.0]

91.75 ±19.82 [07.69;100.0]

90.39±19.89 [08.70;100.0]

Qua quan sát Bảng 3.1 và các bảng khác trong luận án, chúng ta thấy rõ ràng rằng sử dụng thêm bộ chọn mở rộng có hiệu quả cao hơn trong việc giảm độ dài của khái niệm và cho kết quả phân lớp tốt hơn. Chúng tôi cũng đã kiểm tra đối với các khái niệm phổ biến/tập đối tượng cho trước trên tập dữ liệu Family và PokerHand.

Tiểu kết Chương 3

Chương này đề xuất thuật toán học khái niệm trong logic mô tả với Ngữ cảnh (3) sử dụng mô phỏng hai chiều. Thuật toán học này cùng với những chiến lược phân hoạch được sử dụng đã được kiểm nghiệm trên hai khía cạnh lý thuyết và thực nghiệm. Để quá trình phân hoạch miền đạt hiệu quả cao, ngoài các bộ chọn cơ bản và bộ chọn đơn giản, các bộ chọn mở rộng cũng được sử dụng trong chương trình cài đặt của thuật toán. Các kết quả thực nghiệm đã chứng tỏ rằng phương pháp đề xuất có ý nghĩa và các bộ chọn mở rộng hỗ trợ rất tốt cho quá trình làm mịn phân hoạch.

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

Các bài toán học khái niệm trong chương này được đặt ra theo hai ngữ cảnh sau:

• Ngữ cảnh (1): Cho L là một logic mô tả quyết định được trong LΣ,Φ có tính chất mô hình nửa hữu hạn, Ad ∈ ΣC là khái niệm đại diện cho “thuộc tính quyết định” và cơ sở tri thức KB0 = (cid:104)R, T , A0(cid:105) trong logic mô tả L không chứa Ad. Với E = (cid:104)E+, E−(cid:105), trong đó E+ và E− là các tập con không giao nhau của ΣI sao cho cơ sở tri thức KB = (cid:104)R, T , A(cid:105) với A = A0 ∪ {Ad(a) | a ∈ E+} ∪ {¬Ad(a) | a ∈ E−} thỏa mãn được. Học khái niệm C như là một định nghĩa của Ad trong ngôn ngữ con LΣ†,Φ†, với Σ† ⊆ Σ \ {Ad} và Φ† ⊆ Φ sao cho:

1. KB |= C(a) với mọi a ∈ E+, và 2. KB |= ¬C(a) với mọi a ∈ E−.

• Ngữ cảnh (2): Ngữ cảnh này tương tự như Ngữ cảnh (1) nhưng với điều kiện

thứ hai được thay thế bằng một điều kiện yếu hơn:

2. KB (cid:54)|= C(a) với mọi a ∈ E−.

Lưu ý rằng, hai bài toán trên được giải quyết theo giả thuyết thế giới mở.

0 như đã cho trong Ví dụ 1.1 và diễn dịch

4.2. Phân hoạch miền của diễn dịch

0 như sau: ∆I = {P1, P2, P3, P4, P5, P6},

Chúng tôi xây dựng thuật toán để làm mịn phân hoạch thông qua Hàm partition. Hàm này cũng sử dụng hàm chooseBlockSelector để quyết định khối và bộ chọn cần phân chia trước. Ví dụ 4.1. Xét cơ sở tri thức KB0 và KB(cid:48) I là mô hình của KB và KB(cid:48)

xI = x với x ∈ {P1, P2, P3, P4, P5, P6}, PubI = ∆I, Awarded I = {P1, P4, P6}, UsefulPubI = {P2, P3, P4, P5, P6}, cites I = {(cid:104)P1, P2(cid:105), (cid:104)P1, P3(cid:105), (cid:104)P1, P4(cid:105), . . . , (cid:104)P4, P5(cid:105), (cid:104)P4, P6(cid:105)},

cited_by I = (cites I)−1, hàm từng phần Year I được đặc tả theo từng cá thể.

Cho E = (cid:104)E+, E−(cid:105) với E+ = {P4, P6} và E− = {P1, P2, P3, P5}, ngôn ngữ con LΣ†,Φ†, trong đó Σ† = {Awarded , cited_by} và Φ† = ∅. Các bước làm mịn miền ∆I của I theo Hàm partition được mô tả như sau:

1. Y1 := ∆I, C1 := (cid:62), Y := {Y1} 2. Phân chia khối Y1 bởi Awarded chúng ta thu được:

• Y2 := {P1, P4, P6}, C2 := Awarded , • Y3 := {P2, P3, P5}, C3 := ¬Awarded , ⇒ Y := {Y2, Y3}

Function partition - Làm mịn miền của diễn dịch trong logic mô tả

Input : I, Σ†, Φ†, E = (cid:104)E+, E−(cid:105) Output: Y = {Yi1, Yi2, . . . , Yik} là một phân hoạch của miền ∆I sao cho Y nhất quán

với E

/* Định nghĩa 3.4, 3.5 và/hoặc 3.6 */

1 n := 1; Y1 := ∆I; C1 := (cid:62); Y := {Y1}; D := ∅; 2 Tạo và thêm các bộ chọn vào D; 3 while (Y không nhất quán với E) do 4

(cid:11) := chooseBlockSelector(Y, D);

) then

(cid:10)Yij , Sij if (Yij không bị phân chia bởi SI ij

break;

;

Cs := Cij (cid:117) Sij ;

s := n + 1; t := n + 2; n := n + 2; Ys := Yij ∩ SI ij Yt := Yij ∩ (¬Sij )I; Ct := Cij (cid:117) ¬Sij ; Y := Y ∪ {Ys, Yt} \ {Yij }; Tạo và thêm các bộ chọn vào D;

/* Định nghĩa 3.4, 3.5 và/hoặc 3.6 */

return Y;

11 12 if (Y nhất quán với E) then 13 14 else

return failure;

3. Chúng ta sử dụng bộ chọn đơn giản nhất ∃cited_by.(cid:62) để phân chia Y2:

• Y4 := {P4, P6}, C4 := C2 (cid:117) ∃cited_by.(cid:62), • Y5 := {P1}, C5 := C2 (cid:117) ¬∃cited_by.(cid:62), ⇒ Y := {Y3, Y4, Y5}

Phân hoạch đạt được là Y = {Y3, Y4, Y5} nhất quán với E.

4.3.1. Thuật toán BBCL

4.3. Học khái niệm trong logic mô tả với Ngữ cảnh (1)

4.3.2. Thuật toán dual-BBCL

rs và lấy kết quả trả về là khái niệm ¬C (cid:48)

Ý tưởng chính của thuật toán BBCL để giải quyết bài toán này là sử dụng các mô hình của KB kết hợp với mô phỏng hai chiều trong mô hình đó và cây quyết định cho việc tìm kiếm khái niệm C. Thuật toán này sử dụng Hàm partition được nêu ở Mục 4.2 để làm mịn miền ∆I của diễn dịch I là mô hình của KB.

4.3.3. Tính đúng đắn của thuật toán BBCL

Thuật toán dual-BBCL được sử dụng để học khái niệm trong logic mô tả với Ngữ cảnh (1). Bằng cách hoán đổi các tập E+ và E− cho nhau, sau đó áp dụng Thuật toán BBCL chúng ta sẽ nhận được khái niệm C (cid:48) rs.

Mệnh đề 4.1 (Tính đúng đắn của thuật toán BBCL). Thuật toán BBCL là đúng đắn. Nghĩa là, nếu thuật toán BBCL trả về một khái niệm Crs thì Crs là một lời giải của bài toán học khái niệm cho cơ sở tri thức trong logic mô tả với Ngữ cảnh (1). (cid:4)

Thuật toán 4.1: BBCL - Học khái niệm trong logic mô tả với Ngữ cảnh (1)

Input : KB, Σ† ⊆ Σ \ {Ad}, Φ† ⊆ Φ, E = (cid:104)E+, E−(cid:105), k Output: Khái niệm C trong LΣ†,Φ† sao cho:

• KB |= C(a) với mọi a ∈ E+, và

• KB |= ¬C(a) với mọi a ∈ E−.

1 C := ∅; C0 := ∅; 2 while not (too hard to extend C) do 3

|k;

/* phân hoạch ∆I theo Hàm partition */

Xây dựng mô hình hữu hạn (tiếp theo) I của KB hoặc I = I (cid:48) Y := partition (I, Σ†, Φ†, E); foreach Yij ∈ Y sao cho ∃a ∈ E+: aI ∈ Yij và ∀a ∈ E−: aI (cid:54)∈ Yij do

if (KB |= ¬Cij (a) với mọi a ∈ E−) then

if (KB (cid:54)|= (Cij (cid:118) (cid:70) C)) then

C := C ∪ {Cij };

else

C0 := C0 ∪ {Cij };

if (KB |= ((cid:70) C)(a) với mọi a ∈ E+) then

go to 20;

13 while not (too hard to extend C) do 14

D := D1 (cid:117) D2 (cid:117) · · · (cid:117) Dl, với D1, D2, . . . , Dl được chọn ngẫu nhiên từ C0; if (KB |= ¬D(a) với mọi a ∈ E− và KB (cid:54)|= (D (cid:118) (cid:70) C)) then

C := C ∪ {D}; if (KB |= ((cid:70) C)(a) với mọi a ∈ E+) then

go to 20;

19 return failure; 20 foreach D ∈ C do 21

if (KB |= (cid:70)(C \ {D})(a) với mọi a ∈ E+) then

C := C \ {D};

/* rút gọn khái niệm C */

23 C := (cid:70) C; 24 return Crs := simplify (C);

4.3.4. Ví dụ minh họa

Ví dụ 4.2. Xét cơ sở tri thức KB0 = (cid:104)R, T , A0(cid:105) như đã cho trong Ví dụ 1.1 và E = (cid:104)E+, E−(cid:105) với E+ = {P4, P6}, E− = {P1, P2, P3, P5}, Σ† = {Awarded , cited_by} và Φ† = ∅. Học định nghĩa cho Ad với KB = (cid:104)R, T , A(cid:105), trong đó A = A0 ∪ {Ad(a) | a ∈ E+} ∪ {¬Ad(a) | a ∈ E−}. Thuật toán BBCL thực hiện như sau:

1. C := ∅, C0 := ∅. 2. KB có nhiều mô hình, trong đó mô hình I được đặc tả như trong Ví dụ 4.1.

3. Áp dụng Hàm partition để làm mịn miền ∆I của I, ta được phân hoạch Y = {Y3, Y4, Y5} nhất quán với E tương ứng với các khái niệm đặc trưng C3, C4, C5, trong đó Y3 = {P2, P3, P5}, Y4 = {P4, P6}, Y5 = {P1} và C3 ≡ ¬Awarded , C4 ≡ Awarded (cid:117) ∃cited_by.(cid:62), C5 ≡ ¬Awarded (cid:117) ∃cited_by.(cid:62).

4. Vì Y4 ⊆ E+ nên ta xem xét C4 ≡ Awarded (cid:117) ∃cited_by.(cid:62). Vì KB |= ¬C4(a) với mọi a ∈ E− nên ta thêm C4 vào C. Do đó, ta có C ≡ {C4} và (cid:70) C ≡ C4. 5. Vì KB |= ((cid:70) C)(a) với mọi a ∈ E+ nên ta có C ≡ (cid:70) C ≡ Awarded (cid:117) ∃cited_by.(cid:62). Do khái niệm C đã ở dạng chuẩn và không thể đơn giản hơn được nữa nên kết quả trả về là Crs ≡ Awarded (cid:117) ∃cited_by.(cid:62). (cid:4)

Ví dụ 4.3. Xét thuật toán dual-BBCL đối với Ví dụ 4.2 và hoán đổi E+ và E− với nhau. Thuật toán dual-BBCL thực hiện ba bước đầu tiên giống như Ví dụ 4.2 và các bước tiếp theo như sau:

4. Vì Y3 ⊆ E+ nên ta xem xét C3 ≡ ¬Awarded . Vì KB |= ¬C3(a) với mọi a ∈ E−

nên ta thêm C3 vào C. Do đó, ta có C = {C3}.

5. Vì Y5 ⊆ E+ nên ta xem xét C5 ≡ Awarded (cid:117) ¬∃cited_by.(cid:62). Vì KB |= ¬C5(a) với mọi a ∈ E− và C5 không bị bao hàm bởi (cid:70) C dựa trên KB nên ta thêm C5 vào C. Do đó, ta có C = {C3, C5} và (cid:70) C ≡ C3 (cid:116) C5.

6. Vì KB |= ((cid:70) C)(a) với mọi a ∈ E+ nên ta có C ≡ (cid:70) C ≡ ¬Awarded (cid:116) (Awarded (cid:117) ¬∃cited_by.(cid:62)). Chuẩn hóa và đơn giản khái niệm C ta được kết quả trả về là Crs ≡ ¬Awarded (cid:116) ¬∃cited_by.(cid:62). (cid:4)

Nếu muốn lấy kết quả của Ví dụ 4.2 chúng ta lấy phủ định của Crs. Lúc đó kết

quả là ¬Crs ≡ ¬(¬Awarded (cid:116) ¬∃cited_by.(cid:62)) ≡ Awarded (cid:117) ∃cited_by.(cid:62).

4.4.1. Thuật toán BBCL2

4.4. Học khái niệm trong logic mô tả với Ngữ cảnh (2)

Phương pháp học khái niệm cho cơ sở tri thức trong logic mô tả với Ngữ cảnh (2)

4.4.2. Tính đúng đắn của thuật toán BBCL2

được trình bày chi tiết thông qua Thuật toán 4.2.

0 = (cid:104)R, T , A(cid:48)

4.4.3. Ví dụ minh họa Ví dụ 4.4. Xét cơ sở tri thức KB(cid:48) 0(cid:105) như đã cho trong Ví dụ 1.1 và E = (cid:104)E+, E−(cid:105), Σ†, Φ† như trong Ví dụ 4.2. Đặt KB = (cid:104)R, T , A(cid:105) với A = A(cid:48) 0 ∪ {Ad(a) | a ∈ E+} ∪ {¬Ad(a) | a ∈ E−}. Thuật toán BBCL2 thực hiện ba bước đầu tiên giống như Ví dụ 4.2 (có bổ sung thêm E− 0 := ∅) và các bước tiếp theo như sau:

Mệnh đề 4.2 (Tính đúng đắn của thuật toán BBCL2). Thuật toán BBCL2 là đúng đắn. Nghĩa là, nếu thuật toán BBCL2 trả về một khái niệm Crs thì Crs là một lời giải của bài toán học khái niệm cho cơ sở tri thức trong logic mô tả với Ngữ cảnh (2). (cid:4)

0 = {P2, P3, P5}.

4. Vì Y3 ⊆ E− nên ta xem xét C3 ≡ ¬Awarded . Vì KB |= ¬C3(a) với mọi a ∈ E+ 0 . Do đó, ta có nên ta thêm ¬C3 vào C và thêm các phần tử của Y3 vào E− C = {C3} và E−

0 = {P1, P2, P3, P5}.

5. Vì Y5 ⊆ E− nên ta xem xét C5 ≡ Awarded (cid:117) ¬∃cited_by.(cid:62). Vì KB |= ¬C5(a) với mọi a ∈ E+ và (cid:100) C không bị bao hàm bởi C5 dựa trên KB nên ta thêm ¬C5 vào C. Do đó, ta có C = {¬C3, ¬C5} và E−

0 = E− nên ta có C ≡ (cid:100) C ≡ ¬¬Awarded (cid:117)¬(Awarded (cid:117)¬∃cited_by.(cid:62)). Rút gọn khái niệm C ta được kết quả trả về là Crs ≡ Awarded (cid:117) ∃cited_by.(cid:62).(cid:4)

6. Vì E−

Thuật toán 4.2: BBCL2 - Học khái niệm trong logic mô tả với Ngữ cảnh (2)

Input : KB, Σ†, Φ†, E = (cid:104)E+, E−(cid:105), k Output: Khái niệm C sao cho:

• KB |= C(a) với mọi a ∈ E+, và

• KB (cid:54)|= C(a) for all a ∈ E−.

0 := ∅;

0 (cid:54)= E−) do

1 C := ∅; C0 := ∅; E− 2 while not (too hard to extend C) và (E− 3

|k;

/* phân hoạch ∆I theo Hàm partition */

Xây dựng mô hình hữu hạn (tiếp theo) I của KB hoặc I = I (cid:48) Y :=partition (I, Σ†, Φ†, E); foreach Yij ∈ Y sao cho ∃a ∈ E−: aI ∈ Yij và ∀a ∈ E+: aI (cid:54)∈ Yij do

if (KB |= ¬Cij (a) với mọi a ∈ E+) then

if (KB (cid:54)|= ((cid:100) C (cid:118) ¬Cij )) then

C := C ∪ {¬Cij }; E−

0 := E−

0 ∪ {a ∈ E− | aI ∈ Yij };

else

C0 := C0 ∪ {¬Cij };

0 (cid:54)= E−) do

12 while not (too hard to extend C) và (E− 13

D := D1 (cid:116) D2 (cid:116) · · · (cid:116) Dl, với D1, D2, . . . , Dl được chọn ngẫu nhiên từ C0; if (KB |= D(a) với mọi a ∈ E+) then

if (KB (cid:54)|= ((cid:100) C) (cid:118) D) và (∃a ∈ E− \ E−

0 : KB (cid:54)|= ((cid:100) C (cid:117) D)(a)) then

C := C ∪ {D}; E− 0 := E−

0 ∪ {a | a ∈ E− \ E−

0 , KB (cid:54)|= ((cid:100) C)(a)};

0 = E−) then

18 if (E− 19

foreach (D ∈ C) do

if (KB (cid:54)|= (cid:100)(C \ {D})(a) với mọi a ∈ E−) then

C := C \ {D};

/* rút gọn khái niệm C */

C := (cid:100) C; return Crs := simplify (C);

23 24 else

return failure;

Tiểu kết Chương 4

Chương này trình bày phương pháp làm mịn phân hoạch miền của diễn dịch trong logic mô tả trên cơ sở của Thuật toán 3.1. Tiếp đó, chúng tôi đề xuất các thuật toán BBCL, dual-BBCL và BBCL2 để giải quyết hai bài toán học khái niệm cho cơ sở tri thức trong logic mô tả với Ngữ cảnh (1) và Ngữ cảnh (2). Ý tưởng chính của các thuật toán này là 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 các mô hình đó và cây quyết định để tìm kiếm khái niệm kết quả. Tính đúng của các thuật toán BBCL và BBCL2 cũng được chứng minh thông qua các bổ đề tương ứng. Các thuật toán này có thể áp dụng cho một lớp lớn các logic mô tả là mở rộng của ALCΣ,Φ có tính chất mô hình hữu hạn hoặc nửa hữu hạn, trong đó Φ ⊆ {I, F, N , Q, O, U, Self}.

KẾT LUẬN

Kết luận

Logic mô tả ngày càng khẳng định được vai trò quan trọng trong các hệ thống biểu diễn và suy luận tri thức. Kể từ khi logic mô tả được xem là nền tảng của ngôn ngữ OWL (một ngôn ngữ được sử dụng để mô hình hóa các hệ thống ngữ nghĩa và ontology theo khuyến nghị của W3C), logic mô tả đã được nhiều nhà khoa học quan tâm nghiên cứu. Đối với các hệ thống ngữ nghĩa, việc tìm kiếm các khái niệm phù hợp, xây dựng những định nghĩa cho các khái niệm đó để đặc tả hệ thống là một vấn đề được đặt ra một cách tự nhiên. Học khái niệm trong logic mô tả là một trong những giải pháp để tìm kiếm và xây dựng định nghĩa cho các khái niệm. Với mục đích đó, luận án tập trung nghiên cứu bài toán học khái niệm trong logic mô tả sử dụng các ngữ cảnh khác nhau. Kết quả nghiên cứu của luận án có thể được tóm tắt như sau:

1. Xây dựng ngôn ngữ logic mô tả LΣ,Φ dựa trên ngôn ngữ ALCreg với tập các đặc trưng mở rộng gồm I, O, N , Q, F , U , Self. Ngoài ra ngôn ngữ được xây dựng còn 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ữ nhằm mô tả các hệ thống thông tin phù hợp với thực tế hơn.

2. Thông qua ngôn ngữ LΣ,Φ, luận án đã xây dựng mô phỏng hai chiều trên lớp các logic mở rộng đang nghiên cứu. Các định lý, bổ đề, hệ quả liên quan đến mô phỏng hai chiều và tính bất biến đối với mô phỏng hai chiều cũng được phát triển và chứng minh trên lớp các logic mở rộng này.

3. Phát triển thuật toán học khái niệm cho hệ thống thông tin trong logic mô tả với Ngữ cảnh (3). Các bộ chọn cơ bản, bộ chọn đơn giản và bộ chọn mở rộng được sử dụng trong quá trình làm mịn phân hoạch. Các chiến lược tìm kiếm cũng được đề xuất dựa vào gia lượng thông tin và tính đơn giản của khái niệm.

4. Xây dựng thuật toán BBCL, dual-BBCL, BBCL2 nhằm giải quyết các bài toán học khái niệm cho cơ sở tri thức trong logic mô tả với Ngữ cảnh (1) và Ngữ cảnh (2).

Những vấn đề cần tiếp tục nghiên cứu

Từ những kết quả đạt được trong luận án, các vấn đề đặt ra cần quan tâm nghiên

cứu trong thời gian tới như sau:

1. Xây dựng các chiến lược học khác nhau thông qua các độ đo trong việc quyết

định khối nào nên phân hoạch trước. So sánh các chiến lược học với nhau.

2. Xây dựng các module học khái niệm trong logic mô tả với các ngữ cảnh khác

nhau như là một API cho phép tích hợp vào các hệ thống khác.

3. Nghiên cứu các thuật toán học nửa giám sát, học không giám sát, học theo xác

suất cho các cở sở tri thức trong logic mô tả.

4. Nghiên cứu khả năng học chính xác khái niệm cho các logic mô tả khác nhau.

TÀI LIỆU THAM KHẢO

[1] L. Badea and S.-H. Nienhuys-Cheng. A refinement operator for description logics. In Proceedings of the 10th International Conference on Inductive Logic Program- ming, ILP’2000, pages 40–59. Springer-Verlag, 2000.

[2] P. Blackburn, J. van Benthem, and F. Wolter. Handbook of Modal Logic. Elsevier

Science, 2006.

[3] R. Cattral, F. Oppacher, and D. Deugo. Evolutionary data mining with automatic

rule generalization, 2002.

[4] W. W. Cohen and H. Hirsh. Learning the Classic description logic: Theoretical and experimental results. In Proceedings of KR’1994, pages 121–133, 1994.

[5] A. Divroodi, Q.-T. Ha, L. A. Nguyen, and H. S. Nguyen. On C-learnability in description logics. In Proceedings of ICCCI’2012 (1), volume 7653 of LNCS, pages 230–238. Springer, 2012.

[6] A. R. Divroodi and L. A. Nguyen. On bisimulations for description logics. Inf.

Sci., 295:465–493, 2015.

[7] N. Fanizzi, C. d’Amato, and F. Esposito. DL-FOIL concept learning in description logics. In Proceedings of ILP’2008, LNCS, pages 107–121. Springer-Verlag, 2008.

[8] M. Frazier and L. Pitt. Classic learning. Machine Learning, 25(2-3):151–193,

1996.

[9] L. Iannone, I. Palmisano, and N. Fanizzi. An algorithm based on counterfactuals for concept learning in the semantic web. Applied Intelligence, 26(2):139–159, 2007.

[10] J. Lehmann and P. Hitzler. Concept learning in description logics using refinement

operators. Machine Learning, 78(1-2):203–250, 2010.

[11] L. A. Nguyen. An efficient tableau prover using global caching for the description

logic ALC. Fundam. Inform., 93(1-3):273–288, 2009.

[12] L. A. Nguyen. Cut-free exptime tableaux for checking satisfiability of a knowledge base in the description logic ALCI. In Proceedings of ISMIS’2011, volume 6804 of LNCS, pages 465–475. Springer-Verlag, 2011.

[13] L. A. Nguyen. A tableau method with optimal complexity for deciding the de- In Proceedings of ICCSAMA’2013 (1), volume 479 of

scription logic SHIQ. Studies in Computational Intelligence, pages 331–342. Springer, 2013.

In Rough Sets and

[14] L. A. Nguyen and A. Sza(cid:32)las. Logic-based roughification. Intelligent Systems (1), pages 517–543. Springer, 2013.

[15] Z. Pawlak. Information systems theoretical foundations. Information Systems,

6(3):205–218, 1981.

[16] P. Sen, G. M. Namata, M. Bilgic, L. Getoor, B. Gallagher, and T. Eliassi-Rad. Collective classification in network data. AI Magazine, 29(3):93–106, 2008.

[17] J. van Benthem. Modal Logic for Open Minds. Center for the Study of Language

and Inf, 2010.

DANH MỤC CÁC CÔNG TRÌNH CỦA TÁC GIẢ

1. T.-L. Tran, Q.-T. Ha, T.-L.-G. Hoang, L. A. Nguyen, H. S. Nguyen, and A. Sza(cid:32)las. Concept learning for description logic-based information systems. In Pro- ceedings of the 2012 Fourth International Conference on Knowledge and Systems Engineering, KSE’2012, pages 65–73. IEEE Computer Society, 2012. (ISBN: 978- 1-4673-2171-6)

2. Q.-T. Ha, T.-L.-G. Hoang, L. A. Nguyen, H. S. Nguyen, A. Sza(cid:32)las, and T.-L. Tran. A bisimulation-based method of concept learning for knowledge bases in description logics. In Proceedings of the Third Symposium on Information and Communication Technology, SoICT’2012, pages 241–249. ACM, 2012. (ISBN: 978-1-4503-1232-5)

3. Trần Thanh Lương, Hoàng Thị Lan Giao. Áp dụng độ đo entropy để phân hoạch khối cho các hệ thống thông tin dựa trên logic mô tả. Kỷ yếu Hội thảo quốc gia lần thứ XV: Một số vấn đề chọn lọc của Công nghệ Thông tin và Truyền thông, trang 11–18, Nhà xuất bản Khoa học và Kỹ thuật, 2013.

4. T.-L. Tran, Q.-T. Ha, T.-L.-G. Hoang, L. A. Nguyen, and H. S. Nguyen. Bisimulation- based concept learning in description logics. In Proceedings of CS&P’2013, pages 421–433. CEURWS.org, 2013. (ISBN: 978-83-62582-42-6)

5. T.-L. Tran, L. A. Nguyen, and T.-L.-G. Hoang. A domain partitioning method for bisimulationbased concept learning in description logics. In Proceedings of ICCSAMA’2014, volume 282 of Advances in Intelligent Systems and Computing, pages 297–312. Springer International Publishing, 2014. (ISBN: 978-3-319-06569- 4)

6. T.-L. Tran, Q.-T. Ha, T.-L.-G. Hoang, L. A. Nguyen, and H. S. Nguyen. Bisimulation- based concept learning in description logics. Fundam. Inform., Vol. 133, No. 2-3, pages 287–303, 2014. (ISSN: 0169-2968)

7. T.-L. Tran and T.-L.-G. Hoang. Entropy-based measures for partitioning the domain of an interpretation in description logics. Journal of Science, Hue Uni- versity, Vol. 98, No. 8, pages 97–101, 2014. (ISSN: 1859-1388)

8. T.-L. Tran, L. A. Nguyen, and T.-L.-G. Hoang. Bisimulation-based concept learn- ing for information systems in description logics. Vietnam Journal of Computer Science, Vol. 2, pages 149–167, 2015. (ISSN: 2196-8888 (print version); ISSN: 2196-8896 (electronic version))