Báo cáo Ðánh giá kết quả tìm kiếm của các hệ thống truy tìm thông tin (Phần 1)

Nội dung text: Báo cáo Ðánh giá kết quả tìm kiếm của các hệ thống truy tìm thông tin (Phần 1)

1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH CÔNG TRÌNH NGHIÊN CỨU KHOA HỌC CẤP TRƯỜNG ÐÁNH GIÁ KẾT QUẢ TÌM KIẾM CỦA CÁC HỆ THỐNG TRUYS K C 0 0 3 9 5 9 TÌM THÔNG TIN MÃ SỐ: T2014-49 S KC 0 0 5 4 9 9 Tp. Hồ Chí Minh, 2014
2. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH BÁO CÁO TỔNG KẾT ĐỀ TÀI KH&CN CẤP TRƯỜNG ĐÁNH GIÁ KẾT QUẢ TÌM KIẾM CỦA CÁC HỆ THỐNG TRUY TÌM THÔNG TIN Mã số: T2014-49 Chủ nhiệm đề tài: CN. Quách Đình Hoàng Hồ Chí Minh, Tháng 11/2014
3. TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH KHOA CÔNG NGHỆ THÔNG TIN BÁO CÁO TỔNG KẾT ĐỀ TÀI KH&CN CẤP TRƯỜNG ĐÁNH GIÁ KẾT QUẢ TÌM KIẾM CỦA CÁC HỆ THỐNG TRUY TÌM THÔNG TIN Mã số: T2014-49 Chủ nhiệm đề tài: CN. Quách Đình Hoàng Thành viên đề tài: CN. Quách Đình Hoàng Hồ Chí Minh, Tháng 11/2014
4. Mục lục 1 Mở đầu1 1.1 Tổng quan tình hình nghiên cứu thuộc lĩnh vực đề tài 1 1.2 Tính cấp thiết 4 1.3 Mục tiêu của nghiên cứu 5 1.4 Cách tiếp cận 5 1.5 Phương pháp nghiên cứu 6 1.6 Đối tượng và phạm vi nghiên cứu 6 1.7 Nội dung nghiên cứu 6 2 Tổng quan về truy tìm thông tin7 2.1 Truy tìm thông tin 7 2.2 Hệ thống truy tìm thông tin 8 2.3 Mô hình truy tìm thông tin 10 3 Giới thiệu về đánh giá hệ thống truy tìm thông tin 12 3.1 Tại sao phải đánh giá 12 3.2 Phương pháp Cranfield 15 3.3 Phương pháp của TREC 19 3.3.1 Lịch sử của TREC 19 3.3.2 Kỹ thuật tổng hợp 21 i
5. 3.3.3 Xây dựng bộ sưu tập thử nghiệm 22 4 Các độ đo về độ chính xác của hệ thống truy tìm thông tin 28 4.1 Độ chính xác và độ bao phủ 29 4.2 Độ chính xác ở hạng thứ k (P@k) 30 4.3 R-Precision 30 4.4 Độ chính xác trung bình 31 4.5 Tổng hợp, trung bình và nội suy 31 4.6 Các độ đo khác 32 5 Sử dụng thống kê để so sánh kết quả 34 5.1 Mẫu và quần thể 36 5.2 Xác suất 37 5.3 Kiểm định giả thuyết và lỗi loại 1 39 5.4 Mức độ ảnh hưởng 42 5.5 Khoảng tin cậy 43 5.6 So sánh hai hệ thống 44 6 Thử nghiệm và đánh giá 47 6.1 Chuẩn bị dữ liệu 47 6.2 Đánh giá kết quả 48 7 Kết luận và kiến nghị 52 7.1 Các kết quả đã đạt được 52 7.2 Giới hạn của đề tài 53 7.3 Các kiến nghị 53 Tài liệu tham khảo 54 ii
6. Danh sách hình vẽ 2.1 Hệ thống truy tìm thông tin (phỏng theo Croft [17]) 9 3.1 Kỹ thuật tổng hợp (pooling) [30] 22 6.1 Đồ thị recall-precision 51 iii
7. Danh sách bảng 6.1 Giá trị precision ứng với các mức recall 49 6.2 Độ chính xác ở thứ hạng k (P@k) 50 6.3 Độ chính xác của các phương pháp với khoảng tin cậy 95% dùng t-test 50 6.4 So sánh các phương pháp 51 iv
8. Danh mục các chữ viết tắt • SIGIR - Special Interest Group on Information Retrieval • CIKM - Conference on Information and Knowledge Management • AAAI - Association for the Advancement of Artificial Intelligence • IJCAI - International Joint Conference on Artificial Intelligence • JASIST - Journal of American Society for Information Sciences and Technol- ogy • JASIS - Journal of American Society for Information Sciences • IJCAI - International Joint Conference on Artificial Intelligence • TOIS - ACM Transactions on Information Systems • TKDE - IEEE Transaction on Knowledge and Data Engineering • IPM - Information Processing and Management • TREC - Text Retrieval Conferfence v
9. BM 08T. Thông tin k ết qu ả nghiên c ứu TR ƯỜNG ĐẠ I H ỌC S Ư PH ẠM K Ỹ THU ẬT CNG HOÀ XÃ H I CH NGH A VI T NAM THÀNH PH Ố H Ồ CHÍ MINH c l p - T do - Hnh phúc KHOA CNTT Tp. HCM, ngày tháng n ăm THÔNG TIN K T QU NGHIÊN C U 1. Thông tin chung: - Tên đề tài: Đánh giá k ết qu ả tìm ki ếm c ủa các h ệ th ống truy tìm thông tin - Mã s ố: T2014-49 - Ch ủ nhi ệm: Quách Đình Hoàng - Cơ quan ch ủ trì: Đại h ọc S ư ph ạm K ỹ thu ật Thành ph ố H ồ Chí Minh - Th ời gian th ực hi ện: 1/2014 - 12/2014 2. M c tiêu: - Nghiên c ứu các k ỹ thu ật đánh giá và so sánh các h ệ th ống truy tìm thông tin. 3. Tính m i và sáng t o: - Tổng h ợp các nghiên c ứu v ề đánh giá và so sánh các h ệ th ống truy tìm thông tin. 4. Kt qu nghiên c u: - Báo cáo t ổng k ết v ề các ph ươ ng pháp và các độ đo để đánh giá các h ệ th ống truy tìm thông tin. - Ch ươ ng trình minh h ọa để đánh giá và so sánh k ết qu ả c ủa các ph ươ ng pháp trên m ột t ập dữ li ệu th ử nghi ệm chu ẩn. 5. Sn ph m: - Báo cáo t ổng k ết và ch ươ ng trình minh h ọa 6. Hi u qu , ph ươ ng th c chuy n giao k t qu nghiên c u và kh n ng áp d ng: - Là m ột ngu ồn tài li ệu ph ục v ụ cho nh ững ng ười có nhu c ầu h ọc t ập và nghiên c ứu v ề truy tìm thông tin. Tr ưng ơn v Ch nhi m tài (ký, h ọ và tên, đóng d ấu) (ký, h ọ và tên)
10. Chương 1 Mở đầu 1.1 Tổng quan tình hình nghiên cứu thuộc lĩnh vực đề tài Sự bùng nổ thông tin trong thời đại hiện nay khiến chúng ta đối mặt với vấn đề quá tải thông tin. Do vậy, việc tìm kiếm thông tin một cách nhanh chóng và chính xác ngày càng trở thành một nhu cầu cấp thiết. Một lĩnh vực của khoa học máy tính liên quan nhiều nhất đến việc nghiên cứu và phát triển các kỹ thuật tìm kiếm là truy tìm thông tin (information retrieval). Nói ngắn gọn, đây là một khoa học nền tảng cho các công cụ tìm kiếm. Lĩnh vực này cung cấp các kỹ thuật nền tảng cho việc xây dựng một hệ thống tìm kiếm thông tin nhằm giúp người dùng tìm được thông tin (thường là tài liệu ở dạng văn bản) thỏa mãn nhu cầu của họ (thường được diễn đạt dưới dạng một truy vấn) từ một nguồn thông tin (thường rất lớn) được lưu trữ trên máy tính [1]. Truy tìm thông tin là một lĩnh vực có một truyền thống thực nghiệm lâu đời. Mặc dù đã bắt đầu từ những năm 1960, vấn đề đánh giá độ chính xác của các hệ thống tìm kiếm vẫn là một chủ đề nóng cho đến hiện nay, với nhiều bài báo được 1
11. công bố ở các hội nghị lớn mỗi năm. Để đánh giá một hệ thống truy tìm thông tin, hai tiêu chí chính được sử dụng là mức độ chính xác của kết quả (effectiveness) và thời gian đáp trả của hệ thống (efficiency). Trong phần lớn các nghiên cứu, việc đánh giá và so sánh thực nghiệm giữa các hệ thống chủ yếu tập trung vào tiêu chí về độ chính xác của kết quả. Độ chính xác của một hệ thống thường được đánh giá theo hai cách: (1) tiến hành nghiên cứu trên những người sử dụng hệ thống để đánh giá chất lượng của quá trình tìm kiếm và kết quả (user based evaluation), hoặc (2) phát triển các bộ sưu tập dữ liệu đánh giá chuẩn (standard test collections) và thử nghiệm một hệ thống trên các tập dữ liệu này để đánh giá chất lượng của kết quả tìm kiếm (system based evaluation)[2]. Cách thứ nhất cho phép chúng ta thấy được hiệu quả thực tế của một hệ thống. Tuy nhiên, do sự tham gia của những người dùng khác nhau, rất khó để có thể so sánh hai hệ thống một cách đáng tin cậy và lặp lại thí nghiệm bằng cách sử dụng phương pháp này. Chính vì vậy mà cách thứ hai là cách thường được chọn (cho đến hiện nay) trong việc đánh giá kết quả tìm kiếm của một hệ thống tìm kiếm (đặc biệt là trong nghiên cứu). Cách đánh giá này được đề xuất bởi Cleverdon và các cộng sự vào những năm 1960 [3,4] và thường được gọi là phương pháp đánh giá Cranfield (Cranfield evaluation method). Theo phương pháp này, một bộ sưu tập các tài liệu và các truy vấn sẽ được chọn làm mẫu, sau đó, người ta sẽ đánh giá tất cả các tài liệu ứng với mỗi truy vấn để xác định những tài liệu có liên quan. Một bộ sưu tập đánh giá chuẩn gồm ba thành phần: (1) bộ sưu tập tài liệu (document collection), (2) bộ sưu tập truy vấn (query collection), và (3) các đánh giá về độ liên quan (relevance judgments) cho tất cả các truy vấn. Một tài liệu được giả định là có liên quan hoặc không có liên quan đến truy vấn (binary relevance) hoặc thể hiện mức độ liên quan theo nhiều cấp (graded relevance). Những đánh giá về sự liên quan cho tất cả các truy vấn sau khi thu thập sẽ được sử dụng để xác định tính chính xác của kết quả trả về (thường xếp hạng các các tài liệu liên quan đến câu truy vấn theo thứ tự giảm dần). Một xếp hạng lý tưởng sẽ đưa tất cả các tài liệu 2
12. liên quan lên trên tất cả những tài liệu không liên quan. Phương pháp này được chấp nhận bởi TREC 1 - một hội nghị được tổ chức hằng năm nhằm đánh giá kết quả của các kỹ thuật tìm kiếm. Chương về đánh giá trong sách của van Rijsbergen [5] là một tài liệu mang tính lịch sử về đo lường độ chính xác trong lĩnh vực truy tìm thông tin. Một nguồn hữu ích khác là cuốn sách của TREC [6], trong đó mô tả các bộ sưu tập thử nghiệm, các thủ tục đánh giá được sử dụng và cách chúng được phát triển. Các bài báo của Saracevic [7] và Mizzaro [8] là một trong các nguồn tốt nhất xem xét lại các vấn đề về sự liên quan (relevance) khi đánh giá hệ thống tìm kiếm. Quá trình thu thập đánh giá liên quan và độ tin cậy của các thí nghiệm được thảo luận trong cuốn sách TREC. Zobel [9] cho thấy sự không đầy đủ của các đánh giá liên quan (relevance judgments) không ảnh hưởng đến các thí nghiệm, nhưng Buckley và Voorhees [10] cho rằng nếu các đánh giá liên quan thiếu quá nhiều thì nó có thể là vấn đề. Voorhees và Buckley [11] bàn đến số lượng truy vấn cho mỗi bộ sưu tập thử nghiệm để kết quả so sánh có ý nghĩa. Sanderson và Zobel [12] chứng tỏ rằng phép kiểm định ý nghĩa thống kê được sử dụng có thể ảnh hưởng để độ tin cậy của so sánh. Carterette và các cộng sự [13] mô tả một kỹ thuật để thu giảm số đánh giá liên quan cần có để vẫn đảm bảo độ tin cậy khi so sánh các hệ thống. TREC không những có ảnh hưởng lớn trong việc phổ biến cách tiếp cận dùng bộ sưu tập thử nghiệm để đánh giá độ chính xác của các hệ thống tìm kiếm mà còn có ảnh hưởng lớn đến các độ đo được sử dụng để đánh giá chúng. Nhiều độ đo đã được tạo ra thông qua TREC. Một số độ đo được sử dụng phổ biến là MAP, R-Precision, P@k, DCG, RBP, BPref [6]. Cho trước một bộ sưu tập tài liệu thử nghiệm gồm tập các tài liệu, tập các truy vấn và tập các đánh giá liên quan ứng với mỗi truy vấn, các nhà nghiên cứu có thể sử dụng các độ đo đã đề cập ở trên để tính độ chính xác của phương pháp A và so 1 3
13. sánh nó với độ chính xác của một phương pháp B khác. Tuy nhiên, kết quả của một so sánh như vậy chỉ cho họ biết phương pháp nào là tốt hơn trên bộ sưu tập tài liệu thử nghiệm cho trước. Về mặt lý thuyết, họ thường muốn mở rộng kết luận của mình đi xa hơn bộ sưu tập tài liệu thử nghiệm được dùng để đánh giá phương pháp. Khi các nhà nghiên cứu báo cáo độ chính xác của hệ thống trên một tập các truy vấn, họ ngầm định rằng họ cũng sẽ thu được các kết quả tương tự trên các tập truy vấn khác. Mục đích dự định của hệ thống là độ hiệu quả của nó cũng tương tự trên các truy vấn khác chứ không chỉ dừng lại ở các truy vấn được dùng để thử nghiệm. Phân tích thống kê thường được sử dụng để ước lượng độ chính xác của một đại lượng hoặc cung cấp bằng chứng hỗ trợ cho một giả thuyết và là vấn đề rất được quan tâm trong cộng đồng nghiên cứu về truy tìm thông tin [14]. Smucker và các cộng sự [15] đã tiến hành so sánh các phép kiểm định ý nghĩa thống kê khi so sánh các hệ thống tìm kiếm và kết luận rằng randomization, bootstrap, và t-test cho kết quả gần như nhau đồng thời đề xuất không sử dụng Wilcoxon và sign test vì không ổn định và không tương thích với các phép thử nghiệm trên. Dựa trên kết quả này, các tác giả đề xuất sử dụng randomization test nhưng nếu số liệu thống kê được quan tâm là giá trị trung bình thì nên sử dụng t-test vì nó an toàn, ít vi phạm giả định thông thường. 1.2 Tính cấp thiết Truy tìm thông tin được xem là một lĩnh vực thực nghiệm, do đó, các phương pháp (hệ thống) đề xuất cần được thực chứng và so sánh, mọi trực giác đều có thể không đúng. Việc đánh giá và so sánh các phương pháp (hệ thống) sẽ giúp xác định được những phương pháp thực sự tốt để định hình và thúc đẩy sự phát triển của lĩnh vực. Đánh giá hiệu quả cũng như độ chính xác của hệ thống là một trong những vấn đề quan trọng của lĩnh vực này. Mục tiêu của việc so sánh các phương pháp là để khẳng định được phương 4
14. pháp này là thực sự tốt hơn (chứ không phải là tốt hơn do ngẫu nhiên) phương pháp kia trong việc đạt được mục đích dự định của nó. Không có đánh giá, rất khó để có thể biết được phương pháp nào tốt hơn. Tuy nhiên, để làm được điều này cần có một có một nền tảng về phương pháp đánh giá được xây dựng tốt và đáng tin cậy. Trong đề tài này, chúng tôi tập trung nghiên cứu các vấn đề liên quan đến đánh giá các hệ thống (phương pháp) truy tìm thông tin nhằm thiết lập các nền tảng cho việc so sánh và đánh giá chúng. 1.3 Mục tiêu của nghiên cứu Mục tiêu của nghiên cứu là nghiên cứu tổng quan về lĩnh vực truy tìm thông tin và các kỹ thuật đánh giá và so sánh các hệ thống truy tìm thông tin. Nội dung của nghiên cứu tâp trung vào hai mục tiêu chính sau: • Khảo sát các độ đo để đánh giá và so sánh các hệ thống truy tìm thông tin • Khảo sát các phương pháp đánh giá và so sánh kết quả tìm kiếm của các hệ thống truy tìm thông tin • Các phương pháp thống kê để so sánh hai phương pháp. 1.4 Cách tiếp cận • Tìm hiểu các độ đo để đánh giá và so sánh các hệ thống truy tìm thông tin • Tìm hiểu các phương pháp so sánh kết quả của các hệ thống truy tìm thông tin • Tìm hiểu các phương pháp thống kê để so sánh hai phương pháp. 5
15. 1.5 Phương pháp nghiên cứu • Phương pháp đọc tài liệu (phần khảo sát các nghiên cứu liên quan) • Phương pháp thực nghiệm (phần đánh giá các phương pháp so sánh) 1.6 Đối tượng và phạm vi nghiên cứu Trong đề tài này, chúng tôi chỉ tập trung vào việc đánh giá các hệ thống (phương pháp) tìm kiếm thông tin cho kho dữ liệu gồm những tài liệu tiếng Anh dạng văn bản (text). Ngoài ra, các đối tượng nghiên cứu khác bao gồm: • Các độ đo để đánh giá và so sánh các hệ thống truy tìm thông tin • Các phương pháp so sánh kết quả của các hệ thống truy tìm thông tin • Các phương pháp thống kê để so sánh hai phương pháp. 1.7 Nội dung nghiên cứu Nội dung công việc cụ thể của nghiên cứu gồm: • Nghiên cứu tổng quan về lĩnh vực truy tìm thông tin để có được kiến thức cơ sở về việc xây dựng một hệ thống tìm kiếm. • Khảo sát các độ đo để đánh giá và so sánh các hệ thống truy tìm thông tin • Khảo sát các phương pháp đánh giá và so sánh các hệ thống truy tìm thông tin • Viết báo cáo tổng kết. 6
16. Chương 2 Tổng quan về truy tìm thông tin Truy tìm thông tin là một lĩnh vực cung cấp các kỹ thuật nền tảng cho việc xây dựng một hệ thống tìm kiếm thông tin. Chương này trình bày những kiến thức cơ sở về truy tìm thông tin để có được bức tranh tổng quát cho vấn đề đã nêu. Nội dung của chương là các khái cơ bản của lĩnh vực truy tìm thông tin, gồm: các định nghĩa về truy tìm thông tin, hệ thống và mô hình truy tìm thông tin. 2.1 Truy tìm thông tin Truy tìm thông tin là lĩnh vực quan tâm đến biểu diễn, tổ chức, lưu trữ, và truy cập vào thông tin [16]. Lĩnh vực này nghiên cứu và phát triển những lý thuyết, nguyên lý, thuật toán và hệ thống giúp người dùng tìm được thông tin (thường là tài liệu ở dạng văn bản) thỏa mãn nhu cầu của họ (thường được diễn đạt dưới dạng một câu truy vấn) từ một nguồn thông tin (thường rất lớn) được lưu trữ trên máy tính [1]. Tuy nhiên, theo nghĩa rộng, lĩnh vực này nghiên cứu các vấn đề giúp con người quản lý và khai thác thông tin nói chung như tìm kiếm văn bản (text retrieval), phân loại văn bản (text classification), gom cụm văn bản (text clustering), tóm tắt văn bản (text summarization), trả lời câu hỏi (question answering), tìm kiếm văn 7
17. bản đa ngôn ngữ (cross-language text retrieval), tìm kiếm thông tin đa phương tiện (multimedia retrieval) như hình ảnh, âm thanh, video, [2]. 2.2 Hệ thống truy tìm thông tin Một hệ thống truy tìm thông tin (information retrieval system) được xây dựng để tìm kiếm trên một bộ sưu tập tài liệu (document collection) nhất định, đó có thể là một tập các tài liệu trên máy tính cá nhân (desktop search engine), trong thư viện (digital library), hoặc trên toàn bộ world wide web (web search engine). Hình 2.1 minh họa các quá trình chính của một hệ thống truy tìm thông tin, gồm: biểu diễn truy vấn, biểu diễn nội dung tài liệu, phương pháp so sánh giữa biểu diễn tài liệu với biểu diễn truy vấn để quyết định tài liệu nào là phù hợp với truy vấn và phản hồi (feedback). Quá trình biểu diễn truy vấn thường được gọi là xử lý truy vấn (query processing) hoặc thành lập truy vấn (query formulation), quá trình biểu diễn tài liệu thường được gọi là lập chỉ mục tài liệu (document indexing). Thông thường, các quá trình này chủ yếu liên quan đến việc trích xuất các từ khóa quan trọng, đại diện cho nội dung của truy vấn, tài liệu và xác định trọng số (weight) cho chúng (mức độ quan trọng của các từ khóa đó trong truy vấn, tài liệu) một cách phù hợp. Kết quả của các quá trình này là các biểu diễn bên trong của hệ thống cho mỗi truy vấn và tài liệu. Quá trình so sánh giữa biểu diễn tài liệu và biểu diễn truy vấn để quyết định tài liệu nào phù hợp với truy vấn được gọi là chiến lược tìm kiếm (retrieval strategy). Một chiến lược tìm kiếm sẽ xác định một giá trị thực phản ánh mức độ phù hợp giữa tài liệu với truy vấn cho mỗi tài liệu. Hầu hết các hệ thống truy tìm thông tin giả định rằng người dùng có thể mô tả chính xác nhu cầu thông tin của họ thông qua một số từ khóa. Tuy nhiên, điều này không phải lúc nào cũng dễ dàng đối với người dùng. Khi gặp trường hợp như vậy, người dùng có thể phải mô tả lại nhu cầu thông tin với những từ khóa liên quan 8
18. Hình 2.1: Hệ thống truy tìm thông tin (phỏng theo Croft [17]) và duyệt kết quả mà hệ thống trả về cho đến khi tìm được thông tin mong muốn. Vì vậy, truy tìm thông tin thường không đơn giản là quá trình một chiều: truy vấn được xác định, tài liệu được trả về, người dùng có thể tìm được tài liệu mong muốn hoặc xác định một truy vấn khác. Việc biểu diễn nhu cầu thông tin của người dùng thường là một quá trình động, liên quan đến những đánh giá (judgment), phản hồi (feedback) của người dùng về các tài liệu tìm được (như hình 2.1). Nhu cầu thông tin thật sự của người dùng cũng có thể thay đổi dựa trên những đánh giá này. Dựa vào phản hồi của người dùng về những tài liệu thực sự liên quan đến truy vấn (relevance feedback), hệ thống tự động tạo một truy vấn mới, hy vọng tốt hơn, và quá trình tìm kiếm được lặp lại bằng cách sử dụng truy vấn mới. Tuy nhiên, trong thực tế, người dùng thường ít khi hoặc không muốn cung cấp các phản hồi, nên một phản hồi giả (pseudo relevance feedback) - giả định rằng những tài liệu nằm ở đầu danh sách tài liệu tìm được là có liên quan đến truy vấn, hay một phản hồi ẩn (implicit relevance 9
19. feedback) - giả định rằng những tài liệu được người dùng kích vào để xem là có liên quan đến truy vấn, có thể được thực hiện. Quá trình tương tác liên tục giữa người dùng với hệ thống thông qua việc truy vấn, đáp trả, và phản hồi sẽ giúp hệ thống hiểu được nhu cầu thông tin thật sự của người dùng. 2.3 Mô hình truy tìm thông tin Mục đích chính của bất kỳ một hệ thống tìm kiếm thông tin là xếp hạng các tài liệu theo thứ tự giảm dần mức độ liên quan (relevance) với nhu cầu thông tin của người dùng (user information needs), thường dưới dạng một truy vấn, và loại bỏ những tài liệu không liên quan (non-relevent). Những tài liệu liên quan là những tài liệu mà người dùng mong muốn tìm thấy và được xem như là những tài liệu chứa những câu trả lời được mong đợi cho truy vấn. Để đạt được mục đích này, hệ thống phải đưa ra một cách đánh giá mức độ liên quan giữa một tài liệu (document) bất kỳ với truy vấn (query) thông qua một chiến lược tìm kiếm (retrieval strategy) hay hàm tìm kiếm (retrieval/ranking function) nào đó. Chất lượng của hệ thống phụ thuộc trực tiếp vào chất lượng của chiến lược tìm kiếm này. Việc tìm được một chiến lược tìm kiếm tốt luôn là một thách thức lớn trong việc xây dựng một hệ thống tìm kiếm thông tin. Các chiến lược tìm kiếm được định nghĩa bởi các mô hình truy tìm thông tin (information retrieval model). Mỗi mô hình truy tìm thông tin là một biểu diễn hình thức (formal representation) xác định cách biểu diễn các tài liệu, cách biểu diễn các truy vấn, và phương pháp đánh giá mức độ liên quan giữa tài liệu với truy vấn [16]. Do đó, độ chính xác (effectiveness) của một hệ thống tìm kiếm thông tin phụ thuộc vào tính hợp lý của mô hình truy tìm thông tin bên dưới nó. Các mô hình truy tìm thông tin được nghiên cứu nhiều là mô hình không gian vectơ (vector space model)[18], mô hình xác xuất (probabilistic model)[19, 20] và mô hình ngôn ngữ 10
20. (language model)[21,2]. Mô hình không gian vectơ xem mỗi tài liệu và truy vấn là một vectơ đặc trưng và đánh giá độ liên quan giữa tài liệu và truy vấn dựa trên độ tương tự (similarity) giữa hai vectơ này. Tuy nhiên các đặc trưng là gì, trọng số (giá trị của mỗi đặc trưng) và độ tương tự được tính như thế nào không nằm trong mô hình. Các đặc trưng thường được chọn là các từ đơn (word), hoặc cụm từ (phrase). Một cách đánh giá trọng số rất thành công là "pivoted normalization weighting" của đại học Cornell [22]. Các độ đo thường được dùng để tính độ tương tự là tích trong (dot product) và hệ số cosine giữa hai vector. Một mở rộng của mô hình không gian vec tơ là mô hình latent semantic indexing (LSI)[23]. Mô hình này đưa ra cách thu giảm số chiều của không gian đặc trưng nhằm biểu diễn tốt hơn vectơ tài liệu và truy vấn. Các mô hình xác suất xác định độ liên quan giữa tài liệu d và truy vấn q bằng cách ước lượng "xác suất mà người sử dụng sẽ tìm thấy tài liệu d thỏa mãn câu truy vấn q". Các mô hình ngôn ngữ tìm cách "ước lượng sự phân phối của các từ trong một ngôn ngữ". Mỗi tài liệu được xem như một mẫu ngẫu nhiên (random sample) từ một mô hình ngôn ngữ bên dưới. Các tài liệu được xếp hạng dựa vào khả năng mỗi mô hình ngôn ngữ của nó sinh ra các từ trong câu truy vấn. Gần đây, mô hình learning to rank [24, 25] được đề xuất và nhanh chóng nhận được sự chú ý của nhiều nhóm nghiên cứu. Các mô hình trên khi được tối ưu đều có kết quả tìm kiếm tốt gần như nhau [2]. Tuy nhiên, do có cơ sở toán học vững chắc, mô hình ngôn ngữ và mô hình learning to rank được quan tâm nhiều trong những năm gần đây qua các hội nghị chính về lĩnh vực này như ACM SIGIR 1 và ACM CIKM 2. 1 2 11
21. Chương 3 Giới thiệu về đánh giá hệ thống truy tìm thông tin 3.1 Tại sao phải đánh giá Ý tưởng căn bản làm nền tảng cho khoa học là "tin, nhưng phải kiểm chứng" (trust, but verify). Giả thuyết nghiên cứu nên luôn phải chịu thách thức từ thí nghiệm. Đó là ý tưởng đơn giản nhưng mạnh mẽ, đã tạo ra phần lớn tri thức của nhân loại. Kể từ khi ra đời vào thế kỷ 17, khoa học hiện đại đã thay đổi thế giới đến không còn nhận ra, và làm cho nó ngày càng tốt hơn. Ngày nay, sử dụng thí nghiệm để đánh giá và kiểm tra giả thuyết nghiên cứu đã trở thành một thành phần cơ bản của phương pháp khoa học. Đầu tiên, các nhà nghiên cứu hình thành một giả thuyết, sau đó họ tiến hành xây dựng thí nghiệm để kiểm tra giả thuyết và cuối cùng đánh giá mức độ mà các kết quả thực nghiệm ủng hộ giả thuyết. Một loại thí nghiệm rất phổ biến là thí nghiệm so sánh (comparative experiment/evaluation), trong đó giả thuyết là cho rằng phương pháp A hiệu quả hơn so với phương pháp B, và các thí nghiệm được tiến hành để so sánh kết quả của hai 12
22. S K L 0 0 2 1 5 4