ĐẠI HỌC QUỐC GIA TP. HCM
TRƯỜNG ĐẠI HỌC BÁCH KHOA TP.HCM
NGUYỄN CHÁNH THÀNH
XÂY DỰNG MÔ HÌNH MỞ RỘNG TRUY VẤN
TRONG TRUY XUẤT THÔNG TIN VĂN BẢN
LUẬN ÁN TIẾN SĨ KỸ THUẬT
TP.HỒ CHÍ MINH – 2010
ĐẠI HỌC QUỐC GIA TP. HCM
TRƯỜNG ĐẠI HỌC BÁCH KHOA TP.HCM
NGUYỄN CHÁNH THÀNH
XÂY DỰNG MÔ HÌNH MỞ RỘNG TRUY VẤN

TRONG TRUY XUẤT THÔNG TIN VĂN BẢN
Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số: 62.48.01.01
LUẬN ÁN TIẾN SĨ KỸ THUẬT
NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS.TS. PHAN THỊ TƯƠI
TP.HỒ CHÍ MINH – 2010
LỜI CAM ĐOAN
Tôi cam ñoan rằng nội dung của luận án này là kết quả nghiên cứu của bản
thân. Tất cả những tham khảo từ các nghiên cứu liên quan ñiều ñược nêu nguồn gốc
một cách rõ ràng từ danh mục tài liệu tham khảo trong luận án. Những ñóng góp
trong luận án là kết quả nghiên cứu của tác giả ñã ñược công bố trong các bài báo
khoa học trong phần “Các công trình khoa học” của luận án và chưa ñược công bố
trong bất kỳ công trình khoa học nào khác.
Tác giả luận án
Nguyễn Chánh Thành
LỜI CẢM ƠN
Trong quá trình hoàn thành luận án này, tôi ñã ñược các thầy cô nơi cơ sở
ñào tạo giúp ñỡ tận tình, cơ quan nơi công tác tạo mọi ñiều kiện thuận lợi và bạn bè

từ ñầu thập niên 1990 với một số thành công. Trong bài toán mở rộng truy vấn, một
số nhóm nghiên cứu trên thế giới ñã sử dụng ontology WordNet. Một số nhóm khác
ñã phát triển ontology ñể phục vụ nhu cầu mở rộng truy vấn. Những ñịnh hướng ñặc
biệt về cấu trúc ontology cần xây dựng bao gồm ñề xuất về nhóm thành phần lớp,
thể hiện, thuộc tính, hay ñề xuất về nhóm thể hiện, thuộc tính, khái niệm và quan hệ
rời rạc (disjointness), IS-A, và tương ñương (equivalence), hoặc phát triển một mô
hình mới về mạng ngữ nghĩa dựa trên những quan hệ trích dẫn từ WordNet như
quan hệ thượng danh (hypernymy), hạ danh (hyponymy) … cùng một số quan hệ
ñược ñịnh nghĩa thêm như chú giải (gloss), chủ ñề và miền (domain).
Luận án này ñề xuất phương pháp mở rộng truy vấn dựa trên cơ sở bản thể
học (ontology-based query expansion). Để thực hiện mục tiêu trên, luận án phải giải
quyết các vấn ñề chính: (1) ñề xuất cơ sở lý thuyết về các mô hình mở rộng truy vấn
dựa trên ontology; (2) phát triển và huấn luyện ontology bằng phương pháp khai
thác kho ngữ liệu sẵn có và phương pháp rút trích dữ liệu từ WordNet; (3) ñề xuất
phương pháp hoàn thiện và mở rộng truy vấn. Phần thực nghiệm của luận án ñược
tiến hành cho ngôn ngữ tiếng Anh dựa trên nguồn dữ liệu và truy vấn tiếng Anh từ
nguồn TREC (Text REtrieval Conference) trong một số lĩnh vực. Các kết quả thực
nghiệm phản ánh tính khả thi của những phương pháp ñề xuất trong luận án, ñồng
thời cho thấy nhiều triển vọng phát triển của các ñề xuất lý thuyết trong luận án.
MỤC LỤC
M Ụ C L Ụ C i
DANH M Ụ C

CÁC B Ả NG iii
DANH M Ụ C

CÁC HÌNH v
DANH M Ụ C CÁC GI Ả I THU Ậ T

