Luận văn Vn-Kim search tiếng anh với truy vấn có liên từ luận lý, tính từ và lượng từ

i ĐẠI HỌC QUỐC GIA TP. HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA KHOA HỌC & KỸ THUẬT MÁY TÍNH ---------o0o---------- LUẬN VĂN TỐT NGHIỆP ĐẠI HỌC VN-KIM SEARCH TIẾNG ANH VỚI TRUY VẤN CÓ LIÊN TỪ LUẬN LÝ, TÍNH TỪ VÀ LƯỢNG TỪ Hội Đồng : Khoa Học Máy Tính 1 GVHD : Pgs.Ts. Cao Hoàng Trụ GVPB : Ks. Châu Kim Cường -----o0o----- SVTH 1 : Nguyễn Trần Đăng Khoa (50601130) SVTH 2 : 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 . . . . . ii LỜI CAM ĐOAN Chúng 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 chúng 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 iii 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ỹ sư Châu Kim Cường, những người đã trực tiếp hướng dẫn chúng tôi trong quá trình làm luận văn này. Sự hướng dẫn chu đáo, tận tình, cùng với những tài liệu và lời khuyên quý giá của thầy và anh trong hơn 3 tháng qua là nhân tố không thể thiếu để chúng tôi có thể hoàn thành nhiệm vụ. Chúng tôi xin gửi lời cảm ơn đến gia đình và bạn bè, những người luôn sát cánh, động viên, và tạo mọi điều kiện tốt nhất để chúng tôi có thể học tập và hoàn tất được luận văn tốt nghiệp này. Chúng tôi chân thành biết ơn sự tận tình dạy dỗ và sự giúp đỡ của tất cả quý thầy cô khoa Khoa học và Kỹ thuật Máy tính trường Đại học Bách khoa. Luận văn này khó tránh khỏi còn thiếu sót do tầm nhìn của chúng tôi còn hạn hẹp, rất mong nhận được sự góp ý của quý thầy cô cùng các bạn. iv TÓM TẮT Luận văn này xây dựng một hệ thống tìm kiếm dựa trên ngữ nghĩa. Hệ thống có thể “hiểu” được câu truy vấn đầu vào bằng tiếng Anh. Câu truy vấn không chỉ chứa thực thể và từ quan hệ, mà còn chứa tính từ, lượng từ, và liên từ luận lý. Để biên dịch câu truy vấn ngôn ngữ tự nhiên, luận văn này dựa trên nền tảng web ngữ nghĩa, kết hợp với phương pháp dịch ít phụ thuộc vào cú pháp của nhóm VN-KIM. Để thể hiện nội dung biên dịch được, luận văn biểu diễn bằng đồ thị ý niệm. Cuối cùng, câu truy vấn SeRQL được dùng để tìm kiếm kết quả. Hướng tiếp cận này đã giúp đề tài xây dựng được một hệ thống trực quan với người sử dụng, và tráng kiện với lỗi cú pháp. Hiệu quả của hệ thống được đánh giá trên tập câu truy vấn mẫu “TREC 2002”. Tỉ lệ số câu hệ thống biên dịch thành công là 85.91%. v MỤC LỤC LỜI CAM ĐOAN .......................................................................................................................... ii LỜI CẢM ƠN .............................................................................................................................. iii TÓM TẮT ..................................................................................................................................iv MỤC LỤC ................................................................................................................................... v DANH MỤC HÌNH .................................................................................................................... viii DANH MỤC BẢNG ......................................................................................................................ix CHƯƠNG 1 TỔNG QUAN ........................................................................................................... 1 1.1 Giới thiệu ....................................................................................................................... 1 1.2 Mục tiêu phạm vi ............................................................................................................ 3 1.3 Kết quả đạt được............................................................................................................. 5 1.4 Cấu trúc luận văn ............................................................................................................ 6 CHƯƠNG 2 KIẾN THỨC NỀN TẢNG ....................................................................................... 7 2.1 Chú thích ngữ nghĩa và tìm kiếm ngữ nghĩa .................................................................... 7 2.1.1 Các khái niệm ........................................................................................................... 7 2.1.2 Các phần mềm, công cụ sử dụng ............................................................................... 8 2.2 Đồ thị ý niệm ................................................................................................................ 10 2.2.1 Sơ lược về đồ thị ý niệm ......................................................................................... 10 2.2.2 Đồ thị ý niệm mở rộng ............................................................................................ 12 2.3 Tìm kiếm thực thể và tài liệu ........................................................................................ 13 2.3.1 Câu truy vấn SeRQL [8] ......................................................................................... 13 2.3.2 Semantic Lucene ..................................................................................................... 14 CHƯƠNG 3 PHÂN TÍCH VẤN ĐỀ VÀ PHƯƠNG PHÁP GIẢI QUYẾT ............................... 16 3.1 Phương pháp chuyển đổi câu truy vấn sang đồ thị ý niệm ............................................. 16 3.2 Xử lý câu truy vấn thông thường ................................................................................... 17 3.3 Xử lý câu truy vấn có từ để hỏi là “How many” ............................................................ 19 vi 3.4 Xử lý câu truy vấn có liên từ luận lý ............................................................................. 21 3.5 Xử lý câu truy vấn có tính từ......................................................................................... 22 3.6 Xử lý câu truy vấn có tính từ so sánh nhất ..................................................................... 24 3.7 Xử lý câu truy vấn có tính từ định lượng so sánh hơn .................................................... 25 CHƯƠNG 4 THIẾT KẾ .............................................................................................................. 27 4.1 Kiến trúc toàn bộ hệ thống ............................................................................................ 27 4.2 Chi tiết các bước của giải thuật ..................................................................................... 29 4.2.1 Nhận biết các thành phần của câu truy vấn .............................................................. 29 4.2.2 Phân tách câu truy vấn ............................................................................................ 30 4.2.3 Xác định lớp của thực thể........................................................................................ 30 4.2.4 Gom các thực thể .................................................................................................... 31 4.2.5 Xác định quan hệ ẩn ................................................................................................ 31 4.2.6 Xác định loại quan hệ giữa các thực thể .................................................................. 32 4.2.7 Xoá bỏ quan hệ không phù hợp ............................................................................... 35 4.2.8 Xác định quan hệ giữa tính từ và thực thể ............................................................... 36 4.2.9 Xây dựng đồ thị ý niệm ........................................................................................... 39 4.2.10 Xây dựng câu truy vấn SeRQL................................................................................ 39 CHƯƠNG 5 HIỆN THỰC........................................................................................................... 40 5.1 Các khối xử lý và giao diện các lớp quan trọng ............................................................. 40 5.1.1 Ứng dụng web phía Client ...................................................................................... 40 5.1.2 Hệ thống xử lý trên server ....................................................................................... 40 5.2 Hệ thống luật ................................................................................................................ 44 5.2.1 Cấu trúc của hệ thống luật ....................................................................................... 45 5.2.2 Cấu trúc thành phần điều kiện của luật .................................................................... 45 5.2.3 Cấu trúc thành phần hành động của luật .................................................................. 46 vii 5.2.4 Xây dựng một số luật đặc biệt ................................................................................. 47 5.3 Lưu trữ và hiển thị đồ thị .............................................................................................. 47 5.4 Xây dựng câu truy vấn SeRQL ..................................................................................... 49 CHƯƠNG 6 THỬ NGHIỆM ....................................................................................................... 53 6.1 Môi trường thử nghiệm ................................................................................................. 53 6.2 Kết quả thực nghiệm ..................................................................................................... 54 CHƯƠNG 7 KẾT LUẬN ............................................................................................................. 57 7.1 Kết quả đạt được........................................................................................................... 57 7.2 Các vấn đề còn tồn tại ................................................................................................... 58 7.3 Hướng phát triển ........................................................................................................... 58 TÀI LIỆU THAM KHẢO ........................................................................................................... 59 PHỤ LỤC A: TẬP CÂU MẪU TREC 2002 .......................................................................................... 60 viii DANH MỤC HÌNH Hình 1-1 Đồ thị có đề xuất quan hệ không tồn tại trong cơ sở tri thức .............................................. 5 Hình 2-1 Ba module của Proton [5] .................................................................................................. 9 Hình 2-2 Cơ sở tri thức của KIM (30/09/2006) [6] ......................................................................... 10 Hình 2-3 Đồ thị ý niệm ví dụ.......................................................................................................... 11 Hình 2-4 Đồ thị ý niệm có đỉnh truy vấn con .................................................................................. 12 Hình 3-1 Đồ thị ý niệm cho mỗi bộ ba ........................................................................................... 18 Hình 3-2 Đỉnh truy vấn con ............................................................................................................ 19 Hình 3-3 Đồ thị ý niệm cho câu truy vấn có "how many" ............................................................... 20 Hình 3-4 Đồ thị ý niệm ví dụ cho câu truy vấn có "how many" [3] ................................................. 20 Hình 3-5 Đồ thị ý niệm ví dụ cho câu truy vấn có "how many" [3] ................................................. 20 Hình 3-6 Đồ thị ý niệm cho câu truy vấn có liên từ luận lý ............................................................. 22 Hình 3-7 Đồ thị ý niệm ví dụ, cho câu truy vấn có tính từ so sánh nhất .......................................... 24 Hình 3-8 Đồ thị ý niệm ví dụ, cho câu truy vấn có tính từ định tính so sánh nhất ............................ 24 Hình 3-9 Đồ thị ý niệm ví dụ, cho câu truy vấn có tính từ định lượng so sánh nhất ......................... 25 Hình 4-1 Kiến trúc tổng quan ......................................................................................................... 27 Hình 4-2 Các bước xử lý ................................................................................................................ 28 Hình 4-3 Lược đồ ánh xạ kiểu quan hệ của bộ ba truy vấn [3] ........................................................ 33 Hình 4-4 Xác định loại quan hệ giữa hai thực thể ei và ej [2] .......................................................... 34 Hình 4-5 Lược đồ ánh xạ kiểu quan hệ giữa tính từ và thực thể [3] ................................................. 37 Hình 4-6 Xác định loại quan hệ giữa tính từ adj và thực thể [3] ...................................................... 38 Hình 5-1 Cấu trúc tập phần tử TransformRules và rule ................................................................... 45 Hình 5-2 Cấu trúc phần tử điều kiện luật ........................................................................................ 46 Hình 5-3 Cấu trúc phần tử hành động ............................................................................................. 46 Hình 5-4 Một luật hoàn chỉnh ........................................................................................................ 47 Hình 5-5 Cấu trúc dữ liệu lưu trữ đồ thị ý niệm .............................................................................. 47 Hình 5-6 Dạng tổng quát của đồ thị ý niệm .................................................................................... 48 Hình 5-7 Tên hình .......................................................................................................................... 49 ix DANH MỤC BẢNG Bảng 5-1 Giao diện các dịch vụ ...................................................................................................... 40 Bảng 5-2 Bản tóm tắt các phương thức lớp ENSearch .................................................................... 41 Bảng 5-3 Bản tóm tắt các phương thức lớp QuerytoCG .................................................................. 41 Bảng 5-4 Bản tóm tắt các phương thức lớp QuerytoCG (2) ............................................................ 42 Bảng 5-5 Bản tóm tắt các phương thức lớp Processing XML.......................................................... 42 Bảng 5-6 Bản tóm tắt các phương thức lớp ProcessingQuery ......................................................... 43 Bảng 5-7 Bản tóm tắt các phương thức lớp ProcessingQuery (2) .................................................... 43 Bảng 5-8 Bản tóm tắt các phương thức lớp QueryOutput ............................................................... 43 Bảng 5-9 Bản tóm tắt các phương thức lớp SeRQLMapping .......................................................... 44 Bảng 5-10 Các thuộc tính của phần tử điều kiện ............................................................................. 46 Bảng 6-1 Kết quả thực nghiệm trên TREC 2002 trước khi làm giàu Ontology ................................ 54 Bảng 6-2 Kết quả thực nghiệm trên TREC 2002 sau khi làm giàu Ontology ................................... 55 Bảng 6-3 Kết quả thực nghiệm trên TREC 2002 sau khi làm giàu Ontology phân theo dạng câu .... 55 1 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. Hiện nay, đã có những công cụ phần mềm nhắm đến mục tiêu đó. Nổi bật nhất có lẽ là các động cơ tìm kiếm dựa trên từ khóa (keyword – based search engine), như động cơ tìm kiếm của Google, Yahoo,... Tuy đã đạt được những thành công nhất định, nhưng các hệ thống này còn có những khuyết điểm làm cho người sử dụng chưa được hài lòng. Có thể nêu ra như:  Kết quả trả về cho một truy vấn là nhiều, nhưng độ chính xác lại thấp. Người dùng phải tốn nhiều thời gian với những kết quả không thích hợp.  Kết quả trả về hoàn toàn phụ thuộc vào từ khóa được cung cấp. Trong khi, theo mong muốn của con người, thì các truy vấn tương tự nhau về mặt ngữ nghĩa phải dẫn đến những kết quả như nhau. Do công cụ tìm kiếm chủ yếu chỉ so trùng, mà chưa “hiểu” được nội dung của thông tin chứa trên WWW và nội dung của câu truy vấn, nên dẫn đến những hạn chế trên. Như vậy, để làm tăng hiệu quả của quá trình tìm kiếm tự động, một hướng tiếp cận là làm cho máy tính “hiểu” được nội dung của thông tin: thông tin được lưu trữ trên WWW và thông tin trong câu truy vấn của người dùng. Đề tài này quan tâm đến khía cạnh giúp cho máy tính hiểu được nội dung của câu truy vấn dùng ngôn ngữ tự nhiên là tiếng Anh. Nhìn chung, việc hướng dẫn cho máy tính xử lý 1 câu truy 2 vấn bằng ngôn ngữ tự nhiên (bất kỳ) nhằm hiểu được ý nghĩa là khá phức tạp, có thể liệt kê ra một số khó khăn:  Ngữ pháp của ngôn ngữ tự nhiên rất đa dạng, cách sử dụng rất linh hoạt. Và một câu có thể có nhiều ngữ pháp phù hợp (mặc dù đối với con người sẽ không có nghĩa). Dẫn đến không thể chỉ dựa vào cấu trúc của câu để xác định ngữ nghĩa.  Cùng một từ nhưng có thể ứng với nhiều từ loại (danh từ, động từ, ...). Muốn hiểu đúng phải xác định đúng loại từ. Lấy ví dụ: “Time flies like an arrow”. “Time” và “flies” có ít nhất 2 cách hiểu có ý nghĩa: “Time” làm danh từ và “flies” làm động từ, hay “Time” làm động từ và “flies” làm danh từ.  Phải giải quyết sự đa hình của từ (morphology) nếu muốn nhận biết đầy đủ các thành phần của câu. Ví dụ như động từ “fly” có thể có dạng “flies”, “flying”, “flew”.  Việc xác định quan hệ ngữ nghĩa giữa các đối tượng trong câu đòi hỏi phải có tri thức về các mối quan hệ phù hợp giữa các đối tượng. Và phải xem xét ngữ cảnh của câu để chọn ra quan hệ phù hợp nhất.  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. 3 1.2 Mục tiêu 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 [2], như:  Hình thức đồ thị: n