Luận án tiến sĩ truy hồi thông tin dựa trên ontology

ĐẠI HỌC QUỐC GIA TP.HCM TRƢỜNG ĐẠI HỌC BÁCH KHOA TP.HCM NGÔ MINH VƢƠNG TRUY HỒI THÔNG TIN DỰA TRÊN ONTOLOGY LUẬN ÁN TIẾN SĨ KỸ THUẬT TP. HỒ CHÍ MINH NĂM 2013 ĐẠI HỌC QUỐC GIA TP.HCM TRƢỜNG ĐẠI HỌC BÁCH KHOA TP.HCM NGÔ MINH VƢƠNG TRUY HỒI THÔNG TIN DỰA TRÊN ONTOLOGY LUẬN ÁN TIẾN SĨ KỸ THUẬT TP. HỒ CHÍ MINH NĂM 2013 ĐẠI HỌC QUỐC GIA TP.HCM TRƢỜNG ĐẠI HỌC BÁCH KHOA TP.HCM NGÔ MINH VƢƠNG TRUY HỒI THÔNG TIN DỰA TRÊN ONTOLOGY Chuyên ngành: Khoa học Máy tính Mã số chuyên ngành: 62.01 Phản biện độc lập 1: PGS. Đồng Thị Bích Thủy, ĐH KHTN, ĐHQG TPHCM Phản biện độc lập 2: PGS.

Lê Thanh Hƣơng, Viện CNTT&TT, ĐH BKHN Phản biện 1: PGS. Đỗ Phúc, ĐH CNTT, ĐHQG TPHCM Phản biện 2: TS. Nguyễn Thị Minh Huyền, ĐH KHTN, ĐHQG HN Phản biện 3: PGS. Dƣơng Tuấn Anh, ĐH BKTPHCM, ĐHQG TPHCM NGƢỜI HƢỚNG DẪN KHOA HỌC PGS.

Cao Hoàng Trụ, ĐH BKTPHCM, ĐHQG TPHCM 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 rõ nguồn gốc một cách rõ ràng từ danh mục tài liệu tham khảo đƣợc đề cập ở phần sau của 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 của tác giả ở phần sau 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 Ngô Minh Vƣơng i 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. Cao Hoàng Trụ, Thầy 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 KH&KT Máy Tính - Đại học Bách Khoa Tp.HCM đã 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ảm ơn Phòng Quản lý Sau Đại học về sự hỗ trợ các thủ tục trong quá trình hoàn thành luận án.

Cảm ơn Ban Giám hiệu Trƣờng Đại học Bách Khoa Tp.HCM, Phòng Khoa học Công nghệ & Dự án, và Phòng Quản lý Sau Đại học đã tài trợ cho tôi thực hiện đề tài nghiên cứu cấp trƣờng năm 2010. Cảm ơn Tập đoàn TOSHIBA đã cấp học bổng Chƣơng trình nghiên cứu khoa học và công nghệ cho học viên sau đại học xuất sắc trong 3 năm 2008, 2009 và 2010. Cảm ơn Ban Giám đốc ĐHQGTpHCM, Ban Quan hệ và Đối ngoại đã tạo điều kiện thuận lợi cho tôi tiếp cận đƣợc học bổng TOSHIBA ở trên. Cảm ơn Tập đoàn VNG đã tài trợ một phần kinh phí để tôi có thể công bố và thuyết trình công trình của mình tại hội nghị IJCNLP-2011 ở Chiang Mai, Thailand.

Những tài trợ này đã hỗ trợ tôi rất nhiều về mặt tài chính để trang trải một phần kinh phí học tập và nghiên cứu của tôi trong thời gian qua. Tôi chân thành cảm ơn Trung tâm CNTT - Ngân hàng Phát Triển Nhà ĐBSCL, Trung tâm R&D - Tập đoàn VNG và Khoa CNTT - Đại học Tôn Đức Thắng đã tạo mọi điều kiện thuận lợi cho tôi từ năm 2008 đến nay để hoàn thành luận án này. Cuối cùng tôi cảm ơn tất cả bạn bè và ngƣời thân đã góp nhiều ý kiến và những lời động viên khích lệ quí báu giúp tôi vƣợt qua khó khăn để hoàn thành tốt luận án. Tác giả luận án Ngô Minh Vƣơng ii TÓM TẮT Các hệ thống truy hồi tài liệu dạng văn bản hiện nay gặp nhiều thách thức trong việc khám phá và biểu diễn ngữ nghĩa của truy vấn và tài liệu.