vii

15
2.3 Các nghiên c ứ u v

ề

ontology

19
2.4 Các nghiên c ứ u v

ề

m ở r ộ ng truy v ấ n

23
2.5 Khai thác d ữ li ệ u t ừ WordNet

39
2.6 Tóm l ượ c

44
Chương 3 XÂY DỰNG NỀN TẢNG HỆ THỐNG

46
3.1 Gi ớ i thi ệ u

46
3.2 Bài toán Xây

d ự ng ontology và bài toán Hoàn ch ỉ nh m ở r ộ ng truy v ấ n


100
4.5 C ơ ch ế t ự hu ấ n luy ệ n c ủ a ontology OOMP

107
4.6 Các ứ ng d ụ ng c ủ a ontology và quan h ệ

109
4.7 Tóm l ượ c

110
Chương 5 HOÀN CHỈNH VÀ RÚT GỌN TRUY VẤN

112
5.1 Gi ớ i thi ệ u

112
i
5.2 Hoàn ch ỉ nh và rút g ọ n truy v ấ n

113
5.3 Ki ể m tra c ụ m danh t ừ hoàn ch ỉ nh

114
5.4 T ạ o c ụ m danh t ừ hoàn ch ỉ nh

121
5.5 T ạ o c ụ m danh t ừ rút g ọ n

122

7.3 L ờ i k ế t

172
CÁC CÔNG TRÌNH KHOA H Ọ C C Ủ A TÁC GI Ả

174
TÀI LI Ệ U THAM KH Ả O

177
i
Phụ lục A. Tóm lược về WordNet a
Phụ lục B. Cấu trúc cụm danh từ tiếng Anh c
Phụ lục C. Danh mục từ loại tiếng Anh g
Phụ lục D. Danh mục luật sinh dạng cụm danh từ của văn phạm tiếng Anh xây

