Mô hình xếp hạng trong IR
IR
2
Male avatar

Mai Thi An viết ngày 24/10/2018

1. Information Retrieval (IR) là gì?

Truy xuất thông tin hay truy vấn thông tin là cách tổ chức trình bày, lưu trữ và truy cập các mục thông tin. Việc miêu tả và tổ chức thông tin phải theo cách mà người dùng có thể truy cập thông tin đáp ứng nhu câu của mình. Hay nói cách khác, truy xuất thông tin là hoạt động thu thập tài nguyên hệ thống thông tin có liên quan đến nhu cầu thông tin từ tập hợp các nguồn thông tin. Các tìm kiếm có thể dựa trên tìm kiếm toàn văn bản hoặc các chỉ mục.
IR là một khoa học tìm kiếm thông tin trong tài liệu, tìm kiếm tài liệu, siêu dữ liệu mô tả dữ liệu và cho cơ sở dữ liêụ văn bản, hình ảnh hoặc âm thanh.
Các công cụ tìm kiếm trên web là các ứng dụng IR dễ thấy nhất.
Một tính năng khác của truy xuất thông tin là nó không thực sự nạp tài liệu, mà có thể chỉ thông báo cho người dùng về sự tồn tại và nơi lưu trữ các tài liệu liên quan đến câu truy vấn.
Hệ thống truy xuất thông tin thường được thực hiện qua những giai đoạn sau:

  • Crawler: hệ thống tự động phân tích dữ liệu từ nguồn nội dung sau đó bóc tách dữ liệu, thông tin cần thiết theo tiêu chí, yêu cầu của hệ thống.
  • Index: ở giai đoạn này, người dùng sử dụng một câu truy vấn phi cấu trúc,hệ thống phân tích cú pháp (tokenization) thành câu truy vấn hệ thống có thể hiểu được.Hệ thống truy xuất thông tin có thể chất vấn, đối chiếu tìm ra thông tin tìm kiếm hoặc liên quan.Các thủ tục được dùng để quyết định các yếu tố thông tin có liên quan đến câu truy vấn đều dựa trên biểu diễn của các câu truy vấn và các yếu tố thông tin có chứa các thành phần ngôn ngữ chỉ mục (index).
  • Ranking: hệ thống trả về cho người dùng những tài liệu, chỉ mục liên quan được xếp theo mức độ liên quan, tầm quan trọng dựa vào câu truy vấn.
  • Relevance Feedback: là một trong những cách tinh chỉnh thứ hạng công cụ tìm kiếm một cách cổ điển nhất. Hệ thống đưa ra thứ tự liên quan của truy vấn, người dùng lựa chọn các bản ghi phù hợp với bản thân. Hệ thống ghi nhận và cải thiện bản xếp hạng của mình.

2. Các mô hình xếp hạng truyền thống

Mô hình xếp hạng là hệ thống giải quyết hoặc xây dựng các vấn đề khác nhau của IR.
Thông thường, mô hình xếp hạng được viết gọn trong 4 chữ D, Q, F, R. Trong đó các chữ được định nghĩa như sau:

  • D(Document collection) là bộ sưu tập tài liệu. Mỗi tài liệu được mô hình hóa như một nhóm các thuật ngữ chỉ mục trong đó các thuật ngữ chỉ mục được giả định là độc lập với nhau.
  • Q (Query collection) là bộ sưu tập truy vấn. Các truy vấn được kích hoạt bởi người dùng thuộc về tập hợp này. Nó cũng được mô hình hóa như một tập các thuật ngữ chỉ mục cho các trường hợp.
  • F là Framwork cho mô hình mô tả tài liệu, các câu truy vấn và mối quan hệ giữa chúng.
  • R (Ranking function) là một hàm xếp hạng liên kết một điểm (số thực) với cặp (qi, dj) trong đó qi ∈ Q và dj ∈ D. Cho truy vấn (qi) các tài liệu được xếp hạng theo điểm số.

2.1. Mô hình Boolean

Là mô hình truy xuất thông tin lâu đời và đơn giản nhất. Mô hình sử dụng các lý thuyết tập hợp và các toán tử Booolean như NOT, OR, AND. Các tài liệu được truy xuất là các tài liệu hoàn toàn khớp với truy vấn đã cho, tuy nhiên các tài liệu liên quan không được đề cập đến.
Ví dụ dưới đây để hiểu rõ về bài toán.
Hệ thống có 4 bản ghi như sau:

  • Doc1 : Nhà ở Cầu Giấy
  • Doc2 : 20m2
  • Doc3 : 3 phòng ngủ
  • Doc4 : Nhà ở Cầu giấy, 50m2 Để trả lời cho câu query Nhà ở Cầu Giấy, không phải 20m2. Hệ thống sẽ phân tích thành Nhà AND Cầu Giấy AND NOT 20m2 Dưới đây là biểu diễn có hoặc không xuất hiện trong doc của các index

Bảng index
Sử dụng phép toán AND ta có:
1001(Nhà)AND1001(Cầu Giấy)AND1011(không 20m2) = 1001
kết quả hệ thống sẽ đưa ra cho bạn Doc4, Doc1.

Ưu điểm:

  • Dễ hiểu, dễ làm
  • Tốc độ tìm kiếm nhanh với khối lượng database không lớn.
  • Tìm kiếm chính xác những gì người dùng yêu cầu.

