Okapi BM25

Okapi BM25 er en rangeringsfunktion , der bruges af søgemaskiner til at sortere dokumenter efter deres relevans for en given søgeforespørgsel. Den er baseret på en probabilistisk model udviklet i 1970'erne og 1980'erne af Stephen Robertson , Karen Spark Jones og andre.

Selve funktionen kaldes BM25 (BM fra engelsk best match ), men den kaldes ofte "Okapi BM25" efter navnet på Okapi-søgemaskinen, skabt på City University London i 1980'erne og 1990'erne, hvor denne funktion først blev anvendt .

BM25 og dens forskellige senere modifikationer (f.eks. BM25F) er moderne TF-IDF- lignende rangeringsfunktioner, der er meget udbredt i praksis i søgemaskiner. I websøgning er disse rangeringsfunktioner ofte inkluderet som komponenter i en mere kompleks, ofte maskinlært , rangeringsfunktion.

Rangeringsfunktionen

BM25 er en søgefunktion på et uordnet sæt af termer (" pose ord ") og et sæt dokumenter, som det evaluerer baseret på forekomsten af søgeord i hvert dokument uden at tage hensyn til forholdet mellem dem (f.eks. nærhed). Det er ikke en enkelt funktion, men en familie af funktioner med forskellige komponenter og parametre. En almindelig form for denne funktion er beskrevet nedenfor.

Givet en forespørgsel , der indeholder ordene , giver BM25-funktionen følgende vurdering af dokumentets relevans for forespørgslen : $Q$ $q_{1},...,q_{n}$ $D$ $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))))))))),

hvor er ordfrekvensen ( eng. term frequency, TF ) i dokumentet , er længden af dokumentet (antallet af ord i det), og er gennemsnitslængden af dokumentet i samlingen. og er frie koefficienter, vælges de normalt som og . $f(q_{i},D)$ $q_{i}$ $D$ $|D|$ $avgdl$ $k_{1}$ $b$ $k_{1}=2,0$ $b=0,75$

${\text{IDF}}(q_{i})$ der er en omvendt dokumentfrekvens ( eng. invers dokumentfrekvens, IDF ) ord . Der er flere fortolkninger af IDF og små variationer på dens formel. Klassisk er det defineret som: $q_{i}$

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

hvor er det samlede antal dokumenter i samlingen og er antallet af dokumenter, der indeholder . Men oftere bruges "udjævnede" versioner af denne formel, for eksempel: $N$ $n(q_{i})$ $q_{i}$

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

Ovenstående IDF-formel har følgende ulempe. For ord i mere end halvdelen af dokumenterne i samlingen er IDF-værdien negativ. I nærvær af to næsten identiske dokumenter, hvoraf det ene har et ord, og det andet ikke har, kan det andet således få en højere score.

Med andre ord vil ofte forekommende ord ødelægge dokumentets endelige resultat. Dette er uønsket, så i mange applikationer kan ovenstående formel justeres på følgende måder:

Ignorer generelt alle negative udtryk i summen (hvilket svarer til at komme ind på stoplisten og ignorere alle tilsvarende højfrekvente ord);
Pålæg en nedre grænse for IDF : hvis IDF er mindre end , så betragte det som lig med . $\varepsilon$ $\varepsilon$ $\varepsilon$
Brug en anden IDF-formel, der ikke accepterer negative værdier.

Fortolkning af IDF i informationsteori

Antag, at søgeordet forekommer i dokumenter. Så indeholder et tilfældigt udvalgt dokument et ord med sandsynlighed (hvor er kardinaliteten af sættet af dokumenter i samlingen). I dette tilfælde vil informationsværdien af sætningen " indeholder " være som følger: $q$ $n(q)$ $D$ ${\frac {n(q)}{N}}$ $N$ $D$ $q$

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

Antag nu, at der er to søgeord og . Hvis de indtaster dokumentet uafhængigt af hinanden, så er sandsynligheden for at finde dem i et tilfældigt udvalgt dokument som følger: $q_{1}$ $q_{2}$ $D$

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

og indholdet af denne begivenhed

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

Det er nogenlunde det, der udtrykkes af IDF-komponenten i BM25.

Ændringer

Med ekstreme værdier af koefficienten i BM25-funktionen opnås rangordningsfunktioner, kendt som BM11 (at ) og BM15 (at ). [en] $b$ $b=1$ $b=0$
BM25F [2] er en modifikation af BM25, hvor dokumentet betragtes som en samling af flere felter (såsom f.eks. overskrifter, brødtekst, linktekst), hvis længder er uafhængigt normaliserede, og hver af dem kan tildeles sin egen grad af betydning i den endelige rangordningsfunktion.

Noter

↑ Xapian: BM25 vægtningsskema . Dato for adgang: 30. januar 2010. Arkiveret fra originalen 15. marts 2010. (ubestemt)
↑ Hugo Zaragoza, Nick Craswell, Michael Taylor, Suchi Saria og Stephen Robertson. Microsoft Cambridge ved TREC-13: Web- og HARD-spor. Arkiveret 26. august 2009 på Wayback Machine In Proceedings af TREC-2004, 2004.

Litteratur

Stephen E. Robertson, Steve Walker, Susan Jones, Micheline Hancock-Beaulieu og Mike Gatford. Okapi ved TREC-3. I Proceedings of the Third Text Retrieval Conference (TREC 1994). Gaithersburg, USA, november 1994.
Stephen E. Robertson, Steve Walker og Micheline Hancock-Beaulieu. Okapi ved TREC-7. I forløbet af den syvende tekstgenhentningskonference. Gaithersburg, USA, november 1998.
Karen Spärck Jones, Steve Walker og Stephen E. Robertson. En probabilistisk model for informationssøgning: udvikling og sammenlignende eksperimenter (del 1 og 2). Information Processing and Management, 36(6):779-840. 2000.
Nick Craswell, Hugo Zaragoza, Stephen Robertson. Microsoft Cambridge ved TREC-14: Enterprise Track. I Proceedings of the Fourteenth Text Retrieval Conference (TREC 2005). Gaithersburg, USA, november 2005. Beskriver anvendelse og tuning af Okapi BM25F.