Okapi BM25

Okapi BM25 är en rankningsfunktion som används av sökmotorer för att sortera dokument efter deras relevans för en given sökfråga. Den är baserad på en probabilistisk modell utvecklad på 1970- och 1980-talen av Stephen Robertson , Karen Spark Jones och andra.

Själva funktionen heter BM25 (BM från engelska best match ), men den kallas ofta "Okapi BM25" efter namnet på Okapi-sökmotorn, skapad vid City University London på 1980- och 1990-talen, där denna funktion först tillämpades .

BM25 och dess olika senare modifieringar (t.ex. BM25F) är moderna TF-IDF- liknande rankningsfunktioner som ofta används i praktiken i sökmotorer. I webbsökning ingår dessa rankningsfunktioner ofta som komponenter i en mer komplex, ofta maskininlärd rankningsfunktion.

Rangordningsfunktionen

BM25 är en sökfunktion på en oordnad uppsättning termer (" påse med ord ") och en uppsättning dokument, som den utvärderar baserat på förekomsten av frågeord i varje dokument, utan att ta hänsyn till förhållandet mellan dem (till exempel, anslutning). Det är inte en enda funktion, utan en familj av funktioner med olika komponenter och parametrar. En vanlig form av denna funktion beskrivs nedan.

Givet en fråga som innehåller orden ger BM25-funktionen följande bedömning av dokumentets relevans för frågan : $F$ $q_{1},...,q_{n}$ $D$ $F$

{\text{poäng}}(D,Q)=\summa _{{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))))))))),

var är ordfrekvensen ( eng. term frequency, TF ) i dokumentet , är dokumentets längd (antalet ord i det) och är medellängden på dokumentet i samlingen. och är fria koefficienter, väljs de vanligtvis som och . $f(q_{i},D)$ $q_{i}$ $D$ $|D|$ $avgdl$ $k_{1}$ $b$ $k_{1}=2,0$ $b=0,75$

${\text{IDF}}(q_{i})$ det finns en omvänd dokumentfrekvens ( eng. invers dokumentfrekvens, IDF ) ord . Det finns flera tolkningar av IDF och små variationer på dess formel. Klassiskt definieras det som: $q_{i}$

\log {\frac {N}{n(q_{i})}},

var är det totala antalet dokument i samlingen och är antalet dokument som innehåller . Men oftare används "utjämnade" versioner av denna formel, till exempel: $N$ $n(q_{i})$ $q_{i}$

{\text{IDF}}(q_{i})=\log {\frac {Nn(q_{i})+0.5}{n(q_{i})+0.5}},

Ovanstående IDF-formel har följande nackdel. För ord i mer än hälften av dokumenten i samlingen är IDF-värdet negativt. Således, i närvaro av två nästan identiska dokument, varav det ena har ett ord och det andra inte, kan det andra få en högre poäng.

Med andra ord kommer ofta förekommande ord att förstöra dokumentets slutresultat. Detta är oönskat, så i många applikationer kan formeln ovan justeras på följande sätt:

Ignorera i allmänhet alla negativa termer i summan (vilket motsvarar att gå in i stopplistan och ignorera alla motsvarande högfrekventa ord);
Lägg på någon lägre gräns för IDF : om IDF är mindre än , betrakta det som lika med . $\varepsilon$ $\varepsilon$ $\varepsilon$
Använd en annan IDF-formel som inte accepterar negativa värden.

Tolkning av IDF i informationsteori

Antag att sökordet förekommer i dokument. Sedan innehåller ett slumpmässigt utvalt dokument ett ord med sannolikhet (var är kardinaliteten för uppsättningen dokument i samlingen). I det här fallet kommer informationsvärdet för frasen " innehåller " att vara följande: $q$ $n(q)$ $D$ ${\frac {n(q)}{N}}$ $N$ $D$ $q$

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

Anta nu att det finns två sökord och . Om de anger dokumentet oberoende av varandra, är sannolikheten att hitta dem i ett slumpmässigt valt dokument som följer: $q_{1}$ $q_{2}$ $D$

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

och innehållet i denna händelse

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

Detta är ungefär vad som uttrycks av IDF-komponenten i BM25.

Ändringar

Med extrema värden på koefficienten i BM25-funktionen erhålls rankningsfunktioner, kända som BM11 (at ) och BM15 (at ). [ett] $b$ $b=1$ $b=0$
BM25F [2] är en modifiering av BM25, där dokumentet betraktas som en samling av flera fält (såsom till exempel rubriker, brödtext, länktext), vars längder är oberoende normaliserade, och var och en av dem kan tilldelas en egen grad av betydelse i den slutliga rankningsfunktionen.

Anteckningar

↑ Xapian: BM25 Viktningsschema . Datum för åtkomst: 30 januari 2010. Arkiverad från originalet den 15 mars 2010. (obestämd)
↑ Hugo Zaragoza, Nick Craswell, Michael Taylor, Suchi Saria och Stephen Robertson. Microsoft Cambridge på TREC-13: Webb- och HÅRDA spår. Arkiverad 26 augusti 2009 på Wayback Machine In Proceedings of TREC-2004, 2004.

Litteratur

Stephen E. Robertson, Steve Walker, Susan Jones, Micheline Hancock-Beaulieu och Mike Gatford. Okapi vid TREC-3. I Proceedings of the Third Text Retrieval Conference (TREC 1994). Gaithersburg, USA, november 1994.
Stephen E. Robertson, Steve Walker och Micheline Hancock-Beaulieu. Okapi vid TREC-7. Ingår i den sjunde texthämtningskonferensen. Gaithersburg, USA, november 1998.
Karen Spärck Jones, Steve Walker och Stephen E. Robertson. En probabilistisk modell för informationsinhämtning: utveckling och jämförande experiment (del 1 och 2). Information Processing and Management, 36(6):779-840. 2000.
Nick Craswell, Hugo Zaragoza, Stephen Robertson. Microsoft Cambridge på TREC-14: Enterprise Track. I Proceedings of the Fourteenth Text Retrieval Conference (TREC 2005). Gaithersburg, USA, november 2005. Beskriver tillämpning och justering av Okapi BM25F.