Tài liệu Xây dựng mô hình mở rộng truy vấn trong truy xuất thông tin văn bản

ĐẠ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è cùng gia ñình thường xuyên ñộng viên khích lệ. Luận án này không thể hoàn thành tốt nếu không có sự tận tình hướng dẫn và sự giúp ñỡ quý báu của PGS.TS. Phan Thị Tươi, giáo viên hướng dẫn mà tôi tôn vinh và muốn ñược bày tỏ lòng biết ơn sâu sắc nhất. Tôi cũng muốn ñược bày tỏ lòng biết ơn ñối với tập thể các thầy cô khoa Khoa học và Kỹ thuật Máy tính trường Đại học Bách khoa TP. Hồ Chí Minh ñã giúp ñỡ và tạo ñiều kiện cho tôi rất nhiều trong quá trình học tập và nghiên cứu ở Khoa; ñặc biệt PGS.TS. Dương Tuấn Anh, PGS.TS. Đỗ Phúc, PGS.TS. Đặng Trần Khánh và PGS.TS. Cao Hoàng Trụ ñã có những lời khuyên quý giá trong quá trình làm nghiên cứu sinh và viết luận án này; cảm ơn Phòng Đào tạo Sau Đại học về sự hỗ trợ các thủ tục hoàn thành luận án. Lời cảm ơn chân thành của tôi xin ñược gửi ñến anh Ngô Hùng Phương cùng tất cả bạn bè, ñặc biệt các thành viên trong nhóm nghiên cứu BK-NLP (thuộc trường Đại học Bách khoa Tp.HCM) ñã góp nhiều ý kiến thiết thực và có những lời ñộng viên khích lệ quý báu giúp tôi vượt qua khó khăn và hoàn thành tốt luận án. Sự biết ơn của tôi xin ñược gửi ñến gia ñình, vợ con và tất cả người thân, ñã hỗ trợ ñộng viên và tạo mọi ñiều kiện thuận lợi cho tôi trong suốt quá trình hoàn thành khóa học nghiên cứu sinh. Cuối cùng, trên tất cả những lời muốn nói, tôi xin tưởng nhớ và tri ân sâu sắc Mẹ và Bà Ngoại tôi, những người ñã luôn cho tôi ñược học hành ñầy ñủ dù ở bất kỳ hoàn cảnh nào và luôn truyền cho tôi một tinh thần hiếu học không ngừng nghỉ. Tác giả luận án Nguyễn Chánh Thành TÓM TẮT Trong truy xuất thông tin (Information Retrieval), do những yếu tố khác nhau, người sử dụng thường dùng các truy vấn dạng ñơn giản biểu diễn yêu cầu cần tìm. Việc này dẫn ñến kết quả tìm ñược không ñáp ứng ñủ nhu cầu mong muốn, hoặc chất lượng thấp. Do ñó, mở rộng truy vấn là vấn ñề cần thiết, ñể từ ñó giúp hệ thống truy xuất thông tin có thêm thông tin theo ngữ cảnh nhằm cải tiến các kết quả truy vấn. Thông tin theo ngữ cảnh có thể thu ñược từ những thông tin phản hồi liên quan, từ ñồng hiện hay mô hình tri thức như bản thể học (ontology). Việc ứng dụng ontology ñể trợ giúp việc mở rộng truy vấn ñược nghiên cứu 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à làm giàu 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. i 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 DANH MỤC CÁC TỪ VIẾT TẮT............................................................................... viii Chương 1 1.1 1.2 1.3 1.4 1.5 1.6 Động cơ nghiên cứu .............................................................................................1 Mục tiêu và phạm vi nghiên cứu .........................................................................5 Đóng góp chính của luận án ................................................................................8 Cấu trúc của luận án...........................................................................................10 Các quy ước .......................................................................................................13 Tóm tắt nội dung luận án ...................................................................................13 Chương 2 2.1 2.2 2.3 2.4 2.5 2.6 XÂY DỰNG ONTOLOGY OOMP ........................................................89 Giới thiệu ...........................................................................................................89 Xây dựng ontology OOMP ................................................................................89 Phương pháp làm giàu dựa trên kho ngữ liệu ....................................................94 Phương pháp làm giàu dựa trên WordNet .........................................................99 Cơ chế tự làm giàu của ontology OOMP .........................................................106 Các ứng dụng của ontology và quan hệ ...........................................................108 Tóm lược ..........................................................................................................109 Chương 5 5.1 XÂY DỰNG NỀN TẢNG HỆ THỐNG .................................................47 Giới thiệu ...........................................................................................................47 Bài toán Xây dựng ontology và bài toán Hoàn chỉnh mở rộng truy vấn ...........47 Các mô hình cho bài toán mở rộng truy vấn ......................................................61 Mẫu nhận dạng cụm danh từ..............................................................................66 Phương pháp thực nghiệm và ñánh giá ..............................................................71 Nguồn dữ liệu thực nghiệm ...............................................................................75 Tóm lược ............................................................................................................87 Chương 4 4.1 4.2 4.3 4.4 4.5 4.6 4.7 CÁC NGHIÊN CỨU LIÊN QUAN ........................................................14 Giới thiệu ...........................................................................................................14 Các nghiên cứu liên quan trong nước ................................................................15 Các nghiên cứu về ontology ..............................................................................19 Các nghiên cứu về mở rộng truy vấn .................................................................23 Khai thác dữ liệu từ WordNet ............................................................................39 Tóm lược ............................................................................................................45 Chương 3 3.1 3.2 3.3 3.4 3.5 3.6 3.7 GIỚI THIỆU ..............................................................................................1 HOÀN CHỈNH VÀ RÚT GỌN TRUY VẤN.......................................111 Giới thiệu .........................................................................................................111 ii 5.2 5.3 5.4 5.5 5.6 5.7 5.8 Hoàn chỉnh và rút gọn truy vấn .......................................................................112 Kiểm tra cụm danh từ hoàn chỉnh ....................................................................113 Tạo cụm danh từ hoàn chỉnh............................................................................120 Tạo cụm danh từ rút gọn ..................................................................................121 Hoàn chỉnh cụm danh từ ..................................................................................122 Giải thuật rút gọn thành phần cụm danh từ......................................................133 Tóm lược ..........................................................................................................139 Chương 6 6.1 6.2 6.3 Mở rộng truy vấn cho ñộng cơ tìm kiếm trên Web .........................................140 Mở rộng truy vấn cho hệ thống truy xuất thông tin có sẵn ..............................151 Tóm lược ..........................................................................................................163 Chương 7 7.1 7.2 7.3 MỞ RỘNG TRUY VẤN........................................................................140 KẾT LUẬN .............................................................................................165 Các kết quả ñạt ñược........................................................................................165 Hướng phát triển ..............................................................................................169 Lời kết ..............................................................................................................171 CÁC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ ...................................................172 TÀI LIỆU THAM KHẢO .............................................................................................175 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