Truy hồi tài liệu dựa trên việc so trùng các từ khóa có nhiều nhƣợc điểm bởi vì nó chỉ xem xét đến hình thức bề mặt của các từ xuất hiện trong văn bản hơn là ý nghĩa của các từ này. Trong khi đó, nội dung của văn bản phần lớn đƣợc xác định bởi các khái niệm nhƣ thực thể có tên và từ WordNet. Mặc khác, truy vấn đã có thể hiện rõ hơn mong muốn của ngƣời đặt truy vấn nếu đƣợc bổ sung các khái niệm tiềm ẩn phù hợp. Mục tiêu của luận án này là nghiên cứu và khai thác các ontology về thực thể có tên, từ WordNet và sự kiện về quan hệ thực thể để nâng cao hiệu quả truy hồi tài liệu về độ chính xác và độ đầy đủ.

Trong văn bản, các khái niệm đƣợc diễn đạt dƣới các dạng nhƣ tên của thực thể hoặc nhãn của từ. Các khái niệm này ẩn chứa các đặc điểm ontology bên dƣới các hình thức bề mặt của chúng nhƣ bí danh/từ đồng nghĩa, lớp cha/nghĩa cha, lớp con/nghĩa con và định danh/nghĩa của từ. Ngoài ra, mỗi truy vấn còn hàm ý các thực thể liên quan đến các thực thể xuất hiện tƣờng minh trong truy vấn. Luận án này có ba nội dung chính.

Thứ nhất, luận án khảo sát tất cả các đặc điểm ontology của thực thể có tên, các cách kết hợp chúng với từ khóa thông thƣờng, và nghiên cứu ảnh hƣởng của chúng đến hiệu quả truy hồi tài liệu, trong đó có cặp tên-lớp và định danh của thực thể có tên mà các công trình trƣớc đây chƣa khai thác. Thứ hai, luận án đề xuất sử dụng thêm cặp nhãn-nghĩa của từ WordNet bên cạnh các đặc điểm ontology cơ bản khác đã đƣợc sử dụng trƣớc đây. Thứ ba, luận án khai thác ontology về sự kiện để mở rộng truy vấn bằng các thực thể tiềm ẩn theo các quan hệ tƣờng minh với các thực thể trong truy vấn. Các mô hình đề xuất đƣợc hiện thực bằng cách mở rộng mô hình không gian vectơ cơ bản và đƣợc đánh giá bằng thực nghiệm trên các tập dữ liệu và độ đo hiệu quả chuẩn.

Kết quả thí nghiệm cho thấy các mô hình đề xuất cho hiệu quả truy hồi tài liệu cao hơn so với các mô hình ở các công trình liên quan quan và mô hình truy hồi tài liệu theo từ khoá thông thƣờng. Đặc biệt luận án đã sử dụng phƣơng pháp kiểm định ý nghĩa thống kê để xác nhận lại sự tăng hiệu quả thật sự của các mô hình đề xuất. iii ABSTRACT Current text document retrieval systems are facing to many challenges in discovering and representing the semantics of queries and documents. Document retrieval based on lexical matching of keywords has many drawbacks because it only considers the surface forms of words appearing in a text rather than the meaning of the words.

Meanwhile, the content of a text is mostly determined by concepts such as named entities and WordNet words. On the other hand, the meaning of a query could express more clearly user intention if it is expanded with suitable latent concepts. The objective of this thesis is to exploit ontologies of named entities, WordNet words and entity relationship facts to improve the performance of document retrieval in terms of the precision and recall measures. In a text, concepts are expressed by their surface forms like entity names or word labels.

