Okapi BM25

W wyszukiwaniu informacji Okapi BM25 (BM to skrót od ang. best matching) jest funkcją rankingową używaną przez wyszukiwarki do szacowania trafności dokumentów względem zadanego zapytania. Opiera się na probabilistycznym podejściu do wyszukiwania informacji rozwijanym w latach 70. i 80. XX wieku m.in. przez Stephena E. Robertsona(inne języki), Karen Spärck Jones.

Właściwa nazwa funkcji rankingowej to BM25. Pełniejsza nazwa Okapi BM25 obejmuje nazwę pierwszego systemu, który ją wykorzystywał – systemu wyszukiwania informacji Okapi, zaimplementowanego w latach 80. i 90. XX wieku w Londynie na City University (obecnie w strukturach University of London).^[1] BM25 oraz jego nowsze warianty, np. BM25F (odmiana BM25 uwzględniająca strukturę dokumentu i m.in. tekst zakotwiczeń), należą do rodziny funkcji wyszukiwania podobnych do TF-IDF, stosowanych w wyszukiwaniu dokumentów.^[2]

BM25 jest funkcją wyszukiwania opartą na modelu „worka słów” (bag-of-words), która porządkuje zbiór dokumentów według dopasowania do zapytania na podstawie występowania terminów zapytania w dokumencie, niezależnie od ich bliskości w tekście. Jest to rodzina funkcji punktujących o nieznacznie różniących się składowych i parametrach. Jedna z najczęściej przytaczanych postaci ma następującą formę.

Dla zapytania ${\displaystyle Q}$, zawierającego słowa kluczowe ${\displaystyle q_{1},\ldots ,q_{n}}$, wynik BM25 dla dokumentu ${\displaystyle D}$ wyraża się wzorem:

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

gdzie ${\displaystyle f(q_{i},D)}$ oznacza liczbę wystąpień słowa kluczowego ${\displaystyle q_{i}}$ w dokumencie ${\displaystyle D}$, ${\displaystyle |D|}$ jest długością dokumentu (liczbą słów), a ${\displaystyle \mathrm {avgdl} }$ jest średnią długością dokumentu w kolekcji, z której pochodzą dokumenty. Parametry ${\displaystyle k_{1}}$ oraz ${\displaystyle b}$ są parametrami swobodnymi; w praktyce (bez zaawansowanej optymalizacji) często przyjmuje się ${\displaystyle k_{1}\in [1{,}2,2{,}0]}$ i ${\displaystyle b=0{,}75}$.^[3] Składowa ${\displaystyle \mathrm {IDF} (q_{i})}$ jest wagą IDF (inverse document frequency) dla terminu ${\displaystyle q_{i}}$, zwykle obliczaną jako:

${\displaystyle \mathrm {IDF} (q_{i})=\ln \left({\frac {N-n(q_{i})+0.5}{n(q_{i})+0.5}}+1\right)}$

gdzie ${\displaystyle N}$ jest liczbą dokumentów w kolekcji, a ${\displaystyle n(q_{i})}$ jest liczbą dokumentów zawierających termin ${\displaystyle q_{i}}$.

Istnieje kilka interpretacji IDF oraz drobne warianty tego wzoru. W oryginalnym wyprowadzeniu BM25 składnik IDF wynika z binarnego modelu niezależności.

Jedną z interpretacji można sformułować na gruncie teorii informacji. Załóżmy, że termin zapytania ${\displaystyle q}$ występuje w ${\displaystyle n(q)}$ dokumentach. Wówczas losowo wybrany dokument ${\displaystyle D}$ zawiera ten termin z prawdopodobieństwem ${\displaystyle {\frac {n(q)}{N}}}$, gdzie ${\displaystyle N}$ jest liczbą dokumentów w kolekcji. Zawartość informacyjna komunikatu „${\displaystyle D}$ zawiera ${\displaystyle q}$” wynosi więc:

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

