Chương 1. Giới thiệu chung. Chương này giới thiệu về mục tiêu và động lực nghiên cứu của luận văn. Tổng quan về xếp hạng.
Chương này trình bày tổng quan về các mô hình xếp hạng truyền thống được sử dụng và phân loại các mô hình xếp hạng. Tổng quan về học máy xếp hạng. Chương này trình bày nền các mô hình học máy xếp hạng được sử dụng trong các hệ thống truy hồi thông tin Chương 4. Giải pháp xếp hạng kết quả tìm kiếm.
Chương này trình bày các công nghệ tính toán song song và đưa ra giải pháp cho bài toán xếp hạng và tính toán song song sử dụng Apache Spark và Elasticsearch. Thực nghiệm và đánh giá. Chương này trình bày về dữ liệu được sử dụng, các giai đoạn xử lý dữ liệu và thực nghiệm, đưa ra kết quả của mô hình, nhận xét và phân tích kết quả thu được. Chương này tổng kết và tóm lược nội dung chính của khóa luận.Tổng quan về xếp hạng Tổng quan về xếp hạng Sự phát triển bùng nổ thông tin của thế giới Web dẫn đến tràn ngập thông tin trên mạng internet.
Một nghiên cứu đã được tiến hành năm 2005[23] chỉ ra rằng thế giới Web chứa khoảng 11.5 tỉ tài liệu tại thời điểm con số được thống kê là tháng 1 năm 2005. Trong cùng năm đó, Yahoo đã thông báo rằng cỗ máy tìm kiếm của họ chứa khoảng hơn 19.2 tài liệu web. Ngày nay con số này đã lên đến hơn 50 triệu tỉ tài liệu đã được đánh chỉ mục trong các cỗ máy tìm kiếm (số liệu được lấy từ trang http://www. Từ những số liệu này chúng ta có thể thấy rằng số lượng tài liệu web đang tăng lên ngày một nhanh.
Với kích thước cực kỳ lớn của thế giới Web rõ ràng rằng người dùng thông thường khó có thể tìm kiếm thông tin mà họ mong muốn bằng cách duyệt và tìm kiếm thông tin trên những trang web. Việc tìm kiếm và trích xuất thông tin đã trở nên quan trọng hơn bao giờ hết, và các công cụ tìm kiếm đã dần dần trở thành một công cụ thiết yếu mà mọi người dùng internet đều sử dụng. Một kiến trúc điển hình của công cụ tìm kiếm được hiển theo hình dưới đây Hình 2-1 Hệ thống tìm kiếm tổng quát [24] Có 6 thành phần chính trong một hệ thống tìm kiếm (Search Engine) là: • Crawler (Bộ thu thập dữ liệu): Thu thập dữ liệu từ trang web và các tài liệu khác từ mạng internet theo sự ưu tiên. • Indexer (Bộ đánh chỉ mục): Có vai trò lấy dữ liệu từ Parser và tạo các chỉ mục từ (term) và các cấu trúc dữ liệu cho phép có thể tìm kiếm nhanh các tài liệu web.
• Link Analyzer (Bộ phân tích liên kết): Lấy dữ liệu từ đồ thị siêu liên kết và xác địch độ quan trọng cho mỗi trang web. Kết quả này có thể để tạo độ ưu tiên được sử dụng cho việc cập nhật lại trang web thông qua Crawler hoặc để xác định như một tham số đặc trưng để xếp hạng. • Query processor (Bộ xử lý truy vấn): Thành phần này nhận các truy vấn từ người dùng sau đó truy vấn được xử lý như loại bỏ các từ phổ biến, sửa lỗi cho truy vấn… sau đó chuyển chúng thành các từ (term) mà hệ thống tìm kiếm có thể hiểu được. • Ranker (Bộ xếp hạng): Đây là thành phần trung tâm của hệ thống tìm kiếm nó chịu trách nhiệm tìm ra tài liệu thích hợp nhất từ truy vấn của người dùng và các tài liệu được đánh mục lục.
Bộ xếp hạng có thể lấy trực tiếp các truy vấn và các tài liệu để tính toán một điểm số (score) sử dụng các công thức heuristic, hoặc cũng có thể trích xuất những đặc điểm giữa các cặp tài liệu và truy vấn để tạo ra điểm số được kết hợp từ những đặc điểm đó. Hệ thống xếp hạng là một thành phần có vai trò trung tâm trong máy tìm kiếm do đó các công ty công nghệ lớn như Yahoo, Google, Microsoft trên thế giới và Cốc Cốc tại Việt Nam thì các thuật toán xếp hạng để cải thiện chất lượng của các cỗ máy tìm kiếm luôn là nhưng lĩnh vực được nghiên cứu nhiều nhất Ngoài ra bộ xếp hạng cũng là thành phần trung tâm của rất nhiều ứng dụng truy hồi thông tin khác như lọc cộng tác, hệ thống hỏi đáp, truy hồi đa phương tiện, tóm tắm văn bản, và các hệ thống quảng cáo trực tuyến. Để giải quyết vấn đề của hệ thống truy hồi thông tin, rất nhiều mô hình xếp hạng heuristic đã được đề xuất và sử dụng trong hệ thống truy hồi thông tin. Trong những năm gần đây, Học máy xếp hạng đã trở thành định hướng nghiên cứu nổi bật trong truy hồi thông tin và một số lượng lớn các bài báo khoa học về vấn đề học máy xếp hạng được xuất bản trong các hội nghị đứng đầu về học máy và truy hồi thông tin.
Hàng năm có rất nhiều các chuyên đề trong hội nghị SIGIR được dành riêng cho chủ đề học máy xếp hạng, Các dataset như LETOR được sử dụng cho chủ đề này cũng được công bố để thuận tiện cho nghiên cứu học máy xếp hạng. Rất nhiều bài báo đã sử dụng dataset này cho việc thực nghiệm và nghiên cứu. Qua đó cũng thấy được tầm quan trọng cũng như mức độ phổ biến của học máy xếp hạng trong các hệ thống truy hồi thông tin. Trong các tài liệu của hệ thống truy hồi thông tin, rất nhiều mô hình xếp hạng đã được đề xuất [5] có thể tạm phân loại 2 mô hình chính đó là mô hình xếp hạng dựa trên độ liên quan (Relevance Ranking Modal) và mô hình xếp hạng dựa trên độ quan trọng (Importance Ranking Models) Mô hình xếp hạng dựa trên độ liên quan Mục tiêu của mô hình xếp hạng dựa trên độ liên quan là tạo ra một danh sách các tài liệu được xếp hạng theo mức độ liên quan giữa tài liệu và truy vấn.
Sau đó sắp xếp tất các các tài liệu theo thứ tự giảm dần theo mức độ liên quan của chúng. Mô hình xếp hạng dựa trên độ liên quan trong hệ thống truy hồi thông tin đầu tiên được dựa trên sự xuất hiện các term của truy vấn trong tài liệu. Ví dụ điển hình cho mô hình này là mô hình Boolean [5]. Về cơ bản mô hình có thể đoán một tài liệu là liên quan hay là không liên quan với truy vấn nhưng không đo được mức độ liên quan.
Một mô hình về đo độ liên quan mới là mô hình không gian Vector (Vector Space modal) được đưa ra [5]. Trong mô hình này tài liệu và truy vấn được nghĩa như là các vector trong một không gian Euclid, trong đó tích trong của 2 vector được sử dụng để đo mức độ liên quan giữa truy vấn và tài liệu. Để tạo ra vector có kết quả tốt nhất thì mỗi term trong không gian vector sẽ có một trọng số, có nhiều phương pháp xếp hạng khác nhau, nhưng tf-idf (term frequency– inverse document frequency) [6] là một phương pháp phổ biến để đánh giá và xếp hạng một từ trong một tài liệu. Về cơ bản thì tf-idf là một hàm xếp hạng giúp chuyển đổi văn bản thành mô hình không gian vector thông qua các trọng số.
Mô hình không gian vector và tf-idf được phát triển bởi Gerard Salton vào đầu thập niên 1960s. TF của một term t trong một vector được định nghĩa là số lần xuất hiện của nó trong tài liệu. IDF được định nghĩa như sau 𝑁 𝐼𝐷𝐹 𝑡 = 𝑙𝑜𝑔 (2.1) 𝑛(𝑡) trong đó N là số lượng tài liệu liệu trong tập hợp truy vấn, và n(t) là số lượng tài liệu mà chứa term t Trong khi mô hình không gian vector bao hàm giả định về việc phụ thuộc giữa các term, Thì mô hình LSI (Laten Semantic Indexing) cố tránh giả định này. Cụ thể, SVD (Singular Value Decomposition) được sử dụng để chuyển đổi không gian tuyến tính các đặc trưng ban đầu thành không gian ngữ nghĩa ẩn (Latent semantic space).
Không gian mới này cũng tương tự như mô hình không gian vector nó được sử dụng để định nghĩa độ liên quan giữa truy vấn và tài liệu. Khi so sánh với mô hình dựa trên xác suất đã tạo được nhiều sự chú ý hơn và đạt được nhiều thành công trong thập kỷ qua. Mô hình nổi tiếng như MB25 và mô hình LMIR (Language model for information retrieval) cả hai có thể phân loại như là mô hình xếp hạng xác suất. Ý tưởng cơ bản của BM25 là xếp hạng tài liệu bằng log và chỉ số odds của mức độ liên quan.
Thực sự thì BM25 không giống như mô hình riêng rẽ, nhưng lại định nghĩa ra hàng loạt mô hình xếp hạng với sự khác nhau giữa các thành phần và các tham số trong công thức. Một trong những cách triển khai phổ biến chỉ số BM25 của một tài liệu d được tính như sau. ) 𝑎𝑣𝑑𝑙 trong đó q là một truy vấn chứa các term t1,…,tm, TF(t,d) là tần suất xuất hiện của term t trong tài liệu d, LEN(d) là tổng độ dài (số các từ) của tài liệu d. và avdl là độ dài trung bình của tài liệu trong tập hợp được lấy ra.
k1 và b là tham số tự chọn, IDF(t) là trọng số IDF của term t được tính bằng công thức trên. LMIR là một ứng dụng của mô hình ngôn ngữ thống kê trong truy hồi thông tin. Một mô hình ngôn ngữ thống kê gán một xác suất đến một chuỗi các term. Khi sử dụng trong hệ thống truy hồi thông tin, một mô hình ngôn ngữ được liên kết với một tài liệu.
Với đầu vào là truy vấn q các tài liệu được xếp hạng dựa trên sự hợp lý (likelihood) của truy vấn đó hoặc xác suất mà mô hình ngôn ngữ của tài liệu sẽ tạo ra term đó trong truy vấn (i. Bằng cách tiếp tục giả định sự độc lập giữa các term do đó 𝑞 G 𝑃 = 𝑃(𝑡𝑖|𝑑) 𝑑 5C9 (2.3) nếu như query q chứa term t1,…,tM Để học mô hình ngôn ngữ của tài liệu, một mô hình hợp lý cực đại (maximum likelihood) được sử dụng, như nhiều phương pháp hợp lý cực đại khác, vấn đề của mình làm mịn ước tính là rất quan trọng. Thông thường một mô hình ngôn ngữ nền tảng ước tính sử dụng toàn bộ tập hợp dữ liệu cho mục đích này. Sau đó, mô hình ngôn ngữ của tài liệu có thể được tạo ra như sau 𝑇𝐹(𝑡5,I ) 𝑃 𝑡5 , 𝑑 = 1 − 𝜆 + 𝜆𝑝 𝑡5 𝐶 (2.4) 𝐿𝐸𝑁(𝑑) Trong đó p(ti|C) là là mô hình ngôn ngữ nền tảng của term ti và 𝜆 ∈ [0,1] nhân tố làm mịn.