Okapi BM25

Trong tìm kiếm thông tin, Okapi BM25 là hàm tính thứ hạng được các công cụ tìm kiếm sử dụng để xếp hạng các văn bản theo độ phù hợp với truy vấn nhất định. Hàm xếp hạng này dựa trên mô hình xác suất, được phát minh ra vào những năm 1970 – 1980. Phương pháp có tên BM25 (BM – best match), nhưng người ta thường gọi "Okapi BM25", vì lần đầu tiên công thức được sử dụng trong hệ thống tìm kiếm Okapi, được sáng lập tại trường đại học London những năm 1980 và 1990.

BM25 là một phương pháp xếp hạng tựa như tf-idf, được sử dụng rộng rãi trong tìm kiếm. Trong Web search những hàm xếp hạng này thường được sử dụng như một phần của các phương pháp tích hợp để dùng trong machine learning, xếp hạng.

== Phương pháp xếp hạng (ranking function) ==
Bm25 – phương pháp tìm kiếm trên một tổ hợp từ, và xếp hạng các tập tài liệu dựa trên từng từ của truy vấn xuất hiện trong tài liệu, mà không quan tâm đến mối quan hệ giữa các từ đó trong từng văn bản. Không phải chỉ là một phương pháp đơn lẻ, mà trên thực tế là cả một tập hợp các phương pháp tính điểm, với những thành phần và thông số hơi khác nhau. Một trong những công thức phổ biến:

Cho một query formula_1, có chứa những từ formula_2, và như vậy BM25 sẽ đưa ra đánh giá độ phù hợp của văn bản formula_3 với truy vấn formula_1:

formula_5
formula_6 TF tần suất xuất hiện của từ formula_7 trong văn bản formula_3

formula_9 số từ trong văn bản formula_3,

và formula_11 độ dài trung bình của văn bản trong tập văn bản.

formula_12 and formula_13 – những hệ số độc lập, thường sẽ được chọn như sau: formula_14 và formula_15. formula_16 - tần số nghịch của từ formula_7. Thường được tính như sau:

formula_18

formula_19 tổng số văn vản trong tập văn bản,
và formula_20 - số văn bản có chứa từ formula_7.

Công thức tính IDF trên có một nhược điểm. Đối với những từ phổ biến, xuất hiện trong hơn một nửa số văn bản trong tập văn bản, IDF sẽ có giá trị âm. Như vậy đối với 2 văn bản tương tự bất kỳ, 1 văn bản có chứa 1 từ, còn văn bản khác không chứa từ đó, thì văn bản không chứa từ đó sẽ có điểm cao hơn.
Như vậy những từ phổ biến sẽ có ảnh hưởng không tốt đến đánh giá văn bản. Vì thế một số trường hợp công thức sẽ được điều chỉnh:
Sử dụng những công thức IDF không có giá trị âm

== Cách hiển thị IDF trong lý thuyết tin học==
Sau đây là cách giải thích từ lý thuyết tin học.
Giả sử cho truy vấn formula_22 xuất hiện trong formula_23 văn bản. Sau đó chọn một văn bản bất kỳ formula_3 có chứa những từ với xác suất formula_25 (formula_19 tổng số văn bản trong tập văn bản). Như vậy, có thể hiểu như sau: "formula_3 chứa formula_22":

Giả sử cho truy vấn gồm 2 từ formula_30 and formula_31. Nếu như cả hai từ xuất hiện độc lập trong văn bản, thì xác suất gặp cả hai từ formula_30 and formula_31 trong văn bản bất kỳ formula_3 được tính:

như vậy:

Với độ biến thiên nhỏ, đây chính là công thức tính yếu tố IDF trong BM25.

==Tham khảo==
- Stephen E. Robertson, Steve Walker, Susan Jones, Micheline Hancock-Beaulieu, and Mike Gatford. Okapi at TREC-3. In Proceedings of the Third Text REtrieval Conference (TREC 1994). Gaithersburg, USA, November 1994.
- Stephen E. Robertson, Steve Walker, and Micheline Hancock-Beaulieu. Okapi at TREC-7. In Proceedings of the Seventh Text REtrieval Conference. Gaithersburg, USA, November 1998.
- Karen Spärck Jones, Steve Walker, and Stephen E. Robertson. A Probabilistic Model of Information Retrieval: Development and Comparative Experiments (parts 1 and 2). Information Processing and Management, 36(6):779-840. 2000.