dựng dựa trên TreeBank i
Phụ lục E. Tính chất ảnh-tạo ảnh trong toán học o
Phụ lục F. Cấu trúc ñịnh dạng tài liệu TREC p
Phụ lục G. Tổ chức cơ sở dữ liệu của thực nghiệm trong luận án s
ii
DANH MỤC CÁC BẢNG
Bảng 3.1. Danh sách mã lỗi quy ước
57
Bảng 3.2. Các trường hợp liên kết giữa q và q’ ñể tính ℘(q | q' )
63
Bảng 3.3. Các trường hợp liên kết giữa q và q’ ñể tính ℘(q')
63
Bảng 3.4.Tập luật sinh tiếng Anh liên quan cụm danh từ (nguồn [2])
67
Bảng 3.5. Danh sách mẫu cơ bản ñặc tả cụm danh từ

106
Bảng 4.8. Các thống kê cho dữ liệu huấn luyện

106
Bảng 4.9. Dữ liệu bổ sung tạo bởi giải thuật A-KBT

108
Bảng 5.1. Thống kê về thời gian thực thi của giải thuật CNPV

117
Bảng 5.2. Các trường hợp xử lý trong giải thuật CNPV theo dạng lỗi

117
Bảng 5.3. Các trường hợp xử lý trong giải thuật CNPV theo dạng lỗi và mẫu

118
Bảng 5.4. Số liệu thống kê các phần tử phân tích trung gian

120
Bảng 5.5. Thống kê về thời gian thực thi của giải thuật NPC

129
Bảng 5.6. Thống kê các trường hợp xử lý trong giải thuật NPC theo dạng lỗi

130
Bảng 5.7. Thống kê các trường hợp xử lý trong giải thuật NPC theo dạng mẫu

130
Bảng 5.8. Thống kê các phần tử phân tích trung gian của giải thuật NPC


Bảng 6.1. Thống kê về thời gian thực thi của giải thuật SNPE

148
Bảng 6.2. Thống kê các trường hợp xử lý trong giải thuật SNPE theo dạng lỗi

148
Bảng 6.3. Thống kê các phần tử phân tích trung gian của giải thuật SNPE

149
Bảng 6.4. Kết quả thực nghiệm của giải thuật CNPG trên dữ liệu trung gian của giải thuật

SNPE

149
Bảng 6.5. Phân tích kết quả thực nghiệm của giải thuật SNPE

151
Bảng 6.6. So sánh kết quả của phương pháp tìm kiếm thô và SNPE

153
Bảng 6.7. Thống kê số liệu thực nghiệm trong giải thuật SIC

160
Bảng 6.8. Số liệu chi tiết của tập si_TermLink tạo ra từ giải thuật SIC

161
Bảng 6.9. Thống kê kết quả trong tập si_TermLink tạo ra từ giải thuật SIC

161
Bảng 6.10. So sánh kết quả thực nghiệm 1

Hình 3.14. Tỉ lệ chọn lọc cụm danh từ hợp lệ theo chiều dài cụm danh từ 85
Hình 3.15. Kết quả rút trích cụm danh từ hợp lệ trong huấn luyện 85
Hình 3.16. Tổ chức lưu trữ cụm danh từ rút trích từ các nguồn dữ liệu 86
Hình 3.17. Phân bổ cụm danh từ trong tập TRAINING_DATA theo dạng mẫu 86
Hình 3.18. Phân bổ cụm danh từ trong tập TEST_DATA theo các nhóm mẫu 87
Hình 4.1. Cấu trúc mức luận lý của ontology OOMP 91
Hình 4.2. Cấu trúc ontology OOMP về tổ chức cơ sở dữ liệu quan hệ 91
Hình 4.3. Đặc tả luận lý cho cấu trúc ontology OOMP 92
Hình 4.4. Các phương pháp huấn luyện ontology OOMP 95
Hình 4.5. Phương pháp huấn luyện dựa trên kho ngữ liệu 95
Hình 4.6. Quan hệ R
m
ñược xây dựng từ quan hệ holonymy trong WordNet 101
11
Hình 4.7. Quan hệ R
m
ñược xây dựng từ quan hệ meronymy trong WordNet

101
Hình 4.8. Quan hệ R
p
ñược xây dựng từ quan hệ attribute trong WordNet

101
Hình 4.9. Quan hệ R
m
ñược xây dựng từ quan hệ similar trong WordNet

101
Hình 4.10. Quan hệ R


132
Hình 5.6. Thống kê số lượng kết quả thực nghiệm theo nguồn dữ liệu

133
Hình 5.7. Cài ñặt chức năng tìm kiếm cho truy vấn sinh từ giải thuật NPMR

138
Hình 5.8. Thống kê số liệu các ñộ ño theo nguồn dữ liệu

139
Hình 5.9. Thống kê số lượng kết quả thực nghiệm theo nguồn dữ liệu

140
Hình 6.1. Mô hình hệ thống mở rộng truy vấn với ñộng cơ tìm kiếm thông tin

143
Hình 6.2. Cài ñặt chức năng tìm kiếm cho truy vấn sinh từ giải thuật SNPE

150
Hình 6.3. Thống kê số lượng kết quả thực nghiệm theo nguồn dữ liệu

152
Hình 6.4. Thống kê số liệu các ñộ ño theo nguồn dữ liệu

152
Hình 6.5. Minh họa tính chất (6.1)

154
Hình 6.6. Ứng dụng tính chất (6.1) vào mở rộng kết quả tìm kiếm

Giải thuật 6.3. Tìm kiếm kết hợp 158
vii
DANH MỤC CÁC TỪ VIẾT TẮT
STT Từ viết tắt Diễn giải tiếng Anh Diễn giải tiếng Việt
1 A-KBT Auto
Knowledge Base
Training
2 CB-KBT Corpus-
Based Knowledge
Base Training
Huấn luyện ontology tự ñộng
Huấn luyện ontology dựa trên kho
ngữ liệu
3 CL Concept Lattice Lưới khái niệm
4 CLIR Cross-
Language

Information Retrieval
5 CNPV Complete
Noun Phrase
Verification
6 CREOLE Collection
of
REusable
Object for Language
Engineering
Truy xuất thông tin xuyên ngôn ngữ
Kiểm tra tính hoàn chỉnh của cụm
danh từ
Tập ñối tượng khả tái sử dụng cho

18 NPRM Noun Phrase
Member
Reduction
Rút gọn thành phần cụm danh từ
viii
19 OMP Object-Member-Property Đối
tượng-Thành phần-Tính chất
20 OOMP Ontology
of Object-
Member-Property
Cơ sở tri thức của Đối tượng-Thành
phần-Tính chất
21 QEM Query Expansion ModelMô hình mở
rộng truy vấn
22 SIC Semantic Index Creation Tạo
chỉ mục hướng ngữ nghĩa
23 SNPE Similar Noun
Phrase
Expansion
Mở rộng cụm danh từ tương ñương
24 TREC Text REtrieval Conference Hội
nghị về Truy xuất văn bản
25 WB-KBT WordNet-Based
Knowledge
Base Training
Huấn luyện ontology dựa trên
WordNet
viii
Chương 1


tập các từ khóa.
− Yêu cầu thông tin (truy vấn) của người sử dụng thường chỉ bao gồm một vài
từ khóa cốt lõi, không thể hiện ñủ ngữ nghĩa cần thiết.
− Người sử dụng không cung cấp ñủ thông tin truy vấn cần thiết cho ñộng cơ
tìm kiếm.
− Động cơ tìm kiếm thông tin hoạt ñộng dựa trên cơ chế so trùng từ khóa và
chưa quan tâm ñúng mức ñến yếu tố ngữ nghĩa trong tương tác và hỗ trợ
người dùng.
− Các ñộng cơ tìm kiếm hiện có thường hỗ trợ chính cho tiếng Anh, nhưng
thiếu công cụ trợ giúp cho ngôn ngữ khác …
Điều này dẫn ñến tình trạng:
− Người sử dụng phải dành một lượng thời gian khá lớn ñể ñọc hiểu và chọn
lọc lại các thông tin ñể có những kết quả mong muốn.
− Người sử dụng gặp khó khăn trong việc diễn ñạt nội dung của vấn ñề cần
tìm.
− Người sử dụng không nhận ñược một kết quả trả lời trọn vẹn hoàn chỉnh (dù
chỉ cần ở mức tóm lược ngắn gọn) như mong muốn về một vấn ñề cần tìm.
− Thiếu một hệ thống tìm kiếm thông tin nhanh và linh hoạt ñể không chỉ có
thể tìm các thông tin trong tài liệu tiếng Anh (như truyền thống) và tiếng Việt
theo cơ chế so trùng từ khóa, mà còn có thể trả lời các câu hỏi của người sử
dụng (trong phạm vi xác ñịnh cho tiếng Việt).
− Hệ thống chưa thực sự ñủ mạnh ñể nhận biết ngữ nghĩa của truy vấn.
Từ các phân tích trên, chúng ta nhận thấy nguyên nhân chính là các hệ thống
tìm kiếm thông tin chưa ñủ mạnh nên kết quả ñưa ra không thể hỗ trợ người dùng
như mong ñợi. Truy vấn của người dùng cũng chưa phản ánh ñầy ñủ ngữ nghĩa ñể
hỗ trợ cho các quá trình tìm kiếm và truy xuất thông tin ñược tốt hơn. Vì vậy, việc
bổ sung ngữ nghĩa vào truy vấn ban ñầu của người dùng là yêu cầu cần thiết.
Một bài toán kinh ñiển trong lĩnh vực Truy xuất thông tin là Mở rộng truy
vấn. Đó là quá trình bổ sung một số từ vào truy vấn của người dùng nhằm tạo ra các
truy vấn mới tương ñồng ngữ nghĩa. Bài toán này là vấn ñề ñược quan tâm vì nó có

hai ñịnh nghĩa về ngữ cảnh. Định nghĩa thứ nhất theo ngôn ngữ học “ngữ cảnh là
các phần của bài luận bao quanh từ hay ñoạn văn và có thể làm sáng tỏ nghĩa của
nó”
b
. Định nghĩa thứ hai dựa trên tình huống “các ñiều kiện tương quan trong ñó
một ñiều gì ñó tồn tại hay xảy ra”
c
. Từ ñó, một nhận ñịnh chung là thông qua
tương tác của người dùng lên hệ thống truy xuất thông tin, ngữ cảnh tương ứng sẽ
bao gồm những thông tin liên quan ñến những hành ñộng, những quyết ñịnh của
người dùng.
Ngữ cảnh trong truy xuất thông tin bao gồm nhiều vấn ñề trong ñó có mở
rộng truy vấn. Một khó khăn là làm sao biểu diễn ñược nghĩa của truy vấn bằng các
thuật ngữ (term) một cách chính xác. Do vậy, mở rộng truy vấn cho phép người
dùng thực hiện tìm kiếm thông tin bằng truy vấn mới có các thuật ngữ là sự biến ñổi
hình thái của thuật ngữ ban ñầu và (hoặc) một số thuật ngữ mới ñược thêm vào truy
vấn nhờ kết quả khử nhập nhằng nghĩa của truy vấn ban ñầu. Nhiều phương pháp
tiếp cận khác nhau ñược ñề xuất hướng ñến việc mở rộng truy vấn. Trong ñó, có
nhiều nghiên cứu hướng ñến việc sử dụng ontology ñể hỗ trợ suy luận ngữ cảnh cho
các truy vấn nhập nhằng. Các khái niệm trong ontology ñược dùng ñể khử nhập
nhằng ngữ nghĩa của từ và hỗ trợ ñể mở rộng truy vấn. Việc mở rộng truy vấn ñạt
thành công ở một mức ñộ nhất ñịnh nhưng vẫn còn nhiều vấn ñề cần cải thiện về kỹ
b
Nguyên văn: “the parts of a discourse that surround a word or passage and can throw light on its meaning”
c
Nguyên văn: “the interrelated conditions in which something exists or occurs”
thuật, giao diện hoặc giải thuật ñể xác ñịnh ngữ nghĩa một cách chính xác hơn từ ñó

cải tiến kết quả truy vấn.
Từ tầm quan trọng về tính hiệu quả của quá trình truy xuất thông tin (trên

(b) Nghiên cứu và phát triển cấu trúc tổ chức ontology cùng giải pháp huấn

luyện tạo
dữ liệu ban ñầu nhằm kiểm chứng kết quả nghiên cứu ở (a) và có thể triển

khai
trong thực tế ñể mang lại kết quả truy xuất thông tin tốt hơn.
Như ñịnh hướng nêu trên, phạm vi nghiên cứu của luận án ñược thể hiện
trong hình 1.1 (trong khung ñường gạch ñứt nét).
(A)
Nhập:

Câu truy
vấn
dạng cụm

danh từ
Bộ xử lý
mở rộng
truy vấn
trên cơ sở
kết hợp
với
ontology
Xuất:

Các câu
truy
vấn:
- dạng cụm

e
). Trong phạm vi luận án, dựa trên giải pháp rút trích các từ ñặc trưng cốt lõi
d
Khái niệm ontology còn ñược diễn dịch là “cây phả hệ tri thức” hay “cơ sở tri thức”
e
Tham khảo thêm ñịnh nghĩa 3.10-Truy vấn hoàn chỉnh, mục 3.2.6, chương 3.
cho một câu ([23] [149]), câu truy vấn ban ñầu của người dùng ñược tiền xử lý ñể
loại bỏ các thành phần không quan trọng nhằm giữ lại những thành phần chính thỏa
ñiều kiện truy vấn hoàn chỉnh. Điều ñó sẽ giúp giảm ñược ñộ phức tạp hay dạng
biểu diễn phức hợp của truy vấn, ñồng thời còn giúp ñảm bảo tính duy nhất của
từng thành phần trong truy vấn thỏa ñiều kiện truy vấn hoàn chỉnh.
Mục (B) của hình trên gồm ñộng cơ tìm kiếm thông tin (search engine). Đây
là một bộ phận quan trọng của hệ thống Truy xuất Thông tin (Information
Retrieval). Động cơ tìm kiếm thông tin giải quyết ba vấn ñề cốt lõi là mô hình biểu
diễn văn bản, thuật toán tìm kiếm so trùng từ khóa - ñối sánh ngữ nghĩa tương ứng
với các truy vấn và cơ chế lọc kết quả truy xuất. Hiện tại trên thế giới có những
ñộng cơ tìm kiếm thông tin nổi tiếng như Google, Yahoo, Microsoft Bing … Tuy
nhiên, nghiên cứu của luận án chỉ sử dụng những ñộng cơ này như một công cụ hỗ
trợ việc tìm kiếm thông tin cho truy vấn ñã mở rộng bằng phương pháp xử lý của
luận án và không ñặt mục tiêu nghiên cứu ba vấn ñề nêu trên. Vì vậy luận án ñã
không trình bày ba vấn ñề này.
Mô hình xử lý của luận án (trong mục (A)) chỉ thực hiện việc mở rộng nội
dung của truy vấn nhập nên hoàn toàn không làm ảnh hưởng ñến ba khía cạnh nêu
trên trong quá trình vận hành của ñộng cơ tìm kiếm ở mục (B). Điều này còn cho
thấy phạm vi nghiên cứu của luận án hướng ñến bài toán mở rộng truy vấn dựa trên
ontology và hoàn toàn khác biệt so với ba khía cạnh ñã nêu.
Từ những trình bày trên, các bài toán chính cần giải quyết trong phạm vi
luận án bao gồm:
Bài toán 1 - Xây dựng ontology
OOMP

hệ
R
m
xác ñịnh thành phần ñặc trưng (member) của ñối tượng (object).
R
p
tính chất ñặc trưng (property) của thành phần.
− Các quan hệ xác ñịnh tính chất trội
R
m và R
p
liên quan.
Các phương pháp mà luận án ñề xuất không những có thể áp dụng trong
phạm vi luận án ñể giải quyết Bài toán 1 và Bài toán 2 nêu trên mà còn có thể áp
dụng trong một số lĩnh vực khác ñể tạo ontology cho một miền khái niệm (trong
lĩnh vực xử lý ngôn ngữ tự nhiên). Ngoài ra, từ góc ñộ toán học, việc xây dựng các
lớp ñồng dạng (liên quan ñến nhóm các ñối tượng, nhóm các thành phần ñặc trưng
f
f
và nhóm các tính chất ñặc trưng
g
) từ các quan hệ nêu trên sẽ giúp cho việc phân
loại ñối tượng hiệu quả hơn. Công trình [ii], [iv], [v] và [ix]
h
ñã giới thiệu phương
pháp xác ñịnh các quan hệ cùng ñịnh nghĩa của những khái niệm này.
Phần ñóng góp này sẽ không thực sự ñầy ñủ nếu không có các ñịnh nghĩa
+OB
−IR
+OB+P

h
Tham khảo thêm phần Các công trình khoa học.
MQE
,
MQE
,
MQE
,
MQE
− Kiểm tra tính hoàn chỉnh của cụm danh từ (Complete Noun Phrase
Verification, CNPV)
− Hoàn chỉnh cụm danh từ (Noun Phrase Completion, NPC)
− Mở rộng cụm danh từ tương tự (Similar Noun Phrase Expansion, SNPE)
Mô hình cùng các phương pháp xử lý truy vấn này có thể áp dụng trong Bài
toán 2, cũng như trong các bài toán khác như:
− Kiểm tra tính hoàn chỉnh của cụm danh từ tiếng Anh theo quan ñiểm ngôn
ngữ học tính toán (ứng dụng trong lĩnh vực xử lý ngôn ngữ tự nhiên: truy
xuất thông tin, rút trích thông tin, tóm lược nội dung văn bản).
− Hoàn chỉnh và mở rộng cụm danh từ tương ñương (ứng dụng trong lĩnh vực
xử lý ngôn ngữ tự nhiên: truy xuất thông tin, rút trích thông tin, tóm lược nội
dung văn bản) ….
Các phương pháp và giải thuật liên quan ñến ñóng góp này ñược giới thiệu
trong [ii], [v] và [ix].
* Đóng góp thứ tư: Phương pháp xây dựng chỉ mục hướng ngữ nghĩa
(Semantic Index Creation, SIC) thông qua việc mở rộng cấu trúc chỉ mục ñể lưu trữ
thêm thông tin liên quan ngữ nghĩa ñến ontology xác ñịnh. Đây chính là cầu nối
giúp triển khai những nghiên cứu lý thuyết vào ứng dụng thực tiễn trong lĩnh vực
truy xuất thông tin. Kết quả thu ñược từ phương pháp này tạo tiền ñề cho nhiều
nghiên cứu ứng dụng liên quan ñến truy xuất thông tin. Phương pháp này ñược trình
này trong công trình [iv] và ñược phát triển trong [iii] và [viii].