Okapi BM25

Okapi BM25 on sijoitustoiminto , jota hakukoneet käyttävät asiakirjojen lajitteluun niiden osuvuuden mukaan tiettyyn hakukyselyyn. Se perustuu Stephen Robertsonin , Karen Spark Jonesin ja muiden 1970- ja 1980-luvuilla kehittämään todennäköisyysmalliin.

Itse toimintoa kutsutaan nimellä BM25 (BM englanninkielisestä best matchistä), mutta sitä kutsutaan usein nimellä "Okapi BM25" Lontoon City Universityssä 1980- ja 1990-luvuilla luodun Okapi-hakukoneen mukaan , jossa tätä funktiota käytettiin ensimmäisen kerran. .

BM25 ja sen monet myöhemmät muunnelmat (esim. BM25F) ovat nykyaikaisia TF-IDF :n kaltaisia rankingfunktioita, joita käytetään laajasti käytännössä hakukoneissa. Verkkohaussa nämä sijoitusfunktiot sisältyvät usein monimutkaisemman, usein koneoppitun sijoitusfunktion komponentteina.

Ranking-toiminto

BM25 on hakutoiminto järjestämättömästä termien joukosta (" pussi sanaa ") ja joukosta asiakirjoja, jotka se arvioi kunkin asiakirjan kyselysanojen esiintymisen perusteella ottamatta huomioon niiden välistä suhdetta (esim. läheisyys). Se ei ole yksittäinen funktio, vaan funktioperhe, jossa on erilaisia komponentteja ja parametreja. Yksi tämän toiminnon yleinen muoto on kuvattu alla.

Kun kysely sisältää sanat , BM25-funktio antaa seuraavan arvion asiakirjan merkityksestä kyselyn kannalta : $K$ $q_{1},...,q_{n}$ $D$ $K$

{\text{score}}(D,Q)=\sum _{{i=1}}^{{n}}{\text{IDF}}(q_{i})\cdot {\frac {f( q_{i},D)\cpiste (k_{1}+1)}{f(q_{i},D)+k_{1}\cpiste (1-b+b\cpiste {\frac {|D| }{{\text{avgdl)))))))),

missä on sanan tiheys ( eng. term Frequency, TF ) asiakirjassa , on asiakirjan pituus (sanojen lukumäärä siinä) ja on asiakirjan keskimääräinen pituus kokoelmassa. ja ovat vapaita kertoimia, ne valitaan yleensä muodossa ja . $f(q_{i},D)$ $q_{i}$ $D$ $|D|$ $avgdl$ $k_{1}$ $b$ $k_{1}=2,0$ $b = 0,75$

${\text{IDF}}(q_{i})$ on olemassa käänteinen asiakirjataajuus ( eng. käänteinen asiakirjataajuus, IDF ) sanat . IDF:stä on useita tulkintoja ja pieniä vaihteluita sen kaavassa. Klassisesti se määritellään seuraavasti: $q_{i}$

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

missä on kokoelman asiakirjojen kokonaismäärä ja . Mutta useammin käytetään tämän kaavan "tasoitettuja" versioita, esimerkiksi: $N$ $n(q_{i})$ $q_{i}$

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

Yllä olevalla IDF-kaavalla on seuraava haittapuoli. Sanojen yli puolessa kokoelman asiakirjoista IDF-arvo on negatiivinen. Siten kahden lähes identtisen asiakirjan läsnä ollessa, joista toisessa on sana ja toisessa ei, toinen voi saada korkeamman pistemäärän.

Toisin sanoen usein esiintyvät sanat pilaavat asiakirjan lopputuloksen. Tämä ei ole toivottavaa, joten monissa sovelluksissa yllä olevaa kaavaa voidaan säätää seuraavilla tavoilla:

Jätä yleensä huomioimatta kaikki negatiiviset termit summassa (mikä vastaa lopetusluetteloon pääsyä ja kaikkien vastaavien korkean taajuuden sanojen huomioimista);
Aseta IDF: lle jokin alaraja : jos IDF on pienempi kuin , katso se yhtä suureksi kuin . $\varepsilon$ $\varepsilon$ $\varepsilon$
Käytä toista IDF-kaavaa, joka ei hyväksy negatiivisia arvoja.

IDF:n tulkinta informaatioteoriassa

Oletetaan, että hakusana esiintyy asiakirjoissa. Sitten satunnaisesti valittu asiakirja sisältää sanan todennäköisyydellä (missä on kokoelman dokumenttijoukon kardinaliteetti). Tässä tapauksessa lauseen " sisältää " tietoarvo on seuraava: $q$ $n(q)$ $D$ ${\frac {n(q)}{N}}$ $N$ $D$ $q$

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

Oletetaan nyt, että hakusanaa on kaksi ja . Jos he syöttävät asiakirjan toisistaan riippumatta, todennäköisyys löytää ne satunnaisesti valitusta asiakirjasta on seuraava: $q_{1}$ $q_{2}$ $D$

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

ja tämän tapahtuman sisältö

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

Tämä on suunnilleen se, mitä IDF-komponentti ilmaisee BM25:ssä.

Muutokset

BM25-funktion kertoimen ääriarvoilla saadaan järjestysfunktiot, jotka tunnetaan nimellä BM11 (at ) ja BM15 (at ). [yksi] $b$ $b = 1$ $b = 0$
BM25F [2] on BM25:n muunnos, jossa asiakirjaa pidetään useiden kenttien kokoelmana (kuten esimerkiksi otsikot, leipäteksti, linkkiteksti), joiden pituudet on itsenäisesti normalisoitu ja joista jokainen on voidaan määrittää oma merkityksensä lopullisessa järjestysfunktiossa.

Muistiinpanot

↑ Xapian: BM25-painotuskaavio . Käyttöpäivä: 30. tammikuuta 2010. Arkistoitu alkuperäisestä 15. maaliskuuta 2010. (määrätön)
↑ Hugo Zaragoza, Nick Craswell, Michael Taylor, Suchi Saria ja Stephen Robertson. Microsoft Cambridge TREC-13:ssa: Web- ja HARD-kappaleet. Arkistoitu 26. elokuuta 2009 Wayback Machinessa In Proceedings of TREC-2004, 2004.

Kirjallisuus

Stephen E. Robertson, Steve Walker, Susan Jones, Micheline Hancock-Beaulieu ja Mike Gatford. Okapi TREC-3:ssa. julkaisussa Proceedings of the Third Text Retrieval Conference (TREC 1994). Gaithersburg, USA, marraskuu 1994.
Stephen E. Robertson, Steve Walker ja Micheline Hancock-Beaulieu. Okapi TREC-7:ssä. Seitsemännen tekstinhakukonferenssin julkaisussa. Gaithersburg, USA, marraskuu 1998.
Karen Spärck Jones, Steve Walker ja Stephen E. Robertson. Todennäköisyyspohjainen tiedonhaun malli: kehitys ja vertailevat kokeet (osat 1 ja 2). Tietojenkäsittely ja hallinta, 36(6):779-840. 2000.
Nick Craswell, Hugo Zaragoza, Stephen Robertson. Microsoft Cambridge TREC-14:ssä: Enterprise Track. Proceedings of the Fourteenth Text Retrieval Conference (TREC 2005). Gaithersburg, USA, marraskuu 2005. Kuvaa Okapi BM25F:n sovellusta ja viritystä.