Okapi BM25

Inom informationssökning är Okapi BM25 ( BM är en förkortning av bästa matchning ) en rankningsfunktion som används av sökmotorer för att uppskatta dokumentens relevans för en given sökfråga. Den är baserad på den probabilistiska återvinningsram som utvecklades på 1970- och 1980-talen av Stephen E. Robertson, Karen Spärck Jones och andra.

Namnet på den faktiska rankningsfunktionen är BM25 . Det fullständigare namnet, Okapi BM25 , inkluderar namnet på det första systemet som använde det, vilket var Okapi informationshämtningssystem, implementerat vid Londons City University på 1980- och 1990-talen . BM25 och dess nyare varianter, t.ex. BM25F (en version av BM25 som kan ta hänsyn till dokumentstruktur och ankartext), representerar TF-IDF- liknande hämtningsfunktioner som används vid dokumenthämtning. ^{[ citat behövs ]}

Rangordningsfunktionen

BM25 är en säck-of-words hämtningsfunktion som rangordnar en uppsättning dokument baserat på söktermerna som förekommer i varje dokument, oavsett deras närhet i dokumentet. Det är en familj av poängfunktioner med lite olika komponenter och parametrar. En av de mest framträdande instansieringarna av funktionen är följande.

Givet en fråga $Q$ , som innehåller nyckelord $q_{1},...,q_{n}$ , BM25-poängen för ett dokument $D$ är:

{\text{score}}(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 \left(1-b+b\cdot { \frac {|D|}{\text{avgdl}}}\right)}}

där $f(q_{i},D)$ är antalet gånger som $q_{i}$ förekommer i dokumentet $D$ , $|D|$ är längden på dokumentet $D$ i ord, och $avgdl$ är den genomsnittliga dokumentlängden i textsamlingen som dokumenten hämtas från. $k_{1}$ och $b$ är fria parametrar, vanligtvis valda, i frånvaro av en avancerad optimering, som $k_{1}\in [1.2,2.0]$ och $b=0,75$ . ${\text{IDF}}(q_{i})$ är IDF-vikten ( invers dokumentfrekvens ) för frågetermen $q_{i}$ . Det beräknas vanligtvis som:

{\text{IDF}}(q_{i})=\ln \left( {\frac {Nn(q_{i})+0.5}{n(q_{i})+0.5}}+1\höger)

där $N$ är det totala antalet dokument i samlingen och $n(q_{i})$ är antalet dokument som innehåller $q_{i}$ .

Det finns flera tolkningar för IDF och små variationer på dess formel. I den ursprungliga BM25-härledningen är IDF-komponenten härledd från den binära oberoendemodellen .

IDF informationsteoretisk tolkning

Här är en tolkning från informationsteori. Antag att en frågeterm $q$ förekommer i $n(q)$ dokument. Sedan kommer ett slumpmässigt valt dokument $D$ att innehålla termen med sannolikhet ${\displaystyle {\frac {n(q)}{N}}} ($ där $N$ återigen är kardinalitet av uppsättningen dokument i samlingen). Därför är informationsinnehållet i meddelandet " $D$ innehåller ${\displaystyle q} ":$

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

Anta nu att vi har två frågetermer $q_{1}$ och $q_{2}$ . Om de två termerna förekommer i dokument helt oberoende av varandra, då är sannolikheten att se både $q_{1}$ och $q_{2}$ i ett slumpmässigt valt dokument $D$ är:

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

och informationsinnehållet för en sådan händelse är:

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

Med en liten variation är detta precis vad som uttrycks av IDF-komponenten i BM25.

Ändringar

Vid de extrema värdena av koefficienten $b$ förvandlas BM25 till rangordningsfunktioner kända som BM11 (för $b=1$ ) och BM15 (för $b=0$ ).
BM25F (eller BM25-modellen med utvidgning till flera viktade fält ) är en modifiering av BM25 där dokumentet anses vara sammansatt av flera fält (som rubriker, huvudtext, ankartext) med möjligen olika grad av betydelse, termrelevans mättnad och längdnormalisering. BM25F definierar varje typ av fält som en ström , och tillämpar en viktning per ström för att skala varje ström mot den beräknade poängen.

BM25+ är en förlängning av BM25. BM25+ utvecklades för att åtgärda en brist hos standarden BM25 där komponenten av termfrekvensnormalisering genom dokumentlängd inte är korrekt nedre gräns; Som ett resultat av denna brist kan långa dokument som stämmer överens med söktermen ofta bedömas orättvist av BM25 som att de har liknande relevans som kortare dokument som inte alls innehåller frågetermen. Poängformeln för BM25+ har bara en ytterligare ledig parameter $\delta$ (ett standardvärde är $1,0$ i frånvaro av träningsdata) jämfört med BM25:

{\ text{poäng}}(D,Q)=\summa _{i=1}^{n}{\text{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|} {\text{avgdl}}}\right)}}+\delta \right]

Allmänna referenser

Stephen E. Robertson; Steve Walker; Susan Jones; Micheline Hancock-Beaulieu & Mike Gatford (november 1994). Okapi vid TREC-3 . Proceedings of the Third Text Retrieval Conference (TREC 1994) . Gaithersburg, USA.
Stephen E. Robertson; Steve Walker & Micheline Hancock-Beaulieu (november 1998). Okapi vid TREC-7 . Proceedings of the Seventh Text Retrieval Conference . Gaithersburg, USA.
Spärck Jones, K. ; Walker, S.; Robertson, SE (2000). "En probabilistisk modell för informationssökning: Utveckling och jämförande experiment: Del 1". Informationsbehandling och hantering . 36 (6): 779–808. CiteSeerX 10.1.1.134.6108 . doi : 10.1016/S0306-4573(00)00015-7 .
Spärck Jones, K. ; Walker, S.; Robertson, SE (2000). "En probabilistisk modell för informationssökning: Utveckling och jämförande experiment: Del 2". Informationsbehandling och hantering . 36 (6): 809–840. doi : 10.1016/S0306-4573(00)00016-9 .
Stephen Robertson & Hugo Zaragoza (2009). "The Probabilistic Relevance Framework: BM25 and Beyond" . Grunder och trender inom informationssökning . 3 (4): 333–389. CiteSeerX 10.1.1.156.5282 . doi : 10.1561/1500000019 .

externa länkar

Robertson, Stephen ; Zaragoza, Hugo (2009). The Probabilistic Relevance Framework: BM25 and Beyond (PDF) . NOW Publishers, Inc. ISBN 978-1-60198-308-4 .