Jeśli mamy dwa terminy zapytania ${\displaystyle q_{1}}$ i ${\displaystyle q_{2}}$, a ich występowanie w dokumentach jest całkowicie niezależne, to prawdopodobieństwo, że oba wystąpią w losowo wybranym dokumencie ${\displaystyle D}$, wynosi:

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

a zawartość informacyjna takiego zdarzenia jest równa:

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

Z niewielką modyfikacją jest to dokładnie to, co wyraża składnik IDF w BM25.

• Dla skrajnych wartości współczynnika ${\displaystyle b}$ BM25 przechodzi w funkcje rankingowe znane jako BM11 (dla ${\displaystyle b=1}$) oraz BM15 (dla ${\displaystyle b=0}$).^[4]
• BM25F jest modyfikacją BM25, w której dokument traktuje się jako złożony z wielu pól (np. nagłówków, tekstu głównego, tekstu zakotwiczeń) o potencjalnie różnej ważności, innym nasyceniu trafności oraz odmiennym sposobie normalizacji długości. BM25F definiuje każdy typ pola jako strumień i stosuje wagę per strumień, aby przeskalować wkład danego pola w końcowy wynik.^[5][2] Jest ona też opisywana jako „BM25 z rozszerzeniem na wiele ważonych pól”.^[6]
• BM25+ jest rozszerzeniem BM25 opracowanym w celu rozwiązania jednej z jego słabości: składnik normalizacji częstości terminu przez długość dokumentu nie ma właściwego dolnego ograniczenia, przez co długie dokumenty dopasowane do terminu potrafią otrzymywać wynik zbliżony do krótszych dokumentów, które w ogóle nie zawierają terminu. BM25+ wprowadza dodatkowy parametr ${\displaystyle \delta }$ (często domyślnie ${\displaystyle 1{,}0}$, gdy brak danych uczących), a wzór na wynik ma postać:^[7]

${\displaystyle \mathrm {score} (D,Q)=\sum _{i=1}^{n}\mathrm {IDF} (q_{i})\cdot \left[{\frac {f(q_{i},D)\cdot (k_{1}+1)}{f(q_{i},D)+k_{1}\cdot \left(1-b+b\cdot {\frac {|D|}{\mathrm {avgdl} }}\right)}}+\delta \right]}$

• Stephen E.S.E. Robertson Stephen E.S.E., SteveS. Walker SteveS., SusanS. Jones SusanS., MichelineM. Hancock-Beaulieu MichelineM., MikeM. Gatford MikeM., Okapi at TREC-3, [w:] Proceedings of the Third Text REtrieval Conference (TREC 1994), Gaithersburg 1994  (ang.). typ?
• Stephen E.S.E. Robertson Stephen E.S.E., SteveS. Walker SteveS., MichelineM. Hancock-Beaulieu MichelineM., Okapi at TREC-7, [w:] Proceedings of the Seventh Text REtrieval Conference, Gaithersburg 1998  (ang.). typ?
• K. SpärckK.S. Jones K. SpärckK.S., S.S. Walker S.S., S.E.S.E. Robertson S.E.S.E., A probabilistic model of information retrieval: Development and comparative experiments: Part 1, „Information Processing & Management”, 36 (6), 2000, s. 779–808, DOI: 10.1016/S0306-4573(00)00015-7  (ang.).
• K. SpärckK.S. Jones K. SpärckK.S., S.S. Walker S.S., S.E.S.E. Robertson S.E.S.E., A probabilistic model of information retrieval: Development and comparative experiments: Part 2, „Information Processing & Management”, 36 (6), 2000, s. 809–840, DOI: 10.1016/S0306-4573(00)00016-9  (ang.).
• StephenS. Robertson StephenS., HugoH. Zaragoza HugoH., The Probabilistic Relevance Framework: BM25 and Beyond, „Foundations and Trends in Information Retrieval”, 3 (4), 2009, s. 333–389, DOI: 10.1561/1500000019  (ang.).

• Stephen Robertson, Hugo Zaragoza: The Probabilistic Relevance Framework: BM25 and Beyond (2009) – pełny tekst (PDF)