->Chính vì thế thuật toán vẫn được sử dụng rộng rãi trong các quy mô tìm kiếm nhỏ như email, ổ cứng.

Nhược điểm:

  • Mô hình có tốc độ tìm kiếm khá chậm với các khối lượng dữ liệu lớn.
  • Không thể biểu diễn các câu truy vấn phức tạp.
  • Những tài liệu liên quan cũng không được đề cập.
  • Hệ thống cũng không bắt được tài liệu chứa từ đồng nghĩa.
  • Thường các bản ghi khó được xếp hạng các bản ghi đã được truy vấn.

2.2. Mô hình không gian vector

Vấn đề của mô hình Boolean là không có khả năng tìm nạp các thành phần thiếu trong quy trình chấm điểm với các bản ghi đã được truy vấn. Điều này làm cho việc ranking trở nên khó khăn, vấn đề này được giải quyết trong mô hình không gian vector.
Mô hình không gian vector là mô hình thể hiện thông tin văn bản như một vector, các phần tử của vector này thể hiện mức độ quan trọng của một từ và cả sự xuất hiện hay không xuất hiện của nó trong một tài liệu.
Mô hình này biểu diễn văn bản như những điểm trong không gian Euclid n-chiều, mỗi chiều tương ứng với một từ trong tập hợp các từ. Phần tử thứ i, là di của vector văn bản cho biết số lần mà từ thứ i xuất hiện trong văn bản. Sự tương đồng của hai văn bản được định nghĩa là khoảng cách giữa các điểm, hoặc là góc giữa những vector trong không gian.
Tần số : là tần số xuất hiện của từ, hoặc cụm từ i trong tài liệu dj được biểu diễn bằng công thức dưới đây
alt text
trong đó freqi,j là số lần cụm từ i, xuất hiện trong tài liệu dj
Tần suất ngịch đảo của tài liệu: nếu tần số biểu hiện cho các từ xuất hiện nhiều trong văn bản cho biết độ phổ biến của từ đó trong hệ thống của mình, thì tìm tần số nghịch đảo cho ta cái nhìn về những từ hiếm xuất hiện trong các tài liệu của mình để mang thông tin đắt giá hơn. Tần suất nghịch đảo được biểu diễn bằng công thức dưới đây.
alt text
Trong đó, ni là số các văn bản có từ hoặc cụm từi, N là tổng số văn bản.
Độ tương đồng giữa 2 vector: Để xếp hạng các tài liệu mà chúng ta có (và trả về các tài liệu có hạng cao), thì chúng ta so sánh câu truy vấn với tập hợp tài liệu. Tài liệu nào càng gần với câu truy vấn thì có điểm cao hơn. Người ta thường sử dụng phương pháp dưới đây:
alt text
Trong đó theta là góc tạo bởi 2 vector di, q.
Ranking: Mô hình xếp hạng các tài liệu bằng việc đánh giá góc giữa tài liệu và câu truy vấn.

Ưu điểm:

  • Có thể xếp hạng bằng các kết quả tương đồng.
  • Kết quả trả về trong khoảng từ 0 đến 1 nên có thể phù hợp với truy vấn.

Hạn chế:

  • Các chỉ mục độc lập với nhau nên khi truy vấn có thể làm mất nghĩa của cả câu.
  • Không có được cái nhìn logic như mô hình Boolean.

2.3. Mô hình xác suất -BM25

Mô hình xác suất mang ý tưởng cơ bản là lấy các tài liệu dựa trên xác suất của tài liệu có liên quan.
Mô hình Okapi BM25 là mô hình mở rộng của mô hình xác suất. Mô hình Okapi BM25(Best Macth) hay BM25. Mô hình được sử dụng lần đầu tiên trong hệ thống tìm kiếm Okapi. Điểm xếp hạng của BM25 được tính theo công thức dưới đây:
alt text

Trong đó, avgdl là độ dài trung bình của văn bản trong toàn tập văn bản.
k1b là hệ số độc lập, k1 thuộc [1.2, 2.0] và b = 0,75.
Mô hình cải thiện được những điểm yếu của hai mô hình trên.

3. Kết luận

Bài viết đưa ra cái nhìn cơ bản về hệ thống truy xuất thông tin. Những mô hình truyền thống vẫn được áp dụng rất nhiều ở những website cơ bản. Trong bài viết tới, mình sẽ giới thiệu về các mô hình mới và có chiều sâu hơn.

4.Danh mục tài liệu tham khảo

https://www.cse.iitb.ac.in/internal/techreports/reports/TR-CSE-2010-31.pdf

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

Male avatar

Mai Thi An

2 bài viết.
0 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
Male avatar
3 2
1. Elastic search là gì? Elasticsearch là công cụ tìm kiếm và lưu trữ toàn văn bản, có khả năng mở rộng cao. Nó cho phép chúng ta lưu trữ, tìm kiếm...
Mai Thi An viết 11 tháng trước
3 2
Bài viết liên quan
White
46 5
Dạo này Rust đang nổi lên như một thế lực khiến một hispter như mình không thể không để tâm. Sau vài ngày dig deeper vào Rust, mình cho rằng Rust l...
Thach Le viết hơn 2 năm trước
46 5
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


Male avatar
{{userFollowed ? 'Following' : 'Follow'}}
2 bài viết.
0 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!