BM25 (Okapi BM25)
Jak działa
score(D,Q) = Σ IDF(qi) · ( f(qi,D)·(k1+1) ) / ( f(qi,D) + k1·(1 - b + b·|D|/avgdl) ). f(qi,D) = częstość termu qi w dokumencie D, |D| = długość D, avgdl = średnia długość dokumentu. k1 (zwykle 1.2–2.0) kontroluje saturację TF, b (zwykle 0.75) siłę normalizacji długości. IDF używa wariantu probabilistycznego.
Rozwiązany problem
W TF-IDF częstość terminu rośnie liniowo (100 wystąpień = 100× waga) i nie uwzględnia spójnie długości dokumentu. BM25 saturuje wkład kolejnych wystąpień i karze nienaturalnie długie dokumenty.
Komponenty
Człon ( f·(k1+1) ) / ( f + k1·... ) sprawia, że wkład częstości terminu rośnie asymptotycznie zamiast liniowo.
Czynnik (1 - b + b·|D|/avgdl) karze dokumenty dłuższe od średniej, ograniczając ich sztuczną przewagę.
IDF(t) = log((N - df + 0.5)/(df + 0.5) + 1) — wariant wyprowadzony z modelu probabilistycznego relewancji.
Oficjalna
Implementacja
Domyślne k1=1.2, b=0.75 nie są optymalne dla każdego korpusu (np. krótkie tytuły vs długie artykuły).
BM25 dalej dopasowuje leksykalnie; synonimy i parafrazy nie są wychwytywane.
Ewolucja
Robertson i Spärck Jones formułują probabilistyczny model wyszukiwania — teoretyczna podstawa BM25.
Pełna formuła BM25 zaprezentowana w systemie Okapi na konferencji TREC-3.
Robertson i Zaragoza systematyzują rodzinę BM25 (w tym BM25F dla pól) w obszernym przeglądzie.
BEIR pokazuje, że BM25 pozostaje konkurencyjny wobec dense retrieverów w zero-shot retrieval.
Hiperparametry (konfigurowalne osie)
Kontroluje jak szybko wkład częstości terminu się saturuje. Niższe k1 = szybsza saturacja.
Siła normalizacji długości dokumentu: 0 = brak, 1 = pełna.
Złożoność obliczeniowa
Złożoność czasowa: O(|Q| · log N) z odwróconym indeksem. Złożoność przestrzenna: O(Σ nnz) odwrócony indeks.
Paradygmat wykonania
Równoległość
Wymagania sprzętowe
Przechodzenie list postingowych odwróconego indeksu to operacja CPU/IO-bound; brak korzyści z GPU.