Those concepts contain hidden ontological features under their surface forms, such as aliases/synonyms, super-classes/hypernyms, sub-classes/hyponyms and identifiers/senses. Besides, each query also implies those entities that are related to entities explicitly appearing in the query. This thesis consists of three main parts. First, the thesis explores ontological features of named entities, different combinations of them and keywords, and evaluates their impact to document retrieval performance, in which name-class pairs and identifies of named entities have not been exploited in previous works.

Second, the thesis proposes usage of form-sense pairs of WordNet words in addition to other basic ontological features that have been used previously. Third, the thesis exploits an ontology of facts to expand a query by latent entities that have explicit relations with other entities in the query. The proposed models are implemented by extending the basic vector space model and experimented on benchmark datasets and standard performance measures. Experiment results show that the proposed models give better retrieval performance than the models of related works and the traditional keyword-based document retrieval model.

Especially, this thesis uses statistical significance tests to confirm the actual improvement in performance of the proposed models. iv MỤC LỤC 1 Chƣơng 1 - GIỚI THIỆU .1 Động cơ nghiên cứu .2 Mục tiêu và phạm vi của luận án.3 Những đóng góp chính của luận án .4 Cấu trúc của luận án. 4 2 Chƣơng 2 - CƠ SỞ KIẾN THỨC .1 Mô hình không gian vectơ .2 Giới thiệu về Lucene.4 Nhận diện thực thể có tên và phân giải nhập nhằng nghĩa của từ.5 Tập dữ liệu kiểm tra .6 Độ đo hiệu quả truy hồi .7 Kiểm định ý nghĩa thống kê. 15 3 Chƣơng 3 - KHAI THÁC THỰC THỂ CÓ TÊN .2 Các công trình liên quan .3 Mô hình đa không gian vectơ cho thực thể có tên .4 Kết hợp thực thể có tên và từ khóa .5 Đánh giá thực nghiệm.

56 4 Chƣơng 4 - KHAI THÁC TỪ WORDNET .2 Các công trình liên quan .3 Mô hình không gian vectơ dựa trên từ WordNet .4 Đánh giá thực nghiệm. 72 5 Chƣơng 5 - KHAI THÁC THÔNG TIN TIỀM ẨN .2 Các công trình liên quan .3 Phƣơng pháp kích hoạt lan truyền .4 Mở rộng truy vấn .5 Đánh giá thực nghiệm. 86 6 Chƣơng 6 – KẾT HỢP CÁC MÔ HÌNH .2 Mô hình hợp nhất .3 Đánh giá thực nghiệm. 95 7 Chƣơng 7 - TỔNG KẾT .2 Hƣớng phát triển.

98 CÁC CÔNG TRÌNH CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN. 100 TÀI LIỆU THAM KHẢO. 102 vi DANH MỤC CÁC BẢNG Bảng 2. Thống kê về việc sử dụng tập kiểm tra trong các công trình mà luận án khảo sát ở SIGIR-2007 và SIGIR-2008.

Khảo sát việc khai thác các đặc điểm ontology của thực thể có tên cho truy hồi tài liệu. Các ví dụ về việc chuyển đổi từ để hỏi sang lớp của thực thể. Các độ chính xác trung bình tại mƣời một điểm đầy đủ chuẩn của các mô hình Lexical, NEo, NEn và NE-KW. Các độ F trung bình tại mƣời một điểm đầy đủ chuẩn của các mô hình Lexical, NEo, NEn và NE-KW.

Các độ chính xác trung bình nhóm của các mô hình Lexical, NEo, NEn và NE-KW. Trị số p hai chiều của phƣơng pháp kiểm định ngẫu nhiên Fisher của mô hình NE+KW so với các mô hình khác. Việc sử dụng các đặc điểm ontology của thực thể có tên để biểu diễn truy vấn và tài liệu. Các độ chính xác trung bình tại mƣời một điểm đầy đủ chuẩn của các mô hình Lexical, Group_1, Group_2, Group_3, NE+KW+notID, và NE+KW .