Đại Học Quốc Gia TP. Hồ Chí Minh
TRƯỜNG ĐẠI HỌC BÁCH KHOA
---------o0o----------
LUẬN VĂN ĐẠI HỌC
XỬ LÝ CÁC CÂU TRUY VẤN VÀ TÌM KIẾM TRÊN
KHO TÀI LIỆU CÓ CHÚ THÍCH NGỮ NGHĨA BẰNG
TIẾNG ANH
Chuyên ngành: Khoa Học Máy Tính
GVHD : Pgs.Ts. Cao Hoàng Trụ
Sinh viên : Nguyễn Trần Đăng Khoa
(50601130)
Tạ Tất Tài
(50602084)
TP. Hồ Chí Minh, tháng 12 – 2010
CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI
TRƯỜNG ĐẠI HỌC BÁCH KHOA
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
Cán bộ hướng dẫn khoa học : PGS.TS. CAO HOÀNG TRỤ
Cán bộ chấm nhận xét 1 :.................................................................................................
Cán bộ chấm nhận xét 2 :.................................................................................................
Luận văn đại học được bảo vệ tại HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN ĐẠI HỌC
TRƯỜNG ĐẠI HỌC BÁCH KHOA, ngày . . . . . tháng . . . . năm . . . . .
LỜI CAM ĐOAN
Tôi cam đoan rằng ngoại trừ các kết quả tham khảo từ các công trình khác như đã ghi rõ trong luận
văn, các công việc trình bày trong luận văn này là do chính tôi thực hiện và chưa có phần nội dung
nào của luận văn này được nộp để lấy một bằng cấp ở trường đại học nào khác.
Ngày..................Tháng..............Năm............
Ký tên
LỜI CẢM ƠN
Trước hết, chúng tôi xin gởi lời cảm ơn chân thành và sâu sắc đến Pgs.Ts. Cao Hoàng Trụ, và kỹ
2.2.2 Đồ thị ý niệm mở rộng...........................................................................................................10
2.3 Tìm thực thể vài tài liệu................................................................................................................11
2.3.1 Câu truy vấn SeRQL [tham khảo
/>2.3.2 Semantic Lucene.....................................................................................................................12
PHÂN TÍCH VẤN ĐỀ VÀ PHƯƠNG PHÁP GIẢI QUYẾT...........................................................14
3.1 Chuyển đổi câu truy vấn với từ để hỏi “How many”..................................................................14
3.2 Chuyển đổi câu truy vấn có tính từ .............................................................................................16
3.3 Chuyển đổi câu truy vấn có tính từ so sánh nhất.........................................................................18
3.4 Chuyển đổi câu truy vấn có tính từ..............................................................................................19
3.5 Chuyển đổi câu truy vấn có tính từ so sánh nhất.........................................................................21
3.5.1 Trường hợp tính từ định tính..................................................................................................21
3.5.2 Trường hợp tính từ định lượng [tham khảo HA]...................................................................21
3.6 Chuyển đổi câu truy vấn có tính từ định lượng so sánh hơn.......................................................22
THIẾT KẾ 24
4.1 Các bước của giải thuật................................................................................................................24
4.1.1 Phân tách câu truy vấn............................................................................................................26
4.1.2 Nhận biết thực thể có tên........................................................................................................26
4.1.3 Nhận biết thực thể không tên.................................................................................................26
4.1.4 Nhận biết tính từ.....................................................................................................................27
4.1.5 Nhận biết từ quan hệ...............................................................................................................27
4.1.6 Xác định lớp của thực thể.......................................................................................................27
4.1.7 Gom các thực thể....................................................................................................................28
4.1.8 Xác định quan hệ ẩn...............................................................................................................29
4.1.9 Xác định loại quan hệ giữa các thực thể................................................................................29
4.1.10 Xoá bỏ quan hệ không phù hợp............................................................................................32
4.1.11 Xác định quan hệ giữa tính từ và thực thể...........................................................................33
4.1.12 Xây dựng đồ thị ý niệm........................................................................................................36
4.2 Tập luật.........................................................................................................................................36
4.2.1 Cấu trúc của hệ thống luật......................................................................................................37
4.2.2 Cấu trúc thành phần điều kiện của luật..................................................................................38
Hình 4.0.8: Lược đồ ánh xạ kiểu quan hệ giữa tính từ và thực thể........................................................35
Hình 4.0.9: Cấu trúc tập thành phần TransformRules và rule................................................................37
Hình 4.0.10: Cấu trúc của thành phần điều kiện luật..............................................................................39
Hình 4.0.11: Ví dụ về thành phần premise..............................................................................................39
Hình 4.0.12: Cấu trúc của thành phần hành động...................................................................................40
Hình 4.0.13: Cấu trúc từ điển quan hệ....................................................................................................40
Hình 4.0.14: Ví dụ một luật hoàn chỉnh..................................................................................................41
Hình 4.0.15: Ví dụ một số thành phần trong từ điển..............................................................................41
Hình 4.0.16: Ví dụ về biểu diễn câu truy vấn “Queried relation”..........................................................45
Hình 4.0.17: Ví dụ về biểu diễn câu truy vấn “Advert / Temporal”.....................................................45
DANH MỤC BẢNG
Bảng 4.1: Bảng thuộc tính thành phần premise......................................................................................38
Bảng 4.2: Mô tả các thuộc tính của thành phần entry.............................................................................41
Bảng 4.3: Kết quả thực nghiệm trên TREC 2002 khi chưa áp dụng phương pháp đề nghị..................43
Bảng 4.4: Kết quả thực nghiệm trên TREC 2002 sau khi áp dụng phương pháp đề nghị....................43
Bảng 4.5: Kết quả thực nghiệm trên TREC 2002 sau khi làm giàu Ontology.......................................44
Bảng 4.6: Bảng tổng kết kết quả cuối cùng đạt được trên tập TREC 2002...........................................46
Bảng 4.7: Kết quả thực nghiệm trên TREC 2007 khi chưa áp dụng phương pháp đề nghị..................47
Bảng 4.8: Kết quả thực nghiệm trên TREC 2007 sau khi áp dụng phương pháp đề nghị.....................47
Bảng 4.9: Kết quả thực nghiệm trên TREC 2007 sau khi làm giàu Ontology.......................................48
Bảng 4.10: Bảng tổng kết kết quả cuối cùng đạt được trên tập TREC 2007.........................................49
23
CHƯƠNG 1.....................................................................
TỔNG QUAN
1.1 Giới thiệu
Kể từ khi ra đời đến nay, World Wide Web (WWW) đã làm thay đổi rất nhiều cách con người
trao đổi và tiếp cận với thông tin, tri thức. Và đối với nền kinh tế tri thức hiện nay, tầm quan trọng của
WWW càng lớn hơn. Điều đó đặt ra yêu cầu là: phải làm sao để quá trình khai thác tri thức từ WWW
đạt được hiệu suất tối ưu. Muốn vậy, một giải pháp là phải tự động hóa được quá trình đó; nói cách
khác, máy móc phải có khả năng khai thác thông tin trên WWW với một độ chính xác cao.
− Câu có thể hàm chứa những mối quan hệ ngầm giữa các đối tượng, mà không được biểu hiện
ra bằng các từ ngữ biểu diễn quan hệ, vì các mối liên hệ này được con người ngầm thỏa thuận
trên một nền tảng kiến thức chung.
− Một cách thường xuyên, câu truy vấn bằng ngôn ngữ tự nhiên không chặt về ngữ pháp, mà
thường được dùng ở dạng thông dụng không “chuẩn” ngữ pháp.
Tuy có nhiều khó khăn như đã kể trên, nhưng hiện nay các nhóm nghiên cứu về lĩnh vực web ngữ
nghĩa đã đạt được những tiến bộ đáng kể. Và việc xây dựng một động cơ tìm kiếm theo ngữ nghĩa là
khả thi, có thể thành công với những câu truy vấn không quá phức tạp. Vì vậy, đề tài này sẽ ứng dụng
các thành tựu đó để xây dựng một động cơ tìm kiếm cho phép người dùng truy vấn bằng ngôn ngữ tự
nhiên, và trả về tài liệu chứa nội dung cần tìm.
23
1.2 Mục tiêu và phạm vi
Liên quan đến mục tiêu tạo ra một công cụ tìm kiếm dựa trên nền tảng Web ngữ nghĩa, đã có
nhiều nghiên cứu được biết đến. Các nghiên cứu này sử dụng nhiều hình thức khác nhau cho câu truy
vấn đầu vào[tham khảo CDT], như:
− Hình thức đồ thị: người sử dụng thao tác trực tiếp trên đồ thị để thực hiện truy vấn.
− Hình thức mẫu câu được dựng sẵn: người sử dụng sẽ lựa chọn trong số những mẫu câu truy
vấn được xây dựng sẵn, lưu trong hệ thống, để thực hiện truy vấn.
− Từ khóa bằng ngôn ngữ tự nhiên.
− Hình thức câu đầy đủ: người sử dụng đưa và một câu ngôn ngữ tự nhiên bất kỳ để thực hiện
truy vấn.
Các hình thức biễu diễn này, nếu càng gần với ngôn ngữ tự nhiên thì lại càng khó xử lý đối với
máy tính. Tuy nhiên, nếu càng gần với ngôn ngữ tự nhiên thì càng dễ tiếp cận đối với người sử dụng.
Hiển nhiên, người sử dụng mong muốn nhất là cho phép nhập vào một câu truy vấn dùng ngôn ngữ tự
nhiên.
Về phương pháp biên dịch câu truy vấn ngôn ngữ tự nhiên, toát lên từ các nghiên cứu là 2 hướng
tiếp cận:
− Phân tích cú pháp: cách này dựa vào việc phân tích cú pháp của câu truy vấn để dịch ra ngôn
ngữ khác mà máy tính hiểu được. Vì vậy phụ thuộc rất chặt vào cú pháp, bất kỳ lỗi cú pháp
nào cũng dẫn đến biên dịch thất bại. Ngoài ra, sẽ khó khăn khi chuyển đổi, sử dụng ngôn ngữ
Hiện nay, mô-đun nhận biết thực thể của VN-KIM Search không thể dùng cho tiếng Anh. Nên, ở
bước nhận biết thực thể, đề tài sẽ sử dụng công cụ sẵn có, và giả sử là quá trình này hoàn toàn chính
xác. Đề tài cũng không giải quyết vấn đề về quan hệ 3 ngôi trong [HA], vì việc đó liên quan tới việc
mở rộng, “làm mịn” Ontology, là một bài toán khác.
1.3 Kết quả đạt được
Đề tài đã xây dựng được 1 hệ thống tìm kiếm dựa trên ngữ nghĩa cho tiếng Anh, với các dạng câu
truy vấn như đã trình bày ở trên.
Đồng thời, mở rộng thêm một số khả năng khi xử lý những câu truy vấn dạng phức tạp. Đầu tiên
là khả năng đề xuất đồ thị ý niệm khả áp dụng ngay cả khi quan hệ với tính từ trong câu truy vấn
không có trong cơ sơ tri thức. Mục đích là làm ta có thể đánh giá tính chính xác của quá trình “hiểu”
câu truy vấn của hệ thống mà không bị quá lệ thuộc vào cơ sơ tri thức. Ví dụ như sau:
“What is the longest dam in the U.S.?” Mặc dù quan hệ giữ “dam” và “long” không có trong
cơ sơ tri thức, nhưng ta vẫn có thể cung cấp đồ thị ý niệm cho người dùng (với quan hệ “ảo” được vẽ
màu xanh lá).
Hình 1.1 Đồ thị có đề xuất quan hệ không tồn tại trong cơ sở tri thức
Ngoài ra, để truy xuất được tài liệu, thì chỉ ngừng lại ở đồ thị là chưa đủ, cần phải chuyển đồ thị
đó sang ngôn ngữ SeRQL, là ngôn ngữ dùng để truy xuất cơ sở tri thức ngữ nghĩa. Luận văn này đã
đề xuất và hiện thực cách thức chuyển từ đồ thị ý niệm của những câu truy vấn dạng này sang truy
vấn SeRQL để lấy về thực thể (entity) cần tìm.
23
Luận văn cũng đề xuất và hiện thực cách xử lý câu truy vấn có chứa dạng so sánh hơn của tính từ
định lượng. Các câu truy vấn có so sánh hơn với một hằng số, hoặc so sánh hơn với một thực thể, như
“What dam in the U.S. is higher than 1200 meters?”, “What dam is higher than Dworshak in the
U.S.?” cũng đã được chuyển sang đồ thị ý niệm, rồi chuyển sang câu truy vấn SeRQL tương ứng.
1.4 Cấu trúc luận văn
Chương 1 đã trình bày khái quát động cơ, mục đích, ý tưởng thực hiện đề tài. Tiếp theo sau
Chương 1 là phần trình bày chi tiết về ý tưởng và phương pháp của chúng tôi để đạt được mục đích
đã đề ra.
Chương 2 trình bày những nghiêu cứu và hệ thống liên quan đến việc chuyển đổi câu truy vấn
tiếng Anh sang đồ thị ý niệm. Mục 2.1 trình bày phương pháp rút trích quan hệ trong câu truy vấn. Sơ
đặc điểm từ vựng, đặc điểm cú pháp và đặc điểm ngữ nghĩa. Những phương pháp này rất hiệu
quả cho việc rút trích quan hệ. Tuy nhiên, vấn đề gặp phải là các đặc điểm phải được mô tả thủ
công và cấu trúc thông tin trong cây cú pháp không được bảo toàn trong cây đặc điểm (Là cây
biểu diễn các đường nối không kết thúc giữa hai thực thể trong cây cú pháp).
• Các phương pháp dựa trên kernel chú trọng vào việc sử dụng các cây kernel riêng lẻ để
khai thác đặc điểm cấu trúc. Hệ thống [19] xây dựng một quan hệ kernel trên cây cú pháp cho
23
việc rút trích quan hệ. Kernel so trùng các node từ gốc cho tới lá một cách đệ quy theo từng lớp
từ trên xuống.
Tuy nhiên các nghiên cứu trên chỉ chú trọng vào rút trích quan hệ giữa các thực thể có tên đã biết.
Để xây dựng được đồ thị ý niệm, ngoài việc rút trích quan hệ giữa các thực thể có tên còn phải rút
trích quan hệ giữa các thực thể không tên với nhau, hay các quan hệ giữa các thực thể có tên với thực
thể không tên.
2.2 Đồ thị ý niệm (Conceptual Graph)
2.2.1 Sơ lược về đồ thị ý niệm
Đồ thị ý niệm là một hình thức biểu diễn logic (logical formalism) vừa có tính trực quan, vừa có
sự chính xác. Về hình thức, đây là một đồ thị tạo ra bởi các đỉnh và các cạnh (có thể có hướng hoặc
không có hướng). Nhờ sử dụng cách biểu diễn đồ họa trực quan đó, đồ thị cho phép con người nhanh
chóng có được một cái nhìn tổng quan, dễ nắm bắt ý nghĩa. Về nội dung, đồ thị ý niệm có thể được
ánh xạ trực tiếp sang logic vị từ (predicate logic). Nhờ đó, có thể biểu diễn ngữ nghĩa một cách chính
xác, giữ được tính chính xác về mặt logic. Với những đặc điểm đó, đồ thị ý niệm vừa dễ tiếp cận đối
với con người, vừa khả xử lý đối với máy tính.
Và đồ thị ý niệm đã được dùng như là một hình thức biểu diễn tri thức, là một ngôn ngữ trung
gian cho việc chuyển đổi qua lại giữa hình thức biểu diễn hướng máy tính và ngôn ngữ tự nhiên. “Tim
Berners Lee, người phát minh của WWW, kết luận rằng các CG có thể dễ dàng tích hợp với Semantic
Web. Nó cũng được chỉ ra là có một ánh xạ chặt với ngôn ngữ RDF.” Nó cũng được chỉ ra trong là có
một ánh xạ chặt giữa CG và ngôn ngữ RDF (ko hiểu đoạn này >.<).” [tham khao HA].
“Trong bài báo đầu tiên công bố liên quan tới đồ thị ý niệm, Sowa đã định nghĩa đồ thị ý niệm
như sau: Chỗ này ta nghĩ chỉ cần nói: Sowa đã định nghĩa dtyn trong 1 bài báo của mình:… rồi trích
dẫn đoạn định nghĩa thôi. Ghi như vầy thì ghi là tk HA được, còn ghi như T thì phải ghi là tk bài báo
Đồ thị ý niệm được sử dụng để kiểm tra tính chính xác của quá trình dịch câu truy vấn trong đề
tài, bên cạnh các tham chiếu xác định và tham chiếu tổng quát, được bổ sung thêm tham chiếu nghi
vấn. Tham chiếu nghi vấn biểu diễn cho thực thể được truy vấn trong câu. Một đồ thị ý niệm truy vấn
là một đồ thị ý niệm mà các tham chiếu có thể là tham chiếu xác định, tham chiếu tổng quát hoặc là
tham chiếu nghi vấn được biểu diễn bằng dấu “?”.
2.2.2 Đồ thị ý niệm mở rộng
Đồ thị ý niệm mở rộng [tham khảo HA] là đồ thị ý niệm có sử dụng thêm một khái niệm đặc biệt,
gọi là đỉnh truy vấn con. Đó là một đỉnh khái niệm, nhưng có kiểu khái niệm riêng, và tham chiếu đến
thực thể của nó là một đồ thị ý niệm khác. Tức là, bên trong đỉnh truy vấn con là nội dung một đồ thị
ý niệm truy vấn tri thức. Đỉnh truy vấn con sẽ được biểu diễn bằng hình chữ nhật vát góc. Đỉnh truy
vấn con được biểu diễn bằng hình chữ nhật tròn góc (Ta nghĩ chỗ này mình nên nói: trong tài liệu
(hay luận văn) này, đỉnh truy vấn con được biểu diễn bằng hình chữ nhật vát góc, vì các ví dụ sau này
đâu phải tròn góc). Ta xét một ví dụ minh họa: ta có câu truy vấn lồng nhau như sau: “Tìm tên của
những giảng viên có tên trùng với tên của những giảng viên tại trường Đại học Bách Khoa”. Câu truy
vấn này sẽ được biểu diễn như sau:
[hình tham khảo HA]
Trong đề tài [tham khảo HA], đỉnh truy vấn con này được sử dụng phần lớn trong các phương
pháp đề xuất sẽ được bàn đến ở những phần tiếp theo.
23
2.3 Tìm thực thể vài tài liệu
Đề tài này biến đổi từ đồ thị ý niệm sang ngôn ngữ truy vấn SeRQL để truy vấn thực thể trong cơ
sở tri thức. Thực thể tìm được sẽ dùng để tìm tài liệu trên Semantic Lucene.
2.3.1 Câu truy vấn SeRQL [tham khảo
/>n-numerical-comparisons]
SeRQL (Sesame RDF Query Language) là một ngôn ngữ truy vấn cơ sở tri thức. Tương tự như
SQL được sử dụng làm ngôn ngữ truy vấn trên các cơ sở dữ liệu quan hệ, SeRQL được sử dụng trên
các cơ sở dữ liệu viết bằng ngôn ngữ RDF.
Trong SeRQL, có 2 loại câu truy vấn: một loại sẽ trả về một bảng các giá trị (một tập các ràng
buộc (binding) giữa biến với giá trị, tương tự như khi truy vấn với SQL), loại còn lại sẽ trả về một đồ
thị RDF (RDF graph). Trong đề tài này chỉ sử dụng loại thứ nhất, gọi là select queries (phiên bản
FROM {Country} ex:population {Population}
ORDER BY Population DESC
Ngoài ra, SeRQL cũng hỗ trợ 3 toán tử UNION, INTERSECT và MINUS để thực hiện kết hợp,
giao và loại trừ các tập kết quả. Ví dụ [tham khảo
/>SELECT title
FROM {book} dc10:title {title}
UNION
SELECT title
FROM {book} dc11:title {title}
Đề tài sẽ sử dụng các toán tử tập hợp này vào việc giải quyết các câu truy vấn có liên từ luận lý.
2.3.2 Semantic Lucene
Lucene: là một thư viện mã nguồn mở viết bằng Java, dùng để phân tích, hỗ trợ đánh chỉ mục và
tìm kiếm thông tin với hiệu suất cao. Lucene được phát triển đầu tiên bởi Doug Cutting, và ra mắt vào
23
tháng 3/2000. Hiện tại Lucene đang được Apache phát triển và duy trì. Lucene không phải một ứng
dụng, mà chỉ là một công cụ đặc tả API cần thiết cho một search engine. Ngoài phiên bản ban đầu
bằng Java, hiện nay còn có Lucene cho các ngôn ngữ khác: .NET, C++, Perl…
VN-KIM Semantic Lucene (S-Lucene): là hiện thực mở rộng của Lucene cho tìm kiếm ngữ nghĩa.
VN-KIM S-Lucene là một thư viện phần mềm trong hệ thống VN-KIM, có vai trò quan trọng trong
việc quản lý, truy hồi các thực thể hay các tài liệu đã được chú giải.
Khác biệt chủ yếu giữa Lucene và S-Lucene đó là Lucene đánh chỉ mục và tìm kiếm trên từ khóa,
trong khi đó S-Lucene mở rộng cho đánh chỉ mục và tìm kiếm theo thực thể.
Đầu vào của S-Lucene là các bộ ba (name/class/ID) nhận được từ quá trình tìm kiếm thực thể. S-
Lucene trả về các tài liệu tương ứng với các bộ ba đó.
23
CHƯƠNG 3
PHÂN TÍCH VẤN ĐỀ VÀ PHƯƠNG PHÁP
GIẢI QUYẾT
3.1 Chuyển đổi câu truy vấn với từ để hỏi “How many”
Về cơ bản, chúng tôi thấy rằng việc biểu diễn các câu truy vấn hỏi về số lượng (Có từ hỏi là
năng thể hiện thuộc tính famous của các người mẫu.
• Giải pháp 1: Định nghĩa lớp FAMOUSMODEL, ví dụ, đối với những người mẫu mà nổi
tiếng. Nó sẽ tạo ra nhiều lớp con của các người mẫu cho những độ khác nhau của thang đo độ
nổi tiếng.
• Giải pháp 2: Định nghĩa kiểu quan hệ FAMEPROPERTY có miền lớp là MODEL và
range lớp là STRING. Cách này gây ra vấn đề của việc so trùng các giá trị String sau đó.
Ở giải pháp thứ nhất nêu trên, ta thấy giải pháp này sẽ dẫn đến bùng nổ số lượng lớp mới phải
định nghĩa. Đặc biệt một vấn đề nảy sinh là việc đưa ra các thang đo để có thể định lượng được các
tính từ. Điều này chỉ có thể giải quyết được trong một số trường hợp đối với các tính từ như “tall”,
“high”… Ví dụ, ta có thể quy ước một ngôi nhà được gọi là cao khi kích thước chiều cao lớn hơn
100m. Tuy nhiên có những tính từ mà con người khó có thể định lượng được như là “good”,
“famous”… thì việc định nghĩa một thang đo cho những tính từ như vậy sẽ gặp nhiều khó khăn.
Ngoài ra, các tác giả trong [10], [11] đã nêu ra rằng các ý nghĩa của các tính từ còn phụ thuộc vào
ngữ cảnh. Ví dụ khi nói: “Peter is tall for a gymnast” thì ý nghĩa ở đây là Peter chỉ được xem là cao
trong ngữ cảnh so sánh với các vận động viên thể dục, còn đối với việc so sánh với người bình
thường thì điều này chưa hẳn đã đúng. Từ nhận xét này, các tác giả trong [10], [11] đã đề xuất giải
pháp khái niệm hóa các tính từ bằng phương pháp động. Các tác giả đề nghị xây dựng các lớp so sánh
để biểu diễn cho ngữ cảnh và sinh ra các quan hệ để biểu diễn độ tương quan về tính chất so với lớp
so sánh này.
Giải pháp thứ hai cho ta một cách mềm dẻo hơn khi biểu diễn các tính từ cho thuộc tính. Vấn đề
nảy sinh của cách thứ hai là việc so trùng giá trị String có thể được giải quyết bằng một từ điển các từ
đồng nghĩa, ví dụ như là WordNet. Tuy nhiên, với giải pháp này, ý nghĩa của các tính từ chỉ có thể
hiểu bởi con người, còn máy tính không thể suy luận được từ việc biểu diễn này. Ví dụ với cách biểu
Copyright: Tài liệu đại học ©