Đề tài Phương pháp nâng cao chất lượng kết quả trả lời cho hệ thống hỏi đáp danh sách Tiếng Việt

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thanh Sơn PHƯƠNG PHÁP NÂNG CAO CHẤT LƯỢNG KẾT QUẢ TRẢ LỜI CHO HỆ THỐNG HỎI ĐÁP DANH SÁCH TIẾNG VIỆT KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ Thông tin HÀ NỘI - 2010 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thanh Sơn PHƯƠNG PHÁP NÂNG CAO CHẤT LƯỢNG KẾT QUẢ TRẢ LỜI CHO HỆ THỐNG HỎI ĐÁP DANH SÁCH TIẾNG VIỆT KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ Thông tin Cán bộ hướng dẫn: PGS.TS Hà Quang Thụy Cán bộ đồng hướng dẫn: ThS. Trần Mai Vũ HÀ NỘI - 2010 Lời cảm ơn Trước tiên, tôi xin gửi lời cảm ơn và lòng biết ơn sâu sắc nhất tới Phó Giáo sư Tiến sĩ Hà Quang Thụy, Thạc sĩ Trần Mai Vũ và Cử nhân Lê Hoàng Quỳnh – những người đã tận tình chỉ bảo và hướng dẫn tôi trong quá trình thực hiện khoá luận tốt nghiệp. Tôi chân thành cảm ơn các thầy, cô và cán bộ của trường Đại Học Công Nghệ đã tạo cho tôi những điều kiện thuận lợi để học tập và nghiên cứu. Tôi cũng xin gửi lời cảm ơn tới các anh chị và các bạn sinh viên trong phòng thí nghiệm Sislab đã giúp tôi rất nhiều trong việc thu thập và xử lý dữ liệu. Cuối cùng, tôi muốn gửi lời cảm ơn tới gia đình và bạn bè, những người thân yêu luôn bên cạnh, động viên tôi trong suốt quá trình thực hiện khóa luận tốt nghiệp. Tôi xin chân thành cảm ơn! Sinh viên Nguyễn Thanh Sơn Tóm tắt Nhờ khả năng hỗ trợ người dùng trong việc khai thác các tài nguyên trên Internet một cách hiệu quả và dễ dàng, hệ thống hỏi đáp nói chung đã được quan tâm nghiên cứu từ khá lâu, tuy nhiên các dạng hệ thống hỏi đáp đặc biệt, trong đó có hệ thống hỏi đáp danh sách vẫn còn đang ở bước đầu phát triển. Hệ thống hỏi đáp danh sách là hệ thống hỏi đáp, nhận đầu vào là câu hỏi dưới dạng ngôn ngữ tự nhiên và trả về câu trả lời dưới dạng một danh sách. Tại Việt Nam, các nghiên cứu về hệ thống hỏi đáp nói chung, cũng như về hệ thống hỏi đáp danh sách nói riêng tập trung cho miền dữ liệu tiếng Việt còn rất nhiều hạn chế. Một trong những lý do chính là chúng ta còn thiếu các công cụ xử lý tiếng Việt, các tài nguyên ngôn ngữ học, … Khóa luận Phương pháp nâng cao chất lượng kết quả trả lời cho hệ thống hỏi đáp danh sách tiếng Việt tập trung nghiên cứu các phương pháp xây dựng hệ thống hỏi đáp danh sách đã được áp dụng trên thế giới cũng như một số phương pháp nâng cao chất lượng kết quả trả lời cho dạng hệ thống hỏi đáp này. Trên cơ sở các nghiên cứu nói trên, kết hợp với việc khảo sát điều kiện thực tế của các công cụ xử lý ngôn ngữ tiếng Việt, khóa luận đề xuất mô hình nâng cao chất lượng kết quả trả lời cho hệ thống hỏi đáp danh sách tiếng Việt sử dụng luật Wrapper và luật ngữ nghĩa. Thực nghiệm mô hình cho kết quả khá khả quan, đạt độ chính xác cho câu trả lời chứa 5 kết quả là 93.87% so với độ chính xác 82.11% của pha hỏi đáp danh sách, đồng thời hứa hẹn nhiều tiềm năng nghiên cứu mới. Mục lục Lời mở đầu .................................................................................................................. 1 Chương 1. Giới thiệu hệ thống hỏi đáp danh sách ........................................................ 3 1.1. Hệ thống hỏi đáp ............................................................................................... 3 1.1.1. Giới thiệu chung .......................................................................................... 3 1.1.2. Một số vấn đề cần quan tâm ........................................................................ 4 1.1.3. Các bước xử lý chung .................................................................................. 5 1.1.4. Tiêu chuẩn đánh giá..................................................................................... 6 1.1.5. Phân loại...................................................................................................... 7 1.2. Hệ thống hỏi đáp danh sách ............................................................................. 10 1.2.1. Giới thiệu .................................................................................................. 10 1.2.2. Một số hướng tiếp cận xây dựng hệ thống hỏi đáp danh sách..................... 10 1.2.3. Những vấn đề cần giải quyết khi xây dựng hệ hỏi đáp danh sách ............... 11 Chương 2. Các nghiên cứu liên quan ......................................................................... 13 2.1. Một số hệ thống hỏi đáp danh sách điển hình ................................................... 13 2.1.1. Hệ thống hỏi đáp danh sách FADA ........................................................... 16 2.1.2. Hệ thống hỏi đáp Ephyra ........................................................................... 20 2.2. Nâng cao chất lượng trả lời cho hệ thống hỏi đáp danh sách ............................ 23 Chương 3: Đề xuất mô hình nâng cao chất lượng câu trả lời cho hệ thống hỏi đáp danh sách tiếng Việt ........................................................................................................... 28 3.1. Mô hình nâng cao chất lượng câu trả lời cho hệ thống hỏi đáp danh sách tiếng Việt ........................................................................................................................ 28 3.2. Pha 1: Hỏi đáp danh sách tiếng Việt ................................................................ 29 3.2.1. Tìm kiếm câu trả lời dựa vào các mẫu quan hệ thượng hạ danh ................. 29 3.2.2. Mô hình pha 1: Hệ thống hỏi đáp danh sách .............................................. 30 3.3. Pha 2: Mở rộng thực thể .................................................................................. 32 3.3.1. Xây dựng các luật Wrapper ...................................................................... 33 3.3.2. Các phương pháp xếp hạng được sử dụng .................................................. 35 3.3.3. Mô hình pha 2: mở rộng thực thể ............................................................... 35 Chương 4. Thực nghiệm và đánh giá ......................................................................... 39 4.1. Thực nghiệm pha hỏi đáp danh sách ................................................................ 39 4.1.1. Dữ liệu thực nghiệm .................................................................................. 39 4.1.2. Kết quả thực nghiệm.................................................................................. 40 4.2. Thực nghiệm đánh giá kết quả mô hình nâng cao chất lượng câu trả lời cho hệ thống hỏi đáp danh sách tiếng việt .......................................................................... 42 Kết luận ..................................................................................................................... 47 Phụ lục....................................................................................................................... 49 Tài liệu tham khảo ..................................................................................................... 51 Danh sách các bảng Bảng 1. 5 kết quả cao nhất tại TREC-12 (Voorhees, 2003) ........................................ 13 Bảng 2. Các lớp trang web ......................................................................................... 17 Bảng 3. Hiệu suất của tập kiểm thử trong TREC-12 ................................................... 20 Bảng 4. Cây kế thừa thực thể tên và các mẫu loại ...................................................... 22 Bảng 5. Kết quả thực thi SEAL với các thuật toán đánh giá và số lượng tập mồi khác nhau ........................................................................................................................... 25 Bảng 6. Ví dụ các truy vấn và chất lượng văn bản thu thập tương ứng ....................... 26 Bảng 7. Độ chính xác trung bình của Ephyra ............................................................. 27 Bảng 8. Độ đo trung bình F1 của Ephyra .................................................................... 27 Bảng 9. Một số mẫu quan hệ thượng hạ danh trong tiếng Anh và tiếng Việt. ............. 30 Bảng 10. Ví dụ về câu hỏi danh sách và từ khóa tương ứng ....................................... 39 Bảng 11. Kết quả thực nghiệm pha hỏi đáp danh sách tiếng Việt ............................... 40 Bảng 12. Kết quả thực nghiệm mô hình nâng cao sử dụng 2 thực thể mồi .................. 42 Bảng 13. Kết quả thực nghiệm mô hình nâng cao sử dụng 3 thực thể mồi .................. 43 Bảng 14. Kết quả thực nghiệm mô hình nâng cao – 4 kết quả đầu vào ....................... 44 Danh sách các hình Hình 1. Các bước chung của hệ thống hỏi đáp ............................................................ 5 Hình 2. Xu hướng trong nghiên cứu về hệ thống hỏi đáp ............................................. 8 Hình 3. Ví dụ về một Snippet trả về từ máy tìm kiếm ................................................ 22 Hình 4. Mô hình thực nghiệm nâng cao chất lượng kết quả trả lời trong .................... 28 Hình 5. Ví dụ về quan hệ thượng hạ danh. ................................................................. 29 Hình 6. Mô hình pha 1 - Hỏi đáp danh sách tiếng Việt ............................................... 30 Hình 7. Ví dụ cấu trúc web ........................................................................................ 33 Hình 8.Ví dụ văn bản bán cấu trúc ............................................................................. 34 Hình 9. Mô hình pha 2 - Mở rộng thực thể ................................................................ 36 Danh sách các biểu đồ Biểu đồ 1. Kết quả của mỗi loại câu hỏi trong tập dữ liệu kiểm thử - TREC, 2007 ..... 15 Biểu đồ 2. Số lượng từ khóa được đáp ứng với số lượng khác nhau của tập kết quả ... 40 Biểu đồ 3. Độ chính xác của các kết quả trong thực nghiệm pha hỏi đáp danh sách tiếng Việt ................................................................................................................... 41 Biểu đồ 4. So sánh độ chính xác câu trả lời ................................................................ 44 Biểu đồ 5.Khả năng đáp ứng từ khóa của hệ thống trong các trường hợp ................... 45 1 Lời mở đầu Internet ngày nay, một mặt đã trở thành kho tài nguyên thông tin khổng lồ và phong phú, nhưng mặt khác, việc thông tin được tổ chức dưới dạng không cấu trúc hoặc bán cấu trúc cũng khiến cho việc nắm bắt thông tin trở nên khó khăn. Máy tìm kiếm đã hỗ trợ khá đắc lực cho người dùng, tuy nhiên, để có thông tin mong muốn, người dùng phải tự tìm trong các trang web mà máy tìm kiếm trả về. Đây là một công việc tốn rất nhiều thời gian và công sức bởi số lượng các trang web được trả về bởi máy tìm kiếm thường là rất lớn. Chính vì vậy hệ thống hỏi đáp đã ra đời, nhằm mục đích tìm kiếm câu trả lời ngắn gọn và chính xác nhất cho người dùng thay vì trả về các văn bản. Các câu hỏi của người dùng thường rất đa dạng và yêu cầu các loại câu trả lời cũng khác nhau. Một trong những hướng nghiên cứu mới và đang được chú ý hiện nay chính là về hệ thống hỏi đáp danh sách. Thay vì chỉ có một kết quả trong câu trả lời, hệ thống hỏi đáp danh sách thường phải trả về câu trả lời là một danh sách các kết quả. Đây chính là đặc điểm khác biệt nhất giữa hệ thống hỏi đáp danh sách và các hệ thống hỏi đáp khác. Trả về câu trả lời chứa đầy đủ và chính xác các kết quả chính là một trong những mục tiêu được chú trọng nhất được hướng đến khi xây dựng hệ thống hỏi đáp danh sách. Tuy nhiên, đó cũng chính thách thức lớn nhất mà các nhà nghiên cứu gặp phải. Khóa luận Phương pháp nâng cao chất lượng kết quả trả lời cho hệ thống hỏi đáp danh sách tiếng Việt thực hiện việc khảo sát, nghiên cứu một số phương pháp đã được sử dụng trong một số hệ thống hỏi đáp danh sách, cũng như tìm hiểu một vài nghiên cứu về việc nâng cao chất lượng trả lời cho hệ thống hỏi đáp danh sách, từ đó đưa ra phương pháp phù hợp để giải quyết bài toán này cho miền dữ liệu tiếng Việt. Khóa luận đề xuất một mô hình giải quyết bài toán gồm 2 pha chính: (1) Pha hỏi đáp danh sách, tìm câu trả lời dựa vào các luật thượng hạ danh (hyponym). (2) Pha nâng cao chất lượng cho câu trả lời của pha hỏi đáp danh sách dựa vào các phương pháp mở rộng thực thể. Nội dung của khóa luận bao gồm các chương sau: Chương 1. Giới thiệu hệ thống hỏi đáp danh sách. Chương 1 trình bày những nội dung cơ bản về hệ thống hỏi đáp nói chung và hệ thống hỏi đáp danh sách nói riêng. Chương 2. Các nghiên cứu liên quan. Chương 2 điểm qua một số các nghiên cứu liên quan trên thế giới cũng như tại Việt Nam về hệ thống hỏi đáp nói chung, cũng 2 như hệ thống hỏi đáp danh sách nói riêng và bài toán mở rộng thực thể. Khóa luận tập trung tìm hiểu các phương pháp được áp dụng trong hai hệ thống hỏi đáp danh sách tiêu biểu là FADA và Ephyra. Cùng với đó, chương này cũng giới thiệu về các nghiên cứu đã có để nâng cao chất lượng câu trả lời cho hệ thống hỏi đáp danh sách, trong đó tập trung cho hướng nâng cao bằng mở rộng thực thể. Chương 3. Đề xuất mô hình nâng cao chất lượng câu trả lời cho hệ thống hỏi đáp danh sách tiếng Việt. Chương 3 trình bày về mô hình nâng cao chất lượng cho hệ thống hỏi đáp danh sách tiếng Việt mà khoá luận đề xuất. Mô hình này gồm 2 pha chính là pha hỏi đáp danh sách và pha mở rộng thực thể. Chương 4. Thực nghiệm và đánh giá. Tiến hành thực nghiệm để kiểm tra chất lượng của phương pháp đã đề xuất bằng cách thực nghiệm riêng pha hỏi đáp danh sách và thực nghiệm có sử dụng bước nâng cao kết quả trong mô hình, từ đó đưa ra đánh giá. Kết luận và hướng phát triển khóa luận: Tóm lược những nội dung chính của khóa luận.Đồng thời đưa ra những hướng nghiên cứu trong thời gian sắp tới dựa vào các định hướng khắc phục một vài hạn chế vẫn còn tồn tại. 3 Chương 1. Giới thiệu hệ thống hỏi đáp danh sách 1.1. Hệ thống hỏi đáp 1.1.1. Giới thiệu chung Sự phát triển ngày càng mạnh mẽ của World Wide Web đã đưa ra thách thức khai phá các thông tin trên web một cách hiệu quả hơn. Tuy kết quả trả về của các máy tìm kiếm ngày càng được nâng cao chất lượng nhưng kết quả vẫn là danh sách các tài liệu có chứa câu truy vấn. Người dùng muốn có thông tin thì phải tự tìm trong các trang web đó. Đây là một công việc tốn rất nhiều thời gian và công sức bởi số lượng các trang web được trả về bởi máy tìm kiếm thường là rất lớn. Chính vì vậy hệ thống hỏi đáp đã ra đời, nhằm mục đích tìm kiếm câu trả lời ngắn gọn và chính xác nhất cho người dùng thay vì trả về các văn bản. Khái niệm hệ thống hỏi đáp: Hệ thống hỏi đáp là hệ thống đuợc xây dựng để thực hiện việc tìm kiếm tự động câu trả lời từ một tập lớn các tài liệu cho câu hỏi đầu vào một cách chính xác và ngắn gọn [30]. Nhiệm vụ của hệ hỏi đáp là tự động tìm ra câu trả lời cho câu hỏi dưới dạng ngôn ngữ tự nhiên. Để tìm được câu trả lời, hệ hỏi đáp phải sử dụng các nguồn dữ liệu có cấu trúc như cơ sở dữ liệu hoặc một tập các văn bản không có cấu trúc. Tuy nhiên, như đã biết, ngôn ngữ tự nhiên chứa các yếu tố nhập nhằng, đa nghĩa, việc xác định được ngữ nghĩa của câu hỏi cũng như tìm ra câu trả lời là một thách thức không nhỏ. Không những vậy, giữa câu hỏi và câu trả lời còn tồn tại các quan hệ “ngầm” hay phụ thuộc ngữ cảnh. Ví dụ câu hỏi “Ai là tác giả của Dế mèn phiêu lưu ký?” Một câu trả lời là: “Tô Hoài đã viết tác phẩm văn xuôi Dế mèn phiêu lưu ký”. Hoặc câu hỏi là “Beethoven sinh năm nào?” Thì một câu trả lời là “Ludwig van Beethoven (1770-1827)” Để tìm được câu trả lời cho câu hỏi “Ai là tác giả của Dế mèn phiêu lưu ký?”, hệ thống cần có cơ chế để biết được rằng “tác giả của một tác phẩm là người viết tác phẩm đó” hoặc cần học được các mẫu thường gặp của câu trả lời (các mẫu về ngày tháng năm sinh, về thời gian, địa chỉ….) tương ứng với từng loại câu hỏi. Các hệ thống 4 hỏi đáp hiện nay sử dụng các công cụ xử lý ngôn ngữ tự nhiên như bộ gán nhãn từ loại (POS Tagger), bộ nhận dạng thực thể định danh (Named Entity Recognizer), bộ phân tích ngữ pháp (Parser)… và các tài nguyên ngôn ngữ như Wordnet [11], ontology [23] để phân tích câu hỏi và trích xuất câu trả lời. Hệ thống hỏi đáp đang nhận được rất nhiều sự quan tâm của các nhà nghiên cứu và các doanh nghiệp công nghệ thông tin, có ý nghĩa cả về khoa học lẫn thực tiễn. Rất nhiều hội nghị thường niên về trích chọn thông tin và khai phá dữ liệu dành một chủ đề riêng cho các nghiên cứu về hệ thống hỏi đáp TREC1, CLEF2. Hiện đã có một số hệ thống hỏi đáp ra đời. Một số hệ thống hỏi đáp tiêu biểu được biết đến như: Answer.com3, START4, Ask Jeeves5, Webclopedia [9], FADA [14], Ephyra [22],... trong đó, FADA, Ephyra là các hệ thống hỏi đáp danh sách sẽ được giới thiệu chi tiết hơn ở chương 2. 1.1.2. Một số vấn đề cần quan tâm Năm 2002, John Burger và cộng sự [7] đã đưa ra một số vấn đề cần quan tâm khi xây dựng một hệ thống hỏi đáp như sau:  Loại câu hỏi: Đầu vào của hệ thống hỏi đáp là câu hỏi của người dùng dưới dạng ngôn ngữ tự nhiên. Câu hỏi trong ngôn ngữ tự nhiên rất đa dạng, nhiều ẩn ý, nhiều nhập nhằng và phụ thuộc vào ngữ cảnh hỏi. Một số loại câu hỏi đang được quan tâm trong hệ hống hỏi đáp như câu hỏi về sự vật, sự kiện, định nghĩa, danh sách, quá trình, cách thức, lý do… Mỗi loại câu hỏi có những đặc trưng và khó khăn riêng, đòi hỏi phải có các chiến lược để trả lời chúng.  Xử lý câu hỏi: Một câu hỏi có thể được diễn đạt bằng nhiều cách khác nhau. Vì thế, việc xử lý câu hỏi là xác định được các câu hỏi tương tự, các quan hệ ngữ pháp, loại câu hỏi, đồng thời có thể chuyển một câu hỏi phức tạp thành chuỗi các câu hỏi đơn giản hơn.  Ngữ cảnh: Câu hỏi thường được gắn với ngữ cảnh và câu trả lời cũng được đưa ra trong một ngữ cảnh xác định. Việc sử dụng các thông tin về ngữ cảnh 1TREC: Text REtrieval Conference. 2 CLEF: The Cross-Language Evaluation Forum. 3 4 5 5 giúp hệ thống hỏi đáp hiểu câu hỏi một cách rõ ràng, loại bỏ được các nhặp nhằng và tăng tính chính xác khi trả lời câu hỏi.  Nguồn dữ liệu: một hệ thống hỏi đáp cho dù có hoạt động thông minh đến đâu cũng không thể tìm được chính xác câu trả lời nếu như câu trả lời đó không nằm trong tập dữ liệu. Chính vì thế, hệ thống hỏi đáp cần phải có nguồn dữ liệu phong phú, có thể là sách, báo chí hay các trang web. Tuy nhiên cần đảm bảo nguồn dữ liệu có độ tin cậy và thông tin chính xác cao.  Trích xuất câu trả lời: Việc trích xuất câu trả lời phụ thuộc vào nhiều yếu tố: độ phức tạp của câu hỏi, loại câu hỏi có được từ quá trình xử lý câu hỏi, dữ liệu chứa câu trả lời, phương pháp tìm kiếm và ngữ cảnh,... Câu trả lời cho người dùng cần phải đảm bảo chính xác và đầy đủ. 1.1.3. Các bước xử lý chung Các hệ thống hỏi đáp hiện nay có kiến trúc khác nhau tùy thuộc vào loại hệ thống hỏi đáp. Tuy nhiên các hệ thống hỏi đáp đều bao gồm ba bước cơ bản như hình 1 [5]. Sự khác nhau giữa các hệ thống hỏi đáp là ở quá trình xử lý trong từng bước, đặc biệt là ở cách tiếp cận trong việc xác định câu trả lời. Bước1 - Phân tích câu hỏi: Đây là bước đầu tiên của hệ hỏi đáp. Đầu vào là câu hỏi dưới dạng ngôn ngữ tự nhiên. Tại bước này, hệ thống phân tích câu hỏi để tạo truy vấn cho bước trích chọn tài liệu liên quan và tìm ra những thông tin hữu ích cho bước trích xuất câu trả lời Bước2 - Thu thập tài liệu: Bước này sử dụng câu truy vấn được tạo ra ở bước phân tích câu hỏi, truy vấn trên các công cụ tìm kiếm để tìm các tài liệu phục vụ cho việc tìm kiếm câu trả lời. Bước3 - Trích xuất câu trả lời: Bước này phân tích tập tài liệu đã thu thập được ở bước 2 và sử dụng các thông tin hữu ích do bước phân tích câu hỏi cung cấp để tìm kiếm, trích chọn và đưa ra câu trả lời chính xác nhất cho câu hỏi của người dùng. Phân tích câu hỏi Thu thập tài liệu Trích xuất câu trả lời Câu hỏi Câu trả lời Hình 1. Các bước chung của hệ