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 $Q$, có chứa những từ $q_{1},...,q_{n}$, và như vậy BM25 sẽ đưa ra đánh giá độ phù hợp của văn bản $D$ với truy vấn $Q$:

${\text{score}}(D,Q)=\sum _{i=1}^{n}{\text{IDF}}(q_{i})\cdot {\frac {f(q_{i},D)\cdot (k_{1}+1)}{f(q_{i},D)+k_{1}\cdot (1-b+b\cdot {\frac {|D|}{\text{avgdl}}})}},$

$f(q_{i},D)$ TF tần suất xuất hiện của từ $q_{i}$ trong văn bản $D$

$|D|$ số từ trong văn bản $D$,

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

$k_{1}$ and $b$ – những hệ số độc lập, thường sẽ được chọn như sau: $k_{1}\in [1.2,2.0]$ và $b=0.75$. ${\text{IDF}}(q_{i})$ - tần số nghịch của từ $q_{i}$. Thường được tính như sau:

${\text{IDF}}(q_{i})=\ln({\frac {N-n(q_{i})+0.5}{n(q_{i})+0.5}}+1),$

$N$ tổng số văn vản trong tập văn bản, và $n(q_{i})$ - số văn bản có chứa từ $q_{i}$.

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: bỏ qua tất cả những số hạng có giá trị âm (việc này tương đương với việc cho những từ phổ biển vào stop-list và bỏ qua tất cả những từ phổ biến). Quy định giá trị thấp nhất cho IDF = ε; nếu giá trị IDF nhỏ hơn ε thì tính IDF bằng ε. 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 $q$ xuất hiện trong $n(q)$ văn bản. Sau đó chọn một văn bản bất kỳ $D$ có chứa những từ với xác suất ${\frac {n(q)}{N}}$ ($N$ tổng số văn bản trong tập văn bản). Như vậy, có thể hiểu như sau: "$D$ chứa $q$":

$-\log {\frac {n(q)}{N}}=\log {\frac {N}{n(q)}}.$

Giả sử cho truy vấn gồm 2 từ $q_{1}$ and $q_{2}$. 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ừ $q_{1}$ and $q_{2}$ trong văn bản bất kỳ $D$ được tính:

${\frac {n(q_{1})}{N}}\cdot {\frac {n(q_{2})}{N}},$

như vậy:

$\sum _{i=1}^{2}\log {\frac {N}{n(q_{i})}}.$

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.